メインコンテンツまでスキップ

3.1.1.3. Compressed Blocks (圧縮ブロック)

圧縮ブロックを解凍するには、Block_Header 内の Block_Size フィールドから圧縮サイズを提供する必要があります。

圧縮ブロックは2つの部分で構成されます: Literals_Section (リテラルセクション、セクション 3.1.1.3.1) と Sequences_Section (シーケンスセクション、セクション 3.1.1.3.2)。これら2つの部分の結果は、シーケンス実行 (セクション 3.1.1.4) で解凍データを生成するために組み合わされます。

圧縮ブロックをデコードするには、次の要素が必要です:

  • 以前にデコードされたデータ、Window_Size の距離まで、またはフレームの開始まで、どちらか小さい方まで。後者の場合、Single_Segment_Flag が設定されます。

  • 「最近のオフセット」リスト、前の Compressed_Block から。

  • 前の Huffman ツリー、Treeless_Literals_Block タイプに必要。

  • 前の Finite State Entropy (FSE) デコーディングテーブル、Repeat_Mode に必要、各シンボルタイプ (リテラル長コード、マッチ長コード、オフセットコード) 用。

デコーディングテーブルが常に前の Compressed_Block から来るわけではないことに注意してください:

  • 各デコーディングテーブルは辞書から来る可能性があります。
  • Huffman ツリーは前の Compressed_Literals_Block から来ます。

3.1.1.3.1. Literals_Section_Header (リテラルセクションヘッダー)​

すべてのリテラルはブロックの最初の部分で再構成されます。それらは最初にデコードされ、シーケンス実行中にコピーされる (セクション 3.1.1.4 を参照) か、シーケンス実行中にオンザフライでデコードされる可能性があります。

リテラルは非圧縮で保存されるか、Huffman プレフィックスコードを使用して圧縮されます。圧縮される場合、オプションのツリー記述が存在し、その後に 1 つまたは 4 つのストリームが続く可能性があります。

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

表 11: 圧縮リテラル

3.1.1.3.1.1. Literals_Section_Header (リテラルセクションヘッダー)​

このフィールドは、リテラルがどのようにパックされているかを記述します。これは、1 から 5 バイトの範囲の可変サイズのバイト整列ビットフィールドで、リトルエンディアン規約を使用します。

フィールドサイズ
Literals_Block_Type2 ビット
Size_Format1-2 ビット
Regenerated_Size5-20 ビット
[Compressed_Size]0-18 ビット

表 12: Literals_Section_Header

この表現では、上位ビットが最下位に位置します。

Literals_Block_Type フィールドは最初のバイトの最下位 2 ビットを使用し、4 つの異なるブロックタイプを記述します:

Literals_Block_Type (リテラルブロックタイプ)Value (値)
Raw_Literals_Block (生リテラル)0
RLE_Literals_Block (RLEリテラル)1
Compressed_Literals_Block (圧縮リテラル)2
Treeless_Literals_Block (ツリーなしリテラル)3

表 13: Literals_Block_Type

Raw_Literals_Block (生リテラル) : リテラルは非圧縮で保存されます。Literals_Section_Content は Regenerated_Size です。

RLE_Literals_Block (RLEリテラル) : リテラルは Regenerated_Size 回繰り返される単一バイト値で構成されます。Literals_Section_Content は 1 です。

Compressed_Literals_Block (圧縮リテラル) : これは標準の Huffman 圧縮ブロックで、Huffman ツリー記述で始まります。詳細は以下を参照してください。Literals_Section_Content は Compressed_Size です。

Treeless_Literals_Block (ツリーなしリテラル) : これは、前の Compressed_Literals_Block からの Huffman ツリーを使用する Huffman 圧縮ブロックです。前の Huffman 圧縮リテラルブロックがない場合は、辞書から取得します。Huffman_Tree_Description はスキップされます。フレーム (またはセクション 5 による辞書) に前の Huffman テーブルがない状態でこのモードがトリガーされた場合、データ破損とみなされるべきであることに注意してください。Literals_Section_Content は Compressed_Size です。

Size_Format は 2 つのファミリーに分かれます:

  • Raw_Literals_Block と RLE_Literals_Block の場合、Regenerated_Size のみをデコードする必要があります。Compressed_Size フィールドはありません。

  • Compressed_Block と Treeless_Literals_Block の場合、Compressed_Size と Regenerated_Size (解凍サイズ) の両方をデコードする必要があります。ストリームの数 (1 または 4) もデコードする必要があります。

複数のバイトにまたがる値の場合、規約はリトルエンディアンです。

