Compressing Data for Atari Programs: RLE, LZ4, ZX0, ZX02, aPLib and Deflate Compared

Atari text screen headed UNPACK 7684 BYTES (KORONIS.MIC) with a table: LZ4 3733 bytes 21 frames, ZX0 2700 25, ZX02 2700 21, ZX5 2675 26, APLIB 2748 23, DEFLATE 2512 94, each marked OK

Every Atari program runs out of something: disk space, load time, cartridge ROM or RAM. A full-screen picture is 7,680 bytes, and a game with a dozen of them won't fit on a single-density disk side. Compressing data on the PC and unpacking it on the Atari is the standard answer, and modern packers do it remarkably well, often to around a third of the original size with an unpacker of a couple of hundred bytes.

What you'll learn: how run-length encoding and LZ-style compression work, which modern formats Atari programmers use, how they compare in size and unpacking speed on the same data (we measured), and how to add a packed file to your own program.

What you need: a PC for the packers, and MADS or Mad Pascal. All measurements here were made in atari800 (XL/XE, NTSC) with a GRAPHICS 0 screen on. The test data were three Micro-Painter pictures that come with the Mad Pascal compression samples, and the LZ unpackers were the ones in Mad Pascal's units.

1. Two families of compression

Run-length encoding (RLE) replaces a run of identical bytes with a count and the byte. It is trivial to unpack, works in a few dozen bytes of code, and suits data with long flat runs: blank screen areas, solid backgrounds, level maps. It does nothing for data that varies byte to byte, such as dithered pictures or text. Many classic Atari games used variations; Fort Apocalypse, for example, unpacks its caverns with a run-length scheme that only treats certain common characters as runs (see Studying the Fort Apocalypse Source Code).

LZ-style (Lempel-Ziv) compression replaces any repeated sequence with a pointer back to an earlier copy: "copy 12 bytes from 40 bytes ago". The packer searches the whole file for the best matches, which can take the PC seconds; the unpacker just copies bytes, which a 6502 does quickly. The modern formats below differ in how they encode those literals, lengths and offsets, trading compression ratio against unpacker size and speed:

Format Notes
LZ4 Byte-aligned codes designed for fast, simple unpacking; the weakest ratio here. Packer used: smalLZ4.
ZX0 Einar Saukas's format, with bit-level codes and an optimal packer. Very good ratio.
ZX02 dmsc's ZX0 variant with a 6502-friendly encoding: about 0.5% worse ratio than ZX0, with 6502 decoders of 130–175 bytes.
ZX5 A newer format from Einar Saukas, with its own packer.
aPLib Ibsen Software's format. Packer used: apultra (Emmanuel Marty and spke).
Deflate The zip/gzip format, with Huffman coding on top of LZ. Best ratio, slowest and largest unpacker. Mad Pascal's unpacker is Piotr Fusik's zlib6502. Packer used: zopfli.

2. Sizes: what we got

We packed the three pictures (7,684, 7,684 and 7,680 bytes) with each tool's default or recommended options, plus our own simple RLE:

Picture RLE (ours) LZ4 ZX0 ZX02 ZX5 aPLib Deflate
koronis.mic 5,013 3,733 2,700 2,700 2,675 2,748 2,512
silents.mic 6,182 4,142 2,926 2,926 2,845 2,949 2,650
wins.mic 5,443 4,060 3,025 3,026 2,963 3,060 2,882

Three points stand out. RLE saves something on these pictures, but every LZ format does far better. Among the other formats the spread is small: deflate was always best, aPLib 6–11% bigger, with ZX5, ZX0 and ZX02 in between. ZX02 matched ZX0 to the byte on two pictures and lost one byte on the third. LZ4 is clearly behind, at about half the original size rather than about a third. Your own data will give different numbers, so always try a few packers on it.

3. Unpacking speed

The size is only half of it. This Mad Pascal program links the six packed versions of koronis.mic as resources, unpacks each into a buffer, times it with the frame counter and checks a 16-bit sum of the result against the original:

// Decompress the same 7,684-byte picture with six unpackers and time them.
uses crt, lz4, zx0, zx2, zx5, aplib, deflate;

{$r bench.rc}

const
  SIZE = 7684;
  GOOD = 31351;          // 16-bit byte sum of the original file

var
  outbuf: array [0..SIZE-1] of byte;
  rtc: byte absolute 20;
  p: pointer;
  t: byte;
  i, sum: word;

procedure report(name: string; psize: word);
begin
  t := rtc - t;
  sum := 0;
  for i := 0 to SIZE-1 do inc(sum, outbuf[i]);
  write(name, ' ', psize:5, ' ', t:4, ' frames ');
  if sum = GOOD then writeln('OK') else writeln('BAD');
  fillchar(@outbuf, SIZE, 0);
end;

procedure sync;
begin
  t := rtc;
  repeat until rtc <> t;
  t := rtc;
end;

