9. Format der komprimierten Daten (Compressed Data Format)
9. Format der komprimierten Daten (Compressed Data Format)
In diesem Abschnitt beschreiben wir das Format des komprimierten Datensatzes im Hinblick auf das Format der einzelnen Datenelemente, die in den vorherigen Abschnitten beschrieben wurden.
9.1. Format des Stream-Headers (Format of the Stream Header)
Der Stream-Header (Stream Header) hat nur das folgende eine Feld:
1..7 Bits: WBITS, ein Wert im Bereich 10..24, kodiert mit dem folgenden
Code variabler Länge (wie er in den komprimierten Daten erscheint,
wobei die Bits von rechts nach links analysiert werden):
Value Bit Pattern
----- -----------
10 0100001
11 0110001
12 1000001
13 1010001
14 1100001
15 1110001
16 0
17 0000001
18 0011
19 0101
20 0111
21 1001
22 1011
23 1101
24 1111
Beachten Sie, dass Bitmuster 0010001 ungültig ist und nicht
verwendet werden darf.
Die Größe des Schiebefensters (Sliding Window), die der maximale Wert jeder nicht-wörterbuchbasierten Referenz-Rückwärtsdistanz (Non-Dictionary Reference Backward Distance) ist, wird durch die folgende Formel gegeben:
window size = (1 << WBITS) - 16
9.2. Format des Meta-Block-Headers (Format of the Meta-Block Header)
Ein konformer komprimierter Datensatz hat mindestens einen Meta-Block (Meta-Block). Jeder Meta-Block enthält einen Header mit Informationen über die unkomprimierte Länge des Meta-Blocks und ein Bit, das signalisiert, ob der Meta-Block der letzte ist. Das Format des Meta-Block-Headers ist wie folgt:
1 Bit: ISLAST, auf 1 gesetzt, wenn dies der letzte Meta-Block ist
1 Bit: ISLASTEMPTY, wenn auf 1 gesetzt, ist der Meta-Block leer; dieses
Feld ist nur vorhanden, wenn das ISLAST-Bit gesetzt ist -- wenn es
1 ist, dann enden der Meta-Block und der Brotli-Stream an diesem Bit,
wobei alle verbleibenden Bits im letzten Byte des komprimierten Streams
mit Nullen gefüllt werden (wenn die Füllbits nicht Null sind, sollte
der Stream als ungültig abgelehnt werden)
2 Bits: MNIBBLES, Anzahl der Nibbles zur Darstellung der unkomprimierten
Länge, kodiert mit dem folgenden Code fester Länge:
Value Bit Pattern
----- -----------
0 11
4 00
5 01
6 10
Wenn MNIBBLES 0 ist, ist der Meta-Block leer, d.h., er generiert
keine unkomprimierten Daten. In diesem Fall hat der Rest des
Meta-Blocks das folgende Format:
1 Bit: reserviert, muss Null sein
2 Bits: MSKIPBYTES, Anzahl der Bytes zur Darstellung der
Metadatenlänge
MSKIPBYTES * 8 Bits: MSKIPLEN - 1, wobei MSKIPLEN die Anzahl
der Metadaten-Bytes ist; dieses Feld ist nur vorhanden,
wenn MSKIPBYTES positiv ist; andernfalls ist MSKIPLEN 0
(wenn MSKIPBYTES größer als 1 ist und das letzte Byte
alle Nullen ist, sollte der Stream als ungültig abgelehnt
werden)
0..7 Bits: Füllbits bis zur nächsten Byte-Grenze, müssen alle
Nullen sein
MSKIPLEN Bytes von Metadaten, nicht Teil der unkomprimierten
Daten oder des Schiebefensters
MNIBBLES * 4 Bits: MLEN - 1, wobei MLEN die Länge der unkomprimierten Daten
des Meta-Blocks in Bytes ist (wenn MNIBBLES größer als 4 ist und das
letzte Nibble alle Nullen ist, sollte der Stream als ungültig
abgelehnt werden)
1 Bit: ISUNCOMPRESSED, wenn auf 1 gesetzt, werden alle Bits komprimierter
Daten bis zur nächsten Byte-Grenze ignoriert, und der Rest des
Meta-Blocks enthält MLEN Bytes literaler Daten; dieses Feld ist nur
vorhanden, wenn das ISLAST-Bit nicht gesetzt ist (wenn die ignorierten
Bits nicht alle Nullen sind, sollte der Stream als ungültig abgelehnt
werden)
1..11 Bits: NBLTYPESL, Anzahl der Literal-Blocktypen (Literal Block Types),
kodiert mit dem folgenden Code variabler Länge (wie er in den
komprimierten Daten erscheint, wobei die Bits von rechts nach links
analysiert werden, sodass 0110111 den Wert 12 hat):
Value Bit Pattern
----- -----------
1 0
2 0001
3..4 x0011
5..8 xx0101
9..16 xxx0111
17..32 xxxx1001
33..64 xxxxx1011
65..128 xxxxxx1101
129..256 xxxxxxx1111
Präfixcode über das Blocktyp-Code-Alphabet für Literal-Blocktypen,
erscheint nur, wenn NBLTYPESL >= 2
Präfixcode über das Blockzähl-Code-Alphabet für Literal-Blockzählungen,
erscheint nur, wenn NBLTYPESL >= 2
Blockzählcode + zusätzliche Bits für erste Literal-Blockzählung,
erscheint nur, wenn NBLTYPESL >= 2
1..11 Bits: NBLTYPESI, Anzahl der Insert-and-Copy-Blocktypen
(Insert-and-Copy Block Types), kodiert mit demselben Code
variabler Länge wie oben
Präfixcode über das Blocktyp-Code-Alphabet für Insert-and-Copy-Blocktypen,
erscheint nur, wenn NBLTYPESI >= 2
Präfixcode über das Blockzähl-Code-Alphabet für Insert-and-Copy-
Blockzählungen, erscheint nur, wenn NBLTYPESI >= 2
Blockzählcode + zusätzliche Bits für erste Insert-and-Copy-Blockzählung,
erscheint nur, wenn NBLTYPESI >= 2
1..11 Bits: NBLTYPESD, Anzahl der Distanz-Blocktypen (Distance Block Types),
kodiert mit demselben Code variabler Länge wie oben
Präfixcode über das Blocktyp-Code-Alphabet für Distanz-Blocktypen,
erscheint nur, wenn NBLTYPESD >= 2
Präfixcode über das Blockzähl-Code-Alphabet für Distanz-Blockzählungen,
erscheint nur, wenn NBLTYPESD >= 2
Blockzählcode + zusätzliche Bits für erste Distanz-Blockzählung,
erscheint nur, wenn NBLTYPESD >= 2
2 Bits: NPOSTFIX, Parameter, der in der Distanzkodierung verwendet wird
4 Bits: vier höchstwertigsten Bits von NDIRECT, um den tatsächlichen Wert
des Parameters NDIRECT zu erhalten, verschieben Sie diese Vier-Bit-
Zahl um NPOSTFIX Bits nach links
NBLTYPESL * 2 Bits: Kontextmodus für jeden Literal-Blocktyp
1..11 Bits: NTREESL, Anzahl der Literal-Präfixbäume, kodiert mit demselben
Code variabler Länge wie NBLTYPESL
Literal-Kontextkarte, kodiert wie in Abschnitt 7.3 beschrieben,
erscheint nur, wenn NTREESL >= 2; andernfalls hat die Kontextkarte
nur Nullwerte
1..11 Bits: NTREESD, Anzahl der Distanz-Präfixbäume, kodiert mit demselben
Code variabler Länge wie NBLTYPESD
Distanz-Kontextkarte, kodiert wie in Abschnitt 7.3 beschrieben,
erscheint nur, wenn NTREESD >= 2; andernfalls hat die Kontextkarte
nur Nullwerte
NTREESL Präfixcodes für Literale
NBLTYPESI Präfixcodes für Insert-and-Copy-Längen
NTREESD Präfixcodes für Distanzen
9.3. Format der Meta-Block-Daten (Format of the Meta-Block Data)
Der komprimierte Datenteil eines Meta-Blocks besteht aus einer Serie von Befehlen (Commands). Jeder Befehl hat das folgende Format:
Blocktyp-Code für nächsten Insert-and-Copy-Blocktyp, erscheint nur, wenn
NBLTYPESI >= 2 und die vorherige Insert-and-Copy-Blockzählung Null ist
Blockzählcode + zusätzliche Bits für nächste Insert-and-Copy-Blockzählung,
erscheint nur, wenn NBLTYPESI >= 2 und die vorherige Insert-and-Copy-
Blockzählung Null ist
Insert-and-Copy-Länge, kodiert wie in Abschnitt 5, unter Verwendung des
Insert-and-Copy-Längenpräfixcodes mit dem aktuellen Insert-and-Copy-
Blocktypindex
Einfügelänge Anzahl von Literalen, mit dem folgenden Format:
Blocktyp-Code für nächsten Literal-Blocktyp, erscheint nur, wenn
NBLTYPESL >= 2 und die vorherige Literal-Blockzählung Null ist
Blockzählcode + zusätzliche Bits für nächste Literal-Blockzählung,
erscheint nur, wenn NBLTYPESL >= 2 und die vorherige Literal-
Blockzählung Null ist
Nächstes Byte der unkomprimierten Daten, kodiert mit dem Literal-
Präfixcode mit dem Index, der durch die vorherigen zwei Bytes der
unkomprimierten Daten, den aktuellen Literal-Blocktyp und die
Kontextkarte bestimmt wird, wie in Abschnitt 7.3 beschrieben
Blocktyp-Code für nächsten Distanz-Blocktyp, erscheint nur, wenn
NBLTYPESD >= 2 und die vorherige Distanz-Blockzählung Null ist
Blockzählcode + zusätzliche Bits für nächste Distanz-Blockzählung,
erscheint nur, wenn NBLTYPESD >= 2 und die vorherige Distanz-
Blockzählung Null ist
Distanzcode, kodiert wie in Abschnitt 4, unter Verwendung des Distanz-
Präfixcodes mit dem Index, der durch die Kopierlänge, den aktuellen
Distanz-Blocktyp und die Distanz-Kontextkarte bestimmt wird, wie in
Abschnitt 7.3 beschrieben, erscheint nur, wenn der Distanzcode keine
implizite 0 ist, wie durch den Insert-and-Copy-Längencode angegeben
Die Anzahl der Befehle im Meta-Block ist so, dass die Summe der erzeugten unkomprimierten Bytes (d.h. die Anzahl der eingefügten Literale plus die Anzahl der aus vergangenen Daten kopierten Bytes oder aus dem statischen Wörterbuch generierten Bytes) über alle Befehle die unkomprimierte Länge MLEN ergibt, die im Meta-Block-Header kodiert ist.
Wenn die Gesamtzahl der erzeugten unkomprimierten Bytes nach dem Einfügeteil des letzten Befehls gleich MLEN ist, wird die Kopierlänge des letzten Befehls ignoriert und erzeugt keine unkomprimierte Ausgabe. In diesem Fall kann die Kopierlänge des letzten Befehls einen beliebigen Wert haben. In jedem anderen Fall sollte der Stream als ungültig abgelehnt werden, wenn die Anzahl der einzufügenden Literale, die Kopierlänge oder die resultierende Wörterbuch-Wortlänge dazu führen würde, dass MLEN überschritten wird.
Wenn der letzte Befehl des letzten nicht leeren Meta-Blocks nicht an einer Byte-Grenze endet, müssen die ungenutzten Bits im letzten Byte Nullen sein.
Quelle (Source): RFC 7932, Section 9
Offizieller Text (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt