Zum Hauptinhalt springen

3.1.1.3. Compressed Blocks (Komprimierte Blöcke)

Um einen komprimierten Block zu dekomprimieren, muss die komprimierte Größe aus dem Block_Size-Feld innerhalb des Block_Header bereitgestellt werden.

Ein komprimierter Block besteht aus zwei Teilen: Literals_Section (Literal-Abschnitt, Abschnitt 3.1.1.3.1) und Sequences_Section (Sequenz-Abschnitt, Abschnitt 3.1.1.3.2). Die Ergebnisse dieser beiden Teile werden dann kombiniert, um in der Sequenzausführung (Abschnitt 3.1.1.4) dekomprimierte Daten zu erzeugen.

Um einen komprimierten Block zu dekodieren, werden folgende Elemente benötigt:

  • Zuvor dekodierte Daten, bis zu einer Entfernung von Window_Size oder dem Anfang des Rahmens, je nachdem, was kleiner ist. Im letzteren Fall wird Single_Segment_Flag gesetzt.

  • Liste "Neueste Offsets", aus dem vorherigen Compressed_Block.

  • Vorheriger Huffman-Baum, benötigt für Treeless_Literals_Block-Typ.

  • Vorherige Finite State Entropy (FSE) Dekodierungstabellen, benötigt für Repeat_Mode, für jeden Symboltyp (Literal-Längencodes, Übereinstimmungslängencodes, Offset-Codes).

Beachten Sie, dass Dekodierungstabellen nicht immer aus dem vorherigen Compressed_Block stammen:

  • Jede Dekodierungstabelle kann aus dem Wörterbuch stammen.
  • Der Huffman-Baum stammt aus dem vorherigen Compressed_Literals_Block.

3.1.1.3.1. Literals_Section_Header (Literal-Abschnitt-Header)​

Alle Literale werden im ersten Teil des Blocks neu zusammengesetzt. Sie können zuerst dekodiert und dann während der Sequenzausführung (siehe Abschnitt 3.1.1.4) kopiert werden, oder sie können während der Sequenzausführung on-the-fly dekodiert werden.

Literale können unkomprimiert gespeichert oder mit Huffman-Präfixcode komprimiert werden. Wenn komprimiert, kann eine optionale Baumbeschreibung vorhanden sein, gefolgt von 1 oder 4 Streams.

+----------------------------+
||  Literals_Section_Header   |
+----------------------------+
|| [Huffman_Tree_Description] |
+----------------------------+
||        [Jump_Table]        |
+----------------------------+
||          Stream_1          |
+----------------------------+
||         [Stream_2]         |
+----------------------------+
||         [Stream_3]         |
+----------------------------+
||         [Stream_4]         |
+----------------------------+

Tabelle 11: Komprimierte Literale

3.1.1.3.1.1. Literals_Section_Header (Literal-Abschnitt-Header)​

Dieses Feld beschreibt, wie Literale verpackt sind. Es ist ein byte-ausgerichtetes Bitfeld variabler Größe, das von 1 bis 5 Bytes reicht und die Little-Endian-Konvention verwendet.

FeldGröße
Literals_Block_Type2 bits
Size_Format1-2 bits
Regenerated_Size5-20 bits
[Compressed_Size]0-18 bits

Tabelle 12: Literals_Section_Header

In dieser Darstellung befinden sich die obersten Bits an der niedrigsten Position.

Das Literals_Block_Type-Feld verwendet die zwei niedrigsten Bits des ersten Bytes und beschreibt vier verschiedene Blocktypen:

Literals_Block_Type (Literal-Blocktyp)Value (Wert)
Raw_Literals_Block (Rohe Literale)0
RLE_Literals_Block (RLE-Literale)1
Compressed_Literals_Block (Komprimierte Literale)2
Treeless_Literals_Block (Baumlose Literale)3

Tabelle 13: Literals_Block_Type

Raw_Literals_Block (Rohe Literale) : Literale werden unkomprimiert gespeichert. Literals_Section_Content ist Regenerated_Size.

RLE_Literals_Block (RLE-Literale) : Literale bestehen aus einem einzelnen Bytewert, der Regenerated_Size-mal wiederholt wird. Literals_Section_Content ist 1.

Compressed_Literals_Block (Komprimierte Literale) : Dies ist ein Standard-Huffman-komprimierter Block, der mit einer Huffman-Baumbeschreibung beginnt. Details siehe unten. Literals_Section_Content ist Compressed_Size.

Treeless_Literals_Block (Baumlose Literale) : Dies ist ein Huffman-komprimierter Block, der den Huffman-Baum aus dem vorherigen Compressed_Literals_Block verwendet, oder wenn es keinen vorherigen Huffman-komprimierten Literal-Block gibt, aus dem Wörterbuch. Huffman_Tree_Description wird übersprungen. Beachten Sie, dass wenn dieser Modus ohne vorherige Huffman-Tabelle im Rahmen (oder Wörterbuch gemäß Abschnitt 5) ausgelöst wird, dies als Datenbeschädigung betrachtet werden sollte. Literals_Section_Content ist Compressed_Size.

