Thinking Skeever

Skyrim/The Witcher 3 Modについてのあれこれ。FoModの作り方、Mod導入時のトラブル事例などのニッチな話を書いていきます。a.k.a. BowmoreLover@nexusmods

LZ4 Frame Format Description Version 1.5.1 日本語訳

本文書はYann Collet氏の「LZ4 Frame Format Description」の日本語訳です。LZ4フレーム形式のデコード処理を書く必要があったのですが、日本語訳が見当たらなかったので翻訳してみました。
誤訳の可能性がありますので、正確性を求める場合は必ず原文を参照してください。
何か間違いがあればコメントでご指摘いただけると助かります。

一部ニュアンスが読み取りにくい部分がありますので補足しておきます。

  • 連結されたフレームのフロー(原文: flow of concatenated frames)- 連続したフレームの流れ、というニュアンスです
  • ブロックチェックサムはコンテンツチェックサムと累積されます(原文: Block checksum is cumulative with Content checksum.) - 累積(cumulative)方法が分からなかったので直訳しました
  • 圧縮が有害(原文: compression is detrimental)- 恐らく圧縮によりサイズが増え、逆効果のケースを指すものと思われます

LZ4 Frame Format Description (LZ4フレーム形式の説明)

著作権表示

Copyright (c) 2013-2015 Yann Collet

Permission is granted to copy and distribute this document for any purpose and without charge, including translations into other languages and incorporation into compilations, provided that the copyright notice and this notice are preserved, and that any substantive changes or deletions from the original are clearly marked. Distribution of this document is unlimited.

著作権表記および本通知が保持されている場合、多言語への翻訳や編集物への編集を含め、目的が何であれ無償で本文書を複製、再配布することが許可されています。オリジナルからの実質的な変更や削除を明確に記述してください。本文書の再配布に制限はありません。

バージョン

1.5.1 (2015/3/31)

はじめに

本書の目的は、CPUの種類・オペレーティングシステムファイルシステム・キャラクターセットに依存せずパイプまたはストリーミングの圧縮に適したLZ4 アルゴリズムを使った可逆圧縮データ形式を定義することです。

本形式ではLZ4圧縮方式を利用します。データ破損検出のためにオプションとしてxxHash-32チェックサム方式を利用します。

本仕様で定義されるデータ形式では、圧縮データへのランダムアクセスは許可されません。

本仕様は、データをLZ4形式に圧縮したりLZ4形式からデータを圧縮解除するソフトウェアの実装者が利用することを意図しています。
本仕様書では、ビット列やその他の基本データ表現レベルの基本的なプログラミング知識があることを前提としています。

以下で特に明記されない限り、(本仕様に)準拠する圧縮装置は、ここに示された仕様に適合したデータセットを生成する必要があります。全てのオプションをサポートする必要はありません。

(本仕様に)準拠する解凍装置は、ここに示された仕様に準拠したパラメータのうち、少なくとも1つのワーキングセットを解凍できる必要があります。チェックサムを無視することもできます。圧縮ストリーム内の特定のパラメータをサポートしていない場合は、常に曖昧ではないエラーコードと、サポートされていないパラメータを示すエラーメッセージを提供する必要があります。

LZ4フレーム形式の全体構造

マジックナンバー フレーム記述子 ブロック (...) エンドマーク コンテントチェックサム
4バイ 3~11バイ 4バイ 0~4バイ

マジックナンバー

4バイト、リトルエンディアン形式。
値 : 0x184D2204

フレーム記述子

3~11バイトです。次の章で詳しく説明します。仕様において最も重要な部分です。

データブロック

詳細は後述。圧縮されたデータが格納されます。

エンドマーク

ブロックのフローは最後のデータブロック長が"0"のときに終了します。サイズは32ビットの値で表現されます。

コンテントチェックサム

コンテントチェックサムはコンテント全てが正しくデコードされたことを確認するためのものです。コンテントチェックサムハッシュ関数 xxh32()に元の(デコードされた)データとシード 0を入力した結果です。コンテントチェックサムは、フレーム記述子に関連付けられたフラグが設定さている場合にのみ存在します。コンテントチェックサムは、全てのブロックが正しい順序でエラーなしに全て送信されたことと、エンコード/デコード処理自体で歪曲が生じていないという結果を検証します。
使用が推奨されます。

フレームの連結

例えば再編成することなく既存の圧縮ファイルに新しいデータを追加するというように、状況によっては複数のフレームを付け足すのが望ましい場合があります。

そのような場合のために、各フレームには独自の記述子フラグのセットがあります。各フレームは独立していると見なされます。フレーム間の唯一の関係性は順序だけです。

単一のストリームやファイルを複数の連結されたフレームにデコードする機能は本仕様の範囲外です。例えば、lz4コマンドラインユティリティの動作は、連結された全てのフレームを順序通りにデコードすることです。

