Writing a Decompressor

Several recent episodes added pieces of a byte-handling story without ever assembling them: bitwise operators for the ALU, hex literals so masks read like their specifications, a binary-safe file reader and its writing twin. Each was forced by a small probe and each worked in isolation. This part is the program that made them work together — a real gzip decompressor — and, as dogfoods tend to, it came back carrying more than it went out for.

One decoder for three block types

DEFLATE, the algorithm inside gzip, is not large but it is unforgiving: get one bit misaligned and the whole stream turns to noise, with no partial credit. The decompressor needs a bit reader that pulls bits least-significant-first across byte boundaries — built here as a three-slot state vector (position, bit buffer, bit count) over the input’s int vector. On top of it sits the part worth bragging about: a single canonical Huffman decoder that serves all three of DEFLATE’s block types. Stored blocks are raw bytes. Fixed-Huffman blocks use a built-in code table. Dynamic blocks ship their own code lengths, compressed by yet another Huffman code. The insight that keeps this to one decoder instead of three is that the fixed tables are just a particular set of code lengths — so the same build a decoder from a length array and decode one symbol functions handle fixed and dynamic identically, and stored is a short special case that copies a length-prefixed run. The whole thing reads the gzip container around it too (skipping the optional name / comment / extra fields) and verifies the trailer’s CRC-32 — reused verbatim from the checksum example two probes ago — against the decompressed output.

Why it was writable now, and what it flushed out

The point worth pausing on is that this program could not have been written a week earlier. The bit reader needs bitwise shifts and masks. The range tables read as hex because hex literals exist. The input arrives through read_file_bytes because a NUL-terminated string would have truncated the compressed data at its first zero byte, and the output leaves through write_file_bytes. Each of those was a separate probe with its own episode; the decompressor is where they finally compose into something that shakes hands with the system gzip and gunzip. It decompresses their output — a 1-byte file, a megabyte file, stored and fixed and dynamic blocks — byte-identical, every time.

And then it did the thing dogfoods do. Writing three hundred lines of tightly nested, deeply recursive, capture-heavy code exercised the compiler’s closure machinery far past what any test had, and it surfaced — first — three distinct code-generation bugs, each an error that only appeared once the C the compiler emitted was handed to a C compiler, and none of which the interpreter had ever hit. That is the next episode. The one after it is about a number the decompressor printed that should not have been possible: 484 megabytes to inflate a single megabyte.