4. Kodierung von Distanzen (Encoding of Distances)
4. Kodierung von Distanzen (Encoding of Distances)
Wie in Abschnitt 2 beschrieben, ist eine Komponente eines komprimierten Meta-Blocks (Compressed Meta-block) eine Sequenz von Rückwärtsdistanzen (Backward Distances). In diesem Abschnitt geben wir die Details zur Kodierung von Distanzen an.
Jede Distanz im komprimierten Datenteil eines Meta-Blocks wird durch ein Paar <distance code, extra bits> dargestellt. Der Distanzcode (Distance Code) und die Extrabits (Extra Bits) werden hintereinander kodiert, der Distanzcode wird unter Verwendung eines Präfixcodes über dem Distanzalphabet kodiert, während der Extrabitswert als ganzzahliger Wert fester Breite kodiert wird. Die Anzahl der Extrabits kann 0..24 betragen und ist vom Distanzcode abhängig.
Um einen Distanzcode und zugehörige Extrabits in eine Rückwärtsdistanz zu konvertieren, benötigen wir die Sequenz der vergangenen Distanzen und zwei zusätzliche Parameter: die Anzahl der "Postfix-Bits" (postfix bits), bezeichnet durch NPOSTFIX (0..3), und die Anzahl der direkten Distanzcodes (Direct Distance Codes), bezeichnet durch NDIRECT (0..120). Beide Parameter sind im Meta-Block-Header kodiert. Wir verwenden auch den folgenden abgeleiteten Parameter:
POSTFIX_MASK = (1 << NPOSTFIX) - 1
Die ersten 16 Distanzsymbole sind spezielle Symbole, die vergangene Distanzen wie folgt referenzieren:
0: last distance (letzte Distanz)
1: second-to-last distance (vorletzte Distanz)
2: third-to-last distance (drittletzte Distanz)
3: fourth-to-last distance (viertletzte Distanz)
4: last distance - 1
5: last distance + 1
6: last distance - 2
7: last distance + 2
8: last distance - 3
9: last distance + 3
10: second-to-last distance - 1
11: second-to-last distance + 1
12: second-to-last distance - 2
13: second-to-last distance + 2
14: second-to-last distance - 3
15: second-to-last distance + 3
Der Ringpuffer (Ring Buffer) der vier letzten Distanzen wird zu Beginn des Streams (im Gegensatz zum Beginn des Meta-Blocks) mit den Werten 16, 15, 11, 4 initialisiert (d.h. die viertletzte wird auf 16 gesetzt, die drittletzte auf 15, die vorletzte auf 11 und die letzte Distanz auf 4), und er wird an Meta-Block-Grenzen nicht zurückgesetzt. Wenn ein Distanzsymbol 0 erscheint, wird die Distanz, die es darstellt (d.h. die letzte Distanz in der Sequenz der Distanzen), nicht in den Ringpuffer der letzten Distanzen geschoben; mit anderen Worten, der Ausdruck "vorletzte Distanz" bedeutet die vorletzte Distanz, die nicht durch ein 0-Distanzsymbol dargestellt wurde (und ähnlich für "drittletzte Distanz" und "viertletzte Distanz"). Ebenso werden Distanzen, die statische Wörterbuchworte (Static Dictionary Words) darstellen (siehe Abschnitt 8), nicht in den Ringpuffer der letzten Distanzen geschoben.
Wenn sich ein spezielles Distanzsymbol zu einem null- oder negativen Wert auflöst, sollte der Stream als ungültig abgelehnt werden.
Wenn NDIRECT größer als null ist, repräsentieren die nächsten NDIRECT Distanzsymbole von 16 bis 15 + NDIRECT Distanzen von 1 bis NDIRECT. Weder die speziellen Distanzsymbole noch die NDIRECT direkten Distanzsymbole werden von Extrabits gefolgt.
Distanzsymbole 16 + NDIRECT und größer haben alle Extrabits, wobei die Anzahl der Extrabits für ein Distanzsymbol "dcode" durch die folgende Formel gegeben ist:
ndistbits = 1 + ((dcode - NDIRECT - 16) >> (NPOSTFIX + 1))
Die maximale Anzahl von Extrabits ist 24; daher beträgt die Größe des Distanzsymbol-Alphabets (16 + NDIRECT + (48 << NPOSTFIX)).
Bei einem Distanzsymbol "dcode" (>= 16 + NDIRECT) und Extrabits "dextra" wird die Rückwärtsdistanz durch die folgende Formel gegeben:
hcode = (dcode - NDIRECT - 16) >> NPOSTFIX
lcode = (dcode - NDIRECT - 16) & POSTFIX_MASK
offset = ((2 + (hcode & 1)) << ndistbits) - 4
distance = ((offset + dextra) << NPOSTFIX) + lcode + NDIRECT + 1
Quelle (Source): RFC 7932, Section 4
Offizieller Text (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt