Assignment

Assembly Programming

You can reference the project guidelines and my code, but the goal is to show me your thought process in reverse engineering my program, neat new things you may have learned, and your thoughts on how my implementation compares to yours in terms of execution speed, RAM usage, code size, and code readability.

Do not bother explaining things that are obvious, or known in advance (“it implements TTT, uses read_int and print_int to read input and display messages, can print just the board or print debug information”, etc.). With the exception of any eventual “cool tricks”, it is unnecessary and undesirable to do a line-by-line commentary of the code.

Example 1: Do not say that a function “computes the result of a1*b1 and then adds to it the result of a2*b2”. Instead say that the function “computes the vector product of A =[a1 a2] and B=[b1 b2]T”.
Example 2: Do not say that “EAX is XORed with itself”. Instead say that “EAX is zeroed efficiently”.
With that said, you are encouraged to try to restore the [REDACTED] comments on the code. Not all of them were particularly informative initially, but obviously some of them shed light into non-obvious manipulations.
With the exception of lol, top, kek, and magic, all labels are “meaningful”, well, to me, at least!
Nothing in the source code is false nor deliberately misleading.

Jorge_TTT_sanitized.asm

%define cmpb      cmp byte

%define decb      dec byte

%define incb      inc byte

%define xorb      xor byte

%define movb      mov byte

%define movq      mov qword

section .bss                              ; Uninitialized data

buffer            resb  4

pfunc       resq  1

section .data                             ; Initialized data

mdbg        db          “Do you want to enable debug information?”, 0xA

mdbgl       equ         $ – mdbg

mPXO        db          “Player X”

mPXOl       equ         $ – mPXO

mplay2            db          “, choose your location (0-8):”, 0xA, “Current board:”, 0xA

mplay2l           equ         $ – mplay2

mwin2       db          ” wins!”, 0xA

mwin2l            equ         $ – mwin2

spot        equ         7           ; [REDACTED]

magic       equ         0x17  ; Magic! =D

mtie        db          “It’s a draw (tie)!”, 0xA

mtiel       equ         $ – mtie

mfinal            db          “Final board:”, 0xA

mfinall           equ         $ – mfinal

merr        db          “That location is out of range or already taken.”, 0xA

merrl       equ         $ – merr

pbd1        db          ” | | “, 0xA

pbd1l       equ         $ – pbd1

pbd2        db          “—–“, 0xA

pbd2l       equ         $ – pbd2

dbd1        db          ” 012345678 “, 0xA, “[”

dbd1l       equ         $ – dbd1

board       db          ”         ” ; 3×3 linearized game board

bdl               equ         $ – board

dbd2        db          “]”, 0xA

dbd2l       equ         $ – dbd2

ebd1        db          “Current board (hex):”, 0xA, ”  0  1  2  3  4  5  6  7  8 “, 0xA, “[”

ebd1l       equ         $ – ebd1

eboard            db          “20 58 20 4F 20 58 20 20 4F”  ; [REDACTED]

el                equ         $ – eboard

ebd2        db          “]”, 0xA

ebd2l       equ         $ – ebd2

hexdigits   db          ‘0123456789ABCDEF’

mbd1        db          “Current board (mem):”, 0xA, “&board = 0x”

mbd1l       equ         $ – mbd1

mboard            db          “FFFFFFFFFFFFFFFF”

ml                equ         $ – mboard

mbd2        db          0xA, “+offset / hex / ASCII”, 0xA

mbd2l       equ         $ – mbd2

mbd3        db          “0x0/: 58h X”, 0xA      ; [REDACTED]

mbd3l       equ         $ – mbd3

lol               db          2,1,6,3,8,4,9,9, \

2,0,7,4,9,9,9,9, \

1,0,8,5,6,4,9,9, \

5,4,6,0,9,9,9,9, \

5,3,7,5,8,0,6,2, \

4,3,8,2,9,9,9,9, \

8,7,3,0,4,2,9,9, \

8,6,5,4,9,9,9,9, \

7,6,5,2,4,0,9,9

top               equ         lol+7

kek               db          5,3,5,3,7,3,5,3,5

section .text                             ; Code

global      _start                              ; Export entry point

print_int:                                ;ecx: const char* msg, edx: size_tmsgl

mov         eax,4                   ; System call number (sys_write)

