Deflate圧縮を自力で解凍する

この記事の背景

VRChatというVRSNSのワールド製作ではUdonSharpという言語（C#っぽいやつ）を使うが、残念ながらDeflateStreamを使うことができない。
そこで、自前で解凍することを試みた。
（が、UdonSharpの実行速度が遅く、現実的な時間で解凍できなかった。）
この時の試行錯誤の結果、得られた知見を備忘録的に残しておく。

Deflate圧縮とは

ハフマン符号化とLZ77を組み合わせて圧縮する圧縮アルゴリズム。

• ハフマン符号化
  • よく登場する文字に短いビットを、あまり登場しない文字に長いビットを割り当てる
• LZ77
  • 前に出てきたデータと同じデータが現れたら、その位置と一致長の情報に置き換える

zipとかgzip、pngやfbxなど様々なファイルで使用されている。

詳しくは、素晴らしい記事がネットにいっぱい転がっているので、各自で検索してほしい。

データの形式

基本的に、アドレス順かつbit番号が小さい順に圧縮データが格納される。

 0x00000000                0x00000001                0x00000002
+-------------------------+-------------------------+-------------------------+
| 07,06,05,04,03,02,01,00 | 15,14,13,12,11,10,09,08 | 23,22,21,20,19,18,17,16 |
+-------------------------+-------------------------+-------------------------+ ......
  7  6  5  4  3  2  1  0    7  6  5  4  3  2  1  0    7  6  5  4  3  2  1  0

ただし、ハフマン符号と数字の情報には取り扱いが注意である。

ハフマン符号

ハフマン符号は、符号の先頭から1bitずつ順番に格納される。
例えば、ハフマン符号「110」は以下のように格納される。

+----------+----------+
| xxxxx011 | xxxxxxxx |
+----------+----------+ ......

数値

一方、数値の場合は、最下位ビットから順番に格納される。
例えば、数値「110」（=6）は以下のように格納される。

+----------+----------+
| xxxxx110 | xxxxxxxx |
+----------+----------+ ......

ブロック

Deflate圧縮のデータは、「ブロック」という単位で分割されている。
各ブロックには、3ビットのヘッダーが付与されている。

• BFINAL (1bit)
  • 最終ブロックなら1
• BTYPE (2bit)
  • 00 (0) ... 無圧縮
  • 01 (1) ... 固定ハフマン形式
  • 10 (2) ... カスタムハフマン形式
  • 11 (3) ... 未定義

注：BTYPEは数値扱いでデータが格納されている。

もしBFINALが1であればそのブロックで終了であるが、0の場合はまだ後ろにブロックが続いていることになる。

固定ハフマン形式のブロック

固定ハフマン形式のブロックには、LZ77で圧縮され、さらにハフマン符号化された圧縮データが入っている。

今回は、例として、以下のデータを解凍する。

73740a7274767471045200

分かりやすいように、1バイトずつ、2進数で表したデータも用意した。

01110011 01110100 00001010 01110010 01110100 01110110 01110100 01110001
00000100 01010010 00000000

ヘッダーは、BFINAL=1、BTYPE=01である。

このデータのハフマン符号化を元に戻すための符号表（文字/一致長の符号表）は、既に定義されている。
この表を用い、符号化されたデータを元に戻す。

値	ビット数	符号
0 - 143	8	00110000 - 10111111
144 - 255	9	110010000 - 111111111
256 - 279	7	0000000 - 0010111
280 - 287	8	11000000 - 11000111

元に戻したデータは、0～287の値になる。
（厳密には、286と287は圧縮データには出てこない）

この0～287の値は、以下の通りに対応している。

• 0～255： そのままのデータ
• 256： ブロック終端
• 257～285：一致長（つまり、この値が出てくればLZ77の処理を行うことになる）

試しに1つ読んでみる。
01110001 → 65
つまりそのままなので、65→0x41→Aである。
続きを読んでいく。

`01110010` → 66  → `0x42` →`B`（`AB`）
`10000010` → 82  → `0x52` →`R`（`ABR`）
`01110001` → 65  → `0x41` →`A`（`ABRA`）
`01110011` → 67  → `0x43` →`C`（`ABRAC`）
`01110001` → 65  → `0x41` →`A`（`ABRACA`）
`01110100` → 68  → `0x44` →`D`（`ABRACAD`）
`01110001` → 65  → `0x41` →`A`（`ABRACADA`）
`0000001`  → 257

0～255以外のデータが出てきた。
この値は、どれだけの長さ、これまでのデータと一致したかを表している。
読みだした値と実際の一致長の対応表は、定められているものを使う。

     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

