Skip to content

SWI 0x13 — HuffUnComp

  • Entry: 0x00001014 (ARM)
  • Status: verified (hardware-checked 2026-07-08: cycle counts measured and output round-trip-verified on real GBA via the worker ROM)

Summary

Decompresses a Huffman-coded stream. A binary tree stored at the front of the compressed data is walked bit-by-bit to produce 4- or 8-bit data symbols, which are packed into 32-bit words and written to the destination. Output is always in 32-bit units, so a single routine serves both RAM and VRAM.

Parameters

Reg In Meaning
r0 ptr Source address pointing at the 4-byte compression header.
r1 ptr Destination address (word-aligned, word-writable).

Returns

No return value.

Clobbered registers

r0–r3, ip (r12), lr, and 8 bytes of stack scratch. r4–r11 saved/restored.

Hardware audit (2026-07-08, canary r4–r12 + CPSR snapshot): caller-visible clobbers: r0/r1 advanced past source/output; r3 = the last output word (0x0055AAFF observed). r2, r4–r12, r13, and CPSR (flags and mode) came back bit-identical on every tested path. r11/r12 are explained by the SWI dispatcher (it pushes {r11, r12, lr} — see 10_irq_boot_and_iwram.md) and CPSR by the SPSR restore on return; r2 and r4–r10 must be preserved or restored by the routine itself — where a static note above claims r2 is destroyed, the hardware disagrees at the caller level. Raw data: results/clobber_audit_pass2.csv.

Algorithm

Header. Byte 0's low nibble is the data symbol size in bits (dataBits, normally 4 or 8). Bits 8–31 of the header word are the decompressed size in bytes. The high nibble of byte 0 (compression type) is ignored. The shared region check is invoked with a dummy size, so it gates only on the source region, never on the declared size (size 0 is instead handled by the main loop).

Tree table. Immediately after the 4-byte header: - Byte at offset 4 = tree table size unit (treeSize); the tree table occupies (treeSize + 1) * 2 bytes. - The root node is the byte at offset 5. - The compressed bit-stream begins right after the tree table, at src + 4 + (treeSize + 1) * 2.

Node format (1 byte each). Bits 0–5 are an offset; bit 7 marks child-0 as a data leaf; bit 6 marks child-1 as a data leaf. The two child nodes of the current node live at childBase = (nodeAddr AND ~1) + (offset + 1) * 2, and the current bit (0 or 1) selects childBase + bit. The leaf flag actually consulted is bit 7 when the bit is 0 and bit 6 when the bit is 1 (implemented by shifting the node byte left by the bit value and testing bit 7). When a child is a leaf, that child node's byte value is the decoded data symbol.

Bit stream / packing. The stream is consumed as little groups of 32 bits (loaded a word at a time, MSB-first). Starting from the root, each bit steps to a child; on reaching a leaf the symbol is emitted and the walk restarts at the root. Symbols are packed into a 32-bit output accumulator by shifting the accumulator right by dataBits and inserting each new symbol into the top dataBits. Once 32 / dataBits symbols have accumulated (4 symbols for 8-bit data, 8 for 4-bit), the word is stored and the remaining-size counter is decreased by 4. The loop runs while remaining size > 0.

Edge cases & known bugs

  • Decompressed size 0: the source-region check passes (dummy size), but the main loop's size > 0 test fails immediately, so nothing is written.
  • Size not a multiple of 4: output is emitted only in whole 32-bit words. A non-multiple-of-4 size causes the routine to write one extra full word (up to 3 extra bytes) — it keeps collecting a whole word whenever the counter is still positive, then stops after the counter goes ≤ 0. Callers must ensure the destination has room for the rounded-up size.
  • Type nibble not enforced: high nibble of byte 0 is never checked.
  • dataBits other than 4/8: the packing threshold is (dataBits & 7) + 4 and the shift is dataBits; only 4 and 8 give sensible behaviour. Other values produce malformed packing (documented, not validated).

  • Source-region protection: identical gate as the other decompression SWIs — a source in 0x00000000–0x01FFFFFF is refused.

  • Non-word-aligned size hardware-confirmed (2026-07-08 anomaly tests, results/cycles_phase3_anomaly.csv): declared sizes 253 and 254 (with a bitstream encoding ≥256 symbols) wrote the full final 32-bit word — the extra 3/2 bytes are the next correctly decoded symbols, not garbage, and the cycle count is identical to the size-256 run (20967). The decoder keeps decoding until the final word fills. If the bitstream ends short, those extra symbols would come from whatever follows the stream.

  • Size 0 hardware-confirmed: nothing written, immediate return (122 cycles).

Cycle count

Hardware-measured net CPU cycles (worker-ROM harness, TM0/TM1 cascade at F/1, 13-cycle baseline subtracted; identical across 3 runs — see 02_hardware_verification_checklist.md § Measurement setup).

8-bit symbols, 4-leaf tree, 256-byte output (EWRAM): 20967 cycles (≈82 cycles/byte at 2 bits/symbol; the per-bit tree walk dominates). The round trip also hardware-confirms the tree-table and bitstream layout described above.

Open questions (need hardware verification)

  • Exact over-write extent when size is not word-aligned (up to 3 bytes) and whether shipped assets ever rely on it.
  • ~~Timing of the tree walk~~ — measured for 2-bit codes, see Cycle count.

GBATEK cross-reference

Confirms GBATEK's tree/node encoding (offset in bits 0–5, leaf flags in bits 6/7, childBase = (addr & ~1) + offset*2 + 2). Adds: type nibble ignored, size-0 and non-word-multiple size handling, and the source-region gate.