LZ77 Reveal

Algorithms & Data

A compressed picture loading in on a Super Nintendo, decoded by an LZ77 byte-stream decoder — the same family behind zip and PNG. Its trick: matches copy back-references from the decoder's own output buffer, so an overlapping copy expands a repeating run for free. Runs automatically; no joypad needed. Written in C and compiled with the llvm-mos-based 65816 toolchain (+mos-a16, 16-bit accumulator mode).

loading core…

Self-running demo — the compressed image decodes and reveals itself.

Click the screen to focus, then watch. Tab away and it pauses.

What it is

LZ77 shrinks data by pointing backward: instead of repeating bytes, it stores "copy N bytes from M ago". Decoding is a small loop reading a token stream of literals and matches:

for each token:
    literal?  ->  out[dp++] = input byte
    match?    ->  from = dp - offset
                  copy length bytes: out[dp++] = out[from++]
                                     // reads its OWN just-written output

The clever part is that a match reads from the buffer being written — so when the copy distance is short, it overlaps its own output and a two-byte token expands into a long run. Here it reconstructs a diamond image; the source is 256 cells, the compressed stream just 56 bytes. It stays bit-exact across every codegen mode.

Compiler stress-test

Item	What it exercises
sliding window	LZ77 compresses by replacing repeated data with a back-reference: "copy N bytes from M bytes ago". The decoder is a tiny state machine reading a flag-driven token stream of literals and (offset, length) matches.
back-reference	A match copies from the output buffer the decoder is still filling. The copy is byte-by-byte and output-relative — pointer arithmetic reading bytes the loop just wrote. It is the self-referential core no other demo in the battery runs.
overlap = RLE	When the offset is smaller than the length, the copy overlaps its own tail — so a single short match expands into a long repeating run. That is how LZ subsumes run-length encoding for free.
bit-exact	Pure byte pointer arithmetic — no multiply, no divide, no libcall. The gate folds the whole 256-byte decoded image; host == default == +mos-a16 == +mos-xy16 == bsnes-jg, byte for byte.

Written in C with the llvm-mos 65816 toolchain and verified against bsnes-jg (and MAME where the SPC700 IPL is present). Hit Verify fidelity to reproduce the build gate's WRAM assert (gate hash 0x0100 — a fold of the full 256-byte decoded image) live in this tab. No far pointers — the same source passes every way: host == default == +mos-a16 == +mos-xy16 == bsnes-jg, -verify clean.