This program implements a patterned flood fill algorithm in C with an embedded Z80 assembly library, written by Alvin Albrecht in 2002–2003. The main routine draws ten random circles on a cleared screen, then picks a random starting point and one of eight hard-coded 8×8 fill patterns before calling the assembly routine `sp_PFill`. The flood fill operates byte-at-a-time using a breadth-first, three-block circular queue allocated on the Z80 stack, with the queue size controlled by the caller—the comment notes a maximum stack consumption of 3×300+30 bytes for the demo invocation. The queue is divided into “pattern,” “investigate,” and “new” blocks, maintaining a two-pixel-thick fill frontier so the expanding diamond wave can be patterned behind it without leaving unfilled gaps; if the queue overflows, a bail-out routine patterns any pending pixels and returns with the carry flag set. Pixel expansion uses a byte-widening loop in `bytefill` that fans out set bits left and right within each display byte before committing them to screen.
Program Analysis
Overall Structure
The program has two distinct layers: a short C driver (main()) and a hand-written Z80 assembly flood-fill engine (SPPFill). The C code uses the graphics.h and spritepack.h libraries and runs in an infinite loop. The assembly is a self-contained library module that exports SPPFill and imports helper routines (SPGetScrnAddr, SPPixelUp, SPPixelDown, SPCharLeft, SPCharRight).
C Driver
Each iteration of while(1) does the following:
- Clears the graphics screen with
clg(). - Draws 10 random circles, each guaranteed to lie fully on-screen (the
do…whileloop rejects coordinates where the circle would clip any edge). - Picks a random seed point
(x, y)and a pattern offsetr— a multiple of 8 in the range 0–56 — indexing one of the eight 8-byte patterns in thepatterns[]array. - Calls
sp_PFill(x, y, patterns + r, 300), passing a queue depth of 300 (worst-case stack use ≈ 930 bytes plus 30 bytes of overhead). - Waits for a keypress with
sp_WaitForKey()before looping.
Fill Pattern Table
Eight 8×8 patterns are defined as inline assembly defb binary literals. Their visual meanings are:
| Index | Description |
|---|---|
| 0 | Solid black (all bits set) |
| 1 | Checkerboard (alternating 0xAA / 0x55) |
| 2 | Outlined rectangle / hollow box |
| 3 | Diagonal lines, top-left to bottom-right |
| 4 | Diagonal lines, top-right to bottom-left |
| 5 | Cross-hatch |
| 6 | Sparse diagonal dots |
| 7 | Border with interior diagonal line |
Queue Architecture
The algorithm allocates its circular queue entirely on the Z80 hardware stack, growing downward. The queue is divided into three logically contiguous blocks, each terminated by a 3-byte sentinel whose screen-address MSB is below 0x40. The physical end of the queue is marked with a 0x80 byte, exploiting the fact that valid display addresses always have an MSB in the range 0x40–0x7F. Queue wrap-around is detected by comparing the current pointer’s MSB against 0x80; when wrap-around is needed, the pointer is reset to IX (the top of the queue).
Each queue entry is a 3-byte struct stored MSB-first:
- Screen address (2 bytes, MSB first)
- Fill byte (1 byte)
Six pointer variables are maintained in a fixed frame relative to IX:
| IX offset | Variable |
|---|---|
| +1/+2 | New block pointer |
| +3/+4 | Investigate block pointer |
| +5/+6 | Pattern block pointer |
| +7/+8 | Available queue depth counter |
| +9/+10 | Fill pattern pointer |
| +11/+12 | Return address |
Three-Block Wave Algorithm
The fill frontier advances as a Manhattan-distance diamond. At each iteration of pfloop:
investigateexpands the investigate block outward in four directions, adding successful expansions to the new block.applypatternwrites the fill pattern to screen for every pixel in the pattern block, freeing that space in the queue.- The investigate block logically becomes the new pattern block, and the new block becomes the new investigate block.
The two-pixel-thick boundary (pattern block + investigate block) ensures there are no holes in the frontier through which already-patterned areas could be re-entered by the fill.
Byte-Level Fill Expansion (bytefill)
Rather than working one pixel at a time, the algorithm operates on whole display bytes. The bytefill routine takes an incoming set of pixels (as a bitmask) and expands them left and right within the byte using a loop:
rrashifts right to probe the right neighbor bit.add a,a(left shift) probes the left neighbor.- The two shifts are OR-ed with the current byte and then masked against already-set pixels in the display byte.
- The loop repeats until the byte stabilizes, ensuring the full horizontal extent of the fill within that byte is determined before committing.
This is considerably faster than single-pixel processing and naturally handles byte-boundary cases for left/right expansion checks.
Left/Right Movement and Screen Boundaries
Horizontal expansion is gated: moving left requires the leftmost bit of the fill byte to be set (bit 7,b) and the screen column not to be zero (guarded by ld a,l / and 31 and a hi-res mode check via bit 5,h). Moving right requires the rightmost bit (bit 0,b) and checks for right-edge wrap by testing l AND 31 == 0 after the move.
Queue Overflow Bail-Out
When the available-depth counter reaches zero in addnew, the routine jumps to bail. The bail-out path clears the current pixel from the screen (to avoid a visible artifact), marks the end of the new block, then calls applypattern three times in succession to drain the pattern block, the investigate block, and the new block. It then restores SP from IX and returns with the carry flag set to signal the partial fill to the caller.
IX-Relative Variable Access and Undocumented Opcodes
The frame-pointer use of IX throughout is a deliberate C-calling-convention mimic in assembly. Two instances of defb 0xdd appear in endinv and annowrap to prefix a subsequent ld e,l or ld d,h instruction with the IX register, effectively encoding ld ixl,l and ld ixh,h — undocumented but widely used Z80 instructions not directly expressible in the assembler’s syntax. This is used to reload DE (the new-block pointer) with the value of IX when wrap-around is detected.
Pattern Application
In applypattern, the scan-line index (bits 0–2 of the screen address MSB, extracted with and 0x07) selects one of the eight bytes from the 8×8 pattern. The selected pattern byte is ANDed with the fill byte (to restrict the pattern to filled pixels) and then the complement of the fill byte is OR-ed in, ensuring unfilled pixels in the byte are cleared. This correctly handles partial bytes at fill boundaries.
Content
Image Gallery
Source Code
/* Alvin Albrecht 01.2003 */
#include <stdlib.h>
#include <graphics.h>
#include <spritepack.h>
extern uchar patterns[];
#asm
._patterns
defb @11111111
defb @11111111
defb @11111111
defb @11111111
defb @11111111
defb @11111111
defb @11111111
defb @11111111
defb @10101010
defb @01010101
defb @10101010
defb @01010101
defb @10101010
defb @01010101
defb @10101010
defb @01010101
defb @00000000
defb @01111110
defb @01100110
defb @01100110
defb @01100110
defb @01100110
defb @01111110
defb @00000000
defb @10001000
defb @01000100
defb @00100010
defb @00010001
defb @10001000
defb @01000100
defb @00100010
defb @00010001
defb @00010001
defb @00100010
defb @01000100
defb @10001000
defb @00010001
defb @00100010
defb @01000100
defb @10001000
defb @10011001
defb @01100110
defb @01100110
defb @10011001
defb @10011001
defb @01100110
defb @01100110
defb @10011001
defb @00100010
defb @01010101
defb @10001000
defb @00000000
defb @00100010
defb @01010101
defb @10001000
defb @00000000
defb @11111111
defb @10000000
defb @10100010
defb @10010100
defb @10001000
defb @10010100
defb @10100010
defb @10000000
#endasm
main()
{
int x,y,r,n;
while (1) {
clg();
for (n=0; n!=10; n++) {
do {
x = rand() % 256;
y = rand() % 192;
r = rand() % 40;
} while (((x-r)<0) || ((y-r)<0) || ((x+r)>255) || ((y+r)>191));
circle(x,y,r,1);
}
x = rand() % 256;
y = rand() % 192;
r = (rand() % 8)*8;
sp_PFill(x, y, patterns + r, 300); /* max stack space used = 3*300+30 bytes */
sp_WaitForKey();
}
}
;
; SPFill
;
INCLUDE "SPconfig.def"
XLIB SPPFill
LIB SPGetScrnAddr, SPPixelUp, SPPixelDown, SPCharLeft, SPCharRight
; Patterned Flood Fill
; Alvin Albrecht 2002
;
;
; This subroutine does a byte-at-a-time breadth-first patterned flood fill.
; It works by allocating a circular queue on the stack, with the size of the
; queue determined by an input parameter. The queue is divided into three
; contiguous blocks: the pattern block, the investigate block and the new block.
; The queue contains 3-byte structures (described below) with a special structure
; delimiting each block. The physical end of the queue is marked with a special
; byte. The contents of the queue grow down in memory.
;
; The pattern block holds pixels that have been blackened on screen and are
; only waiting to have the pattern applied to them before they are removed
; from the queue.
;
; The investigate block holds pixels that have been blackened on screen and
; are waiting to be investigated before they become part of the pattern
; block. 'Investigating' a pixel means trying to expand the fill in all
; four directions. Any successful expansion causes the new pixel to be
; added to the new block.
;
; The new block holds pixels that have been blackened on screen and are
; waiting to become part of the investigate block. The new block expands
; as the investigate block is investigated.
;
; The pattern fill algorithm follows these steps:
; 1. Examine the investigate block. Add new pixels to the new block if an
; expansion is possible.
; 2. Pattern the pattern block. All pixels waiting to be patterned are
; patterned on screen.
; 3. The investigate block becomes the pattern block.
; The new block becomes the investigate block.
; 4. Repeat until the investigate block is empty.
;
; The algorithm may bail out prematurely if the queue fills up. Bailing
; out causes any pending pixels in the queue to be patterned before the
; subroutine exits. If PFILL would continue to run by refusing to enter
; new pixels when the queue is full, there would be no guarantee that
; the subroutine would ever return.
;
; In English, the idea behind the patterned flood fill is simple. The
; start pixel grows out in a circular shape (actually a diamond). A
; fill boundary two pixels thick is maintained in that circular shape.
; The outermost boundary is the frontier, and is where the flood fill
; is growing from (ie the investigate block). The inner boundary is
; the pattern block, waiting to be patterned. A solid inner boundary
; is necessary to prevent the flood-fill frontier pixels from growing
; back toward the starting pixel through holes in the pattern. Once
; the frontier pixels are investigated, the innermost boundary is
; patterned. The newly investigated pixels become the outermost
; boundary (the investigate block) and the old investigate block becomes
; the new pattern block.
;
; Each entry in the queue is a 3-byte struct that grows down in memory:
; screen address (2-bytes, MSB first)
; fill byte (1-byte)
; A screen address with MSB < 0x40 is used to indicate the end of a block.
; A screen address with MSB >= 0x80 is used to mark the physical end of the Q.
;
; The fill pattern is a typical 8x8 pixel character, stored in 8 bytes.
; enter: h = y coord, l = x coord, bc = max stack depth, de = address of fill pattern
; In hi-res mode, carry flag is most significant bit of x coord
; used : ix, af, bc, de, hl
; exit : no carry = success, carry = had to bail queue was too small
; stack: 3*bc+30 bytes, not including the call to PFILL or interrupts
.SPPFill
push de ; save (pattern pointer) variable
dec bc ; we will start with one struct in the queue
push bc ; save max stack depth variable
ld a,h
call SPGetScrnAddr ; de = screen address, b = pixel byte
ex de,hl ; hl = screen address
call bytefill ; b = fill byte
jr c, viable
pop bc
pop de
ret
.viable
ex de,hl ; de = screen address, b = fill byte
ld hl,-7
add hl,sp
push hl ; create pattern block pointer = top of queue
push hl
pop ix ; ix = top of queue
dec hl
dec hl
dec hl
push hl ; create investigate block pointer
ld hl,-12
add hl,sp
push hl ; create new block pointer
xor a
push af
dec sp ; mark end of pattern block
push de ; screen address and fill byte are
push bc ; first struct in investigate block
inc sp
push af
dec sp ; mark end of investigate block
ld c,(ix+7)
ld b,(ix+8) ; bc = max stack depth - 1
inc bc
ld l,c
ld h,b
add hl,bc ; space required = 3*BC (max depth) + 10
add hl,bc ; but have already taken 9 bytes
ld c,l
ld b,h ; bc = # uninitialized bytes in queue
ld hl,0
sbc hl,bc ; negate hl, additions above will not set carry
add hl,sp
ld (hl),0 ; zero last byte in queue
ld sp,hl ; move stack below queue
ld a,$80
push af ; mark end of queue with $80 byte
inc sp
ld e,l
ld d,h
inc de
dec bc
ldir ; zero the uninitialized bytes in queue
; NOTE: Must move the stack before clearing the queue, otherwise if an interrupt
; occurred, garbage could overwrite portions of the (just cleared) queue.
; ix = top of queue, bottom of queue marked with 0x80 byte
; Variables indexed by ix, LSB first:
; ix + 11/12 return address
; ix + 09/10 fill pattern pointer
; ix + 07/08 max stack depth
; ix + 05/06 pattern block pointer
; ix + 03/04 investigate block pointer
; ix + 01/02 new block pointer
; A picture of memory at this point:
;
;+-----------------------+ higher addresses
;| | |
;|- return address -| |/
;| | V
;+-----------------------+ lower addresses
;| fill |
;|- pattern pointer -|
;| |
;+-----------------------+
;| |
;|- max stack depth -|
;| |
;+-----------------------+
;| |
;|- pattern block -|
;| |
;+-----------------------+
;| |
;|- investigate block -|
;| |
;+-----------------------+
;| |
;|- new block -|
;| |
;+-----------------------+
;| end of block marker | <- ix = pattern block = top of queue
;| ? |
;| ? |
;+-----------------------+
;| screen address MSB | <- investigate block
;| screen address LSB |
;| fill byte |
;+-----------------------+
;| end of block marker |
;| ? |
;| ? |
;+-----------------------+
;| 0 | <- new block
;| 0 |
;| 0 |
;+-----------------------+
;| |
;| ...... | size is a multiple of 3 bytes
;| rest of queue |
;| all zeroed |
;| ...... |
;| |
;+-----------------------+
;| 0x80 | <- sp, special byte marks end of queue
;+-----------------------+
.pfloop
ld l,(ix+3)
ld h,(ix+4) ; hl = investigate block
ld e,(ix+1)
ld d,(ix+2) ; de = new block
call investigate
ld (ix+1),e
ld (ix+2),d ; save new block
ld (ix+3),l
ld (ix+4),h ; save investigate block
ld l,(ix+5)
ld h,(ix+6) ; hl = pattern block
ld c,(ix+7)
ld b,(ix+8) ; bc = max stack depth (available space)
call applypattern
ld (ix+7),c
ld (ix+8),b ; save stack depth
ld (ix+5),l
ld (ix+6),h ; save pattern block
ld a,(hl) ; done if the investigate block was empty
cp 0x40
jp nc, pfloop
.endpfill
ld de,11 ; return address is at ix+11
add ix,de
ld sp,ix
or a ; make sure carry is clear, indicating success
ret
; IN/OUT: hl = investigate block, de = new block
.investigate
ld a,(hl)
cp 0x80 ; bit 15 of screen addr set if time to wrap
jp c, inowrap
push ix
pop hl ; hl = ix = top of queue
ld a,(hl)
.inowrap
cp 0x40 ; screen address < 0x4000 marks end of block
jp c, endinv ; are we done yet?
ld b,a
dec hl
ld c,(hl) ; bc = screen address
dec hl
ld a,(hl) ; a = fill byte
dec hl
push hl ; save spot in investigate block
ld l,c
ld h,b ; hl = screen address
ld b,a ; b = fill byte
.goup
push hl ; save screen address
call SPPixelUp ; move screen address up one pixel
jr c, updeadend ; if went off-screen
push bc ; save fill byte
call bytefill
call c, addnew ; if up is not dead end, add this to new block
pop bc ; restore fill byte
.updeadend
pop hl ; restore screen address
.godown
push hl ; save screen address
call SPPixelDown ; move screen address down one pixel
jr c, downdeadend
push bc ; save fill byte
call bytefill
call c, addnew ; if down is not dead end, add this to new block
pop bc ; restore fill byte
.downdeadend
pop hl ; restore screen address
.goleft
bit 7,b ; can only move left if leftmost bit of fill byte set
jr z, goright
ld a,l
and 31
jr nz, okleft
bit 5,h ; for hi-res mode: column = 1 if l=0 and bit 5 of h is set
jr z, goright
.okleft
push hl ; save screen address
call SPCharLeft
push bc ; save fill byte
ld b,0x01 ; set rightmost pixel for incoming byte
call bytefill
call c, addnew ; if left is not dead end, add this to new block
pop bc ; restore fill byte
pop hl ; restore screen address
.goright
bit 0,b ; can only move right if rightmost bit of fill byte set
jr z, nextinv
or a ; clear carry
call SPCharRight
jr c, nextinv ; went off screen
ld a,l
and 31
jr z, nextinv ; wrapped around line
ld b,0x80 ; set leftmost pixel for incoming byte
call bytefill
call c, addnew ; if right is not dead end, add this to new block
.nextinv
pop hl ; hl = spot in investigate block
jp investigate
.endinv
dec hl
dec hl
dec hl ; investigate block now points at new block
ld a,(de) ; check if new block is at end of queue
cp 0x80
jr c, nowrapnew
defb 0xdd
ld e,l
defb 0xdd
ld d,h ; de = ix = top of queue
.nowrapnew
xor a
ld (de),a ; store end marker for new block
dec de
dec de
dec de
ret
; enter b = incoming byte, hl = screen address
; exit b = fill byte, screen blackened with fill byte
.bytefill
ld a,b
xor (hl) ; zero out incoming pixels that
and b ; run into set pixels in display
ret z
.bfloop
ld b,a
rra ; expand incoming pixels
ld c,a ; to the right and left
ld a,b ; within byte
add a,a
or c
or b
ld c,a
xor (hl) ; zero out pixels that run into
and c ; set pixels on display
cp b
jp nz, bfloop ; keep going until incoming byte does not change
or (hl)
ld (hl),a ; fill byte on screen
scf ; indicate that this was a viable step
ret
; add incoming fill byte and screen address to new block
; enter b = incoming byte, hl = screen address, de = new block
.addnew
push hl ; save screen address
ld l,(ix+7)
ld h,(ix+8) ; hl = max stack depth
ld a,h
or l
jr z, bail ; no space in queue so bail!
dec hl ; available queue space decreases by one struct
ld (ix+7),l
ld (ix+8),h
pop hl ; hl = screen address
ld a,(de) ; check if new block is at end of queue
cp 0x80
jr c, annowrap
defb 0xdd
ld e,l
defb 0xdd
ld d,h ; de = ix = top of queue
.annowrap
ex de,hl
ld (hl),d ; make struct, store screen address (2 bytes)
dec hl
ld (hl),e
dec hl
ld (hl),b ; store fill byte (1 byte)
dec hl
ex de,hl
ret
; if the queue filled up, we need to bail. Bailing means patterning any set pixels
; which may still be on the display. If we didnt bail and tried to trudge along,
; there is no guarantee the fill would ever return.
.bail
pop hl ; hl = screen address, b = fill byte
ld a,b
xor (hl)
ld (hl),a ; clear this byte on screen
xor a
ld (de),a ; mark end of new block
ld l,(ix+5)
ld h,(ix+6) ; hl = pattern block
call applypattern ; for pattern block
call applypattern ; for investigate block
call applypattern ; for new block
ld de,11 ; return address is at ix+11
add ix,de
ld sp,ix
scf ; indicate we had to bail
ret
; hl = pattern block, bc = max stack depth (available space)
.applypattern
ld a,(hl)
cp 0x80 ; bit 15 of screen addr set if time to wrap
jp c, apnowrap
push ix
pop hl ; hl = ix = top of queue
ld a,(hl)
.apnowrap
cp 0x40 ; screen address < 0x4000 marks end of block
jr c, endapply ; are we done yet?
and 0x07 ; use scan line 0..7 to index pattern
add a,(ix+9)
ld e,a
ld a,0
adc a,(ix+10)
ld d,a ; de points into fill pattern
ld a,(de) ; a = pattern
ld d,(hl)
dec hl
ld e,(hl) ; de = screen address
dec hl
and (hl) ; and pattern with fill byte
sub (hl) ; or in complement of fill byte
dec a
ex de,hl
and (hl) ; apply pattern to screen
ld (hl),a
ex de,hl
dec hl
inc bc ; increase available queue space
jp applypattern
.endapply
dec hl
dec hl
dec hl ; pattern block now pts at investigate block
retNote: Type-in program listings on this website use ZMAKEBAS notation for graphics characters.