Zum Hauptinhalt springen

8. Statisches Wörterbuch (Static Dictionary)

8. Statisches Wörterbuch (Static Dictionary)​

Zu jedem gegebenen Zeitpunkt während des Dekodierens der komprimierten Daten hat eine Referenz auf eine duplizierte Zeichenkette in den bisher erzeugten unkomprimierten Daten einen maximalen Rückwärtsdistanzwert (Maximum Backward Distance Value), der das Minimum aus der Fenstergröße (Window Size) und der Anzahl der erzeugten unkomprimierten Bytes ist. Das Dekodieren einer Distanz aus dem komprimierten Stream, wie in Abschnitt 4 beschrieben, kann jedoch Distanzen erzeugen, die größer als dieser maximal zulässige Wert sind. In diesem Fall wird die Distanz als Referenz auf ein Wort im statischen Wörterbuch (Static Dictionary) behandelt, das in Anhang A angegeben ist. Die Kopierlänge (Copy Length) für eine statische Wörterbuchreferenz muss zwischen 4 und 24 liegen.

Das statische Wörterbuch hat drei Teile:

  • DICT[0..DICTSIZE]: ein Array von Bytes
  • DOFFSET[0..24]: ein Array von Byte-Offset-Werten für jede Länge
  • NDBITS[0..24]: ein Array von Bit-Tiefenwerten für jede Länge

Die Anzahl der statischen Wörterbuch-Wörter für eine gegebene Länge ist:

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

DOFFSET und DICTSIZE werden durch die folgende Rekursion definiert:

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

Der Offset eines Wortes innerhalb des DICT-Arrays für eine gegebene Länge und einen Index ist:

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

Jedes statische Wörterbuch-Wort hat 121 verschiedene Formen, die durch Anwendung einer Worttransformation (Word Transformation) auf ein Basiswort (Base Word) im DICT-Array erhalten werden. Die Liste der Worttransformationen ist in Anhang B angegeben. Das statische Wörterbuch-Wort für ein <length, distance>-Paar kann wie folgt rekonstruiert werden:

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]

Die in den unkomprimierten Stream kopierte Zeichenkette wird berechnet, indem die Transformation auf das Basiswörterbuch-Wort angewendet wird. Wenn transform_id größer als 120 ist oder die Länge kleiner als 4 oder größer als 24 ist, sollte der komprimierte Stream als ungültig abgelehnt werden.

Jede Worttransformation hat die folgende Form:

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

wobei der _i-Index die oben genannte transform_id bezeichnet. Jedes T_i ist eine der folgenden 21 elementaren Transformationen (Elementary Transforms):

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

Die Form dieser elementaren Transformationen ist wie folgt:

Identity(word) = word

FermentFirst(word) = siehe unten

FermentAll(word) = siehe unten

OmitFirstk(word) = die letzten (length(word) - k) Bytes von word, oder
                   leere Zeichenkette wenn length(word) < k

OmitLastk(word) = die ersten (length(word) - k) Bytes von word, oder
                  leere Zeichenkette wenn length(word) < k

Wir definieren die in dieser Spezifikation verwendeten FermentFirst- und FermentAll-Transformationen durch die folgenden C-Sprache-Funktionen:

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);
   }
}

Anhang B enthält die Liste der Transformationen, indem die Präfix- (Prefix), elementare Transformations- (Elementary Transform) und Suffix-Komponenten jeder von ihnen spezifiziert werden. Beachten Sie, dass die elementare Transformation OmitFirst8 in der Liste der Transformationen nicht verwendet wird. Die Zeichenketten in Anhang B sind im C-String-Format in Bezug auf Escape-(Backslash-)Zeichen.

Die maximale Anzahl zusätzlicher Bytes, die eine Transformation zu einem Basiswort hinzufügen kann, beträgt 13. Da das größte Basiswort 24 Bytes lang ist, ist ein Puffer von 38 Bytes ausreichend, um alle transformierten Wörter zu speichern (einschließlich eines abschließenden Null-Bytes).

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

Letztes Update am