From 28c5db6075f799fbb33996229ddf8691fcf3d0d3 Mon Sep 17 00:00:00 2001 From: arai Date: Sat, 24 Sep 2005 13:01:59 +0000 Subject: [PATCH] * Hacking_of_LHa: updated. (2003-02-23 edition) git-svn-id: svn+ssh://svn.sourceforge.jp/svnroot/lha/lha/trunk@829 6a8cc165-1e22-0410-a132-eb4e3f353aba --- Hacking_of_LHa | 617 ++++++++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 584 insertions(+), 33 deletions(-) diff --git a/Hacking_of_LHa b/Hacking_of_LHa index 89f9123..2fb2b3a 100644 --- a/Hacking_of_LHa +++ b/Hacking_of_LHa @@ -3,7 +3,7 @@ $Id$ The Hacking of LHa for UNIX (2nd draft) ------------------------------------------- - Koji Arai + Koji Arai Ëܽñ¤Ï¡¢LHa for UNIX 1.14i ¤Î¥½¡¼¥¹¤ò²òÆɤ·¡¢¤½¤Î°µ½Ì¥¢¥ë¥´¥ê¥º¥à¤Î¼Â Áõ¤ò³Îǧ¤¹¤ë¤¿¤á¤Î¤â¤Î¤À¡£¤³¤ÎÀ®²Ì¤ÏÊ̤ηÁ¤Ç¤Þ¤È¤á¤Ê¤ª¤µ¤ì»ñÎÁ¤Ë¤Ê¤ë¤« @@ -2143,7 +2143,7 @@ init_putbits( /* void */ ) } ¤½¤ì¤¾¤ì bit ÆþÎÏ¡¢bit ½ÐÎϤò¹Ô¤¦¤¿¤á¤Î½é´ü²½½èÍý¤À¡£CHAR_BIT ¤È¤¤¤¦¤Î -¤Ï 8 ¤Ç¡¢char ¤Î bit ¥µ¥¤¥º¤òɽ¤·¤Æ¤¤¤ë¤é¤·¤¤¡£¾ÜºÙ¤Ï¤ï¤«¤é¤Ê¤¤¤¬½é´ü +¤Ï 8 ¤Ç¡¢char ·¿¤Î bit ¥µ¥¤¥º¤òɽ¤·¤Æ¤¤¤ë¤é¤·¤¤¡£¾ÜºÙ¤Ï¤ï¤«¤é¤Ê¤¤¤¬½é´ü ¾õÂ֤ϤȤˤ«¤¯¤³¤ì¤À¡£¤³¤³¤Ç»ÈÍѤµ¤ì¤Æ¤¤¤ëÊÑ¿ô¤Ï¡¢ static unsigned char subbitbuf, bitcount; @@ -2305,7 +2305,7 @@ n{16} (B) ¤Ç¡¢subbitbuf ¤Ë»Ä¤Ã¤Æ¤¤¤ë bit ¤ò bitbuf ¤Ë¤º¤é¤·¤Æ¤¤¤ë¡£º£¤Ï¤Þ¤À ¶õ¤Ê¤Î¤Çbitbuf ¤Ï¤³¤³¤Ç¤â¤Þ¤À¶õ¤À¡£ -(C) ¤Ç¡¢8 ¥Ó¥Ã¥È¥Õ¥¡¥¤¥ë¤«¤é¥Ç¡¼¥¿¤òÆɤà(compsize ¤Ï¾ï¤Ë0¤Ç¤Ê¤¤¤È¹Í¤¨ +(C) ¤Ç¡¢¥Õ¥¡¥¤¥ë¤«¤é¥Ç¡¼¥¿¤ò8 ¥Ó¥Ã¥ÈÆɤà(compsize ¤Ï¾ï¤Ë0¤Ç¤Ï¤Ê¤¤¤È¹Í¤¨ ¤ë)¡£bitcount ¤Ï 8 ¤Ë¤Ê¤ë¡£¤³¤Î»þÅÀ¤Ç bit¥Ð¥Ã¥Õ¥¡Á´ÂÎ¤Ï subbitbuf ¤À¤± Ãͤ¬Æþ¤Ã¤¿¾õÂ֤ˤʤ롣 @@ -2328,7 +2328,7 @@ bit ¤¦¡£½èÍýÆâÍƤò³Îǧ¤·¤Æ¤ß¤ì¤Ð¤ï¤«¤ë¡£ ¤³¤³¤Ç¡¢subbitbuf ¤ÎÍÑÅӤ˵¤¤Å¤¤¤¿¡£¥Õ¥¡¥¤¥ë¤«¤é¤ÎÆɤ߹þ¤ß¤¬ 8 ¥Ó¥Ã¥È -ñ°Ì¤Ç¤·¤«¤Ç¤­¤Ê¤¤¤Î¤Ç¡¢¤½¤ì¤òÊ䤦¤¿¤á¤ÎÀèÆɤߥХåե¡¤Ç¤¢¤í¤¦¡£Î㤨¤Ð +ñ°Ì¤Ç¤·¤«¤Ç¤­¤Ê¤¤¤Î¤Ç¡¢¤½¤ì¤òÊ䤦¤¿¤á¤ÎÊݸÍѥХåե¡¤Ç¤¢¤í¤¦¡£Î㤨¤Ð 1 ¥Ó¥Ã¥È¤À¤± bitbuf ¤ò fill ¤·¤¿¤±¤ì¤Ð subbitbuf ¤Ë 7 bit »Ä¤·¡¢1 bit ¤À¤± bitbuf ¤ËÀßÄꤵ¤ì¤ë(³Îǧ¤·¤Æ¤ß¤ì¤Ð¤ï¤«¤ë) @@ -2579,10 +2579,18 @@ LHa for UNIX ¤³¤Î¥Æ¥­¥¹¥È¤Ï 9 ¥Ð¥¤¥È¤¢¤ë¤ï¤±¤À¤¬¡¢¤³¤Î¥Õ¥¡¥¤¥ë¤Ç»È¤ï¤ì¤Æ¤¤¤ëʸ»ú¤Ï3 ¼ïÎष¤«¤Ê¤¤¡¢a, b, c ¤À¡£¤À¤«¤é¤³¤Î¥Õ¥¡¥¤¥ë¤À¤±¤Ë´Ø¤·¤Æ¸À¤¨¤Ð 1 ʸ»ú -¤Ï 2 ¥Ó¥Ã¥È¤¢¤ì¤Ðɽ¸½²Äǽ¤Ç¤¢¤ë(¤³¤Î¥Õ¥¡¥¤¥ë¤Î¾ì¹çÁ´ÂΤǡ¢18¥Ó¥Ã¥È¤¢¤ì -¤Ðɽ¸½²Äǽ)¡£¤µ¤é¤Ë¡¢½Ð¸½ÉÑÅ٤ι⤤ʸ»ú¤ò¾¯¤Ê¤¤¥Ó¥Ã¥È¿ô¤Çɽ¸½¤·¡¢¤Þ¤ì -¤Ë¤·¤«¸½¤ì¤Ê¤¤Ê¸»ú¤òŤ¤¥Ó¥Ã¥È¿ô¤Çɽ¤¹¤è¤¦¤Ë¤¹¤ì¤Ð¤è¤ê¥Ó¥Ã¥È¿ô¤ò¾¯¤Ê¤¯ -¤Ç¤­¤ë¡£Î㤨¤Ð +¤Ï 2 ¥Ó¥Ã¥È¤¢¤ì¤Ðɽ¸½²Äǽ¤Ç¤¢¤ë¡£Î㤨¤Ð³Æʸ»ú¤ËÂФ·¤Æ°Ê²¼¤Î¥Ó¥Ã¥È¤ò +³ä¤êÅö¤Æ¤¿¤È¤¹¤ë¤È + + ʸ»ú ¥Ó¥Ã¥Èɽ¸½ + a 00 + b 01 + c 10 + +Àè¤Î¥Æ¥­¥¹¥È¥Õ¥¡¥¤¥ë¤ÎÆâÍÆ abcabcaba ¤Ï¡¢18¥Ó¥Ã¥È¤¢¤ì¤Ðɽ¸½²Äǽ¤È¤Ê¤ë¡£ + +¤µ¤é¤Ë¡¢½Ð¸½ÉÑÅ٤ι⤤ʸ»ú¤ò¾¯¤Ê¤¤¥Ó¥Ã¥È¿ô¤Çɽ¸½¤·¡¢¤Þ¤ì¤Ë¤·¤«¸½¤ì¤Ê¤¤ +ʸ»ú¤òŤ¤¥Ó¥Ã¥È¿ô¤Çɽ¤¹¤è¤¦¤Ë¤¹¤ì¤Ð¤è¤ê¥Ó¥Ã¥È¿ô¤ò¾¯¤Ê¤¯¤Ç¤­¤ë¡£Î㤨¤Ð ʸ»ú ¥Ó¥Ã¥Èɽ¸½ a 0 @@ -2596,33 +2604,57 @@ LHa for UNIX ¤òµá¤á¤Æ¤ª¤¯É¬Íפ¬¤¢¤ê¡¢Éü¹æ²½¤ÎºÝ¤Ï¤É¤Î¥Ó¥Ã¥ÈÎ󤬤ɤÎʸ»ú¤ËÂбþ¤¹¤ë¤« ¤ò¤¢¤é¤«¤¸¤áÃΤëɬÍפ¬¤¢¤ë¡£ -¤Ç¤Ï¡¢Éä¹æ²½¤ÎºÝ¤Ëʸ»ú¤ËÂбþ¤¹¤ë¥Ó¥Ã¥ÈÎó¤òµá¤á¤ëÊýË¡¤À¤¬¡¢°Ê²¼¤¬¤½¤Î¥¢ -¥ë¥´¥ê¥º¥à¤À¡£¥Ï¥Õ¥Þ¥óË¡¤Ç¤Ï¥Ï¥Õ¥Þ¥óÌڤȤ¤¤¦ÌÚ¹½Â¤¤ò¹½ÃÛ¤¹¤ë¡£³Æʸ»ú¤Î -½Ð¸½²ó¿ô +ʸ»úËè¤Ë¥Ó¥Ã¥ÈĹ¤Î¤Ð¤é¤Ä¤­¤¬¤¢¤ë¤è¤¦¤Ê²ÄÊÑĹÉä¹æ¤Ë¤Ï°Ê²¼¤Î¾ò·ï¤¬¤¢¤ë¡£ + + ¤¢¤ëÉä¹æ¤Î¥Ó¥Ã¥È¥Ñ¥¿¡¼¥ó¤Ï¡¢Â¾¤ÎÉä¹æ¤Î¥Ó¥Ã¥È¥Ñ¥¿¡¼¥ó¤Î³«»Ï¤Ë¤Ï¤Ê¤é + ¤Ê¤¤¡£ + +¤È¤¤¤¦¤â¤Î¤À¡£¤³¤ì¤ò¡Ö¸ìƬ¾ò·ï¡×¤È¸À¤¦¤é¤·¤¤¡£Î㤨¤Ð¡¢Àè¤ÎÎã¤Ç¤Ï 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¸À¸ì¤Ë¤è¤ëºÇ¿·¥¢¥ë¥´¥ê¥º @@ -3041,7 +3073,7 @@ count_len() len_cnt[i] = 0; count_len(root); -¤³¤ì¤Ç¡¢len_cnt[0:16] ¤Ë¤Ï¥Ï¥Õ¥Þ¥óÌڤγÆÁؤÎÍդοô¤¬·×¾å¤µ¤ì¤ë¡£Â³¤¤¤Æ (B) +¤³¤ì¤Ç¡¢len_cnt[1..16] ¤Ë¤Ï¥Ï¥Õ¥Þ¥óÌڤγÆÁؤÎÍդοô¤¬·×¾å¤µ¤ì¤ë¡£Â³¤¤¤Æ (B) /* (B) */ cum = 0; @@ -3299,7 +3331,12 @@ make_code(n, len, code) } } -ºÇ½é¤Î for ʸ¤Ç¤Ï¡¢ÊÑ¿ô i ¤ËÂФ·¤Æ¡¢weight[i] ¤¬°Ê²¼¤Î¤è¤¦¤ËÀßÄꤵ¤ì¤ë¡£ +# ¸å¤Çµ¤¤¬¤Ä¤¤¤¿¤³¤È¤À¤¬¡¢¤¢¤é¤«¤¸¤áÀßÄꤷ¤Æ¤¤¤¿ codeparm[] ¤ÎÆâÍƤϤ³ +# ¤³¤Ç¤Ï»ÈÍѤµ¤ì¤Ê¤¤¡£¤Ä¤Þ¤ê¡¢codeparm[] ¤ÏÀèÄø¤Ï¥ï¡¼¥¯ÍѤΥХåե¡¤È +# ¤·¤ÆÍøÍѤµ¤ì¤Æ¤¤¤¿¤¬¡¢¤³¤³¤Ç¤Î codeparm[] ¤Ï½èÍý·ë²Ì¤òɽ¤¹¤È¤¤¤¦Æó¤Ä +# ¤ÎÌò³ä¤¬¤¢¤ë + +ºÇ½é¤Î for ʸ¤Ç¤Ï¡¢ÊÑ¿ô i ¤ËÂФ·¤Æ¡¢weight[i] ¤¬²¼¤Î¤è¤¦¤ËÀßÄꤵ¤ì¤ë weight[i=1..16] = 2^(16-i) @@ -3389,8 +3426,9 @@ a, b, c 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] ¥Ó¥Ã¥È¤À¤±¤ò¸«¤ë)¡£Éä¹æ²½¤ÎºÝ¤ËÌÚ¤òé¤ëɬÍפϤʤ¯¡¢¹â®¤ÊÉä¹æ ²½¤¬²Äǽ¤Ë¤Ê¤ë(¤È´üÂÔ¤µ¤ì¤ë¡£¤É¤ÎÄøÅÙ¸ú²Ì¤¬¤¢¤ë¤«¤Ï¤¤¤º¤ì¸¡¾Ú¤·¤Æ¤ß¤¿ @@ -3674,7 +3712,7 @@ output_st1(c, p) (B) ¤Ï¡¢buf ¤Ë°ú¿ô¤ÇÅϤµ¤ì¤¿Ê¸»ú c ¤ò³ÊǼ¤·¡¢c_freq[c] ¤ÎÃÍ(ʸ»ú¤Î½Ð¸½ ÉÑÅÙ)¤ò­¤·¤Æ¤¤¤ë¡£¤É¤¦¤ä¤é´ðËܤÏÅϤµ¤ì¤¿Ê¸»ú c ¤ò±ä¡¹¤È buf ¤Ë³ÊǼ¤·¡¢ -¸å¤Ç¡¢°µ½Ì¤ò¹Ô¤¦(¤ª¤½¤é¤¯ (A) ¤À¤í¤¦)¤è¤¦¤Ë¤Ê¤Ã¤Æ¤¤¤ë¤è¤¦¤À¡£ +¸å¤Ç°µ½Ì¤ò¹Ô¤¦(¤ª¤½¤é¤¯ (A) ¤À¤í¤¦)¤è¤¦¤À¡£ ¤³¤Î buf ¤Î¥µ¥¤¥º¤Ï¤È¸À¤¦¤È¡¢¤³¤ì¤Ï alloc_buf() ¤Ç³ä¤êÅö¤Æ¤é¤ì¤Æ¤¤¤¿¡£ @@ -3829,7 +3867,8 @@ buf | 32 | c1 | c2 | len | off | c3 | c4 | c5 | c6 | c7 | ¤Ç¡¢3 * CHAR_BIT ¤È¤¤¤¦¤Î¤Ï ¤Î³ÊǼ¥Ð¥¤¥È¿ô¤ò¼¨¤·¤Æ¤¤¤ë¡£ (¤È»×¤Ã¤¿¤¬¡¢3 * CHAR_BIT ¤Ç¤Ï¥Ó¥Ã¥È¿ô¤À¡£°ìÊý¡¢bufsiz ¤Ï¥Ð¥¤¥È¿ô¤À¡£ ·×»»¤Ë»ÈÍѤ·¤Æ¤¤¤ëñ°Ì¤¬°ã¤¦¡£²¿¤ä¤é¥Ð¥°¤Ã¤Ý¤¤Ê·°Ïµ¤¤¬¤¢¤ë¤¬¡¢¥Ð¥°¤À¤È -¤·¤Æ¤â¥Ð¥Ã¥Õ¥¡¤ò¸úΨŪ¤Ë»ÈÍѤǤ­¤Ê¤¤¤À¤±¤Ê¤Î¤ÇÂ礷¤¿¤³¤È¤Ï¤Ê¤¤¤Î¤À¤í¤¦) +¤·¤Æ¤â¥Ð¥Ã¥Õ¥¡¤ò¤Á¤ç¤Ã¤È¤À¤±ÌµÂ̤ˤ·¤Æ¤¤¤ë¤À¤±¤Ê¤Î¤ÇÂ礷¤¿¤³¤È¤Ï¤Ê¤¤¤Î +¤À¤í¤¦) output_pos = 0 ¤È¤·¤Æ¤¤¤ë¤³¤È¤«¤é¤³¤Î»þÅÀ¤Î buf ¤ÎÃæ¿È¤¬¤¹¤Ù¤Æ send_block() ¤Ç°µ½Ì¤µ¤ì¥Õ¥¡¥¤¥ë¤Ë½ÐÎϤµ¤ì¤ë¤À¤í¤¦¤³¤È¤¬ÁÛÁü¤Ç¤­¤ë¡£ @@ -3980,9 +4019,9 @@ root ---------------------------------------------------------------------------- -¤³¤ì¤¬¡¢1¥Ö¥í¥Ã¥¯¤Ë1¼ïÎष¤«Ê¸»ú¤¬¤Ê¤¤¾ì¹ç¤Î¥Õ¥¡¥¤¥ë¤Î¾õÂÖ¤À(off¤Î¾ðÊó -¤Ï¤Þ¤À´Þ¤Þ¤Ê¤¤)¡£(B)¤Î if ¤¬¿¿¤Î¤È¤­¤¬¤É¤¦¤Ê¤ë¤«¤ÏÊ£»¨¤½¤¦¤Ê¤Î¤Ç¸å¤Ç¸« -¤ë¤³¤È¤Ë¤·¤è¤¦¡£ +¤³¤ì¤¬¡¢1¥Ö¥í¥Ã¥¯¤Ë1¼ïÎष¤«Ê¸»ú¤¬¤Ê¤¤¾ì¹ç¤Î½ÐÎϤÀ(off¤Î¾ðÊó¤Ï¤Þ¤À´Þ¤Þ +¤Ê¤¤)¡£(B)¤Î if ¤¬¿¿¤Î¤È¤­¤¬¤É¤¦¤Ê¤ë¤«¤ÏÊ£»¨¤½¤¦¤Ê¤Î¤Ç¸å¤Ç¸«¤ë¤³¤È¤Ë¤· +¤è¤¦¡£ ³¤¤¤Æ (C) @@ -4420,7 +4459,7 @@ c_len[i] != 0 ¤³¤¦¤·¤Æ¡¢Ê¸»ú¤Î Huffman Éä¹æɽ¤Ï¡¢pt_len[] ¤È pt_code[](pt_code[] ¤Ï ¤Ä¤Þ¤ê c_len[] ¤Î Huffman Éä¹æ)¤ò½ÐÎϤ¹¤ë¤³¤È¤Çɽ¸½¤µ¤ì¤ë¡£c_code[] ¤¬ -½ÐÎϤµ¤ì¤Æ¤Ê¤¤»×¤¦¤«¤â¤·¤ì¤Ê¤¤¤¬¡¢¤ª¤½¤é¤¯¡¢decode ½èÍý¤¬ c_len[] ¤ÎÃÍ +½ÐÎϤµ¤ì¤Æ¤Ê¤¤¤È»×¤¦¤«¤â¤·¤ì¤Ê¤¤¤¬¡¢¤ª¤½¤é¤¯¡¢decode ½èÍý¤¬ c_len[] ¤ÎÃÍ ¤«¤é·×»»¤·¤Æµá¤á¤Æ¤¤¤ë¤Î¤Ç¤Ï¤Ê¤¤¤«¤È»×¤ï¤ì¤ë¡£¤³¤ì¤Ï decode ½èÍý¤Î²òÆÉ ¤ÇÌÀ¤é¤«¤Ë¤Ê¤ë¤À¤í¤¦¡£ @@ -4448,7 +4487,6 @@ dicbit + 1 -lh6- 15 16 5 -lh7- 16 17 5 - ¤Þ¤È¤á¤ë¤È LHA ¤Ë¤ª¤±¤ë°µ½Ì¥Õ¥¡¥¤¥ë¤Î¹½Â¤¤Ï°Ê²¼¤ÎϢ³¤Ç¤¢¤ë¤È¸À¤¨¤ë¤è ¤¦¤À¡£ @@ -4488,6 +4526,519 @@ dicbit + 1 ¤³¤È¤â¤¢¤ë¤Ç¤¢¤í¤¦¤³¤È¤ò´üÂÔ¤·¤Æ¤¤¤ë¡£°Ê¹ß¡¢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 -- 2.11.0