（表形式にするのが面倒なので、RFC1951から抜粋）

Extra Bitsが0ではない場合は、Extra Bits分数値を読み込み、ベースの値に足す。
例えば、265の時は、追加で1ビット読み込み、0であれば11、1であれば11に1を足して12となる。

今回は、257なので、Extra Bitsは0、一致長は3となる。

続いて、距離を求める。
距離はハフマン符号化されているが、この対照表（距離の符号長表）も既に定義されている。

値	ビット数	符号
0 - 31	5	00000 - 11111

（あくまでもハフマン符号なので、データの読み出し方法に注意）

今回は、00101→5であった。
読みだした値と実際の距離の対応表は、定められているものを使う。

     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

（表形式にするのが面倒なので、RFC1951から抜粋）

今回は、5なので、Extra Bitsは1である。
よって、1バイト読み出す。
読みだした結果は0であったので、実際の距離は、7+0=7となる。

ここまでの読み出し結果は、ABRACADAであるので、末尾の7バイト前から1バイトずつ、合計3バイトをコピーする。
すると、ABRACADABRAとなった。
ここまでが、257～285の値が出てくる時の処理である。

符号表を用い、0～287の値を読み出す作業に戻る。
0000000 → 256

またもや、0～255以外の値が出てきた。
256は、ブロック終端を意味している。
ヘッダーのBFINALが1であったので、これ以降に続くブロックもない。
つまり、これで解凍作業が終わったことになる。

カスタムハフマン形式のブロック

カスタムハフマン形式のブロックは、以下のようにデータが並んでいる。

• ヘッダー (3bit)
• HLIT (5bit)
  • 文字/一致長符号の個数
• HDIST (5bit)
  • 距離符号の個数
• HCLEN (4bit)
  • 符号長表の符号長表のサイズ
• 符号長表の符号長表
• 符号化された文字/一致長の符号長表
• 符号化された距離の符号長表
• LZ77で圧縮され、さらにハフマン符号化された圧縮データ

これらを順番に読み解き、圧縮データを頑張って解凍する。

今回は、以下のデータを例として、解凍する。

（データが短い場合、zlibを用いて圧縮すると固定ハフマン形式になってしまうため、参考サイトの例示用データを引用させていただいた。）
https://github.com/cetus-caelestis/deflate_sample02/blob/master/src/main.cpp

15c5411100000001c16c8704fa87315e8b8ac919

分かりやすいように、1バイトずつ、2進数で表したデータも用意した。

00010101 11000101 01000001 00010001 00000000 00000000 00000000 00000001
11000001 01101100 10000111 00000100 11111010 10000111 00110001 01011110
10001011 10001010 11001001 00011001

ヘッダーは、BFINAL=1、BTYPE=10である。

HLIT, HDIST, HCLENの読み取り

数値の格納規則に従って、それぞれ値を読み取る。

ただし、読み取った値と実際の値には差があるので修正を行う。

HLIT  ... 読み取った値(5bit) + 257
HDIST ... 読み取った値(5bit) + 1
HCLEN ... 読み取った値(4bit) + 4

例示用データでは、以下のようになった。

HLIT  = 2 (00010) + 257 = 259
HDIST = 5 (00101) + 1   = 6
HCLEN = 14 (1110) + 4   = 18

符号長表の符号長表の作成

続いて、符号長表の符号長表を作成する。
以下の順番で、符号長の符号長がHCLEN個、格納されている。

16, 17, 18, 0,  8,  7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15

HCLEN<19である場合は、右から19-HCLEN個の符号長の符号長は0、つまり出現しないということになる。

符号長の符号長は、0～7の数字、つまり3bitのデータである。
つまり、HCLEN×3bit、データを読み取ればよい。

16, 17, 18, 0,  8,  7,  9,  6,  10, 5,  11, 4,  12, 3,  13, 2,  14, 1,  15
000 100 010 100 000 000 000 000 000 000 000 000 000 001 000 100 000 100 (無)

符号表の符号長が0、つまり出現しないものを省略して符号長表の符号長表を作成する。

符号長	符号長の符号長
3	1
18	2
0	4
1	4
2	4
17	4

符号長表の符号表の作成

続いて、符号長の符号長から、符号長の符号を導出する。
（このように、ハフマン木ではなく符号長のみを用いる方法をCanonical Huffman Codeというらしい）

以下のように処理を行う。

• 符号長順（今回だと符号長の符号長順）に処理
• 同じ符号長のグループ内では、値が小さいものから符号を割り当てる
• 同じ符号長のグループ内では、前に割り当てた符号を+1したものを割り当てる

