zlib - standard

zlib

RFC 1950 ZLIB Compressed Data Format Specification version 3.3

doi:10.17487/rfc1950

urn:ietf:rfc:1950

Catrgory: Informational

RFC 1951 DEFLATE

RFC 1952 GZIP

Network Working Group

Request for Comments: 1950

分類: 情報

P. Deutsch

Aladdin Enterprises

J-L. Gailly

Info-ZIP

1996年5月

ZLIB 圧縮データフォーマット仕様バージョン 3.3

このメモのステータス

このメモはインターネットコミュニティ向けの情報を提供します。いかなる種類のインターネット標準も規定するものではありません。このメモの配布は無制限です。

IESG注記：

IESGは、この文書に含まれる知的財産権に関する記述の有効性について、いかなる立場も表明しません。

通知

この文書は、著作権表示およびこの表示が保持され、原本からの重要な変更または削除が明確に示されている限り、他の言語への翻訳および編集物への組み込みを含め、いかなる目的であっても無償で複製および配布することを許可します。

この文書および関連文書のHTML形式の最新版へのポインタは、URL <ftp://ftp.uu.net/graphics/png/documents/zlib/zdoc-index.html> にあります。

概要

本仕様は、ロスレス圧縮データ形式を定義する。任意の長さの順次入力データストリームであっても、事前に制限された量の中間ストレージのみを使用して、データの生成または利用が可能となる。本仕様は現在DEFLATE圧縮方式を採用しているが、他の圧縮方式を使用するように容易に拡張できる。特許の影響を受けない方法で容易に実装できる。本仕様は、データ破損の検出に使用されるADLER-32チェックサム（Fletcherチェックサムの拡張および改良）も定義し、その計算アルゴリズムも提供する。

1 はじめに Introduction

1.1 目的 Purpose

この仕様の目的は、以下の条件を満たすロスレス圧縮データ形式を定義することです。

CPUの種類、オペレーティングシステム、ファイルシステム、および文字セットに依存しないため、データ交換に使用できます。

任意の長さの連続した入力データストリームであっても、事前に制限された量の中間ストレージのみを使用して生成または使用できます。したがって、データ通信やUnixフィルタなどの同様の構造で使用できます。

様々な圧縮方式を使用できます。

特許で保護されない方法で容易に実装できるため、自由に実施できます。

この仕様で定義されるデータ形式は、圧縮データへのランダムアクセスを可能にするものではありません。

1.2 対象読者 Intended audience

本仕様は、zlib形式へのデータ圧縮、および／またはzlib形式からのデータの解凍を行うソフトウェアの実装者を対象としています。

本仕様書の内容は、ビットレベルおよびその他の基本的なデータ表現におけるプログラミングの基礎知識を前提としています。

1.3 適用範囲 Scope

この仕様は、任意のバイト列のメモリ内圧縮に使用できる圧縮データ形式を規定する。

1.4 仕様準拠 Compliance

以下で特に明記されていない限り、準拠する解凍器は、ここで提示されるすべての仕様に準拠するあらゆるデータセットを受け入れ、解凍できなければなりません。また、準拠する圧縮器は、ここで提示されるすべての仕様に準拠するデータセットを生成しなければなりません。

1.5 用語の定義と表記規則 Definitions of terms and conventions used

バイト：8ビットを1単位として格納または伝送する単位（オクテットと同じ）。（この仕様では、1バイトは正確に8ビットです。

文字を8以外のビット数で格納するマシンでも、同じです。）バイト内のビットの番号付けについては、以下を参照してください。

1.6 以前のバージョンからの変更点 Changes from previous versions

バージョン3.1は、この仕様の最初の公開リリースでした。バージョン3.2では、一部の用語が変更され、Adler-32のサンプルコードが書き直されてわかりやすくなりました。バージョン3.3では、プリセット辞書のサポートが導入され、仕様がRFCスタイルに変更されました。

2 詳細仕様 Detailed specification

2.1 全体的な慣習 Overall conventions

下の図では、次のようなボックスがあります。

code:box

+---+

| | <-- 縦棒が欠けているかもしれない

+---+

1 バイトを表します。