Raw_Literals_Block と RLE_Literals_Block の Size_Format は 1 または 2 ビットを使用します。その値は (Literals_Section_Header[0]>>2) & 0x3 です。

  • Size_Format == 00 または 10: Size_Format は 1 ビットを使用します。Regenerated_Size は 5 ビット (値 0-31) を使用します。Literals_Section_Header は 1 バイトを使用します。Regenerated_Size = Literal_Section_Header[0]>>3。

  • Size_Format == 01: Size_Format は 2 ビットを使用します。Regenerated_Size は 12 ビット (値 0-4095) を使用します。Literals_Section_Header は 2 バイトを使用します。Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4)。

  • Size_Format == 11: Size_Format は 2 ビットを使用します。Regenerated_Size は 20 ビット (値 0-1048575) を使用します。Literals_Section_Header は 3 バイトを使用します。Regenerated_Size = (Literals_Section_Header[0]>>4) + (Literals_Section_Header[1]<<4) + (Literals_Section_Header[2]<<12)。

これらの場合、Stream_1 のみが存在します。効率は悪いですが、短い値 (例: 13) を表すために長い形式を使用することは許可されていることに注意してください。

Compressed_Literals_Block と Treeless_Literals_Block の Size_Format は常に 2 ビットを使用します。

  • Size_Format == 00: 単一ストリーム。Regenerated_Size と Compressed_Size の両方が 10 ビット (値 0-1023) を使用します。Literals_Section_Header は 3 バイトを使用します。

  • Size_Format == 01: 4 ストリーム。Regenerated_Size と Compressed_Size の両方が 10 ビット (値 0-1023) を使用します。Literals_Section_Header は 3 バイトを使用します。

  • Size_Format == 10: 4 ストリーム。Regenerated_Size と Compressed_Size の両方が 14 ビット (値 0-16383) を使用します。Literals_Section_Header は 4 バイトを使用します。

  • Size_Format == 11: 4 ストリーム。Regenerated_Size と Compressed_Size の両方が 18 ビット (値 0-262143) を使用します。Literals_Section_Header は 5 バイトを使用します。

Compressed_Size と Regenerated_Size フィールドの両方がリトルエンディアン規約に従います。Compressed_Size は、存在する場合、Huffman_Tree_Description のサイズを含むことに注意してください。

3.1.1.3.1.2. Raw_Literals_Block (生リテラル)​

Stream_1 のデータは Regenerated_Size バイトの長さです。シーケンス実行 (セクション 3.1.1.3.2) 中に使用される生のリテラルデータが含まれています。

3.1.1.3.1.3. RLE_Literals_Block (RLEリテラル)​

Stream_1 は、デコードされたリテラルを生成するために Regenerated_Size 回繰り返す必要がある単一バイトで構成されます。

3.1.1.3.1.4. Compressed_Literals_Block and Treeless_Literals_Block (圧縮リテラルとツリーなしリテラル)​

両方のモードには Huffman エンコードデータが含まれています。Treeless_Literals_Block の場合、Huffman テーブルは前の圧縮リテラルブロックまたは辞書から来ます。セクション 5 を参照してください。

3.1.1.3.1.5. Huffman_Tree_Description (Huffman ツリー記述)​

この部分は、Literals_Block_Type タイプが Compressed_Literals_Block (2) の場合にのみ存在します。Huffman_Tree_Description の形式はセクション 4.2.1 にあります。Huffman_Tree_Description のサイズはデコード中に決定されます。ストリームがどこから始まるかを決定するために使用する必要があります。

Total_Streams_Size = Compressed_Size - Huffman_Tree_Description_Size

3.1.1.3.1.6. Jump_Table (ジャンプテーブル)​

Jump_Table は、4 つの Huffman エンコードストリームがある場合にのみ存在します。

(リマインダー: Huffman 圧縮データは 1 つまたは 4 つの Huffman エンコードストリームで構成されます。)

1 つのストリームのみが存在する場合、それはリテラルブロックの残りの全体部分を占める単一のビットストリームで、セクション 4.2.2 で説明されているようにエンコードされます。

4 つのストリームがある場合、Literals_Section_Header は、すべての 4 つのストリームを組み合わせた解凍サイズと圧縮サイズを知るのに十分な情報のみを提供します。各ストリームの解凍サイズは (Regenerated_Size+3)/4 に等しくなりますが、最後のストリームは最大 3 バイト小さくなり、Regenerated_Size で指定された合計解凍サイズに達する可能性があります。

に最終更新