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

RFC 8878 - Zstandard圧縮と'application/zstd'メディアタイプ

  • ステータス: Informational
  • 発行日: February 2021
  • ストリーム: IETF
  • 廃止: RFC8478
  • エラッタ: エラッタなし

概要 (Abstract)​

Zstandard、または "zstd" (発音: "ズィー・スタンダード") は、ロスレスデータ圧縮機構 (Lossless Data Compression Mechanism) です。本文書はこの機構を説明し、MIMEを介してzstd圧縮コンテンツを転送する際に使用するメディアタイプ (Media Type)、コンテンツエンコーディング (Content Encoding)、構造化構文サフィックス (Structured Syntax Suffix) を登録します。

名前に "standard" (標準) という単語が含まれていますが、読者は本文書がインターネット標準トラックの仕様ではないことに注意してください。情報提供のみを目的として公開されています。

本文書はRFC 8478を置き換え、廃止します。

目次 (Contents)​

コア章節​

標準化章節​

関連リソース​

  • 公式原文: RFC 8878
  • 公式ページ: RFC 8878 DataTracker
  • Zstandard公式サイト: http://www.zstd.net
  • GitHubリポジトリ: https://github.com/facebook/zstd

1. Introduction (序論)​

Zstandard, または "zstd" (発音: "ズィー・スタンダード") は、gzip [RFC1952] に類似したデータ圧縮機構 (Data Compression Mechanism) です。

名前に "standard" (標準) という単語が含まれていますが、本文書はインターネット標準トラックの仕様 (Internet Standards Track Specification) ではないことに注意してください。本文書は情報提供のみを目的として公開されています。

本文書は Zstandard フォーマットを説明します。また、Zstandard で圧縮されたデータオブジェクトの転送を可能にするため、本文書はメディアタイプ (Media Type)、コンテンツエンコーディング (Content Encoding)、および構造化構文サフィックス (Structured Syntax Suffix) を登録します。これらは、ペイロード (Payload) でそのようなコンテンツが使用される際に識別するために使用できます。

2. Definitions (定義)​

本文書の他の部分で使用される用語を明確にするため、ここで定義します。

uncompressed (未圧縮) : 圧縮される前の元の形式の任意のバイト集合を記述します。

compressed (圧縮済み) : このメカニズムを通じてバイト集合を処理した結果を記述します。元の入力はこうして圧縮されています。

decompressed (解凍済み) : このメカニズムの逆過程を通じてバイト集合を処理した結果を記述します。これが成功すると、解凍されたペイロード (Decompressed Payload) と未圧縮のペイロード (Uncompressed Payload) は区別できません。

encode (エンコード) : データをある形式から別の形式に変換するプロセス。これには圧縮が含まれる場合もあれば、本仕様の一部として行われる他の変換を指す場合もあります。

decode (デコード) : "encode" の逆。元のコンテンツを復元するために、以前のエンコーディングを逆転させるプロセスを記述します。

frame (フレーム) : Zstandard によって圧縮されたコンテンツは Zstandard フレームに変換されます。複数のフレームを単一のファイルまたはストリームに追加できます。フレームは完全に独立しており、明確な開始と終了を持ち、デコーダー (Decoder) にどのように解凍するかを伝えるパラメータのセットを持っています。

block (ブロック) : フレームは1つまたは複数のブロックをカプセル化します。各ブロックには任意のコンテンツが含まれ、そのヘッダー (Header) によって記述され、フレームパラメータに依存する保証された最大コンテンツサイズを持っています。フレームとは異なり、各ブロックは適切なデコードのために前のブロックに依存します。ただし、各ブロックは後続ブロックを待たずに解凍できるため、ストリーミング操作 (Streaming Operations) が可能です。

natural order (自然順序) : そのタイプのオブジェクトまたは値に典型的なオブジェクトまたは値のシーケンスまたは順序。たとえば、一意の整数のセットは、セットまたはシーケンス内のある要素から次の要素に進むときに値が減少しない場合、「自然順序」にあります。

仕様内の識別子の命名規則は Mixed_Case_With_Underscores (アンダースコア付き混合ケース) です。角括弧内の識別子は、提示されたコンテキストでその識別子がオプションであることを示します。

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

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.1. Frame_Header_Descriptor (フレームヘッダー記述子)​

ヘッダーの最初のバイトは Frame_Header_Descriptor と呼ばれます。これは、他のどのフィールドが存在するかを記述します。このバイトをデコードするだけで、Frame_Header のサイズを決定できます。

ビット番号 (Bit Number)フィールド名 (Field Name)
7-6Frame_Content_Size_Flag
5Single_Segment_Flag
4(未使用, unused)
3(予約済み, reserved)
2Content_Checksum_Flag
1-0Dictionary_ID_Flag

表 3: Frame_Header_Descriptor

表 3 では、ビット 7 が最上位ビットで、ビット 0 が最下位ビットです。

3.1.1.1.1.1. Frame_Content_Size_Flag (フレームコンテンツサイズフラグ)​

これは 2 ビットフラグ (Frame_Header_Descriptor を 6 ビット右シフトしたものに相当) で、Frame_Content_Size (解凍データサイズ) がヘッダー内に提供されるかどうかを指定します。Frame_Content_Size_Flag は、表 4 に従って Frame_Content_Size が使用するバイト数である FCS_Field_Size を提供します:

Frame_Content_Size_Flag0123
FCS_Field_Size0 または 1248

表 4: Frame_Content_Size_Flag が FCS_Field_Size を提供

Frame_Content_Size_Flag が 0 の場合、FCS_Field_Size は Single_Segment_Flag に依存します: Single_Segment_Flag が設定されている場合、FCS_Field_Size は 1 です。それ以外の場合、FCS_Field_Size は 0 で、Frame_Content_Size は提供されません。

3.1.1.1.1.2. Single_Segment_Flag (単一セグメントフラグ)​

このフラグが設定されている場合、データは単一の連続したメモリセグメント内で再生成される必要があります。

この場合、Window_Descriptor バイトはスキップされますが、Frame_Content_Size は存在する必要があります。したがって、デコーダは Frame_Content_Size 以上のサイズのメモリセグメントを割り当てる必要があります。

デコーダを不合理なメモリ要求から保護するために、デコーダは、デコーダの承認範囲内のメモリサイズを超える要求をする圧縮フレームを拒否することが許可されています。

より広い互換性のために、デコーダは少なくとも 8 MB のメモリサイズをサポートすることが推奨されます。これは推奨事項にすぎません。各デコーダは、ローカルの制限に基づいて、より高いまたはより低い制限を自由にサポートできます。

3.1.1.1.1.3. Unused Bit (未使用ビット)​

本仕様のバージョンに準拠するデコーダは、このビットを解釈してはなりません。これは、将来のバージョンで、フレームを正しくデコードするために必須ではない属性を表すために使用される可能性があります。本仕様に準拠するエンコーダは、このビットをゼロに設定する必要があります。

3.1.1.1.1.4. Reserved Bit (予約済みビット)​

このビットは、将来の機能のために予約されています。その値はゼロである必要があります。本仕様のバージョンに準拠するデコーダは、これが設定されていないことを確認する必要があります。このビットは、将来のリビジョンで、フレームを正しくデコードするために解釈する必要がある機能を表すために使用される可能性があります。

3.1.1.1.1.5. Content_Checksum_Flag (コンテンツチェックサムフラグ)​

