Writing a Compressor

The decompressor read the format; the natural next question is whether the language can write it. Reading and writing a compressed stream are not symmetric tasks — decoding is mechanical, following a spec that leaves no choices, while encoding is where all the decisions live — but they share a shape. Every structure the inflater took apart, the deflater has to assemble: the same blocks, the same code tables, the same bit-level packing. Writing the compressor after the decompressor felt less like new construction than like building the mirror image of something already standing.

The bit writer is the bit reader backwards

The inflater’s core was a bit reader: a byte cursor and a small buffer, handing out bits least-significant-first across byte boundaries because that is the order DEFLATE packs them. The deflater needs the exact inverse — a bit writer that accepts a value and a width and pushes those bits into an output stream in the same order, flushing a full byte whenever eight accumulate and padding the last one with zeros. The two are so nearly reflections of each other that writing the second was mostly a matter of reading the first and reversing the direction of every assignment. The one asymmetry worth naming is that the Huffman codes have to be emitted most-significant-bit-first while the extra bits go least-significant-first, so the writer pre-reverses each code — the same bit-reversal the reader never needed because it consumed codes the other way.

Greedy matching

Where the reader simply obeyed the back-references it found in the stream, the writer has to invent them. This is the real work of a compressor: at each position, look backward through the window for the longest run of bytes that repeats here, and if it is at least three long, emit a length/distance pair instead of the literal bytes. The implementation is a naive window scan — walk back up to the 32-kilobyte limit, measure the match at each candidate, keep the longest. A real compressor uses a hash chain to avoid rescanning, and this one does not; it is honest greedy matching, fast enough natively and slow when interpreted, which is exactly the tradeoff a probe should make visible rather than hide. The matched length and distance then go through the same base-plus-extra-bits encoding tables the reader used to decode them, run in reverse.

Fixed Huffman, and the gap it leaves

The first version used the fixed-Huffman tables — the built-in code lengths from the spec that both sides already agree on, so nothing about the tree has to be transmitted. That is the simplest correct encoder, and it works: a redundant eighteen-kilobyte text file compressed to a hundred and thirty-eight bytes in six hundredths of a second, and both the system gunzip and the inflater from the last part reconstructed it byte for byte with a matching checksum. But gzip -9 on the same input produced sixty-six bytes. The difference is not a bug — it is the whole point of dynamic Huffman, which fits a custom code table to each block’s actual symbol frequencies instead of using a fixed one. Fixed Huffman plus greedy matching leaves roughly a factor of two on the table, and naming that gap precisely — a completeness gap in the encoder, not a defect in the output — is what set up the next step.

What made the compressor writable at all was that everything it needed had already arrived for other reasons: the bitwise operators, the binary-safe file reader and writer, the checksum from an earlier probe. Nothing new had to be added to the language to close the loop from bytes to compressed bytes and back. The encoder compiled and produced valid gzip without a single change to the compiler — a decompressor and a compressor, both in pure Mere, interoperable with the system tools and with each other. The gap that remained was about compression ratio, not correctness, and it was a gap I knew how to close.