RFC1951 伸長コードのメモ

今回圧縮形式のX Fileの読み込みコードを制作するにあたり、MSZip圧縮データの 伸長を自作してみました。MSZip圧縮は、RFC1951(Deflate format)のアプリケーション になっているので、元の資料にあたればすんなり作れるとたかをくくっていたのですが、 やってみると案外ハマるポイントが多かったのです。ただ、結果として出来上がったので、 ハマった部分をメモしておこうと、この記事を作成しました。

特にハマったのは、ビットの順序、英語で読んでも日本語訳を読んでも全くわからない。

判った後原文を読むと、『ああ確かに書いてあったね』なのですが、始めて読んだときは意味が判らない 書き方がされているのも事実。そのあたり少し力を入れて解説してみます。

 

RFC1951 Deflate フォーマットについて

大きなデータは最大32Kbyte のブロックに分割されて
格納される（32Kbyte というのは、伸長後のサイズ）

データはビット単位で保存されているので、ビット単位 で読み出す仕様になっている。 ビットの格納順序（読み出し順序）は LSB->MSB （普通に二進数を左から右に読む感覚と違うので注意が必要。）

読み出し順序

Byte 0Byte 1Byte 2
7654 3210 7654 3210 7654 3210

 

これは中身の順番と必ずしも一致しないので要注意。
これはあくまで読み出し順序。

読み取ったデータをどのように解釈するかによって ビットの並び順が違うので要注意。
ハフマン符号以外のデータは、保存する際、 元のデータをLSB->MSBの順で読み取って、
上の表の順序で保存されます。
ハフマン符号は、上位ビットから順に読みだす （ハフマン木の上から見ていく）ようにしないと ビット長が判らないため、MSB->LSB の順で保存されます。

ここで要注意なのが、固定ハフマン木を使ったデコード（後述）。
距離を示すデータは、全ての値が5ビットとなる設定だが、 それらはハフマン符号とは言えないような値なのに、 ビットの並びはハフマン符号扱いになっているのでハマる。

 

各ブロックのヘッダ

ブロックは３種類あって、最初の３ビットで識別される。

まず一つ目のビットは最終ブロックか否かを表す。 （最終ブロックを伸長するまで伸長後のデータサイズは 判らない）

まずはじめの1ビットは、0なら次のブロックあり、1なら そのブロックでデータ終了の意味。

続く2ビットは、ブロックの種類。これを、 LSB->MSBの順序で読み出す。
MSB->LSB
?????101
は最終ブロックで、ブロック種別が、10 だと みなす。

このブロック種別は、

の３種類です。
11 は予約語で、出て来たらエラーです。

 

【00 非圧縮ブロック】

はじめの16ビットに、データの長さ(バイト単位)が格納されています。
続いて、同じく16ビットで、データの長さの１の補数（ビット反転）が入っています。
その後、８ビットずつ、指定された長さのデータが格納されています。

 

【01 固定ハフマン符号化ブロック】

固定のハフマン木を使って、コードを読み取ります。

まず、ハフマン符号を読み取ります。読み取ったハフマン符号を
デコードすると、0～285 の値となります。
ハフマン符号は、上位ビットから先に読みだされます。
この読み取った値は、以下の３ブロックに分けて解釈されます。

範囲 0 ～ 255 : そのまま、１バイトのデータ(Literal)として解釈します。
値　256 : ブロックの末尾を表します。
範囲 257 ～ 285 : データを複製する長さ(Length)を表します。複製元については、次のセクションを参照

長さコード(Length code)

CodeExtra
Bits		Length(s)CodeExtra
Bits		Length(s)CodeExtra
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
 
追加ビット(Extra Bits)があれば、長さコードに続いて読み込みます。
長さは、257 ～ 285 の値で決まる長さの追加ビットのデータに応じて決定します。
追加ビットは、ハフマン符号ではなく、読みだしたビットは、LSB->MSBの順に
解釈されます。

長さを読み取ったら、次に複製元への距離が保存されています。
固定ハフマン符号の場合は、５ビット固定で読み取ります。
５ビット固定なのですが、読み取った５ビットは、ハフマン符号と同様に、MSB->LSB で解釈されます。

適応ハフマン符号化ブロックでは、距離コードも可変長ハフマン符号で記録 されます。