このフラグが設定されている場合、フレームの最後に 32 ビットの Content_Checksum が存在します。上記の Content_Checksum の説明を参照してください。

3.1.1.1.1.6. Dictionary_ID_Flag (辞書IDフラグ)​

これは 2 ビットフラグ (= Frame_Header_Descriptor & 0x3) で、辞書 ID がヘッダー内に提供されるかどうかを示します。また、このフィールドのサイズを DID_Field_Size として指定します:

Dictionary_ID_Flag0123
DID_Field_Size0124

表 5: Dictionary_ID_Flag

3.1.1.1.2. Window Descriptor (ウィンドウ記述子)​

これは、フレームを解凍するために必要な最小メモリバッファに関する保証を提供します。この情報は、デコーダが十分なメモリを割り当てるために重要です。

Window_Descriptor バイトはオプションです。Single_Segment_Flag が設定されている場合、Window_Descriptor は存在しません。この場合、Window_Size は Frame_Content_Size であり、その値は 0 から 2^64 - 1 バイト (16 ExaBytes) までです。

ビット番号 (Bit Number)7-32-0
フィールド名 (Field Name)Exponent (指数)Mantissa (仮数)

表 6: Window_Descriptor

最小メモリバッファサイズは Window_Size と呼ばれます。これは次の式で記述されます:

windowLog = 10 + Exponent;
windowBase = 1 << windowLog;
windowAdd = (windowBase / 8) * Mantissa;
Window_Size = windowBase + windowAdd;

最小 Window_Size は 1 KB です。最大 Window_Size は (1<<41) + 7*(1<<38) バイト、つまり 3.75 TB です。

一般に、より大きな Window_Size 値は、メモリ使用量の増加を犠牲にして、圧縮率を向上させる傾向があります。

圧縮データを正しくデコードするには、デコーダは少なくとも Window_Size バイトのバッファを割り当てる必要があります。

デコーダを不合理なメモリ要求から保護するために、デコーダは、デコーダの承認範囲内のメモリサイズを超える要求をする圧縮フレームを拒否することが許可されています。

相互運用性を向上させるために、デコーダは最大 8 MB の Window_Size 値をサポートし、エンコーダは 8 MB を超える Window_Size を必要とするフレームを生成しないことが推奨されます。これは推奨事項にすぎず、デコーダはローカルの制限に基づいて、より高いまたはより低い制限を自由にサポートできます。

3.1.1.1.3. Dictionary_ID (辞書ID)​

これは、フレームを正しくデコードするために必要な辞書 ID を含む可変サイズのフィールドです。このフィールドはオプションです。存在しない場合、使用する辞書を決定するのはデコーダ次第です。

Dictionary_ID フィールドのサイズは DID_Field_Size によって提供されます。DID_Field_Size は Dictionary_ID_Flag の値から直接派生します。1 バイトで ID 0-255 を表現でき、2 バイトで ID 0-65535 を表現でき、4 バイトで ID 0-4294967295 を表現できます。フォーマットはリトルエンディアンです。

大きな 4 バイト辞書 ID を使用して小さな ID (たとえば 13) を表現することは、効率が悪くても許可されています。

プライベート環境では、任意の辞書 ID を使用できます。ただし、公共空間で配布されるフレームと辞書の場合、Dictionary_ID は慎重に割り当てる必要があります。次の範囲は、IANA に登録された辞書専用に予約されています (セクション 7.4 を参照):

  • 低範囲 (low range): <= 32767
  • 高範囲 (high range): >= (1 << 31)

Dictionary_ID の他の値は、参加者間の私的な取り決めによって使用できます。

登録されていない予約済み辞書 ID を参照する解凍用に送信された有効なペイロードは、エラーになります。

3.1.1.1.4. Frame_Content_Size (フレームコンテンツサイズ)​

これは元の (圧縮されていない) サイズです。この情報はオプションです。Frame_Content_Size は可変バイト数を使用し、FCS_Field_Size によって提供されます。FCS_Field_Size は Frame_Content_Size_Flag の値によって提供されます。FCS_Field_Size は 0 (存在しない)、1、2、4、または 8 バイトに等しくなります。

FCS Field Size (フィールドサイズ)Range (範囲)
0unknown (不明)
10 - 255
2256 - 65791
40 - 2^32 - 1
80 - 2^64 - 1

表 7: Frame_Content_Size

Frame_Content_Size フォーマットはリトルエンディアンです。FCS_Field_Size が 1、4、または 8 バイトの場合、値は直接読み取られます。FCS_Field_Size が 2 の場合、256 のオフセットが追加されます。小さいサイズ (たとえば 18) を表現するために互換性のある任意のバリアントを使用することは、効率が悪くても許可されています。

3.1.1.2. Blocks (ブロック)​

Magic_Number と Frame_Header の後に、いくつかのブロックがあります。各フレームには少なくとも 1 つのブロックが必要ですが、フレームあたりのブロック数に上限はありません。

ブロックの構造は次のとおりです:

+==============+===============+
|| Block_Header | Block_Content |
+==============+===============+
||   3 bytes    |    n bytes    |
+--------------+---------------+

表 8: ブロックの構造

Block_Header は 3 バイトを使用し、リトルエンディアン規約で記述されます。3 つのフィールドが含まれます:

Last_BlockBlock_TypeBlock_Size
bit 0bits 1-2bits 3-23

表 9: Block_Header

3.1.1.2.1. Last_Block (最後のブロック)​

最下位ビット (Last_Block) は、これが最後のブロックかどうかを示します。フレームはこの最後のブロックの後に終了します。オプションの Content_Checksum が続く場合があります (セクション 3.1.1 を参照)。

3.1.1.2.2. Block_Type (ブロックタイプ)​

次の 2 ビットは Block_Type を表します。4 つのブロックタイプがあります:

Value (値)Block_Type (ブロックタイプ)
0Raw_Block (生ブロック)
1RLE_Block (RLEブロック)
2Compressed_Block (圧縮ブロック)
3Reserved (予約済み)

表 10: 4 つのブロックタイプ

Raw_Block (生ブロック) : これは圧縮されていないブロックです。Block_Content には Block_Size バイトが含まれます。

RLE_Block (RLEブロック) : これは Block_Size 回繰り返される単一バイトです。Block_Content は単一バイトで構成されます。解凍側では、このバイトを Block_Size 回繰り返す必要があります。

Compressed_Block (圧縮ブロック) : これはセクション 3.1.1.3 で説明されている圧縮ブロックです。Block_Size は Block_Content の長さ、つまり圧縮データです。解凍サイズは不明ですが、その最大可能値は保証されています (以下を参照)。

Reserved (予約済み) : これはブロックではありません。この値は現在の仕様では使用できません。そのような値が存在する場合、破損したデータとみなされ、仕様に準拠するデコーダはそれを拒否する必要があります。

3.1.1.2.3. Block_Size (ブロックサイズ)​

Block_Header の上位 21 ビットは Block_Size を表します。

Block_Type が Compressed_Block または Raw_Block の場合、Block_Size は Block_Content のサイズです (したがって Block_Header は含まれません)。

Block_Type が RLE_Block の場合、Block_Content のサイズは常に 1 であるため、Block_Size はこのバイトを繰り返す必要がある回数を表します。

Block_Size は Block_Maximum_Size によって制限されます (以下を参照)。

3.1.1.2.4. Block_Content and Block_Maximum_Size (ブロックコンテンツとブロック最大サイズ)​

