3
\$\begingroup\$

The rules of John Conway's Game of Life are simple:

  • An OFF pixel that has 3 live neighbours is turned ON.
  • An ON pixel that has anything other than 2 or 3 live neighbours is turned OFF.

Many people that program this game select the easiest of video modes: the 320x200 256-color mode. To satisfy my desire for a smooth animation and to really challenge myself, I chose to run the game on the legacy video mode with the highest spatial resolution. So mode 12h, a 640x480 16-color mode. That's a lot more pixels!

Key features

I never read the video memory (VRAM) because that would be extremely slow. I store info about what is displayed on the screen in a couple of matrices in regular memory. Both these matrices have the same dimensions and during the game, in preparation for the next generation, the contents of the 'WriteMatrix' is copied onto the 'ReadMatrix'. Although this is a fairly big copy, my tests have shown that using SIMD instructions wasn't worthwhile. What a pity!

I don't output a pixel at a time because on a planar video mode it would involve reading from the video memory in order to combine the new pixel with what is already displayed. My program outputs 32 pixels at once. And because the game is intrinsically monochrome it's enough to simply write to the video aperture. No need to use any of the VGA specifics (like ports).

Instead of counting the number of neighbours that are alive, I maintain info about how many live neighbours a pixel has in a 3-bit counter stored adjacent to the pixel's ON/OFF state. To enhance data density I store the information for 2 pixels in every byte-sized matrix element, using next layout:

    Pixel with an even X           Pixel with an odd X
-----------------------------  ----------------------------
bit 7         bits 6-4         bit 3         bits 2-0
ON/OFF state  Neighbour count  ON/OFF state  Neigbour count

The 3-bit field can not store the full neighbour count which ranges from 0 to 8, but the count can easily be completed using the state bit of the special 'closest' neighbour (held within the same matrix element).

The game's surface doesn't end at the edges of the screen! e.g. When a pixel moves off the screen's right edge, it re-enters via the left edge. This is true for all the edges. Think of the opposing edges of the screen being stitched together, producing a toroidal surface. This is the most interesting approach but also a little more involved. It's also the reason why my 2 matrices have an extra top and bottom line.

Running the program

The game begins with drawing approx. 50 % of ON pixels. As a leftover from experimentation (you are invited to experiment on this further) I leave the edges of the screen free from pixels. At this point the WriteMatrix is also initialized. After inspection of the initial screen a keypress is expected. I have not wasted any time optimizing this initialization phase.

When I do the matrix copying, I use rep movsw because that was the fastest. For the copies of the top and bottom lines, that require corrections because they are stitched to the opposite edges, I've unrolled the loop for best performance. Using the SIMD paddb instruction was marginally better, but I judged against it so that people that can't run this program from real address mode, could still run it from an emulator like DOSBox. Optimizing this part of the program is unlikely to speed up much, since it accounts for little over 1% of the execution time.

To produce the next generation I use a couple of nested loops. The outer loop runs in the Y direction and in order to minimize changing the segment registers I subdivided the operation in 3 bands that each process 160 lines. Because the pixel at the far left and the pixel at the far right are special in that they make changes at the opposite edges, I've peeled these off from the inner loop. The inner loop runs in the X direction and has been unrolled foremost because processing pixels at an even X or at an odd X is different anyway. These loops (and their subroutines) were heavily optimized to the extent that it's no longer nice code to look at. Hopefully the experts here can still give me some pointers.

The user can control the game via the keyboard. Pressing any key will halt the game and display in the upper left corner of the screen the number of pixels that changed state (in green) in the most recent generation (in red). The key that the user presses next decides about what happens then. ESC exits the program, SPC will rapidly produce the next generation and halt again, and any other key will continue the game at full speed.


I ran the program on a 1.73 GHz Pentium dual-core T2080.
The table below summarizes my tests (gps is GenerationsPerSecond):