読み取った距離コードは以下の表に応じて、追加ビットを読み込んでから、 使用されます。

距離コード(Distance code)

CodeExtra
Bits		DistCodeExtra
Bits		DistCodeExtra
Bits		Dist
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

距離は、0 ～ 29 の値で決まる長さの追加ビットのデータに応じて決定します。
追加ビットは、ハフマン符号ではなく、読みだしたビットは、LSB->MSBの順に
解釈されます。

 

距離と長さを算出できたら、これからデータを書き込もうとする アドレスから、距離分だけ戻った位置から、長さ分のデータをコピー して次に進みます。

コピー元は前の圧縮ブロックの事もありますので、設計時注意が必要です。

 

固定ハフマン符号一覧

固定ハフマン符号のLiteral / Length コードは以下のデータを使って、 ハフマン木が生成され、デコードされます。

※下の表の二進数と、ハフマン符号が一致しないように見えるかもしれませんが、
上位ビットから先に圧縮データに書き込まれているため、
読みだされるビットを右(LSB)から記載するとこうなります。
よく考えると、長さの定まらない符号を読み取りながら木をたどる都合上、上位ビットから読みだしてもらわないとイカンので、 こうせざるを得ないのです。

ただ、木(Tree)の実装方法は、省メモリ、スピード優先などの事情で いろいろなバリエーションが考えられるますので、ハフマン符号の持たせ方 も必ずしもこうではありません。
（私も検討中）

