The Minesweeper code kata is a little programming exercise focusing on a subset of the well-known Minesweeper game that comes with a certain operation system. Its assignment is to write a program which accepts an input of arbitrary mine fields, with mine locations marked, and produces the full mine field with all hint values calculated. For example, given the following 4 times 4 mine field
4 4 *... .... .*.. ...., the same mine field including the hint numbers would look like
*100 2210 1*10 1110
The ChallengeRecently the local functional programming group, the Lambdaheads, announced their Minesweeper Challenge. Being a functional programming group, most of the presented solutions used Haskell, F# and other functional languages. I participated and showed them my highly factored object orientated solution in Java, which surely looked as strange to them as their Haskell code was for me.
After seeing a solution in plain C, one participant joked that someone should use Assembly to show an even more low-level implementation. I agreed, it seemed like a great idea at that time, almost as cool as implementing Game of Life in XSLT. As usual I could not let got of the crazy idea. After my first steps in Windows 32 Assembly I was ready for a more complex task.
What about testing?
Although there are people test driving their Assembly, I could not find real unit testing support. The official way to go is to use C/C++ unit testing frameworks and write tests against the global functions in the generated OBJ files. I did not want to learn C this day and created (sort of) an integration test by feeding some mine field into Minesweeper's Standard Input and checking the output manually. Yes, I could have created a minimalist unit testing framework, which is a great exercise to get to know a new language by itself and I have done so in the past, just to keep the flow of TDD. I will come back to this topic later. (Thank you Emmanuel for reminding me of my duties ;-)
Getting Feedback
I wanted to get as much feedback as possible. Feedback is critical when working in an environment as unforgiving as Assembly. In the beginning my integration test did not help me and I split the implementation of my Minesweeper into four parts: Reading Input -> Creating Hints -> Preparing Output -> Printing Results. I decided to work backwards so I could use the result printing to give me feedback about the other stages.
Printing Results
In the beginning the mine field's
grid would be a constant string.max_dimension equ 99 ; temp data grid: times max_dimension * max_dimension db 'x' width: dd 4 height: dd 4Starting with Hello World I incrementally added to the output until
_printGrid would print grid line by line to Standard Out. Then I added support for mine fields of any dimension, using width and height._printGrid:
; local variables, starting memory[ebp - 4]
numberOfBytesWritten equ -1 * register_size
enter_method 1 ; stack frame (macro)
push esi
push edi
; get handle for stdout
push STD_OUTPUT_HANDLE
call _GetStdHandle@4
mov ebx, eax ; hStdOut
.loop_all_lines: ; for (edi = height; edi > 0; edi--)
mov esi, 0 ; address of current line
mov edi, [height] ; loop counter
.loop:
; write the next line
; BOOL WriteFile( hstdOut, message, length(message), &bytes, null);
push NULL
lea edx, [ebp + numberOfBytesWritten]
push edx
push dword [width]
lea eax, [grid + esi]
push eax
push ebx ; hstdOut
call _WriteFile@20
; write a new-line
push NULL
lea edx, [ebp + numberOfBytesWritten]
push edx
push len_cr
push cr
push ebx
call _WriteFile@20
.next:
add esi, max_dimension ; go down to next line
sub edi, 1 ; edi--
jnz .loop ; edi > 0
pop edi ; drop stack frame
pop esi
exit_method
ret
cr:
db 13, 10 ; Windows \n\r
len_cr equ $ - crThe code above just loops all the grid's lines in esi and prints them followed by a Windows new-line each.Creating Hints
Next I made the
grid mutable by moving it into the data segment and put a real mine field into it.section .bss
max_dimension equ 4
last_field_in_grid equ max_dimension * max_dimension - 1
grid: resb max_dimension * max_dimension
width: resd 1
height: resd 1
...
_main:
; temp copy
mov [width], dword 3 ; 3x3 inside 4x4 total space
mov [height], dword 3
mov eax, [fake_grid + 0]
mov [grid + 0], eax
...
...
; test cases for solving the game
fake_grid:
db '---0---0---00000' ; empty
; db 'x--0---0---00000' ; upper left clip
; db '--x0---0---00000' ; upper right clipUsing _printGrid and these "test cases", I developed _solveGrid to count the number of mines each field is adjacent to._solveGrid:
push esi
push edi
.loop_all_fields_backwards: ; for (edi = last_field_in_grid; edi >= 0; edi--)
mov edi, last_field_in_grid
.loopFields:
cmp [grid + edi], byte is_bomb ; is it a bomb? (or incremented bomb field)
jb .nextField ; branch if less than bomb
; it is bomb, increment all neighbouring hints
.loop_all_neighbours_backwards: ; for (ecx = 7; ecx >= 0; ecx--)
mov ecx, 7 ; 8 neighbour coordinates to test
.loopNeighbours:
mov esi, edi ; add to current bomb's position...
add esi, dword [around + ecx * register_size]
cmp esi, last_field_in_grid ; is the neighbour position valid?
ja .nextNeighbour ; neighbour position is outside
add [grid + esi], byte 1 ; else add bomb count for neighbour
.nextNeighbour:
sub ecx, 1 ; ecx--
jnc .loopNeighbours ; ecx >= 0
.nextField:
sub edi, 1 ; edi--
jnc .loopFields ; edi >= 0
pop edi
pop esi
ret
is_bomb equ 'x'
around: dd - max_dimension - 1
dd - max_dimension
dd - max_dimension + 1
dd - 1
dd 1
dd max_dimension - 1
dd max_dimension
dd max_dimension + 1_solveGrid iterates all fields in grid using edi, even the ones outside the mine field. If the field is a bomb (contains an 'x'), The code loops ecx for all eight neighbours and increments their field indexed by esi. This adds one to byte value that is there, even if it is a bomb. That works as long as the bomb symbol has an ASCII value of at least 9 higher than the symbol of the empty space. In the edges of the field not all neighbours exist, so esi is clipped by last_field_in_grid which prevents array overflow. Interestingly there is no need to test for underflow, i.e. negative indices in esi, because these are also skipped by branch instruction ja. (The actual bit value of negative values is above last_field_in_grid.)Preparing Output
After counting the adjacent bombs,
grid contains the needed information but is not ready to be printed. For example hints need to be numbers._formatGrid:
push esi
push edi
.loop_all_fields_backwards: ; for (edi = last_field_in_grid; edi >= 0; edi--)
mov edi, last_field_in_grid
.loopFields:
cmp [grid + edi], byte is_bomb ; is it a bomb?
jnb .formatBomb ; bombs are increased as well, so we check for >=
.formatHint: ; it is a hint, need to make it a number
add [grid + edi], byte emptyToHint
jmp .nextField
.formatBomb: ; it is a bomb, reset symbol
mov [grid + edi], byte bomb
.nextField:
sub edi, 1 ; edi--
jnc .loopFields ; edi >= 0
pop edi
pop esi
ret
is_empty equ '-'
emptyToHint equ '0' - is_empty
bomb equ 'B'This resets bombs to their symbol and converts hints into decimal numbers. emptyToHint is the difference between the input character of the original mine field and the wanted hint digits. For example, if a field was incremented three times it contains '-' + 3 + '0' - '-' = '0' + 3 = '3' now, which is exactly what is need.Reading Input
Finally I reached the fourth part of the implementation, reading the mine field from Standard Input. Reading the actual grid was similar to writing it, just the opposite direction of data flow, e.g. using
_ReadFile@20 system call instead of _WriteFile@20 and skipping the new-line instead of writing it. More interesting was reading the first line containing the dimensions of the grid because these contain decimal numbers of arbitrary length._readDigit:
; parameters
fileReadHandle equ 4 + 1 * register_size
; local variables
numberOfBytesRead equ -1 * register_size
byteBuffer equ -2 * register_size
number equ -3 * register_size
enter_method 3
mov [ebp + number], dword 0
.read_next_character:
lea edx, [ebp + numberOfBytesRead] ; lpNumberOfBytesRead
lea eax, [ebp + byteBuffer] ; lpBuffer
mov ebx, [ebp + fileReadHandle] ; hstdIn
; read a single character
push NULL
push edx
push dword 1
push eax
push ebx
call _ReadFile@20
mov eax, [ebp + byteBuffer]
and eax, 0xff
cmp eax, '0'
jb .finished
sub eax, '0'
; multiply by 10 and add new number
mov ebx, [ebp + number]
shl ebx, 1 ; * 2
mov ecx, ebx
shl ecx, 2 ; * 8
add ebx, ecx ; = * 10
add ebx, eax
mov [ebp + number], ebx
jmp .read_next_character
.finished:
mov eax, [ebp + number]
exit_method
ret_readDigit reads bytes from its input until it finds something that is white-space. In fact everything that has an ASCII value less than '0' is considered white-space. The currently read value is converted to a number by subtracting the ASCII value of '0' and added as next digit. Of course this is extremely simplified, as extra white-space, Windows new-lines or unexpected characters completely mess up the logic. Fortunately this is just a kata and no production code ;-)Completed
The reading of the input completed the Minesweeper Kata in Assembly. To avoid repetition I separated the Standard In/Out handles from their actual usage and provided them as arguments to the functions. The final main entry point looked like that:
global _main
_main:
call _getStdInFileHandle
push eax ; hstdOut 3 times for next calls
push eax
; read width
push eax
call _readDigit
add esp, register_size ; clean up parameter
mov [width], eax
; read height
; 2nd eax still pushed
call _readDigit
add esp, register_size
mov [height], eax
; read grid
; 3rd eax still pushed
call _readGrid
add esp, register_size
call _solveGrid
call _formatGrid
call _getStdOutFileHandle
push eax ; hstdOut
call _printGrid
add esp, register_size
jmp _exitIf you want to see the whole kata, the complete source in here.Done?
The kata is finished, but there are several issues remaining. Its design was influenced by my need for feedback through the console output. I am wondering how an implementation would look like if I had followed a strict TDD approach. I guess it would be less coupled to system calls at least. Also I am unhappy with its internal coupling. All four major functions depend on the
grid and its internal structure, e.g. they need to know max_dimension. Following D.L. Parnas' criteria to decompose systems, it would be favourable to decouple the data from the different algorithms. The grid could be wrapped in its own module (OBJ) allowing only API access, which would add indirection, a lot of subroutine calls and the need to copy data around. This feels against the spirit of raw Assembly. It seems I will have to revisit Minesweeper again.
2 comments:
thanks for sharing code about minesweeper
how to play minesweeper
thanks for sharing a very good information on play minesweeper online
Post a Comment