Resolution Total time First sec. Last sec. Average
---------- ---------- ---------- --------- --------
640x480    24 s        216 gps    379 gps   352 gps ; Pulsar appears after 15 seconds!
640x400    16 s        268 gps    453 gps   410 gps
640x350    10 s        316 gps    516 gps   454 gps
320x200     4 s       1324 gps   1776 gps  1580 gps

The game 'ends' when there's but still-live and oscillators left.


I was somewhat disappointed about the speed gain from using SIMD instructions.
Does anyone know of a solution that leans more on using SIMD (up to SSE3)?

What would be a good method to detect that the game has fallen into merely oscillatting? I have tried the method of discovering a repeating pattern in the number of changed pixels. It works fine for my test data, but is this the way to go in general?

; John Conway's Game of Life (c) 2020 Sep Roland
; ----------------------------------------------
; assemble with FASM

SW=640                                  ; ScreenWidth
SH=480                                  ; ScreenHeight
LL=SW/2                                 ; LineLength (Matrices store 2 pixels
BW=SH/3                                 ; BandWidth     per byte-sized element)

        ORG     256

        cld
        mov     ax, 0A000h
        mov     gs, ax                  ; CONST VideoSegment
        mov     bx, cs
        add     bx, 256                 ; Align 4096 on matrices 
        mov     dx, 2*(LL*(SH+2))/16    ; ReadMatrix and WriteMatrix
        mov     ax, [0002h]             ; PSP.NXTGRAF
        sub     ax, dx
        cmp     ax, bx
        jb      Exit
        mov     [InitSRegs+2], bx       ; MemoryBase
        mov     sp, 0100h

        mov     ax, 0012h               ; BIOS.SetVideo graphics mode 640x480x4
        int     10h
        call    GameOfLife
        mov     ax, 0003h               ; BIOS.SetVideo text mode 80x25
        int     10h

Exit:   mov     ax, 4C00h               ; DOS.Terminate
        int     21h
; --------------------------------------
        ALIGN   4
X1      dw      1                       ; Window for initial pixels
Y1      dw      1
X2      dw      SW-2
Y2      dw      SH-2
; --------------------------------------
        db      (16-($+5)) and 15 dup 90h ; To align .NextG
; IN (bx,dx)
GameOfLife:
        call    InitMatricesAndScreen   ; -> (EAX BX..BP DS ES)
        xor     dx, dx                  ; Number of generations

.NextG: inc     dx
        call    CopyMatrices            ; -> (AX..CX SI..BP DS..FS)
        call    ProduceNextGeneration   ; -> CX (EAX BX SI..BP DS ES)
        ; Pause the game on presence of any key
        mov     ah, 01h                 ; BIOS.CheckKey
        int     16h                     ; -> AX ZF
        jz      .NextG
        mov     ah, 00h                 ; BIOS.GetKey
        int     16h                     ; -> AX

.ShowI: mov     bx, 000Ch               ; DisplayPage and LightRedOnBlack
        mov     ax, dx                  ; DX is number of generations
        call    .PrintNumber
        mov     bl, 0Ah                 ; LightGreenOnBlack
        mov     ax, cx                  ; CX is number of changed pixels
        call    .PrintNumber
        mov     ax, 0E0Dh               ; BIOS.Teletype
        int     10h

        ; Decide what to do next based on specific keys
        mov     ah, 00h                 ; BIOS.GetKey
        int     16h                     ; -> AX
        cmp     al, 27                  ; ESC is EndOfGame
        je      .End
        cmp     al, 32                  ; SPC is SingleStep
        jne     .NextG
        mov     cx, ax
        mov     ah, 05h                 ; BIOS.WriteKey
        int     16h
        jmp     .NextG
.End:   ret
; - - - - - - - - - - - - - - - - - - -
; IN (ax) OUT ()
.PrintNumber:
        pusha
        mov     di, 10
        push    " "                     ; Sentinel and separator