mov         ebx,1                   ; First argument: file descriptor (stdout == 1)

int         0x80                    ; Call kernel

ret

read_int:                                 ;ecx: char* msg, ; edx: size_tmsgl

mov         eax,3                   ; System call number (sys_read)

xor         ebx,ebx                       ; First argument: file descriptor (stdin == 0)

int         0x80                    ; Call kernel

ret

check_line:                               ; [REDACTED]

mov         bl,[mPXO+spot]          ; [REDACTED]

add         bl,bl                   ; [REDACTED]

sub         bl,[board+esi]          ; [REDACTED]

sub         bl,[board+edi]          ; [REDACTED]

jz          win

ret

tie:                                      ; No return, (it’s a tie)

mov         ecx,mtie                ; Second argument: pointer to message to write

mov         edx,mtiel+mfinall ; Third argument: message length

call  print_int

jmp               pfinalb

win:                                      ; No return, (someone won)

mov         ecx,mPXO                ; Second argument: pointer to message to write

mov         edx,mPXOl               ; Third argument: message length

call  print_int

mov         ecx,mwin2               ; Second argument: pointer to message to write

mov         edx,mwin2l              ; Third argument: message length

call  print_int

mov         ecx,mfinal              ; Second argument: pointer to message to write

mov         edx,mfinall             ; Third argument: message length

call  print_int

; Fallthrough

pfinalb:                                  ; No return, (print final board and exit)

call  [pfunc]

mov         eax,1                   ; System call number (sys_exit)

xor         ebx,ebx                       ; First syscall argument: exit code

int         0x80                    ; Call kernel

; No ret

debug_board:

mov         ecx,dbd1                ; Second argument: pointer to message to write

mov         edx,dbd1l+bdl+dbd2l     ; Third argument: message length

call  print_int

mov         ecx,8                   ; Locations

hexboard:

mov         bl,[board+ecx]

mov         dx,’20’

cmp         bl,’ ‘

cmove ax,dx

mov         dx,’58’

cmp         bl,’X’

cmove ax,dx

mov         dx,’4F’

cmp         bl,’O’

cmove ax,dx

mov         [eboard+2*ecx+ecx],al

mov         [eboard+2*ecx+ecx+1],ah

dec         ecx

jns         hexboard

mov         ecx,ebd1                ; Second argument: pointer to message to write

mov         edx,ebd1l+el+ebd2l      ; Third argument: message length

call  print_int

mov         ecx,mbd1                ; Second argument: pointer to message to write

mov         edx,mbd1l+ml+mbd2l      ; Third argument: message length

call  print_int

mov         rsi,board

mov         rdi,mbd3

memboard:

incb  [rdi+3]                       ; [REDACTED]

mov         bl,[rsi]                ; [REDACTED]

mov         [rdi+10],bl

mov         dx,’20’

cmp         bl,’ ‘

cmove ax,dx

mov         dx,’58’

cmp         bl,’X’

cmove ax,dx

mov         dx,’4F’

cmp         bl,’O’

cmove ax,dx

mov         [rdi+6],ax              ; [REDACTED]

mov         ecx,mbd3                ; Second argument: pointer to message to write

mov         edx,mbd3l               ; Third argument: message length

call  print_int

inc         rsi

cmp         rsi,board+9

jne         memboard

movb  [rdi+3],’/’             ; [REDACTED]

ret

print_board:

xor         esi,esi                       ; [REDACTED]

nrow:

mov         edi,2                   ; [REDACTED]

ncol:

mov         dl,[board+esi+edi]      ; [REDACTED]

mov         [pbd1+edi*2],dl         ; [REDACTED]

dec         edi

jns         ncol                    ; [REDACTED]

mov         ecx,pbd1                ; Second argument: pointer to message to write

add         esi,3                   ; [REDACTED]

cmp         esi,9                   ; [REDACTED]

je          pdone

mov         edx,pbd1l+pbd2l         ; Third argument: message length

call  print_int

jmp         nrow

pdone:

mov         edx,pbd1l               ; Third argument: message length

call  print_int

ret

_start:

; Enable debug?

mov         ecx,mdbg                ; Second argument: pointer to message to write

mov         edx,mdbgl               ; Third argument: message length

call  print_int

; Read answer

mov         ecx,buffer              ; Store input at location ‘buffer’

