; Quiz 3 Solutions v1 through v4
; Serguei Mokhov, mokhov@cs.concordia.ca

global _start

; A macro to print out a (text) buffer
; of a certain length
;
; Synopsis:
;   print <buffer>, <length>

%macro print 2
    mov ecx, %1
    mov edx, %2
    mov ebx, STDOUT
    mov eax, WRITE
    int 0x80
%endmacro

%macro endl 0
    print eol, 2
%endmacro

;
; Initialized data segment
;

segment .data

EXIT   equ 1
READ   equ 3
WRITE  equ 4

STDIN  equ 0
STDOUT equ 1

DIM_X  equ 10
DIM_Y  equ 10
BSIZE  equ 40

grid db '..........'
     db '..........'
     db '..........'
     db '..........'
     db '..........'
     db '..........'
     db '..........'
     db '..........'
     db '..........'
     db '..........'

eol db 0xA, 0xA

    ;
    ; Some user-friendliness will never hurt.
    ;

    msg_original_grid     db "Original grid: "
    msg_original_grid_len equ $ - msg_original_grid

    msg_input_prompt      db "Please input some live cells, one pair of coordinates per line.", 0xA
                          db "Terminate the input by entering 'g'."
    msg_input_prompt_len  equ $ - msg_input_prompt


segment .bss

    ; Where the input goes
    line_buffer resb BSIZE
    result      resd 1

    ; ASCII Display
    display_ascii  resb 10 ; 10 ASCII digits
    display_length equ $ - display_ascii


segment .text

;
; The journey begins here...
;

_start:

    ; Input
    print msg_original_grid, msg_original_grid_len
    endl
    call printGrid

    print msg_input_prompt, msg_input_prompt_len
    endl
    call inputCells

    call printGrid

    ;
    ; Version 1 Test
    ;

    mov  bx, 0x0000
    call r_c_to_address
    call updateCellState

    mov  bx, 0x0201
    call r_c_to_address
    call updateCellState

    mov bx, 0x0808
    call r_c_to_address
    call updateCellState

    mov  bx, 0x0504
    call r_c_to_address
    call updateCellState

    mov  bx, 0x0203
    call r_c_to_address
    call updateCellState

    mov bx, 0x0909
    call r_c_to_address
    call updateCellState

    call printGrid

    ;
    ; Version 2 Test
    ;

    push grid
    call countLiveCells
    pop  ecx
    call to_ascii

    print display_ascii, display_length
    endl

    ;
    ; Version 3 Test
    ;

    push grid
    call toggleCells
    call printGrid

    ;
    ; Version 4 Test
    ;

    mov [grid + 0], dword 'O.O.'
    mov [grid + 4], dword 'O.O.'
    mov [grid + 8], dword 'O.O.'
    mov [grid + 12], dword '..O.'
    mov [grid + 16], dword 'O...'

    call printGrid

    mov  ebx, grid
    call copyLiveCells
    call printGrid

.exit:
    xor eax, eax
    inc eax
    xor ebx, ebx
    int 0x80

; ----------------------------------

;
; Version 1 Solution
;

updateCellState:
    ; Sum the row and column
    add bl, bh

    ; See if the sum is even or odd ((r + c) % 2)
    ; To do that, is just enough to check the rightmost bit
    ; of the result
    and bl, 1
    
    jz  .cellmustdie

    mov [grid + esi], byte 'O'
    ret

.cellmustdie
    mov [grid + esi], byte '.'
    ret

;
; Version 2 Solution
;

countLiveCells:
    ; Fix the offset within the stack
    push   ebp
    mov    ebp, esp

    ; Preserve the registers we use
    push   ebx
    push   ecx
    push   esi
    push   eax

    ; Get the address of the grid from the stack
    mov    ebx, [ebp + 8]

    ; Total length of grid in bytes (100)
    mov    ecx, DIM_X * DIM_Y

    ; Counter, initially 0
    xor    esi, esi

.again:
    ; Get element grid[ecx - 1]
    mov    al, [ebx + ecx - 1]

    cmp    al, 'O'
    jne    .next

    ; Count it if it were 'O'
    inc    esi

.next:
    loop   .again

    ; Return the value of the counter to the stack
    mov [ebp + 8], esi

    ; Clean up and return
    pop eax
    pop esi
    pop ecx
    pop ebx
    pop ebp

    ret

;
; Version 3 Solution
;

toggleCells:
    ; Fix displacement within the stack
    push ebp
    mov  ebp, esp

    push ebx
    push ecx
    push eax

    ; Get the address of the grid and set the count (100)
    mov  ebx, [ebp + 8]
    mov  ecx, DIM_X * DIM_Y

.again:
    ; Toggle liveness status of element grid[ecx - 1]
    mov  al, [ebx + ecx - 1]

    cmp  al, 'O'
    jne  .live

    mov  al, '.'
    jmp  .swap

