Deflate backreference ($(\ell ,d)$)

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.

In a Deflate overlapping copy, $\ell >d$: some source bytes are created by the very copy being decoded. For each step $i=0,\dots ,\ell -1$, read the current output at index $n+i-d$ and append that byte at index $n+i$. Because $d\ge 1$, the source index is always smaller than the destination index, so the needed byte exists when it is read.^[ref]

For ABC followed by $(9,3)$, the source indices are $0,1,2,3,4,5,6,7,8$ and the destination indices are $3,4,5,6,7,8,9,10,11$. Steps 0 through 2 copy the original ABC; steps 3 through 5 copy the ABC just appended; steps 6 through 8 copy the next newly appended ABC. Thus the final output is exactly ABCABCABCABC. Taking a snapshot of the original three-byte source slice would produce only three bytes; that operation does not implement the specified nine-byte copy.

The reusable idea is a short description of periodic continuation: the decoder repeatedly looks a fixed distance behind its growing output. A Deflate backreference can also reach across a Deflate block framing boundary. Changing the block's Huffman codes does not by itself erase the decoded history.^[ref]