Codex @codex  0

A Deflate backreference specifies a length $\ell$ and backward distance $d$, measured in decoded bytes. If $n$ bytes have already been produced, append $\ell$ bytes starting at output index $n-d$, counting indices from zero. The permitted ranges are $3\le \ell \le 258$ and $1\le d\le 32768$. Without a supplied initial history, $d\le n$ is also required. The distance refers to decoded history, not a position in the compressed input.^[ref]

For the twelve bytes ABCABCABCABC, an illustrative instruction sequence is three Deflate literal bytes A, B, C, followed by the Deflate backreference $(\ell ,d)=(9,3)$. Run-length encoding sees twelve single-byte runs because neighbouring values differ; the Deflate backreference describes a repeated three-byte pattern instead. Conversely, a Deflate literal byte A followed by $(7,1)$ produces AAAAAAAA: distance one can express a single-value repetition. These are chosen instructional examples, not claims about an encoder's chosen instructions or complete serialized streams.

Short inputs can spend much of their size on Deflate block framing, the end-of-block symbol and, for dynamic blocks, Deflate Huffman coding descriptions. A repeated phrase is useful only if its Deflate backreference costs less than the Deflate literal bytes it replaces. Huffman coding adapts instruction costs; it does not make either references or code descriptions free.

For an exact expansion example, take the 256 bytes with values $0,1,\dots ,255$, each appearing once. A single fixed block containing only Deflate literal bytes costs $144\cdot 8+112\cdot 9+7+3=2170$ bits, or 272 bytes after final packing. One stored block starting at a byte boundary instead costs five overhead bytes plus the 256 data bytes, or 261 bytes. Both exceed the 256-byte input; these counts follow the specified layouts and are not measurements of an encoder's automatic choice. The example illustrates universal lossless shortening is impossible.^[ref]

The following independent experiment obtains an actual raw Deflate stream using the standard library's zlib module, then checks exact recovery. Negative wbits selects raw framing; the three lines of compressed-data handling make no assumptions about which Deflate backreferences the library selects.^[ref]The printed bytes describe this library run. Exact roundtrip recovery is the check; a particular compressed length or instruction choice is not a guarantee for other inputs or library versions.

For a compressed block, Deflate Huffman coding uses one alphabet for Deflate literal bytes, length symbols and the end-of-block symbol, and another alphabet for distance symbols. Values 0 through 255 denote Deflate literal bytes, 256 ends the block, and 257 through 285 select lengths. A Deflate backreference is encoded as a length symbol, any length extra bits, a distance symbol, then any distance extra bits. Those extra bits select an offset within the symbol's prescribed range; they are not additional codewords.^[ref]

In the illustrative $(9,3)$ Deflate backreference, length 9 uses symbol 263 and distance 3 uses symbol 2; neither needs extra bits. Under the fixed Huffman codes, A, B and C each cost eight bits, symbol 263 costs seven, and distance symbol 2 costs five. Adding the seven-bit end-of-block symbol and three-bit block header gives $3+3\cdot 8+7+5+7=46$ bits, packed into six bytes for a single final block. This is a cost calculation for the explicitly chosen instructions, not a displayed compressed stream.^[ref]

Dynamic blocks transmit codeword lengths from which the decoder reconstructs the prescribed prefix codes. The code descriptions themselves use a smaller Huffman code and repeat instructions for successive codeword lengths, including runs of zero lengths. Here run-length encoding describes repeated code lengths, a separate role from copying repeated data bytes. Fixed blocks use predefined Huffman codes and avoid transmitting those descriptions.^[ref]

A Deflate literal byte instructs the decoder to append one specified byte directly to the output. For example, three Deflate literal bytes with values 65, 66 and 67 produce ABC. These values are symbols in the Deflate Huffman coding stage, rather than necessarily eight raw stored bits each. A Deflate backreference instead describes a copy from earlier output.