次のようなボックスがあります。

code:one byte

+==============+

| |

+==============+

可変数のバイトを表します。

コンピュータ内に格納されるバイトは「ビット順序」を持ちません。これは、バイトが常に単位として扱われるためです。しかし、0から255までの整数として扱われるバイトには、最上位ビットと最下位ビットがあり、数値は最上位桁を左にして表記するため、バイトも最上位ビットを左にして表記します。以下の図では、バイトのビットに番号を付けており、ビット0が最下位ビットとなります。つまり、ビットは次のように番号付けされています。

code:numbered

+--------+

|76543210|

+--------+

コンピュータ内では、数値が複数バイトを占める場合があります。ここで説明する形式のマルチバイト数値はすべて、最上位バイトから（メモリの下位アドレスに）格納されます。例えば、10進数520は次のように格納されます。

code:520

0 1

+--------+--------+

|00000010|00001000|

+--------+--------+

^ ^

| |

| + 下位バイト = 8

+ 上位バイト = 2 x 256

2.2 Data format

zlib ストリームの構造は次のとおりです。

code:CMFFLG

0 1

+---+---+

|CMF|FLG| (more-->)

+---+---+

(if FLG.FDICT set)

code:FIDCT

0 1 2 3

+---+---+---+---+

| DICTID | (more-->)

+---+---+---+---+

+===============+---+---+---+---+

|...圧縮データ...| ADLER32 |

+===============+---+---+---+---+

ADLER32 の後に出現する可能性のあるデータは、zlib ストリームの一部ではありません。

CMF (圧縮方式とフラグ Compression Method and flags)

このバイトは、4 ビットの圧縮方式と、圧縮方式に応じた 4 ビットの情報フィールドに分割されます。

table:CMF

bits 0 to 3 CM 圧縮方式 Compression method

bits 4 to 7 CINFO 圧縮情報 Compression info

CM (圧縮方式 Compression Method)

ファイルで使用されている圧縮方式を識別します。CM = 8 は、ウィンドウサイズが最大 32KB の「deflate」圧縮方式を示します。これは gzip と PNG で使用されている方式です（参考文献については、第 3 章の 1 と 2 を参照してください）。CM = 15 は予約語です。この仕様の将来のバージョンでは、圧縮データの前に追加フィールドが存在することを示すために使用される可能性があります。

CINFO (圧縮情報 Compression Info)

CM = 8の場合、CINFOはLZ77ウィンドウサイズの2を底とする対数から8を引いた値です（CINFO=7は32Kのウィンドウサイズを示します）。このバージョンの仕様では、CINFOに7を超える値は許可されていません。CMが8でない場合、CINFOはこの仕様では定義されていません。

FLG (GLaGs)

このフラグバイトは以下のように分割されます。

table:FLG

bits 0 to 4 FCHECK (check bits for CMF and FLG)

bit 5 FDICT (プリセット辞書)

bits 6 to 7 FLEVEL (compression level)

FCHECK 値は、CMF と FLG を MSB 順に格納された 16 ビットの符号なし整数 (CMF*256 + FLG) として表示したときに、31 の倍数となるようにする必要があります。

FDICT (プリセット辞書 Preset dictionary)

FDICTが設定されている場合、FLGバイトの直後にDICT辞書識別子が存在します。この辞書は、圧縮出力を生成することなく、最初に圧縮器に供給されるバイト列です。DICTは、このバイト列のAdler-32チェックサムです（ADLER32の定義は下記を参照）。解凍器はこの識別子を使用して、圧縮器がどの辞書を使用したかを判別できます。

FLEVEL (圧縮レベル Compression level)

これらのフラグは、特定の圧縮方式で使用できます。「deflate」（CM = 8）方式では、これらのフラグは以下のように設定されます。

0 - 圧縮機は最速アルゴリズムを使用

1 - 圧縮機は高速アルゴリズムを使用

2 - 圧縮機はデフォルトのアルゴリズムを使用

3 - 圧縮機は最大圧縮率、最遅アルゴリズムを使用

FLEVELの情報は解凍には必要ありません。再圧縮が必要かどうかを示すために存在します。