mov         edx,2                         ; Read these many bytes

call  read_int

; [REDACTED]

cmpb  [buffer],’Y’

je          do_debug

cmpb  [buffer],’y’

je          do_debug

cmpb  [buffer],’D’

je          do_debug

cmpb  [buffer],’d’

je          do_debug

; [REDACTED]

movq  [pfunc],print_board

jmp         play

do_debug:

movq  [pfunc],debug_board

mov         ecx,15                        ; [REDACTED]

mov         rdx, board              ; [REDACTED]

mov         rbx, hexdigits          ; [REDACTED]

memheader:

mov         rax,rdx                       ; [REDACTED]

and         rax,0x000000000000000f

xlatb                               ; [REDACTED]

mov byte          [mboard+ecx],al

dec         ecx

mov         rax,rdx                       ; [REDACTED]

and         rax,0x00000000000000f0

shr         rax,4                   ; [REDACTED]

xlatb                               ; [REDACTED]

mov byte          [mboard+ecx],al

shr         rdx,8                   ; [REDACTED]

dec         ecx

jns         memheader

jmp         play

invalid:

mov         ecx,merr                ; Second argument: pointer to message to write

mov         edx,merrl               ; Third argument: message length

call  print_int

; Fallthrough

play:

; Print messages and board

mov         ecx,mPXO                ; Second argument: pointer to message to write

mov         edx,mPXOl+mplay2l ; Third argument: message length

call  print_int

call  [pfunc]

; Read input

mov         ecx,buffer              ; Store input at location ‘buffer’

mov         edx,2;                        ; Read these many bytes

call  read_int

; Validate

movzx eax, byte [buffer]

sub         al,’0′                        ; [REDACTED]

cmp         al,8

ja          invalid

; Range is valid

cmpb  [board+eax],’ ‘         ; Is empty?

jne         invalid

; Move is fully valid

mov         bl,[mPXO + spot]

mov         [board+eax],bl          ; [REDACTED]

; [REDACTED]

movzx ecx, byte [kek+eax]     ; [REDACTED]

pair:

movzx esi, byte [lol+eax*8+ecx]

dec         ecx

movzx edi, byte [lol+eax*8+ecx]

call  check_line

dec         ecx

jns         pair                    ; [REDACTED]

decb  [top]                   ; [REDACTED]

jz          tie

xorb  [mPXO+spot],magic ; [REDACTED]

jmp               play 

Solution 

Jorge_TTT_sanitized.asm

%define cmpb      cmp byte

%define decb      dec byte

%define incb      inc byte

%define xorb      xor byte

%define movb      mov byte

%define movq      mov qword

section .bss                              ; Uninitialized data

buffer            resb  4

pfunc       resq  1

section .data                             ; Initialized data

mdbg        db          “Do you want to enable debug information?”, 0xA

mdbgl       equ         $ – mdbg

mPXO        db          “Player X”

mPXOl       equ         $ – mPXO

mplay2            db          “, choose your location (0-8):”, 0xA, “Current board:”, 0xA

mplay2l           equ         $ – mplay2

mwin2       db          ” wins!”, 0xA

mwin2l            equ         $ – mwin2

spot        equ         7           ; position of the player mark in the mPXO message

magic       equ         0x17  ; Magic! =D

mtie        db          “It’s a draw (tie)!”, 0xA

mtiel       equ         $ – mtie

mfinal            db          “Final board:”, 0xA

mfinall           equ         $ – mfinal

merr        db          “That location is out of range or already taken.”, 0xA

merrl       equ         $ – merr

pbd1        db          ” | | “, 0xA

pbd1l       equ         $ – pbd1

pbd2        db          “—–“, 0xA

pbd2l       equ         $ – pbd2

dbd1        db          ” 012345678 “, 0xA, “[”

dbd1l       equ         $ – dbd1

board       db          ”         ” ; 3×3 linearized game board

bdl               equ         $ – board

dbd2        db          “]”, 0xA

dbd2l       equ         $ – dbd2

ebd1        db          “Current board (hex):”, 0xA, ”  0  1  2  3  4  5  6  7  8 “, 0xA, “[”

ebd1l       equ         $ – ebd1

eboard            db          “20 58 20 4F 20 58 20 20 4F”  ; template used to display the linear board in hexadecimal

el                equ         $ – eboard

ebd2        db          “]”, 0xA