Block_Content のサイズは Block_Maximum_Size によって制限されます。これは次の 2 つのうち小さい方です:

  • Window_Size
  • 128 KB

Block_Maximum_Size は特定のフレームに対して一定です。この最大値は、フレーム内の任意のブロックの解凍サイズと圧縮サイズの両方に適用されます。

この制限の理論的根拠は、デコーダがフレームの開始時にこの情報を読み取り、それを使用してバッファを割り当てることができることです。ブロックサイズの保証により、バッファが有効なフレームの後続のブロックに対して十分であることが保証されます。

圧縮ブロックが圧縮されていないブロックよりも大きい場合は、代わりに圧縮されていないブロック (つまり Raw_Block) を送信することをお勧めします。

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 で指定された合計解凍サイズに達する可能性があります。

3.1.1.3.2. Sequences_Section (シーケンスセクション)​

圧縮ブロックはシーケンスの連続体です。シーケンスはリテラルコピーコマンドに続いてマッチコピーコマンドです。リテラルコピーコマンドは長さを指定します。これは Literals_Section からコピー (または抽出) するバイト数です。マッチコピーコマンドはオフセットと長さを指定します。

すべてのシーケンスがデコードされ、Literals_Section にまだリテラルが残っている場合、これらのバイトはブロックの最後に追加されます。

これはセクション 3.1.1.4 でより詳細に説明されています。

Sequences_Section は、コマンドをデコードするために必要なすべてのシンボルをまとめます。3 つのシンボルタイプがあります: リテラル長コード、オフセットコード、マッチ長コード。これらは単一の「ビットストリーム」でインターリーブエンコードされます。

Sequences_Section はヘッダーで始まり、各シンボルタイプのオプションの確率テーブルが続き、その後にビットストリームが続きます。

Sequences_Section_Header
  [Literals_Length_Table]
  [Offset_Table]
  [Match_Length_Table]
  bitStream

Sequences_Section をデコードするには、そのサイズが知られている必要があります。このサイズは Literals_Section のサイズから導出されます:

Sequences_Section_Size = Block_Size - Literals_Section_Header 
                         - Literals_Section_Content

3.1.1.3.2.1. Sequences_Section_Header (シーケンスセクションヘッダー)​

このヘッダーは2つの要素で構成されます:

  • Number_of_Sequences (シーケンス数)
  • Symbol_Compression_Modes (シンボル圧縮モード)

Number_of_Sequences​

Number_of_Sequences は 1 から 3 バイトを使用する可変サイズフィールドです。最初のバイトが "byte0" の場合:

  • if (byte0 == 0): シーケンスなし。シーケンス部分はここで停止します。解凍コンテンツは Literals_Section コンテンツとして完全に定義されます。Repeat_Mode で使用される FSE テーブルは更新されません。

  • if (byte0 < 128): Number_of_Sequences = byte0。1 バイトを使用します。

  • if (byte0 < 255): Number_of_Sequences = ((byte0 - 128) << 8) + byte1。2 バイトを使用します。

  • if (byte0 == 255): Number_of_Sequences = byte1 + (byte2 << 8) + 0x7F00。3 バイトを使用します。

Symbol_Compression_Modes​

Symbol_Compression_Modes は、各シンボルタイプの圧縮モードを定義する単一バイトです。

ビット番号 (Bit Number)フィールド名 (Field Name)
7-6Literal_Lengths_Mode
5-4Offsets_Mode
3-2Match_Lengths_Mode
1-0Reserved (予約済み)

表 14: Symbol_Compression_Modes

最後のフィールド Reserved はすべてゼロである必要があります。

Literals_Lengths_Mode、Offsets_Mode、Match_Lengths_Mode は、それぞれリテラル長コード、オフセットコード、マッチ長コードの Compression_Mode を定義します。これらは同じ列挙に従います:

Value (値)Compression_Mode (圧縮モード)
0Predefined_Mode (事前定義モード)
1RLE_Mode (RLEモード)
2FSE_Compressed_Mode (FSE圧縮モード)
3Repeat_Mode (リピートモード)

表 15: Literals_Lengths_Mode, Offsets_Mode, and Match_Lengths_Mode

Predefined_Mode (事前定義モード) : セクション 3.1.1.3.2.2 で定義されているように、事前定義された FSE (セクション 4.1 を参照) 分布テーブルを使用します。分布テーブルは存在しません。

RLE_Mode (RLEモード) : テーブル記述は、シンボルの値を含む 1 バイトで構成されます。このシンボルはすべてのシーケンスに使用されます。

FSE_Compressed_Mode (FSE圧縮モード) : 標準 FSE 圧縮。分布テーブルが存在します。この分布テーブルの形式はセクション 4.1.1 で説明されています。リテラル長コードとマッチ長コードテーブルの最大許容精度は 9 で、オフセットコードテーブルの最大精度は 8 であることに注意してください。シンボルが 1 つだけ存在する場合、このモードは使用してはならず、代わりに RLE_Mode を使用する必要があります (他のモードも機能しますが)。

Repeat_Mode (リピートモード) : Number_Of_Sequences > 0 の前の Compressed_Block で使用されたテーブルが再利用されます。これが最初のブロックの場合は、辞書からのテーブルが使用されます。これには RLE_Mode が含まれることに注意してください。したがって、Repeat_Mode が RLE_Mode に続く場合、同じシンボルが繰り返されます。また、Predefined_Mode も含まれます。この場合、Repeat_Mode は Predefined_Mode と同じ結果になります。分布テーブルは存在しません。フレーム (またはセクション 5 による辞書) に繰り返すべき前のシーケンステーブルがない状態でこのモードが使用された場合、これは破損とみなされるべきです。

3.1.1.3.2.1.1. Sequence Codes for Lengths and Offsets (長さとオフセットのシーケンスコード)​

各シンボルは独自のコンテキスト内のコードで、Baseline (ベースライン) と追加する Number_of_Bits (ビット数) を指定します。コードは FSE 圧縮され、元の追加ビットと同じビットストリームでインターリーブされます。

Literals Length Codes (リテラル長コード)​

リテラル長コードは 0 から 35 (含む) の値です。これらは 0 から 131071 バイトの長さを定義します。リテラル長は、デコードされた Baseline にビットストリームから Number_of_Bits ビットを読み取った結果 (リトルエンディアン値として) を加えたものに等しくなります。

Literals_Length_CodeBaselineNumber_of_Bits
0-15length0
16161
17181
18201
19221
20242
21282
22323
23403
24484
25646
261287
272568
285129
29102410
30204811
31409612
32819213
331638414
343276815
356553616

表 16: リテラル長コード

Match Length Codes (マッチ長コード)​

マッチ長コードは 0 から 52 (含む) の値です。これらは 3 から 131074 バイトの長さを定義します。マッチ長は、デコードされた Baseline にビットストリームから Number_of_Bits ビットを読み取った結果 (リトルエンディアン値として) を加えたものに等しくなります。

Match_Length_CodeBaselineNumber_of_Bits
0-31Match_Length_Code + 30
32351
33371
34391
35411
36432
37472
38513
39593
40674
41834
42995
431317
442598
455159
46102710
47205111
48409912
49819513
501638714
513277115
526553916

表 17: マッチ長コード

Offset Codes (オフセットコード)​

オフセットコードは 0 から N の値です。

デコーダーは、サポートする最大 N を自由に制限できます。少なくとも 22 の値をサポートすることが推奨されます。執筆時点で、リファレンスデコーダーがサポートする最大 N 値は 31 です。