圧縮データ(compressed data)

圧縮方式8の場合、圧縮データはL. Peter Deutsch著「DEFLATE圧縮データフォーマット仕様」に記載されているdeflate圧縮データ形式で保存されます。（下記第3章の参考文献3を参照）

その他の圧縮データ形式は、このバージョンのzlib仕様では規定されていません。

ADLER32 (Adler-32 チェックサム)

このチェックサムは、Adler-32 アルゴリズムに従って計算された非圧縮データ（辞書データは除く）のチェックサム値を含みます。このアルゴリズムは、ITU-T X.224 / ISO 8073 規格で使用されている Fletcher アルゴリズムの 32 ビット拡張および改良版です。第 3 章の参考文献 4 および 5 を参照してください。

Adler-32 は、バイトごとに累積された 2 つの合計で構成されます。s1 はすべてのバイトの合計、s2 はすべての s1 値の合計です。どちらの合計も 65521 を法として計算されます。s1 は 1 に、s2 は 0 に初期化されます。Adler-32 チェックサムは、s2*65536 + s1 として、最上位バイト順（ネットワーク順）で格納されます。

2.3 準拠 Compliance

準拠する圧縮器は、正しいCMF、FLG、およびADLER32を持つストリームを生成する必要がありますが、プリセット辞書をサポートする必要はありません。zlibデータ形式が他の標準データ形式の一部として使用される場合、圧縮器は、その他のデータ形式で指定されたプリセット辞書のみを使用できます。その他の形式がプリセット辞書機能を使用しない場合、圧縮器はFDICTフラグを設定してはなりません。

準拠する解凍器は、CMF、FLG、およびADLER32をチェックし、これらのいずれかに誤った値がある場合はエラー通知を提供する必要があります。準拠する解凍器は、CMがこの仕様で定義されている値（このバージョンでは値8のみが許可されています）のいずれでもない場合、エラー通知を提供する必要があります。これは、他の値が、後続のデータの解釈を誤らせる可能性のある新機能の存在を示している可能性があるためです。

準拠する解凍器は、FDICTが設定され、DICTIDが既知のプリセット辞書の識別子でない場合、エラー通知を提供する必要があります。解凍器はFLEVELを無視しても準拠を維持できます。 zlibデータ形式が他の標準形式の一部として使用される場合、準拠するデコンプレッサは、その形式で指定されるすべてのプリセット辞書をサポートする必要があります。その形式がプリセット辞書機能を使用しない場合、準拠するデコンプレッサはFDICTフラグが設定されているストリームをすべて拒否する必要があります。

3 参考文献 References

1 Deutsch, L.P., “GZIP 圧縮データフォーマット仕様”, ftp://ftp.uu.net/pub/archiving/zip/doc/ で入手可能

2 Thomas Boutell, “PNG (Portable Network Graphics) 仕様”, ftp://ftp.uu.net/graphics/png/documents/ で入手可能

3 Deutsch, L.P., “DEFLATE 圧縮データフォーマット仕様”, ftp://ftp.uu.net/pub/archiving/zip/doc/ で入手可能

4 Fletcher, J. G., “An Arithmetic Checksum for Serial Transmissions,” IEEE Transactions on Communications, Vol. COM-30, No. 1, January 1982, pp. 247-252.

5 ITU-T勧告X.224、附属書D、「チェックサムアルゴリズム」、1993年11月、pp. 144, 145。

