8. Dictionnaire statique (Static Dictionary)

À tout moment donné pendant le décodage des données compressées, une référence à une chaîne dupliquée dans les données non compressées produites jusqu'à présent a une valeur de distance arrière maximale (Maximum Backward Distance Value), qui est le minimum de la taille de la fenêtre (Window Size) et du nombre d'octets non compressés produits. Cependant, le décodage d'une distance à partir du flux compressé, comme décrit dans la section 4, peut produire des distances supérieures à cette valeur maximale autorisée. Dans ce cas, la distance est traitée comme une référence à un mot dans le dictionnaire statique (Static Dictionary) donné dans l'annexe A. La longueur de copie (Copy Length) pour une référence au dictionnaire statique doit être comprise entre 4 et 24.

Le dictionnaire statique a trois parties :

DICT[0..DICTSIZE] : un tableau d'octets
DOFFSET[0..24] : un tableau de valeurs de décalage d'octets pour chaque longueur
NDBITS[0..24] : un tableau de valeurs de profondeur de bits pour chaque longueur

Le nombre de mots du dictionnaire statique pour une longueur donnée est :

NWORDS[length] = 0                       (if length < 4)
NWORDS[length] = (1 << NDBITS[length])   (if length >= 4)

DOFFSET et DICTSIZE sont définis par la récursion suivante :

DOFFSET[0] = 0
DOFFSET[length + 1] = DOFFSET[length] + length * NWORDS[length]
DICTSIZE = DOFFSET[24] + 24 * NWORDS[24]

Le décalage d'un mot dans le tableau DICT pour une longueur et un index donnés est :

offset(length, index) = DOFFSET[length] + index * length

Chaque mot du dictionnaire statique a 121 formes différentes, obtenues en appliquant une transformation de mot (Word Transformation) à un mot de base (Base Word) dans le tableau DICT. La liste des transformations de mots est donnée dans l'annexe B. Le mot du dictionnaire statique pour une paire <length, distance> peut être reconstruit comme suit :

word_id = distance - (max allowed distance + 1)
index = word_id % NWORDS[length]
base_word = DICT[offset(length, index)..offset(length, index+1)-1]
transform_id = word_id >> NDBITS[length]

La chaîne copiée dans le flux non compressé est calculée en appliquant la transformation au mot de base du dictionnaire. Si transform_id est supérieur à 120, ou si la longueur est inférieure à 4 ou supérieure à 24, alors le flux compressé doit être rejeté comme invalide.

Chaque transformation de mot a la forme suivante :

transform_i(word) = prefix_i + T_i(word) + suffix_i

où l'indice _i dénote le transform_id ci-dessus. Chaque T_i est l'une des 21 transformations élémentaires (Elementary Transforms) suivantes :

Identity, FermentFirst, FermentAll,
OmitFirst1, ..., OmitFirst9, OmitLast1, ..., OmitLast9

La forme de ces transformations élémentaires est la suivante :

Identity(word) = word

FermentFirst(word) = voir ci-dessous

FermentAll(word) = voir ci-dessous

OmitFirstk(word) = les derniers (length(word) - k) octets de word, ou
                   chaîne vide si length(word) < k

OmitLastk(word) = les premiers (length(word) - k) octets de word, ou
                  chaîne vide si length(word) < k

Nous définissons les transformations FermentFirst et FermentAll utilisées dans cette spécification par les fonctions en langage C suivantes :

int Ferment(uint8_t* word, int word_len, int pos) {
   if (word[pos] < 192) {
      if (word[pos] >= 97 and word[pos] <= 122) {
         word[pos] = word[pos] ^ 32;
      }
      return 1;
   } else if (word[pos] < 224) {
      if (pos + 1 < word_len) {
         word[pos + 1] = word[pos + 1] ^ 32;
      }
      return 2;
   } else {
      if (pos + 2 < word_len) {
         word[pos + 2] = word[pos + 2] ^ 5;
      }
      return 3;
   }
}

void FermentFirst(uint8_t* word, int word_len) {
   if (word_len > 0) {
      Ferment(word, word_len, 0);
   }
}

void FermentAll(uint8_t* word, int word_len) {
   int i = 0;
   while (i < word_len) {
      i += Ferment(word, word_len, i);
   }
}

L'annexe B contient la liste des transformations en spécifiant les composants préfixe (Prefix), transformation élémentaire (Elementary Transform) et suffixe (Suffix) de chacune d'elles. Notez que la transformation élémentaire OmitFirst8 n'est pas utilisée dans la liste des transformations. Les chaînes de l'annexe B sont au format de chaîne C en ce qui concerne les caractères d'échappement (barre oblique inverse).

Le nombre maximal d'octets supplémentaires qu'une transformation peut ajouter à un mot de base est de 13. Puisque le plus grand mot de base fait 24 octets de long, un tampon de 38 octets est suffisant pour stocker tous les mots transformés (en comptant un octet zéro de terminaison).

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

8. Dictionnaire statique (Static Dictionary)​

8. Dictionnaire statique (Static Dictionary)