ebd2l       equ         $ – ebd2

hexdigits   db          ‘0123456789ABCDEF’

mbd1        db          “Current board (mem):”, 0xA, “&board = 0x”

mbd1l       equ         $ – mbd1

mboard            db          “FFFFFFFFFFFFFFFF”

ml                equ         $ – mboard

mbd2        db          0xA, “+offset / hex / ASCII”, 0xA

mbd2l       equ         $ – mbd2

mbd3        db          “0x0/: 58h X”, 0xA      ; template used for printing board positions and hex contents one line at a time

; position initialized to ‘/’ so an increment will bring it to ‘0’

mbd3l       equ         $ – mbd3

lol               db          2,1,6,3,8,4,9,9, \

2,0,7,4,9,9,9,9, \

1,0,8,5,6,4,9,9, \

5,4,6,0,9,9,9,9, \

5,3,7,5,8,0,6,2, \

4,3,8,2,9,9,9,9, \

8,7,3,0,4,2,9,9, \

8,6,5,4,9,9,9,9, \

7,6,5,2,4,0,9,9

top               equ         lol+7

kek               db          5,3,5,3,7,3,5,3,5

section .text                             ; Code

global      _start                              ; Export entry point

print_int:                                ;ecx: const char* msg, edx: size_tmsgl

mov         eax,4                   ; System call number (sys_write)

mov         ebx,1                   ; First argument: file descriptor (stdout == 1)

int         0x80                    ; Call kernel

ret

read_int:                                 ;ecx: char* msg, ; edx: size_tmsgl

mov         eax,3                   ; System call number (sys_read)

xor         ebx,ebx                       ; First argument: file descriptor (stdin == 0)

int         0x80                    ; Call kernel

ret

check_line:                               ; check if the two positions edi and esi in the board contain the current player mark

mov         bl,[mPXO+spot]          ; load the current player’s mark in bl

add         bl,bl                   ; put 2 times the current mark in bl

sub         bl,[board+esi]          ; subtract the character in position esi in the board from bl

sub         bl,[board+edi]          ; subtract the character in position edi in the board from bl

jz          win

ret

tie:                                      ; No return, (it’s a tie)

mov         ecx,mtie                ; Second argument: pointer to message to write

mov         edx,mtiel+mfinall ; Third argument: message length

call  print_int

jmp               pfinalb

win:                                      ; No return, (someone won)

mov         ecx,mPXO                ; Second argument: pointer to message to write

mov         edx,mPXOl               ; Third argument: message length

call  print_int

mov         ecx,mwin2               ; Second argument: pointer to message to write

mov         edx,mwin2l              ; Third argument: message length

call  print_int

mov         ecx,mfinal              ; Second argument: pointer to message to write

mov         edx,mfinall             ; Third argument: message length

call  print_int

; Fallthrough

pfinalb:                                  ; No return, (print final board and exit)

call  [pfunc]

mov         eax,1                   ; System call number (sys_exit)

xor         ebx,ebx                       ; First syscall argument: exit code

int         0x80                    ; Call kernel

; No ret

debug_board:

mov         ecx,dbd1                ; Second argument: pointer to message to write

mov         edx,dbd1l+bdl+dbd2l     ; Third argument: message length

call  print_int

mov         ecx,8                   ; Locations

hexboard:

mov         bl,[board+ecx]

mov         dx,’20’

cmp         bl,’ ‘

cmove ax,dx

mov         dx,’58’

cmp         bl,’X’

cmove ax,dx

mov         dx,’4F’

cmp         bl,’O’

cmove ax,dx

mov         [eboard+2*ecx+ecx],al

mov         [eboard+2*ecx+ecx+1],ah

dec         ecx

jns         hexboard

mov         ecx,ebd1                ; Second argument: pointer to message to write

mov         edx,ebd1l+el+ebd2l      ; Third argument: message length

call  print_int

mov         ecx,mbd1                ; Second argument: pointer to message to write

mov         edx,mbd1l+ml+mbd2l      ; Third argument: message length

call  print_int

mov         rsi,board

mov         rdi,mbd3

memboard:

incb  [rdi+3]                       ; increment the character representing the position

mov         bl,[rsi]                ; load the current char from the board and update template with it

mov         [rdi+10],bl