@@:     xor     dx, dx
        div     di
        add     dl, "0"
        push    dx
        test    ax, ax
        jnz     @b
@@:     pop     ax
        mov     ah, 0Eh                 ; BIOS.Teletype
        int     10h
        cmp     al, 32
        jne     @b
        popa
        ret
; --------------------------------------
; IN (bx,dx) OUT () MOD (eax,bx,cx,dx,si,di,bp,ds,es)
InitMatricesAndScreen:
        shr     dx, 1                   ; Leave ReadMatrix alone

; Clear WriteMatrix
        mov     bp, 4096                ; CONST
        xor     di, di
        xor     ax, ax
        jmp     .b
.a:     mov     cx, 65536/2             ; Clear 64KB
        rep stosw
        add     bx, bp                  ; BX is alias for ES
.b:     mov     es, bx
        sub     dx, bp
        ja      .a                      ; Have more than 64KB
        add     dx, bp
        imul    cx, dx, 16/2
        rep stosw

; Fill WriteMatrix and Screen with approx. 50% of ON pixels
        xor     bp, bp                  ; GS:BP is VideoPointer
        xor     si, si                  ; Random Seed
        mov     dx, SH-1                ; Y
        mov     cx, SW-1                ; X
        xor     bx, bx                  ; Offset (paragraphs) in WriteMatrix
.c:     push    bx                      ; (1)
        call    InitSRegs               ; -> AX=DS BX=ES
        mov     di, LL                  ; Current position in a 3-line window
.d:     call    .InitEvenPixel          ; -> EAX CX DX SI
        call    .InitOddPixel           ; -> EAX CX DX SI
        inc     di
        test    di, 15
        jnz     .e
        call    .WritePixels            ; -> BP (EAX)
.e:     cmp     di, LL*2                ; At end of line ?
        jb      .d                      ; No
        pop     bx                      ; (1)
        add     bx, LL/16               ; Window travels down in WriteMatrix
        cmp     bp, (SW/8)*SH           ; At end of screen ?
        jb      .c                      ; No

; Inspect the initial screen
        mov     ah, 00h                 ; BIOS.GetKey
        int     16h                     ; -> AX
        ret
; - - - - - - - - - - - - - - - - - - -
; IN (eax,cx,dx,si,ds:di) OUT (eax,cx,dx,si)
.InitEvenPixel:
        shl     eax, 1
        call    .DecideAboutPixel       ; -> CX DX SI SF
        js      @f
        inc     ax                      ; ON pixel
        add     word [di-1-LL],    0001'0001'0000'0001b
        add     word [di-1],       1000'0000'0000'0001b
        add     word [di-1+LL],    0001'0001'0000'0001b
@@:     ret
; - - - - - - - - - - - - - - - - - - -
; IN (eax,cx,dx,si,ds:di) OUT (eax,cx,dx,si)
.InitOddPixel:
        shl     eax, 1
        call    .DecideAboutPixel       ; -> CX DX SI SF
        js      @f
        inc     ax                      ; ON pixel
        add     word [di-LL],      0001'0000'0001'0001b
        add     word [di],         0001'0000'0000'1000b
        add     word [di+LL],      0001'0000'0001'0001b
@@:     ret
; - - - - - - - - - - - - - - - - - - -
; IN (cx,dx,si) OUT (cx,dx,si,SF)
.DecideAboutPixel:
        inc     cx                      ; Go to next (X,Y)
        cmp     cx, SW
        jb      @f
        xor     cx, cx
        inc     dx
        cmp     dx, SH
        jb      @f
        xor     dx, dx
@@:     cmp     cx, [cs:X1]             ; Confine to (X1,Y1)-(X2,Y2)
        js      @f
        cmp     dx, [cs:Y1]
        js      @f
        cmp     [cs:X2], cx
        js      @f
        cmp     [cs:Y2], dx
        js      @f
        imul    si, 25173               ; Next random number
        add     si, 13849
        xor     si, 62832