その符号長のグループへの割り当てが終わった時は、以下の処理を行い、次の符号長の処理に移る。

• 割り当てを行った場合は、+1して末尾に0を付加
• 行っていない場合は、単に0を付加

この処理を行うことで、符号が瞬時復号可能な特性を持つ。

符号長	符号長の符号長	符号長の符号
3	1	0
18	2	10
0	4	1100
1	4	1101
2	4	1110
17	4	1111

この例での詳しい考え方

表の見出しが分かりにくいため、ここだけ見出しを変更する。

値	符号長	符号
3	1	0
18	2	10
0	4	1100
1	4	1101
2	4	1110
17	4	1111

符号長1を考える。
`3`に対して、符号`0`を割り当てる。

符号長2を考える。
符号長1で割り当てを行ったので、+1して末尾に0を付加する。（この操作で`10`になった）
`18`に対して、符号`10`を割り当てる。

符号長3を考える。
符号長2で割り当てを行ったので、+1して末尾に0を付加する。（この操作で`110`になった）

符号長4を考える。
符号長3で割り当てを行わなかったので、末尾に0を付加する。（この操作で`1100`になった）
一番値が小さい`0`に対して、符号`1100`を割り当てる。
次に値が小さい`1`に対して、+1した、符号`1101`を割り当てる。
次に値が小さい`2`に対して、+1した、符号`1110`を割り当てる。
次に値が小さい`17`に対して、+1した、符号`1111`を割り当てる。

文字/一致長の符号長表の作成

次に、文字/一致長の符号長表を作成する。

文字/一致長の符号表は、固定ハフマンの時にも出てきた、0～285までの値に対するハフマン符号の対照表である。
（ただし、固定ハフマンと違い、カスタムハフマン形式では自分で構築する必要がある。）

データに含まれる、文字/一致長の符号長の個数は、HLITに入っている。
（0～285全てのデータが入っている訳ではなく、最後の方に符号長0が続いている場合は、その部分を省略する）

例では、HLITの値は259なので、0～258までの値に対するハフマン符号の対照表を作成することになる。
（つまり、259～285までの符号長は0ということであり、最後の解凍処理の時に259～285は出てこない）

読み取る符号長の値について、先ほど作成した符号長表の符号表から分かる通り、0～18の値となる。
0～15の値に関しては、そのまま符号長として扱うが、16～18の値に関しては、ランレングス符号化に用いられている。

ランレングス符号化：同じ値が連続している箇所を、いくつ連続しているかのデータに置き換えることで圧縮を行う手法。

• 16: 一つ前に出現した値が3～6回繰り返される
  • 拡張ビットとして2bit読み出し、ベースの値である3と足して値を求める
• 17: 0が3～10回繰り返される
  • 拡張ビットとして3bit読み出し、ベースの値である3と足して値を求める
• 18: 0が11～138回繰り返される
  • 拡張ビットとして7bit読み出し、ベースの値である11と足して値を求める

それでは、例のデータを先ほど作成した符号長表の符号表を用いて読んでいく。

`10` → 18
    拡張ビットを7ビット読み出すと、`0110110`→54
    11 + 54 = 65

つまり、0から65個0が続く、言い換えれば0～64までの符号長は0となる。
続きを読んでいく。

`1110` → 2、65の符号長は2
`0`    → 3、66の符号長は3
`0`    → 3、67の符号長は3
`0`    → 3、68の符号長は3
`10`   → 18
    拡張ビットを7ビット読み出すと、`0000010` → 2
    11 + 2 = 13
    69～81の符号長は0
`0`    → 3、82の符号長は3
`10`   → 18
    拡張ビットを7ビット読み出すと、`1111111` → 127
    11 + 127 = 138
    83～220の符号長は0
`10`   → 18
    拡張ビットを7ビット読み出すと、`0011000` → 24
    11 + 24 = 35
    つまり、221～255の符号長は0
`0`    → 3、256の符号長は3
`1100` → 0、257の符号長は0
`0`    → 3、258の符号長は3

258までの符号長を読むことができたので、ここで終了である。

符号長が0の部分を省略し、符号長順→値順に並べたものが以下である。

値	符号長
65	2
66	3
67	3
68	3
82	3
256	3
258	3

文字/一致長の符号表の作成

符号長表の符号表の作成の時と同じ要領で行う。

値	符号長	符号
65	2	00
66	3	010
67	3	011
68	3	100
82	3	101
256	3	110
258	3	111

この例での詳しい考え方

符号長1を考える。
符号`0`を割り当てるものはない。

