PNG イメージを自力でパースしてみる～3/6 カスタムハフマン編～

ここまでのあらすじ

PNG イメージを自力でパースしてみる～1/6 予備知識編～
PNG イメージを自力でパースしてみる～2/6 Deflateの基本と固定ハフマン編～

ここでは Deflateのカスタムハフマンについてを解説

カスタムハフマン符号化 (BTYPE:10)
- 圧縮
- 解凍
サンプル
参考にしたサイトさん

カスタムハフマン符号化 (BTYPE:10)

Deflate で定義されている圧縮タイプのうちの一つ

個人的にここのブロックの圧縮ルールが結構ややこしかった。
まずはどんなふうに圧縮されているかを見てから復号の解説を行いたいと思う

圧縮

カスタムハフマンのブロックは、以下の手順で作成される (たぶん)

Deflateの LZ77 でデータ圧縮
カノニカル・ハフマン符号化
符号長表を符号化
配置

符号長表を符号化とかいうパッと見なんかよくわからないことをしていらっしゃるけど、まずは一番上から順を追って解説してみる

1. Deflateの LZ77 でデータ圧縮

Deflate仕様の LZ77 で元データを圧縮する。
実際の圧縮方法については、これのひとつ前の記事で解説した

この結果、"文字" または "一致した長さ" (それと終端符号) は 0 ～ 285 (+拡張ビット)
"距離" は 0 ～ 29 (+拡張ビット) のかたちになって出力される

f:id:DarkCrowCorvus:20170105224856j:plain

2. カノニカル・ハフマン符号化

LZ77で置換された各値の出現回数を調べる
各値に対する符号の長さを求め、符号長表を作成する
得られた符号長表から、カノニカル・ハフマンを使って符号表を作成する。
得られた符号表を使って、LZ77符号化されたデータをさらに符号化する

カノニカル・ハフマンについては、これのふたつ前の記事で解説した。これによって、圧縮後のデータに符号長表だけを収めれば、符号表と元データを間違いなく復元できる。

符号の長さを求めるときにひとつ注意するべきことがある。Deflateのカスタムハフマンで扱うハフマン符号は、仕様によりその符号長が 15 以下にならなければならない

一応、長さの制限されたハフマン符号を作成する方法がきちんとあるらしい。長くなるためこっちの記事で解説することにする

なお、文字/一致した長さの値 (0～285) の出現回数と、距離の値 (0～29) の出現回数の 2つは、それぞれ別々に統計され、それぞれ別々の符号表として作成される。

また、LZ77符号化されたデータは、その中に現れる値が文字/一致した長さの値か、距離の値かによって、その都度2つの異なる符号表を使って符号化される。

f:id:DarkCrowCorvus:20170105224953j:plain

3. 符号長表を符号化

直前の手続きによって得られた 2つの符号長表は、表中の "符号長" を表す値の偏り具合によって、それ自体、一度ハフマン符号化される

まず、2つの符号長表は、値の昇順に連続して連なるリスト構造に展開されているものとする。このうち、本来出現しない値に対しては符号長：0 が充てられる。

f:id:DarkCrowCorvus:20170106201614j:plain

符号長表中の圧縮データ化される範囲は「可変」である。

文字/一致した長さの符号長表 の場合、利用されている一番大きな一致した長さの値に合わせて、0から最小で256(257個)、最大で285(286個) までの範囲の符号長を対象とする。

距離の符号長表 については、最小で0のみ(1個)、最大で0～31(32個) までの範囲の符号長を対象とする。こちらも利用されている距離の最大値によって、圧縮データ中に含める範囲が変化する。

この2つの表中の圧縮範囲に対しては、次の２つの圧縮が施される

3.1 ランレングス符号化

表中の符号長の値を連ねたとき、同じ値が連続する箇所があれば、それをいくつ連続したかを表す数のデータに置き換えることで圧縮を行う。
このアプローチは通常、ランレングス符号化 と呼ばれる

Deflate仕様のランレングス符号化では、符号長表の圧縮範囲の値が連続する場所に対して、以下の通りに置き換えを行うものとしている

・ひとつ前に出現した値が 3 ～ 6 回繰り返される	16 ( 拡張ビット：2 )
・"０" が 3 ～10 回繰り返される	17 ( 拡張ビット：3 )
・"０" が 11 ～ 138 回繰り返される	18 ( 拡張ビット：7 )

f:id:DarkCrowCorvus:20170107163645j:plain