@@:     ret
; - - - - - - - - - - - - - - - - - - -
; IN (eax,gs:bp) OUT (bp) MOD (eax)
.WritePixels:
        bswap   eax
        mov     [gs:bp], eax            ; Writing 32 pixels at once
        add     bp, 4
        ret
; --------------------------------------
        ALIGN   16
; IN (bx) OUT (ax=ds,bx=es)
InitSRegs:                              ; BX is optional offset in paragraphs
        add     bx, word 0              ; SMC, MemoryBase
        lea     ax, [bx+(LL*(SH+2))/16]
        xchg    ax, bx
        mov     ds, ax                  ; DS refers to WriteMatrix or higher up
        mov     es, bx                  ; ES refers to ReadMatrix or higher up
        ret
        LEA     BX, [WORD BX+0]
        LEA     BX, [WORD BX+0]
; --------------------------------------
; IN () OUT () MOD (ax,bx,cx,si,di,bp,ds,es,fs)
CopyMatrices:                           ; Copies from WriteMatrix to ReadMatrix

; Copy all lines between top and bottom unmodified
        push    dx                      ; (1)
        mov     bx, (LL*2)/16
        call    InitSRegs               ; -> AX=DS BX=ES
        mov     bp, 4096                ; CONST
        mov     di, 0
        mov     si, 0
        mov     dx, (LL*(SH-2))/16      ; Number of paragraphs to copy
        sub     dx, bp                  ; between matrices
        jbe     .b
.a:     mov     cx, 65536/2             ; Copy 64KB
        rep movsw
        add     bx, bp                  ; BX is alias for ES
        add     ax, bp                  ; AX is alias for DS
        mov     es, bx
        mov     ds, ax
        sub     dx, bp
        ja      .a                      ; Have more than 64KB
.b:     add     dx, bp
        imul    cx, dx, WORD 16/2
        rep movsw
        pop     dx                      ; (1)

; Copy the top line with corrections because it is stitched to the bottom line
        mov     bx, 0
        mov     cx, (LL*SH)/16
        mov     si, LL
        call    .Copy1

; Copy the bottom line with corrections because it is stitched to the top line
        mov     bx, cx
        neg     cx
        xor     si, si

.Copy1: call    InitSRegs               ; -> AX=DS BX=ES
        add     ax, cx
        mov     fs, ax
        lea     bx, [si+LL]
.c:     mov     bp, [si+2]
        mov     ax, [si]
        add     bp, [fs:si+2]
        add     ax, [fs:si]
        mov     [es:si+2], bp
        mov     [es:si], ax
        add     si, 4
        cmp     si, bx
        jb      .c
        ret
        LEA     BX, [WORD BX+0]
; --------------------------------------
; IN () OUT (cx) MOD (eax,bx,si,di,bp,ds,es)
ProduceNextGeneration:

; Conditions in ReadMatrix define what changes in WriteMatrix
        xor     bp, bp                  ; GS:BP is VideoPointer
        xor     cx, cx                  ; Number of changed pixels
        xor     bx, bx
RepeatOuterLoop:
        push    bx                      ; (1)
        call    InitSRegs               ; -> AX=DS BX=ES
        mov     di, LL                  ; Current place in a couple of
OuterLoop:                              ; (BW+2)-line windows on both matrices
        lea     si, [di+LL-1]           ; End of current line in matrix
        mov     bl, [es: WORD di+0]     ; ReadMatrix
        shl     eax, 1
        and     bx, 00F0h               ; Even X=0
        jmp     word [cs:TableA+bx]     ; -> EAX
BackA:  call    InnerLoop               ; -> EAX DI BP (BL)
        mov     bl, [es:di]             ; ReadMatrix
        shl     eax, 1
        shl     bx, 1
        and     bx, 001Eh               ; Odd X=SW-1
        jmp     word [cs:TableD+bx]     ; -> EAX
