Realtime RLE for the Z80

[cngsoft]

Here's a little thing I wrote just for fun after making the compactage of "North Star" and noticing that the area used by the game's software double buffer stores a compressed version of the in-game screen decoration that gets unpacked to VRAM when the game begins and packed back into the buffer after the end: realtime run-length encoding for the Z80.

; ENCODER: HL=^SOURCE,DE=^TARGET,IX=FULL_LENGTH; HL+=FULL_LENGTH,DE+=PAKD_LENGTH,IX=0,B=0,ACF!

rle2pack_init ld b,0
rle2pack_loop ld c,(hl)
rle2pack_find ld a,xh
or xl
jr z,rle2pack_exit
dec ix
inc hl
inc b
jr z,rle2pack_over
ld a,(hl)
cp c
jr z,rle2pack_find
rle2pack_over call rle2pack_fill
jr rle2pack_loop
rle2pack_exit cp b
call nz,rle2pack_fill
; generate the end marker from the last byte!
dec hl
ld a,(hl)
inc hl
cpl
jr rle2pack_exit_
rle2pack_fill dec b
ld a,c
jr z,rle2pack_fill_
rle2pack_exit_ ld (de),a
inc de
ld (de),a
inc de
dec b
ld a,b
rle2pack_fill_ ld (de),a
inc de
ld b,0
ret

; DECODER: HL=^SOURCE,DE=^TARGET; HL+=PAKD_LENGTH,DE+=FULL_LENGTH,B!,AF!

rle2upak_init ld b,1
ld a,(hl)
inc hl
cp (hl)
jr nz,rle2upak_fill
inc hl
ld b,(hl)
inc hl
inc b
ret z
inc b
rle2upak_fill ld (de),a
inc de
djnz $-2
jr rle2upak_init

The encoder is 49 bytes long and does almost 32 kB/s on average; the decoder fits in 19 bytes and runs twice as fast. Both support zero-length blocks thanks to the end marker, that also means that the decoder doesn't need to know the stream's length (packed or not) in advance. By turning all INC HL, DEC HL and INC DE into DEC HL, INC HL and DEC DE streams will be encoded and decoded in reverse.

The format itself is as follows: single bytes are encoded as themselves, double bytes as themselves plus a $00, and strings of three or more identical bytes (up to 256) become the first two bytes plus the length minus 2; the end-of-stream marker is a couple of identical bytes plus a $FF, and avoids clashing with previous single bytes (i.e. XX, XX XX $FF won't be misread as XX XX XX, $FF). Best-case compression (all memory is made of strings of 256 identical bytes) is 3*length/256+3; worst-case compression (all memory is made of different couples of identical bytes, i.e. XX XX YY YY XX XX YY YY...) is 3*length/2+3.

This method outperforms "North Star" in all fields: it's faster, its footprint is smaller and it compresses the same data better. Don't expect it to crunch as much as any Lempel-Ziv method would do, however, specially those used in cross-platform development such as ApLib or Exomizer.

[Ast]

I'll test it to see the real gain. Thank you very much CngSoft!