This is an implementation of Conway's Game of Life that fits within the 512-byte floppy bootloader use by the IBM PC. In fact, the program takes up roughly only half of that space.
As an additional fun challenge, the implementation has been limited to using only the instructions and addressing modes available on the original Intel 8086 processor.
Being limited to what was available on the original Intel 8086 presents some interesting challenges:
- Indirect memory accesses can only be performed using the
bx
,bp
,si
, anddi
registers. - The
shl
andshr
instructions cannot be used with an immediate operand other than than1
. Other shift amounts can only be specified by thecl
register. - Register operands for numerous instructions are fixed and cannot be changed (for example,
mul
always operates onax
). - There is no
movzx
instruction. - There are no
fs
andgs
segments. - Registers are 16 bits wide at most.
One of the main consequences of these limitations is the need for more instructions than would otherwise be necessary, largely as a result of the need to perform a lot of register juggling.
The game 'world' is a 256x256 grid of cells - 65,536 cells in total. Each cell is stored as one byte, which is 1
for a live cell and 0
for a dead cell. While it seems slightly wasteful to use an entire byte for each cell, doing so reduces the number of instructions that would be required to operate on a more compact representation.
As each cell is one byte, the world state at any one timestep occupies 65,534 bytes (64 kB) of memory. This happens to exactly fill a single 16-bit 8086 segment.
During each simulation step, ds
points to the current world state and es
points to the next world state. The stack segment, ss
, is repurposed as a third data-segment that is used to read and write VGA RAM. As a result, the main simulation routine cannot make use of the stack. Game state update and rendering is done in a single pass.
Another advantage of using one byte for each cell is that it plays well with how the 8086's general purpose registers are split into high and low halves. For example, while ax
might hold the linear offset of a cell, al
and ah
automatically hold the cell's X and Y co-ordinates respectively. Furthermore, al
and ah
can be incremented and decremented separately to create wraparound at the world's edges, without carrying into one another.
The initial state of the world is populated using a xorshift pseudorandom number generator (based on an implementation by John Metcalf).
The seed value for PRNG is derived from the current time, which is read from the CMOS.
BIOS video mode 11h
(1-bit monochrome 640x480) is used for graphics, with one pixel used for each cell. This resolution allows for the whole 256x256 world to be seen on screen at once (admittedly slightly on the small side).
Unfortunately, the use of 1-bit monochrome graphics mean that multiple pixels are stored in each byte, and extra instructions are required to pack these bits.
The colour-palette is customised on boot via writes to the VGA DAC.
The programmable interval timer (IRQ0) is used to control the speed of execution.
Install nasm
(tested with version 2.15.05
), then build using:
make all
Optionally, the size of the floppy disk may be specified in kibibytes (1024-byte units). By default, a 1440 KiB image will be produced, which is a common size for 3.5-inch high-density floppies on the IBM PC (see list of floppy disk formats on Wikipedia for other sizes).
make all FLOPPY_SIZE=360
Install qemu-system-i386
(tested with version 7.2.90
), then run using:
make run