BackD:  bswap   eax
        mov     [gs:bp], eax            ; Writing 32 pixels at once
        add     bp, WORD 4
        inc     di
        cmp     di, LL+(LL*BW)          ; Process BW count matrix lines
        jb      OuterLoop               ; w/o changing segment registers
        pop     bx                      ; (1)
        add     bx, (LL/16)*BW          ; Windows travel down in both matrices
        cmp     bp, (SW/8)*SH           ; At end of screen ?
        jb      RepeatOuterLoop         ; No
        ret
; --------------------------------------
        ALIGN   16
; Pixels on even X=0 coordinates
TableA: dw      BackA, 7 dup 0          ;  0 OFF pixel with 0 or 1 neighbour
        dw      BackA, 7 dup 0          ;  1 OFF pixel with 1 or 2 neighbours
        dw      .TST2, 7 dup 0          ;  2 OFF pixel with 2 or 3 neighbours
        dw      .TST3, 7 dup 0          ;  3 OFF pixel with 3 or 4 neighbours
        dw      BackA, 7 dup 0          ;  4 OFF pixel with 4 or 5 neighbours
        dw      BackA, 7 dup 0          ;  5 OFF pixel with 5 or 6 neighbours
        dw      BackA, 7 dup 0          ;  6 OFF pixel with 6 or 7 neighbours
        dw      BackA, 7 dup 0          ;  7 OFF pixel with 7 or 8 neighbours
        dw      .OFF, 7 dup 0           ;  8 ON pixel with 0 or 1 neighbour
        dw      .TST9, 7 dup 0          ;  9 ON pixel with 1 or 2 neighbours
        dw      .STAY, 7 dup 0          ; 10 ON pixel with 2 or 3 neighbours
        dw      .TST11, 7 dup 0         ; 11 ON pixel with 3 or 4 neighbours
        dw      .OFF, 7 dup 0           ; 12 ON pixel with 4 or 5 neighbours
        dw      .OFF, 7 dup 0           ; 13 ON pixel with 5 or 6 neighbours
        dw      .OFF, 7 dup 0           ; 14 ON pixel with 6 or 7 neighbours
        dw      .OFF, 7 dup 0           ; 15 ON pixel with 7 or 8 neighbours
; - - - - - - - - - - - - - - - - - - -
; An OFF pixel with 2 registered neighbours
.TST2:  test    byte [es:di],      0000'1000b
        jz      BackA                   ; One neighbour short to turn ON
.ON:    inc     cx
        add     byte [di-LL],      0001'0001b
        add     byte [di],         1000'0000b
        add     byte [di+LL],      0001'0001b
        add     byte [di-1],       0000'0001b
        add     byte [di-1+LL],    0000'0001b
        add     byte [di-1+LL*2],  0000'0001b
        inc     ax
        jmp     BackA
; - - - - - - - - - - - - - - - - - - -
        ALIGN   16
; An OFF pixel with 3 registered neighbours
.TST3:  test    byte [es:di],      0000'1000b
        jz      .ON                     ; Has 3 neighbours
        jmp     BackA
; - - - - - - - - - - - - - - - - - - -
        db      (16-($+6)) and 15 dup 90h ; To align .OFF
; An ON pixel with 1 registered neighbour
.TST9:  test    byte [es:di],      0000'1000b
        jnz     .STAY                   ; Has 2 neighbours
.OFF:   inc     cx
        sub     byte [di-LL],      0001'0001b
        sub     byte [di],         1000'0000b
        sub     byte [di+LL],      0001'0001b
        sub     byte [di-1],       0000'0001b
        sub     byte [di-1+LL],    0000'0001b
        sub     byte [di-1+LL*2],  0000'0001b
        jmp     BackA
; - - - - - - - - - - - - - - - - - - -
; An ON pixel with 3 registered neighbours
.TST11: test    byte [es:di],      0000'1000b
        jnz     .OFF                    ; Has more than 3 neighbours