オフセットコードは、リトルエンディアンで読み取られる追加ビットの数でもあり、次の式で Offset_Value に変換できます:

Offset_Value = (1 << offsetCode) + readNBits(offsetCode);
if (Offset_Value > 3) Offset = Offset_Value - 3;

これは、最大 Offset_Value が (2^(N+1)) - 1 であり、最大 (2^(N+1)) - 4 の後方参照距離をサポートすることを意味しますが、最大後方参照距離によって制限されます (セクション 3.1.1.1.2 を参照)。

1 から 3 の Offset_Values は特別です: これらは「リピートコード」を定義します。これはセクション 3.1.1.5 でより詳細に説明されています。

3.1.1.3.2.2. Default Distributions (デフォルト分布)​

シンボルタイプに対して Predefined_Mode が選択された場合、その FSE デコーディングテーブルは、ここで定義されている事前定義分布テーブルから生成されます。この分布をデコーディングテーブルに変換する方法の詳細については、セクション 4.1 を参照してください。

3.1.1.3.2.2.1. Literals Length Codes (リテラル長コード)​

デコーディングテーブルは 6 ビットの精度ログ (64 状態) を使用します。

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 (マッチ長コード)​

デコーディングテーブルは 6 ビットの精度ログ (64 状態) を使用します。

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 (オフセットコード)​

デコーディングテーブルは 5 ビットの精度ログ (32 状態) を使用し、最大 N 値 28 をサポートし、最大 536,870,908 のオフセット値を許可します。

圧縮ブロック内のシーケンスがこれより大きいオフセットを必要とする場合、デフォルト分布では表現できません。

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
  };

3.1.1.4. Sequence Execution (シーケンス実行)​

リテラルとシーケンスの両方がデコードされると、それらが組み合わされてブロックのデコードされたコンテンツが生成されます。

各シーケンスは、Sequences_Section (セクション 3.1.1.3.2) で説明されているようにデコードされたタプル (literals_length, offset_value, match_length) で構成されます。シーケンスを実行するには、まずデコードされたリテラルから literals_length バイトを出力にコピーします。

次に、以前にデコードされたデータから match_length バイトをコピーします。コピー元のオフセットは offset_value によって決定されます:

  • if Offset_Value > 3: オフセットは Offset_Value - 3 です;

  • if Offset_Value is from 1-3: オフセットは特別なリピートオフセット値です。この場合のオフセットの決定方法については、セクション 3.1.1.5 を参照してください。

オフセットは現在の位置 (リテラルをコピーした後) から定義されるため、オフセットが 6 でマッチ長が 3 の場合、6 バイト前から 3 バイトをコピーする必要があります。以前にデコードされたデータにつながるすべてのオフセットは、Frame_Header_Descriptor (セクション 3.1.1.1.1) で定義された Window_Size 未満である必要があることに注意してください。

実行フロー例​

例 1: 基本的なシーケンス実行​

シーケンスが (literals_length=5, offset_value=10, match_length=4) であるとします:

  1. リテラルをコピー: リテラルセクションから 5 バイトを出力にコピー
  2. オフセットを計算: Offset_Value=10 > 3、したがって Offset = 10 - 3 = 7
  3. マッチをコピー: 出力位置から 7 バイト前から 4 バイトをコピー

例 2: リピートオフセットの使用​

シーケンスが (literals_length=3, offset_value=1, match_length=8) であるとします:

  1. リテラルをコピー: リテラルセクションから 3 バイトを出力にコピー
  2. リピートオフセットを使用: offset_value=1 は Repeated_Offset1 を使用することを意味します
  3. マッチをコピー: Repeated_Offset1 位置から 8 バイトをコピー

重要な制約​

  1. Window_Size 制限: すべてのオフセットは < Window_Size でなければなりません
  2. データ整合性: オフセットがデコードされたデータの範囲を超えないようにする必要があります
  3. リテラル消費: すべてのシーケンスが実行された後、残りのリテラルは出力の最後に追加されます

3.1.1.5. Repeat Offsets (リピートオフセット)​

上記のように、最初の3つの値はリピートオフセットを定義します。これらを Repeated_Offset1、Repeated_Offset2、Repeated_Offset3 と呼びます。これらは新しさの順に並べられており、Repeated_Offset1 は「最も新しいもの」を表します。

offset_value が 1 の場合、使用されるオフセットは Repeated_Offset1 であり、以下同様です。

例外が1つあります: 現在のシーケンスの literals_length が 0 の場合、リピートオフセットは 1 ずれるため:

  • offset_value が 1 の場合 Repeated_Offset2 を意味します
  • offset_value が 2 の場合 Repeated_Offset3 を意味します
  • offset_value が 3 の場合 Repeated_Offset1 - 1_byte を意味します

初期化​

最初のブロックの場合、開始オフセット履歴は次の値で埋められます:

  • Repeated_Offset1 = 1
  • Repeated_Offset2 = 4
  • Repeated_Offset3 = 8

辞書が使用される場合を除き、その場合は辞書から取得されます。

その後、各ブロックは最新の Compressed_Block の終了値から開始オフセット履歴を取得します。Compressed_Block でないブロックはスキップされることに注意してください。それらはオフセット履歴に影響しません。

更新ルール​

Compressed_Block のシーケンスを実行中、Repeated_Offsets の値は常に最近使用された3つのオフセットを表すように最新の状態に保たれます。これを実現するために、各シーケンスの実行後に次のように更新されます:

ケース 1: 非リピートオフセット​

シーケンスの offset_value が Repeated_Offsets のいずれかを参照しない場合 (3 より大きい値を持つ場合、またはシーケンスの literals_length がゼロで値 3 を持つ場合):

  • Repeated_Offsets の値は 1 つ後方にシフトされます
  • Repeated_Offset1 は、使用されたばかりのオフセットの値を取ります

更新式:

Repeated_Offset3 = Repeated_Offset2
Repeated_Offset2 = Repeated_Offset1
Repeated_Offset1 = 新しいオフセット

ケース 2: リピートオフセット​

シーケンスの offset_value が Repeated_Offsets のいずれかを参照する場合 (値 1 または 2 を持つ場合、またはシーケンスの literals_length が非ゼロで値 3 を持つ場合):

  • Repeated_Offsets が再配置されます
  • Repeated_Offset1 は使用された Repeated_Offset の値を取ります
  • 既存の値は、最初の Repeated_Offset から offset_value で選択された Repeated_Offset まで押し戻されます

これにより、これらのオフセット値の 1 ステップのラップアラウンド回転が効果的に実行され、その順序が再び使用の新しさを反映します。

更新例テーブル​

次のテーブルは、Repeated_Offsets に一連のシーケンスを適用するときの値を示しています:

offset_valueliterals_lengthRepeated_Offset1Repeated_Offset2Repeated_Offset3Comment (コメント)
--148開始値
111411111114非リピート
122111114リピート1; 変更なし
222522222211111非リピート
1114111111122221111非リピート
333633333311112222非リピート
222111133332222リピート2; 1と2を交換
333222211113333リピート3; 3を1に回転
10222122221111解析されたオフセットを挿入
10222222213333リピート2

表 18: Repeated_Offsets

特殊ケース処理​

literals_length = 0 の場合​

literals_length = 0 の場合、offset_value の解釈がシフトします:

