The Hacking of LHa for UNIX (2nd draft)
-------------------------------------------
- Koji Arai <mailto:jca02266@nifty.ne.jp>
+ Koji Arai <mailto:jca02266@nifty.com>
Ëܽñ¤Ï¡¢LHa for UNIX 1.14i ¤Î¥½¡¼¥¹¤ò²òÆɤ·¡¢¤½¤Î°µ½Ì¥¢¥ë¥´¥ê¥º¥à¤Î¼Â
Áõ¤ò³Îǧ¤¹¤ë¤¿¤á¤Î¤â¤Î¤À¡£¤³¤ÎÀ®²Ì¤ÏÊ̤ηÁ¤Ç¤Þ¤È¤á¤Ê¤ª¤µ¤ì»ñÎÁ¤Ë¤Ê¤ë¤«
}
¤½¤ì¤¾¤ì bit ÆþÎÏ¡¢bit ½ÐÎϤò¹Ô¤¦¤¿¤á¤Î½é´ü²½½èÍý¤À¡£CHAR_BIT ¤È¤¤¤¦¤Î
-¤Ï 8 ¤Ç¡¢char ¤Î bit ¥µ¥¤¥º¤òɽ¤·¤Æ¤¤¤ë¤é¤·¤¤¡£¾ÜºÙ¤Ï¤ï¤«¤é¤Ê¤¤¤¬½é´ü
+¤Ï 8 ¤Ç¡¢char ·¿¤Î bit ¥µ¥¤¥º¤òɽ¤·¤Æ¤¤¤ë¤é¤·¤¤¡£¾ÜºÙ¤Ï¤ï¤«¤é¤Ê¤¤¤¬½é´ü
¾õÂ֤ϤȤˤ«¤¯¤³¤ì¤À¡£¤³¤³¤Ç»ÈÍѤµ¤ì¤Æ¤¤¤ëÊÑ¿ô¤Ï¡¢
static unsigned char subbitbuf, bitcount;
(B) ¤Ç¡¢subbitbuf ¤Ë»Ä¤Ã¤Æ¤¤¤ë bit ¤ò bitbuf ¤Ë¤º¤é¤·¤Æ¤¤¤ë¡£º£¤Ï¤Þ¤À
¶õ¤Ê¤Î¤Çbitbuf ¤Ï¤³¤³¤Ç¤â¤Þ¤À¶õ¤À¡£
-(C) ¤Ç¡¢8 ¥Ó¥Ã¥È¥Õ¥¡¥¤¥ë¤«¤é¥Ç¡¼¥¿¤òÆɤà(compsize ¤Ï¾ï¤Ë0¤Ç¤Ê¤¤¤È¹Í¤¨
+(C) ¤Ç¡¢¥Õ¥¡¥¤¥ë¤«¤é¥Ç¡¼¥¿¤ò8 ¥Ó¥Ã¥ÈÆɤà(compsize ¤Ï¾ï¤Ë0¤Ç¤Ï¤Ê¤¤¤È¹Í¤¨
¤ë)¡£bitcount ¤Ï 8 ¤Ë¤Ê¤ë¡£¤³¤Î»þÅÀ¤Ç bit¥Ð¥Ã¥Õ¥¡Á´ÂÎ¤Ï subbitbuf ¤À¤±
Ãͤ¬Æþ¤Ã¤¿¾õÂ֤ˤʤ롣
¤¦¡£½èÍýÆâÍƤò³Îǧ¤·¤Æ¤ß¤ì¤Ð¤ï¤«¤ë¡£
¤³¤³¤Ç¡¢subbitbuf ¤ÎÍÑÅӤ˵¤¤Å¤¤¤¿¡£¥Õ¥¡¥¤¥ë¤«¤é¤ÎÆɤ߹þ¤ß¤¬ 8 ¥Ó¥Ã¥È
-ñ°Ì¤Ç¤·¤«¤Ç¤¤Ê¤¤¤Î¤Ç¡¢¤½¤ì¤òÊ䤦¤¿¤á¤ÎÀèÆɤߥХåե¡¤Ç¤¢¤í¤¦¡£Î㤨¤Ð
+ñ°Ì¤Ç¤·¤«¤Ç¤¤Ê¤¤¤Î¤Ç¡¢¤½¤ì¤òÊ䤦¤¿¤á¤ÎÊݸÍѥХåե¡¤Ç¤¢¤í¤¦¡£Î㤨¤Ð
1 ¥Ó¥Ã¥È¤À¤± bitbuf ¤ò fill ¤·¤¿¤±¤ì¤Ð subbitbuf ¤Ë 7 bit »Ä¤·¡¢1 bit
¤À¤± bitbuf ¤ËÀßÄꤵ¤ì¤ë(³Îǧ¤·¤Æ¤ß¤ì¤Ð¤ï¤«¤ë)
¤³¤Î¥Æ¥¥¹¥È¤Ï 9 ¥Ð¥¤¥È¤¢¤ë¤ï¤±¤À¤¬¡¢¤³¤Î¥Õ¥¡¥¤¥ë¤Ç»È¤ï¤ì¤Æ¤¤¤ëʸ»ú¤Ï3
¼ïÎष¤«¤Ê¤¤¡¢a, b, c ¤À¡£¤À¤«¤é¤³¤Î¥Õ¥¡¥¤¥ë¤À¤±¤Ë´Ø¤·¤Æ¸À¤¨¤Ð 1 ʸ»ú
-¤Ï 2 ¥Ó¥Ã¥È¤¢¤ì¤Ðɽ¸½²Äǽ¤Ç¤¢¤ë(¤³¤Î¥Õ¥¡¥¤¥ë¤Î¾ì¹çÁ´ÂΤǡ¢18¥Ó¥Ã¥È¤¢¤ì
-¤Ðɽ¸½²Äǽ)¡£¤µ¤é¤Ë¡¢½Ð¸½ÉÑÅ٤ι⤤ʸ»ú¤ò¾¯¤Ê¤¤¥Ó¥Ã¥È¿ô¤Çɽ¸½¤·¡¢¤Þ¤ì
-¤Ë¤·¤«¸½¤ì¤Ê¤¤Ê¸»ú¤òŤ¤¥Ó¥Ã¥È¿ô¤Çɽ¤¹¤è¤¦¤Ë¤¹¤ì¤Ð¤è¤ê¥Ó¥Ã¥È¿ô¤ò¾¯¤Ê¤¯
-¤Ç¤¤ë¡£Î㤨¤Ð
+¤Ï 2 ¥Ó¥Ã¥È¤¢¤ì¤Ðɽ¸½²Äǽ¤Ç¤¢¤ë¡£Î㤨¤Ð³Æʸ»ú¤ËÂФ·¤Æ°Ê²¼¤Î¥Ó¥Ã¥È¤ò
+³ä¤êÅö¤Æ¤¿¤È¤¹¤ë¤È
+
+ ʸ»ú ¥Ó¥Ã¥Èɽ¸½
+ a 00
+ b 01
+ c 10
+
+Àè¤Î¥Æ¥¥¹¥È¥Õ¥¡¥¤¥ë¤ÎÆâÍÆ abcabcaba ¤Ï¡¢18¥Ó¥Ã¥È¤¢¤ì¤Ðɽ¸½²Äǽ¤È¤Ê¤ë¡£
+
+¤µ¤é¤Ë¡¢½Ð¸½ÉÑÅ٤ι⤤ʸ»ú¤ò¾¯¤Ê¤¤¥Ó¥Ã¥È¿ô¤Çɽ¸½¤·¡¢¤Þ¤ì¤Ë¤·¤«¸½¤ì¤Ê¤¤
+ʸ»ú¤òŤ¤¥Ó¥Ã¥È¿ô¤Çɽ¤¹¤è¤¦¤Ë¤¹¤ì¤Ð¤è¤ê¥Ó¥Ã¥È¿ô¤ò¾¯¤Ê¤¯¤Ç¤¤ë¡£Î㤨¤Ð
ʸ»ú ¥Ó¥Ã¥Èɽ¸½
a 0
¤òµá¤á¤Æ¤ª¤¯É¬Íפ¬¤¢¤ê¡¢Éü¹æ²½¤ÎºÝ¤Ï¤É¤Î¥Ó¥Ã¥ÈÎ󤬤ɤÎʸ»ú¤ËÂбþ¤¹¤ë¤«
¤ò¤¢¤é¤«¤¸¤áÃΤëɬÍפ¬¤¢¤ë¡£
-¤Ç¤Ï¡¢Éä¹æ²½¤ÎºÝ¤Ëʸ»ú¤ËÂбþ¤¹¤ë¥Ó¥Ã¥ÈÎó¤òµá¤á¤ëÊýË¡¤À¤¬¡¢°Ê²¼¤¬¤½¤Î¥¢
-¥ë¥´¥ê¥º¥à¤À¡£¥Ï¥Õ¥Þ¥óË¡¤Ç¤Ï¥Ï¥Õ¥Þ¥óÌڤȤ¤¤¦ÌÚ¹½Â¤¤ò¹½ÃÛ¤¹¤ë¡£³Æʸ»ú¤Î
-½Ð¸½²ó¿ô
+ʸ»úËè¤Ë¥Ó¥Ã¥ÈĹ¤Î¤Ð¤é¤Ä¤¤¬¤¢¤ë¤è¤¦¤Ê²ÄÊÑĹÉä¹æ¤Ë¤Ï°Ê²¼¤Î¾ò·ï¤¬¤¢¤ë¡£
+
+ ¤¢¤ëÉä¹æ¤Î¥Ó¥Ã¥È¥Ñ¥¿¡¼¥ó¤Ï¡¢Â¾¤ÎÉä¹æ¤Î¥Ó¥Ã¥È¥Ñ¥¿¡¼¥ó¤Î³«»Ï¤Ë¤Ï¤Ê¤é
+ ¤Ê¤¤¡£
+
+¤È¤¤¤¦¤â¤Î¤À¡£¤³¤ì¤ò¡Ö¸ìƬ¾ò·ï¡×¤È¸À¤¦¤é¤·¤¤¡£Î㤨¤Ð¡¢Àè¤ÎÎã¤Ç¤Ï a ¤Ë
+0 ¤ò³ä¤êÅö¤Æ¤¿¤Î¤Ç¾¤Îʸ»ú¤Ïɬ¤º 1 ¤«¤é»Ï¤Þ¤ë¤è¤¦¤Ë¤Ê¤Ã¤Æ¤¤¤ë¡£¤³¤Î¾ò
+·ï¤òËþ¤¿¤µ¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤Íýͳ¤Ï¤Á¤ç¤Ã¤È¹Í¤¨¤ì¤Ð¤ï¤«¤ë¡£²¾¤Ë°Ê²¼¤Î´Ö°ã¤Ã
+¤¿³äÅö¤ò¹Ô¤Ã¤¿¤È¤¹¤ë¡£
+
+ ʸ»ú ¥Ó¥Ã¥Èɽ¸½
+ a 0
+ b 10
+ c 01
+
+¤³¤ì¤À¤È¡¢¥Ó¥Ã¥È¥Ñ¥¿¡¼¥ó 010 ¤¬ ab ¤Ê¤Î¤« ca ¤Ê¤Î¤«Û£Ëæ¤Ë¤Ê¤ë¤Î¤¬¤ï¤«
+¤ë¤À¤í¤¦¡£
+
+ʸ»ú¤ËÂбþ¤¹¤ë¸ìƬ¾ò·ï¤òËþ¤¿¤¹(ºÇŬ¤Ê)¥Ó¥Ã¥ÈÎó¤òµá¤á¤ëÊýË¡¡¢¤½¤ì¤¬¥Ï¥Õ
+¥Þ¥óË¡¤À¡£¥Ï¥Õ¥Þ¥óË¡¤Ç¤Ï¥Ï¥Õ¥Þ¥óÌڤȤ¤¤¦ÌÚ¹½Â¤¤ò¹½ÃÛ¤¹¤ë¤Î¤À¤¬¡¢¤½¤Î¥¢
+¥ë¥´¥ê¥º¥à¤Ï°Ê²¼¤Î¤È¤ª¤ê¤À¡£
- a:4¡¢b:3¡¢c:2
+¤Þ¤º¡¢°µ½ÌÂоݤǤ¢¤ë¥Æ¥¥¹¥È¤Ë´Ø¤·¤Æ³Æʸ»ú¤Î½Ð¸½²ó¿ô¤ò¿ô¤¨¤ë¡£Î㤨¤Ð
+abcabcaba ¤È¤¤¤¦¥Æ¥¥¹¥È¤Ç¤Ï¡¢a ¤Ï 4²ó¡¢b¤Ï3²ó¡¢c¤Ï2²ó¤Ê¤Î¤Ç¡¢
-¤«¤é¡¢½Ð¸½²ó¿ô¤ÎÄ㤤¤â¤ÎƱ»Î¤ò°ì¤Ä¤ÎÀá¤Ë«¤Í¤ë¡£¤³¤ÎÀá¤Ï 3+2=5 ¤È¤¤¤¦
-½Ð¸½²ó¿ô¤ò»ý¤Ä¤â¤Î¤È¹Í¤¨¤ë¡£
+ 4 3 2
+ | | |
+ a b c
- 5
- / \
- b c
+¤È¤Ê¤ë¡£¼¡¤Ë¡¢½Ð¸½²ó¿ô¤ÎÄ㤤¤â¤ÎƱ»Î¤ò°ì¤Ä¤ÎÀá¤Ë«¤Í¤ë¡£¤³¤ÎÀá¤Ï 3+2=5
+¤È¤¤¤¦½Ð¸½²ó¿ô¤ò»ý¤Ä¤â¤Î¤È¹Í¤¨¤ë¡£
+
+ 4 5
+ | / \
+ a b c
°Ê¹ß¤µ¤é¤Ë½Ð¸½²ó¿ô¤ÎÄ㤤¤â¤ÎƱ»Î¤ò°ì¤Ä¤ÎÀá¤Ë«¤Í¤ëÁàºî¤ò·«¤êÊÖ¤¹¡£¤³¤Î
Îã¤Ç¤Ï¡¢¤â¤¦°ìÅÙ«¤Í¤ì¤Ð½ª¤ê¤À¡£
- /\
- / \
- / / \
- a b c
+ 9
+ /\
+ / \
+ / / \
+ a b c
¤³¤³¤Ç¡¢Ìڤκ¸Â¦¤¬ 0 ±¦Â¦¤¬ 1 ¤Ç¤¢¤ë¤È¤¹¤ë¤È¡£a ¤Ïº¬¤«¤éº¸¤Ë1¤Ä¿Ê¤à¤À
¤±¤Ê¤Î¤Ç 0¡£b ¤Ï¡¢±¦(1)¢ªº¸(0) ¤Ê¤Î¤Ç¡¢10¡£c ¤Ï±¦(1)¢ª±¦(1) ¤Ê¤Î¤Ç¡¢11
¤È¤Ê¤ë¡£¼ÂºÝ¤ÎÉä¹æ²½¤ÎºÝ¤Ïʸ»ú¤«¤é¥Ó¥Ã¥ÈÎó¤òµá¤á¤ë¤Î¤ÇÍÕ¤«¤éº¬¤Ë¤à¤«¤Ã
¤ÆµÕ½ç¤Ëé¤ë¤³¤È¤Ë¤Ê¤ë¡£¤Þ¤¿¡¢Éü¹æ¤ÎºÝ¤ÏÆþÎϤΥӥåÈÎó¤Ë±è¤Ã¤Æ¤³¤ÎÌÚ¤ò
-é¤ë¤³¤È¤ÇÂбþ¤¹¤ëʸ»ú¤òµá¤á¤ë(¤Ê¤Î¤Ç°µ½Ìʸ¤Ë¤Ï¤³¤ÎÌÚ¹½Â¤¤¬°ì½ï¤Ë¾ðÊó
-¤È¤·¤Æ³ÊǼ¤µ¤ì¤ë¤³¤È¤Ë¤Ê¤ë)¡£
+º¬¤«¤éé¤ë¤³¤È¤ÇÂбþ¤¹¤ëʸ»ú¤òµá¤á¤ë(¤Ê¤Î¤Ç°µ½Ìʸ¤Ë¤Ï¤³¤ÎÌÚ¹½Â¤¤¬°ì½ï
+¤Ë¾ðÊó¤È¤·¤Æ³ÊǼ¤µ¤ì¤ë¤³¤È¤Ë¤Ê¤ë)¡£
¤³¤Î¤è¤¦¤Ê¥Ï¥Õ¥Þ¥óÌÚ¤òºîÀ®¤¹¤ë²Õ½ê¤¬¤¢¤ë¤«¤É¤¦¤«¤òõ¤·¤Æ¤ß¤¿¤È¤³¤í
maketree.c:make_tree() ¤¬¸«¤Ä¤«¤Ã¤¿¡£¤³¤ì¤Ï¡ÖC¸À¸ì¤Ë¤è¤ëºÇ¿·¥¢¥ë¥´¥ê¥º
len_cnt[i] = 0;
count_len(root);
-¤³¤ì¤Ç¡¢len_cnt[0:16] ¤Ë¤Ï¥Ï¥Õ¥Þ¥óÌڤγÆÁؤÎÍդοô¤¬·×¾å¤µ¤ì¤ë¡£Â³¤¤¤Æ (B)
+¤³¤ì¤Ç¡¢len_cnt[1..16] ¤Ë¤Ï¥Ï¥Õ¥Þ¥óÌڤγÆÁؤÎÍդοô¤¬·×¾å¤µ¤ì¤ë¡£Â³¤¤¤Æ (B)
/* (B) */
cum = 0;
}
}
-ºÇ½é¤Î for ʸ¤Ç¤Ï¡¢ÊÑ¿ô i ¤ËÂФ·¤Æ¡¢weight[i] ¤¬°Ê²¼¤Î¤è¤¦¤ËÀßÄꤵ¤ì¤ë¡£
+# ¸å¤Çµ¤¤¬¤Ä¤¤¤¿¤³¤È¤À¤¬¡¢¤¢¤é¤«¤¸¤áÀßÄꤷ¤Æ¤¤¤¿ codeparm[] ¤ÎÆâÍƤϤ³
+# ¤³¤Ç¤Ï»ÈÍѤµ¤ì¤Ê¤¤¡£¤Ä¤Þ¤ê¡¢codeparm[] ¤ÏÀèÄø¤Ï¥ï¡¼¥¯ÍѤΥХåե¡¤È
+# ¤·¤ÆÍøÍѤµ¤ì¤Æ¤¤¤¿¤¬¡¢¤³¤³¤Ç¤Î codeparm[] ¤Ï½èÍý·ë²Ì¤òɽ¤¹¤È¤¤¤¦Æó¤Ä
+# ¤ÎÌò³ä¤¬¤¢¤ë
+
+ºÇ½é¤Î for ʸ¤Ç¤Ï¡¢ÊÑ¿ô i ¤ËÂФ·¤Æ¡¢weight[i] ¤¬²¼¤Î¤è¤¦¤ËÀßÄꤵ¤ì¤ë
weight[i=1..16] = 2^(16-i)
b 2 2 4 2^14 01000000 00000000
c 2 2 4 2^14 10000000 00000000
d 2 2 4 2^14 11000000 00000000
+ ^^ <- ¥Ï¥Õ¥Þ¥óÉä¹æ
-¤À¡£°Ê¹ß¡¢code[] (¼ÂºÝ¤Ë¤Ï codeparm) ¤òÍøÍѤ¹¤ë¤³¤È¤Çɽ°ú¤¤Çʸ»ú¤Ë
+¤À¡£°Ê¹ß¡¢code[] (¼ÂºÝ¤Ë¤Ï codeparm) ¤òÍøÍѤ¹¤ë¤³¤È¤Çɽ°ú¤¤Çʸ»ú c ¤Ë
Âбþ¤¹¤ë¥Ï¥Õ¥Þ¥óÉä¹æ¤òÆÀ¤ë¤³¤È¤¬¤Ç¤¤ë¤è¤¦¤Ë¤Ê¤Ã¤Æ¤¤¤ë(code[c]¤Î¤¦¤Á¾å
°Ì len[c] ¥Ó¥Ã¥È¤À¤±¤ò¸«¤ë)¡£Éä¹æ²½¤ÎºÝ¤ËÌÚ¤òé¤ëɬÍפϤʤ¯¡¢¹â®¤ÊÉä¹æ
²½¤¬²Äǽ¤Ë¤Ê¤ë(¤È´üÂÔ¤µ¤ì¤ë¡£¤É¤ÎÄøÅÙ¸ú²Ì¤¬¤¢¤ë¤«¤Ï¤¤¤º¤ì¸¡¾Ú¤·¤Æ¤ß¤¿
(B) ¤Ï¡¢buf ¤Ë°ú¿ô¤ÇÅϤµ¤ì¤¿Ê¸»ú c ¤ò³ÊǼ¤·¡¢c_freq[c] ¤ÎÃÍ(ʸ»ú¤Î½Ð¸½
ÉÑÅÙ)¤ò¤·¤Æ¤¤¤ë¡£¤É¤¦¤ä¤é´ðËܤÏÅϤµ¤ì¤¿Ê¸»ú c ¤ò±ä¡¹¤È buf ¤Ë³ÊǼ¤·¡¢
-¸å¤Ç¡¢°µ½Ì¤ò¹Ô¤¦(¤ª¤½¤é¤¯ (A) ¤À¤í¤¦)¤è¤¦¤Ë¤Ê¤Ã¤Æ¤¤¤ë¤è¤¦¤À¡£
+¸å¤Ç°µ½Ì¤ò¹Ô¤¦(¤ª¤½¤é¤¯ (A) ¤À¤í¤¦)¤è¤¦¤À¡£
¤³¤Î buf ¤Î¥µ¥¤¥º¤Ï¤È¸À¤¦¤È¡¢¤³¤ì¤Ï alloc_buf() ¤Ç³ä¤êÅö¤Æ¤é¤ì¤Æ¤¤¤¿¡£
¤Ç¡¢3 * CHAR_BIT ¤È¤¤¤¦¤Î¤Ï <len, off> ¤Î³ÊǼ¥Ð¥¤¥È¿ô¤ò¼¨¤·¤Æ¤¤¤ë¡£
(¤È»×¤Ã¤¿¤¬¡¢3 * CHAR_BIT ¤Ç¤Ï¥Ó¥Ã¥È¿ô¤À¡£°ìÊý¡¢bufsiz ¤Ï¥Ð¥¤¥È¿ô¤À¡£
·×»»¤Ë»ÈÍѤ·¤Æ¤¤¤ëñ°Ì¤¬°ã¤¦¡£²¿¤ä¤é¥Ð¥°¤Ã¤Ý¤¤Ê·°Ïµ¤¤¬¤¢¤ë¤¬¡¢¥Ð¥°¤À¤È
-¤·¤Æ¤â¥Ð¥Ã¥Õ¥¡¤ò¸úΨŪ¤Ë»ÈÍѤǤ¤Ê¤¤¤À¤±¤Ê¤Î¤ÇÂ礷¤¿¤³¤È¤Ï¤Ê¤¤¤Î¤À¤í¤¦)
+¤·¤Æ¤â¥Ð¥Ã¥Õ¥¡¤ò¤Á¤ç¤Ã¤È¤À¤±ÌµÂ̤ˤ·¤Æ¤¤¤ë¤À¤±¤Ê¤Î¤ÇÂ礷¤¿¤³¤È¤Ï¤Ê¤¤¤Î
+¤À¤í¤¦)
output_pos = 0 ¤È¤·¤Æ¤¤¤ë¤³¤È¤«¤é¤³¤Î»þÅÀ¤Î buf ¤ÎÃæ¿È¤¬¤¹¤Ù¤Æ
send_block() ¤Ç°µ½Ì¤µ¤ì¥Õ¥¡¥¤¥ë¤Ë½ÐÎϤµ¤ì¤ë¤À¤í¤¦¤³¤È¤¬ÁÛÁü¤Ç¤¤ë¡£
----------------------------------------------------------------------------
-¤³¤ì¤¬¡¢1¥Ö¥í¥Ã¥¯¤Ë1¼ïÎष¤«Ê¸»ú¤¬¤Ê¤¤¾ì¹ç¤Î¥Õ¥¡¥¤¥ë¤Î¾õÂÖ¤À(off¤Î¾ðÊó
-¤Ï¤Þ¤À´Þ¤Þ¤Ê¤¤)¡£(B)¤Î if ¤¬¿¿¤Î¤È¤¤¬¤É¤¦¤Ê¤ë¤«¤ÏÊ£»¨¤½¤¦¤Ê¤Î¤Ç¸å¤Ç¸«
-¤ë¤³¤È¤Ë¤·¤è¤¦¡£
+¤³¤ì¤¬¡¢1¥Ö¥í¥Ã¥¯¤Ë1¼ïÎष¤«Ê¸»ú¤¬¤Ê¤¤¾ì¹ç¤Î½ÐÎϤÀ(off¤Î¾ðÊó¤Ï¤Þ¤À´Þ¤Þ
+¤Ê¤¤)¡£(B)¤Î if ¤¬¿¿¤Î¤È¤¤¬¤É¤¦¤Ê¤ë¤«¤ÏÊ£»¨¤½¤¦¤Ê¤Î¤Ç¸å¤Ç¸«¤ë¤³¤È¤Ë¤·
+¤è¤¦¡£
³¤¤¤Æ (C)
¤³¤¦¤·¤Æ¡¢Ê¸»ú¤Î Huffman Éä¹æɽ¤Ï¡¢pt_len[] ¤È pt_code[](pt_code[] ¤Ï
¤Ä¤Þ¤ê c_len[] ¤Î Huffman Éä¹æ)¤ò½ÐÎϤ¹¤ë¤³¤È¤Çɽ¸½¤µ¤ì¤ë¡£c_code[] ¤¬
-½ÐÎϤµ¤ì¤Æ¤Ê¤¤»×¤¦¤«¤â¤·¤ì¤Ê¤¤¤¬¡¢¤ª¤½¤é¤¯¡¢decode ½èÍý¤¬ c_len[] ¤ÎÃÍ
+½ÐÎϤµ¤ì¤Æ¤Ê¤¤¤È»×¤¦¤«¤â¤·¤ì¤Ê¤¤¤¬¡¢¤ª¤½¤é¤¯¡¢decode ½èÍý¤¬ c_len[] ¤ÎÃÍ
¤«¤é·×»»¤·¤Æµá¤á¤Æ¤¤¤ë¤Î¤Ç¤Ï¤Ê¤¤¤«¤È»×¤ï¤ì¤ë¡£¤³¤ì¤Ï decode ½èÍý¤Î²òÆÉ
¤ÇÌÀ¤é¤«¤Ë¤Ê¤ë¤À¤í¤¦¡£
-lh6- 15 16 5
-lh7- 16 17 5
-
¤Þ¤È¤á¤ë¤È LHA ¤Ë¤ª¤±¤ë°µ½Ì¥Õ¥¡¥¤¥ë¤Î¹½Â¤¤Ï°Ê²¼¤ÎϢ³¤Ç¤¢¤ë¤È¸À¤¨¤ë¤è
¤¦¤À¡£
¤³¤È¤â¤¢¤ë¤Ç¤¢¤í¤¦¤³¤È¤ò´üÂÔ¤·¤Æ¤¤¤ë¡£°Ê¹ß¡¢decode ½èÍý¤ÎÆâÍƤò½èÍý¤Î
ή¤ì¤òÄɤ¦¤³¤È¤Ç³Îǧ¤·¤è¤¦¡£
+¤Ç¤Ï¡¢¤¤¤è¤¤¤è decode ½èÍý¤Î²òÆɤËÆþ¤ë¡£¤³¤ì¤¬½ª¤ì¤Ð LHA ¤Î½èÍý¤ÎÁ´ËÆ
+¤ò°ì±þ¤ÏÌÖÍ夷¤¿¤³¤È¤Ë¤Ê¤ë¤Î¤Ç¡¢µ¤¹ç¤¤¤òÆþ¤ì¤Æ¿Ê¤á¤è¤¦¡£
+
+decode ½èÍý¤Ï°Ê²¼¤Î´Ø¿ô¤«¤éÀ®¤Ã¤Æ¤¤¤ë¡£¤³¤ì¤é¤Ï¡¢slide.c ¤Î decode ´Ø
+¿ô¤«¤é¸Æ¤Ð¤ì¤Æ¤¤¤ë¡£
+
+huf.c:decode_c_st1() /* ʸ»ú¡¢Ä¹¤µ¤Î decode ½èÍý */
+huf.c:decode_p_st1() /* °ÌÃ֤Πdecode ½èÍý */
+huf.c:decode_start_st1() /* decode ½èÍý¤Î½é´ü²½ */
+
+ (¼ÂºÝ¤Ë¤Ï¡¢struct decode_option ¤Î decode_c,
+ decode_p, decode_start ¤ò²ð¤·¤Æ¸Æ¤Ð¤ì¤ë)
+
+decode_start_st1() ¤Ï¡¢°Ê²¼¤ÎÄ̤ê¤À¡£¤³¤ì¤Ï encode_start_st1() ¤Î¤È¤
+¤ÈÆÃÊÌÊѤï¤ë½ê¤Ï¤Ê¤¤¡£ÆäËÀâÌÀ¤ÎɬÍפϤʤ¤¤À¤í¤¦¡£
+
+void
+decode_start_st1( /* void */ )
+{
+ if (dicbit <= 13) {
+ np = 14;
+ pbit = 4;
+ } else {
+ if (dicbit == 16) {
+ np = 17; /* for -lh7- */
+ } else {
+ np = 16;
+ }
+ pbit = 5;
+ }
+
+ init_getbits();
+ blocksize = 0;
+}
+
+¤Ç¤Ï¡¢decode_c_st1() ¤ò¸«¤è¤¦¡£
+
+unsigned short
+decode_c_st1( /*void*/ )
+{
+ unsigned short j, mask;
+
+ if (blocksize == 0) {
+ blocksize = getbits(16);
+ read_pt_len(NT, TBIT, 3);
+ read_c_len();
+ read_pt_len(np, pbit, -1);
+ }
+ blocksize--;
+ j = c_table[bitbuf >> 4];
+ if (j < NC)
+ fillbuf(c_len[j]);
+ else {
+ fillbuf(12);
+ mask = 1 << (16 - 1);
+ do {
+ if (bitbuf & mask)
+ j = right[j];
+ else
+ j = left[j];
+ mask >>= 1;
+ } while (j >= NC);
+ fillbuf(c_len[j] - 12);
+ }
+ return j;
+}
+
+blocksize == 0 ¤Î¾ì¹ç¤Ë
+
+ if (blocksize == 0) {
+ blocksize = getbits(16);
+ read_pt_len(NT, TBIT, 3);
+ read_c_len();
+ read_pt_len(np, pbit, -1);
+ }
+
+¤È¡¢¤¤¤í¤¤¤í¤È¤ä¤Ã¤Æ¤¤¤ë¤¬¤³¤ÎÉôʬ¤Ï¤¹¤°ÁÛÁü¤¬¤Ä¤¯¡£< LHA ¥Õ¥¡¥¤¥ë¤Î¹½
+¤ > ¤Î¥Ï¥Õ¥Þ¥óÉä¹æɽ¤òÆɤ߹þ¤ó¤Ç¤¤¤ë¤Î¤À¤í¤¦¡£¤½¤¦¤·¤Æ¡¢°ìÅÙÆɤ߹þ¤ó
+¤À¸å¤Ï¸å³¤Î½èÍý¤Ç 1 ¥Ö¥í¥Ã¥¯Ê¬(blocksize ʬ)´°Î»¤¹¤ë¤Þ¤Ç decode ¤ò¹Ô
+¤¦¤À¤±¤À¡£
+
+ blocksize--;
+ j = c_table[bitbuf >> 4];
+
+decode ½èÍý¤Ï¥Ï¥Õ¥Þ¥óÉä¹æɽ¤òɽ°ú¤¤¹¤ë¤À¤±¤Ê¤Î¤Çñ½ã¤À¡£bitbuf >> 4
+¤Ï¡¢bitbuf >> (16 - 12) ¤ÈÆɤßÊѤ¨¤¿Êý¤¬¤ï¤«¤ê¤ä¤¹¤¤¡£¤³¤ì¤Ï°ÊÁ°²¿ÅÙ¤â
+½Ð¤¿·Á¤À¤¬ bitbuf ¤Î¾å°Ì 12 bit ¤ò¼è¤ê½Ð¤·¤Æ¤¤¤ë¡£¤½¤¦¤·¤Æ¤½¤ÎÃÍ(¥Ï¥Õ
+¥Þ¥óÉä¹æ)¤ò¸µ¤Ëɽ°ú¤¤·¤¿·ë²Ì j ¤¬Éü¹æ¤·¤¿Ê¸»ú¤È¤Ê¤ë¡£¤Ê¤¼ 12 bit ¤Ê¤Î¤«
+¤Ï¤è¤¯¤ï¤«¤é¤Ê¤¤¸å¤Ç¹Í¤¨¤è¤¦¡£¤³¤Î¸å¤ÎÉôʬ¤Ç¡¢
+
+ if (j < NC)
+ fillbuf(c_len[j]);
+ else {
+ fillbuf(12);
+ mask = 1 << (16 - 1);
+ do {
+ if (bitbuf & mask)
+ j = right[j];
+ else
+ j = left[j];
+ mask >>= 1;
+ } while (j >= NC);
+ fillbuf(c_len[j] - 12);
+ }
+ return j;
+
+j < NC ¤Î¾ì¹ç¤Ï c_len[j] ¤Ç¥Ï¥Õ¥Þ¥óÉä¹æ¤Î¥Ó¥Ã¥ÈĹʬ¤ò fillbuf() ¤·¤Æ¤¤
+¤ë¡£¤Ä¤Þ¤êÀèÄøɽ°ú¤¤·¤¿ 12 bit ¤Î¤¦¤Á c_len[j] bit ¤¬ËÜÅö¤Î¥Ï¥Õ¥Þ¥óÉä
+¹æ¤Ê¤Î¤À¤¬¡¢É½°ú¤¤ÎºÝ¤Ë¼ÂºÝ¤Î¥Ó¥Ã¥ÈŤòµ¤¤Ë¤¹¤ëɬÍפ¬¤Ê¤¤¤Î¤¬ÆÃħŪ¤À¡£
+
+else ¤ÎÉôʬ¤Ï¡¢j ¤òµá¤áľ¤·¤Æ¤¤¤ë¤³¤È¤«¤é¡¢¤É¤¦¤ä¤éÉä¹æɽ¤«¤é¤Îɽ°ú¤
+¤Ç¤ÏÉü¹æ¤Ç¤¤Ê¤¤¾ì¹ç¤òɽ¤·¤Æ¤¤¤ë¤é¤·¤¤¡£¤³¤Î¾ì¹ç¡¢É½°ú¤¤Ë»ÈÍѤ·¤¿ 12
+bit ¤ò¼Î¤Æ(fillbuf(12))¡¢¥Ï¥Õ¥Þ¥óÌÚ(left[], right[])¤òé¤ë»ö¤Ç¡¢Éü¹æ¤ò
+¹Ô¤Ã¤Æ¤¤¤ë¡£¤³¤Î¸å¡¢fillbuf(c_len[j] - 12) ¤·¤Æ¤¤¤ë¤³¤È¤«¤é¡¢Éä¹æŤÏ
+12 bit °Ê¾å¤¢¤ë¤Î¤À¤í¤¦¡£
+
+decode_c_st1() ¤¬ decode ¤¹¤ë°µ½Ìʸ¤Î¹½Â¤¤Ï¿Þ¤Çɽ¤¹¤È°Ê²¼¤Î¤è¤¦¤Ë¤Ê¤ë
+
+----------------------------------------------------------------------------
+
+j < NC ¤Î¾ì¹ç (c_len[j] < 12 ¤Î¾ì¹ç)
+
+ <- c_len[j] ->
+ <----- 12 ------->
+ +--------------+----------
+°µ½Ìʸ | ¥Ï¥Õ¥Þ¥óÉä¹æ |
+ +--------------+----------
+
+j >= NC ¤Î¾ì¹ç (c_len[j] > 12 ¤Î¾ì¹ç)
+
+ <------------ c_len[j] --------->
+ <------ 12 ------>
+ +------------------+--------------+--------
+°µ½Ìʸ | root | ¥Ï¥Õ¥Þ¥óÉä¹æ |
+ +------------------+--------------+--------
+
+ root: ¥Ï¥Õ¥Þ¥óÌڤκ¬
+
+----------------------------------------------------------------------------
+
+¤Ï¤¿¤·¤Æ¡¢°µ½Ì½èÍý¤Î¤È¤¤Ë¤³¤Î¤è¤¦¤Ê¹½Â¤¤òºî¤Ã¤¿³Ð¤¨¤Ï¤Ê¤¤¤Î¤À¤¬¤É¤¦¤¤
+¤¦¤³¤È¤À¤í¤¦¡©²ÝÂê¤ò»Ä¤·¤Ä¤Äº£ÅÙ¤Ï decode_p_st1() (°ÌÃÖ¤ÎÉü¹æ½èÍý)¤ò¸«
+¤ë¡£
+
+unsigned short
+decode_p_st1( /* void */ )
+{
+ unsigned short j, mask;
+
+ j = pt_table[bitbuf >> (16 - 8)];
+ if (j < np)
+ fillbuf(pt_len[j]);
+ else {
+ fillbuf(8);
+ mask = 1 << (16 - 1);
+ do {
+ if (bitbuf & mask)
+ j = right[j];
+ else
+ j = left[j];
+ mask >>= 1;
+ } while (j >= np);
+ fillbuf(pt_len[j] - 8);
+ }
+ if (j != 0)
+ j = (1 << (j - 1)) + getbits(j - 1);
+ return j;
+}
+
+ÀèÄø¤ÈƱ¤¸¤À¡£º£Å٤ϡ¢bitbuf ¤Î¤¦¤Á 8 bit ¤ò»ÈÍѤ·¤Æɽ°ú¤¤ò¹Ô¤¤¡¢
+j < np ¤Ê¤é pt_len[j] ¤òµÍ¤á¡¢¤½¤¦¤Ç¤Ê¤±¤ì¤Ð¥Ï¥Õ¥Þ¥óÌÚ¤òé¤Ã¤Æ¤¤¤ë¡£
+Éü¹æ¤·¤¿ j ¤Ï°ÌÃÖ¤òɽ¤¹ÃͤΠbit Ĺ¤Ê¤Î¤ÇºÇ¸å¤Ë
+
+ j = (1 << (j - 1)) + getbits(j - 1);
+
+¤Ç¡¢ËÜÅö¤Î°ÌÃÖ¤ÎÃͤòÆɤó¤Ç¤¤¤ë(encode_p() ¤¬¤½¤¦¤¤¤¦½èÍý¤À¤Ã¤¿»ö¤ò»×¤¤
+½Ð¤½¤¦)¡£
+
+decode_p_st1() ¤¬ decode ¤¹¤ë°µ½Ìʸ¤Î¹½Â¤¤Ï¿Þ¤Çɽ¤¹¤È°Ê²¼¤Î¤è¤¦¤Ë¤Ê¤ë
+
+----------------------------------------------------------------------------
+
+j < np ¤Î¾ì¹ç (pt_len[j] < 8 ¤Î¾ì¹ç)
+
+ <- pt_len[j] ->
+ <------ 8 ------->
+ +--------------+----------
+°µ½Ìʸ | ¥Ï¥Õ¥Þ¥óÉä¹æ |
+ +--------------+----------
+
+j >= np ¤Î¾ì¹ç (pt_len[j] > 8 ¤Î¾ì¹ç)
+
+ <----------- pt_len[j] --------->
+ <------ 8 ------->
+ +------------------+--------------+----------+----------
+°µ½Ìʸ | root | ¥Ï¥Õ¥Þ¥óÉä¹æ | °ÌÃÖ¤ÎÃÍ |
+ +------------------+--------------+----------+----------
+
+ root: ¥Ï¥Õ¥Þ¥óÌڤκ¬
+
+----------------------------------------------------------------------------
+
+°Ê¾å¤¬¡¢decode ½èÍý¤Î³µÍפÀ¡£¤³¤³¤Þ¤Ç¤Î½èÍý¤ÏÊ̤ˤɤ¦¤È¤¤¤¦»ö¤â¤Ê¤¤¤À
+¤í¤¦¡£decode ½èÍý¤Î¥¥â¤Ï¡¢°µ½Ìʸ¤ËËä¤á¹þ¤ó¤À¥Ï¥Õ¥Þ¥óÉä¹æɽ¤ÎÆɤ߹þ¤ß
+¤Ë¤¢¤ë¡£blocksize == 0 ¤Î¤È¤¤Ë¡¢decode_c_st1() ¤Ç¸Æ¤Ð¤ì¤ë
+read_pt_len(), read_c_len() ¤À¡£¤³¤ì¤Ë¤è¤ê¡¢decode ½èÍý¤Ç»ÈÍѤ¹¤ë¥Æ¡¼¥Ö¥ë
+
+c_table[] ¥Ï¥Õ¥Þ¥óÉä¹æ -> ʸ»ú¤ÎÊÑ´¹¥Æ¡¼¥Ö¥ë
+c_len[] ¥Ï¥Õ¥Þ¥óÉä¹æ -> ¥Ï¥Õ¥Þ¥óÉä¹æ¤Î¥Ó¥Ã¥ÈŤÎÂбþ
+pt_table[] ¥Ï¥Õ¥Þ¥óÉä¹æ -> °ÌÃ֤ΥӥåÈŤÎÊÑ´¹¥Æ¡¼¥Ö¥ë
+pt_len[] ¥Ï¥Õ¥Þ¥óÉä¹æ -> ¥Ï¥Õ¥Þ¥óÉä¹æ¤Î¥Ó¥Ã¥ÈŤÎÂбþ
+left[] ¥Ï¥Õ¥Þ¥óÌÚ(º¸¤Î¥Î¡¼¥É)
+right[] ¥Ï¥Õ¥Þ¥óÌÚ(±¦¤Î¥Î¡¼¥É)
+
+¤¬¹½ÃÛ¤µ¤ì¤ë¡£¤³¤ÎÉôʬ¤ÎÊý¤¬ decode ½èÍýËÜÂΤè¤ê¤ä¤ä¤³¤·¤½¤¦¤À¡£
+¤Ç¤Ï¡¢¤³¤ì¤é¤ò¸«¤Æ¹Ô¤³¤¦¡£
+
+ if (blocksize == 0) {
+ blocksize = getbits(16);
+ read_pt_len(NT, TBIT, 3);
+ read_c_len();
+ read_pt_len(np, pbit, -1);
+ }
+
+ºÇ½é¤Ï¡¢read_pt_len(NT, TBIT, 3) ¤«¤é
+
+static void
+read_pt_len(nn, nbit, i_special)
+ short nn;
+ short nbit;
+ short i_special;
+{
+ int i, c, n;
+
+ n = getbits(nbit);
+ if (n == 0) {
+ c = getbits(nbit);
+ for (i = 0; i < nn; i++)
+ pt_len[i] = 0;
+ for (i = 0; i < 256; i++)
+ pt_table[i] = c;
+ }
+ else {
+ i = 0;
+ while (i < n) {
+ c = bitbuf >> (16 - 3);
+ if (c == 7) {
+ unsigned short mask = 1 << (16 - 4);
+ while (mask & bitbuf) {
+ mask >>= 1;
+ c++;
+ }
+ }
+ fillbuf((c < 7) ? 3 : c - 3);
+ pt_len[i++] = c;
+ if (i == i_special) {
+ c = getbits(2);
+ while (--c >= 0)
+ pt_len[i++] = 0;
+ }
+ }
+ while (i < nn)
+ pt_len[i++] = 0;
+ make_table(nn, pt_len, 8, pt_table);
+ }
+}
+
+¼ÂºÝ¡¢Â礷¤¿»ö¤Ï¤Ê¤¤¡£< pt_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > ¤Ë¤·¤¿¤¬¤Ã¤Æ¡¢
+pt_len[] ¤òÆɤßľ¤·¤Æ¤¤¤ë¤À¤±¤À¡£read_c_len() ¤â¸«¤è¤¦¡£
+
+static void
+read_c_len( /* void */ )
+{
+ short i, c, n;
+
+ n = getbits(CBIT);
+ if (n == 0) {
+ c = getbits(CBIT);
+ for (i = 0; i < NC; i++)
+ c_len[i] = 0;
+ for (i = 0; i < 4096; i++)
+ c_table[i] = c;
+ } else {
+ i = 0;
+ while (i < n) {
+ c = pt_table[bitbuf >> (16 - 8)];
+ if (c >= NT) {
+ unsigned short mask = 1 << (16 - 9);
+ do {
+ if (bitbuf & mask)
+ c = right[c];
+ else
+ c = left[c];
+ mask >>= 1;
+ } while (c >= NT);
+ }
+ fillbuf(pt_len[c]);
+ if (c <= 2) {
+ if (c == 0)
+ c = 1;
+ else if (c == 1)
+ c = getbits(4) + 3;
+ else
+ c = getbits(CBIT) + 20;
+ while (--c >= 0)
+ c_len[i++] = 0;
+ }
+ else
+ c_len[i++] = c - 2;
+ }
+ while (i < NC)
+ c_len[i++] = 0;
+ make_table(NC, c_len, 12, c_table);
+ }
+}
+
+¤³¤Á¤é¤â¡¢< c_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > ¤Ë¤·¤¿¤¬¤Ã¤Æ¡¢c_len[] ¤òÆɤß
+ľ¤·¤Æ¤¤¤ë¤À¤±¤À¡£·ë¶É¥¥â¤È¤Ê¤ë¤Î¤Ï¡¢make_table() ¤Ë¤¢¤ë¤é¤·¤¤¡£¤³¤Î
+´Ø¿ô¤Ë¤è¤ê¡¢Æɤ߹þ¤ó¤À pt_len[], c_len[] ¤«¤é pt_table[], c_table[]
+(¤½¤·¤Æ¡¢¥Ï¥Õ¥Þ¥óÌÚ left[], right[])¤ò¹½ÃÛ¤·¤Æ¤¤¤ë¤Î¤À¤í¤¦¡£
+
+·ë¶É¡¢decode ½èÍý read_c_len(), read_pt_len() ¤òÆɤó¤Ç¤â¤Ê¤¼¤³¤Î¤è¤¦¤Ê
+Éä¹æ²½¤ò¹Ô¤Ã¤Æ¤¤¤ë¤Î¤«¤è¤¯¤ï¤«¤é¤Ê¤«¤Ã¤¿¡£²¿¤«Åý·×Ū¤Êº¬µò¤Ç¤â¤¢¤ë¤Î¤À
+¤í¤¦¤«¡©¤½¤ì¤È¤â LHA ¤Ë¤È¤Ã¤ÆÎò»ËŪ¤Ê»ö¾ð¤Ç¤â¤¢¤ë¤Î¤«¡©¤³¤ì¤Ë´Ø¤·¤Æ¤Ï
+ÊÌÅÓ¸¡¾Ú¤ÎɬÍפ¬¤¢¤ë¤À¤í¤¦¡£
+
+¤Ç¤Ï¡¢ºÇ¸å¤Î´Ø¿ô make_table() ¤ò²òÆɤ·¤è¤¦¡£¤³¤ì¤Ï¡¢maketbl.c ¤ÇÄêµÁ¤µ
+¤ì¤Æ¤¤¤ë¡£
+
+void
+make_table(nchar, bitlen, tablebits, table)
+ short nchar;
+ unsigned char bitlen[];
+ short tablebits;
+ unsigned short table[];
+{
+ unsigned short count[17]; /* count of bitlen */
+ unsigned short weight[17]; /* 0x10000ul >> bitlen */
+ unsigned short start[17]; /* first code of bitlen */
+ unsigned short total;
+ unsigned int i, l;
+ int j, k, m, n, avail;
+ unsigned short *p;
+
+ /* (A) */
+ avail = nchar;
+
+ /* initialize */
+ for (i = 1; i <= 16; i++) {
+ count[i] = 0;
+ weight[i] = 1 << (16 - i);
+ }
+
+ /* (B) */
+ /* count */
+ for (i = 0; i < nchar; i++)
+ count[bitlen[i]]++;
+
+ /* (C) */
+ /* calculate first code */
+ total = 0;
+ for (i = 1; i <= 16; i++) {
+ start[i] = total;
+ total += weight[i] * count[i];
+ }
+ if ((total & 0xffff) != 0)
+ error("make_table()", "Bad table (5)\n");
+
+ /* (D) */
+ /* shift data for make table. */
+ m = 16 - tablebits;
+ for (i = 1; i <= tablebits; i++) {
+ start[i] >>= m;
+ weight[i] >>= m;
+ }
+
+ /* (E) */
+ /* initialize */
+ j = start[tablebits + 1] >> m;
+ k = 1 << tablebits;
+ if (j != 0)
+ for (i = j; i < k; i++)
+ table[i] = 0;
+
+ /* (F) */
+ /* create table and tree */
+ for (j = 0; j < nchar; j++) {
+ k = bitlen[j];
+ if (k == 0)
+ continue;
+ l = start[k] + weight[k];
+ if (k <= tablebits) {
+ /* code in table */
+ for (i = start[k]; i < l; i++)
+ table[i] = j;
+ }
+ else {
+ /* code not in table */
+ p = &table[(i = start[k]) >> m];
+ i <<= tablebits;
+ n = k - tablebits;
+ /* make tree (n length) */
+ while (--n >= 0) {
+ if (*p == 0) {
+ right[avail] = left[avail] = 0;
+ *p = avail++;
+ }
+ if (i & 0x8000)
+ p = &right[*p];
+ else
+ p = &left[*p];
+ i <<= 1;
+ }
+ *p = j;
+ }
+ start[k] = l;
+ }
+}
+
+½ç¤Ë¸«¤Æ¹Ô¤³¤¦¡£
+
+ /* (A) */
+ avail = nchar;
+
+ /* initialize */
+ for (i = 1; i <= 16; i++) {
+ count[i] = 0;
+ weight[i] = 1 << (16 - i);
+ }
+
+avail ¤Ï¤ª¤½¤é¤¯ maketree.c:make_tree() ¤Ç¤½¤¦¤Ç¤¢¤Ã¤¿¤è¤¦¤Ë¡¢ÌÚ¤ÎÀá¤Î
+½é´üÃͤÀ¤í¤¦¤ÈͽÁÛ¤·¤Æ¤ª¤¯¡£count[], weight[] ¤â¡¢maketree.c ¤Ç¤Î
+len_cnt[] weight[] ¤ÈƱµÁ¤À¤í¤¦(¤¹¤Ê¤ï¤Á¡¢count[i] ¤Ï¡¢Ìڤο¼¤µ i ÈÖÌÜ
+¤ÎÍդοô¡¢weight[i] ¤Ï½Å¤ß)
+
+ /* (B) */
+ /* count */
+ for (i = 0; i < nchar; i++)
+ count[bitlen[i]]++;
+
+count[] ¤òµá¤á¤Æ¤¤¤ë¡£bitlen[i] ¤Ï¡¢Ê¸»ú i ¤Î¥Ï¥Õ¥Þ¥óÉä¹æ¤Ç¤Î bit ŤÇ
+¤¢¤Ã¤¿¡£¤ä¤Ï¤ê count[] ¤ÏͽÁÛÄ̤ê¤À¡£
+
+ /* (C) */
+ /* calculate first code */
+ total = 0;
+ for (i = 1; i <= 16; i++) {
+ start[i] = total;
+ total += weight[i] * count[i];
+ }
+ if ((total & 0xffff) != 0)
+ error("make_table()", "Bad table (5)\n");
+
+¤³¤ì¤Ï¡¢maketree.c:make_code() ¤ÎÁ°È¾Éôʬ¤È¤Þ¤Ã¤¿¤¯Æ±¤¸¤À¡£¤³¤ì¤Ë¤è¤ê¡¢
+¿¼¤µ i ¤ËÂФ·¤Æ¡¢°Ê²¼¤ÎÂбþɽ¤¬¤Ç¤¤ë(¤³¤ì¤ÏÁ°¤Ë¤â½ñ¤¤¤¿¡£Li ¤Ï¡¢
+count[i] ¤ÎÃͤòɽ¤·¤Æ¤¤¤ë)¡£
+
+ i count[i] weight[i] start[i]
+ --------------------------------------------
+ 1 L1 2^15 0
+ 2 L2 2^14 2^15 * L1
+ 3 L3 2^13 2^15 * L1 + 2^14 * L2
+ 4 L4 2^12 2^15 * L1 + 2^14 * L2 + 2^13 * L3
+
+¤³¤ì¤¬²¿¤òɽ¤¹¤«¤È¸À¤¦¤È¿¼¤µ i ¤ÎÉä¹æ(¤Ä¤Þ¤ê bit Ĺ i ¤ÎÉä¹æ)¤Ï¡¢
+start[i] ¤«¤é start[i+1]-1 ¤ÎÈϰϤÎÃͤò»ý¤Ä¤È¸À¤¦»ö¤ò°ÕÌ£¤¹¤ë¡£ºÆÅÙ¡¢
+Îã¤Ç¼¨¤½¤¦¡£
+
+ /\ a: 0
+ a /\ b: 10
+ b c c: 11
+
+ i count[i] weight[i] start[i]
+ --------------------------------------------
+ 1 1 2^15 0
+ 2 2 2^14 2^15
+ 3 0 2^13 2^15 + 2^14 * 2
+
+¤³¤ì¤è¤ê¡¢¿¼¤µ 1 ¤ÎÍÕ a ¤Ï¡¢start[1] .. start[2]-1 ¤Ä¤Þ¤ê¡¢
+00000000 00000000 .. 01111111 11111111 ¤ÎÈϰϤÎÉä¹æ¤È¤Ê¤ë¡£
+¿¼¤µ 2 ¤ÎÍÕ b, c ¤Ï¡¢start[2] .. start[3]-1 ¤Ä¤Þ¤ê¡¢
+10000000 00000000 ... 11111111 11111111 ¤È¤Ê¤ë¡£
+
+ /* (D) */
+ /* shift data for make table. */
+ m = 16 - tablebits;
+ for (i = 1; i <= tablebits; i++) {
+ start[i] >>= m;
+ weight[i] >>= m;
+ }
+
+Íýͳ¤Ï¤ï¤«¤é¤Ê¤¤¤¬¡¢ºîÀ®¤¹¤ë¥Æ¡¼¥Ö¥ë¤ò°ú¿ô¤ÇÅϤµ¤ì¤¿ bit ¿ô¤Î¥Æ¡¼¥Ö¥ë
+¤Ë¤Ê¤ë¤è¤¦¼ÌÁü¤·¤Æ¤¤¤ë¡£¤Ä¤Þ¤ê¡¢ÃͤÎÈϰϤνé´üÃÍ start[] ¤È weight[]
+¤ò 16 - tablebits ¤Ç¥·¥Õ¥È¤¹¤ë¤³¤È¤Ç¡¢
+
+ 01111111 11111111
+
+¤È¤¤¤¦¥Æ¡¼¥Ö¥ë¤ÎÃͤÏ(tablebits ¤¬ 12 ¤Ç¤¢¤ë¤È¤¹¤ë¤È)¡¢
+
+ 00000111 11111111
+
+¤ÎÃͤˤ¹¤ë¡£encode ¤¹¤ë¤È¤¤Ï¡¢16 bit ¤Î¥Æ¡¼¥Ö¥ë¤ò¤½¤Î¤Þ¤Þ»ÈÍѤ·¤Æ¤¤¤¿
+¤Ë¤â´Ø¤ï¤é¤º decode ¤Î¤È¤¤Ë¤Ï¥Æ¡¼¥Ö¥ë¤Î bit ¿ô¤ò¸º¤é¤·¤Æ¤¤¤ë¤Î¤À¡£¤Þ¤Ã
+¤¿¤¯Íýͳ¤¬¤ï¤«¤é¤Ê¤¤¡£
+
+ÅöÁ³¡¢encode ¤Ç»ÈÍѤ·¤Æ¤¤¤¿¤È¤¤Î¥Æ¡¼¥Ö¥ë¤è¤ê¾ðÊóÎ̤¬¸º¤Ã¤Æ¤¤¤ë¤Î¤Ç¡¢
+¤¹¤Ù¤Æ¤ò¥Æ¡¼¥Ö¥ë»²¾È¤Ç decode ¤¹¤ë¤³¤È¤Ï¤Ç¤¤Ê¤¤¡£¤½¤³¤Ç¡¢Â¤ê¤Ê¤¤Éôʬ
+¤Ï¸å¤Î½èÍý¤ÇÌÚ¤òºî¤ë¤³¤È¤ÇÊä¤Ã¤Æ¤¤¤ë¤è¤¦¤À¡£
+
+¤Á¤ç¤Ã¤Èµ¤Ê¬Åª¤Ë¥Î¤é¤Ê¤¤¤Î¤Ç¤Ï¤·¤ç¤ë¤¬¡¢¸å¤Î (E), (F) ¤ÏÌÚ¤òƱ»þ¤Ëºî¤Ã
+¤Æ¤¤¤ë¤³¤È¤ò½ü¤±¤Ð¡¢maketree.c:make_code() ¤Î¸åȾÉôʬ¤ÈƱ¤¸¤À¤È¹Í¤¨¤Æ
+¤¤¤¤¤À¤í¤¦¡£
+
# Local Variables:
# mode : indented-text
# indent-tabs-mode: nil
OSDN Git Service