フレーム記述子

フラグ ブロック記述子 コンテント長 ヘッダチェックサム
1バイ 1バイ 0~8バイ 1バイ

記述子は最低3バイトで、オプションのパラメータに応じて最大11バイトを使用します。

フラグバイ

ビット番号 7~6 5 4 3 2 1~0
フィールド名 バージョン ブロック独立 ブロックチェックサム コンテント長 コンテントチェックサム 予約

ブロック識別子バイ

ビット番号 7 6~5~4 3~2~1~0
フィールド名 予約 ブロック最大長 予約

表においては、ビット7は最上位ビットを、ビット0は最下位ビットを示しています。

バージョン番号

2ビットのフィールドで、必ず"01"を設定します。本バージョンの仕様では他の値をデコードすることはできません。他のバージョン番号は異なるフラグのレイアウトを使うことになります。

ブロック独立フラグ

フラグが"1"の場合、ブロックは独立しています。フラグが"0"の場合、各ブロックは前のブロックに依存します(LZ4のウィンドウサイズである64KBまで)。この場合、全てのブロックを順序通りにデコードする必要があります。

小さなブロックにおいては特に、ブロックの依存性は圧縮率を向上させます。一方、ダイレクトジャンプやマルチスレッドによるデコードは不可能です。

ブロックチェックサムフラグ

このフラグが設定されている場合、各データブロックの後に、xxHash-32アルゴリズムによって算出された、生の(圧縮された)データブロックに対する4バイトのチェックサムが続きます。この目的は、デコード前に即時にデータ破損(ストレージや伝送のエラー)を検出することです。ブロックチェックサムの使用はオプションです。

コンテント長フラグ

このフラグが設定されている場合、フレーム中のデータの圧縮解除時の長さがフラグの後に8バイト符号なしリトルエンディアン形式の値として存在します。コンテント長の使用はオプションです。

コンテントチェックサムフラグ

このフラグが設定されている場合、コンテントチェックサムがエンドマークの後ろの追加されます。
推奨値: "1" (コンテントチェックサムを提供)

ブロック最大長

この情報の目的は、デコーダーのメモリ割り当てを助けることです。この長さは元の(圧縮前の)データ長を示します。ブロック最大長は次の表の値のどれかとなります。

0 1 2 3 4 5 6 7
未使用 未使用 未使用 未使用 64KB 256KB 1MB 4MB

デコーダーは(システム固有の)長さを超える割り当てブロック長を拒否することができます。未使用の値は将来の仕様改訂で使用される可能性があります。現バージョンの仕様に準拠したデコーダーは、本仕様で定義されたブロック長だけをデコードできます。

予約ビット

予約ビットの値は必ず0(ゼロ)にする必要があります。予約ビットは将来バージョンの仕様で使用される可能性がありますが、通常は新しいオプション機能を有効にします。これが起こった場合、現バージョンの仕様を尊重するデコーダーはそのようなフレームをデコードできないものとします。

コンテント長

これは元の(未圧縮の)長さです。この情報はオプションであり、関連付けられたフラグが設定されている場合にのみ存在します。コンテント長は符号なし8バイト、最大16ヘクサバイトを提供します。形式はリトルエンディアンです。この値は通常、表示やメモリ割り当てのための情報です。デコーダーによってはスキップされたり、コンテントの正しさを検証するために使用されたりします。

ヘッダーチェックサム

オプションの記述子フィールドを含む、結合された識別子フィールドの1バイトのチェックサムです。この値はシードに0を使い、フレーム識別子(オプションフィールドが存在する場合はそれらも含む)を入力としたxxh32()の結果の2バイト目((xxh32()>>8) & 0xFF)です。チェックサムの誤りは記述子のエラーを示します。ヘッダチェックサムは情報であり、スキップすることができます。

データブロック

ブロック長 データ (ブロックチェックサム)
4バイ 0~4バイ

ブロック長

このフィールドは4バイトを使用し、形式はリトルエンディアンです。

ブロック内のデータが圧縮されいない場合、最上位ビットは"1"です。

ブロック内のデータがLZ4で圧縮されいる場合、最上位ビットは"0"です。

その他の全てのビットは後続のデータブロック長をバイト単位で示します(ブロックチェックサムはサイズには含まれない)。

ブロック長はブロック最大長より大きくなることはありません。このようなことは、元データが圧縮できない場合に発生する可能性があります。この場合、その種のデータブロックは非圧縮形式で渡されるものとします。

データ

デコードすべき実データのある場所です。先行するフィールドの指示によって、圧縮されているかどうかが決まります。圧縮されていないデータの長さは「ブロック最大長」を上限とした任意のサイズにできます。任意のタイミングで「フラッシュ」されうるので、データブロックは必ずしも「完全に埋められた状態」ではないことに注意してください。どのブロックも「部分的に埋める」ことができる。