offset_value実際に使用されるオフセット
1Repeated_Offset2
2Repeated_Offset3
3Repeated_Offset1 - 1

この特別な処理は、連続したマッチコピー操作を最適化するためです。

重要なポイント​

  1. 新しさの原則: Repeated_Offset1 は常に最近使用されたオフセットです
  2. 自動更新: オフセット履歴は各シーケンス実行後に自動的に更新されます
  3. 辞書サポート: 初期値は辞書から取得できます
  4. 特別なシフト: literals_length=0 の場合、オフセット解釈がシフトします

3.1.2. Skippable Frames (スキップ可能フレーム)​

+==============+============+===========+
|| Magic_Number | Frame_Size | User_Data |
+==============+============+===========+
||   4 bytes    |  4 bytes   |  n bytes  |
+--------------+------------+-----------+

表 19: スキップ可能フレーム

スキップ可能フレームを使用すると、ユーザー定義のメタデータを連結されたフレームのストリームに挿入できます。

この仕様で定義されているスキップ可能フレームは、[LZ4] のスキップ可能フレームと互換性があります。

互換性のあるデコーダーの観点から、スキップ可能フレームは単にスキップされ、その内容は無視され、スキップ可能フレームの後でデコードが再開されます。

スキップ可能フレームは、連結されたフレームストリームに透かしを追加したり、あらゆる種類のトラッキング情報 (単なる汎用一意識別子 (UUID) であっても) を埋め込むために使用できることに注意する必要があります。このような可能性に警戒しているユーザーは、連結されたフレームストリームをスキャンして、分析または削除のためにそのようなフレームを検出しようとする必要があります。

フィールドの説明​

Magic_Number (マジックナンバー)​

サイズ: 4 バイト、リトルエンディアン形式
値: 0x184D2A5?、つまり 0x184D2A50 から 0x184D2A5F までのいずれかの値

16 個の値すべてが有効にスキップ可能フレームを識別します。この仕様は、スキップ可能フレームの特定のマーキング方法を詳述していません。

マジックナンバー範囲:

  • 最小値: 0x184D2A50
  • 最大値: 0x184D2A5F
  • 合計: 16 個の有効なマジックナンバー

Frame_Size (フレームサイズ)​

サイズ: 4 バイト、リトルエンディアン形式、符号なし 32 ビット
意味: 後続の User_Data のサイズ (バイト単位) (マジックナンバーとサイズフィールド自体を含まない)

これは、User_Data が (2^32 - 1) バイトより大きくできないことを意味します。

最大 User_Data サイズ: 4,294,967,295 バイト (約 4 GB)

User_Data (ユーザーデータ)​

サイズ: 可変 (Frame_Size によって指定)
コンテンツ: 任意のデータ

このフィールドは何でもかまいません。データはデコーダーによってスキップされます。

使用シナリオ​

1. メタデータの埋め込み​

  • バージョン情報
  • 作成タイムスタンプ
  • 作成者情報
  • ライセンスデータ

2. 透かしとトラッキング​

  • UUID 埋め込み
  • ソーストラッキング
  • 配布チャネル識別

3. アプリケーション固有データ​

  • カスタムヘッダー
  • アプリケーション構成
  • 拡張情報

互換性に関する注意​

デコーダーの動作​

仕様に準拠したデコーダーは次のことを行う必要があります:

  1. マジックナンバーを認識: 0x184D2A5? 範囲内のマジックナンバーを検出
  2. サイズを読み取る: Frame_Size フィールドを解析
  3. データをスキップ: Frame_Size バイトの User_Data をスキップ
  4. デコードを続行: スキップ可能フレームの後で処理を続行

エンコーダーの推奨事項​

エンコーダーは次のことができます:

  1. 任意の配置: フレームストリーム内の任意の位置にスキップ可能フレームを挿入
  2. 複数のフレーム: 複数のスキップ可能フレームを挿入
  3. カスタムマーキング: 内部マーキングに 16 個のマジックナンバーのいずれかを使用

セキュリティに関する考慮事項​

プライバシーの問題​

スキップ可能フレームは次のために使用される可能性があります:

  • データフローのトラッキング
  • 隠し情報の埋め込み
  • データソースの識別

推奨措置​

プライバシーを懸念するユーザー向け:

  1. スキャン検出: 入力ストリームをスキャンしてスキップ可能フレームを検出
  2. コンテンツ分析: User_Data のコンテンツを調査
  3. 選択的削除: 必要に応じてスキップ可能フレームを削除
  4. ログ記録: 監査のために検出されたスキップ可能フレームを記録

例​

UUID の埋め込み​

Magic_Number: 0x184D2A50
Frame_Size: 16 (0x10000000, リトルエンディアン)
User_Data: [16 バイト UUID]

タイムスタンプの埋め込み​

Magic_Number: 0x184D2A51
Frame_Size: 8
User_Data: [8 バイト Unix タイムスタンプ]

LZ4 との互換性​

スキップ可能フレーム形式は LZ4 と互換性があり、次のことが可能です:

  • フォーマット間のツール相互運用性
  • 統一されたメタデータ処理
  • 簡素化されたデコーダー実装

注意: スキップ可能フレームは解凍データのコンテンツに影響せず、ストリームのメタデータにのみ影響します。

4. Entropy Encoding (エントロピー符号化)​

Zstandard フォーマットは2種類のエントロピー符号化を使用します: FSE と Huffman 符号化です。Huffman はリテラル (Literals) の圧縮に使用され、FSE は他のすべてのシンボル (Literals_Length_Code、Match_Length_Code、およびオフセットコード) と Huffman ヘッダーの圧縮に使用されます。

4.1 FSE (有限状態エントロピー)​

FSE は Finite State Entropy (有限状態エントロピー) の略で、[ANS] に基づくエントロピーコーデックです。FSE エンコーディング/デコーディングはシンボル間で引き継がれる状態 (State) を伴うため、デコーディングはエンコーディングと逆の方向で行う必要があります。したがって、すべての FSE ビットストリーム (Bitstreams) は終端から先頭に向かって読み取られます。ストリーム内のビットの順序は逆転しないことに注意してください。ビットは単に書き込まれた順序とは逆の順序で読み取られます。

FSE の詳細については、"FiniteStateEntropy" [FSE] を参照してください。

FSE デコーディングには、2の累乗サイズを持ち、3つの要素を含むデコーディングテーブル (Decoding Table) が含まれます: Symbol (シンボル)、Num_Bits (ビット数)、Baseline (ベースライン)。テーブルサイズの2を底とする対数は Accuracy_Log (精度ログ) です。FSE 状態値はこのテーブル内のインデックスを表します。

初期状態値を取得するには、ストリームから Accuracy_Log ビットをリトルエンディアン値として消費します。ストリーム内の次のシンボルは、その状態のテーブルで示される Symbol です。次の状態値を取得するには、デコーダーはストリームから Num_Bits ビットをリトルエンディアン値として消費し、Baseline に追加する必要があります。

4.1.1 FSE Table Description (FSE テーブル記述)​

FSE ストリームをデコードするには、デコーディングテーブルを構築する必要があります。Zstandard フォーマットは、ここで説明されているように FSE テーブル記述をエンコードします。

FSE 分布テーブル (Distribution Table) は、0から最後に存在するシンボル (含む) までのすべてのシンボルの確率を正規化スケール (1 &lt;&lt; Accuracy_Log) で記述します。非ゼロ確率を持つシンボルが2つ以上必要であることに注意してください。

