4. Encodage des distances (Encoding of Distances)

Comme décrit dans la section 2, un composant d'un méta-bloc compressé (Compressed Meta-block) est une séquence de distances arrière (Backward Distances). Dans cette section, nous fournissons les détails de l'encodage des distances.

Chaque distance dans la partie données compressées d'un méta-bloc est représentée par une paire <distance code, extra bits>. Le code de distance (Distance Code) et les bits supplémentaires (Extra Bits) sont encodés dos à dos, le code de distance est encodé en utilisant un code préfixe sur l'alphabet de distance, tandis que la valeur des bits supplémentaires est encodée comme une valeur entière de largeur fixe. Le nombre de bits supplémentaires peut être 0..24, et il dépend du code de distance.

Pour convertir un code de distance et les bits supplémentaires associés en une distance arrière, nous avons besoin de la séquence des distances passées et de deux paramètres supplémentaires : le nombre de "bits postfixe" (postfix bits), désigné par NPOSTFIX (0..3), et le nombre de codes de distance directs (Direct Distance Codes), désigné par NDIRECT (0..120). Ces deux paramètres sont encodés dans l'en-tête du méta-bloc. Nous utiliserons également le paramètre dérivé suivant :

POSTFIX_MASK = (1 << NPOSTFIX) - 1

Les 16 premiers symboles de distance sont des symboles spéciaux qui référencent les distances passées comme suit :

last distance (dernière distance)
second-to-last distance (avant-dernière distance)
third-to-last distance (troisième dernière distance)
fourth-to-last distance (quatrième dernière distance)
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

Le tampon circulaire (Ring Buffer) des quatre dernières distances est initialisé par les valeurs 16, 15, 11, 4 (c'est-à-dire que la quatrième dernière est définie à 16, la troisième dernière à 15, l'avant-dernière à 11, et la dernière distance à 4) au début du flux (par opposition au début du méta-bloc), et il n'est pas réinitialisé aux limites des méta-blocs. Lorsqu'un symbole de distance 0 apparaît, la distance qu'il représente (c'est-à-dire la dernière distance dans la séquence de distances) n'est pas poussée dans le tampon circulaire des dernières distances ; en d'autres termes, l'expression "avant-dernière distance" signifie la deuxième dernière distance qui n'a pas été représentée par un symbole de distance 0 (et de même pour "troisième dernière distance" et "quatrième dernière distance"). De même, les distances qui représentent des mots du dictionnaire statique (Static Dictionary Words) (voir section 8) ne sont pas poussées dans le tampon circulaire des dernières distances.

Si un symbole de distance spécial se résout en une valeur nulle ou négative, le flux doit être rejeté comme invalide.

Si NDIRECT est supérieur à zéro, alors les NDIRECT symboles de distance suivants, de 16 à 15 + NDIRECT, représentent des distances de 1 à NDIRECT. Ni les symboles de distance spéciaux ni les NDIRECT symboles de distance directs ne sont suivis de bits supplémentaires.

Les symboles de distance 16 + NDIRECT et supérieurs ont tous des bits supplémentaires, où le nombre de bits supplémentaires pour un symbole de distance "dcode" est donné par la formule suivante :

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

Le nombre maximum de bits supplémentaires est 24 ; par conséquent, la taille de l'alphabet de symboles de distance est (16 + NDIRECT + (48 << NPOSTFIX)).

Étant donné un symbole de distance "dcode" (>= 16 + NDIRECT) et des bits supplémentaires "dextra", la distance arrière est donnée par la formule suivante :

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

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

4. Encodage des distances (Encoding of Distances)​

4. Encodage des distances (Encoding of Distances)