ブロックチェックサム

関連付けられたフラグが設定されている場合にのみ存在します。これはリトルエンディアン形式のチェックサム4バイトで、xxHash-32アルゴリズムを使った生(デコード前)のデータブロックとシード0の計算値です。この目的は、デコード前に即時にデータ破損(ストレージや伝送のエラー)を検出することです。

ブロックチェックサムはコンテンツチェックサムと累積されます。

スキップ可能フレーム

マジックナンバー フレーム長 ユーザデータ
4バイ 4バイ

スキップ可能フレームは、連結されたフレームのフローにユーザ定義のデータを統合することを可能にします。
その設計は非常に単純で、デコーダーがユーザ定義データをすばやくスキップしてデコードを続行することが唯一の目的です。

識別を容易にするため、スキップ可能フレームから連結されたフレームのフローを開始することは推奨されません。
何らかのユーザデータをスキップ可能なフレームにカプセル化してフローを開始する必要がある場合、0バイトのLZ4フレームから開始して、スキップ可能フレームを続けることを推奨します。
これにより、ファイル種別の識別が容易になります。

マジックナンバー

4バイトのリトルエンディアン形式です。
値: 0x184D2A5X、つまり0x184D2A50から0x184D2A5Fの値です。

16種類すべての値でスキップ可能フレームが識別可能です。

フレーム長

後続のユーザデータ長をバイト単位で示します(マジックナンバーおよび長さフィールド自体は含めません)。4バイトのリトルエンディアン形式で、符号なし32ビットです。つまり、ユーザデータは(2^32-1)バイトより大きくできません。

ユーザデータ

ユーザデータは何でも構いません。データはデコーダーによりスキップされます。

レガシーフレーム

レガシーフレーム形式は"LZ4Demo"の初期バージョンで定義されていたものです。あまりにも制限が多いので、最新の圧縮機では本形式を使用しないでください。

レガシー形式の主な特徴:

  • 固定ブロック長: 8MB
  • 最後のブロックを除き、全てのブロックを完全に埋める必要がある
  • 圧縮が有害であっても、全ブロックは常に圧縮される
  • 最後のブロックの検出は、"EOF"(ファイル終了)マークが続くか、既知のフレームマジックナンバーが続く場合のみである
  • チェックサムなし
  • トルエンディアン形式
マジックナンバー ブロック圧縮長 圧縮データ ブロック圧縮長 圧縮データ (...) エンドマーク
4バイ 4バイ ブロック圧縮長 4バイ ブロック圧縮長 繰り返し EOF

マジックナンバー

4バイトのリトルエンディアン形式です。
値: 0x184C2102

ブロック圧縮長

後続の圧縮データブロックの長さをバイト単位で示します。
4バイトのリトルエンディアン形式です。

データ

圧縮データが実際にある場所です。
圧縮が有害であっても、データは常に圧縮されます。

エンドマーク

レガシーフレームの終わりは暗黙的です。
必ずファイルやストリームで標準のEOF(ファイルの終わり)の印が後続する必要があります。

あるいは、フレームの後に有効なフレームのマジックナンバーが続く場合、完了したと見なされます。
レガシーフレームはフレーム連結と互換性を持ちます。

他の値はブロック長として解釈され、許容範囲に収まらない場合はエラーを発生させます。

バージョン履歴

1.5.1 : マークダウン記法互換形式に変更した

1.5 : 定義からDictionary IDを削除した

1.4.1 : 用語を「ストリーム」から「フレーム」に変更した

1.4 : スキップ可能なストリープを追加。ストリームのチェックサムの再追加

1.3 : ヘッダチェックサムの変更

1.2 : 「ブロック長フィールドの動的長」の決定延期のため、「ブロック長」の選択肢を減らした

1.1 : オプションのフィールドを記述子の一部にした

1.0 : 「ブロック長」の仕様変更。圧縮/非圧縮フラグを追加した。

0.9 : 「ブロック最大長」テーブルの規模を縮小した

0.8 : 削除 : 高圧縮フラグ

0.7 : 削除 : ストリームチェックサム

0.6 : 解決済み : ストリーム長には8バイトを使用し、エンディアンはリトルエンディアンとする

0.5: 著作権表示の追加

0.4 : Google Doc互換のOpenDocument形式に変更した

日本語訳の改訂履歴

  • 2016/11/27 23:30 : 初回公開

以上

Copyright (C) 2015,2017 ThinkingSkeever, All Rights Reserved.
ブログの記事内に記載されているメーカー名、製品名称等は、日本及びその他の国における各企業の商標または登録商標です。
リンクはご自由に。記事の転載はご遠慮ください。記事を引用する場合はトラックバックするか元のURLを明記してください。