ビットストリームはリトルエンディアン方式で順方向に読み取られます。正確なサイズを知る必要はありません。サイズはデコーディングプロセスによって発見され、報告されます。ビットストリームは最初に動作するスケールを報告します。low4bits が最初のバイトの最下位4ビットを指定する場合、Accuracy_Log = low4bits + 5 です。

これに続いて、0から最後に存在するシンボルまでの各シンボル値が続きます。各フィールドで使用されるビット数は可変であり、次に依存します:

残りの確率 + 1 : たとえば、Accuracy_Log が8で、すでに100の確率ポイントが配分されていると仮定すると、デコーダーは0から (256 - 100 + 1) == 157 (含む) までの任意の値を読み取ることができます。したがって、log₂(157) == 8 ビットを読み取る必要があります。

デコードされた値 : 小さい値は1ビット少なく使用します。たとえば、0から157 (含む) までの値が可能であると仮定すると、255 - 157 = 98 個の値が8ビットフィールドに残ります。最初の98個の値 (したがって0から97まで) は7ビットのみを使用し、98から157までの値は8ビットを使用します。これは表20のスキームによって実現されます:

+============+===============+===========+
| Value Read | Value Decoded | Bits Used |
+============+===============+===========+
|   0 - 97   |     0 - 97    |     7     |
+------------+---------------+-----------+
|  98 - 127  |    98 - 127   |     8     |
+------------+---------------+-----------+
| 128 - 225  |     0 - 97    |     7     |
+------------+---------------+-----------+
| 226 - 255  |   128 - 157   |     8     |
+------------+---------------+-----------+

表20: デコードされた値

シンボル確率は順番に1つずつ読み取られます。確率は式 P = Value - 1 を使用してデコードされた値 (Value Decoded) から取得されます。これは、値0が負の確率-1になることを意味します。これは「1未満」を意味する特別な確率です。分布テーブルへの影響については後述します。合計配分確率ポイントを計算する目的では、1としてカウントされます。

シンボルの確率がゼロの場合、2ビットの繰り返しフラグ (Repeat Flag) が続きます。この繰り返しフラグは、現在のシンボルに続くゼロ確率の数を示します。0から3までの数値を提供します。3の場合、別の2ビットの繰り返しフラグが続き、以下同様です。

最後のシンボルが累積合計 (1 &lt;&lt; Accuracy_Log) に達すると、デコーディングが完了します。最後のシンボルが累積合計を (1 &lt;&lt; Accuracy_Log) を超えさせる場合、分布は破損していると見なされます。

最後に、デコーダーはこのプロセスで使用されたバイト数と存在するシンボルの数を知ることができます。ビットストリームは整数バイトを消費します。最後のバイト内の残りのビットは単に未使用です。

テーブルが使用されるコンテキストは、予想されるシンボル数を指定します。その予想シンボル数は256を超えません。デコードされたシンボルの数が予想と等しくない場合、ヘッダーは破損していると見なされるべきです。

正規化された確率の分布は、一意のデコーディングテーブルを作成するのに十分です。テーブルのサイズは (1 &lt;&lt; Accuracy_Log) です。各セルは、デコードされたシンボルと次の状態を取得するための指示を記述します。

シンボルは、上記の「1未満」の確率について自然な順序でスキャンされます。この確率を持つシンボルには、テーブルの終端から始めて後退しながら単一のセルが割り当てられます。これらのシンボルは完全な状態リセット (Full State Reset) を定義し、Accuracy_Log ビットを読み取ります。

残りのすべてのシンボルは自然な順序で割り当てられます。シンボル0とテーブル位置0から始めて、各シンボルはその確率と同じ数のセルを割り当てられます。セルの割り当ては分散されており、線形ではありません。各後続位置は次のルールに従います:

position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;

位置がすでに「1未満」の確率シンボルによって占有されている場合、その位置はスキップされます。位置はシンボル間でリセットされません。現在のシンボルに十分な状態が割り当てられたときに次のシンボルに切り替えながら、テーブル内の各位置を単に反復します。

結果は状態値のリストです。各状態は現在のシンボルをデコードします。

次の状態に必要な Number_of_Bits と Baseline を取得するには、まずすべての状態を自然な順序でソートする必要があります。下位の状態は上位の状態よりも1ビット多く必要になります。このプロセスは各シンボルに対して繰り返されます。

例: シンボルの確率が5であると仮定すると、5つの状態値を受け取ります。状態は自然な順序でソートされます。次の2の累乗は8です。確率空間は8つの等しい部分に分割されます。Accuracy_Log が7であると仮定すると、これは128の状態を定義し、各シェア (8で除算) のサイズは16です。8に到達するために、8 - 5 = 3 の最下位状態は「ダブル」カウントされ、シェア数を2倍 (幅32) にし、プロセスでさらに1ビットを必要とします。

Baseline は、より少ないビットを使用するより高い状態から開始して割り当てられ、自然に進み、その後最初の状態から再開し、各状態は Baseline から割り当てられた幅を取得します。

+----------------+-------+-------+--------+------+-------+
|  state order   |   0   |   1   |   2    |  3   |   4   |
+----------------+-------+-------+--------+------+-------+
|     width      |   32  |   32  |   32   |  16  |   16  |
+----------------+-------+-------+--------+------+-------+
| Number_of_Bits |   5   |   5   |   5    |  4   |   4   |
+----------------+-------+-------+--------+------+-------+
|  range number  |   2   |   4   |   6    |  0   |   1   |
+----------------+-------+-------+--------+------+-------+
|    Baseline    |   32  |   64  |   96   |  0   |   16  |
+----------------+-------+-------+--------+------+-------+
|     range      | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+----------------+-------+-------+--------+------+-------+

表21: Baseline割り当て

次の状態は、必要な Number_of_Bits を読み取り、指定された Baseline を追加することによって現在の状態から決定されます。

デフォルト分布に適用されるこのプロセスの結果については、付録Aを参照してください。

4.2 Huffman Coding (ハフマン符号化)​

Zstandard Huffman 符号化ストリームは、FSE ビットストリームと同様に逆方向に読み取られます。したがって、ビットストリームの開始を見つけるには、Huffman 符号化ストリームの最後のバイトのオフセットを知る必要があります。

情報を含む最後のビットを書き込んだ後、コンプレッサーは単一の1ビットを書き込み、その後バイトの残りを0ビットで埋めます。そのため、圧縮ビットストリームの最後のバイトは0にはなりません。

解凍時、パディングを含む最後のバイトが最初に読み取るバイトです。デコンプレッサーは、最大7ビットの0パディングと、発生する最初の1ビットをスキップする必要があります。その後、ビットストリームの有用な部分が始まります。

ビットストリームには、リトルエンディアン順序で Huffman 符号化されたシンボルが含まれており、コードは以下の方法で定義されます。

4.2.1 Huffman Tree Description (ハフマン木記述)​

プレフィックス符号化 (Prefix Coding) は、事前に既知のアルファベットからのシンボルをビットシーケンス (コードワード) で表現し、各シンボルに1つのコードワードを割り当てます。異なるシンボルは異なる長さのビットシーケンスで表現される場合がありますが、パーサーは常に符号化された文字列を明確にシンボルごとに解析できます。

既知のシンボル頻度を持つアルファベットが与えられると、Huffman アルゴリズムは、そのアルファベットのすべての可能なプレフィックスコードの中で最小ビット数を使用して最適なプレフィックスコードを構築できます。

