Sunday, 26 July 2015

Z80 Size Programming Challenge #5

Recently I issued the fifth Z80 challenge for the Sinclair Spectrum:

This time the challenge is to write a solid flood fill routine to fill a region of unset pixels, bounded in 4 directions (up, down, left, right) by set pixels or the screen edge. The routine should be called with the X and Y coordinates in a register. There's no need to set the screen attributes.

Scoring is multi-objective: a routine will be judged by the code size and stack space required to fill a test image. Your routine will be awarded one point for each competing routine it is smaller *and* uses less stack space than. The routine(s) with the most points will be declared winner(s).

The deadline is Wednesday 22nd July, midday (GMT).

  1. The X and Y coordinates are in pixels with 0,0 at the top left.
  2. No memory other than the screen, stack and your routine can be written.
  3. If you call a ROM routine it's size will be added to your code size.
  4. Programs must return. The RET instruction is included in the size.
  5. So everyone has a fair chance comment with the code size not code.
  6. There are no prizes, just the chance to show off your coding skills.

The test image is designed to check correct behaviour at the screen boundary and to be pathological — triggering suboptimal behaviour in some common flood fill algorithms:

Final Results

Congratulations to everyone who coded a working flood fill and to Dworkin Z Amberu who claimed first place by being shorter and using less memory than competing entries.

Entries have been plotted on this genuine fake Spectrum screenshot. If the graph is empty below and to the left of an entry, that entry is in first place:


ColourCoderCodeMemoryTime
RedJohn Metcalf98~2K2.1 seconds
OrangePaul Rhodes102~1.8K3.2 seconds
YellowRalph Becket109~2K8.8 seconds
GreenMiguel Jódar166~800 bytes4.8 seconds
WhiteDworkin Z Amberu58~9.8K28.6 seconds
CyanJohn Metcalf54~6.1K28.6 seconds
BlackDworkin Z Amberu84~270 bytes40 seconds
BlueDworkin Z Amberu1928 bytes~40 minutes
PurpleAdrian Brown19912 bytes~3 hours?

Shortest Entry

The simplest entry is a recursive routine weighing in at 54 bytes. Despite being too heavy on the stack to score well it's one of the easiest to understand. Each time the routine is called it checks whether or not the pixel at X,Y is set. If not the pixel will be set then the fill routine is called recursively with the pixels up, down, left and right of the current pixel:

; called with e = X horizontal, d = Y vertical
FILL:
  ld b,e
  ld a,d
  and 248
  rra
  cp 96
  ret nc
  rra
  rra
  ld l,a
  xor d
  and 248
  xor d
  ld h,a
  ld a,e
  xor l
  and 7
  xor e
  rrca
  rrca
  rrca
  ld l,a
  ld a,128
PLOTBIT:
  rrca
  djnz PLOTBIT
  or (hl)
  cp (hl)
  ret z
  ld (hl),a
  inc e
  call nz,FILL
  dec e
  dec de
  call ZFILL
  inc de
  call FILL
  inc d
  inc d
ZFILL:
  call nz,FILL
  dec d
  ret

The winning entries will be available shortly.

3 comments:

  1. Hi John, Sounds like some really useful routines. Any chance of posting them? Many thanks. Paddy

    ReplyDelete
  2. The shortest entry bombs out if attempting to fill a large area.

    ReplyDelete
    Replies
    1. It uses a crazy amount of stack, eventually overwriting itself with return addresses! I'd recommend using a scanline floodfill which is much more stack efficient (under normal circumstances) http://www.retroprogramming.com/2017/04/zx-spectrum-scanline-flood-fill.html

      Delete