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

3. Compression Algorithm (圧縮アルゴリズム)

本セクションでは、Zstandard アルゴリズムについて説明します。

本文書の目的は、a) CPU タイプ、オペレーティングシステム、ファイルシステム、文字セットに依存せず、b) Zstandard アルゴリズムを使用したファイル圧縮、パイプおよびストリーム圧縮 (Pipe and Streaming Compression) に適した、可逆圧縮データフォーマット (Lossless Compressed Data Format) を定義することです。本仕様のテキストは、読者がビットレベルおよびその他の原始データ表現に関する基本的なプログラミング知識を持っていることを前提としています。

データは、任意の長さの順次提示される入力データストリームに対して、事前に制限された中間ストレージ量 (A Priori Bounded Amount of Intermediate Storage) のみを使用して生成または消費できます。したがって、データ通信に使用できます。このフォーマットは、Zstandard 圧縮方法とオプションの xxHash-64 チェックサム方法 [XXHASH] を使用して、データ破損 (Data Corruption) を検出します。

本仕様で定義されるデータフォーマットは、圧縮データへのランダムアクセス (Random Access) を許可しようとはしません。

以下で特に指定されない限り、準拠する圧縮器 (Compliant Compressor) は、ここで指定される仕様に準拠するデータセットを生成する必要があります。ただし、すべてのオプションをサポートする必要はありません。

準拠する解凍器 (Compliant Decompressor) は、ここで指定される作業パラメータセットに準拠する少なくとも1つのセットを解凍できる必要があります。情報フィールド (Informative Fields)（チェックサムなど）を無視することもできます。圧縮ストリームで定義されたパラメータをサポートしない場合は常に、明確なエラーコード (Unambiguous Error Code) と、どのパラメータがサポートされていないかを説明する関連エラーメッセージを生成する必要があります。

本仕様は、ソフトウェア実装者がデータを Zstandard フォーマットに圧縮したり、Zstandard フォーマットからデータを解凍したりするために使用することを目的としています。Zstandard フォーマットは、[ZSTD] で入手可能な、ポータブルな C 言語で記述されたオープンソース参照実装によってサポートされています。

3.1 Frames (フレーム)​

Zstandard 圧縮データは、1つ以上のフレーム (Frames) で構成されます。各フレームは独立しており、他のフレームとは独立して解凍できます。複数の連結されたフレームの解凍内容は、各フレームの解凍内容の連結です。

Zstandard には2つのフレームフォーマットが定義されています: Zstandard フレームとスキップ可能フレーム (Skippable Frames)。Zstandard フレームには圧縮データが含まれ、スキップ可能フレームにはカスタムユーザーメタデータ (Custom User Metadata) が含まれます。

3.1.1 Zstandard Frames (Zstandard フレーム)​

単一の Zstandard フレームの構造は次のとおりです:

+--------------------+------------+
|| Magic_Number       | 4 bytes    |
+--------------------+------------+
|| Frame_Header       | 2-14 bytes |
+--------------------+------------+
|| Data_Block         | n bytes    |
+--------------------+------------+
|| [More Data_Blocks] |            |
+--------------------+------------+
|| [Content_Checksum] | 4 bytes    |
+--------------------+------------+

表 1: 単一の Zstandard フレームの構造

Magic_Number (マジックナンバー) : 4 バイト、リトルエンディアンフォーマット (Little-endian Format)。値: 0xFD2FB528。

Frame_Header (フレームヘッダー) : 2 から 14 バイト、詳細はセクション 3.1.1.1 を参照。

Data_Block (データブロック) : 詳細はセクション 3.1.1.2 を参照。これはデータが出現する場所です。

Content_Checksum (コンテンツチェックサム) : オプションの 32 ビットチェックサム、Content_Checksum_Flag が設定されている場合にのみ存在します。コンテンツチェックサムは、XXH64() ハッシュ関数 [XXHASH] の、元の (デコードされた) データを入力とし、シードをゼロとするダイジェストの結果です。チェックサムの下位 4 バイトがリトルエンディアンフォーマットで格納されます。

マジックナンバーの選択は、任意のファイルの先頭でそれを見つける確率を下げるように設計されています。これは、自明なパターン (0x00、0xFF、繰り返しバイト、インクリメントバイトなど) を回避し、ASCII 範囲外のバイト値を含み、UTF-8 空間にマップされないため、テキストファイルの先頭に出現する可能性が低くなります。

3.1.1.1 Frame Header (フレームヘッダー)​

フレームヘッダーのサイズは可変で、最小 2 バイト、最大 14 バイトで、オプションのパラメータによって異なります。Frame_Header の構造は次のとおりです:

+-------------------------+-----------+
|| Frame_Header_Descriptor | 1 byte    |
+-------------------------+-----------+
|| [Window_Descriptor]     | 0-1 byte  |
+-------------------------+-----------+
|| [Dictionary_ID]         | 0-4 bytes |
+-------------------------+-----------+
|| [Frame_Content_Size]    | 0-8 bytes |
+-------------------------+-----------+

表 2: Frame_Header の構造

(セクション 3.1.1.1 およびそのサブセクションの内容が長いため、ビットフィールドの詳細な説明、Window Descriptor、Dictionary_ID、Frame_Content_Size などの技術的詳細については、完全な RFC 8878 文書を参照してください)

注: セクション 3 には以下を含む多くの技術的詳細が含まれています:

  • 3.1.1.2 Blocks (ブロック構造)
  • 3.1.1.3 Compressed Blocks (圧縮ブロック、Literals と Sequences を含む)
  • 3.1.1.4 Sequence Execution (シーケンス実行)
  • 3.1.1.5 Repeat Offsets (リピートオフセット)
  • 3.1.2 Skippable Frames (スキップ可能フレーム)

完全な技術実装の詳細については、RFC 8878 原文を参照してください: https://www.rfc-editor.org/rfc/rfc8878.txt

に最終更新