.live:
    mov  al, 'O'

.swap:
    mov  [ebx + ecx - 1], al

    loop .again
    
    pop  eax
    pop  ecx
    pop  ebx
    pop  ebp

    ; Callee is responsible for clean up the address
    ret  4


;
; Version 4 Solution
;


copyLiveCells:

    ; Preserve the registers we alter
    push   ecx
    push   eax

    ; One row is 10 elements long    
    mov    ecx, DIM_X

.again:
    ; Get element grid[0][ecx - 1]
    mov    al, [ebx + ecx - 1]

    ; Are we alive? No -- skip.
    cmp    al, 'O'
    jne    .next

    ; Yes -- copy over to the next line.
    mov    [ebx + ecx - 1 + DIM_X], al

.next:
    loop   .again

    ; Restore context and return
    pop    eax
    pop    ecx

    ret

; ---------------------------------------

printGrid:

    ; pusha saves all resgistrs

    push eax
    push ebx
    push ecx
    push edx
    push esi

;------------------------

    mov ecx, DIM_Y
    xor esi, esi

.print_lines:

    push ecx

        mov eax, WRITE
        mov ebx, STDOUT
        mov ecx, grid
        add ecx, esi
        mov edx, DIM_X
        int 0x80

        mov eax, WRITE
        mov ebx, STDOUT
        mov ecx, eol
        mov edx, 1
        int 0x80

    pop ecx

    add esi, DIM_X

    loop .print_lines

; ----------------------

    mov eax, WRITE
    mov ebx, STDOUT
    mov ecx, eol
    mov edx, 2
    int 0x80

    pop esi
    pop edx
    pop ecx
    pop ebx
    pop eax

    ret


inputCells:

    pusha

.loop_forever:

    ; read line
    mov eax, READ
    mov ebx, STDIN
    mov ecx, line_buffer ; line buffer
    mov edx, BSIZE  ; length buffer
    int 0x80

    ; parse the input
    ; edx - input length
    call parse

    ; -> bl = r, bh = c
    ;    al = 'g'
    ;    al = -1 (error)

    cmp al, 'g'
    je .end_input

    cmp al, -1
    ; jump over initialization
    je .loop_forever

    ; convert r,c to d
    ; al = r, ah = c
    call r_c_to_address
    ; -> esi = d

    ; store 'O' at [grid + d]
    mov [grid + esi], byte 'O'

    jmp .loop_forever

.end_input:

    popa

    ret


parse:

    xor esi, esi
    xor edi, edi

    mov ecx, edx

.again:
    ; take one char at time
    ; until EOL or 2nd digit encountered

    cmp edi, 2
    je  .ret

    mov  al, [line_buffer + esi]

    cmp  al, 'g'
    je  .ret

    ; if it is a blank or a non-digit, skip

    ; if it is a first digit, convert to numeric
    ; and store in bl

    and  al, 0x0F
    cmp  al, 9

    jg   .next

    or   edi, edi

    jnz  .digitcount

    mov  bl, al

.digitcount:
    mov  bh, al
    inc  edi

    ; if it is a second digit, convert to numeric
    ; and store in bh

    ; if it is a 'g' ret it in al

    ; if one or both digits missing at EOL, return -1 in al

.next:
    inc  esi
    loop .again

.over:
    cmp  edi, 2
    je   .ret

    xor  al, al
    dec  al

.ret:
    ret

; al = r, ah = c
; Output: esi = d = DIM_X * r + c
r_c_to_address:
    push ebx
    push eax

    mov al, bl
    mov bl, DIM_X

    mul    bl
    
    ; add bh to the result above
    ; ax = bl * al

    add al, bh

    mov esi, eax
    and esi, 0x0000FFFF

    pop eax
    pop ebx

    ret


to_ascii:
    mov  eax, ecx

    xor  ecx, ecx ; counter of how many ASCII digits we will have received
    xor  ebx, ebx
    xor  edi, edi

.again:
    or   eax, eax   ; eax = 0? if yes, stop converting else divide

    jnz  .div

    inc  ecx
    jmp  .ret

.div:
    mov  ebx, 10
    xor  edx, edx
    div  ebx

    or   dl, 0x30

    ; Put the current ASCII character into the the end of the display buffer
    mov  [display_ascii + display_length - 1 + edi], dl
    dec  edi
    inc  ecx

    jmp  .again

.ret:

    ; Shift all ASCII digits towards the beginning of the buffer
    mov  edx, ecx ; return value

    mov  ebx, display_ascii
    add  ebx, display_length + 1
    sub  ebx, ecx

    xor  edi, edi

.shift:
    mov  al, [ebx + edi]
    mov  [display_ascii + edi], al
    mov  byte [ebx + edi], ' '
    inc  edi
    loop .shift

    ret