; ---   ---   ---   ---   ---   ---   --
.STAY:  inc     ax
        jmp     BackA
; --------------------------------------
        ALIGN   64
InnerLoop:
        mov     bl, [es:di]             ; ReadMatrix
        shl     eax, 1
        and     bx, 000Fh               ; Odd X
        shl     bx, 1
        jmp     word [cs:TableB+bx]     ; -> EAX
BackB:  movzx   bx, byte [es:di+1]      ; ReadMatrix
        inc     di
        and     bx, 00F0h               ; Even X
        test    di, 15
        jz      Plot
        shl     eax, 1
        jmp     word [cs:TableC+bx]     ; -> EAX
BackC:  cmp     di, si                  ; Just before the end of line ?
        jb      InnerLoop               ; No
        ret
Plot:   bswap   eax
        mov     [gs:bp], eax            ; Writing 32 pixels at once
        add     bp, 4
        xor     eax, eax
        jmp     word [cs:TableC+bx]     ; -> EAX
        NOP
; --------------------------------------
        ALIGN   16
; Pixels on odd X<>SW-1 coordinates
TableB: dw      BackB                   ;  0 OFF pixel with 0 or 1 neighbour
        dw      BackB                   ;  1 OFF pixel with 1 or 2 neighbours
        dw      .TST2                   ;  2 OFF pixel with 2 or 3 neighbours
        dw      .TST3                   ;  3 OFF pixel with 3 or 4 neighbours
        dw      BackB                   ;  4 OFF pixel with 4 or 5 neighbours
        dw      BackB                   ;  5 OFF pixel with 5 or 6 neighbours
        dw      BackB                   ;  6 OFF pixel with 6 or 7 neighbours
        dw      BackB                   ;  7 OFF pixel with 7 or 8 neighbours
        dw      .OFF                    ;  8 ON pixel with 0 or 1 neighbour
        dw      .TST9                   ;  9 ON pixel with 1 or 2 neighbours
        dw      .STAY                   ; 10 ON pixel with 2 or 3 neighbours
        dw      .TST11                  ; 11 ON pixel with 3 or 4 neighbours
        dw      .OFF                    ; 12 ON pixel with 4 or 5 neighbours
        dw      .OFF                    ; 13 ON pixel with 5 or 6 neighbours
        dw      .OFF                    ; 14 ON pixel with 6 or 7 neighbours
        dw      .OFF                    ; 15 ON pixel with 7 or 8 neighbours
; - - - - - - - - - - - - - - - - - - -
; An OFF pixel with 2 registered neighbours
.TST2:  test    byte [es:di],      1000'0000b
        jns     BackB                   ; One neighbour short to turn ON
.ON:    inc     cx
        add     word [di-LL],      0001'0000'0001'0001b
        add     word [di],         0001'0000'0000'1000b
        add     word [di+LL],      0001'0000'0001'0001b
        inc     ax
        jmp     BackB
; - - - - - - - - - - - - - - - - - - -
        ALIGN   16
; An OFF pixel with 3 registered neighbours
.TST3:  test    byte [es:di],      1000'0000b
        jns     .ON                     ; Has 3 neighbours
        jmp     BackB
; - - - - - - - - - - - - - - - - - - -
        db      (16-($+6)) and 15 dup 90h ; To align .OFF
; An ON pixel with 1 registered neighbour
.TST9:  test    byte [es:di],      1000'0000b
        js      .STAY                   ; Has 2 neighbours
.OFF:   inc     cx
        sub     word [di-LL],      0001'0000'0001'0001b
        sub     word [di],         0001'0000'0000'1000b
        sub     word [di+LL],      0001'0000'0001'0001b
        jmp     BackB
; - - - - - - - - - - - - - - - - - - -
; An ON pixel with 3 registered neighbours
.TST11: test    byte [es:di],      1000'0000b
        js      .OFF                    ; Has more than 3 neighbours
