更新が必要な人

今回は Inflate のアルゴリズム部分のバグ修正となるので、過去のバージョンで Inflate を利用している方は更新する必要があります。

バグ詳細

このコミットの解説となります。

Deflate では、リテラルと長さ・距離符号(LZSS)をハフマン符号化して圧縮します。
ハフマン符号も辞書をそのまま格納するのではなく、符号の長さだけを格納することで更なるサイズ節約を行っています。
さらに、符号の長さもランレングス符号化を行って格納されます。

リテラルと長さ符号、距離符号は別々にハフマン符号化し、それぞれ RFC1951 では HLIT, HDIST と呼ばれています。
このように、別々の辞書を使ってハフマン符号化されるため、ランレングス符号化もそれぞれ別のコンテキストで行われるものだとおもっていたのですが、
どうやら、HLIT と HDIST を連続したものと扱いランレングス符号化するのが正しかったようです。

issue#29 の例でいうと、HLIT の符号長が

[..., 5, 3, 5, 6, 6, 4, 5, 7, 8, 8, 7]

となっていて、HDIST は以下のようになっていました。

[16, 16, 4, 7, 3, 7, 6, 7, 7, 6, 6, 6, 5, 6, 5, 4, 4, 4, 3, 4, 3, 4]

HDIST の 16 という値は「前の値を複数回コピーする」というもので、修正前の実装では初期値である 0 をコピーしてしまっていました。
これを今回の修正で、HLIT の最後の値である 7 をコピーすることで正常に展開することができるようになりました。
今までのテストで見つかっていなかったのが不思議ですが、あまり頻繁にあるケースではないのかもしれません。