Tic Tac Toe in x86
You must write a small report (1 to 4 pages, no images, no source listings) explaining how you haveimplemented the program.
You can reference the project guidelines and the code, but the goal is to show your thought process in reverse engineering the program, and your thoughts on how the implementation compares to yours in terms of execution speed, RAM usage, code size, and code readability.
Example 1:
Do not say that a function “computes the result of a1*b1and then adds to it the result of a1*b”. Instead say that the function “computes the vector product of A =[a1a2] and B=[b1b2]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.
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.
AHMED_TTT.asm
;; Name: Ahmed Alkaabi
;; Email: [email protected]
section .data
msg1 db “Do you want to enable debug information?”,0xA,0xD
len1 equ $-msg1
msg2 db “Player X, choose your location (1-9): “,0xA,0xD
len2 equ $-msg2
msg3 db “Current board:”,0xA,0xD
len3 equ $-msg3
row1 db ” | | “,0xA,0xD
db “—–“,0xA,0xD
row2 db ” | | “,0xA,0xD
db “—–“,0xA,0xD
row3 db ” | | “,0xA,0xD
lenb equ $-row1
dbg1 db ” 012345678 “,0xA,0xD
arr1 db “[ ]”,0xA,0xD
lend equ $-dbg1
msg5 db “That location is out of range or already taken.”,0xA,0xD
len5 equ $-msg5
msg6 db “The game is a draw!”,0xA,0xD
db “Final board:”,0xA,0xD
len6 equ $-msg6
msg7 db “Player X wins!”,0xA,0xD
db “Final board:”,0xA,0xD
len7 equ $-msg7
eol db 0xA,0xD
eol_len equ $-eol
board db 0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x20
mark db “XO”
player db 0
debug db 0,0
move db 0,0
section .bss
section .text
global _start
;; print_string subroutine
;; prints a string using sys_write
;; on entry: edx = number of bytes to print
;; ecx = address of string
print_string: ; defining function print_string
mov ebx, 1 ; print to stdout
mov eax, 4 ; sys write function
int 0x80 ; call kernel
ret ; return from subroutine
;; read_string subroutine
;; reads a string using sys_read
;; on entry: edx = number of bytes to print
;; ecx = address of read buffer
read_string: ; defining function read_string
mov eax, 3 ; sys read function
mov ebx, 2 ; read from stdin
int 0x80 ; call kernel
ret ; return from subroutine
;; print_current_board subroutine
;; prints the current board using the board template and the current board
print_current_board:
;; fill row 1 of the board template with current board contents
mov edi,row1 ; load row1 address in edi
mov esi,board ; load board address in esi
mov ecx,3 ; load ecx to loop 3 times (3 chars per row)
setrow1:
mov al,[esi] ; load a char from the board
mov [edi],al ; save char in the template
inc esi ; go to next char in board
add edi,2 ; go to next position in template, skipping the column separator
loop setrow1 ; repeat 3 times while ecx is not zero
;; fill row 2 of the board template with current board contents
mov edi,row2 ; load row2 address in edi
mov ecx,3 ; load ecx to loop 3 times (3 chars per row)
setrow2:
mov al,[esi] ; load a char from the board
mov [edi],al ; save char in the template
inc esi ; go to next char in board
add edi,2 ; go to next position in template, skipping the column separator
loop setrow2 ; repeat 3 times while ecx is not zero
;; fill row 3 of the board template with current board contents
mov edi,row3 ; load row3 address in edi
mov ecx,3 ; load ecx to loop 3 times (3 chars per row)
setrow3:
mov al,[esi] ; load a char from the board
mov [edi],al ; save char in the template
inc esi ; go to next char in board
add edi,2 ; go to next position in template, skipping the column separator
loop setrow3 ; repeat 3 times while ecx is not zero
;; print the template board
mov ecx,row1 ; load address of start of template
mov edx,lenb ; load length of board template
call print_string ; print it on the screen
ret ; return from subroutine
;; print_board subroutine
;; prints the current board and a message on top of it
print_board:
;; print message “Current board”
mov ecx,msg3 ;load address of message in ecx
mov edx,len3 ; load length of message in edx
call print_string ; print the message in the screen
call print_current_board ; print the current board using the function
ret ; return from subroutine
;; debug_current_board subroutine
;; prints the current debug board
debug_current_board:
;; fill array 1 with current board contents
mov edi,arr1+1 ; load address of the debug board template in edi, just after the ‘[‘
mov esi,board ; load address of board in esi
mov ecx,9 ; load ecx to loop 9 times (9 chars in the board)
copyarr1:
mov al,[esi] ; load a char from the board
mov [edi],al ; save char in the debug template
inc esi ; go to next char in board
inc edi ; go to next char in debug template
loop copyarr1 ; repeat 9 times while ecx is not zero
;; print entire debug board template
mov ecx,dbg1 ; load address of start of template
mov edx,lend ; load length of debug board template
call print_string ; print it on the screen
ret ; return from subroutine
;; debug_board subroutine
;; prints the current debug board and a message on top of it
debug_board:
;; print message “Current board”
mov ecx,msg3 ;load address of message in ecx
mov edx,len3 ; load length of message in edx
call print_string ; print the message in the screen
call debug_current_board ; print the current debug board using the function
ret ; return from subroutine
;; is_tie subroutine
;; if the board is a tie returns eax=1, otherwise returns eax=0
;; on exit: eax = 0 if is a tie
;; 1 if it’s not a tie
is_tie:
mov eax,0 ; initialize eax to zero to return no tie by default
mov esi,board ; load address of board in esi
mov ecx,9 ; load ecx to loop 9 times (9 chars in the board)
find20:
cmp BYTE [esi],0x20 ; see if the curren position in the board has a empty space (0x20)
je nope ; if so, then the board is not yet full, return no tie
inc esi ; otherwise, increment esi to go to next character in board
loop find20 ; repeat 9 times while ecx is not zero
mov eax,1 ; if we get here, we have found no spaces on the board so it is full, return tie=1
nope:
ret ; return from subroutine
;; is_full subroutine
;; if 3 positions on the board separated by ebx are the same and are not spaces
;; it returns al = repeated mark, otherwise returns al = 0x20 (space)
;; On entry: esi = start address of the characters to compare
;; ebx = separation between the characters to compare
;; On exit: al = 0x20 if no repeated characters are found or if there was a space
;; ‘X’ if there were 3 repeated X characters
;; ‘O’ if there were 3 repeated O characters
is_full:
push rsi ; save rsi register on the stack
mov al,0x20 ; set al to 0x20 to return no repeated characters by default
mov ah,BYTE [esi] ; load character at given start position into ah
cmp ah,0x20 ; compare loaded character with space
je noteq ; if it was a space, exit, there were no repeated chars
add esi,ebx ; otherwise, go to next character by incrementing the addres by the given separation ebx
cmp ah,BYTE [esi] ; compare the initial character with the character at second position
jne noteq ; if they are not equal, exit, there were no repeated chars
add esi,ebx ; otherwise, go to next character by incrementing the address by the given separation ebx
cmp ah,BYTE [esi] ; compare the initial character with the character at third position
jne noteq ; if they are not equal, exit, there were no repeated chars
;; if we get here, the initial char was equal to the second and to the third one
;; and there were no spaces so ah has the repeated character
mov al,ah ; move it to al to return it as the character repeated 3 times
noteq:
pop rsi ; restore rsi register from the stack
ret ; return from subroutine
;; is_win subroutine
;; if there is a winner returns the mark for the winner, otherwise it returns 0x20
;; On exit: al = 0x20 if no 3 repeated characters are found (no winner)
;; ‘X’ if there were 3 repeated X characters, winner is X
;; ‘O’ if there were 3 repeated O characters, winner is O
is_win:
;; try to find repeated marks in the rows first
mov ecx,3 ; load ecx to loop 3 times (3 chars per row)
mov esi,board ; load board address in esi
mov ebx,1 ; compare elements separated by 1
cmprows: ; loop through each row
call is_full ; call is_full to see if three characters in a row are equal
cmp al,0x20 ; see if it returned 0x20
jne winret ; if it wasn’t 0x20, it found a character repeated 3 times in a row, this is the winner
add esi,3 ; advance to next row
loop cmprows ; repeat 3 times while ecx is not zero
;; try to find repeated marks in the columns
mov ecx,3 ; load ecx to loop 3 times (3 chars per column)
mov esi,board ; load board address in esi
mov ebx,3 ; compare elements separated by 3
cmpcols: ; loop through each column
call is_full ; call is_full to see if three characters in a column are equal
cmp al,0x20 ; see if it returned 0x20
jne winret ; if it wasn’t 0x20, it found a character repeated 3 times in a row, this is the winner
add esi,1 ; advance to next column
loop cmpcols ; repeat 3 times while ecx is not zero
;; try to find repeated marks in the main diagonal
mov esi,board ; load board address in esi
mov ebx,4 ; compare elements separated by 4
call is_full ; call is_full to see if three characters in the diagonal are equal
cmp al,0x20 ; see if it returned 0x20
jne winret ; if it wasn’t 0x20, it found a character repeated 3 times in the diagonal, this is the winner
;; try to find repeated marks in the lower diagonal
mov esi,board+2 ; load board address in esi
mov ebx,2 ; compare elements separated by 2
call is_full ; call is_full to see if three characters in the diagonal are equal
;; after this we simply return the result from is_full
winret:
ret ; return from subroutine
;; main procedure
_start:
;; prompt the user for the debug option
mov ecx,msg1 ;load address of message in ecx
mov edx,len1 ; load length of message in edx
call print_string ; print the message in the screen
;; read debug input from user
mov ecx,debug ;load address of buffer to read the input in ecx
mov edx,2 ; read two characters, the required char and the enter
call read_string ; read the character usign sys_read
cmp BYTE [debug],’Y’ ; compare the read debug option with Y
je debugy ; if the option entered Y, go to debugy
cmp BYTE [debug],’y’ ; compare the read debug option with y
je debugy ; if the option entered y, go to debugy
cmp BYTE [debug],’D’ ; compare the read debug option with D
je debugy ; if the option entered D, go to debugy
cmp BYTE [debug],’d’ ; compare the read debug option with d
je debugy ; if the option entered d, go to debugy
;; if we get here, the user entered a character other than Y,y,D,d
mov BYTE [debug],0 ; move zero to debug since the user select no debugging
jmp begin ; jump to start of game
debugy: ; if we get here, the user entered Y,y,D or d
mov BYTE [debug],1 ; move 1 to debug since the user select activate debugging
begin: ; start of game
;; prompt the user for the position to play
mov ecx,msg2 ;load address of message in ecx
mov edx,len2 ; load length of message in edx
call print_string ; print the message on the screen
test BYTE [debug],1 ; see if the debug option was selected by comparing with 1
jnz dbb1 ; if it’s not zero, debug is enabled, jump to dbb1
call print_board ; otherwise use the print_board subroutine to print the current board
jmp dbb2 ; skip the next instruction to continue
dbb1:
call debug_board ; if we get here, use the debug_board subroutine to print the current board
dbb2:
;; read position from user
mov ecx,move ;load address of buffer to read the input in ecx
mov edx,2 ; read two characters, the required char and the enter
call read_string ; read the character usign sys_read
sub BYTE [move],’1′ ; convert from ascii 1-9 to integer 0-8 by subtracting ‘1’ from the character
cmp BYTE [move],0 ; compare converted number with 0
jl outrange ; if it’s below 0 it’s out of range, go to outrange
cmp BYTE [move],8 ; compare converted number with 8
jg outrange ; if it’s above 8 it’s out of range, go to outrange
;; see if the board location is free
movzx ebx,BYTE [move] ; load the position selected by the user into ebx
mov edi,board ; load board address in edi
cmp BYTE [edi+ebx],0x20 ; compare the selected position on the board with an empty space
jne outrange ; if they are not equal the position is taken, go to outrange
;; get player mark
movzx ecx,BYTE [player] ; load the current player (0 or 1) into ecx
mov esi,mark ; load the address of the marks into esi
mov al,[esi+ecx] ; get the mark for the current player into al
mov [edi+ebx],al ; make the move to the selected position by writing the player mark on the board
call is_win ; see if a player has won the game by calling is_win
cmp al,0x20 ; see if the subroutine returned a space (no winner)
jne winend ; if is not space, it found the winner with mark O or X in al, end the game going to winend
call is_tie ; see if the game is tied by calling the subroutine is_tie
cmp eax,1 ; see if the subroutine returned a 1 (tie)
je tieend ; if it returned 1, the game is a tie, end the game going to tieend
xor BYTE [player],1 ; if no tie and no winner, change turn by using the xor which inverts either 0 to 1 or 1 to 0
;; modify the prompt message to use the current player mark
movzx ebx,BYTE [player] ; load the current player (0 or 1) into ecx
mov esi,mark ; load the address of the marks into esi
mov al,[esi+ebx] ; get the mark for the current player into al
mov edi,msg2 ; load address of the prompt message into edi
mov [edi+7],al ; change the mark shown in the message to the mark for the current player
jmp begin ; go back to the beginning so the new player can make a move
outrange: ; we get here when the read position is out of range or the position is taken
;; we simply print an error message to indicate the error and then repeat the prompt
mov ecx,msg5 ;load address of message in ecx
mov edx,len5 ; load length of message in edx
call print_string ; print message on the screen
jmp begin ; repeat from the start to ask for a new position
tieend: ; we get here when a tie is found, we simply print the game is a draw, print
;; the board and exit the game
mov ecx,msg6 ;load address of message in ecx
mov edx,len6 ; load length of message in edx
call print_string ; print the message on the screen
jmp last_board ; go to last_board to print the last board and exit
winend: ; we get here when a winner is found, we simply print the win message
;; and the winner mark, print the last board and exit
;; first, change the mark of the winner in the win message
mov edi,msg7 ; load address of win message into edi
mov [edi+7],al ; change the mark for the winner in the win message
;; print the game is a win and show the mark for the winner
mov ecx,msg7 ;load address of message in ecx
mov edx,len7 ; load length of message in edx
call print_string ; print message on the screen
last_board: ; print last board
test BYTE [debug],1 ; see if the debug option was selected by comparing with 1
jnz dbb3 ; if it’s not zero, debug is enabled, jump to dbb3
call print_current_board ; otherwise use the print_board subroutine to print the last board
jmp endgame ; skip the next instruction to continue
dbb3:
call debug_current_board ; if we get here, use the debug_board subroutine to print the current board
endgame: ; end of game, exit to os by calling the kernel
mov eax,1 ; system call number
int 0x80 ; call kernel
Jorge_TTT_sanitized.asm
; CMPE 310 – Fall 2017 – Project 1 – TicTacToe
; Jorge Teixeira
%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_t msgl
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_t msgl
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
; CMPE 310 – Fall 2017 – Project 1 – TicTacToe
; Jorge Teixeira
%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 X character in mPXO
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” ; hexadecimal representation of the board
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 ; position, hexadecimal value and character of a board site
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_t msgl
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_t msgl
mov eax,3 ; System call number (sys_read)
xor ebx,ebx ; First argument: file descriptor (stdin == 0)
int 0x80 ; Call kernel
ret
check_line: ; is a procedure to compare 2 positions in the board with bl
mov bl,[mPXO+spot] ; gets the character in the message, which will have the current player
add bl,bl ; multiply by two so subtracting twice results in zero
sub bl,[board+esi] ; subtract the character at position esi
sub bl,[board+edi] ; subtract the character at position edi
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] ; rdi points to the lowest part of the position in the message, increment it
mov bl,[rsi] ; get a character from the board and save it in the message
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 ax in the message, ax has the hexadecimal representation of the character in the board
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],’/’ ; put the / character in the message in the lowest part of the hexadecimal position
ret
print_board:
xor esi,esi ; initialize esi to zero
nrow:
mov edi,2 ; initialize edi to count 3 columns from 2 to 0
ncol:
mov dl,[board+esi+edi] ; get board character at row edi and column esi
mov [pbd1+edi*2],dl ; save the character in the message
dec edi
jns ncol ; repeat while the value in edi is positive or zero
mov ecx,pbd1 ; Second argument: pointer to message to write
add esi,3 ; advance to next row in the board
cmp esi,9 ; compare with total of characters in 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
; if the read character was Y,y,D or d, go to do_debug
cmpb [buffer],’Y’
je do_debug
cmpb [buffer],’y’
je do_debug
cmpb [buffer],’D’
je do_debug
cmpb [buffer],’d’
je do_debug
; if it was another character, put the print_board address in pfunc
movq [pfunc],print_board
jmp play
do_debug:
movq [pfunc],debug_board
mov ecx,15 ; ecx will count the number of hexadecimal digits to be printed including 0
mov rdx, board ; get the address of the board in rdx
mov rbx, hexdigits ; get the table address for translating from integer to hexadecimal
memheader:
mov rax,rdx ; put the current part of the board address into rax
and rax,0x000000000000000f
xlatb ; take the bits 0 to 3 of the address and get the translation to hexadecimal using the table
mov byte [mboard+ecx],al
dec ecx
mov rax,rdx ; put the current part of the board address into rax
and rax,0x00000000000000f0
shr rax,4 ; take the bits 4 to 7 of the address and put them in the bitx 0 to 3 in rax
xlatb ; get the translation of the bits 0 to 3 to hexadecimal using the table
mov byte [mboard+ecx],al
shr rdx,8 ; update the address moving the bits 8-15 to the lower position in rdx
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′ ; translate the read character from ascii to 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 move in the board
; determine if there was a winner
movzx ecx, byte [kek+eax] ; get the number of neighbors to look for a win from the move position
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 comparing each pair of positions with the move until all relevant neighbors are compared
decb [top] ; decrement the number of available moves
jz tie
xorb [mPXO+spot],magic ; change the turn using magic
jmp play
The program Jorge_TTT uses a similar approach to my code, where the messages are modified in order to display the current player and display the current board. However, there are many more optimizations in Jorge’s code. For example, in my program I use a complete board template in the print_board subroutine which I modify every time the board must be printed. In Jorge’s code, the template is not the complete board but only the template of a row. Jorge’s code uses several optimizations for displaying the debug board. One of them is to use a direct translation from the board characters to hexadecimal, this code uses a series of comparisons to translate the character. I think this part could be simplified further by using a lookup table, the entries could be selected by using the bits 4 and 5 from the character since the space (hex 0x20) has bits 10 (2), the X (hex 58) has bits 01 and the O (hex 0x4f) has bits 00. Thus, a table with three entries would give the translation directly with 3 instructions, an and, a shift and a table translation. Another code optimization can be found for selecting the routine to print the board, the address of the subroutine to use is saved into a variable, this simplifies calling the function and avoids doing comparisons as in my code. The most surprising trick was the use of a table to hold the possible positions to check for a given move, that is, the lol table. In my code I used loops and a special function to check if 3 positions at arbitrary distances from each other contain repeated characters. In Jorge’s code there is also a routine to check for 3 repeated characters but the positions are not calculated but read from the lol table which simplifies the code a bit. A surprisingly simple solution was used for determining the ties, count the number of characters on the board, updating the count with every move, it is now obvious to me that this was the best way to do it and that there is no need to recount the characters in the board every time there is a move. Another quite interesting optimization is the way to change the current player, in my code I use a variable that is either 0 or 1 to indicate the player so a simple xor with 1 switches the player. However, I must also use a table to get the actual player character. In Jorge’s code the switch is direct, xoring the player character with 0x17 “magic”, which changes one player character into the other.