出力データ長さハフマン符号読みだされる符号
080x030 00001100
180x031 10001100
280x032 01001100
380x033 11001100
480x034 00101100
580x035 10101100
680x036 01101100
780x037 11101100
880x038 00011100
980x039 10011100
1080x03a 01011100
1180x03b 11011100
1280x03c 00111100
1380x03d 10111100
1480x03e 01111100
1580x03f 11111100
1680x040 00000010
1780x041 10000010
1880x042 01000010
1980x043 11000010
2080x044 00100010
2180x045 10100010
2280x046 01100010
2380x047 11100010
2480x048 00010010
2580x049 10010010
2680x04a 01010010
2780x04b 11010010
2880x04c 00110010
2980x04d 10110010
3080x04e 01110010
3180x04f 11110010
3280x050 00001010
3380x051 10001010
3480x052 01001010
3580x053 11001010
3680x054 00101010
3780x055 10101010
3880x056 01101010
3980x057 11101010
4080x058 00011010
4180x059 10011010
4280x05a 01011010
4380x05b 11011010
4480x05c 00111010
4580x05d 10111010
4680x05e 01111010
4780x05f 11111010
4880x060 00000110
4980x061 10000110
5080x062 01000110
5180x063 11000110
5280x064 00100110
5380x065 10100110
5480x066 01100110
5580x067 11100110
5680x068 00010110
5780x069 10010110
5880x06a 01010110
5980x06b 11010110
6080x06c 00110110
6180x06d 10110110
6280x06e 01110110
6380x06f 11110110
6480x070 00001110
6580x071 10001110
6680x072 01001110
6780x073 11001110
6880x074 00101110
6980x075 10101110
7080x076 01101110
7180x077 11101110
7280x078 00011110
7380x079 10011110
7480x07a 01011110
7580x07b 11011110
7680x07c 00111110
7780x07d 10111110
7880x07e 01111110
7980x07f 11111110
8080x080 00000001
8180x081 10000001
8280x082 01000001
8380x083 11000001
8480x084 00100001
8580x085 10100001
8680x086 01100001
8780x087 11100001
8880x088 00010001
8980x089 10010001
9080x08a 01010001
9180x08b 11010001
9280x08c 00110001
9380x08d 10110001
9480x08e 01110001
9580x08f 11110001
9680x090 00001001
9780x091 10001001
9880x092 01001001
9980x093 11001001
10080x094 00101001
10180x095 10101001
10280x096 01101001
10380x097 11101001
10480x098 00011001
10580x099 10011001
10680x09a 01011001
10780x09b 11011001
10880x09c 00111001
10980x09d 10111001
11080x09e 01111001
11180x09f 11111001
11280x0a0 00000101
11380x0a1 10000101
11480x0a2 01000101
11580x0a3 11000101
11680x0a4 00100101
11780x0a5 10100101
11880x0a6 01100101
11980x0a7 11100101
12080x0a8 00010101
12180x0a9 10010101
12280x0aa 01010101
12380x0ab 11010101
12480x0ac 00110101
12580x0ad 10110101
12680x0ae 01110101
12780x0af 11110101
12880x0b0 00001101
12980x0b1 10001101
13080x0b2 01001101
13180x0b3 11001101
13280x0b4 00101101
13380x0b5 10101101
13480x0b6 01101101
13580x0b7 11101101
13680x0b8 00011101
13780x0b9 10011101
13880x0ba 01011101
13980x0bb 11011101
14080x0bc 00111101
14180x0bd 10111101
14280x0be 01111101
14380x0bf 11111101
14490x190 000010011
14590x191 100010011
14690x192 010010011
14790x193 110010011
14890x194 001010011
14990x195 101010011
15090x196 011010011
15190x197 111010011
15290x198 000110011
15390x199 100110011
15490x19a 010110011
15590x19b 110110011
15690x19c 001110011
15790x19d 101110011
15890x19e 011110011
15990x19f 111110011
16090x1a0 000001011
16190x1a1 100001011
16290x1a2 010001011
16390x1a3 110001011
16490x1a4 001001011
16590x1a5 101001011
16690x1a6 011001011
16790x1a7 111001011
16890x1a8 000101011
16990x1a9 100101011
17090x1aa 010101011
17190x1ab 110101011
17290x1ac 001101011
17390x1ad 101101011
17490x1ae 011101011
17590x1af 111101011
17690x1b0 000011011
17790x1b1 100011011
17890x1b2 010011011
17990x1b3 110011011
18090x1b4 001011011
18190x1b5 101011011
18290x1b6 011011011
18390x1b7 111011011
18490x1b8 000111011
18590x1b9 100111011
18690x1ba 010111011
18790x1bb 110111011
18890x1bc 001111011
18990x1bd 101111011
19090x1be 011111011
19190x1bf 111111011
19290x1c0 000000111
19390x1c1 100000111
19490x1c2 010000111
19590x1c3 110000111
19690x1c4 001000111
19790x1c5 101000111
19890x1c6 011000111
19990x1c7 111000111
20090x1c8 000100111
20190x1c9 100100111
20290x1ca 010100111
20390x1cb 110100111
20490x1cc 001100111
20590x1cd 101100111
20690x1ce 011100111
20790x1cf 111100111
20890x1d0 000010111
20990x1d1 100010111
21090x1d2 010010111
21190x1d3 110010111
21290x1d4 001010111
21390x1d5 101010111
21490x1d6 011010111
21590x1d7 111010111
21690x1d8 000110111
21790x1d9 100110111
21890x1da 010110111
21990x1db 110110111
22090x1dc 001110111
22190x1dd 101110111
22290x1de 011110111
22390x1df 111110111
22490x1e0 000001111
22590x1e1 100001111
22690x1e2 010001111
22790x1e3 110001111
22890x1e4 001001111
22990x1e5 101001111
23090x1e6 011001111
23190x1e7 111001111
23290x1e8 000101111
23390x1e9 100101111
23490x1ea 010101111
23590x1eb 110101111
23690x1ec 001101111
23790x1ed 101101111
23890x1ee 011101111
23990x1ef 111101111
24090x1f0 000011111
24190x1f1 100011111
24290x1f2 010011111
24390x1f3 110011111
24490x1f4 001011111
24590x1f5 101011111
24690x1f6 011011111
24790x1f7 111011111
24890x1f8 000111111
24990x1f9 100111111
25090x1fa 010111111
25190x1fb 110111111
25290x1fc 001111111
25390x1fd 101111111
25490x1fe 011111111
25590x1ff 111111111
25670x000 0000000
25770x001 1000000
25870x002 0100000
25970x003 1100000
26070x004 0010000
26170x005 1010000
26270x006 0110000
26370x007 1110000
26470x008 0001000
26570x009 1001000
26670x00a 0101000
26770x00b 1101000
26870x00c 0011000
26970x00d 1011000
27070x00e 0111000
27170x00f 1111000
27270x010 0000100
27370x011 1000100
27470x012 0100100
27570x013 1100100
27670x014 0010100
27770x015 1010100
27870x016 0110100
27970x017 1110100
28080x0c0 00000011
28180x0c1 10000011
28280x0c2 01000011
28380x0c3 11000011
28480x0c4 00100011
28580x0c5 10100011
28680x0c6 01100011
28780x0c7 11100011

 

