Deflate
RFC自体はフォーマットと自称しているが、アルゴリズムと解釈されることが多いと思う
実装
フォーマット
block
各ブロックの先頭は3ビット
1ビット目がそのブロックが終端ブロックかどうかを示す
0: 終端ブロックではない
1: 終端ブロック
2ビット目がそのブロックのタイプを示す
00: Uncompressed、ママのデータが格納される
01: Fixed Huffman codesでエンコードされている
10: Dynamic Huffman codesでエンコードされている
Uncompressed blocks
まず、次のbyte boundaryまでデータを無視する
残りのブロックが次を表す
code:plain
0 1 2 3 4...
+---+---+---+---+================================+
| LEN | NLEN |... LEN bytes of literal data...|
+---+---+---+---+================================+
LENがblockの大きさ、NLENがLENの1の補数
Compressed blocks
テーブルを参照しながらリテラルを埋めていく
各アルファベット（ハフマン符号化されるトークン？）は以下のように対応する:
0 - 255がリテラル
256がend-of-block
257-285がlength code
以下のように並べられていく:
literal: リテラルに対応する符号
match: length codeに対応する符号・（長さのExtra bits）・distance codeに対応する符号・（距離のExtra bits)
distanceよりlengthのほうが大きくて走査が終端に達したら、またdistanceまで戻ってリピートする
end: end-of-block (256) に対応する符号
各length codeは以下の通り対応する:
code:plain
Extra Extra Extra
Code Bits Length(s) Code Bits Lengths Code Bits Length(s)
---- ---- ------ ---- ---- ------- ---- ---- -------
257 0 3 267 1 15,16 277 4 67-82
258 0 4 268 1 17,18 278 4 83-98
259 0 5 269 2 19-22 279 4 99-114
260 0 6 270 2 23-26 280 4 115-130
261 0 7 271 2 27-30 281 5 131-162
262 0 8 272 2 31-34 282 5 163-194
263 0 9 273 3 35-42 283 5 195-226
264 0 10 274 3 43-50 284 5 227-257
265 1 11,12 275 3 51-58 285 0 258
266 1 13,14 276 3 59-66
各distance codeは以下のように対応する:
code:plain
Extra Extra Extra
Code Bits Dist Code Bits Dist Code Bits Distance
---- ---- ---- ---- ---- ------ ---- ---- --------
0 0 1 10 4 33-48 20 9 1025-1536
1 0 2 11 4 49-64 21 9 1537-2048
2 0 3 12 5 65-96 22 10 2049-3072
3 0 4 13 5 97-128 23 10 3073-4096
4 1 5,6 14 6 129-192 24 11 4097-6144
5 1 7,8 15 6 193-256 25 11 6145-8192
6 2 9-12 16 7 257-384 26 12 8193-12288
7 2 13-16 17 7 385-512 27 12 12289-16384
8 3 17-24 18 8 513-768 28 13 16385-24576
9 3 25-32 19 8 769-1024 29 13 24577-32768
Fixed Huffman codesのblock
リテラルを以下のように参照する:
code:plain
Lit Value Bits Codes
--------- ---- -----
0 - 143 8 00110000 through
10111111
144 - 255 9 110010000 through
111111111
256 - 279 7 0000000 through
0010111
280 - 287 8 11000000 through
11000111
よっぽどファイルサイズが小さくてDynamic Huffman codesを作るまでもない場合くらいしか出てこないと思いますよ
Dynamic Huffman codesを含むblock
バイナリ列を出現頻度に応じてハフマン符号化してあげようねえ
符号長シーケンスそのものもハフマン符号化される
block冒頭 count は次から始まる:
5ビットの HLIT, リテラルもしくはlength codeの数 - 257 (257 - 286)
5ビットの HDIST, distance codeの数 - 1 (1 - 32)
4ビットの HCLEN, このブロック自体のアルファベットの数 - 4 (4 - 19)
(HCLEN + 4) * 3 ビットが次の code の列で消費される
次に、符号長アルファベットのハフマン木をその符号長のリスト code として記述する
ここがキワモノで、各符号長アルファベットは指定せずとも次の順番で指定されている:
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
16・17・18が先頭にいるのは、後述するrepeat・zerosがたくさん出てくることを期待しているんだと思う
符号長アルファベットの符号長 (0 - 7)
次に、各リテラルおよびlength code → distance codeの符号長を並べていく
即ち、前述した(HLIT + 257) + (HDIST + 1)個のアルファベットの符号長を指定する
0-15: lens、符号長を4ビットで表す (0 - 15)
16: 2ビットのrepeat、直前の符号長を繰り返す (3-6)
17: 3ビットのzeros、ゼロ符号長を繰り返す (3-10)
18: 7ビットのzeros、ゼロ符号長を繰り返す (11-138)
ここで、ゼロ符号長は即ちそのアルファベットは登場しないことを表す
zlib
zlibの場合は、ヘッダーが2バイト（以上）・フッターが4バイトつく
RFC 1950を参照
ヘッダー
1バイト目
下位4: CM Compression method。Deflateなら8
上位4: CINFO Compression info。通常は7（= 32K window size）
2バイト目
下位5: FCHECK ヘッダーのチェックビット
1: FDICT 辞書が存在するか
上位2: FLEVEL Compression Level
まあ無視でいいんじゃね？
Content-Encoding
CompressionStreamについては、生Deflateが deflate-raw で利用できる