mov         dx,’20’

cmp         bl,’ ‘

cmove ax,dx

mov         dx,’58’

cmp         bl,’X’

cmove ax,dx

mov         dx,’4F’

cmp         bl,’O’

cmove ax,dx

mov         [rdi+6],ax              ; save board character translation to hex in the template

mov         ecx,mbd3                ; Second argument: pointer to message to write

mov         edx,mbd3l               ; Third argument: message length

call  print_int

inc         rsi

cmp         rsi,board+9

jne         memboard

movb  [rdi+3],’/’             ; restore the position in the template to ‘/’

ret

print_board:

xor         esi,esi                       ; initialize esi to zero

nrow:

mov         edi,2                   ; we will fill the 3 chars in a single row on the board template (0 to 2)

ncol:

mov         dl,[board+esi+edi]      ; load character from the board at the current position

mov         [pbd1+edi*2],dl         ; save the character in the board line template

dec         edi

jns         ncol                    ; repeat while edi is not negative

mov         ecx,pbd1                ; Second argument: pointer to message to write

add         esi,3                   ; advance to next row in the board by adding 3

cmp         esi,9                   ; if we get to position 9 we have printed all the board

je          pdone

mov         edx,pbd1l+pbd2l         ; Third argument: message length

call  print_int

jmp         nrow

pdone:

mov         edx,pbd1l               ; Third argument: message length

call  print_int

ret

_start:

; Enable debug?

mov         ecx,mdbg                ; Second argument: pointer to message to write

mov         edx,mdbgl               ; Third argument: message length

call  print_int

; Read answer

mov         ecx,buffer              ; Store input at location ‘buffer’

mov         edx,2                         ; Read these many bytes

call  read_int

; determine if the user entered Y, y, D or d

cmpb  [buffer],’Y’

je          do_debug

cmpb  [buffer],’y’

je          do_debug

cmpb  [buffer],’D’

je          do_debug

cmpb  [buffer],’d’

je          do_debug

; by default, use the print board function

movq  [pfunc],print_board

jmp         play

do_debug:

movq  [pfunc],debug_board

mov         ecx,15                        ; we will use it to loop 16 times

mov         rdx, board              ; load the board address in rdx

mov         rbx, hexdigits          ; load the hexadecimal table for translating digits

memheader:

mov         rax,rdx                       ; load the current address into rax

and         rax,0x000000000000000f

xlatb                               ; translate the lowest nibble to ascii using the hex table

mov byte          [mboard+ecx],al

dec         ecx

mov         rax,rdx                       ; restore the board address in rax

and         rax,0x00000000000000f0

shr         rax,4                   ; move the upper nibble of the first byte to the bottom

xlatb                               ; translate the second nibble to ascii using the hex table

mov byte          [mboard+ecx],al

shr         rdx,8                   ; update the address to print the next byte

dec         ecx

jns         memheader

jmp         play

invalid:

mov         ecx,merr                ; Second argument: pointer to message to write

mov         edx,merrl               ; Third argument: message length

call  print_int

; Fallthrough

play:

; Print messages and board

mov         ecx,mPXO                ; Second argument: pointer to message to write

mov         edx,mPXOl+mplay2l ; Third argument: message length

call  print_int

call  [pfunc]

; Read input

mov         ecx,buffer              ; Store input at location ‘buffer’

mov         edx,2;                        ; Read these many bytes

call  read_int

; Validate

movzx eax, byte [buffer]

sub         al,’0′                        ; convert the read ascii char to an integer

cmp         al,8

ja          invalid

; Range is valid

cmpb  [board+eax],’ ‘         ; Is empty?

jne         invalid

; Move is fully valid

mov         bl,[mPXO + spot]

mov         [board+eax],bl          ; save the current player mark to the selected position in the board

; check the board for a possible winner or tie

movzx ecx, byte [kek+eax]     ; get the number of positions to compare into ecx

pair:

movzx esi, byte [lol+eax*8+ecx]

dec         ecx

movzx edi, byte [lol+eax*8+ecx]

call  check_line

dec         ecx

jns         pair                    ; repeat while ecx>=0

decb  [top]                   ; decrement number of free positions

jz          tie

xorb  [mPXO+spot],magic ; change the player by xoring with ‘X’^’O’ = 0x17

jmp             play