【10 適応ハフマン符号化ブロック】

前半に格納されているハフマン木を読み取り、 読みとったハフマン木を使って、続く圧縮されたデータを読み取ります。

ハフマン木の読み取り方

最初の14ビットにこれから読み出す木のデータのサイズ（個数）が記録されています。

サイズ名称内容
5 bitsHLITLiteral/Lengthコードの個数 - 257
5 bitsHDISTDistance コードの個数 - 1
4 bitsHLENコード長コードの個数 - 4

コード長コード（範囲：0～18）はハフマン符号としてこの後使用されるのですが、 その準備として、コード長コードそれぞれのビット長が必要になります。 続いて、コード長コードの個数(HLEN+4)分のビット長データが3ビットずつ 格納されます。
コード長データは、0のコードから順には決まらず、以下の順序になっています。

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

ここまでのデータはハフマン符号ではないため、読みだしたビット列は 読みだした順に、LSB->MSBの順で解釈されます。

ビット長が与えられなかったコード長コードのビット数は０と解釈します。

この0～18の数値は単純にビット長とせず、以下のように解釈します。

コード長コードの解釈

0-15単純にビット長として解釈
16一つ前のコードのビット長を3～6回繰り返す、繰り返し回数は、
次の2ビットを読みだして、3を足す事で求める
170を、3～10回繰り返す。繰り返し回数は次の3ビットを読み出し、 3を足す事で求める。
180を、11～138回繰り返す。繰り返し回数は次の7ビットを読み出し、 11を足す事で求める。


コード長コードそれぞれのビット数が決まったら、それを基に、コード長コードの ハフマン符号およびハフマン木を生成します。

19個のハフマン符号を生成するプログラムは以下のようになります。
プログラム中に出てくるcodeLengthsOfTheCodeLengths には、各コード長コードの ビット長が入っているものとします。これはHLENに続いて読み込まれたデータです。

    //  Given : codeLengthsOfTheCodeLengths
    int *bitLengths = new int[19];
    int *nextCodes  = new int[19];
    HuffmanCode    node[19];  //  members: WORD length; WORD code;
    int maxBits = -1;
    memset((VOID*)bitLengths,0,sizeof(int)*19);
    memset((VOID*)nextCodes,0,sizeof(int)*19);
    memset((VOID*)node,0,sizeof(node));
    for (int i = 0; i <= 18 ; ++i){
        int len = codeLengthsOfTheCodeLength[i];
        node[i].length = len;
        bitLengths[len]++;
        if (maxBits < len)
            maxBits = len;
    }
    int code = 0;
    bitLengths[0] = 0;
    for (int bits = 1; bits <= 18; bits++) {
        code = (code + bitLengths[bits-1]) << 1;
        nextCodes[bits] = code;
    }

    for (int n = 0; n <= 18 ; n++) {
        int len = node[n].length;
        if (len != 0) {
            node[n].code = binreverse(nextCodes[len],len);
            nextCodes[len]++;
        }
    }
続いて格納されるのは、HLIT+257個の、Literal / Length コードのビットです。
これらは、先ほどのコード長コードで表されハフマン符号で記録されていますので、 先程生成したハフマン木を使って、デコードします。

これで、HLIT+257個のコードそれぞれのビット長が決まりましたので、Literal/Length コードについて、ハフマン符号およびハフマン木を生成することができます。

その後は、HDIST+1個のDistance コードのビット長です。
これも先ほどのコード長コードで表されます。
これで、HDIST+1個のコードすべてのビット長が決まりましたので、Distance コード について、ハフマン符号およびハフマン木を生成する事ができます。

あとは、固定ハフマン符号化ブロックと同様にハフマン符号化された データが格納されます。もちろん256で終了です。

違いは、固定ハフマン符号ではなく、Literal/Length コードは先ほど作った、 Literal/Lengthコードのハフマン木を用いてデコードし、Distance コードも、 先程作った、Distanceコードのハフマン木を用いてデコードすることです。