Simple zlib Decompression

概要

zlibフォーマットを自力で伸張するライブラリszlib(Github)を作成しました.
できるプログラマはこのようなものを簡単に作ると思いますが, 私は大変苦労したため,
ノートを残しておこうと思います.
Githubにコードは置きました.

zlib

仕様RFC1950ではヘッダとAdler-32チェックサムが定義されているだけなので, 特に難しくありません.
|zlibヘッダ|Deflateで圧縮されたデータ|Adler-32|
とデータが並んでいます.

Deflate

Deflate形式では, データをビット単位で扱います.
多数のビットを読み込む場合, ビットの並びは,
ハフマン符号の場合はビッグエンディアンのように上位ビットから,
それ以外は下位ビットから読み込みます.
仕様RFC1951の3.2.3.の疑似コードを参考に以下のような外枠を作ります.
ブロックヘッダは3bitで, ブロックタイプ(2bits)と終了ブロックフラグ(1bit)からなります.

do
    ブロックヘッダを読み込む(3bits)
    if 非圧縮ブロック
        非圧縮ブロックを読み込む
    else if 固定ハフマンブロック
        固定ハフマンブロックを読み込む
    else if カスタムハフマンブロック
        カスタムハフマンブロックを読み込む
    endif
while 終了ブロックでない

非圧縮ブロック

非圧縮ブロックはバイト境界から始まります. ブロックヘッダの終わりから次のバイト境界まで無視します.
次に, ブロックのバイト長さが|LEN(2bytes)|NLEN(2bytes)|のように続きます. NLENはLENのビット反転です.
その次にLENバイトのデータが続きます. zlibでは, 圧縮levelを0にすれば非圧縮ブロックのみになるようです.

固定ハフマンブロック

仕様RFC1951の3.2.5.にあるとおり, 固定のハフマンツリーで出コードします.
出力バッファはオフセット32KB + 長さ258Bで十分でしょうか. <オフセット, 長さ>から出力する場合は,
出力バッファから出力バッファと出力へコピーしていけばよいです.
zlibでは, strategyにZ_FIXEDを指定すればよいようです.

loop
    ハフマンコードを読む
    if ハフマンコード == 終端コード(256)
        終了
    else if ハフマンコード <= 255
        ハフマンコード値を出力
    else if 257 <= ハフマンコード
        LZSSのための<オフセット, 長さ>の組をデコード
        <オフセット, 長さ>から出力
    endif
end loop

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

ハフマンコードのデコードテーブルが始めに存在します.
デコード処理は, 固定ハフマンブロックと同じです.
用語が乱立してわかりにくかったのですが, Canonical Huffmanでエンコードされています.

//Canonical Huffman: ハフマンコードの長さから, ハフマンコードをデコードする
//長さの出現数を数える
for(sz_s32 i = 0; i<=maxBits; ++i){
    bl_count[i] = 0;
}
for(sz_s16 i = 0; <length; ++i){
    SZ_ASSERT(hclens[i].length_<=maxBits);
    ++bl_count[hclens[i].length_];
}

//ハフマンコードに変換, 長さ0は出現しないコード
sz_s16 code = 0;
bl_count[0] = 0;
for(sz_s32 bits = 1; bits<=maxBits; ++bits){
    code = (code + bl_count[bits-1])<<1;
    next_code[bits] = code;
}
for(sz_s16 i = 0; i<length; ++i){
    sz_s16 len = hclens[i].length_;
    if(0 != len){
        hclens[i].code_ = next_code[len];
        hclens[i].length_ = len;
        ++next_code[len];
    } else{
        hclens[i].code_ = -1;
    }
}

参照

• RFC1951
• RFC1951(日本語訳)
• 七誌の開発日記（旧）カスタムハフマン符号