A compressor is only correct if it is exactly reversible, so every lesson pins concrete bytes, tokens, or codes and proves the round trip. Pack bits high-first with a padded final byte, split a run at its maximum encodable length, build a Huffman tree with a deterministic tie-break and derive canonical codes from lengths alone, copy an overlapping LZ77 back-reference byte by byte, and combine Huffman with LZ77 into one container that stores its own method, original length, and code tables.
Over 33 lessons you build a working general-purpose compression library from scratch, built around a single promise: decompress(compress(x)) returns exactly x, for every input. That round-trip invariant keeps the whole thing exactly testable - real packed bytes, real token streams, real Huffman codes - and language-neutral, because the codec you write is defined by the bytes it emits, not by any library call.
You start with the substrate everything else needs: an MSB-first bit writer and reader that pack variable-width codes across byte boundaries and pad the final byte. On top of that you build three separable codecs - run-length encoding that never expands pathologically, canonical Huffman coding that stores only code lengths and rebuilds the codes, and an LZ77/LZSS sliding-window matcher that emits offset-length back-references - then combine Huffman and LZ77 into a DEFLATE-lite pipeline. A self-describing container records the method, the original length, and the code tables, and the top-level Compress chooses the smaller of the compressed and stored forms so incompressible input never grows. The capstone compresses and decompresses a real multi-line paragraph, asserts the output is byte-identical, and reports the compression ratio.
This is a teaching-grade compressor built around the classic Huffman, LZ77, and DEFLATE ideas: it is exactly reversible, self-describing, and honest about incompressible data. It deliberately stops short of production DEFLATE - no extra-bit length and distance code families, a small bounded match window rather than 32 KB, and a plain code-length table instead of the run-length-encoded code-length alphabet real DEFLATE packs - which is exactly the honest core that zlib, gzip, and zstd extend with larger windows, entropy-coded code lengths, and format framing.
Every compressor speaks in bits, not bytes, because its codes are rarely a whole number of bytes long. Today you build the substrate everything else needs - a bit writer that packs individual bits into bytes, high bit first, and pads the last byte when you flush.
Build a bit writer that accepts single bits and packs them into bytes, most significant bit first.
A compressor’s whole job is to spend fewer bits on common things, so it must be able to emit codes that are not a whole number of bits: a 3-bit code here, a 7-bit code there. Bytes are the wrong unit. The fix is a bit writer that accepts bits one at a time and packs them into bytes for you.
We pack most significant bit first: the first bit you write lands in the top
position of the byte (the 0x80 place), the next just below it, and so on. So
writing 1, 0, 1 builds the byte 10100000, which is 0xA0. When you
flush, any partially filled byte is emitted as-is, with the unused low bits
left as zero padding. That padding is harmless as long as the reader knows
how many real bits to expect, which is exactly what later lessons arrange. Pick a
bit order and state it plainly; the only rule is that the reader must use the
same one.
// fill each byte from the top bit (0x80) downwardtype BitWriter struct {out []bytecur byte // byte being fillednbit uint // bits used in cur, 0..7}func (w *BitWriter) WriteBit(b uint) {w.cur |= byte(b&1) << (7 - w.nbit) // place at the next high positionw.nbit++// when nbit reaches 8, append cur and reset (left as an exercise)}
The tool works end to end on real files and stdin with honest, non-panicking error handling, but it is a single-block, small-window, unchecksummed DEFLATE-lite - a correct teaching-scale codec, not a production-ready compressor.
The 1952 paper that introduced Huffman coding - the bottom-up merge of the two least frequent symbols that yields an optimal prefix code. The whole Huffman chapter is this one idea, made canonical and serialisable.
The 1977 paper (LZ77) that introduced the sliding-window dictionary: replace a repeated substring with a reference back to its earlier occurrence. The LZSS chapter is the practical literal-versus-match refinement of this.
The specification that combines LZ77 and Huffman into one format, and the exact source of the canonical-code assignment used here. Read section 3.2 for canonical Huffman and how real DEFLATE packs length and distance codes with extra bits - the parts this project deliberately simplifies.
A modern, from-the-ground-up survey of coding and modelling - bit I/O, entropy, Huffman, arithmetic and range coding, LZ variants, and context mixing. The best single free reference for where this project sits in the wider landscape.
A hands-on classic that walks through bit I/O, Huffman, adaptive Huffman, arithmetic coding, and LZ77/LZSS with complete C listings - the closest print companion to the arc built here.