Huffman Decode
Algorithms & Data Huffman coding is the compression at the
heart of ZIP, JPEG and MP3: frequent symbols get short bit-codes, rare ones get long ones. Decoding
means reading the stream one bit at a time and walking a tree — left on a 0, right on a 1 —
until you hit a leaf. Here a coded image loads in pixel by pixel as the tree is walked. Runs on its
own; no joypad needed. Written in C and compiled with the
llvm-mos-based 65816 toolchain
(+mos-a16, 16-bit accumulator mode).
Self-running demo — the coded image decodes in bit by bit, then replays.
Click the screen to focus, then watch. Tab away and it pauses.
What it is
A prefix tree turns a stream of bits back into symbols. Start at the root and let each bit steer you down until you land on a leaf:
node = root;
while (node is not a leaf) {
bit = next bit of the stream; // MSB-first
node = bit ? node.right : node.left; // descend the tree
}
emit(node.symbol); // then start over at the root Because the codes are chosen so none is a prefix of another, the bare bit stream is unambiguous — the walk always lands cleanly on a symbol. Here the symbols are pixel colours, so the image materialises as the stream is consumed. It stays bit-exact across every codegen mode.
Compiler stress-test
| Item | What it exercises |
|---|---|
| bit-by-bit reader | Huffman codes are not byte-aligned — a symbol can be one bit or several. So the decoder pulls single bits from the stream, most-significant first, masking and shifting one byte at a time. A bit-granular reader, unlike the byte-oriented copy of an LZ decoder. |
| tree descent | Each bit chooses a branch — left or right — of a prefix tree; when you reach a leaf, that is your symbol, and you jump back to the root. Following a chain of node pointers driven by a bit stream is the whole decode. |
| prefix code | The codes are chosen so no code is a prefix of another (0, 10, 110, 111), which is exactly what makes a bare bit stream unambiguously decodable — the tree walk never gets stuck. |
| cross-checked | The image is encoded, then decoded, and the build gate verifies the decoded pixels match the original exactly — any slip in the bit reader or the tree walk is caught. |
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 CRC 0xE8E4 — the decoded image, cross-checked pixel-for-pixel
against the original) live in this tab. No far pointers — the same source passes every way:
host == default == +mos-a16 == +mos-xy16 == bsnes-jg,
-verify clean.