; ---   ---   ---   ---   ---   ---   --
.STAY:  inc     ax
        jmp     BackB
; --------------------------------------
        ALIGN   16
; Pixels on even X<>0 coordinates
TableC: dw      BackC, 7 dup 0          ;  0 OFF pixel with 0 or 1 neighbour
        dw      BackC, 7 dup 0          ;  1 OFF pixel with 1 or 2 neighbours
        dw      .TST2, 7 dup 0          ;  2 OFF pixel with 2 or 3 neighbours
        dw      .TST3, 7 dup 0          ;  3 OFF pixel with 3 or 4 neighbours
        dw      BackC, 7 dup 0          ;  4 OFF pixel with 4 or 5 neighbours
        dw      BackC, 7 dup 0          ;  5 OFF pixel with 5 or 6 neighbours
        dw      BackC, 7 dup 0          ;  6 OFF pixel with 6 or 7 neighbours
        dw      BackC, 7 dup 0          ;  7 OFF pixel with 7 or 8 neighbours
        dw      .OFF, 7 dup 0           ;  8 ON pixel with 0 or 1 neighbour
        dw      .TST9, 7 dup 0          ;  9 ON pixel with 1 or 2 neighbours
        dw      .STAY, 7 dup 0          ; 10 ON pixel with 2 or 3 neighbours
        dw      .TST11, 7 dup 0         ; 11 ON pixel with 3 or 4 neighbours
        dw      .OFF, 7 dup 0           ; 12 ON pixel with 4 or 5 neighbours
        dw      .OFF, 7 dup 0           ; 13 ON pixel with 5 or 6 neighbours
        dw      .OFF, 7 dup 0           ; 14 ON pixel with 6 or 7 neighbours
        dw      .OFF, 7 dup 0           ; 15 ON pixel with 7 or 8 neighbours
; - - - - - - - - - - - - - - - - - - -
; An OFF pixel with 2 registered neighbours
.TST2:  test    byte [es:di],      0000'1000b
        jz      BackC                   ; One neighbour short to turn ON
.ON:    inc     cx
        add     word [di-1-LL],    0001'0001'0000'0001b
        add     word [di-1],       1000'0000'0000'0001b
        add     word [di-1+LL],    0001'0001'0000'0001b
        inc     ax
        jmp     BackC
; - - - - - - - - - - - - - - - - - - -
        ALIGN   16
; An OFF pixel with 3 registered neighbours
.TST3:  test    byte [es:di],      0000'1000b
        jz      .ON                     ; Has 3 neighbours
        jmp     BackC
; - - - - - - - - - - - - - - - - - - -
        db      (16-($+6)) and 15 dup 90h ; To align .OFF
; An ON pixel with 1 registered neighbour
.TST9:  test    byte [es:di],      0000'1000b
        jnz     .STAY                   ; Has 2 neighbours
.OFF:   inc     cx
        sub     word [di-1-LL],    0001'0001'0000'0001b
        sub     word [di-1],       1000'0000'0000'0001b
        sub     word [di-1+LL],    0001'0001'0000'0001b
        jmp     BackC
; - - - - - - - - - - - - - - - - - - -
; An ON pixel with 3 registered neighbours
.TST11: test    byte [es:di],      0000'1000b
        jnz     .OFF                    ; Has more than 3 neighbours
; ---   ---   ---   ---   ---   ---   --
.STAY:  inc     ax
        jmp     BackC
; --------------------------------------
        ALIGN   16