Size_Format ist in zwei Familien unterteilt:

  • Für Raw_Literals_Block und RLE_Literals_Block muss nur Regenerated_Size dekodiert werden. Es gibt kein Compressed_Size-Feld.

  • Für Compressed_Block und Treeless_Literals_Block müssen sowohl Compressed_Size als auch Regenerated_Size (dekomprimierte Größe) dekodiert werden. Die Anzahl der Streams (1 oder 4) muss ebenfalls dekodiert werden.

Für Werte, die mehrere Bytes umfassen, ist die Konvention Little-Endian.

Size_Format für Raw_Literals_Block und RLE_Literals_Block verwendet 1 oder 2 Bits. Sein Wert ist (Literals_Section_Header[0]>>2) & 0x3.

  • Size_Format == 00 oder 10: Size_Format verwendet 1 Bit. Regenerated_Size verwendet 5 Bits (Wert 0-31). Literals_Section_Header verwendet 1 Byte. Regenerated_Size = Literal_Section_Header[0]>>3.

  • Size_Format == 01: Size_Format verwendet 2 Bits. Regenerated_Size verwendet 12 Bits (Wert 0-4095). Literals_Section_Header verwendet 2 Bytes. Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4).

  • Size_Format == 11: Size_Format verwendet 2 Bits. Regenerated_Size verwendet 20 Bits (Wert 0-1048575). Literals_Section_Header verwendet 3 Bytes. Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4) + (Literals_Section_Header[2]<<12).

Für diese Fälle existiert nur Stream_1. Beachten Sie, dass es erlaubt ist, ein langes Format zu verwenden, um einen kurzen Wert darzustellen (z.B. 13), auch wenn dies ineffizient ist.

Size_Format für Compressed_Literals_Block und Treeless_Literals_Block verwendet immer 2 Bits.

  • Size_Format == 00: Ein einzelner Stream. Sowohl Regenerated_Size als auch Compressed_Size verwenden 10 Bits (Wert 0-1023). Literals_Section_Header verwendet 3 Bytes.

  • Size_Format == 01: 4 Streams. Sowohl Regenerated_Size als auch Compressed_Size verwenden 10 Bits (Wert 0-1023). Literals_Section_Header verwendet 3 Bytes.

  • Size_Format == 10: 4 Streams. Sowohl Regenerated_Size als auch Compressed_Size verwenden 14 Bits (Wert 0-16383). Literals_Section_Header verwendet 4 Bytes.

  • Size_Format == 11: 4 Streams. Sowohl Regenerated_Size als auch Compressed_Size verwenden 18 Bits (Wert 0-262143). Literals_Section_Header verwendet 5 Bytes.

Sowohl Compressed_Size- als auch Regenerated_Size-Felder folgen der Little-Endian-Konvention. Beachten Sie, dass Compressed_Size, wenn vorhanden, die Größe der Huffman_Tree_Description einschließt.

3.1.1.3.1.2. Raw_Literals_Block (Rohe Literale)​

Die Daten in Stream_1 sind Regenerated_Size Bytes lang. Sie enthalten rohe Literaldaten, die während der Sequenzausführung (Abschnitt 3.1.1.3.2) verwendet werden.

3.1.1.3.1.3. RLE_Literals_Block (RLE-Literale)​

Stream_1 besteht aus einem einzelnen Byte, das Regenerated_Size-mal wiederholt werden sollte, um die dekodierten Literale zu erzeugen.

3.1.1.3.1.4. Compressed_Literals_Block and Treeless_Literals_Block (Komprimierte und baumlose Literale)​

Beide Modi enthalten Huffman-kodierte Daten. Für Treeless_Literals_Block stammt die Huffman-Tabelle aus dem vorherigen komprimierten Literal-Block oder dem Wörterbuch; siehe Abschnitt 5.

3.1.1.3.1.5. Huffman_Tree_Description (Huffman-Baumbeschreibung)​

Dieser Teil ist nur vorhanden, wenn der Literals_Block_Type-Typ Compressed_Literals_Block (2) ist. Das Format der Huffman_Tree_Description finden Sie in Abschnitt 4.2.1. Die Größe der Huffman_Tree_Description wird während der Dekodierung bestimmt. Sie muss verwendet werden, um zu bestimmen, wo die Streams beginnen.

Total_Streams_Size = Compressed_Size - Huffman_Tree_Description_Size

3.1.1.3.1.6. Jump_Table (Sprungtabelle)​

Die Jump_Table ist nur vorhanden, wenn es 4 Huffman-kodierte Streams gibt.

(Erinnerung: Huffman-komprimierte Daten bestehen aus 1 oder 4 Huffman-kodierten Streams.)

Wenn nur 1 Stream vorhanden ist, handelt es sich um einen einzelnen Bitstrom, der den verbleibenden gesamten Teil des Literal-Blocks einnimmt und wie in Abschnitt 4.2.2 beschrieben kodiert ist.

Wenn es 4 Streams gibt, bietet Literals_Section_Header nur genügend Informationen, um die dekomprimierte und komprimierte Größe aller 4 Streams kombiniert zu kennen. Die dekomprimierte Größe jedes Streams ist gleich (Regenerated_Size+3)/4, außer für den letzten Stream, der bis zu 3 Bytes kleiner sein kann, um die in Regenerated_Size angegebene Gesamtdekomprimierte Größe zu erreichen.

Letztes Update am