Deflate圧縮を自力で解凍する

## この記事の背景
VRChatというVRSNSのワールド製作ではUdonSharpという言語（C#っぽいやつ）を使うが、残念ながら[DeflateStream](https://learn.microsoft.com/ja-jp/dotnet/api/system.io.compression.deflatestream?view=net-8.0)を使うことができない。
そこで、自前で解凍することを試みた。
（が、UdonSharpの実行速度が遅く、現実的な時間で解凍できなかった。）
この時の試行錯誤の結果、得られた知見を備忘録的に残しておく。

## Deflate圧縮とは
ハフマン符号化とLZ77を組み合わせて圧縮する圧縮アルゴリズム。
- ハフマン符号化
    - よく登場する文字に短いビットを、あまり登場しない文字に長いビットを割り当てる
- LZ77
    - 前に出てきたデータと同じデータが現れたら、その位置と一致長の情報に置き換える


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

https://ja.wikipedia.org/wiki/Deflate

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

## データの形式
基本的に、アドレス順かつ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     |

<details><summary>この例での詳しい考え方</summary>

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

|  値   |    符号長      |    符号     |
| :---: | :-----------: | :---------: |
|   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`を割り当てる。
```

</details>

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

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

文字/一致長の符号表は、固定ハフマンの時にも出てきた、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   |

<details><summary>この例での詳しい考え方</summary>

```
符号長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`を割り当てる。
```

</details>

### 距離の符号長表の作成

距離の符号表は、固定ハフマンの時にも出てきた、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圧縮のデータに独自のヘッダーやフッターが追加される。

<details><summary>gzipのヘッダー・フッター</summary>

### ヘッダー

- マジックナンバー (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)

</details>

<details><summary>zlibのヘッダー・フッター</summary>

### ヘッダー

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

### フッター

- ADLER32 (4bit)

</details>

## 参考サイト

https://datatracker.ietf.org/doc/html/rfc1951

https://darkcrowcorvus.hatenablog.jp/entry/2016/09/23/195644

https://darkcrowcorvus.hatenablog.jp/entry/2016/09/27/222117

https://darkcrowcorvus.hatenablog.jp/entry/2017/01/07/165627

https://qiita.com/ajinadai/items/9c02dc750bc017c93c8f