(gopher://info.itu.chから入手可能)。ITU-T X.244もISO 8073と同一である。

4 ソースコード Source code

「zlib」準拠ライブラリのC言語実装のソースコードは、ftp://ftp.uu.net/pub/archiving/zip/zlib/ から入手できます。

5 セキュリティに関する考慮事項 Security Considerations

ADLER32 チェックサム値のチェックに失敗したデコーダーでは、検出されないデータ破損が発生する可能性があります。

6 謝辞 Acknowledgements

この文書に記載されている商標は、それぞれの所有者に帰属します。

Jean-Loup GaillyとMark Adlerはzlibフォーマットを設計し、この仕様書に記載されている関連ソフトウェアを開発しました。Glenn Randers-Pehrsonは、この文書をRFCおよびHTMLフォーマットに変換しました。

7 著者のアドレス Authors' Addresses

L. Peter Deutsch

Aladdin Enterprises

203 Santa Margarita Ave.

Menlo Park, CA 94025

電話: (415) 322-0103 (午前のみ)

FAX: (415) 322-1734

Eメール: <ghost@aladdin.com>

Jean-Loup Gailly

Eメール: <gzip@prep.ai.mit.edu>

本仕様の技術的内容に関するご質問は、下記までメールでお問い合わせください。

Jean-Loup Gailly <gzip@prep.ai.mit.edu>

Mark Adler <madler@alumni.caltech.edu>

本仕様に関する編集上のご意見は、下記までメールでお問い合わせください。

L. Peter Deutsch <ghost@aladdin.com>

Glenn Randers-Pehrson <randeg@alumni.rpi.edu>

8 付録：根拠 Appendix: Rationale

8.1 プリセット辞書

プリセット辞書は、短い入力シーケンスを圧縮する場合に特に便利です。圧縮器は、辞書のコンテキストを利用して、入力をよりコンパクトにエンコードできます。解凍器は、辞書の圧縮バージョンを仮想的に解凍することで、適切なコンテキストで初期化できます。ただし、deflateアルゴリズムなどの特定の圧縮アルゴリズムでは、実際に解凍を行うことなくこの操作を実行できます。

圧縮器と解凍器は全く同じ辞書を使用する必要があります。辞書は固定することも、入力データの種類に応じて、一定数の定義済み辞書から選択することもできます。

解凍器は、辞書識別子をチェックすることで、圧縮器がどの辞書を選択したかを判断できます。最適な辞書はアプリケーションに固有であるため、このドキュメントでは定義済み辞書の内容は規定しません。zlib仕様のこの機能を使用する標準データ形式では、使用可能な辞書を正確に定義する必要があります。

8.2 Adler-32アルゴリズム

Adler-32アルゴリズムはCRC32アルゴリズムよりもはるかに高速でありながら、検出されないエラーの確率は極めて低い。

符号なしlong型アキュムレータのモジュロ演算は5552バイト遅延させることができるため、モジュロ演算時間は無視できる。バイトがa、b、cの場合、2番目の合計は3a + 2b + c + 3となり、単なるチェックサムである最初の合計とは異なり、位置と順序が重要となる。65521が素数であることは、チェック結果が変更されない可能性のある2バイトエラーの大規模なクラスを回避するために重要である。（Fletcherチェックサムは255を使用するが、これは素数ではないため、Fletcherチェックは0 <-> 255の単一バイトの変化を考慮に入れない。）

合計s1は、シーケンスの長さをs2の一部とするために0ではなく1に初期化される。これにより、長さを別途チェックする必要がなくなる。 (ゼロのシーケンスの Fletcher チェックサムはゼロになります。)

9 付録: サンプルコード

以下のCコードは、データバッファのAdler-32チェックサムを計算します。これは速度ではなく、分かりやすさを重視して書かれています。

サンプルコードはANSI Cプログラミング言語で記述されています。C言語を使わない方は、以下のヒントを参考にすると読みやすくなるかもしれません。

code:sample

& ビット単位の AND 演算子.

> ビット単位の右シフト演算子. 符号なしの値に適用すると、右シフトは左側にゼロビットを挿入します。

<< ビット単位の左シフト演算子。左シフトは右側にゼロビットを挿入します。

++ "n++" は変数 n をインクリメントします。

% モジュロ演算子: a % b は a を b で割った余りです。

#define BASE 65521 /* 65536より小さい最大の素数 */

実行中のAdler-32チェックサムをbuf0..len-1バイトで更新し、

更新されたチェックサムを返します。Adler-32チェックサムは1に

初期化する必要があります。

使用例:

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 + bufn) % BASE;

s2 = (s2 + s1) % BASE;

}

return (s2 << 16) + s1;

}

/* バイトbuf0..len-1のadler32を返す */

unsigned long adler32(unsigned char *buf, int len)

{

return update_adler32(1L, buf, len);

}