Koji Arai
JCA02****@nifty*****
2003年 2月 3日 (月) 01:18:28 JST
新井です。 In message "Re: [Lha-users] The Hacking of LHa for UNIX (2nd draft)" on Mon, 03 Feb 2003 00:00:47 +0900 (JST), Koji Arai <JCA02****@nifty*****> wrote: > 新井です。 > > In message "Re: [Lha-users] The Hacking of LHa for UNIX (2nd draft)" > on Sun, 02 Feb 2003 08:32:17 +0900 (JST), > Koji Arai <JCA02****@nifty*****> wrote: > > 新井です。 > > > > 更新しました。 > > さらに頑張ってみました。 新たな事実に気づいたのでもうちょい更新。 Index: Hackinf_of_LHa =================================================================== RCS file: /cvsroot/lha/lha/Hackinf_of_LHa,v retrieving revision 1.9 diff -u -u -r1.9 Hackinf_of_LHa --- Hackinf_of_LHa 2 Feb 2003 15:01:05 -0000 1.9 +++ Hackinf_of_LHa 2 Feb 2003 16:15:52 -0000 @@ -3378,6 +3378,74 @@ い(少なくとも符号化に関してはそのようだ。huf.c を眺めるとどうやら復号 時は left[]、right[]は使われるらしい)。 +さらにふと思い付いた。謎の (C) のコードだが 深さ 17 以上の木が作成され +た場合に木を再構築する処理だということがわかった。最初、len_cnt[] (あ +る深さの葉の数) だけが、操作されていたからよくわからなかったのだ、 + + /* (C) */ + /* adjust len */ + if (cum) { + fprintf(stderr, "17"); + len_cnt[16] -= cum; /* always len_cnt[16] > cum */ + do { + for (i = 15; i > 0; i--) { + if (len_cnt[i]) { + len_cnt[i]--; + len_cnt[i + 1] += 2; + break; + } + } + } while (--cum); + } + +深さ n の葉の数を 1 つ減らして、その下の葉の数を 2 足している。 +これが、cum の数だけ繰り返される。例えば、前にも出た + + : + n /\ .. len_cnt[14] = 0000000000000001 + o /\ .. len_cnt[15] = 0000000000000001 + p /\ .. len_cnt[16] = 0000000000000011 + q r |||||||||||||||| + vvvvvvvvvvvvvvvv + cum = 0000000000000001 + +の例では、最初に len_cnt[16] から cum {1} が引かれ、 + + : + n /\ .. len_cnt[14] = 0000000000000001 + o /\ .. len_cnt[15] = 0000000000000001 + p / .. len_cnt[16] = 0000000000000010 + q + +続いて、深さ 15 より上の葉のある節から 1 つ子を取り、 + + : + n /\ .. len_cnt[14] = 0000000000000001 + /\ .. len_cnt[15] = 0000000000000001 + p / .. len_cnt[16] = 0000000000000010 + q + +下の葉の数(この例では、len_cnt[16])を 2 足している。 + + / \ + n / \ .. len_cnt[14] = 0000000000000001 + /\ /\ .. len_cnt[15] = 0000000000000000 + o r p / .. len_cnt[16] = 0000000000000100 + q + +cum は、この例では 0 になるので、これで木の平滑化は終る。テキストだと +ちょっと見にくいが、そういう処理ということで間違いないだろう。 +lenparm[] の値はこの後の (D) で、この木を元に計算されている。 + +ところで、本当の所は以下のような文字の対応になる(表を作成するときに文 +字コード順になっているため)のだが、結果的に元の木から p を含む節を取り +除き o の位置に挿入する処理になっている。なんだか面白い。 + + / \ + n / \ .. len_cnt[14] = 0000000000000001 + /\ /\ .. len_cnt[15] = 0000000000000000 + o p q r .. len_cnt[16] = 0000000000000100 + # Local Variables: # mode : indented-text # indent-tabs-mode: nil -- 新井康司 (Koji Arai)
Fork