; Pixels on odd X=SW-1 coordinates
TableD: dw      BackD                   ;  0 OFF pixel with 0 or 1 neighbour
        dw      BackD                   ;  1 OFF pixel with 1 or 2 neighbours
        dw      .TST2                   ;  2 OFF pixel with 2 or 3 neighbours
        dw      .TST3                   ;  3 OFF pixel with 3 or 4 neighbours
        dw      BackD                   ;  4 OFF pixel with 4 or 5 neighbours
        dw      BackD                   ;  5 OFF pixel with 5 or 6 neighbours
        dw      BackD                   ;  6 OFF pixel with 6 or 7 neighbours
        dw      BackD                   ;  7 OFF pixel with 7 or 8 neighbours
        dw      .OFF                    ;  8 ON pixel with 0 or 1 neighbour
        dw      .TST9                   ;  9 ON pixel with 1 or 2 neighbours
        dw      .STAY                   ; 10 ON pixel with 2 or 3 neighbours
        dw      .TST11                  ; 11 ON pixel with 3 or 4 neighbours
        dw      .OFF                    ; 12 ON pixel with 4 or 5 neighbours
        dw      .OFF                    ; 13 ON pixel with 5 or 6 neighbours
        dw      .OFF                    ; 14 ON pixel with 6 or 7 neighbours
        dw      .OFF                    ; 15 ON pixel with 7 or 8 neighbours
; - - - - - - - - - - - - - - - - - - -
; An OFF pixel with 2 registered neighbours
.TST2:  test    byte [es:di],      1000'0000b
        jns     BackD                   ; 2 neighbours is not enough
.ON:    inc     cx
        add     byte [di-LL],      0001'0001b
        add     byte [di],         0000'1000b
        add     byte [di+LL],      0001'0001b
        add     byte [di+1-LL*2],  0001'0000b
        add     byte [di+1-LL],    0001'0000b
        add     byte [di+1],       0001'0000b
        inc     ax
        jmp     BackD
; - - - - - - - - - - - - - - - - - - -
        ALIGN   16
; An OFF pixel with 3 registered neighbours
.TST3:  test    byte [es:di],      1000'0000b
        jns     .ON                     ; Has 3 neighbours
        jmp     BackD
; - - - - - - - - - - - - - - - - - - -
        db      (16-($+6)) and 15 dup 90h ; To align .OFF
; An ON pixel with 1 registered neighbour
.TST9:  test    byte [es:di],      1000'0000b
        js      .STAY                   ; Has 2 neighbours
.OFF:   inc     cx
        sub     byte [di-LL],      0001'0001b
        sub     byte [di],         0000'1000b
        sub     byte [di+LL],      0001'0001b
        sub     byte [di+1-LL*2],  0001'0000b
        sub     byte [di+1-LL],    0001'0000b
        sub     byte [di+1],       0001'0000b
        jmp     BackD
; - - - - - - - - - - - - - - - - - - -
; An ON pixel with 3 registered neighbours
.TST11: test    byte [es:di],      1000'0000b
        js      .OFF                    ; Has more than 3 neighbours
; ---   ---   ---   ---   ---   ---   --
.STAY:  inc     ax
        jmp     BackD
; --------------------------------------
\$\endgroup\$
1
  • \$\begingroup\$ related: lemire.me/blog/2018/07/18/… shows an AVX2 version. (If you want to keep using 16-bit mode, SSE is usable but VEX-encoded instructions like AVX / AVX2 aren't.) \$\endgroup\$ Dec 1, 2020 at 10:03

1 Answer 1

1
\$\begingroup\$

If you only want to detect oscillating between two states, you method will probably work, but it will have some false positives (think things are oscillating when they aren't, and abort too early). There are ways to improve it (add counts for each row and column comes to mind) but ultimately it'll be a heuristic and sometimes fail.

A PERFECT method to detect oscillation (of any cycle length, not just length 2), is to use a cycle-finding algorithm. The easiest-to-understand one is Floyd's cycle-finding algorithm, also called the tortoise and the hare. It will use 2X the memory, and 3-4X the time.

At each game step, increment board A one step (which you display) and board B two steps (which you never display). If board A == board B, the game is about to cycle. (IMO, if this is a screensaver, I would run it for a few cycles after you detect this, it's still nice to look at for a while)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.