10. Dekodierungsalgorithmus (Decoding Algorithm)

Der Dekodierungsalgorithmus (Decoding Algorithm), der die unkomprimierten Daten erzeugt, ist wie folgt:

Fenstergröße lesen
do
   ISLAST-Bit lesen
   if ISLAST
      ISLASTEMPTY-Bit lesen
      if ISLASTEMPTY
         aus der Schleife ausbrechen
   MNIBBLES lesen
   if MNIBBLES ist Null
      überprüfen, dass das reservierte Bit Null ist
      MSKIPLEN lesen
      alle Bits bis zur nächsten Byte-Grenze überspringen
      MSKIPLEN Bytes überspringen
      zum nächsten Meta-Block fortfahren
   else
      MLEN lesen
   if not ISLAST
      ISUNCOMPRESSED-Bit lesen
      if ISUNCOMPRESSED
         alle Bits bis zur nächsten Byte-Grenze überspringen
         MLEN Bytes komprimierter Daten als Literale kopieren
         zum nächsten Meta-Block fortfahren

   Schleife für jede drei Blockkategorien (i = L, I, D)
      NBLTYPESi lesen
      if NBLTYPESi >= 2
         Präfixcode für Blocktypen lesen, HTREE_BTYPE_i
         Präfixcode für Blockzählungen lesen, HTREE_BLEN_i
         Blockzählung lesen, BLEN_i
         Blocktyp setzen, BTYPE_i auf 0
         vorletzten und letzten Blocktyp auf 0 und 1 initialisieren
      else
         Blocktyp setzen, BTYPE_i auf 0
         Blockzählung setzen, BLEN_i auf 16777216
   NPOSTFIX und NDIRECT lesen
   Array von Literal-Kontextmodi lesen, CMODE[]
   NTREESL lesen
   if NTREESL >= 2
      Literal-Kontextkarte lesen, CMAPL[]
   else
      CMAPL[] mit Nullen füllen
   NTREESD lesen
   if NTREESD >= 2
      Distanz-Kontextkarte lesen, CMAPD[]
   else
      CMAPD[] mit Nullen füllen
   Array von Literal-Präfixcodes lesen, HTREEL[]
   Array von Insert-and-Copy-Längenpräfixcodes lesen, HTREEI[]
   Array von Distanz-Präfixcodes lesen, HTREED[]
   do
      if BLEN_I ist Null
         Blocktyp mit HTREE_BTYPE_I lesen und BTYPE_I setzen
            vorherigen Blocktyp speichern
         Blockzählung mit HTREE_BLEN_I lesen und BLEN_I setzen
      BLEN_I dekrementieren
      Insert-and-Copy-Längensymbol mit HTREEI[BTYPE_I] lesen
      Einfügelänge ILEN und Kopierlänge CLEN berechnen
      Schleife für ILEN
         if BLEN_L ist Null
            Blocktyp mit HTREE_BTYPE_L lesen und BTYPE_L setzen
               vorherigen Blocktyp speichern
            Blockzählung mit HTREE_BLEN_L lesen und BLEN_L setzen
         BLEN_L dekrementieren
         Kontextmodus CMODE[BTYPE_L] nachschlagen
         Kontext-ID CIDL aus den letzten zwei unkomprimierten Bytes berechnen
         Literal mit HTREEL[CMAPL[64*BTYPE_L + CIDL]] lesen
         Literal in unkomprimierten Stream schreiben
      if Anzahl der in der Schleife für diesen Meta-Block erzeugten
         unkomprimierten Bytes gleich MLEN ist, dann aus der Schleife
         ausbrechen (in diesem Fall wird die Kopierlänge ignoriert und
         kann einen beliebigen Wert haben)

      if Distanzcode ein implizites Null aus Insert-and-Copy-Code ist
         Rückwärtsdistanz auf letzte Distanz setzen
      else
         if BLEN_D ist Null
            Blocktyp mit HTREE_BTYPE_D lesen und BTYPE_D setzen
               vorherigen Blocktyp speichern
            Blockzählung mit HTREE_BLEN_D lesen und BLEN_D setzen
         BLEN_D dekrementieren
         Kontext-ID CIDD aus CLEN berechnen
         Distanzcode mit HTREED[CMAPD[4*BTYPE_D + CIDD]] lesen
         Distanz durch Distanz-Kurzcode-Substitution berechnen
         if Distanzcode nicht Null ist,
            und Distanz keine statische Wörterbuchreferenz ist,
            Distanz in den Ringpuffer der letzten Distanzen schieben
      if Distanz kleiner als die maximal zulässige Distanz plus eins ist
         Distanz Bytes rückwärts in den unkomprimierten Daten bewegen,
         und CLEN Bytes von dieser Position in den
         unkomprimierten Stream kopieren
      else
         statisches Wörterbuch-Wort nachschlagen, Wort wie angewiesen
         transformieren und Ergebnis in den unkomprimierten Stream kopieren
   while Anzahl unkomprimierter Bytes für diesen Meta-Block < MLEN
while not ISLAST

Wenn der Stream vor Abschluss des letzten Meta-Blocks endet, sollte der Stream als ungültig abgelehnt werden.

Beachten Sie, dass eine duplizierte Zeichenkettenreferenz auf eine Zeichenkette in einem vorherigen Meta-Block verweisen kann, d.h. die Rückwärtsdistanz kann eine oder mehrere Meta-Block-Grenzen überschreiten. Eine Rückwärtskopierdistanz wird jedoch nicht über den Anfang des unkomprimierten Streams oder die Fenstergröße hinaus verweisen; jede solche Distanz wird als Referenz auf ein statisches Wörterbuch-Wort interpretiert. Beachten Sie auch, dass die referenzierte Zeichenkette die aktuelle Position überlappen kann, zum Beispiel, wenn die letzten 2 dekodierten Bytes die Werte X und Y haben, fügt eine Zeichenkettenreferenz mit <length = 5, distance = 2> X,Y,X,Y,X zum unkomprimierten Stream hinzu.

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

10. Dekodierungsalgorithmus (Decoding Algorithm)​

10. Dekodierungsalgorithmus (Decoding Algorithm)