プレフィックスコードは最大コード長を超えてはなりません。より多くのビットは精度を向上させますが、より大きなヘッダーサイズを生成し、より多くのメモリまたはより複雑なデコーディング操作を必要とします。この仕様では、最大コード長を11ビットに制限しています。

ゼロ (含む) から最後に存在するリテラル値 (除く) までのすべてのリテラル値は、0から Max_Number_of_Bits までの値を持つ Weight (重み) で表されます。Weight から Number_of_Bits への変換は、この擬似コードに従います:

if Weight == 0:
    Number_of_Bits = 0
else:
    Number_of_Bits = Max_Number_of_Bits + 1 - Weight

最後のシンボルの Weight は、以前にデコードされたものから推定され、最も近い2の累乗に完成させます。この2の累乗は Max_Number_of_Bits、つまり現在の木の深さを与えます。

(以降、表22-26とHuffman符号化ストリームの詳細が続きます)

5. Dictionary Format (辞書形式)​

Zstandard は「生コンテンツ辞書 (Raw Content Dictionaries)」と互換性があり、少なくとも 8 バイト以上でなければならないという制約以外、形式に制限はありません。これらの辞書は、フォーマット済み辞書のコンテンツ部分のみであるかのように機能します。

ただし、参照実装の zstd --train によって作成される辞書は、ここで説明する特定の形式に従います。

辞書は圧縮コンテンツに含まれず、帯域外 (Out of Band) で提供されます。つまり、Dictionary_ID はどの辞書を使用すべきかを識別しますが、この仕様では圧縮または解凍の前に辞書を取得するメカニズムは説明していません。

辞書にはサイズがあり、バッファ制限またはファイルサイズによって定義されます。一般的な形式は次のとおりです:

+==============+===============+================+=========+
| Magic_Number | Dictionary_ID | Entropy_Tables | Content |
+==============+===============+================+=========+

表 27: 辞書の一般形式

Magic_Number (マジックナンバー) : 4 バイト ID、値 0xEC30A437、リトルエンディアン形式。

Dictionary_ID (辞書ID) : 4 バイト、リトルエンディアン形式で格納されます。Dictionary_ID は 0 を除く任意の値を取ることができます (0 は Dictionary_ID が存在しないことを表します)。デコーダーはこれを使用して、正しい辞書を使用しているかを確認します。フレームがプライベート環境で配布される場合、任意の Dictionary_ID を使用できます。ただし、圧縮フレームを公開配布する場合、次の範囲は予約されており、使用してはなりません:

  • 低範囲: &lt;= 32767
  • 高範囲: >= 2³¹

Entropy_Tables (エントロピーテーブル) : 圧縮ブロック内のテーブルと同じ形式に従います。これらのテーブルをデコードする方法については、関連する FSE および Huffman セクションを参照してください。それらは次の順序で格納されます: リテラル用の Huffman テーブル、オフセット用の FSE テーブル、マッチ長用の FSE テーブル、およびリテラル長用の FSE テーブル。これらのテーブルは、シーケンスデコードの繰り返し統計リテラルモード (Repeat Stats Literals Mode) および繰り返し分布モード (Repeat Distribution Mode) を埋めます。最後に、3 つのオフセット値があり、繰り返しオフセットを埋め ({1,4,8} を使用する代わりに)、順に格納され、それぞれ 4 バイトのリトルエンディアン、合計 12 バイトです。各繰り返しオフセットは、辞書サイズより小さい値を持つ必要があります。

Content (コンテンツ) : 辞書の残りの部分はそのコンテンツです。コンテンツは、圧縮または解凍されるデータの前にある「過去 (Past)」として機能し、シーケンスコマンド (Sequence Commands) で参照できます。このフレームからデコードされたデータ量が Window_Size 以下である限り、シーケンスコマンドは、これまでにデコードされた出力の合計長より長いオフセットを指定して、辞書を参照できます。これには、辞書内のオフセットが Window_Size より大きい部分も含まれます。ただし、合計出力が Window_Size を超えた後は、これは許可されなくなり、辞書にアクセスできなくなります。

6. Use of Dictionaries (辞書の使用)​

zstd の辞書使用に関する規定を提供する取り組みが進行中です。例えば、[DICT-SEC] を参照してください。考えられる結果は、さまざまなユースケースに最適化された十分にテストされた辞書のレジストリとその識別子、および未登録の辞書を使用するためのプライベート交渉メカニズム (Private Negotiation Mechanism) です。

zstd ペイロード (Payload) で辞書を使用する将来の仕様との互換性、特に MIME との互換性を確保するため、ここで登録されたメディアタイプを使用してエンコードされたコンテンツは辞書を使用すべきではありません (SHOULD NOT)。この要件の例外は、上記で示唆されたプライベート辞書交渉である可能性がありますが、これは本仕様の一部ではありません。

7. IANA Considerations (IANA考慮事項)​

IANA は、以下に説明するように、既存の 2 つの登録を更新し、1 つの新規登録を行いました。

7.1 The 'application/zstd' Media Type ('application/zstd' メディアタイプ)​

application/zstd メディアタイプは、zstd を使用して圧縮されたデータブロックを識別します。データは、このドキュメントで説明されているバイトストリームです。IANA は「Media Types」(メディアタイプ) レジストリに以下を追加しました:

Type name (タイプ名) : application

Subtype name (サブタイプ名) : zstd

Required parameters (必須パラメータ) : N/A

Optional parameters (オプションパラメータ) : N/A

Encoding considerations (エンコーディング考慮事項) : binary

Security considerations (セキュリティ考慮事項) : RFC 8878 のセクション 8 を参照してください。

Interoperability considerations (相互運用性考慮事項) : N/A

Published specification (公開仕様) : RFC 8878

Applications which use this media type (このメディアタイプを使用するアプリケーション) : データサイズが問題となるあらゆる場所

Fragment identifier considerations (フラグメント識別子考慮事項) : このタイプにはフラグメント識別子が定義されていません。

Additional information (追加情報) :

  • Deprecated alias names for this type (このタイプの非推奨エイリアス名): N/A
  • Magic number(s) (マジックナンバー): 4 バイト、リトルエンディアン形式。値: 0xFD2FB528
  • File extension(s) (ファイル拡張子): zst
  • Macintosh file type code(s) (Macintosh ファイルタイプコード): N/A

Person & email address to contact for further information (詳細情報の連絡先) : Yann Collet &lt;[email protected]&gt;

Intended usage (使用目的) : common (一般)

Restrictions on usage (使用制限) : N/A

Author (著者) : Murray S. Kucherawy

Change Controller (変更管理者) : IETF

Provisional registration (暫定登録) : no

For further information (詳細情報) : [ZSTD] を参照してください

7.2 Content Encoding (コンテンツエンコーディング)​

IANA は、「Hypertext Transfer Protocol (HTTP) Parameters」(ハイパーテキスト転送プロトコル (HTTP) パラメータ) レジストリ内の「HTTP Content Coding Registry」(HTTP コンテンツコーディングレジストリ) に以下のエントリを追加しました:

Name (名前) : zstd

Description (説明) : Zstandard プロトコルを使用して圧縮されたバイトストリーム

Reference (参照) : RFC 8878

7.3 Structured Syntax Suffix (構造化構文サフィックス)​

IANA は「Structured Syntax Suffix」(構造化構文サフィックス) レジストリに以下を登録しました:

Name (名前) : Zstandard

