Play the Simulation Game Life

Life was invented by the mathematician John Conway. The game board is a two-dimensional grid, on which each cell is either occupied or not. The next generation is calculated according to the following rules:

Some fascinating patterns can come from these simple rules as the generations unfold.

The program assumes that three variables can be accessed: a (the array), xsize (the size in the x dimension), and ysize (the size in the y dimension). It also uses two variables, curx and cury, to track its position in the array. The array uses one byte per cell, laid out in memory as the first row of xsize bytes, followed by the second row of xsize bytes, up until the ysizeth row of xsize bytes. A cell that is occupied has the value 1; an unoccupied cell has the value 0.

This fragment of code calculates only a single generation. The results for the next generation must be determined in their entirety before any of the cells are updated. The birth or death of a cell mustn't affect its neighbors in the current generation. To accomplish this, the program stores the current generation in the lowest bit of each cell and the next generation in the second bit. When it is done, it shifts every byte to the right by one bit.

Source Code

1. mov curx, 0 2. mov cury, 0 3. mov eax, a 4. 5. ; we jump up here each time we start 6. ; to calculate the results for a single cell. 7. ; That cell is at (curx, cury). 8. ; ecx holds the neighbor count for the cell. 9. outerloop: 10. mov ecx, 0 11. ; Figure out where to loop from in the ydir. 12. ; ebx holds the y loop counter. 13. mov ebx, cury 14. test ebx, ebx ; is ebx equal to 0? 15. je newrow ; in row 1, start in row 1 16. sub ebx, 1 ; not in row 1, start in row cury-1 17. newrow: 18. ; Figure out where to loop from in the xdir. 19. ; edi holds the pointer into the beginning of 20. ; the row and edx holds the x loop counter. 21. mov edi, ebx 22. imul edi, xsize 23. add edi, a ; edi is address of row ebx 24. mov edx, curx 25. test edx, edx 26. je countcell ; in col 1, start in col 1 27. sub edx, 1 ; not in col 1, start in col curx-1 28. countcell: 29. mov ch, [edi+edx] ; ch is value of a[edx,ebx] 30. and ch, 0xfd ; turn off the next generation bit 31. add cl, ch ; add to running count 32. and ch, 0x00 ; remove temp value from ch 33. 34. ; are we done in xdir? 35. cmp edx, curx 36. jg rowdone ; edx > curx, so row is done 37. inc edx 38. cmp edx, xsize 39. je rowdone ; edx == xsize, so row is done 40. jmp countcell ; count next cell 41. rowdone: 42. ; are we done in ydir? 43. cmp ebx, cury 44. jg cellcounted ; ebx > cury, so cell is done 45. inc ebx 46. cmp ebx, ysize 47. je cellcounted ; ebx == ysize, so cell is done 48. jmp newrow 49. cellcounted: 50. ; cell is done, so update and move to next one 51. ; first get current value of cell in ch 52. mov edi, cury 53. imul edi, xsize 54. add edi, curx 55. add edi, a ; edi is address of a[curx,cury] 56. mov ch, [edi] ; read current value into ch 57. 58. cmp ch, 1 ; is it on? 59. je cellon 60. cmp cl, 3 ; off: turn on if 3 neighbors 61. jne celldone 62. jmp turnon 63. 64. cellon: ; on: remain if 2 or 3 neighbors 65. cmp cl, 2 66. jl celldone 67. cmp cl, 3 68. jg celldone 69. 70. turnon: 71. or ch, 0x02 ; turn on bit 2 for next generation 72. mov [edi], ch 73. 74. ; now see where to go next 75. celldone: 76. inc curx 77. mov ebx, xsize 78. cmp curx, ebx ; if curx has reached xsize... 79. je nextrow ; ...go to next row 80. jmp outerloop ; otherwise count this cell 81. 82. nextrow: 83. mov curx, 0 ; back to column 0 84. inc cury 85. mov ebx, ysize 86. cmp cury, ebx ; if cury has not reached ysize... 87. jne outerloop ; ...count this cell 88. 89. ; done, so just shift the table right one bit 90. mov edi,a ; edi is start of array 91. mov ecx, xsize 92. imul ecx, ysize ; ecx is size of array 93. dec edi ; so loop starts and ends right 94. shiftloop: 95. shr [edi+ecx], 1 96. loop shiftloop

Suggestions

Because the assembly language is not indented, loops are not obvious. Identify the beginning and end of all the loops in the code.
Check that the counts for the top-left element (0,0) and the bottom-right element (xsize-1,ysize-1) are calculated correctly.
Verify that the next generation is properly prevented from interfering with the current generation.
Check that all the comparisons and resulting jumps are correct.

Hints

Because the code is complicated, there is only one hint, which is an array laid out as follows. (Cells that are on are shown as a 1; cells that are off are shown as a . for visual clarity, but really contain a 0.) This array has at least one instance of occupied cells with 2, 3, and 4 neighbors, as well as unoccupied cells with 1, 3, and 5 neighbors:

Explanation of the Bug

The program calculates the next-generation results incorrectly for cells that are on. Lines 64-68 appear to check it correctly:

However, the cell-counting loop counts the current cell also. So, for a cell that is on, the neighbor total will be one higher than expected. Thus, the code on lines 64-68 needs to read as follows

The result of this A.logic error is that existing cells survive if they have one or two neighbors, instead of two or three. This small change makes the simulation much bleaker-in particular, if a cell is born because it has three neighbors, it is likely that all four cells will die in the next generation because they all have three neighbors.