= Deflate backreference
{c}
{title2=$(\ell,d)$}
= Deflate length-distance pair
{c}
{synonym}
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\leq\ell\leq258$ and $1\leq d\leq32768$. Without a supplied initial history, $d\leq n$ is also required. The distance refers to decoded history, not a position in the compressed <input>.<DEFLATE Compressed Data Format Specification version 1.3 by L. Peter Deutsch>[RFC 1951, sections 3.2.3 and 3.2.5: available history, overlap, length and distance ranges]{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.
Back to article page
