3.1.1.3.2. Sequences_Section (Sequenz-Abschnitt)
Ein komprimierter Block ist ein Kontinuum von Sequenzen. Eine Sequenz ist ein Literal-Kopierbefehl, gefolgt von einem Übereinstimmungs-Kopierbefehl. Der Literal-Kopierbefehl gibt eine Länge an. Es ist die Anzahl der Bytes, die aus dem Literals_Section kopiert (oder extrahiert) werden sollen. Der Übereinstimmungs-Kopierbefehl gibt einen Offset und eine Länge an.
Wenn alle Sequenzen dekodiert wurden und im Literals_Section noch Literale übrig sind, werden diese Bytes am Ende des Blocks hinzugefügt.
Dies wird in Abschnitt 3.1.1.4 ausführlicher beschrieben.
Die Sequences_Section kombiniert alle zum Dekodieren der Befehle erforderlichen Symbole. Es gibt drei Symboltypen: Literal-Längencodes, Offset-Codes und Übereinstimmungslängencodes. Sie werden in einem einzelnen "Bitstrom" verschachtelt kodiert.
Die Sequences_Section beginnt mit einem Header, gefolgt von optionalen Wahrscheinlichkeitstabellen für jeden Symboltyp, dann dem Bitstrom.
Sequences_Section_Header
[Literals_Length_Table]
[Offset_Table]
[Match_Length_Table]
bitStream
Um die Sequences_Section zu dekodieren, muss ihre Größe bekannt sein. Diese Größe wird aus der Größe der Literals_Section abgeleitet:
Sequences_Section_Size = Block_Size - Literals_Section_Header
- Literals_Section_Content
3.1.1.3.2.1. Sequences_Section_Header (Sequenz-Abschnitt-Header)
Dieser Header besteht aus zwei Elementen:
- Number_of_Sequences (Anzahl der Sequenzen)
- Symbol_Compression_Modes (Symbol-Kompressionsmodi)
Number_of_Sequences
Number_of_Sequences ist ein Feld variabler Größe, das 1 bis 3 Bytes verwendet. Wenn das erste Byte "byte0" ist:
-
if (byte0 == 0): Keine Sequenzen. Der Sequenzteil stoppt hier. Der dekomprimierte Inhalt ist vollständig als Literals_Section-Inhalt definiert. Im Repeat_Mode verwendete FSE-Tabellen werden nicht aktualisiert.
-
if (byte0 < 128): Number_of_Sequences = byte0. Verwendet 1 Byte.
-
if (byte0 < 255): Number_of_Sequences =
((byte0 - 128) << 8) + byte1. Verwendet 2 Bytes. -
if (byte0 == 255): Number_of_Sequences =
byte1 + (byte2 << 8) + 0x7F00. Verwendet 3 Bytes.
Symbol_Compression_Modes
Symbol_Compression_Modes ist ein einzelnes Byte, das den Kompressionsmodus für jeden Symboltyp definiert.
| Bitnummer (Bit Number) | Feldname (Field Name) |
|---|---|
| 7-6 | Literal_Lengths_Mode |
| 5-4 | Offsets_Mode |
| 3-2 | Match_Lengths_Mode |
| 1-0 | Reserved (Reserviert) |
Tabelle 14: Symbol_Compression_Modes
Das letzte Feld Reserved muss alles Null sein.
Literals_Lengths_Mode, Offsets_Mode und Match_Lengths_Mode definieren jeweils den Compression_Mode für Literal-Längencodes, Offset-Codes und Übereinstimmungslängencodes. Sie folgen derselben Aufzählung:
| Value (Wert) | Compression_Mode (Kompressionsmodus) |
|---|---|
| 0 | Predefined_Mode (Vordefinierter Modus) |
| 1 | RLE_Mode (RLE-Modus) |
| 2 | FSE_Compressed_Mode (FSE-komprimierter Modus) |
| 3 | Repeat_Mode (Wiederholungsmodus) |
Tabelle 15: Literals_Lengths_Mode, Offsets_Mode und Match_Lengths_Mode
Predefined_Mode (Vordefinierter Modus) : Verwendet vordefinierte FSE (siehe Abschnitt 4.1) Verteilungstabelle, wie in Abschnitt 3.1.1.3.2.2 definiert. Es wird keine Verteilungstabelle vorhanden sein.
RLE_Mode (RLE-Modus) : Die Tabellenbeschreibung besteht aus einem Byte, das den Wert des Symbols enthält. Dieses Symbol wird für alle Sequenzen verwendet.
FSE_Compressed_Mode (FSE-komprimierter Modus) : Standard-FSE-Kompression. Es wird eine Verteilungstabelle vorhanden sein. Das Format dieser Verteilungstabelle wird in Abschnitt 4.1.1 beschrieben. Beachten Sie, dass die maximal zulässige Präzision für Literal-Längencodes und Übereinstimmungslängencodes-Tabellen 9 beträgt, und die maximale Präzision für Offset-Codes-Tabelle 8 beträgt. Wenn nur ein Symbol vorhanden ist, darf dieser Modus nicht verwendet werden; stattdessen sollte RLE_Mode verwendet werden (obwohl jeder andere Modus auch funktioniert).
Repeat_Mode (Wiederholungsmodus) : Die Tabelle, die im vorherigen Compressed_Block mit Number_Of_Sequences > 0 verwendet wurde, wird erneut verwendet, oder wenn dies der erste Block ist, die Tabelle aus dem Wörterbuch. Beachten Sie, dass dies RLE_Mode einschließt, so dass wenn Repeat_Mode RLE_Mode folgt, dasselbe Symbol wiederholt wird. Es schließt auch Predefined_Mode ein, in diesem Fall hat Repeat_Mode dasselbe Ergebnis wie Predefined_Mode. Es wird keine Verteilungstabelle vorhanden sein. Wenn dieser Modus verwendet wird, ohne dass eine vorherige Sequenztabelle im Rahmen (oder Wörterbuch; siehe Abschnitt 5) zu wiederholen ist, sollte dies als Beschädigung betrachtet werden.
3.1.1.3.2.1.1. Sequence Codes for Lengths and Offsets (Sequenzcodes für Längen und Offsets)
Jedes Symbol ist ein Code in seinem eigenen Kontext, der Baseline (Basislinie) und Number_of_Bits (Anzahl der Bits) zum Hinzufügen angibt. Codes werden FSE-komprimiert und im selben Bitstrom mit den ursprünglichen zusätzlichen Bits verschachtelt.
Literals Length Codes (Literal-Längencodes)
Literal-Längencodes sind Werte von 0 bis 35 (einschließlich). Sie definieren Längen von 0 bis 131071 Bytes. Die Literal-Länge entspricht der dekodierten Baseline plus dem Ergebnis des Lesens von Number_of_Bits Bits aus dem Bitstrom (als Little-Endian-Wert).
| Literals_Length_Code | Baseline | Number_of_Bits |
|---|---|---|
| 0-15 | length | 0 |
| 16 | 16 | 1 |
| 17 | 18 | 1 |
| 18 | 20 | 1 |
| 19 | 22 | 1 |
| 20 | 24 | 2 |
| 21 | 28 | 2 |
| 22 | 32 | 3 |
| 23 | 40 | 3 |
| 24 | 48 | 4 |
| 25 | 64 | 6 |
| 26 | 128 | 7 |
| 27 | 256 | 8 |
| 28 | 512 | 9 |
| 29 | 1024 | 10 |
| 30 | 2048 | 11 |
| 31 | 4096 | 12 |
| 32 | 8192 | 13 |
| 33 | 16384 | 14 |
| 34 | 32768 | 15 |
| 35 | 65536 | 16 |
Tabelle 16: Literal-Längencodes
Match Length Codes (Übereinstimmungslängencodes)
Übereinstimmungslängencodes sind Werte von 0 bis 52 (einschließlich). Sie definieren Längen von 3 bis 131074 Bytes. Die Übereinstimmungslänge entspricht der dekodierten Baseline plus dem Ergebnis des Lesens von Number_of_Bits Bits aus dem Bitstrom (als Little-Endian-Wert).
| Match_Length_Code | Baseline | Number_of_Bits |
|---|---|---|
| 0-31 | Match_Length_Code + 3 | 0 |
| 32 | 35 | 1 |
| 33 | 37 | 1 |
| 34 | 39 | 1 |
| 35 | 41 | 1 |
| 36 | 43 | 2 |
| 37 | 47 | 2 |
| 38 | 51 | 3 |
| 39 | 59 | 3 |
| 40 | 67 | 4 |
| 41 | 83 | 4 |
| 42 | 99 | 5 |
| 43 | 131 | 7 |
| 44 | 259 | 8 |
| 45 | 515 | 9 |
| 46 | 1027 | 10 |
| 47 | 2051 | 11 |
| 48 | 4099 | 12 |
| 49 | 8195 | 13 |
| 50 | 16387 | 14 |
| 51 | 32771 | 15 |
| 52 | 65539 | 16 |
Tabelle 17: Übereinstimmungslängencodes
Offset Codes (Offset-Codes)
Offset-Codes sind Werte von 0 bis N.
Der Decoder kann frei sein maximales unterstütztes N begrenzen. Es wird empfohlen, mindestens einen Wert von 22 zu unterstützen. Zum Zeitpunkt des Schreibens beträgt der maximale N-Wert, den der Referenz-Decoder unterstützt, 31.
Offset-Code ist auch die Anzahl der zusätzlichen Bits, die im Little-Endian-Verfahren gelesen werden, kann mit folgender Formel in Offset_Value konvertiert werden:
Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
if (Offset_Value > 3) Offset = Offset_Value - 3;
Dies bedeutet, dass der maximale Offset_Value (2^(N+1)) - 1 beträgt und Rückwärtsreferenzabstände von bis zu (2^(N+1)) - 4 unterstützt werden, aber durch die maximale Rückwärtsreferenzabstand begrenzt sind (siehe Abschnitt 3.1.1.1.2).
Offset_Values von 1 bis 3 sind speziell: Sie definieren "Wiederholungscodes". Dies wird in Abschnitt 3.1.1.5 ausführlicher beschrieben.
3.1.1.3.2.2. Default Distributions (Standard-Verteilungen)
Wenn Predefined_Mode für einen Symboltyp ausgewählt wird, wird seine FSE-Dekodierungstabelle aus der hier definierten vordefinierten Verteilungstabelle generiert. Details zur Konvertierung dieser Verteilung in eine Dekodierungstabelle finden Sie in Abschnitt 4.1.
3.1.1.3.2.2.1. Literals Length Codes (Literal-Längencodes)
Die Dekodierungstabelle verwendet ein Präzisionslog von 6 Bits (64 Zustände).
short literalsLength_defaultDistribution[36] =
{ 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
-1,-1,-1,-1
};
3.1.1.3.2.2.2. Match Length Codes (Übereinstimmungslängencodes)
Die Dekodierungstabelle verwendet ein Präzisionslog von 6 Bits (64 Zustände).
short matchLengths_defaultDistribution[53] =
{ 1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-1,-1,
-1,-1,-1,-1,-1
};
3.1.1.3.2.2.3. Offset Codes (Offset-Codes)
Die Dekodierungstabelle verwendet ein Präzisionslog von 5 Bits (32 Zustände) und unterstützt einen maximalen N-Wert von 28, was Offset-Werte bis zu 536.870.908 ermöglicht.
Wenn eine Sequenz im komprimierten Block einen größeren Offset benötigt, kann sie nicht mit der Standard-Verteilung dargestellt werden.
short offsetCodes_defaultDistribution[29] =
{ 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1,-1,-1,-1,-1,-1
};