4. Codifica delle distanze (Encoding of Distances)

Come descritto nella sezione 2, un componente di un meta-blocco compresso (Compressed Meta-block) è una sequenza di distanze all'indietro (Backward Distances). In questa sezione, forniamo i dettagli sulla codifica delle distanze.

Ogni distanza nella parte dati compressi di un meta-blocco è rappresentata da una coppia <distance code, extra bits>. Il codice di distanza (Distance Code) e i bit extra (Extra Bits) sono codificati uno dopo l'altro, il codice di distanza è codificato utilizzando un codice prefisso sull'alfabeto delle distanze, mentre il valore dei bit extra è codificato come valore intero a larghezza fissa. Il numero di bit extra può essere 0..24, e dipende dal codice di distanza.

Per convertire un codice di distanza e i bit extra associati in una distanza all'indietro, abbiamo bisogno della sequenza delle distanze passate e di due parametri aggiuntivi: il numero di "bit postfisso" (postfix bits), indicato da NPOSTFIX (0..3), e il numero di codici di distanza diretti (Direct Distance Codes), indicato da NDIRECT (0..120). Entrambi questi parametri sono codificati nell'header del meta-blocco. Utilizzeremo anche il seguente parametro derivato:

POSTFIX_MASK = (1 << NPOSTFIX) - 1

I primi 16 simboli di distanza sono simboli speciali che fanno riferimento alle distanze passate come segue:

last distance (ultima distanza)
second-to-last distance (penultima distanza)
third-to-last distance (terzultima distanza)
fourth-to-last distance (quartultima distanza)
last distance - 1
last distance + 1
last distance - 2
last distance + 2
last distance - 3
last distance + 3
second-to-last distance - 1
second-to-last distance + 1
second-to-last distance - 2
second-to-last distance + 2
second-to-last distance - 3
second-to-last distance + 3

Il buffer circolare (Ring Buffer) delle quattro ultime distanze è inizializzato con i valori 16, 15, 11, 4 (cioè la quartultima è impostata a 16, la terzultima a 15, la penultima a 11, e l'ultima distanza a 4) all'inizio del flusso (al contrario dell'inizio del meta-blocco), e non viene reimpostato ai confini dei meta-blocchi. Quando appare un simbolo di distanza 0, la distanza che rappresenta (cioè l'ultima distanza nella sequenza di distanze) non viene spinta nel buffer circolare delle ultime distanze; in altre parole, l'espressione "penultima distanza" significa la penultima distanza che non è stata rappresentata da un simbolo di distanza 0 (e similmente per "terzultima distanza" e "quartultima distanza"). Allo stesso modo, le distanze che rappresentano parole del dizionario statico (Static Dictionary Words) (vedere sezione 8) non vengono spinte nel buffer circolare delle ultime distanze.

Se un simbolo di distanza speciale si risolve in un valore zero o negativo, il flusso dovrebbe essere rifiutato come non valido.

Se NDIRECT è maggiore di zero, allora i successivi NDIRECT simboli di distanza, da 16 a 15 + NDIRECT, rappresentano distanze da 1 a NDIRECT. Né i simboli di distanza speciali né i NDIRECT simboli di distanza diretti sono seguiti da bit extra.

I simboli di distanza 16 + NDIRECT e superiori hanno tutti bit extra, dove il numero di bit extra per un simbolo di distanza "dcode" è dato dalla seguente formula:

ndistbits = 1 + ((dcode - NDIRECT - 16) >> (NPOSTFIX + 1))

Il numero massimo di bit extra è 24; pertanto, la dimensione dell'alfabeto dei simboli di distanza è (16 + NDIRECT + (48 << NPOSTFIX)).

Dato un simbolo di distanza "dcode" (>= 16 + NDIRECT) e bit extra "dextra", la distanza all'indietro è data dalla seguente formula:

hcode = (dcode - NDIRECT - 16) >> NPOSTFIX
lcode = (dcode - NDIRECT - 16) & POSTFIX_MASK
offset = ((2 + (hcode & 1)) << ndistbits) - 4
distance = ((offset + dextra) << NPOSTFIX) + lcode + NDIRECT + 1

Fonte (Source): RFC 7932, Section 4
Testo ufficiale (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt

4. Codifica delle distanze (Encoding of Distances)​

4. Codifica delle distanze (Encoding of Distances)