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