本ドキュメントは、RFC 1950 『RFC 1950 ZLIB Compressed Data Format Specification version 3.3』 を futomi が日本語化したものです。みなさまの理解に役立てれば幸いです。なお、緑色で記載された文章は、futomi が注釈として加筆したものです。また、一部、直訳ではなく、意訳した部分がございます。原文と表現が異なることがございますので、ご了承ください。
注意: この日本語訳は、futomi が理解を深めるために、自分なりに日本語化したものです。本日本語訳には、翻訳上の誤りがある可能性があります。したがって、内容について一切保証をするものではありません。正確さを求める場合には、必ず原文を参照してください。当方は、この文書によって利用者が被るいかなる損害の責任を負いません。
もし誤りなどを見つけたら、こちらからご連絡いただければ幸いです。
| Network Working Group |
P. Deutsch |
| Request for Comments: 1950 |
Aladdin Enterprises |
| Category: Informational |
J-L. Gailly |
|
Info-ZIP |
|
May 1996 |
このメモは、インターネットコミュニティーのために情報を提供するものです。このメモは、いかなる種類のインターネット標準を定めるものではありません。このメモの配布は無制限です。
IESG は、本文書に含まれるいかなる知的所有権声明の正当性に関して、特定の立場をとりません。
Copyright (c) 1996 L. Peter Deutsch and Jean-Loup Gailly
いかなる目的に対しても、多言語への翻訳、編集物への組み込みを含めて、本文書のコピーおよび配布を無償で許諾します。ただし、著作権表示およびこの注意事項を遵守して下さい。また、元文書から実質的な変更や削除があれば、その部分を明確に表示下さい。※本日本語訳においては、緑色で記した箇所が futomi による加筆部分です。実質的な変更や削除は、本日本語訳においてはございません。
本文書の最新版と、HTML フォーマットの関連文書の情報は、こちらに掲載されております。
<ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html>.
この仕様は、可逆圧縮データフォーマットを定義するものです。次々に現れるどんな長さの入力データストリームでさえも、事前に制限した中間記憶装置の容量を使うだけで、データを生成または消費することができます。このフォーマットは、現状、DEFLATE 圧縮方式を採用していますが、他の圧縮方式へ容易に拡張することができます。それは、特許に抵触しない形で、ためらうことなく実装することができます。この仕様では、さらに、データ改竄の検出に使われる ADLER-32 チェックサム（Fletcher チェックサムを拡張・改良したもの）を定義し、その計算アルゴリズムを説明します。
1.1. 目的
この仕様は、以下に示す可逆圧縮データフォーマットを定義することを目的としています。
- CPU タイプ、オペレーティングシステム、ファイルシステム、文字セットから独立しています。従って、交換目的で使うことができます。
- 事前に制限した中間記憶装置の容量を使うだけで、長さにかかわりなく次々に出現する入力データストリームを、生成または消費することができます。従って、データ通信や、Unix フィルターのような仕組みに使うことができます。
- 多数の異なる圧縮方式を使うことができます。
- 特許に抵触しない形で、ためらうことなく実装することができます。だから、自由に実行することができます。
この仕様で定義されるデータフォーマットは、圧縮データへランダムアクセスすることはできません。
1.2. 対象読者
この仕様は、データを zlib フォーマットに圧縮する、もしくは zlib フォーマットから解凍するソフトウェアの開発者による利用を対象としています。
この仕様の文章は、ビットレベルや他の原始的なデータ表現でのプログラミングにおける基本的な知識を前提としています。
1.3. 適用範囲
この仕様は、連続した任意バイトのメモリ内圧縮に使える圧縮データフォーマットを規定します。
1.4. 準拠
以降で示すものでなければ、準拠した解凍器は、ここで提示されるすべての仕様に従ってるどんなデータセットでも受け入れ、そして解凍できなければいけません。；準拠した圧縮器は、ここで提示されるすべての仕様に従っているデータセットを生成しなければいけません。
1.5. 用語・規約の定義
バイト： 一つのユニットとして、蓄積もしくは転送された 8 ビット です。（オクテットと同義）。（たとえ 8 ビットで一つの文字を蓄積しないマシンにおいても、この仕様では、バイトは正確に 8 ビットを意味します。） バイトの中でのビットの番号付けは、下記をご覧下さい。
1.6. 前バージョンからの変更点
この仕様は、バージョン 3.1 で初めて公開されました。バージョン 3.2 では、いくつかの専門用語が変更され、Adler-32 サンプルコードが分かりやすく書き換えられました。バージョン 3.3 では、プリセット辞書のサポートが紹介され、仕様が RFC スタイルに変換されました。
2.1. 全般的な規約
下図をご覧下さい。次のような箱は 1 バイトを表します。
+---+
| | <-- 垂直棒は表示されない場合があります。
+---+
次の様な箱は、可変長バイトを表します。
+==============+
| |
+==============+
コンピュータに蓄積されているバイトは、ビットの順番に意味はありません。なぜなら、それらは常に一つの単位として扱われるからです。しかし、0 ～ 255 までの整数としてみなされるバイトは、最上位ビット（MSB）もしくは最下位ビット（LSB）を持っています。私達は左から最上位桁の数字を書きますから、左に最上位ビットを持つバイトを書き込みます。下図をご覧下さい。ビット 0 が最下位ビットとなるように、バイトのビットを番号付けしています。
+--------+
|76543210|
+--------+
コンピュータ内部では、数字はマルチバイトで構成される場合があります。ここで説明するフォーマット内のすべてのマルチバイト数字は、最初に最上位バイトから蓄積されます（低いメモリアドレスに）。例えば、十進数 520 は、次のように蓄積されます。
0 1
+--------+--------+
|00000010|00001000|
+--------+--------+
^ ^
| |
| + 下位バイト = 8
+ 上位バイト = 2 x 256
2.2. データフォーマット
zlib ストリームは、下図の構造となっています。
0 1
+---+---+
|CMF|FLG| (続く-->)
+---+---+
（FLG. FDICT がセットされている場合）
0 1 2 3
+---+---+---+---+
| DICTID | (続く-->)
+---+---+---+---+
+=====================+---+---+---+---+
|.....圧縮データ......| ADLER32 |
+=====================+---+---+---+---+
ADLER32 の後ろに現れるいかなるデータも、zlib ストリームの一部ではありません。
| CMF (Compression Method and flags) |
|
このバイトは、4 ビットの圧縮方式と 4 ビットの圧縮方式に依存する情報フィールドに分けられます。 |
|
|
ビット 0 ～ 3 CM （圧縮方式）
ビット 4 ～ 7 CINFO （圧縮情報） |
| CM (圧縮方式 - Compression method) |
|
これは、ファイルで使われる圧縮方式を表します。CM = 8 は、32K までのウィンドウサイズを使った "deflate" 圧縮方式であることを意味します。これは、gzip や PNG によって使われる方式です（第 3 章のリファレンス [1], [2] をご覧下さい。）。CM = 15 は予約です。圧縮データの前に余分なフィールドが存在するということは、本仕様の将来のバージョンにおいて使われるかも知れないということを意味します。※
※ CM の値は 8 のみということですが、これをビット列で表現すれば、"1000" です。15 は将来のために予約されてるとのことですが、この値をビット列で表現すれば、"1111" となります。つまり、CM を表現する 4 ビットのうち、一番左のビット（ビット番号 3）だけを立てて、それ以外はビットを立ててはいけないということです。"1111" だけが予約されているという意味ではなく、"0100", "0010", "0001" 等、右から 3 つのビット（ビット番号 0 ～ 2）のいずれも、将来のために予約されているということです。 |
| CINFO (圧縮情報 - Compression info) |
|
CM = 8 の場合には、CINFO は、底が 2 の LZ77 ウィンドウサイズの対数から 8 を引いた値となります（CINFO=7 は、32K のウィンドウサイズを意味します。※）。本仕様バージョンでは、7 を超える CINFO の値を認めていません。CM の値が 8 でなければ CINFO は定義されません。
※ LZ77 ウィンドウサイズが 32K バイト（32 * 1,024 = 32,768 バイト）の場合、CINFO の値は、log2(32,768) - 8 = 7 となるのです。 |
| FLG (FLaGs) |
|
このフラグのバイトは、次のように分割されます。 |
|
|
ビット 0 ～ 4 FCHECK （CMF と FLG のチェックビット）
ビット 5 FDICT （プリセット辞書）
ビット 6 ～ 7 FLEVEL （圧縮レベル） |
|
CMF と FLG を MSB の順序で蓄積された 16 ビットの符号なし整数（CMF*256 + FLG）としてみたときに、この値が 31 の倍数となるように、FCHECK の値が定義されなければいけません。 |
| FDICT (Preset dictionary) |
|
FDICT がセットされている場合には、DICT 辞書識別子が FLG バイトの直後に現れないといけません。辞書は、圧縮出力を生成することなしに、圧縮器に最初に入力される連続したバイトです。DICT は、この連続したバイトの Adler-32 チェックサムです（後述の ADLER32 の定義をご覧下さい。）。解凍器は、この識別子を使って、圧縮器が辞書を使ったかどうかを判定することができます。 |
| FLEVEL (Compression level) |
|
これらのフラグは、特定の圧縮方式での利用に限り有効です。"deflate" 方式 (CM = 8) は、これらのフラグを次のようにセットします。 |
|
|
0 - 圧縮器は、最も速いアルゴリズムを使った
1 - 圧縮器は、速いいアルゴリズムを使った
2 - 圧縮器は、デフォルトアルゴリズムを使った
3 - 圧縮器は、最も遅いが、最大の圧縮率を誇るアルゴリズムを使った |
|
FLEVEL の情報は、解凍する際には必要ありません。再圧縮をする価値があるならば、それを示唆するためにあるのです。 |
| 圧縮データ |
|
圧縮方式 8 に対して、圧縮データは、 L. Peter Deutsch 著 "DEFLATE 圧縮データフォーマット仕様" で説明されている deflate 圧縮データフォーマットで蓄積されます（後述の第 3 章のリファレンス [3] をご覧下さい。）。
他の圧縮データフォーマットは、zlib 仕様のこのバージョンでは規定されておりません。 |
| ADLER32 (Adler-32 checksum) （※後述の補足を参照） |
|
これは、Adler-32 アルゴリズムで計算された非圧縮データ（辞書データも含む）のチェックサム値を収容します。このアルゴリズムは、 Fletcher アルゴリズムの 32 ビット拡張で改良されたもので、ITU-T X224 / ISO 8073 標準で使われています。後述の第 3 章 リファレンス [4], [5] をご覧下さい。
Adler-32 は、バイトごとに蓄積された 2 つの和から成り立っています。s1 は、すべてのバイトの和です。s2 は、すべての s1 値の和です。双方の和の値は、modulo 65521 で計算されます。s1 は 1 に初期化され、s2は 0 に初期化されます。Adler-32 チェックサムは、最上位バイトが最初にくる順番（ネットワークオーダー）で、s2 * 65536 + s1 として蓄積されます。 |
以上を踏まえ、zlib ヘッダーの具体例を先頭からビット順に示すと、次の通りとなります。括弧内の数字は、ビット数を表します。一番下段には具体的なビット列の例を示しました。以上までで説明されている各ヘッダーの内容と、それぞれに対応したビット列の順番に注意して下さい。
CMF FLG
+----------------------------+----------------------------+
|CMINFO(4) |CM(4) |FLEVEL(2)|FDICT(1)|FCHECK(5)|
+----------------------------+----------------------------+
0111 1000 11 0 11010
2.3. 準拠
準拠した圧縮器は、正確な CMF, FLG そして ADLER32 と一緒にストリームを生成しなければいけません。しかし、プリセット辞書をサポートする必要はありません。zlib データフォーマットが他の標準的なデータフォーマットの一部として使われるときには、圧縮器はこの他のデータフォーマットによって特定されたプリセット辞書のみを使うかも知れません。もしこの他のフォーマットがプリセット辞書機能を使わないのであれば、圧縮器は FDICT フラグをセットしてはいけません。
準拠した解凍器は、CMF, FLG そして ADLER32 をチェックしなければいけません。そして、これらのうち一つでも不正な値があったなら、エラーであることを伝えなければいけません。準拠した解凍器は、もし CM がこの仕様で定義された値でないなら、エラーであることを伝えなければいけません（このバージョンでは、8 のみが許可かされています。）。なぜなら、他の値は、新機能の存在を指し示しているかもしれず、それ以降に続くデータを正しく解釈できないかもしれないからです。準拠した解凍器は、FDICT がセットされ、かつ、DICTID が既知のプリセット辞書の指示子でないなら、エラーであることを伝えなければいけません。解凍器は、FLEVEL を無視するかもしれませんが、それでも準拠しています。zlib データフォーマットが他の標準フォーマットの一部として使われいるときには、準拠した解凍器は、他のフォーマットによって特定されたプリセット辞書のすべてをサポートしなければいけません。他のフォーマットがプリセット辞書機能を使わない時は、準拠した解凍器は、FDICT フラグがセットされたどんなストリームも拒否しなければいけません。
C 言語で書かれた "zlib" 準拠ライブラリーのソースコードは、ftp://ftp.uu.net/pub/archiving/zip/zlib/ で入手できます。
ADLER32 チェックサム値の照合に失敗するデコーダは、未検知のデータ改竄にさらされるかもしれません。
この文書で引用されている商標は、各所有者の財産です。
Jean-Loup Gailly と Mark Adler は、zlib フォーマットを設計しました。そして、この仕様で説明されている関連ソフトウェアを書きました。Glenn Randers-Pehrson は、この文書を RFC と HTML フォーマットに変換しました。
8.1. プリセット辞書
プリセット辞書は、短い入力シーケンスを圧縮するには、非常に役に立ちます。圧縮器は、辞書コンテキストを活用することで、よりコンパクトな方法で入力をエンコードすることができます。解凍器は、どんな出力を生成せずに、圧縮された辞書を仮想的に解凍することで、適切なコンテキストを使って初期化されることが可能です。しかし、deflate アルゴリズムのような一部の圧縮アルゴリズムでは、全く解凍を実行せずとも、この操作を達成することが可能です。
圧縮器と解凍器は、正確に同じ辞書を使わなければいけません。辞書は、固定されているかもしれませんし、入力データの種類に応じて、事前に決められた辞書の特定の番号の中から選択されるのかも知れません。解凍器は、辞書指示子をチェックすることで、どの辞書が圧縮器によって選択されたのかを特定することが可能です。この文書は、事前に決められた辞書の内容を特定しません。なぜなら最良の辞書がアプリケーション仕様だからです。zlib 仕様のこの機能を使う標準データフォーマットは、正確に許可された辞書を定義しなければいけません。
8.2. Adler-32 アルゴリズム
Adler-32 アルゴリズムは、CRC32 アルゴリズムより高速で、さらに、今なお、検知できないエラーの確率が極端に低いのが特徴です。
符号なし long 加算でのモジュロは、5552 バイトの遅れが起こりえます。そのため、モジュロ演算時間は、取るに足らないのです。バイトが a, b, c だとすると、第 2 の和は、3a + 2b + c + 3 となります（※後述の補足を参照） 。つまり、位置と順序は繊細であり、第 1 の和とは異なり、まさにチェックサムなのです。65521 という値が素数であるということは、チェックを変更しないようにする 2 バイトエラーの可能性のある大きなクラスを避けるために重要なことなのです。（Fletcher チェックサムは、255 を使いますが、それは素数ではなく、単一のバイトが 0 ～ 255 間で変化するために、Fletcher チェックを鈍感にさせるのです。）
和 s1 は、s2 の連続部分の長さにするために、ゼロの代わりに 1 に初期化されます。だから、長さを個別にチェックする必要がないのです。（連続したゼロは、ゼロの Fletcher チェックサムを持ちます。）
【補足】
ここで言っている "第 2 の和" とは、「2.2 データフォーマット」の "ADLER32 (Adler-32 checksum)" 欄で説明している "s2" のことを意味しています。そもそも Adler-32 チェックサムの計算方法は、RFC の説明では分かりにくいので、ここで補足します。「8.2 Adler-32 アルゴリズム」で解説されている s2 = 3a + 2b + c +3 を例に説明します。
まず、もととなるデータを 1 バイトずつ分割します。それぞれのバイトを 2 進数の数字に見立てます（符号なし整数ですので、十進数で表すと、0 ～ 255 の値になります。）。もととなるデータの各バイトの値が a, b, c だとします。Adler-32 チェックサムは、1 バイトずつ、都度、s1 と s2 を計算することに注意して下さい。また、s1 と s2 を求める時には、s1 は 1 に初期化し、s2 は 0 に初期化する点にも注意して下さい。分かりやすく言えば、最初に s1 の値を 1 にしてくということです。
では、1 バイト目の "a" から順に s1 と s2 を計算して見ましょう。まず、1 バイト目では、s1 の値は "a + 1" となります。次に 2 バイト目では、s1 の値は、先ほどの s1 = a + 1 に 2 バイト目の値 "b" を足して、s1 = (a + 1) + b = a + b + 1 となります。最後に 3 バイト目では、s1 の値は、2 バイト目で計算した s1 = a + b + 1 に、3 バイト目の値 c を足して、s1 = ( a + b + 1) + c = a + b + c + 1 となります。s2 は、各バイトで計算した s1 の和ですから、s2 = (a + 1) + (a + b + 1 ) + ( a + b + c + 1 ) = 3a + 2b + c + 3 となるのです。
この説明は、高々 3 バイトのデータを例に挙げましたが、実際には、同じことをバイトごとにどんどん繰り返していきます。そうすると、s1 の値や s2 の値が無限に大きくなってしまいます。実際の計算では modulo 65521 で計算しなければいけません。やさしく言い換えれば、各バイトごとで計算される値を 65521 で割った余りが、s1 になるのです。s2 も同様です。
以下の C コードは、データバッファの Adler-32 チェックサムを計算します。分かりやすく書いたコードですので、スピード重視ではありません。このサンプルコードは、ANSI C プログラミング言語です。C 言語利用者でない場合には、以下のヒントを使えば分かりやすいでしょう。
| & |
|
AND ビット演算子 |
| >> |
|
右ビットシフト演算子。符号なしの数量に適用すると、右にシフトした分だけ、左側にゼロビットを挿入します。 |
| << |
|
左ビットシフト演算子。左にシフトした分だけ、右側にゼロビットを挿入します。 |
| ++ |
|
"n++" は、n の値を加算します。 |
| % |
|
モジュロ演算子。a % b は、a を b で割った余りです。 |
#define BASE 65521 /* largest prime smaller than 65536 */
/*
Update a running Adler-32 checksum with the bytes buf[0..len-1]
and return the updated checksum. The Adler-32 checksum should be
initialized to 1.
Usage example:
unsigned long adler = 1L;
while (read_buffer(buffer, length) != EOF) {
adler = update_adler32(adler, buffer, length);
}
if (adler != original_adler) error();
*/
unsigned long update_adler32(unsigned long adler,
unsigned char *buf, int len)
{
unsigned long s1 = adler & 0xffff;
unsigned long s2 = (adler >> 16) & 0xffff;
int n;
for (n = 0; n < len; n++) {
s1 = (s1 + buf[n]) % BASE;
s2 = (s2 + s1) % BASE;
}
return (s2 << 16) + s1;
}
/* Return the adler32 of the bytes buf[0..len-1] */
unsigned long adler32(unsigned char *buf, int len)
{
return update_adler32(1L, buf, len);
}