10. Algorithme de décodage (Decoding Algorithm)

L'algorithme de décodage (Decoding Algorithm) qui produit les données non compressées est le suivant :

lire la taille de la fenêtre
do
   lire le bit ISLAST
   if ISLAST
      lire le bit ISLASTEMPTY
      if ISLASTEMPTY
         sortir de la boucle
   lire MNIBBLES
   if MNIBBLES est zéro
      vérifier que le bit réservé est zéro
      lire MSKIPLEN
      sauter tous les bits jusqu'à la prochaine limite d'octet
      sauter MSKIPLEN octets
      continuer au prochain méta-bloc
   else
      lire MLEN
   if not ISLAST
      lire le bit ISUNCOMPRESSED
      if ISUNCOMPRESSED
         sauter tous les bits jusqu'à la prochaine limite d'octet
         copier MLEN octets de données compressées comme littéraux
         continuer au prochain méta-bloc

   boucle pour chaque trois catégories de blocs (i = L, I, D)
      lire NBLTYPESi
      if NBLTYPESi >= 2
         lire le code préfixe pour les types de blocs, HTREE_BTYPE_i
         lire le code préfixe pour les comptages de blocs, HTREE_BLEN_i
         lire le comptage de blocs, BLEN_i
         définir le type de bloc, BTYPE_i à 0
         initialiser l'avant-dernier et le dernier type de bloc à 0 et 1
      else
         définir le type de bloc, BTYPE_i à 0
         définir le comptage de blocs, BLEN_i à 16777216
   lire NPOSTFIX et NDIRECT
   lire le tableau des modes de contexte littéraux, CMODE[]
   lire NTREESL
   if NTREESL >= 2
      lire la carte de contexte littérale, CMAPL[]
   else
      remplir CMAPL[] avec des zéros
   lire NTREESD
   if NTREESD >= 2
      lire la carte de contexte de distance, CMAPD[]
   else
      remplir CMAPD[] avec des zéros
   lire le tableau des codes préfixes littéraux, HTREEL[]
   lire le tableau des codes préfixes de longueurs insertion-copie, HTREEI[]
   lire le tableau des codes préfixes de distances, HTREED[]
   do
      if BLEN_I est zéro
         lire le type de bloc en utilisant HTREE_BTYPE_I et définir BTYPE_I
            sauvegarder le type de bloc précédent
         lire le comptage de blocs en utilisant HTREE_BLEN_I et définir BLEN_I
      décrémenter BLEN_I
      lire le symbole de longueur insertion-copie en utilisant HTREEI[BTYPE_I]
      calculer la longueur d'insertion, ILEN, et la longueur de copie, CLEN
      boucle pour ILEN
         if BLEN_L est zéro
            lire le type de bloc en utilisant HTREE_BTYPE_L et définir BTYPE_L
               sauvegarder le type de bloc précédent
            lire le comptage de blocs en utilisant HTREE_BLEN_L et définir BLEN_L
         décrémenter BLEN_L
         rechercher le mode de contexte CMODE[BTYPE_L]
         calculer l'ID de contexte, CIDL à partir des deux derniers octets non compressés
         lire le littéral en utilisant HTREEL[CMAPL[64*BTYPE_L + CIDL]]
         écrire le littéral dans le flux non compressé
      if le nombre d'octets non compressés produits dans la boucle pour
         ce méta-bloc est MLEN, alors sortir de la boucle (dans ce cas,
         la longueur de copie est ignorée et peut avoir n'importe quelle valeur)

      if le code de distance est un zéro implicite du code insertion-copie
         définir la distance arrière à la dernière distance
      else
         if BLEN_D est zéro
            lire le type de bloc en utilisant HTREE_BTYPE_D et définir BTYPE_D
               sauvegarder le type de bloc précédent
            lire le comptage de blocs en utilisant HTREE_BLEN_D et définir BLEN_D
         décrémenter BLEN_D
         calculer l'ID de contexte, CIDD à partir de CLEN
         lire le code de distance en utilisant HTREED[CMAPD[4*BTYPE_D + CIDD]]
         calculer la distance par substitution de code court de distance
         if le code de distance n'est pas zéro,
            et la distance n'est pas une référence au dictionnaire statique,
            pousser la distance dans le tampon circulaire des dernières distances
      if la distance est inférieure à la distance maximale autorisée plus un
         reculer de distance octets dans les données non compressées,
         et copier CLEN octets de cette position vers
         le flux non compressé
      else
         rechercher le mot du dictionnaire statique, transformer le mot comme
         indiqué, et copier le résultat dans le flux non compressé
   while nombre d'octets non compressés pour ce méta-bloc < MLEN
while not ISLAST

Si le flux se termine avant l'achèvement du dernier méta-bloc, alors le flux doit être rejeté comme invalide.

Notez qu'une référence de chaîne dupliquée peut faire référence à une chaîne dans un méta-bloc précédent, c'est-à-dire que la distance arrière peut traverser une ou plusieurs limites de méta-blocs. Cependant, une distance de copie arrière ne fera pas référence au-delà du début du flux non compressé ou de la taille de la fenêtre ; toute distance de ce type est interprétée comme une référence à un mot du dictionnaire statique. Notez également que la chaîne référencée peut chevaucher la position actuelle, par exemple, si les 2 derniers octets décodés ont les valeurs X et Y, une référence de chaîne avec <length = 5, distance = 2> ajoute X,Y,X,Y,X au flux non compressé.

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

10. Algorithme de décodage (Decoding Algorithm)​

10. Algorithme de décodage (Decoding Algorithm)