DEFLATE-Lite: connect tokens, codes, and framing

The capstone combines greedy LZ77, canonical Huffman, and the MSB-first writer from prior modules. Its DL container is a teaching format, with a 128-byte window and match lengths 3..18. It is not a stream that a DEFLATE or gzip decoder can consume.

Build the token and symbol stream

For input AAAAAAA, emit literal A, then (distance=1,length=6). The match overlaps and regenerates six As. Translate these tokens into two alphabets:

Meaning	Alphabet	Symbol
Literal A	literal/length	65
Match length 6	literal/length	256+(6-3)=259
Match distance 1	distance	1-1=0
End of block	literal/length	272

Literal/length symbols 256..271 represent lengths 3..18. Symbol 272 always terminates the block; it is not a match length. A decoder reads from the distance alphabet only immediately after a length symbol. Choosing the wrong alphabet at that point destroys alignment for all later tokens.

Independently derive a fixed-mode file

All 273 literal/length symbols have length 9, assigned in numeric order. All 128 distances have length 7. Thus this example emits:

A       = 001000001
length6 = 100000011
dist1   = 0000000
EOF     = 100010000

Concatenation has 34 meaningful bits, rounded to five bytes: 20 c0 c0 44 00. Prepend magic, version, mode: 44 4c 01 00. The complete nine-byte file is therefore:

44 4c 01 00 20 c0 c0 44 00

Derive it before calling the encoder; then feed these independently supplied bytes to the decoder. This catches a shared code numbering or packing bug that a round trip could miss. Decoding reaches output lengths 1,7,7 at literal, match, EOF respectively.

Account for the header when choosing a model

Fixed mode has a four-byte header. Dynamic mode has four bytes plus 273 literal/length lengths and 128 distance lengths: 405 bytes total. In the dynamic model for this tiny input, all three used literal/length frequencies are one. Deterministic Huffman lengths are 2,2,1 for symbols 65,259,272; the single distance has length one. Payload is just six bits, but the file is 406 bytes. Fixed wins at nine.

The reference compares header bits plus meaningful payload bits, with fixed mode winning an exact bit-cost tie. Fewer total bits cannot create a larger padded byte count, although two different bit costs can round to the same byte count. Token choice is still greedy, so selecting the smaller model does not imply a globally optimal parse.

Count EOF once when building frequencies. If no match occurs, the reference assigns distance symbol zero a singleton code so its generated header remains simple. A decoder may also accept an empty distance table if no length symbol ever requests a distance.

Decode as a state machine

1. Validate magic DL, version 1, mode 0 or 1, and the complete dynamic table if present.
2. Validate lengths in 0..32, reject oversubscribed prefix tables, and require EOF to have a code. Incomplete trees are permitted.
3. Decode one literal/length symbol. A literal appends a byte; EOF returns success; a length requires one distance symbol.
4. Check distance against already decoded output, then append output[len(output)-distance] once per match byte.
5. Repeat until EOF. A missing tree edge, exhausted bitstream, or impossible backward distance returns (nil,false).

The 32-bit code limit follows the code storage type. Do not shift first and validate later: a length 33 can lose leading information and make malformed headers appear decodable. Likewise, three one-bit codes exceed available prefixes even if an insertion routine can overwrite a leaf without panicking.

This API stops at EOF and ignores trailing bits or bytes. It has no checksum, declared output size, concatenated-block handling, or integrity proof. A successful decode certifies the teaching syntax traversed to EOF, not that the bytes came from a trusted sender. The exercise limits encoder inputs to 4096 bytes; a deployment would need its own output/resource bounds.

Reconstruct and diagnose

1. Which symbols represent length 18 and distance 128?
2. Why does a match as the first token fail?
3. A dynamic model saves 3000 payload bits. Can it beat fixed mode on header cost alone?
4. Why do code lengths [1,1,1] have to be rejected before decoding?

Model answers

1. 271 and 127, in different alphabets.
2. There is no previous output to copy; every positive distance exceeds output length zero.
3. No. Dynamic adds 401 bytes = 3208 bits before payload rounding.
4. They need three first-level branches in a binary tree. Canonical assignment would overflow one-bit capacity and alias a prefix.

See RFC 1951 for the production format that motivates the pipeline. Its code lengths, length/distance ranges, header encoding, and bit packing are distinct from this exercise's explicit custom contract.