拡張ビットには、"どれだけ連続するか" を調整する値が設定され、
ベース値 + 拡張ビットによって本来の連続した長さを求められるようになっている

3.2 カノニカル・ハフマン符号化

ランレングス符号化が終わった2つの符号長表に対して、その表中の値の出現回数を調べ、符号長表を作成し、それから符号表を作成し、それから符号化を行う。

f:id:DarkCrowCorvus:20170107163725j:plain

値の出現回数は、表2つを合わせて集計される。

各値の出現回数が分かれば、次にその各値に対する符号長を求める。
ここでも求める符号長の、その長さに注意すること。LZ77符号化済みデータに対する符号長制限が 15以下だったのに対し、こちらでは 7以下になっていなければならない

得られた各値に対する符号長から 符号長表の符号長表 を作成すれば、あとはそれから、符号表を作成し、2つの符号長表を圧縮する。

f:id:DarkCrowCorvus:20170107163737j:plain

ここまでの手続きで、ひとまずカスタムハフマンブロックに含む各データの符号化が完了する

4. 配置

最終的にカスタムハフマンブロック中には、以下の要素が順番に整列することになる

ヘッダー情報 (前回の記事で紹介済み)
HLIT：文字/一致長符号の個数 (５ビット)
HDIST：距離符号の個数 (５ビット)
HCLEN：符号長表の符号長表のサイズ (４ビット)
符号長表の符号長表
符号化された文字/一致長の符号長表
符号化された距離の符号長表
圧縮データ

2. HLIT：文字/一致長符号の個数
HLIT ...header literalの略？

ここには、文字/一致長の符号長表に含めた符号長の個数 (257 ～ 286) を表す値が設定される。実際には個数 -257 した 0 ～ 29 までの範囲の値が５ビット長の中に収められる

3. HDIST：距離符号の個数
HDIST ...header distanceの略？

ここには、距離符号長表に含めた符号長の個数 (1 ～ 32) を表す値が設定される。実際には個数 -1 した 0 ～ 31 までの範囲の値が５ビット長の中に収められる

4. HCLEN：符号長表の符号長表のサイズ
HCLEN ...header code lengthの略？

ここにはカスタムハフマンブロックに収められる符号長表の符号長表に、符号長がいくつ含まれているか (～19) を表す値が設定される。実際には個数 -4 した 0 ～ 15 までの範囲の値が４ビット長の中に収められる

5. 符号長表の符号長表

符号長表の符号長表は、カスタムハフマンブロックに対して、以下のような変則的な並びになった状態で記録される。

各符号長値 (0～7) は、それぞれ３ビット長の中に収められる。
また、このうち本来出現しない値に対しては、符号長：０が充てられる

この並びの中に各符号長を収めた時、最後尾「15」の符号長が０で、なおかつそこから先頭方向に連続して０が続く場合、カスタムハフマンブロックに並びを収めるとき、その０が続く部分を省略することができる。

ただし省略できる符号長は15個まで。
並びの中の符号長の個数は 4未満にはならない

f:id:DarkCrowCorvus:20170107144210j:plain

この結果、並びの中に残った符号長の個数 -4 した値が、
前述の HCLEN に実際に設定される数になる。

それ以降にようやく

6. 符号化された文字/一致長の符号長表
7. 符号化された距離の符号長表
8. 圧縮データ

のデータが順番に現れるようになっている

解凍

上で説明した構築の手順を逆にたどれば、カスタムハフマンブロックの解凍が行える

ヘッダー情報を読み出す(前回の記事で紹介済み)
HLIT (5ビット) 、HDIST (5ビット) 、HCLEN (4ビット) をそれぞれ読み出す。
HCLEN + 4 によって並びの中の符号長の数がわかれば、後に続く符号長(3ビット) をその数だけ読み出し、本来の符号長表の符号長表を復元する
符号長表の符号長表から、符号長表の符号表を作成する。
HLIT + 257 によって、このブロックに含まれている文字/一致長の符号長値の数がわかれば、先ほど作成した符号長表の符号表を使って、その数だけの符号長を読み出して復号し、本来の文字/一致長の符号長表を復元する
HDIST + 1 によって、このブロックに含まれている距離の符号長値の数がわかれば、同じく符号長表の符号表を使って、その数だけの符号長を読み出して復号し、本来の距離の符号長表を復元する
復元した2つの符号長表から文字/一致長の符号表と、距離の符号表をそれぞれ作成する
作成した2つの符号表を使って、残りの圧縮データを読み出して復号する