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

1. はじめに (Introduction)

1. はじめに (Introduction)​

1.1. 目的 (Purpose)​

本仕様の目的は、以下の特性を持つロスレス圧縮データフォーマット (Lossless Compressed Data Format) を定義することです:

  • CPU タイプ、オペレーティングシステム、ファイルシステム、文字セットに依存しない。したがって、データ交換に使用できる。

  • 任意に長い、シーケンシャルに提示される入力データストリームに対しても、事前に制限された量の中間ストレージのみを使用して、生成または消費できる。したがって、データ通信や Unix フィルタなどの類似構造で使用できる。

  • 現在利用可能な最高の汎用圧縮方法と同等の圧縮率 (Compression Ratio) でデータを圧縮し、特に gzip プログラムよりもかなり優れている。

  • 現在の LZMA 実装よりもはるかに高速に展開 (Decompress) する。

本仕様で定義されるデータフォーマットは、以下を試みません:

  • 圧縮データへのランダムアクセスを許可する。

  • 特殊化されたデータ（例: ラスターグラフィックス）を、現在利用可能な最高の特殊化アルゴリズムと同じ密度で圧縮する。

本ドキュメントは、brotli 圧縮データフォーマットの権威ある仕様です。有効な brotli 圧縮データストリームのセットと、有効な brotli 圧縮データストリームから非圧縮データストリームを生成するデコーダアルゴリズム (Decoder Algorithm) を定義します。

1.2. 対象読者 (Intended Audience)​

本仕様は、brotli フォーマットでデータを圧縮および/または展開するソフトウェア実装者が使用することを目的としています。

仕様のテキストは、ビットおよびその他のプリミティブデータ表現のレベルでのプログラミングの基本的な背景を前提としています。ハフマン符号化 (Huffman Coding) の技術に精通していることは有用ですが、必須ではありません。

本仕様は、DEFLATE フォーマット仕様 [RFC1951] で導入された表記法と用語を（大量に）使用しています。完全性のために、RFC 1951 の関連部分の全文を常に含めています。したがって、DEFLATE フォーマットに精通していることは有用ですが、必須ではありません。

本仕様で定義される圧縮データフォーマットは、WOFF ファイルフォーマット 2.0 [WOFF2] の不可欠な部分です。したがって、本仕様は WOFF 2.0 圧縮器および展開器の実装者も対象としています。

1.3. 範囲 (Scope)​

本ドキュメントは、バイトシーケンス (Sequence of Bytes) を（通常はより短い）ビットシーケンス (Sequence of Bits) として表現する方法と、後者のビットシーケンスをバイトにパッキングする方法を規定します。

1.4. 準拠 (Compliance)​

以下に特に示されない限り、準拠展開器 (Compliant Decompressor) は、ここで提示されるすべての仕様に準拠する任意のデータセットを受け入れ、展開できなければなりません。準拠圧縮器 (Compliant Compressor) は、ここで提示されるすべての仕様に準拠するデータセットを生成しなければなりません。

1.5. 用語と規約の定義 (Definitions of Terms and Conventions Used)​

バイト (Byte): 単位として保存または送信される 8 ビット（オクテットと同じ）。本仕様では、文字を 8 以外のビット数で保存するマシンであっても、バイトは正確に 8 ビットです。バイト内のビットの番号付けについては以下を参照してください。

文字列 (String): 任意のバイトのシーケンス。

コンピュータ内に保存されるバイトは、常に単位として扱われるため、「ビット順序」を持ちません。ただし、0 から 255 の間の整数と見なされるバイトには、最上位ビット (msb) と最下位ビット (lsb) があります。数値を最上位桁を左に書くため、バイトも最上位ビットを左に書きます。以下の図では、バイトのビットを、ビット 0 が最下位ビットになるように番号付けします。つまり、ビットは次のように番号付けされます:

+--------+
|76543210|
+--------+

コンピュータ内では、数値は複数のバイトを占める場合があります。ここで説明するフォーマットのすべてのマルチバイト数値は、最下位バイト (Least-Significant Byte) を最初に（より低いメモリアドレスに）保存します。たとえば、10 進数 520 は次のように保存されます:

    0        1
+--------+--------+
|00001000|00000010|
+--------+--------+
 ^        ^
 |        |
 |        + more significant byte = 2 x 256
 + less significant byte = 8

1.5.1. バイトへのパッキング (Packing into Bytes)​

本ドキュメントは、ビットシーケンシャルメディア上でバイトのビットが送信される順序の問題には対応していません。ここで説明する最終データフォーマットは、ビット指向ではなくバイト指向であるためです。ただし、以下では圧縮ブロックフォーマット (Compressed Block Format) を、バイトのシーケンスではなく、さまざまなビット長のデータ要素のシーケンスとして説明します。したがって、これらのデータ要素をバイトにパックして最終的な圧縮バイトシーケンスを形成する方法を指定する必要があります:

  • データ要素は、バイト内のビット番号が増加する順序でバイトにパックされます。つまり、バイトの最下位ビットから始まります。

  • ハフマンコード (Huffman Code) 以外のデータ要素は、データ要素の最下位ビットから始めてパックされます。

  • ハフマンコードは、コードの最上位ビットから始めてパックされます。

言い換えれば、圧縮データをバイトのシーケンスとして、最初のバイトを右余白から始めて左に進むように印刷し、各バイトの最上位ビットを通常どおり左にすると、右から左に結果を解析でき、固定幅要素は正しい MSB から LSB の順序で、ハフマンコードはビット反転順序（つまり、コードの最初のビットが相対的な LSB 位置にある）で配置されます。

例として、次のデータ要素を 3 バイトのシーケンスにパックすることを考えます:

  • 2 ビット値 1（2 進数 01）
  • 3 ビット値 2（2 進数 010）
  • 5 ビット値 6（2 進数 00110）
  • ビットパターン 1011 の 4 ビットコード（最初のビットが 1、2 番目のビットが 0、3 番目のビットが 1、4 番目のビットが 1）
  • 2 ビット値 0（2 進数 00）
  • ビットパターン 0011 の 4 ビットコード
  • 5 ビット値 31（2 進数 11111）

次の図は、これらの要素がどのようにパックされるかを示しています:

       Byte 0           Byte 1           Byte 2
   +---------------+----------------+----------------+
   |0|1|1|0|0|0|1|0|1|1|0|1|1|0|0|0|0|1|1|1|1|1|1|1|
   +---------------+----------------+----------------+
    ^ ^ ^   ^     ^ ^     ^       ^   ^             ^
    | | |   |     | |     |       |   |             |
    | | |   |     | |     |       |   +-------------|---+ 5-bit value 31
    | | |   |     | |     |       +-----------------|---|-+ 4-bit code 0011
    | | |   |     | |     +-----------------------+     |
    | | |   |     | |                             |     | 2-bit value 0
    | | |   |     | +-----------------------------+-----+ 4-bit code 1011
    | | |   +---+ 5-bit value 6
    | | +-----+ 3-bit value 2
    | +---+ 2-bit value 1

出典 (Source): RFC 7932, Section 1
公式テキスト (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt

に最終更新