+suffix (サフィックス) : +zstd

Encoding Considerations (エンコーディング考慮事項) : binary

Interoperability Considerations (相互運用性考慮事項) : N/A

Fragment Identifier Considerations (フラグメント識別子考慮事項) : +zstd に指定されたフラグメント識別子の構文と意味は、application/zstd に指定されたものと同じである必要があります。

Security Considerations (セキュリティ考慮事項) : RFC 8878 のセクション 8 を参照してください。

Contact (連絡先) : application/zstd メディアタイプの著者を参照してください。

Author/Change Controller (著者/変更管理者) : IETF

7.4 Dictionaries (辞書)​

進行中の作業には、特定のタイプのデータの圧縮と解凍を最適化する辞書の開発が含まれます。公開使用のためにそのような辞書を指定するには、セクション 3.1.1.1.3 で説明されている予約範囲からのコードポイントの登録と、特定の辞書との関連付けが必要になります。

現在、公開使用のためにそのような辞書は公開されていないため、このドキュメントではそのようなレジストリの作成を IANA に直ちに要求していません。

8. Security Considerations (セキュリティに関する考慮事項)​

あらゆるデータ圧縮方法は、データ内の冗長性を減らすことを含みます。Zstandard も例外ではなく、通常の予防措置が適用されます。

内容を秘密にする必要があるメッセージを、第三者によって生成されたメッセージと一緒に圧縮してはなりません。このような圧縮は、エントロピー削減分析 (Entropy Reduction Analysis) を通じて秘密メッセージの内容を推測するために使用される可能性があります。例えば、これは圧縮比情報漏洩簡素化攻撃 (Compression Ratio Info-leak Made Easy, CRIME) [CRIME] で実証されています。

デコーダーは、圧縮フレーム内のあらゆる種類のデータ改ざんが、許可されたメモリ範囲を超えた読み取りまたは書き込みなどのシステム障害を引き起こすことを検出および防止する能力を示す必要があります。これは、実装言語または注意深い境界チェック (Bound Checking) によって保証できます。特に注目すべきは、Number_of_Sequences 値のエンコーディングで、これによりデコーダーがブロックヘッダー (さらにその先) まで読み取る可能性があり、実際の解凍データよりも小さいことを示す Frame_Content_Size により、バッファオーバーフロー (Buffer Overflow) を引き起こそうとする試みです。デコーダー実装をファジーテスト (Fuzz-test、つまり無効、予期しない、またはランダムな入力を提供し、安全な動作を検証する) して、エラーフレームを検出し、悪影響のあるシステム副作用なしにそれらを処理する能力をテストおよび強化することを強くお勧めします。

攻撃者は、フォーマットは正しいが不合理なメモリ要件を持つ圧縮フレームを提供する可能性があります。デコーダーは常にメモリ要件を制御し、このようなシナリオからメモリ使用を保護するために特定の (システム固有の) 制限を強制する必要があります。

様々な関連コンテンツペイロード上でディクショナリをトレーニングすることにより、圧縮を最適化できます。その後、デコーダーはペイロードを解凍するためにこのディクショナリを使用できる必要があります。このドキュメントでは、特定の圧縮ペイロードのディクショナリを取得する方法を指定していませんが、サードパーティのディクショナリがデコーダーと予期しない相互作用を引き起こし、メモリまたはその他のリソース枯渇攻撃 (Resource-exhaustion Attacks) につながる可能性があることに注意する価値があります。このようなトピックは、ディクショナリの取得と伝送に関する今後の RFC のセキュリティに関する考慮事項セクションでより詳細に議論されることが期待されますが、慎重を期すために現在この問題を強調しています。

セクション 3.1.2 で説明されているように、スキップ可能フレーム (Skippable Frames) に任意のユーザーメタデータを格納できます。このようなフレームはデータ解凍中に無視されますが、圧縮ペイロードのパスを追跡するためのウォーターマーク (Watermark) として使用できます。

Appendix A. Decoding Tables for Predefined Codes (附録A. 事前定義コードのデコードテーブル)​

この附録には、事前定義されたリテラル長、マッチ長、およびオフセットコードの FSE デコードテーブルが含まれています。これらのテーブルは、セクション 4.1.1 で示したアルゴリズムを使用して構築されています。ここのテーブルは、実装がデコードテーブルを正しく構築したかどうかをクロスチェックするための例として使用できます。

A.1. Literals Length Code Table (リテラル長コードテーブル)​

State (状態)Symbol (シンボル)Number_Of_Bits (ビット数)Base (ベース)
0000
0040
10416
21532
3350
4450
5650
6750
7950
81050
91250
101460
111650
121850
131950
142150
152250
162450
1725532
182650
192760
202960
213160
220432
23140
24250
254532
26550
277532
28850
2910532
301150
311360
3216532
331750
3419532
352050
3622532
372350
382540
3925416
4026532
412860
423060
430448
441416
452532
463532
475532
486532
498532
509532
5111532
5212532
531560
5417532
5518532
5620532
5721532
5823532
5924532
603560
613460
623360
633260

表 28: リテラル長コードテーブル

A.2. Match Length Code Table (マッチ長コードテーブル)​

State (状態)Symbol (シンボル)Number_Of_Bits (ビット数)Base (ベース)
0000
0060
1140
22532
3350
4550
5650
6850
71060
81360
91660
101960
112260
122560
132860
143160
153360
163560
173760
183960
194160
204360
214560
221416
23240
243532
25450
266532
27750
28960
291260
301560
311860
322160
332460
342760
353060
363260
373460
383660
393860
404060
414260
424460
431432
441448
452416
464532
475532
487532
498532
501160
511460
521760
532060
542360
552660
562960
575260
585160
595060
604960
614860
624760
634660

表 29: マッチ長コードテーブル

A.3. Offset Code Table (オフセットコードテーブル)​

State (状態)Symbol (シンボル)Number_Of_Bits (ビット数)Base (ベース)
0000
0050
1640
2950
31550
42150
5350
6740
71250
81850
92350
10550
11840
121450
132050
14250
157416
161150
171750
182250
19450
208416
211350
221950
23150
246416
251050
261650
272850
282750
292650
302550
312450

表 30: オフセットコードテーブル

Appendix B. Changes since RFC 8478 (附録B. RFC 8478からの変更点)​

以下は、RFC 8478 と比較した本文書の変更点です:

  • 正誤表 [Err5786] および [Err6303] を適用しました。

  • 辞書に関する前方互換性を明確化しました。

  • Block_Maximum_Size の適用を明確化しました。

  • 構造化メディアタイプサフィックスの登録を追加しました。

  • コンテンツチェックサムが常に 4 バイトであることを明確化しました。

  • 予約済み入力および破損した入力の処理を明確化しました。

  • メディアタイプ登録にフラグメント識別子の考慮事項を追加しました。

Acknowledgments (謝辞)​

zstd は Yann Collet によって開発されました。

Felix Handte と Nick Terrell が本リビジョンおよび RFC 8478 へのフィードバックを提供しました。RFC 8478 は、Bobo Bose-Kolanu、Kyle Nekritz、および David Schleimer からの貢献も受けました。

Authors' Addresses (著者の連絡先)​

Yann Collet
Facebook
1 Hacker Way
Menlo Park, CA 94025
United States of America

Email: [email protected]

Murray S. Kucherawy (editor)
Facebook
1 Hacker Way
Menlo Park, CA 94025
United States of America

Email: [email protected]