brotli-pure

A from-scratch Brotli codec in pure Common Lisp (no FFI) — for the web's Content-Encoding: br. Brotli had no Common Lisp implementation at all (unlike gzip/deflate via chipz/salza2, or zstd via this project's sibling zstd-pure), so this fills that gap: clean-room, dependency-free, and differential-tested byte-for-byte against the reference brotli (python brotli / node zlib).

Status — complete codec ✅ (decoder + entropy-coding encoder)

decompress reads the full Brotli format (RFC 7932): the WBITS window header and the meta-block loop (ISLAST/ISLASTEMPTY, MNIBBLES/MLEN, metadata blocks); uncompressed meta-blocks; and compressed meta-blocks in full —

• canonical prefix (Huffman) codes — both simple (1–4 symbols) and complex (code-length-code alphabet + 16/17 repeat coding);
• block-type / block-count machinery for the literal, insert-and-copy, and distance category streams;
• insert-and-copy commands (the 704-symbol command alphabet, §5 cell table);
• distances — NPOSTFIX/NDIRECT, the 16 short codes over a rolling distance ring buffer (which persists across meta-blocks), direct codes, and the full extra-bits formula;
• context modeling — LSB6 / MSB6 / UTF8 / Signed literal contexts, plus literal and distance context maps (inverse move-to-front + RLE);
• the static dictionary (122,784 bytes, vendored at data/dictionary.bin) with all 121 word transforms (case folding, omit-first/last, prefix/suffix).

Differential-tested byte-for-byte against the reference brotli (python brotli): 1100 fuzz cases — zeros / random / text / structured / HTML, sizes from 0 to 200 KB, qualities 0–11, window sizes 10–24 — all decode identically. A curated 44-vector subset is committed under inspect/vectors/ and checked by the offline gate (so it needs no external tools to run).

Encoder ✅ — compress is a real entropy-coding compressor: a greedy hash-chain LZ77 match finder produces insert-and-copy commands, then length-limited canonical Huffman codes the literal / command / distance alphabets (with the "last distance" ring-buffer code for repeats); it falls back to a stored meta-block when entropy coding wouldn't shrink the data. Output is a standard brotli stream — verified decodable by both node and python brotli. 300-case fuzz (zeros / random / text / structured / ramp, 0–400 KB): every output round-trips through our own decoder and the reference, and the ratio is competitive with reference quality-5. It uses a single literal/command/distance tree (no block splitting or context modeling), so it trades some ratio for simplicity; correctness and interop come first.

Layout

src/
  bitio       LSB-first bit reader + writer (brotli/deflate convention)
  tables      context lookup tables + the 121 word transforms (RFC 7932 §8)
  huffman     canonical prefix codes: simple + complex (clcl + repeat coding)
  dict        static dictionary load + word-transform application
  decompress  compressed meta-block decoder (commands, contexts, distances)
  brotli      stream framing, uncompressed meta-blocks, compress-stored
  encode      compressed encoder: LZ77 + length-limited Huffman
data/
  dictionary.bin   the brotli static dictionary (122,784 bytes), vendored
inspect/
  vectors/           reference brotli streams (.br) + originals (.raw)
  offline-test.lisp  the gate: decode vs reference + self round-trip
  differential.sh    cross-check both directions vs node + python brotli
  run-all.sh

Use

(asdf:load-system "brotli-pure")
(brotli-pure:decompress <octets of a br stream>)  ; => octets   (full decoder)
(brotli-pure:compress   <octets>)                 ; => brotli stream (LZ77 + Huffman)

License

MIT.