符号長2を考える。
符号長1で割り当てを行わなかったので、末尾に0を付加する。（この操作で`00`になった）
`65`に対して、符号`00`を割り当てる。

符号長3を考える。
符号長2で割り当てを行ったので、+1して末尾に0を付加する。（この操作で`010`になった）
一番値が小さい`66`に対して、符号`010`を割り当てる。
次に値が小さい`67`に対して、+1した、符号`011`を割り当てる。
次に値が小さい`68`に対して、+1した、符号`100`を割り当てる。
次に値が小さい`82`に対して、+1した、符号`101`を割り当てる。
次に値が小さい`256`に対して、+1した、符号`110`を割り当てる。
次に値が小さい`258`に対して、+1した、符号`111`を割り当てる。

距離の符号長表の作成

距離の符号表は、固定ハフマンの時にも出てきた、0～31までの値に対するハフマン符号の対照表である。
データに含まれる、距離の符号長の個数は、HDISTに入っている。
（0～31全てのデータが入っている訳ではなく、最後の方に符号長0が続いている場合は、その部分を省略する）

例では、HDISTの値は6なので、0～5までの値に対するハフマン符号の対照表を作成することになる。
（つまり、6～31までの符号長は0ということであり、最後の解凍処理の時に6～31は出てこない）

文字/一致長の符号長表の作成と同じ要領で行う。

それでは、例のデータを先ほど作成した符号長表の符号表を用いて読んでいく。

`1111` → 17
    拡張ビットを3ビット読み出すと、`010`→2
    3 + 2 = 5
    0～4の符号長は0
`1101` → 1、5の符号長は1

5までの符号長を読むことができたので、ここで終了である。

符号長が0の部分を省略し、符号長順→値順に並べたものが以下である。

値	符号長
5	1

距離の符号表の作成

符号長表の符号表の作成の時と同じ要領で行う。

値	符号長	符号
5	1	0

圧縮データの読み出し

ようやく必要なものが揃ったので、圧縮データの読み出しを行う。

使うものは、文字/一致長の符号表

値	符号長	符号
65	2	00
66	3	010
67	3	011
68	3	100
82	3	101
256	3	110
258	3	111

と、距離の符号表である。

値	符号長	符号
5	1	0

固定ハフマンの時と同じ要領で、読み出しを行う。

`00`  → 65 → `0x41` → `A`（`A`）
`010` → 66 → `0x42` → `B`（`AB`）
`101` → 82 → `0x52` → `R`（`ABR`）
`00`  → 65 → `0x41` → `A`（`ABRA`）
`011` → 67 → `0x43` → `C`（`ABRAC`）
`00`  → 65 → `0x41` → `A`（`ABRACA`）
`100` → 68 → `0x44` → `D`（`ABRACAD`）
`111` → 258
    拡張ビット0、一致長4
    距離を読み出すと、`0` → 5
        拡張ビット1、読み取り結果`0`、距離7
        末尾の7バイト前から1バイトずつ、合計4バイトをコピー（`ABRACADABRA`）
`110` → 256
    ブロック末尾、読み取り終了

おまけ：gzipとzlibについて

zlibやgzipの場合、Deflate圧縮のデータに独自のヘッダーやフッターが追加される。

gzipのヘッダー・フッター

ヘッダー

• マジックナンバー (2byte)
  • 0x1f 0x8bで固定
• 圧縮形式 (1byte)
  • 0x08 (Deflate)
• フラグ (1byte)
  • bit0 ... テキストファイルなら1
  • bit1 ... CRC16の領域が存在するなら1
  • bit2 ... 特別領域が存在するなら1
  • bit3 ... ファイル名が存在するなら1
  • bit4 ... コメントが存在するなら1
• 最終更新日時 (4byte)
• 拡張フラグ (1byte)
• OS (1byte)
• 拡張長さ (2byte)
  • フラグのbit2が立っている時のみ
• 拡張領域 (拡張長さbyte)
  • フラグのbit2が立っている時のみ
• ファイル名 (?byte)
  • フラグのbit3が立っている時のみ
  • 0x00が出てきたらそこで終了
• コメント (?byte)
  • フラグのbit4が立っている時のみ
  • 0x00が出てきたらそこで終了
• CRC16 (2byte)
  • フラグのbit1が立っている時のみ

フッター

• CRC32 (3byte)
• 元のファイルサイズ (4byte)

zlibのヘッダー・フッター

ヘッダー

• 圧縮方式＆フラグ (1byte)
• フラグ (1byte)
• 辞書ID (4byte)
  • フラグのbit5が立っている時のみ

フッター

• ADLER32 (4bit)

参考サイト