begin
  writeln('UNPACK 7684 BYTES (KORONIS.MIC)');
  writeln('FORMAT  SIZE  TIME');
  GetResourceHandle(p, 'plz4'); sync; unLZ4(p, @outbuf); report('LZ4    ', 3733);
  GetResourceHandle(p, 'pzx0'); sync; unZX0(p, @outbuf); report('ZX0    ', 2700);
  GetResourceHandle(p, 'pzx2'); sync; unZX2(p, @outbuf); report('ZX02   ', 2700);
  GetResourceHandle(p, 'pzx5'); sync; unZX5(p, @outbuf); report('ZX5    ', 2675);
  GetResourceHandle(p, 'papl'); sync; unAPL(p, @outbuf); report('APLIB  ', 2748);
  GetResourceHandle(p, 'pdef'); sync; unDEF(p, @outbuf); report('DEFLATE', 2512);
  repeat until keypressed;
end.

with this resource file, bench.rc:

plz4	RCDATA	'koronis.lz4'
pzx0	RCDATA	'koronis.zx0'
pzx2	RCDATA	'koronis.zx2'
pzx5	RCDATA	'koronis.zx5'
papl	RCDATA	'koronis.apl'
pdef	RCDATA	'koronis.def'

All six unpacked correctly. The times, in NTSC frames (1/60 s) for 7,684 bytes:

Format Size Unpack time
LZ4 3,733 21 frames
ZX0 2,700 25 frames
ZX02 2,700 21 frames
ZX5 2,675 26 frames
aPLib 2,748 23 frames
Deflate 2,512 94 frames

So on this picture ZX02 unpacked as fast as LZ4 while being 28% smaller, and the bit-oriented formats all took around 0.35–0.45 seconds. Deflate saved another 188 bytes over ZX02 but took more than four times as long, about 1.6 seconds. Remember that these are particular unpackers, not the formats themselves: dmsc's own ZX02 package offers three 6502 decoders that trade size against speed.

4. A minimal RLE packer and decoder

For data with long runs, or when every byte of code counts, RLE is still useful. Here is a simple format and a PC packer in Python:

  • $00–$7F n: copy the next n+1 bytes literally.
  • $80–$FE n: repeat the next byte n−$7E times (2 to 128).
  • $FF: end of data.
# rlepack.py in out -- simple RLE for the Atari decoder in rle.asm
#   $00-$7F  n: copy the next n+1 bytes
#   $80-$FE  n: repeat the next byte n-$7E times (2..128)
#   $FF      end of data
import sys
data = open(sys.argv[1], 'rb').read()
out, lit, i = bytearray(), bytearray(), 0
def flush():
    global lit
    while lit:
        chunk = lit[:128]; out.append(len(chunk) - 1); out.extend(chunk); lit = lit[128:]
while i < len(data):
    run = 1
    while i + run < len(data) and data[i + run] == data[i] and run < 128: run += 1
    if run >= 3 or (run == 2 and not lit):
        flush(); out.append(0x7E + run); out.append(data[i]); i += run
    else:
        lit.append(data[i]); i += 1
flush(); out.append(0xFF)
open(sys.argv[2], 'wb').write(out)
print(len(data), '->', len(out))

The 6502 decoder is 67 bytes. This test program unpacks koronis.mic, times it and checks the sum:

; RLE decoder for the format made by rlepack.py, timed and checked. MADS.
;   $00-$7F n: copy the next n+1 bytes   $80-$FE n: repeat next byte n-$7E times
;   $FF: end
RTCLOK  = $12
ICCOM   = $0342
ICBLL   = $0348
CIOV    = $E456
SRC     = $CB               ; packed data pointer
DST     = $CD               ; output pointer
PTR     = $CF

        org $2000
start   lda #<packed
        sta SRC
        lda #>packed
        sta SRC+1
        lda #<outbuf
        sta DST
        lda #>outbuf
        sta DST+1
        lda RTCLOK+2        ; wait for a new frame, then time it
w0      cmp RTCLOK+2
        beq w0
        lda RTCLOK+2
        sta t0
        jsr unrle
        sec
        lda RTCLOK+2
        sbc t0
        sta frames
        ldx #0              ; 16-bit sum of 7684 output bytes
        stx sum
        stx sum+1
        lda #<outbuf
        sta PTR
        lda #>outbuf
        sta PTR+1
        ldy #0
        lda #<7684
        sta cnt
        lda #>7684
        sta cnt+1
s1      clc
        lda (PTR),y
        adc sum
        sta sum
        bcc s2
        inc sum+1
s2      inc PTR
        bne s3
        inc PTR+1
s3      lda cnt
        bne s4
        dec cnt+1
s4      dec cnt
        lda cnt
        ora cnt+1
        bne s1
        jsr say
        dta c'RLE: ',0
        lda #<(pend-packed)
        ldx #>(pend-packed)
        jsr dec5
        jsr say
        dta c' BYTES, ',0
        lda frames
        ldx #0
        jsr dec5
        jsr say
        dta c' FRAMES, SUM ',0
        lda sum
        ldx sum+1
        jsr dec5
        jmp *

