7. Modélisation de contexte (Context Modeling)

Comme décrit dans la section 2, l'arbre préfixe (Prefix Tree) utilisé pour encoder un octet littéral (Literal Byte) ou un code de distance (Distance Code) dépend du type de bloc (Block Type) et de l'ID de contexte (Context ID). Cette section spécifie comment calculer l'ID de contexte pour un littéral et un code de distance particuliers et comment encoder la carte de contexte (Context Map) qui mappe une paire <block type, context ID> à l'index d'un code préfixe dans le tableau des codes préfixes littéraux et de distance.

7.1. Modes de contexte et recherche d'ID de contexte pour les littéraux (Context Modes and Context ID Lookup for Literals)

Le contexte (Context) pour encoder le prochain littéral est défini par les deux derniers octets du flux (p1, p2, où p1 est l'octet le plus récent), que ces octets soient produits par des méta-blocs non compressés, des références arrière (Backward References), des références au dictionnaire statique (Static Dictionary References) ou par des insertions littérales (Literal Insertions). Au début du flux, p1 et p2 sont initialisés à zéro.

Il existe quatre méthodes, appelées modes de contexte (Context Modes), pour calculer l'ID de contexte :

LSB6 : l'ID de contexte est la valeur des six bits les moins significatifs de p1.
MSB6 : l'ID de contexte est la valeur des six bits les plus significatifs de p1.
UTF8 : l'ID de contexte est une fonction complexe de p1, p2, optimisée pour la compression de texte.
Signed : l'ID de contexte est une fonction complexe de p1, p2, optimisée pour la compression de séquences d'entiers signés.

L'ID de contexte pour les modes de contexte UTF8 et Signed est calculé à l'aide des tables de recherche suivantes Lut0, Lut1 et Lut2.

Lut0 :=
  0,  0,  0,  0,  0,  0,  0,  0,  0,  4,  4,  0,  0,  4,  0,  0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
  8, 12, 16, 12, 12, 20, 12, 16, 24, 28, 12, 12, 32, 12, 36, 12,
 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 32, 32, 24, 40, 28, 12,
 12, 48, 52, 52, 52, 48, 52, 52, 52, 48, 52, 52, 52, 52, 52, 48,
 52, 52, 52, 52, 52, 48, 52, 52, 52, 52, 52, 24, 12, 28, 12, 12,
 12, 56, 60, 60, 60, 56, 60, 60, 60, 56, 60, 60, 60, 60, 60, 56,
 60, 60, 60, 60, 60, 56, 60, 60, 60, 60, 60, 24, 12, 28, 12,  0,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3

Lut1 :=
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1,
  1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,
  1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Lut2 :=
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7

Les longueurs et les valeurs de vérification CRC-32 (voir Annexe C) de chacune de ces tables en tant que séquence d'octets sont les suivantes :

Table    Length    CRC-32
-----    ------    ------
Lut0     256       0x8e91efb7
Lut1     256       0xd01a32f4
Lut2     256       0x0dd7a0d6

Étant donné que p1 est le dernier octet non compressé et p2 est l'avant-dernier octet non compressé, les ID de contexte peuvent être calculés comme suit :

For LSB6:    Context ID = p1 & 0x3f
For MSB6:    Context ID = p1 >> 2
For UTF8:    Context ID = Lut0[p1] | Lut1[p2]
For Signed:  Context ID = (Lut2[p1] << 3) | Lut2[p2]

À partir des tables de recherche définies ci-dessus et des opérations pour calculer les ID de contexte, nous pouvons voir que les ID de contexte pour les littéraux sont dans la plage 0..63.

Les modes de contexte LSB6, MSB6, UTF8 et Signed sont désignés par les entiers 0, 1, 2, 3.

Un mode de contexte est défini pour chaque type de bloc littéral et ils sont stockés dans un tableau consécutif de bits dans l'en-tête du méta-bloc, toujours deux bits par type de bloc.

7.2. ID de contexte pour les distances (Context ID for Distances)

Le contexte (Context) pour encoder un code de distance est défini par la longueur de copie (Copy Length) correspondant à la distance. Les ID de contexte sont 0, 1, 2 et 3 pour les longueurs de copie 2, 3, 4 et plus de 4, respectivement.

7.3. Encodage de la carte de contexte (Encoding of the Context Map)

Il existe deux cartes de contexte (Context Maps), une pour les littéraux et une pour les distances. La taille de la carte de contexte est 64 * NBLTYPESL pour les littéraux, et 4 * NBLTYPESD pour les distances. Chaque valeur dans la carte de contexte est un entier entre 0 et 255, indiquant l'index du code préfixe à utiliser lors de l'encodage du prochain littéral ou distance.

Les cartes de contexte sont des matrices bidimensionnelles, encodées sous forme de tableaux unidimensionnels :

CMAPL[0..(64 * NBLTYPESL - 1)]
CMAPD[0..(4 * NBLTYPESD - 1)]

L'index du code préfixe pour encoder un code littéral ou de distance avec le type de bloc BTYPE_x et l'ID de contexte CIDx est :

index of literal prefix code = CMAPL[64 * BTYPE_L + CIDL]
index of distance prefix code = CMAPD[4 * BTYPE_D + CIDD]

Les valeurs de la carte de contexte sont encodées avec la combinaison de l'encodage par longueur de course (Run Length Encoding) pour les valeurs nulles et du codage préfixe. Soit RLEMAX le nombre de codes de longueur de course et NTREES la valeur maximale dans la carte de contexte plus un. NTREES doit être égal au nombre de valeurs différentes dans la carte de contexte ; en d'autres termes, les valeurs différentes dans la carte de contexte doivent être l'intervalle [0..NTREES-1]. L'alphabet du code préfixe a les RLEMAX + NTREES symboles suivants :

0: valeur zéro
1: répéter un zéro 2 à 3 fois, lire 1 bit pour la longueur de répétition
2: répéter un zéro 4 à 7 fois, lire 2 bits pour la longueur de répétition
...
RLEMAX: répéter un zéro (1 << RLEMAX) à (1 << (RLEMAX+1))-1 fois,
        lire RLEMAX bits pour la longueur de répétition
RLEMAX + 1: valeur 1
...
RLEMAX + NTREES - 1: valeur NTREES - 1

Si RLEMAX = 0, le codage par longueur de course n'est pas utilisé et les symboles de l'alphabet sont directement les valeurs dans la carte de contexte. Nous pouvons maintenant définir le format de la carte de contexte (le même format est utilisé pour les cartes de contexte littérales et de distance) :

1..5 bits: RLEMAX, 0 est encodé avec un bit 0, et les valeurs 1..16
           sont encodées avec le motif de bits xxxx1 (donc 01001 est 5)

Code préfixe avec taille d'alphabet NTREES + RLEMAX

Valeurs de taille de carte de contexte encodées avec le code préfixe
ci-dessus et le codage par longueur de course pour les valeurs nulles.
Si une longueur de course entraînerait plus de longueurs au total que
la taille de la carte de contexte, alors le flux doit être rejeté
comme invalide.

1 bit:  bit IMTF, si défini, nous effectuons une transformation inverse
        de déplacement vers l'avant (Inverse Move-to-Front Transform)
        sur les valeurs de la carte de contexte pour obtenir les index
        des codes préfixes.

Notez que RLEMAX peut être plus grand que la valeur nécessaire pour représenter la séquence la plus longue de valeurs nulles. De plus, la valeur NTREES est encodée juste avant la carte de contexte comme décrit dans la section 9.2.

Nous définissons la transformation inverse de déplacement vers l'avant (Inverse Move-to-Front Transform) utilisée dans cette spécification par la fonction en langage C suivante :

void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
   uint8_t mtf[256];
   int i;
   for (i = 0; i < 256; ++i) {
      mtf[i] = (uint8_t)i;
   }
   for (i = 0; i < v_len; ++i) {
      uint8_t index = v[i];
      uint8_t value = mtf[index];
      v[i] = value;
      for (; index; --index) {
         mtf[index] = mtf[index - 1];
      }
      mtf[0] = value;
   }
}

Notez que la transformation inverse de déplacement vers l'avant ne produira pas de valeurs en dehors de l'intervalle [0..NTREES-1].

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