Koji Arai
JCA02****@nifty*****
2003年 2月 12日 (水) 00:01:43 JST
Fork新井です。
圧縮に関してはこれで終り。
Index: Hackinf_of_LHa
===================================================================
RCS file: /cvsroot/lha/lha/Hackinf_of_LHa,v
retrieving revision 1.12
retrieving revision 1.13
diff -u -u -r1.12 -r1.13
--- Hackinf_of_LHa 8 Feb 2003 20:09:25 -0000 1.12
+++ Hackinf_of_LHa 11 Feb 2003 14:59:29 -0000 1.13
@@ -1,4 +1,4 @@
-$Id: Hackinf_of_LHa,v 1.12 2003/02/08 20:09:25 arai Exp $
+$Id: Hackinf_of_LHa,v 1.13 2003/02/11 14:59:29 arai Exp $
The Hacking of LHa for UNIX (2nd draft)
-------------------------------------------
@@ -3796,13 +3796,13 @@
----------------------------------------------------------------------------
-output_mask 128 64 32 16 8 4 2 1
- +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
-buf | 32 | c1 | c2 | len | off | c3 | c4 | c5 | c6 | c7 |
- +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
- cpos /
- /
- output_pos
+output_mask 128 64 32 16 8 4 2 1
+ +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
+buf | 32 | c1 | c2 | len | off | c3 | c4 | c5 | c6 | c7 |
+ +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
+ cpos /
+ /
+ output_pos
----------------------------------------------------------------------------
@@ -3961,10 +3961,10 @@
値 root だ)。このとき以下のような出力になる。(TBIT{5}, CBIT{9} である)
----------------------------------------------------------------------------
- 5bit
- 5bit 9bit 9bit
- |--|--|----|----|
- +--+--+----+----+
+ TBIT CBIT
+ TBIT CBIT
+ |--|--|----|----| TBIT: 5
+ +--+--+----+----+ CBIT: 9
| 0| 0| 0|root|
+--+--+----+----+
@@ -4230,9 +4230,228 @@
0 20以上 t_freq[2]++
0以外 t_freq[c_len[i]+2]++;
-これがどういう理屈であるかはよくわからないが、とにかく頻度計算を
-行う場合に t_freq[0], t_freq[1], t_freq[2] を特別扱いしている。
+これがどういう理屈であるかはよくわからないが、とにかく頻度計算を行う場
+合に t_freq[0], t_freq[1], t_freq[2] を特別扱いしている。そして、頻度
+計算の対象が c_len[] であることから (B) の処理は、c_len[] に関して
+Huffman 符号化を行う処理のようだ。
+
+そうして、make_tree() で、t_freq[] に関して Huffman 符号表を作成し、
+write_pt_len() で、この符号表(文字の Huffman 符号のビット長 c_len の
+Huffman 符号のビット長) pt_len[] を出力する。
+
+static void
+write_pt_len(n, nbit, i_special)
+ short n;
+ short nbit;
+ short i_special;
+{
+ short i, k;
+
+ while (n > 0 && pt_len[n - 1] == 0)
+ n--;
+ putbits(nbit, n);
+ i = 0;
+ while (i < n) {
+ k = pt_len[i++];
+ if (k <= 6)
+ putbits(3, k);
+ else
+ putbits(k - 3, USHRT_MAX << 1);
+ if (i == i_special) {
+ while (i < 6 && pt_len[i] == 0)
+ i++;
+ putbits(2, i - 3);
+ }
+ }
+}
+
+最初に pt_len[] の要素数を TBIT{5} 出力し、続けて符号 bit 長 pt_len[]
+の要素を出力している。pt_len[] を出力するときは、その値が 6 より大きい
+かどうかで形式を変えて出力している。6 以下であればそのまま 3 bit で出
+力し、7 bit 以上であれば、bit 数で表現するらしい。例えば pt_len[i] ==
+7 なら、1110 となる。最初の 3 bit は必ず 1 になり、最初の形式と区別が
+つくようになっている。
+
+さらに、i_special 番目の pt_len[i] を出力後は、i_special ... 6 の範囲
+で pt_len[i] == 0 が続くことを 2 bit で、表現している。i_special は
+write_pt_len() の 3 番目の引数で、今回の場合は 3 だ。例えば
+pt_len[3..5] がすべて 0 なら pt_len[3] を出力後、i - 3 (= 3) を 2 bit
+出力する。つまり、11 が出力される。このようなことをしている意味はこれ
+またよくわからない。ちょっと複雑なので図示してみた。
+
+----------------------------------------------------------------------------
+< pt_len[] の出力フォーマット >
+
+ 0 TBIT{5}
+ +-------+-----------+-----------+-- --+-----------+
+ | n | pt_len[0] | pt_len[1] | ... pt_len[n-1]|
+ +-------+-----------+-----------+-- --+-----------+
+
+pt_len[i] <= 6 の場合
+
+ 0 3bit
+ +-----+
+ pt_len[i] | | | |
+ +-----+
+
+pt_len[i] >= 7 の場合
+
+ 0 pt_len[i] - 3
+ +----------------+
+ pt_len[i] |1 1 1 1 ... 1 0 |
+ +----------------+
+
+pt_len[i_special] の直後は 2 bit の情報が付加される。この値を x とする
+と、pt_len[i_special .. x + 3] の範囲で 0 が続くことを意味する。
+
+----------------------------------------------------------------------------
+
+最後に、write_c_len() で、符号表 c_len[] と pt_code[] を出力する。
+
+static void
+write_c_len(/*void*/)
+{
+ short i, k, n, count;
+
+ n = NC;
+ while (n > 0 && c_len[n - 1] == 0)
+ n--;
+ putbits(CBIT, n);
+ i = 0;
+ while (i < n) {
+ k = c_len[i++];
+ if (k == 0) {
+ count = 1;
+ while (i < n && c_len[i] == 0) {
+ i++;
+ count++;
+ }
+ if (count <= 2) {
+ for (k = 0; k < count; k++)
+ putcode(pt_len[0], pt_code[0]);
+ }
+ else if (count <= 18) {
+ putcode(pt_len[1], pt_code[1]);
+ putbits(4, count - 3);
+ }
+ else if (count == 19) {
+ putcode(pt_len[0], pt_code[0]);
+ putcode(pt_len[1], pt_code[1]);
+ putbits(4, 15);
+ }
+ else {
+ putcode(pt_len[2], pt_code[2]);
+ putbits(CBIT, count - 20);
+ }
+ }
+ else
+ putcode(pt_len[k + 2], pt_code[k + 2]);
+ }
+}
+
+前に、頻度を数えたときと同様の条件で出力形式が変わっている。処理内容は
+簡単なので、以下の図を示すだけにする(理屈はよくわからない)。
+
+----------------------------------------------------------------------------
+< c_len[] の出力フォーマット >
+
+ 0 CBIT{9}
+ +-------+-----------+-----------+-- --+-----------+
+ | n | c_len[0] | c_len[1] | ... c_len[n-1]|
+ +-------+-----------+-----------+-- --+-----------+
+
+c_len[i] == 0 の場合
+
+ 0 が続く数を count とすると、
+
+ count == 0..2 の場合
+
+ pt_len[0]
+ <---------->
+ +------------+
+ | pt_code[0] |
+ +------------+
+
+ count == 3..18 の場合
+
+ pt_len[1] 4 bit
+ <----------> <------>
+ +------------+-------+
+ | pt_code[1] |count-3|
+ +------------+-------+
+
+ count == 19 の場合
+
+ pt_len[0] pt_len[1] 4 bit
+ <----------> <----------> <------>
+ +------------+------------+-------+
+ | pt_code[0] | pt_code[1] |count-3|
+ +------------+------------+-------+
+
+ count >= 20 の場合
+
+ pt_len[2] CBIT{9}
+ <----------> <------>
+ +------------+--------+
+ | pt_code[2] |count-20|
+ +------------+--------+
+
+c_len[i] != 0 の場合
+
+ pt_len[c_len[i]+2]
+ +-------------------+
+ |pt_code[c_len[i]+2]|
+ +-------------------+
+
+----------------------------------------------------------------------------
+
+こうして、文字の Huffman 符号表は、pt_len[] と pt_code[](pt_code[] は
+つまり c_len[] の Huffman 符号)を出力することで表現される。c_code[] が
+出力されてない思うかもしれないが、おそらく、decode 処理が c_len[] の値
+から計算して求めているのではないかと思われる。これは decode 処理の解読
+で明らかになるだろう。
+
+この後、send_block() は、<off> の Huffman 符号表を出力するのだが、これ
+は、先の pt_len[] の出力フォーマットと同じなので詳細ははしょろう。
+
+まとめると LHA における圧縮ファイルの構造は以下の連続であると言えるよ
+うだ。
+
+----------------------------------------------------------------------------
+LHA ファイルの構造(1 ブロック分)
+
+ +-----------+
+ | blocksize |
+ +-----------+
+ 16bit
+
+ +-----+--------------------+
+ | len | pt_len | c_lenのハフマン符号表
+ +-----+--------------------+
+ 5bit ?? bit
+ TBIT
+
+ +-------+------------------+
+ | len | c_len | 文字と長さのハフマン符号表
+ +-------+------------------+
+ 9bit ?? bit
+ CBIT
+
+ +---------+--------------------+
+ | len | pt_len | 位置のハフマン符号表
+ +---------+--------------------+
+ pbit ?? bit
+ (pbit=14bit(lh4,5) or 16bit(lh6) or 17bit(lh7))
+
+ +---------------------+
+ | 圧縮文 |
+ +---------------------+
+
+----------------------------------------------------------------------------
+ここまでの解読では細部をかなりはしょったが、decode 処理を見ればわかる
+こともあるであろうことを期待している。以降、decode 処理の内容を処理の
+流れを追うことで確認しよう。
# Local Variables:
# mode : indented-text