; ---- the decoder: SRC = packed data, DST = output ----
unrle   ldy #0
next    lda (SRC),y         ; control byte
        cmp #$FF
        beq done
        tax
        jsr incsrc
        txa
        bmi run
        tax                 ; literal: copy X+1 bytes
lit     lda (SRC),y
        sta (DST),y
        jsr incsrc
        jsr incdst
        dex
        bpl lit
        jmp next
run     sec                 ; run: repeat the next byte n-$7E times
        sbc #$7E
        tax
        lda (SRC),y
        jsr incsrc
r1      sta (DST),y
        jsr incdst
        dex
        bne r1
        jmp next
done    rts
incsrc  inc SRC
        bne i1
        inc SRC+1
i1      rts
incdst  inc DST
        bne i2
        inc DST+1
i2      rts

; ---- text output ----
say     pla
        sta PTR
        pla
        sta PTR+1
sy1     inc PTR
        bne sy2
        inc PTR+1
sy2     ldy #0
        lda (PTR),y
        beq sy3
        jsr putc
        jmp sy1
sy3     lda PTR+1
        pha
        lda PTR
        pha
        rts
putc    ldx #0
        stx ICBLL
        stx ICBLL+1
        pha
        lda #11
        sta ICCOM
        pla
        jmp CIOV
dec5    sta num
        stx num+1
        ldx #0
dc1     lda #'0'
        sta digit
dc2     lda num
        sec
        sbc p10lo,x
        tay
        lda num+1
        sbc p10hi,x
        bcc dc3
        sta num+1
        sty num
        inc digit
        bne dc2
dc3     stx savx
        lda digit
        jsr putc
        ldx savx
        inx
        cpx #5
        bne dc1
        rts
p10lo   dta <10000,<1000,<100,<10,<1
p10hi   dta >10000,>1000,>100,>10,>1
num     dta a(0)
digit   dta 0
savx    dta 0
t0      dta 0
frames  dta 0
sum     dta a(0)
cnt     dta a(0)
packed  ins 'koronis.rle'
pend
outbuf  .ds 7684
        run start

It printed RLE: 05013 BYTES, 00020 FRAMES, SUM 31351: correct, and about as fast as the LZ4 unpacker in spite of the subroutine calls for every byte. Replacing incsrc/incdst with inline code and indexed copies would speed it up considerably; we haven't measured that.

5. Using a packer in your own program

The workflow is the same for every format:

  1. Pack on the PC: for example zx02 -f level1.bin level1.zx2. Keep the original out of the build.
  2. Include the packed file: in MADS with ins 'level1.zx2' under a label; in Mad Pascal with a resource line (label RCDATA 'level1.zx2') and GetResourceHandle, as above.
  3. Unpack at run time into its final place: screen memory, a font, a level buffer. In Mad Pascal that is one call (unZX2(src, dest), unLZ4, unAPL and so on). In assembly, add the format's 6502 decoder source to your program, set its source and destination pointers and call it.

Some practical rules:

  • Unpack in place, not twice. Pointing the destination at screen memory or a font saves a second copy.
  • Match the packer to the decoder. ZX0 has two file formats (-c selects the older "classic" one), and Mad Pascal's unit has separate calls for them. A mismatched format unpacks garbage without any error.
  • Mind the decoder's own size when the data is small. A 130-byte decoder pays off quickly on a 7K picture, but not on a 200-byte table.
  • Streams from disk. Several of the Mad Pascal samples (unlz4_stream.pas and others) unpack while reading a file, so the packed data never has to fit in memory whole.

Troubleshooting

  • Garbage after unpacking: wrong decoder for the format or version, a destination that overlaps the packed source, or a packed file loaded at a different address from the one the program expects.
  • The program crashes after unpacking: the output is longer than the space you gave it, and it overwrote code. Know the unpacked size.
  • Packed data barely smaller: the data is already compressed, or very noisy. Try another packer, or store it unpacked.
  • Unpacking is too slow for a level change: use LZ4 or ZX02, unpack during a fade or a "get ready" screen, or unpack only what changes.

Further reading

  • The Mad Pascal repository's samples/a8/compression folder (LZ4, ZX0, ZX02, ZX5, aPLib, deflate, and older formats such as LZW and Huffman), and the unit headers in lib, which name the authors of each decoder.
  • ZX02 by dmsc, on GitHub (dmsc/zx02), and ZX0 by Einar Saukas (einar-saukas/ZX0).
  • On this site: ZX02: A ZX0 Variant Tuned for Tiny 6502 Decompressors, GlurkRLE: A ROM-Friendly Compressor Tuned for Graph2Font Screens, Atari Graphics File Formats, A Tour of the Mad Pascal Samples, Studying the Fort Apocalypse Source Code.

Credits