X-Git-Url: http://git.osdn.net/view?a=blobdiff_plain;f=Hacking_of_LHa;h=37343d9d1143800003620c520e2e558163f6a2cb;hb=67b228cc75193e8bd7e9e49cffb8c1172562a30e;hp=d57c0f334dd76b6967f527a5fbafe226116fcd13;hpb=6f7e23e006461e133ff3bd25e1b62093cfe26150;p=lha%2Flha.git diff --git a/Hacking_of_LHa b/Hacking_of_LHa index d57c0f3..37343d9 100644 --- a/Hacking_of_LHa +++ b/Hacking_of_LHa @@ -1,6 +1,6 @@ $Id$ - The Hacking of LHa for UNIX (2nd draft) + The Hacking of LHa for UNIX (3rd draft) ------------------------------------------- Koji Arai @@ -23,8 +23,17 @@ $Id$ ½èÍý¤Ë´Ø¤·¤Æ¤Ï̵ÃΤǤ¢¤ë¡£ÍѸì¤Î»È¤¤ÊýÅù¤ÏŬÀڤǤʤ¤¤«¤â¤·¤ì¤Ê¤¤¤Î¤Ç¤³ ¤ÎÊýÌ̤Ǥâ¸æ»ØƳ失¤ì¤Ð¹¬¤¤¤Ç¤¢¤ë¡£ +< Ìܼ¡ > + +ɽµ­¤Ë¤Ä¤¤¤Æ +slide ¼­½ñË¡ (slide.c) +bit Æþ½ÐÎϥ롼¥Á¥ó (crcio.c) +Huffman Ë¡ (huf.c) +LHA ¥Õ¥¡¥¤¥ë¤Î¹½Â¤(¤Þ¤È¤á) +¥»¥­¥å¥ê¥Æ¥£¥Ð¥°¤Î¹Í»¡ + =============================================================================== -o ɽµ­¤Ë¤Ä¤¤¤Æ +ɽµ­¤Ë¤Ä¤¤¤Æ * ´Ø¿ô¤Ï¡¢¤½¤ÎÄêµÁ¥½¡¼¥¹ file.c ¤È´Ø¿ô̾ func() ¤ò¼¨¤¹¤Î¤Ë file.c:func() @@ -532,7 +541,7 @@ hash[] ---------------------------------------------------------------------------- < ½é´ü¾õÂÖ > - + dicsiz=2^dicbit 2*2^dicbit v v txtsiz +-------------+-------------+-------------+-------------+---+ @@ -938,7 +947,7 @@ maxmatch (pos, remainder ¤Ï¡¢get_next() ¤Ç¹¹¿·¤µ¤ì¤Æ¤¤¤ë¤³¤È¤ËÃí°Õ) ---------------------------------------------------------------------------- - + dicsiz=2^dicbit 2*2^dicbit v v txtsiz +-------------+-------------+-------------+-------------+---+ @@ -1131,7 +1140,7 @@ while ¤Ê¤ï¤±¤À¡£¤µ¤é¤Ë¡¢pos¤Ï¸½»þÅÀ¤Ç dicbit+1 ¤Ç¤¢¤ë¤«¤é¡¢1 ¤À¡£¿Þ¤Ë½ñ¤³¤¦¡£ ---------------------------------------------------------------------------- - + dicsiz=2^dicbit 2*2^dicbit v v txtsiz +-------------+-------------+-------------+-------------+---+ @@ -1518,7 +1527,7 @@ remainder ¤Î¾õÂÖ¤À¡£¤³¤ì¤¬¡¢update() ¤ò¸Æ¤Ó½Ð¤¹»þ¤Î½é´ü¾õÂÖ¤À¡£ ---------------------------------------------------------------------------- - + dicsiz=2^dicbit 2*2^dicbit v v txtsiz +-------------+-------------+-------------+-------------+---+ @@ -1581,7 +1590,7 @@ static void update() ¤ì¤Æ¤¤¤ë¡£¤³¤ì¤Ï¤Ä¤Þ¤ê¿Þ¼¨¤¹¤ë¤È¡¢°Ê²¼¤Î¾õÂ֤ˤʤë¤È¸À¤¦»ö¤À ---------------------------------------------------------------------------- - + dicsiz=2^dicbit 2*2^dicbit v v txtsiz +-------------+-------------+---+---------+-------------+---+ @@ -2506,7 +2515,7 @@ putcode() +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |* * * |x y z | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - / / <-n-> + / / <-n-> subbitbuf x <--------> bitcount @@ -2561,6 +2570,7 @@ init_putbits() ¤Æ¤¤¤ë¤Î¤Ï LHa ¤Ë¤È¤Ã¤Æ½ÅÍפʻö¤À¡£decode ½èÍý¤Ç¤ÏľÀÜ bitbuf ¤ò»²¾È¤¹ ¤ë²Õ½ê¤¬¤¢¤ë¡£ + Huffman Ë¡ (huf.c) ------------------ @@ -2959,7 +2969,7 @@ left[0...nparm], right[0...nparm] Îã: . -- k (= avail-1) / \ - left[k] -- . \ + left[k] -- . \ /\ \ a b c -- right[k] | \ @@ -3111,7 +3121,7 @@ count_len() len_cnt[16] 0.. 2^16°Ê¾å 17¥Ó¥Ã¥È°Ê¾å len_cnt[15] 0.. 2^15 16¥Ó¥Ã¥È len_cnt[14] 0.. 2^14 15¥Ó¥Ã¥È - : + : len_cnt[ 3] 0.. 2^3 4 ¥Ó¥Ã¥È len_cnt[ 2] 0.. 2^2 3 ¥Ó¥Ã¥È len_cnt[ 1] 0.. 2^1 2 ¥Ó¥Ã¥È @@ -3334,7 +3344,7 @@ make_code(n, len, code) # ¸å¤Çµ¤¤¬¤Ä¤¤¤¿¤³¤È¤À¤¬¡¢¤¢¤é¤«¤¸¤áÀßÄꤷ¤Æ¤¤¤¿ codeparm[] ¤ÎÆâÍƤϤ³ # ¤³¤Ç¤Ï»ÈÍѤµ¤ì¤Ê¤¤¡£¤Ä¤Þ¤ê¡¢codeparm[] ¤ÏÀèÄø¤Ï¥ï¡¼¥¯ÍѤΥХåե¡¤È # ¤·¤ÆÍøÍѤµ¤ì¤Æ¤¤¤¿¤¬¡¢¤³¤³¤Ç¤Î codeparm[] ¤Ï½èÍý·ë²Ì¤òɽ¤¹¤È¤¤¤¦Æó¤Ä -# ¤ÎÌò³ä¤¬¤¢¤ë +# ¤ÎÌò³ä¤¬¤¢¤ë¡£¤³¤ì¤Ï¡¢Îΰè¤òÀáÌ󤹤뤿¤á¤ÎÊÑ¿ô¤Î»È¤¤²ó¤·¤À¡£ ºÇ½é¤Î for ʸ¤Ç¤Ï¡¢ÊÑ¿ô i ¤ËÂФ·¤Æ¡¢weight[i] ¤¬²¼¤Î¤è¤¦¤ËÀßÄꤵ¤ì¤ë @@ -3345,7 +3355,7 @@ make_code(n, len, code) start[1] = 0 start[n] = start[n-1] + weight[n-1] * len_cnt[n-1] (n > 1) -¤È¤¤¤¦Á²²½¼°¤À¡£starr[] ¤Îź»ú i ¤Ï¡¢len_cnt[i](¿¼¤µ i ¤ÎÍդοô)¤Îź»ú +¤È¤¤¤¦Á²²½¼°¤À¡£start[] ¤Îź»ú i ¤Ï¡¢len_cnt[i](¿¼¤µ i ¤ÎÍդοô)¤Îź»ú ¤Ç¤â¤¢¤ë¤³¤È¤«¤é¡¢¥Ï¥Õ¥Þ¥óÌڤο¼¤µ¤òɽ¤·¤Æ¤¤¤ë¡£start ¤¬¼ÂºÝ¤Ë¤É¤Î¤è¤¦ ¤ÊÃͤò¼è¤ë¤«¤È¸À¤¦¤È¡¢Î㤨¤Ð len_cnt[i] ¤Î³ÆÍ×ÁǤ¬ Li ¤Ç¤¢¤Ã¤¿¾ì¹ç¡¢ @@ -3470,7 +3480,7 @@ codeparm[c] } while (--cum); } -¿¼¤µ n ¤ÎÍդοô¤ò 1 ¤Ä¸º¤é¤·¤Æ¡¢¤½¤Î²¼¤ÎÍդοô¤ò 2 ­¤·¤Æ¤¤¤ë¡£ +¿¼¤µ i ¤ÎÍդοô¤ò 1 ¤Ä¸º¤é¤·¤Æ¡¢¤½¤Î²¼¤ÎÍդοô¤ò 2 ­¤·¤Æ¤¤¤ë¡£ ¤³¤ì¤¬¡¢cum ¤Î¿ô¤À¤±·«¤êÊÖ¤µ¤ì¤ë¡£Î㤨¤Ð¡¢Á°¤Ë¤â½Ð¤¿ : @@ -3576,8 +3586,8 @@ c_freq[] ¤È¤¤¤¦´Ø·¸¤Î¤è¤¦¤À¡£¤É¤¦¤ä¤é c_code¡¢pt_code ¤È¤¤¤¦ 2 ¼ïÎà¤Î Huffman Éä¹æɽ¤ò»ÈÍѤ¹¤ë¤é¤·¤¤¡£ -# ¤¢¤È¤Ç¤ï¤«¤ë¤³¤È¤À¤¬¼ÂºÝ¤Ï3¼ïÎà¤ÎHuffmanÉä¹æɽ¤òºî¤Ã¤Æ¤ª¤ê -# pt_code¤ÏÊÑ¿ô¤¬»È¤¤²ó¤·¤µ¤ì¤Æ¤¤¤ë¡£ÊÑ¿ô¤Î»ÈÍÑÎΰè¤ò¸º¤é¤· +# ¤¢¤È¤Ç¤ï¤«¤ë¤³¤È¤À¤¬¼ÂºÝ¤Ï 3 ¼ïÎà¤Î Huffman Éä¹æɽ¤òºî¤Ã¤Æ¤ª¤ê +# pt_code ¤ÏÊÑ¿ô¤¬»È¤¤²ó¤·¤µ¤ì¤Æ¤¤¤ë¡£ÊÑ¿ô¤Î»ÈÍÑÎΰè¤ò¸º¤é¤· # ¤¿¤«¤Ã¤¿¤Î¤À¤í¤¦¡£ ¤½¤Î¾¤ÎÊÑ¿ô¤Ë´Ø¤·¤Æ¤âͽÁÛ¤òΩ¤Æ¤¿¤¤½ê¤À¤¬¡¢¤â¤¦¤¯¤¸¤±¤¿¤Î¤Ç¡¢½èÍýÆâÍÆ @@ -3857,9 +3867,10 @@ buf | 40 | c1 | c2 |len | off | c4 |len | off | c6 | c7 | c8 | ---------------------------------------------------------------------------- ¤³¤Î¤è¤¦¤Ê¾õÂ֤ˤʤ俤Ȥ­¤È¤¤¤¦¤³¤È¤À¡£¤µ¤é¤Ë¡¢buf[cpos] ¤Ë¤Ï¡¢ - ¤¬³ÊǼ¤µ¤ì¤Æ¤¤¤ë°ÌÃÖ¤òɽ¤·¤Æ¤¤¤ë¡£¤³¤Î¾õÂÖ¤ò 1 ¥Ö¥í¥Ã¥¯¤È¤· -¤Æ¤³¤Î¥Ö¥í¥Ã¥¯Ã±°Ì¤Ë¾ðÊó¤¬ buf ¤Ë³ÊǼ¤µ¤ì¡¢buf ¤¬¤¤¤Ã¤Ñ¤¤¤Ë¤Ê¤Ã¤¿¤é -(A) ¤Î½èÍý¤Î̵»ë¤·¤¿if ʸ¤ÎÃæ¿È¤Ç + ¤¬³ÊǼ¤µ¤ì¤Æ¤¤¤ë°ÌÃÖ¤òɽ¤·¤Æ¤¤¤ë¡£¤³¤Î¾õÂÖ¤ò 1 ¥»¥°¥á¥ó¥È¤È¸Æ +¤Ö¤³¤È¤Ë¤·¤è¤¦¡£¤½¤·¤Æ¤³¤Î¥»¥°¥á¥ó¥Èñ°Ì¤Ë¾ðÊó¤¬ buf ¤Ë³ÊǼ¤µ¤ì¡¢buf ¤¬ +¤¤¤Ã¤Ñ¤¤¤Ë¤Ê¤Ã¤¿¤é¤³¤Î¥»¥°¥á¥ó¥È¤Î½¸¤Þ¤ê¤ò 1 ¥Ö¥í¥Ã¥¯¤È¤·¤Æ (A) ¤Î½èÍý +¤Î̵»ë¤·¤¿if ʸ¤ÎÃæ¿È¤Ç if (output_pos >= bufsiz - 3 * CHAR_BIT) { send_block(); @@ -3875,20 +3886,24 @@ buf | 40 | c1 | c2 |len | off | c4 |len | off | c6 | c7 | c8 | ¤·¤Æ¤â¥Ð¥Ã¥Õ¥¡¤ò¤Á¤ç¤Ã¤È¤À¤±ÌµÂ̤ˤ·¤Æ¤¤¤ë¤À¤±¤Ê¤Î¤ÇÂ礷¤¿¤³¤È¤Ï¤Ê¤¤¤Î ¤À¤í¤¦) -# ¤É¤¦¤ä¤é¥Ð¥°¤Ç¤Ï¤Ê¤¤¤é¤·¤¤¡£3 * CHAR_BIT ¤È¤¤¤¦¤Î¤Ï¡¢1¥Ö¥í¥Ã¥¯¤¬ -# CHAR_BIT ¤Î¥¹¥í¥Ã¥È(8 ¤Ä¤Î¥¹¥í¥Ã¥È)¤ò»ý¤Á¡¢1 ¥Ö¥í¥Ã¥¯¤¬¤¹¤Ù¤Æ -# (3 bytes)¤Î¾ì¹ç¡¢ºÇÂç 3 bytes * 8 ¤È¤Ê¤ë¤³¤È¤ò¼¨¤·¤Æ¤¤¤ë¤è -# ¤¦¤À¡£ +# ¤É¤¦¤ä¤é¥Ð¥°¤Ç¤Ï¤Ê¤¤¤é¤·¤¤¡£3 * CHAR_BIT ¤È¤¤¤¦¤Î¤Ï¡¢1 ¥»¥°¥á¥ó¥È¤¬ +# CHAR_BIT ¤Î¥¹¥í¥Ã¥È(8 ¤Ä¤Î¥¹¥í¥Ã¥È)¤ò»ý¤Á¡¢1 ¥»¥°¥á¥ó¥ÈÆâ¤Î¥¹¥í¥Ã¥È¤¬ +# ¤¹¤Ù¤Æ (3 bytes)¤Î¾ì¹ç¡¢ºÇÂç 3 bytes * 8 ¤È¤Ê¤ë¤³¤È¤ò¼¨¤·¤Æ +# ¤¤¤ë¤è¤¦¤À¡£ # CHAR_BIT ¤Ï¡¢buf[cpos] ¤Î¥Ó¥Ã¥È¿ô¤òɽ¤·¤Æ¤¤¤ë¡£ # -# ¼ÂºÝ¤Î¤È¤³¤í1¥Ö¥í¥Ã¥¯¤Ï¡¢buf[cpos]¤Î1 byte¤¬ÀèƬ¤ËɬÍפʤΤǺÇÂ祵¥¤¥º¤Ï +# ¼ÂºÝ¤Î¤È¤³¤í 1 ¥»¥°¥á¥ó¥È¤Ï¡¢buf[cpos] ¤ÎÎΰè 1 byte ¤¬ÀèƬ¤ËɬÍפʤΠ+# ¤ÇºÇÂ祵¥¤¥º¤Ï # 3 * CHAR_BIT + 1 # ¤È¤Ê¤ë¡£¤½¤¦¤¤¤¦°ÕÌ£¤Ç¤Ï¡¢ -# if (output_pos > bufsiz - (3 * CHAR_BIT + 1)) { +# if (buf ¤Î»Ä¤ê¥µ¥¤¥º < ºÇÂ祵¥¤¥º) { +# ¤È¤¤¤¦·Á¼°¡£¤Ä¤Þ¤ê¡¢ +# if (bufsiz - output_pos < 3 * CHAR_BIT + 1) { # ¤ÎÊý¤¬¤ï¤«¤ê¤ä¤¹¤¤¤è¤¦¤Ë»×¤¦¡£ -output_pos = 0 ¤È¤·¤Æ¤¤¤ë¤³¤È¤«¤é¤³¤Î»þÅÀ¤Î buf ¤ÎÃæ¿È¤¬¤¹¤Ù¤Æ -send_block() ¤Ç°µ½Ì¤µ¤ì¥Õ¥¡¥¤¥ë¤Ë½ÐÎϤµ¤ì¤ë¤À¤í¤¦¤³¤È¤¬ÁÛÁü¤Ç¤­¤ë¡£ +output_pos = 0 ¤È¤·¤Æ¤¤¤ë¤³¤È¤«¤é¤³¤Î»þÅÀ¤Î buf ¤ÎÃæ¿È(¥»¥°¥á¥ó¥È¤Î½¸¤Þ +¤ê=1 ¥Ö¥í¥Ã¥¯)¤¬¤¹¤Ù¤Æ send_block() ¤Ç°µ½Ì¤µ¤ì¥Õ¥¡¥¤¥ë¤Ë½ÐÎϤµ¤ì¤ë¤À¤í +¤¦¤³¤È¤¬ÁÛÁü¤Ç¤­¤ë¡£ ¤³¤Î 1 ¥Ö¥í¥Ã¥¯¤ËËþ¤¿¤Ê¤¤¾õÂ֤ǥե¡¥¤¥ë¤Î½ª¤ê¤¬Í褿¾ì¹ç¡¢¸å½èÍý encode_end_st1() ¤Ç send_block() ¤¬¸Æ¤Ð¤ì¤ë¤Ç¤¢¤í¤¦¤³¤È¤âÁÛÁü¤Ç¤­¤ë¡£ @@ -3984,7 +3999,7 @@ make_tree() ---------------------------------------------------------------------------- - 16bit + 16bit |---------| +----+----+ | size | @@ -4020,7 +4035,7 @@ root return heap[1]; } -¤È¤¤¤¦Îã³°¾ò·ï¤¬¤¢¤Ã¤¿¡£¤³¤ì¤Ï¡¢°µ½Ì¤¹¤ëʸ»ú¤¬¤Ê¤¤¡¢¤¢¤ë¤¤¤Ï1¼ïÎष¤« +¤È¤¤¤¦Îã³°¾ò·ï¤¬¤¢¤Ã¤¿¡£¤³¤ì¤Ï¡¢°µ½Ì¤¹¤ëʸ»ú¤¬¤Ê¤¤¡¢¤¢¤ë¤¤¤Ï 1 ¼ïÎष¤« ¤Ê¤¤¾ì¹ç¤Î½èÍý¤À¡£°µ½Ì¤¹¤ëʸ»ú¤¬¤Ê¤¤¾ì¹ç¤Ë send_block() ¤¬¸Æ¤Ð¤ì¤ë¤³¤È ¤Ï¤Ê¤¤¤À¤í¤¦¤«¤é¡¢(B) ¤Î½èÍý¤Î else ¤Ï 1 ¥Ö¥í¥Ã¥¯Ãæ¤Ë°µ½Ì¤¹¤ëʸ»ú¤¬ 1 ¼ïÎष¤«¤Ê¤¤¾ì¹ç¤Î½èÍý¤Ç¤¢¤ë(¤³¤Î 1 ¼ïÎà¤Îʸ»ú¤È¤Ï¡¢make_tree() ¤ÎÌá¤ê @@ -4036,9 +4051,9 @@ root ---------------------------------------------------------------------------- -¤³¤ì¤¬¡¢1¥Ö¥í¥Ã¥¯¤Ë1¼ïÎष¤«Ê¸»ú¤¬¤Ê¤¤¾ì¹ç¤Î½ÐÎϤÀ(off¤Î¾ðÊó¤Ï¤Þ¤À´Þ¤Þ -¤Ê¤¤)¡£(B)¤Î if ¤¬¿¿¤Î¤È¤­¤¬¤É¤¦¤Ê¤ë¤«¤ÏÊ£»¨¤½¤¦¤Ê¤Î¤Ç¸å¤Ç¸«¤ë¤³¤È¤Ë¤· -¤è¤¦¡£ +¤³¤ì¤¬¡¢1 ¥Ö¥í¥Ã¥¯¤Ë 1 ¼ïÎष¤«Ê¸»ú¤¬¤Ê¤¤¾ì¹ç¤Î½ÐÎϤÀ(off ¤Î¾ðÊó¤Ï¤Þ¤À +´Þ¤Þ¤Ê¤¤)¡£(B)¤Î if ¤¬¿¿¤Î¤È¤­¤¬¤É¤¦¤Ê¤ë¤«¤ÏÊ£»¨¤½¤¦¤Ê¤Î¤Ç¸å¤Ç¸«¤ë¤³¤È +¤Ë¤·¤è¤¦¡£ ³¤¤¤Æ (C) @@ -4115,7 +4130,7 @@ flags } else encode_c(buf[pos++]); -flags ¤Î7¥Ó¥Ã¥ÈÌÜ(127)¤¬Î©¤Ã¤Æ¤¤¤ë¤È¤­ buf[pos] ¤Ï¡¢ ¤ò»Ø¤·¡¢ +flags ¤Î 7 ¥Ó¥Ã¥ÈÌÜ(128)¤¬Î©¤Ã¤Æ¤¤¤ë¤È¤­ buf[pos] ¤Ï¡¢ ¤ò»Ø¤·¡¢ encode_c(len + 256) encode_p(off) @@ -4198,6 +4213,48 @@ off |0000 0000 0100 0000| for (i = 0; i < np; i++) p_freq[i] = 0; +¤³¤³¤Ç¡¢ÉÑÅÙɽ¤ò¥¯¥ê¥¢¤·¤Æ¤¤¤ë¤È¤¤¤¦¤³¤È¤Ïʸ»ú¤ä°ÌÃ֤νи½²ó¿ô¤Ï 1 ¥Ö¥í¥Ã¥¯ +ñ°Ì¤Ç¤·¤«·×¾å¤·¤Ê¤¤¤³¤È¤òɽ¤¹¡£ + +# °ìÊý¡¢c_freq ¤ä p_freq ¤Ï unsigned short ¤Ç¤¢¤ë¤«¤é(16 bit ¤À¤È¤· +# ¤Æ)65535 ¤Þ¤Ç¤·¤«¿ô¤¨¤é¤ì¤Ê¤¤¡£¤µ¤é¤Ë¡¢{c,p}_freq ¤Ë¤Ï Huffman Ìڤι½ +# ÃۤβáÄø¤Ç½Ð¸½²ó¿ô¤ÎÁíϤ¬¥»¥Ã¥È¤µ¤ì¤ë¾ì¹ç¤¬¤¢¤ë¤³¤È¤«¤é 1 ¥Ö¥í¥Ã¥¯¤Ë +# ¤Ï 65535 ʸ»ú + 65535 ¸Ä¤Î°ÌÃ֤ޤǤ·¤«³ÊǼ¤Ç¤­¤Ê¤¤¡£ +# ¤¤¤ä¡¢°ÌÃÖ¤Ïɬ¤ºÄ¹¤µ¤È¥»¥Ã¥È¤Ç¤¢¤ë¤³¤È¤«¤é¡£°ÌÃ֤νи½²ó¿ô¤Ïʸ»ú¤Î½Ð +# ¸½²ó¿ô(¤³¤ì¤ÏŤµ¤Î½Ð¸½²ó¿ô¤ò´Þ¤à)¤Ë´Þ¤Þ¤ì¤ë¤¿¤á 65535 ¥¹¥í¥Ã¥È¤Þ¤Ç¤· +# ¤« buf ¤ò»ý¤Æ¤Ê¤¤¤³¤È¤Ë¤Ê¤ë¡£¤³¤ì¤Ï blocksize (16 bit)¤È¤â°ìÃפ¹¤ë¡£ +# +# buf ¤ÎÎΰè³ÎÊݤϰʲ¼¤Î¤è¤¦¤Ë¤Ê¤Ã¤Æ¤¤¤¿¡£ +# +# unsigned char * +# alloc_buf( /* void */ ) +# { +# bufsiz = 16 * 1024 *2; /* 65408U; */ /* t.okamoto */ +# while ((buf = (unsigned char *) malloc(bufsiz)) == NULL) { +# bufsiz = (bufsiz / 10) * 9; +# if (bufsiz < 4 * 1024) +# break; +# } +# return buf; +# } +# +# ¤³¤ì¤«¤é¡¢bufsiz ¤Ï¡¢16 * 1024 *2 = 2^4 * 2^10 * 2 = 2^15 ¤Ç¤¢¤ë¡£ +# 1 ¥»¥°¥á¥ó¥È¤ÎºÇ¾®¥µ¥¤¥º¤¬¥Ð¥¤¥È¿ô¤Ç(1*CHAR_BIT+1)¤Ç¤¢¤ë¤«¤é +# ¤³¤ÎÎΰè¤Ë³ÊǼ¤Ç¤­¤ëºÇÂ祻¥°¥á¥ó¥È¿ô¤Ï¡¢ +# 2^15 / (1*CHAR_BIT+1) +# ¤Ç¤¢¤ê¡¢1 ¥»¥°¥á¥ó¥È¤Ï 8 ¥¹¥í¥Ã¥È¤¢¤ë¤«¤é¡¢ºÇÂ祹¥í¥Ã¥È¿ô¤Ï +# 8 * 2^15 / (1*CHAR_BIT+1) +# = 2^18 / 9 +# = 29127.1111111111 +# ¤È¤Ê¤ë¡£¤³¤ì¤Ï¡¢ÉÑÅÙɽ¤Î¾å¸Â(¥¹¥í¥Ã¥È¿ô¤Î¾å¸Â) +# 65535=2^16-1 +# ¤è¤ê¤â¾®¤µ¤¤¤Î¤ÇÌäÂê¤Ï¤Ê¤¤¤³¤È¤Ë¤Ê¤ë¡£ +# +# ¤Ê¤ª¡¢1 ¥Ö¥í¥Ã¥¯¤Î¥µ¥¤¥º¤Ï¤³¤Î¥Ð¥Ã¥Õ¥¡¥µ¥¤¥º¤Ë¤è¤ê·è¤Þ¤ë¤ï¤±¤À¤¬ 1 ¥Ö +# ¥í¥Ã¥¯¤Î¥µ¥¤¥º¤¬Â礭¤±¤ì¤ÐÂ礭¤¤¤Û¤É¤è¤¤¤È¤¤¤¦¤ï¤±¤Ç¤Ï¤Ê¤¤¡£¤à¤·¤í¡¢ +# ʸ»ú¤Î½Ð¸½³ÎΨ¤ÎÊÑÆ°¤ËÄɿ魯¤ë¤¿¤á¤Ë¤Ï¾®¤µ¤¤Êý¤¬¤è¤¤¤Î¤À¤¬¤½¤¦¤¹¤ë¤È +# Huffman ÌڤγÊǼ²ó¿ô¤¬Áý¤¨¤ë¤Î¤Ç´Êñ¤Ë¤ÏºÇŬÃͤϷè¤Þ¤é¤Ê¤¤¡£ + °Ê¾å¤Ç¡¢°µ½Ì½èÍýÁ´ÂΤγµÍפ¬¤ï¤«¤Ã¤¿¡£¸å¤Ï̵»ë¤·¤Æ¤¤¤¿ Huffman ɽ¤ò½Ð ÎϤ¹¤ë²Õ½ê¤À¤±¤À¡£ @@ -4290,7 +4347,7 @@ count c_len[i] count t_freq[] ------------------------------------------- - 0 0 .. 2 t_freq[0] += count + 0 1 .. 2 t_freq[0] += count 0 3 ..18 t_freq[1]++ 0 19 t_freq[0]++, t_freq[1]++ 0 20°Ê¾å t_freq[2]++ @@ -4341,12 +4398,12 @@ pt_len[] ¤Ð¡¢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 ¤¬½ÐÎϤµ¤ì¤ë¡£¤³¤Î¤è¤¦¤Ê¤³¤È¤ò¤·¤Æ¤¤¤ë°ÕÌ£¤Ï¤³¤ì -¤Þ¤¿¤è¤¯¤ï¤«¤é¤Ê¤¤¡£¤Á¤ç¤Ã¤ÈÊ£»¨¤Ê¤Î¤Ç¿Þ¼¨¤·¤Æ¤ß¤¿¡£ +¤µ¤é¤Ë¡¢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..5] ¤ò½ÐÎϤ»¤º¤Ë¡¢i - 3 (= 3) ¤ò +2 bit ½ÐÎϤ¹¤ë¡£¤Ä¤Þ¤ê¡¢11 ¤¬½ÐÎϤµ¤ì¤ë¡£¤³¤Î¤è¤¦¤Ê¤³¤È¤ò¤·¤Æ¤¤¤ë°ÕÌ£¤Ï +¤³¤ì¤Þ¤¿¤è¤¯¤ï¤«¤é¤Ê¤¤¡£¤Á¤ç¤Ã¤ÈÊ£»¨¤Ê¤Î¤Ç¿Þ¼¨¤·¤Æ¤ß¤¿¡£ ---------------------------------------------------------------------------- < pt_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > @@ -4370,12 +4427,14 @@ pt_len[i] >= 7 pt_len[i] |1 1 1 1 ... 1 0 | +----------------+ -pt_len[i_special] ¤Îľ¸å¤Ï 2 bit ¤Î¾ðÊó¤¬Éղ䵤ì¤ë¡£¤³¤ÎÃͤò x ¤È¤¹¤ë -¤È¡¢pt_len[i_special .. x + 3] ¤ÎÈÏ°Ï¤Ç 0 ¤¬Â³¤¯¤³¤È¤ò°ÕÌ£¤¹¤ë¡£ +pt_len[i_special-1] ¤Îľ¸å¤Ï 2 bit ¤Î¾ðÊó¤¬Éղ䵤ì¤ë¡£¤³¤ÎÃͤò x ¤È¤¹¤ë +¤È¡¢pt_len[i_special .. x + 2] ¤ÎÈÏ°Ï¤Ç 0 ¤¬Â³¤¯¤³¤È¤ò°ÕÌ£¤¹¤ë¡£x ¤¬ 0 +¤Ê¤é pt_len[i_special] ¤Ï 0 ¤Ç¤Ï¤Ê¤¤¡£ ---------------------------------------------------------------------------- -ºÇ¸å¤Ë¡¢write_c_len() ¤Ç¡¢Éä¹æɽ c_len[] ¤È pt_code[] ¤ò½ÐÎϤ¹¤ë¡£ +ºÇ¸å¤Ë¡¢write_c_len() ¤Ç¡¢Huffman Éä¹æ¤Î¥Ó¥Ã¥ÈĹ c_len[] (¤Î Huffman Éä +¹æɽ pt_code[]) ¤ò½ÐÎϤ¹¤ë¡£ static void write_c_len(/*void*/) @@ -4433,10 +4492,10 @@ c_len[i] == 0 0 ¤¬Â³¤¯¿ô¤ò count ¤È¤¹¤ë¤È¡¢ - count == 0..2 ¤Î¾ì¹ç + count == 1..2 ¤Î¾ì¹ç - pt_len[0] - <----------> + pt_len[0] + <----------> +------------+ | pt_code[0] | +------------+ @@ -4480,6 +4539,11 @@ c_len[i] != 0 ¤«¤é·×»»¤·¤Æµá¤á¤Æ¤¤¤ë¤Î¤Ç¤Ï¤Ê¤¤¤«¤È»×¤ï¤ì¤ë¡£¤³¤ì¤Ï decode ½èÍý¤Î²òÆÉ ¤ÇÌÀ¤é¤«¤Ë¤Ê¤ë¤À¤í¤¦¡£ +# ¾¯¤·ÊѤʤ³¤È¤ò½ñ¤¤¤Æ¤¤¤ë¡£pt_code[] ¤Î½ÐÎϤϡ¢c_len[] ¤Î Huffman Éä¹æ +# ¤ò½ÐÎϤ·¤Æ¤¤¤ë¤Î¤Ç¤¢¤ê¡¢Huffman ÌڤξðÊó¤È¤·¤Æ½ÐÎϤ·¤Æ¤¤¤ë¤ï¤±¤Ç¤Ï¤Ê +# ¤¤¡£¤Ä¤Þ¤ê¡¢c_code[] ¤¬½ÐÎϤµ¤ì¤Æ¤¤¤Ê¤¤¤Î¤ÈƱÍÍ¤Ë pt_code[] ¤â½ÐÎÏ¤Ï +# ¤·¤Æ¤¤¤Ê¤¤¡£ + ¤³¤Î¸å¡¢send_block() ¤Ï¡¢(C) ¤Ç¡¢ ¤Î Huffman Éä¹æɽ¤ò½ÐÎϤ¹¤ë¤Î¤À ¤¬¡¢ @@ -4487,13 +4551,13 @@ c_len[i] != 0 ¤³¤ì¤Ï¡¢Àè¤Î pt_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È¤ÈƱ¤¸¤Ê¤Î¤Ç¾ÜºÙ¤Ï¤Ï¤·¤ç¤í¤¦¡£ ¤¿¤À¤·¡¢º£Å٤Πpt_len[] ¤Î½ÐÎÏ¤Ç¤Ï write_pt_len() ¤ÎÂè»°°ú¿ô i_special -¤¬ -1 ¤Ç»ØÄꤵ¤ì¤Æ¤¤¤Æ¡¢i_special ÈÖÌܤΠpt_len[i_special..6] ¤Ë´Ø¤·¤Æ +¤¬ -1 ¤Ç»ØÄꤵ¤ì¤Æ¤¤¤Æ¡¢i_special ÈÖÌܤΠpt_len[i_special..5] ¤Ë´Ø¤·¤Æ ÆÃÊÌ°·¤¤¤¬¤Ê¤¯¤Ê¤Ã¤Æ¤¤¤ë¤È¤³¤í¤¬°Û¤Ê¤ë¡£ np ¤ä pbit ¤Î°ÕÌ£¤â¤³¤Î»þÅÀ¤Ç¤ï¤«¤ë¤Î¤Ç°ì±þÀâÌÀ¤·¤Æ¤ª¤¯¡£np, pbit ¤½¤· -¤Æ¡¢LHA ¤Î°µ½Ì method ¤È¤Î´Ø·¸¤Ï°Ê²¼¤Îɽ¤ÎÄ̤ê¤Ê¤Î¤À¤¬¡¢np ¤Ï¡¢¤Î -ºÇÂçbitĹ+1 ¤À¡£ ¤ÎºÇÂçbitĹ¤Ï¤¹¤Ê¤ï¤Á dicbit ¤Ê¤Î¤Ç¡¢np ¤Ï¡¢ -dicbit + 1 ¤Ç¤¢¤ë¡£-lh4- ¤Î¤È¤­¤Ëdicbit + 2 ¤Ê¤Î¤¬ÉԻ׵ĤÀ¤¬¡¢¤³¤ì¤ÏÎò +¤Æ¡¢LHA ¤Î°µ½Ì method ¤È¤Î´Ø·¸¤Ï°Ê²¼¤Îɽ¤ÎÄ̤ê¤Ê¤Î¤À¤¬¡¢np ¤Ï¡¢ ¤Î +ºÇÂç bit Ĺ + 1 ¤À¡£ ¤ÎºÇÂç bit Ĺ¤Ï¤¹¤Ê¤ï¤Á dicbit ¤Ê¤Î¤Ç¡¢np ¤Ï¡¢ +dicbit + 1 ¤Ç¤¢¤ë¡£-lh4- ¤Î¤È¤­¤Ë dicbit + 2 ¤Ê¤Î¤¬ÉԻ׵ĤÀ¤¬¡¢¤³¤ì¤ÏÎò »ËŪ¤ÊÍýͳ¤À¤í¤¦¤È»×¤ï¤ì¤ë¡£pbit ¤Ï¡¢ÃÍ np ¤ò½ÐÎϤ¹¤ë¤Î¤ËɬÍ×¤Ê bit ¿ô ¤Ê¤Î¤Çɽ¤ÎÄ̤ê¤Ë¤Ê¤ë¡£ @@ -4620,9 +4684,8 @@ blocksize == 0 } ¤È¡¢¤¤¤í¤¤¤í¤È¤ä¤Ã¤Æ¤¤¤ë¤¬¤³¤ÎÉôʬ¤Ï¤¹¤°ÁÛÁü¤¬¤Ä¤¯¡£< LHA ¥Õ¥¡¥¤¥ë¤Î¹½ -¤ > ¤Î¥Ï¥Õ¥Þ¥óÉä¹æɽ¤òÆɤ߹þ¤ó¤Ç¤¤¤ë¤Î¤À¤í¤¦¡£¤½¤¦¤·¤Æ¡¢°ìÅÙÆɤ߹þ¤ó -¤À¸å¤Ï¸å³¤Î½èÍý¤Ç 1 ¥Ö¥í¥Ã¥¯Ê¬(blocksize ʬ)´°Î»¤¹¤ë¤Þ¤Ç decode ¤ò¹Ô -¤¦¤À¤±¤À¡£ +¤ > ¤Î¥Ï¥Õ¥Þ¥óÉä¹æɽ¤òÆɤ߹þ¤ó¤Ç¤¤¤ë¤Î¤À¤í¤¦¡£¤½¤¦¤·¤Æ¡¢°ìÅÙÆɤ߹þ¤ó¤À +¸å¤Ï¸å³¤Î½èÍý¤Ç blocksize ʬÆɤ߹þ¤à¤Þ¤Ç decode ¤ò¹Ô¤¦¤À¤±¤À¡£ blocksize--; j = c_table[bitbuf >> 4]; @@ -4860,9 +4923,14 @@ read_c_len( /* void */ ) } ¤³¤Á¤é¤â¡¢< c_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > ¤Ë¤·¤¿¤¬¤Ã¤Æ¡¢c_len[] ¤òÆÉ¤ß -ľ¤·¤Æ¤¤¤ë¤À¤±¤À¡£·ë¶É¥­¥â¤È¤Ê¤ë¤Î¤Ï¡¢make_table() ¤Ë¤¢¤ë¤é¤·¤¤¡£¤³¤Î -´Ø¿ô¤Ë¤è¤ê¡¢Æɤ߹þ¤ó¤À pt_len[], c_len[] ¤«¤é pt_table[], c_table[] -(¤½¤·¤Æ¡¢¥Ï¥Õ¥Þ¥óÌÚ left[], right[])¤ò¹½ÃÛ¤·¤Æ¤¤¤ë¤Î¤À¤í¤¦¡£ +ľ¤·¤Æ¤¤¤ë¤À¤±¤À¡£ +# ¤³¤Î¤¢¤¿¤ê¤Ë¤Ê¤ë¤È²òÀϤ¬¤«¤Ê¤ê»¨¤Ë¤Ê¤Ã¤Æ¤¤¤ë(Åö»þÈè¤ì¤Æ¤¤¤¿¤Î¤À¤í¤¦)¡£ +# ºÇ½ªÅª¤Ë¤Ï¸å½Ò¤Î¡ÖLHA ¥Õ¥¡¥¤¥ë¤Î¹½Â¤(¤Þ¤È¤á)¡×¤Ë¤Æ¡¢ºÆÅÙ¸¡Æ¤¤·¤Ê¤ª¤· +# ¤Æ¤¤¤ë¤Î¤Ç¤½¤Á¤é¤ò¸«¤ÆÍߤ·¤¤¡£ÉÔÌÀ¤À¤Ã¤¿Éôʬ¤â¤³¤³¤Ç¤¹¤Ù¤ÆÌÀ¤é¤«¤Ë¤· +# ¤Æ¤¤¤ë¡£ +·ë¶É¥­¥â¤È¤Ê¤ë¤Î¤Ï¡¢make_table() ¤Ë¤¢¤ë¤é¤·¤¤¡£¤³¤Î´Ø¿ô¤Ë¤è¤ê¡¢Æɤ߹þ¤ó +¤À pt_len[], c_len[] ¤«¤é pt_table[], c_table[] (¤½¤·¤Æ¡¢¥Ï¥Õ¥Þ¥óÌÚ +left[], right[])¤ò¹½ÃÛ¤·¤Æ¤¤¤ë¤Î¤À¤í¤¦¡£ ·ë¶É¡¢decode ½èÍý read_c_len(), read_pt_len() ¤òÆɤó¤Ç¤â¤Ê¤¼¤³¤Î¤è¤¦¤Ê Éä¹æ²½¤ò¹Ô¤Ã¤Æ¤¤¤ë¤Î¤«¤è¤¯¤ï¤«¤é¤Ê¤«¤Ã¤¿¡£²¿¤«Åý·×Ū¤Êº¬µò¤Ç¤â¤¢¤ë¤Î¤À @@ -5043,6 +5111,7 @@ start[i] ¤È¤¤¤¦¥Æ¡¼¥Ö¥ë¤ÎÃͤÏ(tablebits ¤¬ 12 ¤Ç¤¢¤ë¤È¤¹¤ë¤È)¡¢ 00000111 11111111 + <--> (16 - tablebits{12}) = 4 bit ¥·¥Õ¥È ¤ÎÃͤˤ¹¤ë¡£encode ¤¹¤ë¤È¤­¤Ï¡¢16 bit ¤Î¥Æ¡¼¥Ö¥ë¤ò¤½¤Î¤Þ¤Þ»ÈÍѤ·¤Æ¤¤¤¿ ¤Ë¤â´Ø¤ï¤é¤º decode ¤Î¤È¤­¤Ë¤Ï¥Æ¡¼¥Ö¥ë¤Î bit ¿ô¤ò¸º¤é¤·¤Æ¤¤¤ë¤Î¤À¡£¤Þ¤Ã @@ -5065,14 +5134,16 @@ bit 10: c_table[10] = b 11: c_table[11] = c -¤È¤¤¤¦¥Æ¡¼¥Ö¥ë¤òºîÀ®¤¹¤ë¤³¤È¤Ç Huffman Éä¹æ²½¤·¤¿¥Ó¥Ã¥ÈÎ󤫤éÉü¹æ¸ì¤ò -ÆÀ¤ë¡£ +¤È¤¤¤¦¥Æ¡¼¥Ö¥ë¡¢¤Ä¤Þ¤ê + + c_table[HuffmanÉä¹æ]=Éü¹æ¸ì -HuffmanÉä¹æ¤«¤éʸ»ú¤òÆÀ¤ëɬÍפ¬¤¢¤ë¤Î¤Ç¡¢c_table[]¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤Ë¤Ï¡¢ -HuffmanÉä¹æ¤¬¼è¤ê¤¦¤ëºÇÂçÃͤò»ØÄê¤Ç¤­¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£16bit ¤ÎHuffman -Éä¹æ¤ÎºÇÂçÃÍ¤Ï 65535 ¤Ç¤¢¤ë¤«¤é +¤òºîÀ®¤¹¤ë¤³¤È¤Ç Huffman Éä¹æ²½¤·¤¿¥Ó¥Ã¥ÈÎ󤫤éÉü¹æ¸ì¤òÆÀ¤é¤ì¤ë¤è¤¦¤Ë¤¹ +¤ë¡£¤½¤·¤Æ¡¢Huffman Éä¹æ¤«¤éʸ»ú¤òÆÀ¤ëɬÍפ¬¤¢¤ë¤Î¤Ç¡¢c_table[] ¤Î¥¤¥ó +¥Ç¥Ã¥¯¥¹¤Ë¤Ï¡¢Huffman Éä¹æ¤¬¼è¤ê¤¦¤ëºÇÂçÃͤò»ØÄê¤Ç¤­¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£ +16 bit ¤ÎHuffman Éä¹æ¤ÎºÇÂçÃÍ¤Ï 65535 ¤Ç¤¢¤ë¤«¤éɽ°ú¤­¤ËɬÍפÊÊÑ¿ô¤Ï¡¢ - unsigned short c_table[65535+1]; (unsigned short > NC-1) + unsigned short c_table[65535+1]; (unsigned short >= NC-1) ¤È¤Ê¤ë¡£¤ª¤½¤é¤¯É½¤Î bit ¿ô¤ò¸º¤é¤·¤Æ¤¤¤ë¤Î¤Ï¤³¤ÎÂ礭¤Ê¥Æ¡¼¥Ö¥ë¤òºî¤ê¤¿ ¤¯¤Ê¤¤¤«¤é¤Ç¤Ï¤Ê¤¤¤«¤È»×¤ï¤ì¤ë¡£c_table[] ¤ÎÍ×ÁÇ¿ô¤òºÇÄã¸ÂɬÍפʿô¤ËÍÞ @@ -5090,8 +5161,8 @@ Huffman unsigned short c_table[4095+1]; -¤È¤Ê¤Ã¤Æ¤ª¤ê¡¢12 ¥Ó¥Ã¥È(2^12=4096)¤ÎHuffmanÉä¹æ¤Ë¤Ä¤¤¤Æɽ°ú¤­¤¬²Äǽ¤È¤Ê¤Ã -¤Æ¤¤¤ë¡£¤½¤·¤Æ¡¢Éü¹æ¸ì¤Ï¡¢0...NC ¤ÎÈϰϤǤ¢¤ë¤«¤é¡¢ +¤È¤Ê¤Ã¤Æ¤ª¤ê¡¢12 ¥Ó¥Ã¥È(2^12=4096)¤Î Huffman Éä¹æ¤Ë¤Ä¤¤¤Æɽ°ú¤­¤¬²Äǽ¤È +¤Ê¤Ã¤Æ¤¤¤ë¡£¤½¤·¤Æ¡¢Éü¹æ¸ì¤Ï¡¢0...NC ¤ÎÈϰϤǤ¢¤ë¤«¤é¡¢ c_table[¥Ó¥Ã¥ÈÎó] < NC ¤Î¾ì¹ç¤Ï¡¢¤½¤Î¤Þ¤Þɽ°ú¤­¤Ç c_table[¥Ó¥Ã¥ÈÎó] >= NC @@ -5108,29 +5179,87 @@ Huffman : | . ... ³¬ÁØ:11 | / \ | - x x ... ³¬ÁØ:12 .' <- ɽ°ú¤­¤Î·ë²Ì x ¤¬(>=NC)¤Î¾ì¹ç¡¢ + x y ... ³¬ÁØ:12 .' <- ɽ°ú¤­¤Î·ë²Ì y ¤¬(>=NC)¤Î¾ì¹ç¡¢ / \ Ìڤγ¤­¤¬¤¢¤ë¤³¤È¤ò¼¨¤¹ - . . ... ³¬ÁØ:13 `. + z . ... ³¬ÁØ:13 `. | : > left[]/right[]¤Çɽ¸½ (³¬ÁØ12¤¬root) ... ³¬ÁØ:16 .' +---------------------------------------------------------------------------- - ³¬ÁØ 1 ¡Á 12 (1¡Á12bit)¤ÎHuffmanÌڤˤĤ¤¤Æ¤Ï¡¢É½°ú¤­¤ÇÉü¹æ - ³¬ÁØ 13 °Ê¾å¤ÎHuffmanÉä¹æ¤Ë¤Ä¤¤¤Æ¤Ï¡¢ÀèƬ 12 bit¤òɽ°ú¤­¤·¡¢¤½¤ÎÃÍ - ¤ÏNC ¤è¤êÂ礭¤¤ÃͤȤʤ롣 +³¬ÁØ 12 ¤è¤ê²¼(13 °Ê¾å¤Î bit ¿ô¤Î Huffman Éä¹æ)¤Î Huffman ÌڤˤĤ¤¤Æ +left[], right[] ¤Çɽ¤·¤Æ¤¤¤ë¤è¤¦¤À¡£ - ɽ°ú¤­¤·¤¿·ë²Ì¤¬ >= NC ¤Î¾ì¹ç¡¢¤½¤ÎÃͤÏÀá¤ò¼¨¤·¡¢left[ɽ°ú¤­¤ÎÃÍ], - right[ɽ°ú¤­¤ÎÃÍ]¤¬¤½¤Î²¼¤ÎÀá¤ò»Ø¤¹¡£ ----------------------------------------------------------------------------- +¾å¤ÎÎã¤Ç¡¢13 ¥Ó¥Ã¥È¤Î Huffman Éä¹æ¤ÇÉä¹æ²½¤µ¤ì¤ëÉü¹æ¸ì z ¤Ë¤Ä¤¤¤Æ¤Ï¡¢ +y ¤Ë¤½¤ÎÌڤΥ롼¥È¥Î¡¼¥É¤ÎÃÍ(y > NC)¤¬³ä¤êÅö¤Æ¤é¤ì¤ë¡£ -³¬ÁØ12¤è¤ê²¼(13 °Ê¾å¤Î bit ¿ô¤Î Huffman Éä¹æ)¤Î Huffman ÌڤˤĤ¤¤Æ -left[], right[] ¤Çɽ¤·¤Æ¤¤¤ë¤è¤¦¤À¡£¤³¤ÎÌڤΥΡ¼¥É¤ÎÃÍ¤Ï NC °Ê¾å¤Î¿ôÃÍ -¤òÏ¢È֤dzä¤êÅö¤Æ¤Æ¤¤¤ë¤è¤¦¤À(¤³¤ì¤Ë¤Ä¤¤¤Æ¤Ï¸å½Ò¤¹¤ë)¡£ +¿Þ¤«¤éÌÀ¤é¤«¤À¤¬¡¢Éü¹æ¸ì¤½¤Î¤â¤Î¤ò»Ø¤¹ 12 bit ¤ÎÉä¹æ(¤¿¤È¤¨¤Ð x)¤È¡¢ÌÚ +¤Î¥ë¡¼¥È¥Î¡¼¥É¤ò»Ø¤¹ 12 bit ¤ÎÉä¹æ(¤¿¤È¤¨¤Ð y)¤¬Æ±¤¸Éä¹æ¤È¤Ê¤ë¤³¤È¤Ï¤Ê +¤¤¡£¤³¤ì¤Ï Huffman Éä¹æ¤¬¸ìƬ¾ò·ï¤òËþ¤¿¤¹¤«¤é¤Ç¤¢¤ë¡£ + +¤Ç¤Ï¡¢y ¤Ë³ä¤êÅö¤Æ¤ëÃͤϤɤΤ褦¤Ë·è¤Þ¤ë¤«¤È¤¤¤¦¤È¤ª¤½¤é¤¯ NC °Ê¾å¤Î¿ô +ÃͤòÏ¢ÈÖ¤«²¿¤«¤Ç³ä¤êÅö¤Æ¤Æ¤¤¤ë¤Î¤Ç¤Ï¤Ê¤¤¤«¤È»×¤ï¤ì¤ë¡£¤³¤ì¤Ë¤Ä¤¤¤Æ¤Ï¤³ +¤ì°Ê¹ß¤Ç³Îǧ¤¹¤ë¡£ ¤Ê¤ª¡¢³¬Áؤ¬¿¼¤¤ Huffman ÌڤȤϡ¢bit Ť¬Ä¹¤¤Éä¹æ¤Ç¤¢¤ê¡¢bit Ť¬Ä¹¤¤¤È ¤¤¤¦¤³¤È¤Ï½Ð¸½ÉÑÅÙ¤¬Ä㤤¤Ï¤º¤Ç¤¢¤ë¤«¤é¡¢left[], right[] ¤ÇÌÚ¤òé¤ë²ó¿ô ¤Ï¾¯¤Ê¤¤¤Ï¤º¤Ç¤¢¤ë¡£¤³¤ì¤ÏÍý¤Ë¤«¤Ê¤Ã¤Æ¤¤¤ë¡£ +¤¢¤È¡¢¤³¤ÎÌÚ¤ËɬÍפʥµ¥¤¥º¤Ï¤¤¤¯¤Ä¤Ç¤¢¤ë¤«¤È¤¤¤¦ÅÀ¤¬µ¤¤Ë¤Ê¤ë¡£¤³¤ì¤Ï¡¢ +³¬ÁØ 13 °Ê¾å¤Î¥Î¡¼¥É¤Î¿ô¤È¤Ê¤ë¤¬¡¢³¬ÁØ n ¤ÎÆóʬÌڤΥΡ¼¥É(¤³¤³¤Ç¤Ï¡¢ÍÕ +¤ª¤è¤ÓÀá¤ò¥Î¡¼¥É¤È¸Æ¤Ö¤³¤È¤Ë¤·¤Æ¤¤¤ë¡£¡Ö¥Î¡¼¥É¡×¤È¡ÖÀá¡×¤ÏËÜÍèƱ¤¸°ÕÌ£ +¤Ê¤Î¤À¤¬¤â¤¦½ñ¤¤¤Æ¤·¤Þ¤Ã¤¿¤Î¤Ç»ÅÊý¤Ê¤¤)¤Î¿ô¤¬ 2^(n+1) - 1 ¤Ç¤¢¤ë(³¬ÁØ +n ¤ÎÍդοô¤Ï 2^n ¤Ç¡¢Àá¤Î¿ô¤Ï 2^n-1)¤«¤é¡¢ + + ³¬ÁØ 12 ¤Î¥Î¡¼¥É¤Î¿ô¤Ï¡¢(2^(12+1)-1) = 8191 + ³¬ÁØ 16 ¤Î¥Î¡¼¥É¤Î¿ô¤Ï¡¢(2^(16+1)-1) = 131071 + +¤È¤Ê¤ê¡¢¤½¤Îº¹¤Ï 131071 - 8191 = 122880 ¤È¤Ê¤ë¡£Ã±½ã¤Ë¹Í¤¨¤ë¤È¡¢ºÇ°­¤Î +¾ì¹ç¤òÁÛÄꤷ¤Æ left[], right[] ¹ç·×¤Ç 122880 ¸Ä¤ÎÎΰ褬ɬÍפǤ¢¤ë¤³¤È¤Ë +¤Ê¤ë¡£¤½¤¦¤¹¤ë¤ÈÎΰè¤òÀáÌ󤹤ë¤È¤¤¤¦ÌÜŪ¤«¤é¤Ï¸µ¤â»Ò¤â¤Ê¤¤¤³¤È¤È¤Ê¤ë¡£ + +¤·¤«¤·¤è¤¯¤è¤¯¹Í¤¨¤ë¤È¤½¤Î¿´ÇۤϤʤ¤¤è¤¦¤À¡£¼ÂºÝ¤Î¤È¤³¤í¤Ï¥Ï¥Õ¥Þ¥óÌÚÁ´ +ÂΤÎÍդοô¤Ïʸ»ú¼ï¤Î¿ô NC ¤·¤«Â¸ºß¤·¤Ê¤¤¤¿¤á(¥Ï¥Õ¥Þ¥óÌÚ¹½ÃÛ¥¢¥ë¥´¥ê¥º¥à +µÚ¤Ó¥¨¥ó¥³¡¼¥É½èÍý¤ò³Îǧ) 2*NC-1¤¬¥Ï¥Õ¥Þ¥óÌÚÁ´ÂΤΥΡ¼¥É¿ô¤Ç¤¢¤ë¡£¤½¤· +¤Æ¡¢ + + ³¬ÁØ 12 ¤ÎÍդοô¤ÎºÇ¾®ÃÍ 12 + +¤Ç¤¢¤ë¤³¤È¤«¤é¡¢³¬ÁØ13°Ê²¼¤Î¥Î¡¼¥É¿ô¤Ï + + ÌÚ¤Çɽ¸½¤¹¤ëºÇÂç¤ÎÍդοô NC-12 + +¤È¤Ê¤êÌڤΥΡ¼¥É¿ô¤ÎºÇÂçÃÍ¤Ï 2*(NC-12)-1 ¤È¤Ê¤ë¡£¤µ¤é¤Ë¡¢¤³¤ÎÌÚ¤ÎÍÕ¤Ï +left right ¤Îź¤¨»ú¤Ë¤Ê¤é¤Ê¤¤¤Î¤Ç¤½¤Îʬ¤ÎÎΰè¤Ï¸·Ì©¤Ë¤ÏÉÔÍפǤ¢¤ë¡£ + +# ¸å¤Î²òÀϤǤ狼¤ë¤³¤È¤À¤¬¡¢left, right ¤Îź¤¨»ú¤Ï NC °Ê¾å¤Ç¤¢¤ë¤¿¤á +# 0...NC ¤ÎÈϰϤÎÎΰè¤Ï(c_len ¤Ë¤Ä¤¤¤Æ¤Ï)»È¤ï¤ì¤Ê¤¤¡£¤Þ¤¿¡¢ÊÑ¿ô left +# right ¤Ï¥¨¥ó¥³¡¼¥É½èÍý¤Ç¥Ï¥Õ¥Þ¥óÌÚ¤òºî¤ëºÝ¤Ë»ÈÍѤ·¤¿ÊÑ¿ô¤òήÍѤ·¤Æ¤¤ +# ¤ë¤¿¤áÎΰ褬­¤ê¤Ê¤¤¤È¤¤¤¦¤³¤È¤Ï¤Ê¤¤¡£ +# +# ɽ°ú¤­¤ò¹Ô¤ï¤º¤Ë Huffman ÌÚ¤ò´°Á´¤ËÆɤ߹þ¤à¤³¤È¤ò¹Í¤¨¤ë¤È¡¢left, +# right ¤Ï¡¢c_len ¤Ë¤Ä¤¤¤Æ¤Ï¡¢ +# NC ... 2*NC-1 +# ¤¬»ÈÍѤµ¤ì¡¢°ÌÃÖ(p_len)¤ËÂФ¹¤ë Huffman Ìڤι½ÃÛ»þ¤Ë¤Ï +# np ... 2*np-1 +# ¤ÎÈϰϤ¬»ÈÍѤµ¤ì¤ë¡£ +# +# c_len, p_len ¤Î Huffman ÌÚ¤ÏƱ»þ¤Ë¸ºß¤¹¤ë¤Î¤Ç¡¢left, right ¤È¤â¤Ë +# ²¼¿Þ¤ÎÎΰ褬Ʊ»þ¤Ë»ÈÍѤµ¤ì¤ë¤³¤È¤Ë¤Ê¤ë¡£ +# (t_len ¤Ï c_len ¤ÎÆɤ߹þ¤ß¤¬´°Î»¤·¤¿»þÅÀ¤ÇÉÔÍפȤʤ뤿¤á¡¢¤³¤Î¿Þ¤Ë¤Ï +# ɽ¤·¤Æ¤¤¤Ê¤¤) +# +# 0 np 2*np-1 NC 2*NC-1 +# +---------+-------+----------+------------------------------+ +# |̤»ÈÍÑ°è |»ÈÍÑ°è | ̤»ÈÍÑ°è | »ÈÍÑ°è | +# +---------+-------+----------+------------------------------+ +# +# np: 14¡Á17 +# NC: 510 +# +# ¥½¡¼¥¹¤ò¸«¤Æ¤ß¤Æ¤â¡¢¤³¤Î¤³¤È¤Ï¤Ê¤«¤Ê¤«µ¤¤¬¤Ä¤­¤Ë¤¯¤¤¡£¤ä¤Ï¤ê¡¢left, +# right ¤Ï³Æ Huffman Éä¹æÍѤËÎΰè¤ò³ä¤êÅö¤Æ¤¿Êý¤¬¤ï¤«¤ê¤ä¤¹¤¤¤À¤í¤¦¡£ + ³¤­¤ò¸«¤Æ¤¤¤³¤¦¡¢(E) ¤Î½èÍý /* (E) */ @@ -5141,7 +5270,31 @@ left[], right[] for (i = j; i < k; i++) table[i] = 0; -¼¡¤Ë (F) ¤Î½èÍý¡£²¼µ­¤ÎÄ̤ê (F.1), (F.2) ¤ÈºÙʬ²½¤·¤Æ¤ß¤¿¡£ +table[] ¤Î½é´üÃͤȤ·¤Æ 0 ¤òÀßÄꤷ¤Æ¤¤¤ë¡£ + +Huffman Éä¹æ¤Ç¤¢¤ë j ¤Ë¤Ï¡¢start[tablebits + 1] ¤Ä¤Þ¤ê¡¢¥Ó¥Ã¥ÈĹ +tablebits ¤ÎºÇÂç¤Î Huffman Éä¹æ+1¤¬ÀßÄꤵ¤ì¤ë¡£(·«¤êÊÖ¤·¤Ë¤Ê¤ë¤¬¡¢¥Ó¥Ã +¥ÈĹ i ¤Î Huffman Éä¹æ¤Ï¡¢start[i] ¤«¤é start[i+1]-1¤ÎÈϰϤÎÉä¹æ¤Ç¤¢¤ë) +m ¤Ç±¦¥·¥Õ¥È¤·¤Æ¤¤¤ë¤Î¤Ï¡¢(D) ¤Ç¤Ï¡¢tablebits ¤Þ¤Ç¤Î start[i] ¤·¤« ±¦ +¥·¥Õ¥È¤·¤Æ¤¤¤Ê¤¤¤¿¤á¤Ç¤¢¤ë¡£ + +k ¤Ï¡¢1 << tablebits ¤«¤é tablebits + 1 ÈÖÌܤΥӥåȤ¬Î©¤Ã¤¿¿ôÃͤȤʤ롣 +¤³¤ÎÃͤϤĤޤê¤Ï tablebits ¥Ó¥Ã¥È¤Î Huffman Éä¹æ¤ÎºÇÂçÃÍ + 1 ¤Ç¤¢¤ë¡£ + +¤½¤·¤Æ¡¢start[j...k] ¤ÎÈϰϤˤĤ¤¤Æ 0 ¤òÀßÄꤷ¤Æ¤¤¤ë¡£·ë¶É tablebits ¤Î +¥Ó¥Ã¥ÈŤÎÈϰϤdzä¤êÅö¤Æ¤é¤ì¤ë¤³¤È¤¬¤Ê¤¤ Huffman Éä¹æ¤ËÂФ·¤Æ 0 ¤Ç½é´ü +²½¤·¤Æ¤¤¤ë¤È¤¤¤¦¤³¤È¤Î¤è¤¦¤À¡£ +³ä¤êÅö¤Æ¤é¤ì¤ë¤³¤È¤¬¤Ê¤¤ Huffman Éä¹æ¤È¤¤¤¦¤³¤È¤Ï 0 ¤Ç½é´ü²½¤·¤Æ¤¤¤ë¤Î +¤Ï¤³¤Î¸å¤Î½èÍý¤ÇÌڤΥΡ¼¥É¤Ë¤Ê¤ëͽÄê¤ÎÎΰè¤À¤È»×¤ï¤ì¤ë¡£ + +¤Á¤ç¤Ã¤Èµ¿Ìä¤Ê¤Î¤À¤¬¡¢if (j != 0) ¤ÏɬÍפʤΤÀ¤í¤¦¤«¡©¤Ä¤Þ¤ê¡¢j = 0 ¤È +¤·¤Æ¡¢table[] ¤ÎÁ´Í×ÁǤˤĤ¤¤Æ 0 ¤Ç½é´ü²½¤·¤Æ¤â²¿¤âÌäÂê¤Ï¤Ê¤¤¤Î¤Ç¤Ï¤Ê¤¤ +¤«¡©¤½¤·¤Æ¤½¤ì¤Ê¤é make_table() ¤Ë table[] ¤Î¥µ¥¤¥º(sizeof)¤òÅϤ· +memset() ¤Ë¤Æ 0 ¤Ç½é´ü²½¤·¤¿Êý¤¬(µ¡³£¸ì¤ÎÌ¿Îá¿ô¤¬¾¯¤Ê¤¯¤Ê¤ë¤Î¤Ç)®¤¤¤Î +¤Ç¤Ï¤Ê¤¤¤À¤í¤¦¤«¡©¤Þ¤¢¡¢Â®¤µ¤ÏÎɤ¤¤È¤·¤Æ¤â memset() ¤ÎÊý¤¬¤è¤ê¤ï¤«¤ê¤ä +¤¹¤¤¤È»×¤¦¡£ + +¼¡¤Ë (F) ¤Î½èÍý¡£¾¯¤·Â礭¤¤¤Î¤Ç²¼µ­¤ÎÄ̤ê (F.1), (F.2) ¤ÈºÙʬ²½¤·¤Æ¤ß¤¿¡£ /* (F) */ /* create table and tree */ @@ -5182,18 +5335,19 @@ left[], right[] ¤³¤ÎÉôʬ¤Ï°ì»þÊÑ¿ô¤ÎÎ̤¬Â¿¤¤¡¢i,j,k,l,m,n,p ¤Þ¤Ç»È¤ï¤ì¤Æ¤¤¤ë¡£ (¤·¤«¤â¡¢Á°¤Î½èÍý¤Þ¤Ç¤ÈÊÑ¿ô¤ÎÍÑÅÓ¤¬°ã¤Ã¤Æ¤¿¤ê¤¹¤ë¤Î¤Ç¡¢Ê£»¨¤Ë¤Ê¤Ã¤Æ¤¤¤ë) -°ìö¡¢°Ê²¼¤ËÀ°Íý¤·¤Æ¤ß¤¿¡£ + +°ìö¡¢°Ê²¼¤ËÀ°Íý¤·¤Æ¤ß¤¿¡£(¤É¤ÎÊÑ¿ô¤Îź¤¨»ú¤Ë»È¤ï¤ì¤Æ¤¤¤ë¤«¤Ê¤É¤«¤é¤Ò¤È +¤á¤ÇȽÃǤ·¤Æ¤ß¤¿·ë²Ì¤Ç¤¢¤ë¡£¤½¤·¤Æ¡¢n, p ¤Ë¤Ä¤¤¤Æ¤Ï¤Ò¤È¤á¤Ç¤Ï¤ï¤«¤é¤Ê¤«¤Ã +¤¿)¡£ i: Huffman Éä¹æ j: Éü¹æʸ»ú - k: j ¤ÎHuffman code¤Ç¤Î¥Ó¥Ã¥ÈĹ + k: j ¤Î Huffman Éä¹æ¤Î¥Ó¥Ã¥ÈĹ(i ¤Î¥Ó¥Ã¥ÈĹ) l: ¥Ó¥Ã¥ÈĹ k ¤ËÂФ¹¤ëHuffman Éä¹æ¤Î½ªÃÍ (start[k] <= Huffman(k) < l) m: Huffman Éä¹æɽ¤òshift¤¹¤ë¥Ó¥Ã¥È¿ô n: ?? p: ?? -n, p ¤Ë¤Ä¤¤¤Æ¤Ï¤Ò¤È¤á¤Ç¤Ï¤ï¤«¤é¤Ê¤«¤Ã¤¿¡£ - ¤³¤ì¤òƧ¤Þ¤¨¤Æ½èÍýÆâÍƤò¸«¤Æ¤ß¤è¤¦¡£¤Þ¤º¡¢(F)Á´ÂΤˤĤ¤¤Æ /* (F) */ @@ -5208,14 +5362,14 @@ n, p start[k] = l; } -Éü¹æʸ»ú j = 0 ... nchar ¤ò¥ë¡¼¥×¤·¤Æ¤¤¤ë(j ¤¬Ê£¹çʸ»ú¤Ç¤¢¤ë¤³¤È¤Ï¡¢ +Éü¹æʸ»ú j = 0 ... nchar ¤ò¥ë¡¼¥×¤·¤Æ¤¤¤ë(j ¤¬Éü¹æʸ»ú¤Ç¤¢¤ë¤³¤È¤Ï¡¢ bitlen[] ¤Îź¤¨»ú¤Ç¤¢¤ë¤³¤È¤«¤é¤ï¤«¤ë)¡£ ¤½¤·¤Æ¡¢k = bitlen[j] ¤¬ 0 ¤Ç¤¢¤ì¤Ð¡¢(Huffman Éä¹æ²½¤µ¤ì¤Æ¤¤¤Ê¤±¤ì¤Ð)¤½ ¤Îʸ»ú¤Ï¥¹¥­¥Ã¥×¤·¤Æ¤¤¤ë¡£¤³¤³¤Ï¡¢Îɤ¤¤À¤í¤¦¡£ (F.1), (F.2) ¤Ï¡¢HuffmanÉä¹æ²½¤µ¤ì¤Æ¤¤¤ëʸ»ú j ¤Ë¤Ä¤¤¤Æ -¤Î½èÍý¤È¤Ê¤ë¡£(ºÇ¸å¤Îstart[k] = l ¤Ï¸å²ó¤·) +¤Î½èÍý¤È¤Ê¤ë¡£(ºÇ¸å¤Î start[k] = l ¤Ï¸å¤Ç¹Í¤¨¤è¤¦) ½èÍý¤ÎÌÜŪ¤«¤éÂ绨ÇÄ¤Ë @@ -5235,24 +5389,23 @@ bitlen[] table[i] = j; } -¥Ó¥Ã¥ÈĹ k <= tablebits ¤Î¾ì¹ç¡¢¥Ó¥Ã¥ÈĹ k ¤¬¼è¤ê¤¦¤ëÈϰϤÎHuffmanÉä¹æ +¥Ó¥Ã¥ÈĹ k <= tablebits ¤Î¾ì¹ç¡¢¥Ó¥Ã¥ÈĹ k ¤¬¼è¤ê¤¦¤ëÈϰϤΠHuffman Éä¹æ ¤Ë¤Ä¤¤¤Æ¡¢Ê¸»ú j ¤ò³ä¤êÅö¤Æ¤Æ¤¤¤ë¡£ ¥Ó¥Ã¥ÈĹ k ¤¬¼è¤ê¤¦¤ëÈϰϤΠHuffman Éä¹æ¤È¤Ï start[k] <= HuffmanÉä¹æ i < l -¤Ç¤¢¤ë¡£Îã¤Ç¼¨¤¹¤È(´ÊÊز½¤Î¤¿¤á¤Ë¡¢ºÇÂç¤ÎHuffmanÉä¹æŤò2¤È¤¹¤ë) +¤Ç¤¢¤ë¡£Îã¤Ç¼¨¤¹¤È(´ÊÊز½¤Î¤¿¤á¤Ë¡¢ºÇÂç¤Î Huffman Éä¹æŤò 2 ¤È¤¹¤ë) /\ a: 0 a /\ b: 10 b c c: 11 -ʸ»úa¤Ï¡¢1¥Ó¥Ã¥È¤Ç¡¢00...10 ¤ÎÈÏ°Ï -ʸ»úb¤Ï¡¢2¥Ó¥Ã¥È¤Ç¡¢10...11 ¤ÎÈÏ°Ï -ʸ»úc¤Ï¡¢2¥Ó¥Ã¥È¤Ç¡¢11 +ʸ»ú a ¤Ï¡¢1 ¥Ó¥Ã¥È¤Ç¡¢00...10 ¤ÎÈÏ°Ï(¤Ä¤Þ¤ê¡¢00 ¤È 01) +ʸ»ú b ¤Ï¡¢2 ¥Ó¥Ã¥È¤Ç¡¢10...11 ¤ÎÈÏ°Ï(¤Ä¤Þ¤ê¡¢10) -¤È¤Ê¤ë¡£¤³¤³¤Ç¡¢Ê¸»ú c ¤Ë¤Ä¤¤¤Æ¤Ï¤³¤Î¥ë¡¼¥×¤Ç¤Ï¥Æ¡¼¥Ö¥ë¤ËÃͤ¬¥»¥Ã¥È¤µ¤ì -¤Ê¤¤¤è¤¦¤Ë¸«¤¨¤ë¡£¼ÂºÝ¤Ï(F) ¤Î¥ë¡¼¥×¤ÎËöÈø¤Ë½Ð¤Æ¤­¤¿ +¤È¤Ê¤ë¡£¤³¤³¤Ç¡¢Ê¸»ú c ¤Ë¤Ä¤¤¤Æ¤Ïʸ»ú b ¤ÈƱ¤¸Éä¹æ¤¬³ä¤êÅö¤Æ¤é¤ì¤ë¤«¤Î¤è¤¦¤Ë +¸«¤¨¤ë¤¬¡¢¼ÂºÝ¤Ï(F) ¤Î¥ë¡¼¥×¤ÎËöÈø¤Ë½Ð¤Æ¤­¤¿ start[k] = l; @@ -5282,7 +5435,7 @@ bitlen[] *p = j; } -¤Þ¤º¡¢ +¤Á¤ç¤Ã¤ÈÊ£»¨¤À¤¬Æñ¤·¤¤¤³¤È¤Ï¤Ê¤¤¡£¤Þ¤º¡¢ p = &table[(i = start[k]) >> m]; @@ -5291,31 +5444,53 @@ bitlen[] i = start[k]; p = &table[i >> m] -¤Ç¤¢¤ê¡¢i ¤Ï Huffman Éä¹æ¤Î½é´üÃÍ +¤Ç¤¢¤ê¡¢i ¤Ï Huffman Éä¹æ¤Î½é´üÃͤǤ¢¤ë¡£i ¤¬ m ¤Ç±¦¥·¥Õ¥È¤µ¤ì¤Æ¤¤¤ë¤¬¡¢ +½é´ü²½Éôʬ¤Î (D) ¤Ç¤Ï¡¢tablebits ¤Þ¤Ç¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤ËÂФ¹¤ëÃÍ +(start[1..tablebits])¤·¤«¥·¥Õ¥È¤·¤Æ¤ª¤é¤º¡¢¤³¤Î (F.2) ¤ÎÉôʬ¤Ï k > +tablebits ¤Ç¤¢¤ë¤«¤é start[k] ¤Ï m ¤Ç¥·¥Õ¥È¤µ¤ì¤Æ¤¤¤Ê¤¤ Huffman Éä¹æ¤È +¤Ê¤Ã¤Æ¤¤¤ë¡£ -p ¤Ï¡¢HuffmanÉä¹æ i ¤Î table ¾å¤Î°ÌÃÖ¤ò»Ø¤¹¡£¸å¤Ç¡¢*p ¤Ë¤ÏÌڤΥ롼¥È°ÌÃÖ -¤òµ­Ï¿¤¹¤ë¤³¤È¤¬Í½ÁÛ¤µ¤ì¤ë¡£ +p ¤Ï¡¢HuffmanÉä¹æ i ¤Î table ¾å¤Î°ÌÃÖ¤ò»Ø¤¹¡£¸å¤Ç¡¢*p ¤Ë¤ÏÌڤΥ롼¥È°Ì +ÃÖ¤òµ­Ï¿¤¹¤ë¤³¤È¤¬Í½ÁÛ¤µ¤ì¤ë¡£ ¼¡¤Ë¡¢ i <<= tablebits; -i ¤ò tablebits ¤Çshift¤¹¤ë¤³¤È¤Ç¡¢Huffman Éä¹æ i ¤Ï -ºÇ¾å°Ì¤Îtablebits ¤ò½ü¤¤¤¿»Ä¤ê¤Î¥Ó¥Ã¥ÈÉôʬ¤Ë¤Ê¤ë¡£ - - k - tablebits - |-----------|----| - +-----------+----+ - i | | | - +-----------+----+ - |----| - ¥³¥³ +i ¤ò tablebits ¤Ç¥·¥Õ¥È¤¹¤ë¤³¤È¤Ç¡¢Huffman Éä¹æ i ¤ÏºÇ¾å°Ì¤Î tablebits +¤ò½ü¤¤¤¿»Ä¤ê¤Î¥Ó¥Ã¥ÈÉôʬ¤Ë¤Ê¤ë¡£¤³¤Î»Ä¤ê¤Î¥Ó¥Ã¥ÈÉôʬ¤òÌÚ¤Çɽ¤¹¡£ + ¼¡¤Ë n = k - tablebits; -n ¤Ï¡¢½ñ¤­´¹¤¨¤¿ i ¤Î¥Ó¥Ã¥ÈŤò¼¨¤¹¡£ÌڤˤϿ¼¤µ n ¤Î³¬Áؤ¬ºîÀ®¤µ¤ì¤ë¤Î¤À¤í¤¦¡£ +n ¤Ï¡¢½ñ¤­´¹¤¨¤¿ i ¤Î¥Ó¥Ã¥ÈŤò¼¨¤¹¡£ÌڤˤϿ¼¤µ n ¤Î³¬Áؤ¬ºîÀ®¤µ¤ì¤ë¤Î +¤À¤í¤¦¡£ + +---------------------------------------------------------------------------- + k: Huffman Éä¹æ i ¤Î¥Ó¥Ã¥ÈĹ + |----------------| + + tablebits (ɽ°ú¤­¤ÇÉü¹æ¤¹¤ëÉôʬ) + |-----------| + +-----------+----+ + Huffman Éä¹æ i| |xxxx| + +-----------+----+ + |----| + n: ÌÚ¤òé¤ë¤³¤È¤ÇÉü¹æ¤¹¤ëÉôʬ + +tablebits ¥Ó¥Ã¥È¥·¥Õ¥È¤Ë¤è¤ê¡¢½ñ¤­´¹¤¨¤¿ i ¤Ï¡¢xxxx ¤ÎÉôʬ¤¬ºÇ¾å°Ì¥Ó¥Ã +¥È¤È¤Ê¤ë¡£ + + +----+-----------+ + Huffman Éä¹æ i|xxxx| | + +----+-----------+ + |----| + n: ÌÚ¤òé¤ë¤³¤È¤ÇÉü¹æ¤¹¤ëÉôʬ + +---------------------------------------------------------------------------- + +¤½¤¦¤·¤Æ¡¢½ñ¤­´¹¤¨¤¿ i ¤Ë¤Ä¤¤¤Æ¡¢ÌÚ¤ò¹½ÃÛ¤¹¤ë¡£ /* make tree (n length) */ while (--n >= 0) { @@ -5335,19 +5510,22 @@ n *p = j; (F.2.1) *p ¤¬ 0 ¤Ç¤¢¤ì¤Ð¡¢*p ¤Ë avail ¤È¤·¤Æ¡¢¿·¤¿¤Êº¬¤ò³ä¤êÅö¤Æ¤½¤Î±¦ -¤Èº¸¤Î»Ò¤Ï0¤Ç½é´ü²½¤·¤Æ¤ª¤¯¡£ +¤Èº¸¤Î»Ò¤Ï 0 ¤Ç½é´ü²½¤·¤Æ¤ª¤¯¡£ + +(F.2.2) Huffman Éä¹æ(¤Î tablebits °Ê¹ß¤Î¥Ó¥Ã¥È) i ¤Ë¤Ä¤¤¤ÆºÇ¾å°Ì¥Ó¥Ã¥È +¤¬Î©¤Ã¤Æ¤¤¤ì¤Ð±¦¤Î»Ò right¡¢¥Ó¥Ã¥È¤¬Î©¤Ã¤Æ¤¤¤Ê¤±¤ì¤Ðº¸¤Î»Ò left ¤òºîÀ® +(Îΰè¤ò p ¤ÇͽÌó)¤¹¤ë¡£ + +¥ë¡¼¥×¤Ë¤è¤Ã¤Æ¥Ó¥Ã¥È¥Ñ¥¿¡¼¥ó¤Ë±è¤Ã¤Æ *p ¤Ë¤Ï¡¢avail++ ¤¬½ç¤Ë³ä¤êÅö¤Æ¤é¤ì¤ë¡£ -(F.2.2) Huffman Éä¹æ(¤Îtablebits°Ê¹ß¤Î¥Ó¥Ã¥È) i ¤Ë¤Ä¤¤¤Æ -ºÇ¾å°Ì¥Ó¥Ã¥È¤¬Î©¤Ã¤Æ¤¤¤ì¤Ð±¦¤Î»Ò right¡¢¥Ó¥Ã¥È¤¬Î©¤Ã¤Æ¤¤¤Ê¤±¤ì¤Ð -º¸¤Î»Ò¤òºîÀ®¤¹¤ë¡£(¤³¤³¤Ç¤Ï¡¢p ¤ò³ä¤êÅö¤Æľ¤·¤Æ¤¤¤ë¤À¤±¤Ç¤¢¤ë)¡£ +avail ¤Î½é´üÃÍ¤Ï nchar ¤Ê¤Î¤Ç¡¢*p >= nchar (c_table[] ¤Ê¤é NC)¤Ç¤¢¤ë¡£ + +¤³¤Î while ¥ë¡¼¥×¤òÈ´¤±¤¿¸å¤Ë(F.2.3)¤Ë¤Æ -(F.2.3) -*p ¤Ë¤Ï¡¢avail++ ¤¬½ç¤Ë³ä¤êÅö¤Æ¤é¤ì avail ¤Î½é´üÃÍ¤Ï nchar ¤Ê¤Î¤Ç¡¢ -*p >= nchar (c_table[] ¤Ê¤é NC)¤Ç¤¢¤ë¡£ -¤³¤Î while ¥ë¡¼¥×¤òÈ´¤±¤¿¸å¤Ë *p = j; -¤¬ÀßÄꤵ¤ì¡¢ÌÚ¤ÎÍդˤϡ¢*p < nchar ¤Ç¤¢¤ëÃͤ¬ÀßÄꤵ¤ì¤Æ¤¤¤ë¡£ -(¤½¤·¤Æ¤³¤ì¤¬µá¤á¤ëÉü¹æʸ»ú¤Ç¤¢¤ë¡£) + +¤¬ÀßÄꤵ¤ì¡¢ÌÚ¤ÎÍդˤϡ¢*p < nchar ¤Ç¤¢¤ëÃͤ¬ÀßÄꤵ¤ì¤Æ¤¤¤ë¡£(¤½¤·¤Æ¤³ +¤ì¤¬µá¤á¤ëÉü¹æʸ»ú¤Ç¤¢¤ë¡£) (F.2.1) ¤Ç¡¢if (*p == 0) ¤È¤·¤Æ¤¤¤ëÍýͳ¤Ï¡¢ @@ -5363,8 +5541,1601 @@ n . <- p / \ -¤È±¦¤Î»Ò¤¬Äɲ䵤ì¤ë¾ì¹ç¤òÁÛÄꤷ¤Æ¤¤¤ë¡£ +¤È±¦¤Î»Ò¤¬Äɲ䵤ì¤ë¾ì¹ç¤òÁÛÄꤷ¤Æ¤¤¤ë¡£¤³¤Î»þÅÀ¤Ç (E) ¤Ë¤Æ table ¤ò 0 +¤Ç½é´ü²½¤·¤Æ¤¤¤ëÍýͳ¤¬¤ï¤«¤Ã¤¿¡£Ìڤꬤ¬³ä¤êÅö¤Æ¤é¤ì¤Æ¤¤¤ë¤«¤É¤¦¤«¤ÎȽ +Ä꤬ɬÍפÀ¤«¤é½é´ü²½¤Ç̤³ä¤êÅö¤Æ¤Ë¤·¤Æ¤ª¤¯É¬Íפ¬¤¢¤ë¤È¤¤¤¦¤³¤È¤À¡£¤â¤Á +¤í¤ó (E) ¤Ç½ñ¤¤¤¿Ä̤ê table Á´ÂΤò 0 ¤Ç½é´ü²½¤·¤Æ¤âÌäÂê¤Ï¤Ê¤¤¤·¤½¤ÎÊý¤¬ +¤ï¤«¤ê¤ä¤¹¤¤¤È»×¤Ã¤¿¡£ + +¤³¤³¤Þ¤Ç¡¢c_table[] ¤òºîÀ®¤¹¤ë¾ì¹ç¤À¤±¤ò¸«¤Æ¤­¤¿¤¬¡¢pt_table ¤Î¾ì¹ç¤â¹Í +¤¨Êý¤ÏƱ¤¸¤Ê¤Î¤Ç²òÀϤÎɬÍפϤʤ¤¤À¤í¤¦¡£ + +¤¿¤À¡¢¤³¤ÎÃʳ¬¤Çɽ°ú¤­¤Î¥Ó¥Ã¥È¿ô¤¬ c_table ¤Ë¤Ä¤¤¤Æ¤Ï 12 ¤¬ p_table ¤Ë¤Ä +¤¤¤Æ¤Ï 8 ¤¬Áª¤Ð¤ì¤Æ¤¤¤ëÍýͳ¤¬ÉÔÌÀ¤Ç¤¢¤ë¡£¤³¤ì¤Ï¡¢ÁÛÁü¤À¤¬ pt_table ¤¬Éä¹æ²½¤¹¤ë +ʸ»ú¼ï¤Ï¾¯¤Ê¤¤¤Î¤Ç pt_table ¤Ë¤Ä¤¤¤Æ¤Ï 8 bit ¤Î¥Æ¡¼¥Ö¥ë¤ò»È¤Ã¤Æ¤âɽ°ú¤­¤Î³ÎΨ¤¬ +¹â¤¤¤Î¤Ç¤Ï¤Ê¤¤¤À¤í¤¦¤«¡£¤Ä¤Þ¤ê¡¢Îΰè(pt_table ¤Î¥µ¥¤¥º)¤ÎÀáÌó¤òÍ¥À褷¤Æ¤¤¤ë¤Î¤Ç +¤Ï¤Ê¤¤¤«¤È»×¤¦¡£ + + +LHA ¥Õ¥¡¥¤¥ë¤Î¹½Â¤(¤Þ¤È¤á) +-------------------------- + +°Ê¾å¤Ç LHa for UNIX ¤Ë¤Ä¤¤¤Æ¤Î°ìÄ̤ê¤Î½èÍý¤ò¸«¤¿¤³¤È¤Ë¤Ê¤ë¡£¤³¤³¤«¤é¤Ï +¼ÂÁõ¤Ë¤Ä¤¤¤Æ¤Ï¶ËÎÏ¿¨¤ì¤º¤Ë LHA ¥Õ¥¡¥¤¥ë¤Î¹½Â¤(°µ½Ì·Á¼°)¤Ë¤Ä¤¤¤Æ¤Þ¤È¤á¤Æ +¤ß¤è¤¦¡£¤Þ¤¿¡¢¤³¤³¤Þ¤ÇºÙÉô¤Ë¤Ä¤¤¤Æ¤Ê¤¾¤Î¤Þ¤Þ¤È¤·¤Æ¤¤¤¿Éôʬ¤¬¤¢¤ë¤Î¤Ç¤³ +¤ì¤é¤âºÆ¸¡Æ¤¤·¤ÆÌÀ¤é¤«¤Ë¤·¤è¤¦¡£ + +---------------------------------------------------------------------------- +< LHA ¥Õ¥¡¥¤¥ë¤Î¹½Â¤(1 ¥Ö¥í¥Ã¥¯Ê¬) > + + +-----------+ + | blocksize | + +-----------+ + 16bit + + t_len: c_len ¤Î¥Ï¥Õ¥Þ¥óÌÚ | + +-----+--------------------+ | +-----+-----+ + | len | t_len | | | 0 |root | + +-----+--------------------+ | +-----+-----+ + TBIT ?? bit | TBIT TBIT + | + c_len: ʸ»ú¤ÈŤµ¤Î¥Ï¥Õ¥Þ¥óÌÚ | + +-------+------------------+ | +-------+-------+ + | len | c_len | | | 0 | root | + +-------+------------------+ | +-------+-------+ + CBIT ?? bit | CBIT CBIT + | + p_len: °ÌÃÖ¤Î(¥Ó¥Ã¥ÈŤÎ)¥Ï¥Õ¥Þ¥óÌÚ | + +-----+--------------------+ | +-----+-----+ + | len | p_len | | | 0 |root | + +-----+--------------------+ | +-----+-----+ + pbit ?? bit | + + °µ½Ìʸ(ʸ»ú¤ÈŤµ¡¢°ÌÃ֤ΥӥåÈĹ¤Î¥Ï¥Õ¥Þ¥óÉä¹æ¤È°ÌÃÖ¤ÎÃÍ) + +---------------------+ + | °µ½Ìʸ | + +---------------------+ + + + method maxmatch dicsiz dicbit np(dicbit+1) pbit(np <= 2^pbit) + ------------------------------------------------------------------ + -lh4- 256 2^12 12 14 (or 13?) 4 (14 <= 2^4) + -lh5- 256 2^13 13 14 4 (14 <= 2^4) + -lh6- 256 2^15 15 16 5 (16 <= 2^5) + -lh7- 256 2^16 16 17 5 (17 <= 2^5) + + threashold 3 + NC 256+maxmatch-threshold+1{510} + CBIT 9 (NC <= 2^9) + + MAXDEPTH 16 + NT MAXDEPTH+1 + TBIT 4 (NT <= 2^4) +---------------------------------------------------------------------------- + +# ¥½¡¼¥¹¾å pt_len ¤È½ñ¤¤¤Æ¤¤¤¿Éôʬ¤Ï¡¢°Ê¹ß¤ÎÀâÌÀ¤Î¤¿¤á¤Ë p_len, t_len +# ¤È̾Á°¤òÊѹ¹¤·¤Æ¤¤¤ë¡£ÊÑ¿ô pt_len ¤Ïñ¤ËÎΰè¤ÎÀáÌó¤Î¤¿¤á¤Ë»È¤¤²ó¤µ¤ì +# ¤Æ¤¤¤¿¤À¤±¤Ç¤¢¤ê¤¤¤ï¤Ð¼ÂÁõ¤ÎÅÔ¹ç¤Ç¤¢¤ë¤«¤é¤À¡£ + +¾åµ­¤Ï¡¢LHA ¥Õ¥¡¥¤¥ë¤Î¹½Â¤(¥Ø¥Ã¥À¤ò½ü¤¯)¤òɽ¤·¤¿¤â¤Î¤Ç¤¢¤ë¡£LHA ¥Õ¥¡¥¤ +¥ë¤Ï¥Ø¥Ã¥À¤È¾åµ­¥Õ¥¡¥¤¥ë¹½Â¤¤Î½¸¤Þ¤ê¤Ç 1 ¥Õ¥¡¥¤¥ë¤Î°µ½Ì¥Õ¥¡¥¤¥ë¤È¤Ê¤ê¡¢ +¤½¤ì¤¬Ê£¿ô½¸¤Þ¤Ã¤Æ¥¢¡¼¥«¥¤¥Ö¤ò¹½À®¤¹¤ë¡£¤Þ¤¿¡¢Ìó«»ö¤È¤·¤Æ¥¢¡¼¥«¥¤¥Ö¤Î +ºÇ¸å¤Ï 1 ¥Ð¥¤¥È¤Î 0 ¤¬Éղ䵤ì¤ë¤³¤È¤È¤Ê¤Ã¤Æ¤¤¤ë¡£ + +°µ½Ì·Á¼°¤Ï method ¤Ë¤è¤Ã¤Æ¥Ñ¥é¥á¡¼¥¿¤¬ÊѲ½¤¹¤ë¡£¤³¤³¤Ç¤Ï¡¢method +lh4,5,6,7 ¤Î·Á¼°¤·¤«¿¨¤ì¤Ê¤¤¤Î¤Ç method ¤Î°ã¤¤¤Ï slide ¼­½ñ¤Î¼­½ñ¥µ¥¤¥º +¤Î°ã¤¤¤·¤«¤Ê¤¤¡£¤¿¤À¤·¡¢¼­½ñ¤Î¥µ¥¤¥º¤Î°ã¤¤¤ËϢư¤·¤Æ°µ½Ì·Á¼°¤Ë±Æ¶Á¤òÍ¿ +¤¨¤ëÊÑ¿ô¤¬¤¢¤ë¤Î¤Ç¤³¤ì¤â¾åµ­¤Ë¤Þ¤È¤á¤Æ¤¤¤ë¡£(¾®Ê¸»ú¤Ï¤½¤ÎÊÑ¿ô¡¢Âçʸ»ú¤Ï +Äê¿ô¤ò°ÕÌ£¤¹¤ë) + +¿ÞÃæ t_len, c_len, p_len ¤Ï¡¢Huffman ÌڤξðÊó¤ò³ÊǼ¤·¤¿Îΰè¤òɽ¤·¡¢¡Ö°µ +½Ìʸ¡×¤¬Ê¿Ê¸¤ò°µ½Ì¤·¤¿ËÜÂΤȤʤ롣 + +¤Þ¤¿¡¢3 ¤Ä¤Î¥Ï¥Õ¥Þ¥óÌڤνÐÎÏ·Á¼°¤Ë¤Ä¤¤¤Æ¥Ï¥Õ¥Þ¥óÌÚ¤¬¹½ÃۤǤ­¤Ê¤¤¾ì¹ç¤Î +·Á¼°¤ò±¦Â¦¤ËÊ»µ­¤·¤¿¡£¤³¤ì¤Ï¡¢Éü¹æ¸ì¤¬ 1 ¼ïÎष¤«¤Ê¤¤¾ì¹ç¤ò¼¨¤·¤Æ¤ª¤ê +root ¤¬¤½¤ÎÉü¹æ¸ì¤È¤Ê¤ë¡£Î㤨¤Ð¡¢c_len ¤¬¤³¤Î·Á¼°¤Ç½ñ¤«¤ì¤Æ¤¤¤¿¾ì¹ç¤Ï°µ +½Ìʸ¤ò¸«¤º¤Ë blocksize ʬ root ¤ò½ÐÎϤ¹¤ì¤ÐÉü¹æ¤È¤Ê¤ë¡£¤Ê¤ª¡¢c_len ¤¬¤³ +¤Î·Á¼°¤Î¾ì¹ç c_len ¤Î¥Ï¥Õ¥Þ¥óÌÚ¤ò¼¨¤¹ t_len ¤â±¦Â¦¤Î·Á¼°¤Ë¤Ê¤ë¤¬¡¢¤³¤Î +¤È¤­¤Î t_len ¤Î root ¤ÎÃÍ¤Ï 0 ¤Ë¤¹¤ë»ö¤Ë¤Ê¤Ã¤Æ¤¤¤ë¤è¤¦¤À(¤¿¤À¡¢Éü¹æ½èÍý +¤Ï¤³¤ÎÃͤ˰͸¤·¤Ê¤¤Êý¤¬Îɤ¤¤À¤í¤¦)¡£ + +°µ½Ìʸ¤Ï¡¢Ê¸»ú c(0 .. 255)¤È <Ťµ len, °ÌÃÖ off> ¤ò Huffman ÌÚ¤ÇÉä¹æ²½ +¤·¤¿ Huffman Éä¹æ¤ÎʤÓ(¤È°ÌÃÖ¤ÎÃÍ)¤Çɽ¤µ¤ì¤ë¡£ + + ¤Ï¡¢slide ¼­½ñË¡¤Ç¤Î°µ½Ì·ë²Ì¤Ç¤¢¤ê¡¢¼­½ñ¾å¤Î off °ÌÃ֤Πlen +ʸ»ú¤ò¤³¤Î·Á¼°¤Çɽ¤·¤Æ¤¤¤ë¡£¼­½ñ¤È¤Ï¡¢¸½ºßÉü¹æ¤ò³«»Ï¤·¤Æ¤¤¤ë°ÌÃÖ¤«¤é¼­ +½ñ¥µ¥¤¥ºÊ¬Á̤ä¿Éü¹æºÑ¤ß¤Îʿʸ¤ò»Ø¤¹¡£ + +°ÌÃÖ off ¤Ï¡¢0 ¤¬¡Ö1ʸ»úÁ°¡×¤ò¸½¤¹¡£½¾¤Ã¤Æ¼­½ñ¥µ¥¤¥º dicsiz ¤¬ 2^3 ¤Î¾ì +¹ç¤òÎã¤Ë¹Í¤¨¤ë¤È°ÌÃÖ¤ÎÃͤ¬ 2^3-1 ¤Î¾ì¹ç¤Ç¤Ï¡¢2^3 ʸ»úÁ°¤ò¼¨¤¹¤³¤È¤Ë¤Ê¤ë¡£ + + ¼­½ñ¥µ¥¤¥º + (Éü¹æºÑ¤ß¤Îʿʸ) + |-------------| + 8 7 6 5 4 3 2 1 x + ^ \ + | Éü¹æ³«»Ï°ÌÃÖ + x ¤«¤é 8 ʸ»úÁ°¤Î°ÌÃÖ + +½¾¤Ã¤Æ¡¢off ¤ÎÃͤÎÈÏ°Ï¤Ï 0 ... 2^dicbit ¤Ç¤¢¤ë¡£ + +Ťµ len ¤ÎÃÍ¤Ï 256 ¤Î¾ì¹ç¤Ëʸ»úÎóĹ 3 ¥Ð¥¤¥È¤ò¼¨¤¹¡£¤Ä¤Þ¤ê¡¢len ¤ËÂФ· +¤Æ len-256+3 ¤¬¼ÂºÝ¤ÎŤµ¤ò¼¨¤¹¡£(¤¿¤À¤·¡¢-lzs- ¤Î¾ì¹ç¤Ï len-256+2 ¤¬¼Â +ºÝ¤ÎŤµ¤È¤Ê¤ë) + +len ¤ÎÃͤ¬ 256 ¤«¤é»Ï¤Þ¤ë¤Î¤Ï¡¢1 ¥Ð¥¤¥È¤Îʸ»ú c ¤ÎÈÏ°Ï 0..255 ¤È½Å¤Ê¤é +¤Ê¤¤¤è¤¦¤Ë¤¹¤ë¤¿¤á¤Ç¤¢¤ë¡£(Ťµ¤Ï¡¢Ê¸»ú¤ÈƱ¤¸ Huffman ÌÚ¤ÇÉä¹æ²½¤µ¤ì¤ë) + +¼ÂºÝ¤ÎŤµ¤¬ 3 ¤«¤é»Ï¤Þ¤ë¤Î¤Ï¡¢ ¤ÎÁȤ¬ 4 ¥Ð¥¤¥È¤Çɽ¤µ¤ì¤ë¤¿¤á¡¢ +¥Þ¥Ã¥ÁĹ¤È¤·¤Æ 2 ʸ»ú°Ê²¼¤ò ¤Î·Á¼°¤Çɽ¤¹¤È°µ½Ì¤Ç¤Ï¤Ê¤¯¿­Ä¹¤Ë +¤Ê¤Ã¤Æ¤·¤Þ¤¦¤«¤é¤Ç¤¢¤ë¡£ + +# Ťµ¤¬ 3 ¤Î¾ì¹ç¤âƱ¤¸¤è¤¦¤Ë»×¤¨¤ë¤¬¤Ê¤¼¤À¤í¤¦¤«¡© +# ¤Ï¤è¤êÀµ³Î¤Ë¤Ï 3 ¥Ð¥¤¥È¤È 1 ¥Ó¥Ã¥È¤Ç¤¢¤ë¡£¤È¤¤¤¦¤Î¤â len ¤¬ +# 256 ¤«¤é»Ï¤Þ¤ë¤«¤é len ¤Î¾ðÊó¤Ï 9 ¥Ó¥Ã¥ÈɬÍפǤ¢¤ë¡£len ¤¬ 256...510 +# ¤ÎÈÏ°Ï¤Ê¤Î¤Ç 8 ¥Ó¥Ã¥È¤Î¤è¤¦¤Ë¤â»×¤¨¤ë¤¬Ê¸»ú c ¤È¤ÎȽÊ̤Τ¿¤á¤Î¾ðÊó¤È +# ¤·¤Æ 1 ¥Ó¥Ã¥È;·×¤ËɬÍפʤΤǤ¢¤ë¡£¤³¤ì¤ÏͽÁÛ¤À¤¬¡¢Åö»þ -lh5- ¤Î¼­½ñ +# ¥µ¥¤¥º¤Ç¤¢¤ì¤Ð°ÌÃÖ¤Ï 13 ¥Ó¥Ã¥È¤·¤«»ÈÍѤ·¤Ê¤¤¤¿¤á¡¢ ¤Ï 22 ¥Ó¥Ã +# ¥È¤È¸«¤Ê¤»¤ë¡£½¾¤Ã¤Æ 3 ¥Ð¥¤¥È¤Ï ¤Î·Á¼°¤Ë¤·¤¿Êý¤¬Îɤ¤¤ÈȽÃÇ +# ¤·¤¿¤Î¤Ç¤Ï¤Ê¤¤¤À¤í¤¦¤«¡©¤Ç¤Ï¡¢-lh7- ¤Î¾ì¹ç¤Ï¡¢Ä¹¤µ¤ÎºÇ¾®ÃÍ¤Ï 4 ¤Ë¤·¤¿ +# Êý¤¬Îɤ¤¤Î¤À¤í¤¦¤«¡©¤ª¤½¤é¤¯°ÌÃÖ¤ÎÃÍ¤Ë 16 ¥Ó¥Ã¥È¤¹¤Ù¤Æ»ÈÍѤ¹¤ë³ÎΨ¤¬ +# Ä㤯¿¤¯¤Î¾ì¹ç¤Ï¸ú²Ì¤¬¤Ê¤¤¤Î¤Ç¤Ï¤Ê¤¤¤«¤È»×¤¦¡£ + +¤Þ¤¿¡¢maxmatch{256}¤¬ºÇÂç¥Þ¥Ã¥ÁŤǤ¢¤ê¡¢¤³¤Î¤È¤­¤Î len ¤ÎÃÍ¤Ï +256+maxmatch-3{509=NC-1} ¤Ç¤¢¤ë¡£ + + len(Éü¹æ¸ì) ¼ÂºÝ¤ÎŤµ + ---------------------------------- + 256..256+maxmatch-3 3..maxmatch + +¤³¤ì¤é¤ò°µ½Ì¤·¤¿·Á¼°¡Ö°µ½Ìʸ¡×¤Ï Huffman Éä¹æ¤ÎϢ³(¤ª¤è¤Ó°ÌÃÖ¤ÎÃÍ¡£¸å +½Ò)¤Ç¤¢¤ë¡£°µ½Ìʸ¤Î¥µ¥¤¥º¤Ï¾å¿Þ¤Î blocksize ¤Çɽ¤µ¤ì¡¢blocksize ¿ô¤Îʸ +»ú¿ô¤Î¾ðÊ󤬽ÐÎϤµ¤ì¤Æ¤¤¤ë¡£¤³¤³¤Ç¡¢¡Öʸ»ú¿ô¡×¤Ï <Ťµ, °ÌÃÖ> ¤ÎÁȤâ 1 +ʸ»ú¤È¤·¤Æ¥«¥¦¥ó¥È¤µ¤ì¤ë¡£Ê¸»ú¤Ê¤Î¤«¡¢<Ťµ, °ÌÃÖ> ¤ÎÁȤʤΤ«¤ÎȽÊ̤ϡ¢ + + Éü¹æ¤·¤¿1ʸ»ú >= 256 ¤Î¾ì¹ç + Ťµ¤ò¼¨¤¹¡£(¤½¤·¤Æ¤½¤Îľ¸å¤Ë°ÌÃ֤ΠHuffman Éä¹æ¤¬¤¢¤ë) + + Éü¹æ¤·¤¿1ʸ»ú < 256 ¤Î¾ì¹ç + ʸ»ú¤ò¼¨¤¹¡£ + +¤È¤Ê¤Ã¤Æ¤¤¤ë¡£¤½¤·¤Æ¡¢Ê¸»ú¤ÈŤµ¤Î Huffman Éä¹æ¤Ï¡¢Huffman ÌڤξðÊó¤ò¼¨ +¤¹ c_len ¤Ë¤è¤êÉü¹æ¤µ¤ì¡¢°ÌÃ֤ΠHuffman Éä¹æ¤Ï¡¢p_len ¤Ë¤è¤êÉü¹æ¤µ¤ì¤ë¡£ + +°ÌÃ֤ΠHuffman Éä¹æ¤Ï°ÌÃ֤ξðÊó¤Î¾å°Ì¥Ó¥Ã¥È¤¬ 0 ¤Ç¤¢¤ëÉôʬ¤ò½ü¤¤¤¿¥Ó¥Ã +¥ÈŤòÉä¹æ²½¤·¤¿¤â¤Î¤Ç¤¢¤ê°ÌÃÖ¤½¤Î¤â¤Î¤ÎÉä¹æ¤Ç¤Ï¤Ê¤¤¡£½¾¤Ã¤Æ°ÌÃÖ¤ÎÉä¹æ +¤Ï + + +------------------------------+----------+ + | °ÌÃ֤ΥӥåÈŤΠHuffman Éä¹æ| °ÌÃÖ¤ÎÃÍ | + | (p_len¤«¤éÉü¹æ) | | + +------------------------------+----------+ + +¤È Huffman Éä¹æ¤Ë³¤¤¤Æ¼ÂºÝ¤ÎÃͤò¼¨¤¹¥Ó¥Ã¥ÈÎ󤬽ÐÎϤµ¤ì¤Æ¤¤¤ë¡£Îã¤Ç¼¨¤¹ +¤È°Ê²¼¤ÎÄ̤ê¤À¡£ + +---------------------------------------------------------------------------- +°ÌÃÖ(off)¤Î½ÐÎÏÎã + +off = 64 ¤Î¾ì¹ç + + |---- 16 bit -------| + +----+----+----+----+ +off |0000 0000 0100 0000| + +----+----+----+----+ + |-7 bit-| + +¤³¤Î°µ½Ìʸ¤Ï°Ê²¼(Ťµ¤¬ 7 bit ¤Ç¤¢¤ë¤È¤¤¤¦¾ðÊó(HuffmanÉä¹æ²½)¤ÈÃͤΥڥ¢) + + |-6 bit-| + +-----------------+-------+ + | 7 ¤ÎHuffmanÉä¹æ |00 0000| + +-----------------+-------+ + +¤³¤ÎÎã¤Ç ɬÍץӥåȤǤ¢¤ë 7 bit ÌܤÏɬ¤º 1 ¤Ç¤¢¤ë¤¿¤áÃͤÎÉôʬ¤Ï 6 bit +½ÐÎϤ¹¤ì¤Ð¤è¤¤¡£ + +off = 1 ¤Î¾ì¹ç + + |---- 16 bit -------| + +----+----+----+----+ +off |0000 0000 0000 0001| + +----+----+----+----+ + |-| + 1 bit + +¤³¤Î°µ½Ìʸ¤Ï°Ê²¼(Ťµ¤¬ 1 bit ¤Ç¤¢¤ë¤È¤¤¤¦¾ðÊó¤Î¤ß) + + +-----------------+ + | 1 ¤ÎHuffmanÉä¹æ | + +-----------------+ + +off = 0 ¤Î¾ì¹ç + + |---- 16 bit -------| + +----+----+----+----+ +off |0000 0000 0000 0000| + +----+----+----+----+ + || + 0 bit + +¤³¤Î°µ½Ìʸ¤Ï°Ê²¼(Ťµ¤¬ 0 bit ¤Ç¤¢¤ë¤È¤¤¤¦¾ðÊó¤ÏÃͤ¬ 0 ¤È¸«¤Ê¤µ¤ì¤ë) + + +-----------------+ + | 0 ¤ÎHuffmanÉä¹æ | + +-----------------+ +---------------------------------------------------------------------------- + +# °ÌÃÖ¤òľÀÜ Huffman Éä¹æ²½¤·¤Ê¤¤Íýͳ¤Ï°ÌÃÖ¤ò»Ø¤¹ÃÍ¤Ï slide ¼­½ñ¾å¤ÎǤ +# °Õ¤Î°ÌÃÖ¤ò»Ø¤¹¤¿¤á¥Ç¡¼¥¿¤ÎÈϰϤ¬¹­¤¯(-lh7- ¤Î¾ì¹ç¤Ç 0 ... 2^16) +# Huffman Éä¹æ²½¤Ë¤è¤ë°µ½Ì¤Î¸ú²Ì¤¬´üÂԤǤ­¤Ê¤¤¤¿¤á¤À¤È»×¤ï¤ì¤ë¡£°ìÊý¡¢ +# °ÌÃÖ¾ðÊó¤Ï¼­½ñ¾å¤ÎÈæ³ÓŪ¶á¤¤°ÌÃ֤˥ޥåÁ¤·¤ä¤¹¤¤¤Ï¤º¤Ç¤¢¤ë¤«¤é Huffman +# Éä¹æ²½¤ÎÂоݤǤ¢¤ë¥Ó¥Ã¥ÈĹ¤Ï¾®¤µ¤¤ÃͤËÊФê¤ä¤¹¤¤¤Ï¤º¤À¡£(ÊФ꤬¤¢¤ë +# ¤È Huffman Éä¹æ²½¤Î¸ú²Ì¤¬¹â¤¤) + +Huffman ÌڤξðÊó¤ò¥Õ¥¡¥¤¥ë¤Ë½ÐÎϤ¹¤ëºÝ p_len, c_len ¤Ï¡¢¤½¤ì¤¾¤ì¤ËŬ¤· +¤¿·Á¼°¤Ç°µ½Ì¤·¤Æ½ÐÎϤµ¤ì¤ë¡£ÆÃ¤Ë c_len ¤Ï¡¢¤µ¤é¤Ë¡¢t_len ¤Ë¤è¤ê +Huffman Éä¹æ²½¤¹¤ë¤³¤È¤Ç°µ½Ì¤ò¹Ô¤¦¡£ + +¥Ï¥Õ¥Þ¥óÌÚ {p,c,t}_len ¤Ï¤É¤ÎÉü¹æ¸ì¤¬¥Ï¥Õ¥Þ¥óÌڤΤɤγ¬Áؤˤ¢¤ë¤«¤Î¾ðÊó +¤Ë¤è¤êɽ¤µ¤ì¤Æ¤¤¤ë¡£¤³¤ì¤À¤±¤Î¾ðÊó¤À¤ÈÌÚ¤ò°ì°Õ¤Ëɽ¤¹¤³¤È¤¬¤Ç¤­¤Ê¤¤¤è¤¦ +¤Ë»×¤¨¤ë¤¬¡¢¼ÂºÝ¤Ï + + Huffman ÌÚ1 Huffman ÌÚ2 + . . + / \ / \ + . a a . + / \ / \ + c b b c + +Huffman ÌÚ1 ¤È Huffman ÌÚ2 ¤Ï»Þ¤Î¿­¤ÓÊý¤ÈÍÕ¤Ëʸ»ú¤ò¿¶¤ë½çÈ֤ΰ㤤¤Ç¤·¤« +¤Ê¤¤¡£¤½¤³¤Ç¡¢LHA ¤Ç¤Ï¡¢°Ê²¼¤Îµ¬Â§¤òÀߤ±¤ë¤³¤È¤Ç¡¢{p,c,t}_len ¤Î¾ðÊó¤À +¤±¤ÇÌÚ¤ò¹½ÃۤǤ­¤ë¤è¤¦¤Ë¤·¤Æ¤¤¤ë¡£ + + o ±¦¤ÎÌÚ¤òÍ¥À褷¤ÆºîÀ®¤¹¤ë¡£(±¦¤Î»Þ¤ò¥Ó¥Ã¥È 1 ¤È¤¹¤ë) + o Ʊ¤¸³¬ÁؤÎÉü¹æ¸ì¤Î³ä¤êÅö¤Æ¤Ï¥³¡¼¥É½ç¤Ëº¸¤«¤é³ä¤êÅö¤Æ¤ë¡£ + +Î㤨¤Ð¡¢ + + c_len['a'] = 2 + c_len['b'] = 1 + c_len['c'] = 3 + c_len['d'] = 3 + +¤È¤¤¤¦¾ðÊ󤬽ñ¤«¤ì¤Æ¤¤¤ë¾ì¹ç¡¢ + + ³¬ÁØ 1 ¤Ë 1 ¸Ä¤ÎÍÕ(Ãͤ¬ 1 ¤Ç¤¢¤ë c_len[] ¤¬ 1 ¸Ä) + ³¬ÁØ 2 ¤Ë 1 ¸Ä¤ÎÍÕ(Ãͤ¬ 2 ¤Ç¤¢¤ë c_len[] ¤¬ 1 ¸Ä) + ³¬ÁØ 3 ¤Ë 2 ¸Ä¤ÎÍÕ(Ãͤ¬ 3 ¤Ç¤¢¤ë c_len[] ¤¬ 2 ¸Ä) + +¤¬¤¢¤ë¤Î¤Ç°Ê²¼¤Î Huffman ÌڤηÁ¤Ë·è¤Þ¤ë(±¦¤ÎÌÚ¤òÍ¥À褷¤ÆºîÀ®¤¹¤ë)¡£ + + . + / \ + . . -- ³¬ÁØ1 + / \ + . . -- ³¬ÁØ2 + / \ + . . -- ³¬ÁØ3 + +¤½¤·¤Æ³Æ³¬ÁØËè¤Ëʸ»ú¤ò¥³¡¼¥É½ç¤Ë³ä¤êÅö¤Æ¤ë¤È + + . + / \ + b . -- ³¬ÁØ1 + / \ + a . -- ³¬ÁØ2 + / \ + c d -- ³¬ÁØ3 + + +¤È°ì°Õ¤ËÄê¤Þ¤ë¤³¤È¤È¤Ê¤ë¡£(¡Ö³¬ÁØËè¤Î¥³¡¼¥É½ç¡×¤Î°ÕÌ£¤¬Àµ³Î¤ËÅÁ¤ï¤ë¤è¤¦ +¤¢¤¨¤Æ¡¢b ¤È a ¤òµÕ¤Ë¤·¤Æ¤ß¤¿¡£) + +¤Ê¤ª¡¢{p,c,t}_len ¤ÎÃͤϤ¢¤ëʸ»ú¤Î³¬ÁؤΰÌÃÖ¤ò¼¨¤¹¤¬¡¢¤³¤ì¤Ï¤Ä¤Þ¤ê¤¢¤ë +ʸ»ú¤ò Huffman Éä¹æ²½¤·¤¿¤È¤­¤ÎÉä¹æĹ(bit Ĺ)¤ò¼¨¤·¤Æ¤¤¤ë¤³¤È¤Ë¤Ê¤ë¡£°Ê +¹ß¡¢{p,c,t}_len ¤Ïź¤¨»ú¤¬Éü¹æ¸ì¡¢Ãͤ¬Éä¹æŤòɽ¤¹ÇÛÎó¤Ç¤¢¤ë¤â¤Î¤È¤·¤Æ +ÀâÌÀ¤ò¹Ô¤¦¡£¤³¤ÎÇÛÎó¤Î¥µ¥¤¥º¤Ï°µ½ÌÂоݤÎʸ»ú½¸¹ç¤ÎÍ×ÁÇ¿ô¤Ç¤¢¤ê¡¢³ÆÍ×ÁÇ +¤Ï 0..16 ¤ÎÃͤò»ý¤Ä¡£(LHA ¤Î Huffman ÌڤΥ롼¥ë¤ÇÌڤγ¬ÁØ¤Ï 16 ¤Þ¤Ç¤È¤Ê¤Ã +¤Æ¤¤¤ë)¤½¤·¤Æ¡¢ÃÍ 0 ¤Ï¤½¤Îʸ»ú¤¬Ê¿Ê¸¤Ë¸½¤ì¤Ê¤¤¤³¤È¤ò¼¨¤¹¡£ + +---------------------------------------------------------------------------- + Huffman ÌÚ¡¡ Í×ÁÇ¿ô ÃͤÎÈÏ°Ï Í×ÁÇ¿ô¤Î¥Ó¥Ã¥ÈĹ + (ÇÛÎó) (Éä¹æĹ) + p_len np 0..16 pbit + c_len NC 0..16 CBIT + t_len NT 0..16 TBIT + + Í×ÁÇ¿ô¤Ï°µ½ÌÂоݤÎʸ»ú½¸¹ç¤Î¿ô + c_len[x]=0 ¤Î¾ì¹ç¡¢Ê¸»ú x ¤ÏÊ£¹ç¤·¤¿·ë²Ì¤Ë¸½¤ì¤Ê¤¤ + Í×ÁÇ¿ô¤Î¥Ó¥Ã¥ÈŤÏÍ×ÁÇ¿ô¤òɽ¸½¤¹¤ë¤Î¤ËɬÍ×¤Ê¥Ó¥Ã¥È + Ĺ(¤³¤Î¸å¤Ç½Ð¤Æ¤¯¤ë) +---------------------------------------------------------------------------- + +¤Ç¤Ï¡¢Huffman ÌڤξðÊó¤Î½ÐÎÏ·Á¼°¤Ë¤Ä¤¤¤ÆÀ°Íý¤·¤è¤¦¡£ + +¤Þ¤º¡¢p_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È¤ò²¼µ­¤Ë¼¨¤¹¡£ + +---------------------------------------------------------------------------- +< p_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > + + 0 pbit{4 or 5} + +-------+-----------+-----------+-- --+-----------+ + | n | p_len[0] | p_len[1] | ... p_len[n-1]| + +-------+-----------+-----------+-- --+-----------+ + +p_len[i] <= 6 ¤Î¾ì¹ç + + 0 3bit + +-----+ + p_len[i] | | | | + +-----+ + +p_len[i] >= 7 ¤Î¾ì¹ç + + 0 p_len[i] - 3 + +----------------+ + p_len[i] |1 1 1 1 ... 1 0 | + +----------------+ + +p_len[n...np] ¤Ï¡¢0 ¤È¤Ê¤ë¡£ + +---------------------------------------------------------------------------- + +Àè¤Ë¤â½ñ¤¤¤¿Ä̤ê p_len ¤Ï°ÌÃÖ¤ÎÃͤÎɬÍץӥåÈŤò Huffman Éä¹æ²½¤·¤¿¤È +¤­¤ÎÌڤξðÊó¤Ç¤¢¤ë¡£¥¹¥é¥¤¥É¼­½ñ¤Î¥µ¥¤¥º¤Ï dicsiz ¤Ç¤¢¤ê -lh7- ¤Î¾ì¹ç¤Ç +16 bit ¤Ç°ÌÃÖ¤ò»Ø¤¹¤³¤È¤¬¤Ç¤­¤ë¤«¤é¡¢p_len ¤Ï°ÌÃ֤ΥӥåÈĹ 0 .. 16 ¤Î +17¸Ä(np¸Ä)¤ÎÃͤò Huffman Éä¹æ²½¤·¤¿·ë²Ì(¤ÎÉä¹æĹ)¤Ç¤¢¤ë¡£ + +¤½¤·¤Æ p_len ¼«ÂΤνÐÎϤˤĤ¤¤Æ¤Ï¡¢0 .. 6 ¤ÎÃÍ(Huffman Éä¹æĹ)¤Ë¤Ä¤¤¤Æ +¤Ï 3 bit ¤Ç¡¢¤½¤ì°Ê¾å¤ÎÃͤˤĤ¤¤Æ¤Ï 0 ¤¬¸½¤ì¤ë¤Þ¤Ç¤Î¥Ó¥Ã¥È¿ô¤Çɽ¤¹¤è¤¦ +¤Ë¤Ê¤Ã¤Æ¤¤¤ë¡£ + +¤Ê¤ª p_len ¤Ï np ¸Ä¤Î¸ÇÄêĹÇÛÎó¤À¤¬¡¢½ÐÎÏ·Á¼°¤È¤·¤Æ¤ÏÀèƬ¤Ë pbit Éý +¤Î p_len ¤ÎÍ×ÁÇ¿ô¤ò½ÐÎϤ·¤Æ¤¤¤ë¡£¤³¤ì¤Ï¤Ê¤¼¤«¤È¤¤¤¦¤È p_len ¤Î¸åÊý¤ÎÃÍ +(p_len[n...np])¤¬ 0 ¤Ç¤¢¤ë¾ì¹ç¤Ë¤½¤ÎÍ×ÁǤò½ÐÎϤ·¤Ê¤¤¤ÇºÑ¤à¤è¤¦¤Ë¤¹¤ë¤¿ +¤á¤Ç¤¢¤ë¡£¤³¤ì¤Ï¾¤Î Huffman Éä¹æ¤Ë¤Ä¤¤¤Æ¤âƱÍͤǤ¢¤ë¡£ + +# ¤Ê¤¼¡¢¤³¤Î¤è¤¦¤Ê·Á¼°¤Ë¤Ê¤Ã¤Æ¤¤¤ë¤«¹Í¤¨¤Æ¤ß¤¿¡£ +# +# p_len ¤ÎÃͤÎÈϰϤϡ¢0 .. 16 ¤Ç¤¢¤ë¤«¤é 1 Í×ÁÇ¤Ï 6 bit ¤Çɽ¸½²Äǽ¤Ç¤¢¤ê¡¢ +# ñ½ã¤Ë½ÐÎϤ·¤¿¾ì¹ç¤ò¹Í¤¨¤ë¤È 6 * 17 = 102 bit ¤Çɽ¸½²Äǽ¤Ç¤¢¤ë¡£ +# +# °ìÊý¡¢p_len ¤Î½ÐÎÏ·Á¼°¤Î¾ì¹ç¡¢LHA ¤Î Huffman Ìڤγ¬ÁؤϺÇÂç 16 ³¬ÁؤǤ¢ +# ¤ë¤³¤È¤«¤é¡¢ºÇ°­¤¹¤Ù¤Æ¤Î p_len[] ¤Ë¤Ä¤¤¤Æ¥Ó¥Ã¥È¿ô¤Î·Á¼°(p_len[] >= 7) +# ¤¬»È¤ï¤ì¤¿¾ì¹ç 1 ¤Ä¤Î p_len[] ¤Ë 16-3 bit * 17 = 221 bit »È¤¦¤³¤È¤Ë¤Ê +# ¤êºÇ°­¤Î»ÈÍÑÎΰè¤ÏÂ礭¤¯¤Ê¤Ã¤Æ¤·¤Þ¤¦¤è¤¦¤Ë»×¤¨¤Æ¤·¤Þ¤¦¡£ +# +# ¤·¤«¤·¡¢¼ÂºÝ¤Ë¤Ï¤½¤¦¤Ï¤Ê¤é¤Ê¤¤¡£¤È¤¤¤¦¤Î¤â np ¤¬ 17 ¤Ç¤¢¤ë¤«¤é +# Huffman ÌÚ¤ÎÍդοô¤ÏºÇÂç¤Ç¤â 17 ¤Ë¤·¤«¤Ê¤é¤Ê¤¤¡£¤½¤·¤ÆÍդοô¤¬ np ¤Ç +# ºÇ¤â Huffman ÌÚ¤¬¿¼¤¯¤Ê¤ë¤Î¤Ï +# +# . +# / \ +# . . -- 1 ³¬ÁØÌÜ +# / \ +# . . -- 2 ³¬ÁØÌÜ +# / \ +# . . -- 3 ³¬ÁØÌÜ +# : +# . +# / \ +# . . -- 16 ³¬ÁØÌÜ +# +# ¤È¤Ê¤ë¾ì¹ç¤Ç¡¢¤³¤Î¾ì¹ç¤Î p_len ¤Î½ÐÎϥӥåÈĹ¤Ï +# +# 2*(16-3) + (15-3) + ... (7-3) + 6*3 +# = 2*13 + 12 + ... 4 + 18 +# = 167 bit +# +# ¤Ç¤¢¤ë¡£Ã±½ã¤Ë½ÐÎϤ¹¤ë¾ì¹ç¤ËÈæ¤Ù¤ë¤È 65 bit Áý¤¨¤ë¡£¤Þ¤¿¡¢1 ³¬Áظº¤é +# ¤·¤¿¾ì¹ç¤Ï¡¢ +# +# . +# / \ +# . . -- 1 ³¬ÁØÌÜ +# / \ +# . . -- 2 ³¬ÁØÌÜ +# / \ +# . . -- 3 ³¬ÁØÌÜ +# : +# / \ +# . . -- 13 ³¬ÁØÌÜ +# / \ +# . . +# / \ / \ +# . . . . -- 15 ³¬ÁØÌÜ +# +# 4*(15-3) + (13-3) + ... (7-3) + 6*3 +# = 4*12 + 10 + ... 4 + 18 +# = 115 bit +# +# ¤Ç¤¢¤ë¡£¤Ê¤ª¡¢¤³¤ÎÌڤξì¹ç¤âÍÕ¤Ï np ¸Ä¤¢¤ë¡£¤â¤¦ 1 ³¬Áظº¤é¤·¤Æ¤ß¤è¤¦¡£ +# +# . +# / \ +# . . -- 1 ³¬ÁØÌÜ +# / \ +# . . -- 2 ³¬ÁØÌÜ +# / \ +# . . -- 3 ³¬ÁØÌÜ +# : +# / \ +# . . -- 12 ³¬ÁØÌÜ +# / \ / \ +# . . . . -- 13 ³¬ÁØÌÜ +# / \ / \ +# . . . . -- 14 ³¬ÁØÌÜ +# +# +# 4*(14-3) + 2*(13-3) + (11-3) + ... + (7-3) + 6*3 +# = 4*11 + 2*10 + 8 + ... 4 + 18 +# = 112 bit +# +# ¤³¤ÎÄ´»Ò¤Ç¡¢¤µ¤é¤Ë¸º¤é¤¹¤È +# +# 13 ³¬ÁØ +# 4*(13-3) + 2*(12-3) + (10-3) + ... + (7-3) + 6*3 +# = 4*10 + 2*9 + 7 + ... + 4 + 18 +# = 98 +# +# 13 ³¬ÁØÌܤÇñ½ã¤Ë½ÐÎϤ¹¤ë¤è¤ê¤â¾®¤µ¤¯¤Ê¤Ã¤¿¡£´¶³ÐŪ¤Ë¤Ï¡¢¤¢¤Þ¤ê¸ú²Ì¤Ï +# ´üÂԤǤ­¤Ê¤¤¤è¤¦¤Ë¸«¤¨¤ë¡£¤³¤ì¤Ï¶²¤é¤¯¤Ï p_len ¤Ë¤Ä¤¤¤Æ¤ÏÉä¹æŤ¬ 6 +# °Ê²¼¤Ë¤Ê¤ë¾ì¹ç¤¬Â¿¤¤¤Î¤Ç¤¢¤í¤¦(¤¹¤Ù¤Æ¤¬ 6 °Ê²¼¤Ç¤¢¤ì¤Ð¡¢3 * 17 = 51 +# bit ¤Ç¤¢¤ê 51 bit ºï¸º¤Ç¤­¤ë)¡£³¬Áؤ¬ 6 ¤Ç¤¢¤ë Huffman ÌÚ¤ÎÍդοô¤ÏºÇ +# Âç 2^6 {64} ¤Ç¤¢¤ë¤«¤é NP{17} ¼ïÎà¤Îʿʸ¤ò³ÊǼ¤¹¤ëΨ¤¬¹â¤¤¤Î¤Ç¤¢¤í¤¦¡£ + +³¤¤¤Æ c_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È¤ò¼¨¤¹¡£ + +---------------------------------------------------------------------------- +< c_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > + + 0 CBIT{9} + +-------+-----------+-----------+-- --+-----------+ + | n | c_len[0] | c_len[1] | ... c_len[n-1]| + +-------+-----------+-----------+-- --+-----------+ + +c_len[i] == 0 ¤Î¾ì¹ç + + 0 ¤¬Â³¤¯¿ô¤ò count ¤È¤¹¤ë¤È¡¢ + + count == 1 ¤Î¾ì¹ç + + t_len[0] + <----------> + +------------+ + | t_code[0] | + +------------+ + + count == 2 ¤Î¾ì¹ç + + t_len[0] t_len[0] + <----------> <----------> + +------------+------------+ + | t_code[0] | t_code[0] | + +------------+------------+ + + count == 3..18 ¤Î¾ì¹ç + + t_len[1] 4 bit + <----------> <------> + +------------+-------+ + | t_code[1] |count-3| + +------------+-------+ + + count == 19 ¤Î¾ì¹ç + + t_len[0] t_len[1] 4 bit + <----------> <----------> <------> + +------------+------------+-------+ + | t_code[0] | t_code[1] |count-3| + +------------+------------+-------+ + + count >= 20 ¤Î¾ì¹ç + + t_len[2] CBIT{9} + <----------> <------> + +------------+--------+ + | t_code[2] |count-20| + +------------+--------+ + +c_len[i] > 0 ¤Î¾ì¹ç + + t_len[c_len[i]+2] + <-----------------> + +-------------------+ + | t_code[c_len[i]+2]| + +-------------------+ + +c_len[n...NC] ¤Ï¡¢0 ¤È¤Ê¤ë¡£ + +---------------------------------------------------------------------------- + +c_len[] ¤ÎÃͤϤ¢¤ëÄøÅÙ 0 ¤¬Ï¢Â³¤¹¤ë¾ì¹ç¤¬Â¿¤¤¤³¤È¤¬´üÂԤǤ­¤ë¡£ +c_len[i]=0 ¤Î¾ì¹ç¤È¤¤¤¦¤Î¤Ï¤½¤Îʸ»ú(i)¤¬Ê¿Ê¸¤Ë¸½¤ì¤Ê¤¤¾ì¹ç¤ò¼¨¤¹¡£ +ASCII ¥Æ¥­¥¹¥È¥Õ¥¡¥¤¥ë¤Î°µ½Ì¤Ê¤é 0..127 ¤ÎÈϰϤΥ³¡¼¥É¤·¤«»È¤ï¤ì¤Ê¤¤¤¿ +¤á¤½¤ì°Ê³°¤Ï 0 ¤Ë¤Ê¤ë¤Ê¤É¤Ç¤¢¤ë¡£¤½¤·¤Æ c_len ¤òñ½ã¤Ë½ÐÎϤ¹¤ë¤³¤È¤ò¹Í +¤¨¤¿¤È¤­ c_len[i]=0 ¤Ç¤¢¤ë¾ðÊó¤ò¿¿ô½ÐÎϤ¹¤ë¤³¤È¤Ë¤Ê¤êÎΰ褬̵Â̤Ǥ¢¤ë +(c_len ¤Ï NC{255+256+2-3=510} ¸Ä¤ÎÍ×ÁǤò»ý¤Á¤½¤ÎÃæ¤Ç̤»ÈÍÑʸ»ú¤ä̤»ÈÍÑ +Ť¬Â¿¿ô¤¢¤ë¤³¤È¤òÁÛÄꤷ¤Æ¤¤¤ë)¡£¤½¤³¤Ç 0 ¤¬Ï¢Â³¤·¤Æ¸½¤ì¤ëÆÃħ¤òÀ¸¤«¤· + + o c_len[]=0 ¤¬Ï¢Â³¤Ç1¸Ä + o c_len ¤¬Ï¢Â³¤Ç 3¡Á18 ¸Ä + o c_len ¤¬Ï¢Â³¤Ç20¸Ä°Ê¾å(20¡ÁNC{510}) + +¤ò¤½¤ì¤¾¤ì°ì¤Ä¤Îʸ»ú¤È¸«¤Ê¤·¤Æ Huffman Éä¹æ²½¤¹¤ë¤³¤È¤Ç c_len ¼«ÂΤνР+ÎÏ¥µ¥¤¥º¤ò¾®¤µ¤¯¤·¤Æ¤¤¤ë¡£¤³¤ì¤Ï 0 ¤Î½Ð¸½ÉÑÅÙ¤òñ½ã¤Ë Huffman Éä¹æ²½¤¹ +¤ë¤è¤ê¤â¸ú²Ì¤¬´üÂԤǤ­¤ë¡£ + +¾å¿Þ¤Ç t_code ¤Ï c_len ¤ò Huffman Éä¹æ²½¤·¤¿¤È¤­¤ÎÉä¹æɽ¤ò¼¨¤·¤Æ¤ª¤ê + + o t_code[0] ... c_len[i] ¤Ï 0 ¤¬ 1 ¸Ä + o t_code[1] ... c_len[i] ¤Ï 0 ¤¬ 3¡Á18 ¸Ä(³¤¯4 ¥Ó¥Ã¥È¤Î¥Ó¥Ã¥ÈÎó¤Ç + ¸Ä¿ô¤¬¤ï¤«¤ë) + o t_code[2] ... c_len[i] ¤Ï 0 ¤¬ 20¡ÁNC-1¸Ä(³¤¯ CBIT ¥Ó¥Ã¥È¤Î¥Ó¥Ã¥È + Îó¤Ç¸Ä¿ô¤¬¤ï¤«¤ë) + o t_code[x] ... c_len[i]=x-2 (x>2) + +¤ÈÉü¹æ¤¹¤ë¤³¤È¤Ë¤Ê¤ë¡£c_len[i] = 0 ¤¬ 2 ¸Ä¤¢¤ë¤¤¤Ï 19 ¸Ä³¤¯¾ì¹ç¤Ï + + t_code[0] ¤¬ 2 ¸Ä + t_code[0] ¤È t_code[1] ¤¬ 1 ¸Ä¤º¤Ä + +¤Ç½ÐÎϤµ¤ì¤Æ¤¤¤ë¡£ + +ºÇ¸å¤Ë¡¢t_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È¤ò¼¨¤¹¡£ + +---------------------------------------------------------------------------- +< t_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > + + 2 bit + 0 TBIT{5} |--| + +-------+----------+----------+----------+--+----------+- -+-----------+ + | n | t_len[0] | t_len[1] | t_len[2] | x|t_len[x+3]| ... | t_len[n-1]| + +-------+----------+----------+----------+--+----------+- -+-----------+ +t_len[i] <= 6 ¤Î¾ì¹ç + + 0 3bit + +-----+ + t_len[i] | | | | + +-----+ + +t_len[i] >= 7 ¤Î¾ì¹ç + + 0 t_len[i] - 3 + +----------------+ + t_len[i] |1 1 1 1 ... 1 0 | + +----------------+ + +t_len[2] ¤Îľ¸å¤Ï 2 bit ¤Î¾ðÊó¤¬Éղ䵤ì¤ë¡£¤³¤ÎÃͤò x{0..3} ¤È¤¹¤ë¤È¡¢ +t_len[3 .. x+2] ¤ÎÈÏ°Ï¤Ç 0 ¤¬Â³¤¯¤³¤È¤ò°ÕÌ£¤·¡¢¤³¤Î 2 bit °Ê¹ß¤Ï¡¢ +t_len[x+3] ¤¬Â³¤¯¤³¤È¤Ë¤Ê¤ë¡£x ¤¬ 0 ¤Î¾ì¹ç¤Ï¡¢t_len[3] ¤Ï 0 ¤Ç¤Ï¤Ê¤¤¡£ + +t_len[n...NT] ¤Ï¡¢0 ¤È¤Ê¤ë¡£ + +---------------------------------------------------------------------------- + +´ðËÜŪ¤Ê¹Í¤¨¤Ï p_len[] ¤Î¾ì¹ç¤ÈƱ¤¸¤Ç¤¢¤ë(t_len[] ¤ÎÍ×ÁÇ¿ô NT ¤Ï 19)¡£ +¤¿¤À¤· t_len[3..5] ¤Ë¤Ä¤¤¤ÆÆÃÊÌ°·¤¤¤µ¤ì¤Æ¤¤¤ë¡£ + +¤Þ¤º¡¢t_len[] ¤È c_len[x] ¤ÎÃͤÎÂбþ¤ò°Ê²¼¤ËÀ°Íý¤·Ä¾¤¹¡£ + + t_len[0] c_len[x]=0 1 ¤Ä¤ò 1 ʸ»ú¤È¤ß¤Ê¤¹ + t_len[1] c_len[x]=0 ¤¬ 3¡Á18 ¸ÄϢ³¤·¤Æ¤¤¤ë²ô¤ò 1 ʸ»ú¤È¤ß¤Ê¤¹ + t_len[2] c_len[x]=0 ¤¬ 20¡ÁNC{510} ¸ÄϢ³¤·¤Æ¤¤¤ë²ô¤ò 1 ʸ»ú¤È¤ß¤Ê¤¹ + t_len[3] c_len[x]=1 + t_len[4] c_len[x]=2 + t_len[5] c_len[x]=3 + t_len[6] c_len[x]=4 + : + t_len[18] c_len[x]=16 + +t_len[3..5] ¤ÎÆÃÊÌ°·¤¤¤Ë¤Ä¤¤¤Æ¹Í¤¨¤ë¤È t_len[3..5] ¤ÎÈÏ°Ï¤Ç 0 ¤¬Ï¢Â³¤¹ +¤ë¾ì¹ç¤Ë¡¢2 ¥Ó¥Ã¥È¤Ç¤½¤Î¤³¤È¤òɽ¤·¤Æ¤¤¤ë¡£¤³¤ì¤Ï¤Ä¤Þ¤ê¤³¤Î¤è¤¦¤Ê¾ì¹ç¤¬ +¿¤¤¤Î¤Ç¤¢¤í¤¦¡£¾å¤ÇÂбþ´Ø·¸¤ò¼¨¤·¤¿¤È¤ª¤ê¡¢t_len[3..5] ¤¬ 0 ¤Ç¤¢¤ë¾ì¹ç +¤È¤¤¤¦¤Î¤Ï¡¢¤Ä¤Þ¤ê¥Ó¥Ã¥ÈĹ c_len[x] ¤¬ 1..3 ¤ÎÈϰϤÎÃͤò»ý¤¿¤Ê¤¤¾ì¹ç¤ò +¼¨¤¹¡£ + +# c_len[x] ¤¬ 1..3 ¤ÎÃͤò»ý¤Ä¾ì¹ç¤È¤¤¤¦¤Î¤Ï Huffman Ìڤˤª¤¤¤Æ¤¢¤ë 3 ʸ»ú +# ¤Î½Ð¸½ÉÑÅÙ¤¬¶Ëü¤Ë¿¤¤¾ì¹ç¤ò¼¨¤¹¡£¤³¤Î¤è¤¦¤Ê¾ì¹ç¤Ï¤¢¤Þ¤ê¤Ê¤¤¤Ç¤¢¤ë¤ÈÁÛ +# Äꤷ¤Æ¤¤¤ë¤Î¤À¤í¤¦¡£ +# +# . +# / \ +# a . +# / \ +# b . +# / \ +# c . +# / \ +# . . +# / \ / \ + +°Ê¾å¤Ç LHA ¥Õ¥¡¥¤¥ë¤Î¹½Â¤¤Ë¤Ä¤¤¤Æ¤Ò¤È¤È¤ª¤êÀâÌÀ¤·¤¿¤³¤È¤Ë¤Ê¤ë¡£¤¿¤À¤·¡¢ +Éü¹æ½èÍý¤ò¹Í¤¨¤ë¾ì¹ç¤ËÃí°Õ»ö¹à¤¬¤¢¤ë¡£¤³¤ì¤Ï¤³¤Î¸å¤ÇÀâÌÀ¤·¤è¤¦¡£ + + +¥»¥­¥å¥ê¥Æ¥£¥Ð¥°¤Î¹Í»¡ +---------------------- + +2006ǯ8·î LHA ¤ÎÉü¹æ½èÍý¤Ë¥»¥­¥å¥ê¥Æ¥£¥Ð¥°(CVE-2006-4335,4337,4338)¤¬È¯ +¸«¤µ¤ì¤¿¡£¤³¤ÎÌäÂê¤Ï LHA ¤Î¼ÂÁõ¤Ë¤ª¤¤¤ÆÉä¹æ²½¤Ë¤Ä¤¤¤Æ¤ÏÅöÁ³¤¢¤é¤æ¤ëÆþÎÏ +¥Õ¥¡¥¤¥ë¤òÁÛÄꤷ¤¿½èÍý¤È¤Ê¤Ã¤Æ¤¤¤ë¤¬Éü¹æ¤Ë¤Ä¤¤¤Æ¤Ï°µ½Ì¥Õ¥¡¥¤¥ë¤¬Àµ¤·¤¤ +¹½Â¤¡¢ÃͤǺîÀ®¤µ¤ì¤Æ¤¤¤ë¤³¤È¤·¤«ÁÛÄꤻ¤º¤Ë½èÍý¤¬ºî¤é¤ì¤Æ¤¤¤¿¤¿¤á¤Ç¤¢¤ë¡£ +¤Ä¤Þ¤ê¡¢ÉÔÀµ¤Ê°µ½Ì¥Õ¥¡¥¤¥ë¤¬Í¿¤¨¤é¤ì¤¿¾ì¹ç¤ÎÆ°ºî¤¬ÉÔÄê¤À¤Ã¤¿¤Î¤À¡£ + +¤³¤³¤Ç¤Ï¡¢LHA ¤ÎÉü¹æ¤Ë¤ª¤¤¤ÆÃí°Õ¤¹¤Ù¤­ÅÀ¤Ë¤Ä¤¤¤Æ¹Í»¡¤¹¤ë¡£¤Þ¤¿¡¢¤³¤³¤Þ +¤Ç¤Ë²òÆɤ·¤¿ LHa for UNIX ver.1.14i ¤Î¥½¡¼¥¹¤Ï¤³¤Î¥»¥­¥å¥ê¥Æ¥£¥Ð¥°¤¬ +»Ä¤Ã¤Æ¤¤¤¿¤â¤Î¤Ê¤Î¤Ç¡¢¥»¥­¥å¥ê¥Æ¥£¥Ð¥°¤ÎÂкö¤ò¹Ô¤Ã¤¿¥½¡¼¥¹¤Ë¤Ä¤¤¤Æ¤â¸å +¤Ç²òÀϤò¹Ô¤¦¤³¤È¤È¤¹¤ë¡£ + +°Ê²¼¡¢LHA ¤Î¹½Â¤¤òºÆ·Ç¤·¡¢³ÆÉü¹æ½èÍý¤ÇÃí°Õ¤¹¤Ù¤­ÅÀ¤ò³Îǧ¤·¤è¤¦¡£ +°Ê¹ß¤ÎÀâÌÀ¤Ç¤ÏÃí°ÕÅÀËè¤Ë (1) (2) ¤Î¤è¤¦¤ËÈÖ¹æ¤ò¿¶¤Ã¤Æ¤¤¤ë¡£ºÇ½ªÅª¤Ë +Á´¥Á¥§¥Ã¥¯¥Ý¥¤¥ó¥È¤ò¥Á¥§¥Ã¥¯¤¹¤ë¤è¤¦¤Ë½¤Àµ¤·¤¿¥½¡¼¥¹¤òºÜ¤»¡¢¤³¤ÎÈÖ¹æ¤Ç +ɳÉÕ¤±¤ò¹Ô¤¦¤³¤È¤È¤¹¤ë¡£ + +---------------------------------------------------------------------------- +< LHA ¥Õ¥¡¥¤¥ë¤Î¹½Â¤(1 ¥Ö¥í¥Ã¥¯Ê¬) > + + +-----------+ + | blocksize | + +-----------+ + 16bit + + ¥Ï¥Õ¥Þ¥óÌÚ + +-----------+-----------+-----------+ + | t_len | c_len | p_len | + +-----------+-----------+-----------+ + + °µ½Ìʸ(ʸ»ú¤ÈŤµ¡¢°ÌÃ֤ΥӥåÈĹ¤Î¥Ï¥Õ¥Þ¥óÉä¹æ¤È°ÌÃÖ¤ÎÃÍ) + +---------------------+ + | °µ½Ìʸ | + +---------------------+ + +---------------------------------------------------------------------------- + +(1) +blocksize ¤ÎÆɤ߹þ¤ß¤Ë¤Ä¤¤¤Æ¤³¤ÎÃÍ¤Ï 1¡Á0xffff ¤Ë¤Ä¤¤¤Æ¤ÏÀµ¤·¤¤¤¬ 0 ¤Ë +¤Ê¤ë¤³¤È¤Ï¤¢¤êÆÀ¤Ê¤¤¤Î¤Ç 0 ¤Î¾ì¹ç¤ËÉÔÀµ¤ÈȽÃǤ·¤Æ¤â¤è¤¤¤È»×¤ï¤ì¤ë¡£ + +(2) +¡Ö°µ½Ìʸ¡×¼«ÂΤˤĤ¤¤Æ¤Ï¡¢blocksize ¿ô¤òÍê¤ê¤ËÆɤ߹þ¤à¤Î¤Ç blocksize ¤ò +±Û¤¨¤Æ°µ½Ìʸ¤¬Â¸ºß¤·¤Æ¤â¼¡¤Î block ¤È¤·¤ÆÆɤޤì¤ë¤À¤±¤Ç¤¢¤ë¡£blocksize +¤ËËþ¤¿¤Ê¤¤¾ì¹ç¤Ï¡¢EOF ¤ò¸¡ÃΤ·¤ÆÁá´ü¤ËÉÔÀµ¤ÈȽÃǤ¹¤ë¤è¤¦¤Ë½èÍý¤·¤¿Êý¤¬ +¤è¤¤¤À¤í¤¦¡£ + +°µ½ÌʸÃæ¤Îʸ»ú¤ÈŤµ¤Ë¤Ä¤¤¤Æ¤Ï + + Éü¹æ¤·¤¿1ʸ»ú >= 256 ¤Î¾ì¹ç + Ťµ¤ò¼¨¤¹¡£(¤½¤·¤Æ¤½¤Îľ¸å¤Ë°ÌÃ֤ΠHuffman Éä¹æ¤¬¤¢¤ë) + + Éü¹æ¤·¤¿1ʸ»ú < 256 ¤Î¾ì¹ç + ʸ»ú¤ò¼¨¤¹¡£ + +¤Ç¤¢¤ê¡¢Ê¸»ú¤È¤·¤Æ¤Ï 0 .. 255 ¤¹¤Ù¤Æ¤Ë¤Ä¤¤¤ÆÀµ¤·¤¤ÃͤʤΤÇÌäÂê¤Ï¤Ê¤¤¡£ + +(3) +Ťµ¤Ï 256 ... NC{256+maxmatch-3+1} ¤ÎÈϰϤÎÃͤò¼è¤ë¤Î¤Ç¤³¤ì¤òĶ¤¨¤ëÃÍ +¤òÊÖ¤¹¾ì¹ç¤ÏÉÔÀµ¤ÈȽÃǤ·¤Æ¤â¤è¤¤¡£¤¿¤À¤·¡¢¤³¤ÎȽÄ꼫ÂÎ¤Ï c_len ¤òÆɤ߹þ +¤ß Huffman ÌÚ¤ò¹½ÃÛ¤¹¤ë¤È¤­¤Ë¹Ô¤¦¤³¤È¤â¤Ç¤­¤ë¡£(¼ÂºÝ¡¢¼ÂÁõ¤Ç¤Ï +Huffman Ìڤˤ³¤ÎÈÏ°ÏÆâ¤ÎÉü¹æ¸ì¤·¤«³ä¤êÅö¤Æ¤Ê¤¤¤Î¤Ç¥Ð¥°¤Ç¤Ê¤¤¸Â¤ê¤ÏȯÀ¸ +¤·¤Ê¤¤¤À¤í¤¦) + +°ÌÃ֤ˤĤ¤¤Æ¤Ï²¼¿Þ¤ÎÄ̤ê°ÌÃ֤ΥӥåÈŤΠHuffman Éä¹æ¤È°ÌÃÖ¤ÎÃͤ¬½ñ¤«¤ì +¤Æ¤¤¤ë¡£ + + +------------------------------+----------+ + | °ÌÃ֤ΥӥåÈŤΠHuffman Éä¹æ| °ÌÃÖ¤ÎÃÍ | + +------------------------------+----------+ + +(4) +°ÌÃÖ¤ÎÃͤȤ·¤Æ¤Ï 0 ... 2^dicbit ¤ÎÈϰϤÎÃͤò»ý¤Ä¤Î¤Ç Huffman Éä¹æ¤ÎÉü¹æ +·ë²Ì¤¬ 0 ... np{dicbit+1} ¤ÎÈϰϤǤ¢¤ì¤Ð°ÌÃÖ¤ÎÃÍÉôʬ¤Ë¤Ä¤¤¤Æ¥Á¥§¥Ã¥¯¤¹ +¤ëɬÍפϤʤ¤¡£½¾¤Ã¤Æ¡¢c_len ¤ÈƱ¤¸¤¯¥Ï¥Õ¥Þ¥óÌڤι½ÃÛ¤ÎÃʳ¬¤ÇÉÔÀµ¤ÊÉü¹æ +¸ì¤òÊÖ¤µ¤Ê¤¤¤è¤¦¤Ë¤·¤Æ¤¤¤ì¤Ð¤è¤¤¡£ + +¤Ç¤Ï¡¢t_len ¤Ë¤Ä¤¤¤Æ¸«¤Æ¤ß¤ë¡£ + +---------------------------------------------------------------------------- +< t_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > + + 2 bit + 0 TBIT{5} |--| + +-------+----------+----------+----------+--+----------+- -+-----------+ + | n | t_len[0] | t_len[1] | t_len[2] | x|t_len[x+3]| ... | t_len[n-1]| + +-------+----------+----------+----------+--+----------+- -+-----------+ + +t_len[i] <= 6 ¤Î¾ì¹ç + + 0 3bit + +-----+ + t_len[i] | | | | + +-----+ + +t_len[i] >= 7 ¤Î¾ì¹ç + + 0 t_len[i] - 3 + +----------------+ + t_len[i] |1 1 1 1 ... 1 0 | + +----------------+ + +t_len[2] ¤Îľ¸å¤Ï 2 bit ¤Î¾ðÊó¤¬Éղ䵤ì¤ë¡£¤³¤ÎÃͤò x{0..3} ¤È¤¹¤ë¤È¡¢ +t_len[3 .. x+2] ¤ÎÈÏ°Ï¤Ç 0 ¤¬Â³¤¯¤³¤È¤ò°ÕÌ£¤·¡¢¤³¤Î 2 bit °Ê¹ß¤Ï¡¢ +t_len[x+3] ¤¬Â³¤¯¤³¤È¤Ë¤Ê¤ë¡£x ¤¬ 0 ¤Î¾ì¹ç¤Ï¡¢t_len[3] ¤Ï 0 ¤Ç¤Ï¤Ê¤¤¡£ + +t_len[n...NT] ¤Ï¡¢0 ¤È¤Ê¤ë¡£ + +---------------------------------------------------------------------------- + +(5) +t_len ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È¤ÎÀèƬ TBIT{5} ¤Ï 0 ... 2^5{32} ¤ÎÈϰϤÎÃͤò³Ê +Ǽ¤Ç¤­¤ë¤¬ t_len ¤ÎÎΰ襵¥¤¥º¤Ï NT{19} ¤Ê¤Î¤Ç 0..19 ¤ÎÈϰϤòĶ¤¨¤ë¾ì¹ç +¤ÏÉÔÀµ¤ÈȽÃǤ·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£ + +(6) +¤Þ¤¿¡¢t_len[i] >= 7 ¤Î¾ì¹ç¤Î·Á¼°¤Ï bit 0 ¤ò¸¡½Ð¤¹¤ë¤Þ¤Ç¤Î¥Ó¥Ã¥ÈŤ¬ÃÍ¤È +¤Ê¤ë¤¬ t_len[i] ¤ÎÃͤϥϥեޥóÉä¹æĹ¤Ê¤Î¤Ç 0 .. 16 ¤ÎÈϰϤǤʤ±¤ì¤Ð¤Ê¤é +¤Ê¤¤¡£t_len[i] >= 7 ¤Î·Á¼°¤Î¶ñÂÎŪ¤ÊÃͤÎÂбþ¤Ï + + 7: 1110 + 8: 1111 0 + : + 15: 1111 1111 1110 + 16: 1111 1111 1111 0 + +¤È¤Ê¤Ã¤Æ¤¤¤ë¤Î¤Ç¡¢16 ¤Î¾ì¹ç¤Î¥Ó¥Ã¥ÈĹ(1 ¤¬ 12 bit ³¤¯)¤è¤ê¥Ó¥Ã¥ÈŤ¬Ä¹ +¤¤¾ì¹ç¤ÏÉÔÀµ¤Ç¤¢¤ë¡£(ºÇÂç 12 ¥Ó¥Ã¥È¤Þ¤Ç¤·¤«¸«¤Ê¤¤¤È¤¹¤ë¤³¤È¤â¹Í¤¨¤é¤ì¤ë¤¬¡¢ +LHA ¤Î°µ½Ì½èÍý¤Ï¾å¤ÎÎã¤Î¤è¤¦¤Ë 16 ¤Î¾ì¹ç¤Ç¤â¥Ó¥Ã¥È 0 ¤ò½ÐÎϤ¹¤ë¤Î¤Ç¡¢¤½ +¤Î¤è¤¦¤ÊÆɤßÊý¤ò¤¹¤ë¤ÈÀµ¾ï¤Ê°µ½Ìʸ¤òÉü¹æ¤Ç¤­¤Ê¤¯¤Ê¤ë¡£) + +(7) +¤µ¤é¤Ë¡¢t_len ¤òÆɤ߹þ¤ó¤À¸å¤Ë¹½ÃÛ¤·¤¿ Huffman ÌÚ¤Ï Huffman ÌڤȤ·¤ÆÀ°¹ç +À­¤¬Êݤ¿¤ì¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£ +¤¿¤È¤¨¤Ð¡¢LHA ¤Ë¤ª¤±¤ë Huffman Ìڤϰʲ¼¤ÎÀ­¼Á¤¬¼é¤é¤ì¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¤Ï +¤º¤À¡£ + + o t_len[x] <= 16 (LHA ¤Î Huffman Ìڤγ¬ÁØ¤Ï 16 ¤Þ¤Ç¤Ç¤¢¤ë) + + o ³Æ³¬ÁؤÎÍդοô¤ÏÀ°¹çÀ­¤¬Êݤ¿¤ì¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£Î㤨¤Ð¡¢1 ³¬ÁØÌܤΠ+ Íդοô¤ÏºÇÂç 2 ¤Ç¤¢¤ê¡¢¤³¤Î¤È¤­²¼°Ì¤Î³¬ÁؤÎÍդοô¤Ï 0 ¤Ç¤¢¤ë¡£³ÆÀá + ¤Ïɬ¤ºÀᤫÍÕ¤ò»ý¤Ä¡£¤Ê¤É¡£ + +¸å¤Ç½èÍý¤ò²òÀϤ¹¤ëºÝ¤Ë¤³¤ÎÊÕ¤ê¤ò³Îǧ¤·¤è¤¦¡£ +¤Ê¤ª¡¢1 ÅÀÌܤˤĤ¤¤Æ¤ÏÁ°½Ò¤ÎÄ̤ê t_len ¤ÎÆɤ߹þ¤ß»þ¤Ë¥Á¥§¥Ã¥¯¤Ç¤­¤ë¡£ +2 ÅÀÌܤˤĤ¤¤Æ¤Ï¼ÂÁõ¤Ç¤ÏÈó¾ï¤Ë¤¦¤Þ¤¤ÊýË¡¤Ç¥Á¥§¥Ã¥¯¤·¤Æ¤¤¤ë¡£ + +³¤¤¤Æ c_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È¤Ë¤Ä¤¤¤Æ¹Í¤¨¤ë¡£ + +---------------------------------------------------------------------------- +< c_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > + + 0 CBIT{9} + +-------+-----------+-----------+-- --+-----------+ + | n | c_len[0] | c_len[1] | ... c_len[n-1]| + +-------+-----------+-----------+-- --+-----------+ + +c_len[i] == 0 ¤Î¾ì¹ç + + 0 ¤¬Â³¤¯¿ô¤ò count ¤È¤¹¤ë¤È¡¢ + + count == 1 ¤Î¾ì¹ç + + t_len[0] + <----------> + +------------+ + | t_code[0] | + +------------+ + + count == 2 ¤Î¾ì¹ç + + t_len[0] t_len[0] + <----------> <----------> + +------------+------------+ + | t_code[0] | t_code[0] | + +------------+------------+ + + count == 3..18 ¤Î¾ì¹ç + + t_len[1] 4 bit + <----------> <------> + +------------+-------+ + | t_code[1] |count-3| + +------------+-------+ + + count == 19 ¤Î¾ì¹ç + + t_len[0] t_len[1] 4 bit + <----------> <----------> <------> + +------------+------------+-------+ + | t_code[0] | t_code[1] |count-3| + +------------+------------+-------+ + + count >= 20 ¤Î¾ì¹ç + + t_len[2] CBIT{9} + <----------> <------> + +------------+--------+ + | t_code[2] |count-20| + +------------+--------+ + +c_len[i] > 0 ¤Î¾ì¹ç + + t_len[c_len[i]+2] + <-----------------> + +-------------------+ + | t_code[c_len[i]+2]| + +-------------------+ + +c_len[n...NC] ¤Ï¡¢0 ¤È¤Ê¤ë¡£ + +---------------------------------------------------------------------------- + +(8) +c_len ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È¤ÎÀèƬ CBIT{9} ¤Ï 0 ... 2^9(512) ¤ÎÈϰϤÎÃͤò +³ÊǼ¤Ç¤­¤ë¤¬ c_len ¤ÎÎΰ襵¥¤¥º¤Ï NC{510} ¤Ê¤Î¤Ç 0..510 ¤ÎÈϰϤòĶ¤¨¤ë +¾ì¹ç¤Ï ÉÔÀµ¤ÈȽÃǤ·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£ + +(9) +¤Þ¤¿¡¢ + count >= 20 ¤Î¾ì¹ç + count == 3..18 ¤Î¾ì¹ç + +¤Î¤½¤ì¤¾¤ì¤Î·Á¼°¤Ë¤ª¤¤¤Æ count ¤Î¿ô¤À¤± c_len[i] ¤Ï 0 ¤¬Â³¤¯¤¬¤³¤ì¤¬ +c_len ¤Î*»Ä¤ê*¥µ¥¤¥º¤ò±Û¤¨¤ë¾ì¹ç¤âÉÔÀµ¤Ç¤¢¤ë¡£ + +(10) +¤µ¤é¤Ë¡¢c_len[i] > 0 ¤Î¾ì¹ç¤Î·Á¼°¤Ë¤ª¤¤¤Æ¡¢t_len[x] ¤òÉü¹æ¤·¤¿·ë²Ì¤¬ +c_len[i]{x}+2 ¤ÎÃͤǤ¢¤êc_len[i] ¤ÎÃͤϥϥեޥóÉä¹æĹ¤Ê¤Î¤Ç 0 .. 16 ¤Î +ÈϰϤǤʤ±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£¤³¤ì¤Ï¡¢c_len, p_len ¤ÈƱ¤¸¤¯ t_len ¤Î¥Ï¥Õ¥Þ¥ó +Ìڤι½ÃÛ¤ÎÃʳ¬¤ÇÉÔÀµ¤ÊÉü¹æ¸ì¤òÊÖ¤µ¤Ê¤¤¤è¤¦¤Ë¤·¤Æ¤¤¤ì¤Ð¤è¤¤¡£ + +(11) +¤â¤Á¤í¤ó¡¢t_len ¤Î¤È¤­¤ÈƱÍÍ c_len ¤òÆɤ߹þ¤ó¤À¸å¤Ë¹½ÃÛ¤·¤¿ Huffman ÌÚ +¤Ï Huffman ÌڤȤ·¤ÆÀ°¹çÀ­¤¬Êݤ¿¤ì¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£ + +³¤¤¤Æ p_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È¤Ë¤Ä¤¤¤Æ¹Í¤¨¤ë¡£ + +---------------------------------------------------------------------------- +< p_len[] ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È > + + 0 pbit{4 or 5} + +-------+-----------+-----------+-- --+-----------+ + | n | p_len[0] | p_len[1] | ... p_len[n-1]| + +-------+-----------+-----------+-- --+-----------+ + +p_len[i] <= 6 ¤Î¾ì¹ç + + 0 3bit + +-----+ + p_len[i] | | | | + +-----+ + +p_len[i] >= 7 ¤Î¾ì¹ç + + 0 p_len[i] - 3 + +----------------+ + p_len[i] |1 1 1 1 ... 1 0 | + +----------------+ + +p_len[n...np] ¤Ï¡¢0 ¤È¤Ê¤ë¡£ + +---------------------------------------------------------------------------- + +(12) +p_len ¤Î½ÐÎÏ¥Õ¥©¡¼¥Þ¥Ã¥È¤ÎÀèƬ pbit{4 or 5} ¤Ï 0 ... 2^4{16} or +2^5{32} ¤ÎÈϰϤÎÃͤò³ÊǼ¤Ç¤­¤ë¤¬ p_len ¤ÎÎΰ襵¥¤¥º¤Ï np{14..17} ¤Ê¤Î¤Ç +0..np ¤ÎÈϰϤòĶ¤¨¤ë¾ì¹ç¤ÏÉÔÀµ¤ÈȽÃǤ·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£ + +¤È¤³¤í¤ÇÉü½¬¤Ë¤Ê¤ë¤¬ np ¤Ï¡¢³Æ°µ½Ì¥á¥½¥Ã¥É¤Î¼­½ñ¤Î¥µ¥¤¥º¤Ç·è¤Þ¤ë¡£Âбþ +¤ò°Ê²¼¤ËºÆ·Ç¤¹¤ë¤Î¤Ç³Îǧ¤·¤Æ¤Û¤·¤¤¡£(-lh4- ¤Î¾ì¹ç¤Î np ¤Ï¤Ê¤¼¤« 13 ¤Ç¤Ï +¤Ê¤¯14 ¤È¤Ê¤Ã¤Æ¤¤¤ë¡£¤ª¤½¤é¤¯¡¢LHA ¤¬¼ÂÁõ¤µ¤ì¤¿Åö»þ -lh6-, -lh7- ¤Ï¸ºß +¤»¤º np ¤ä pbit ¤Ï¸ÇÄêÃÍ(Äê¿ô NP, PBIT)¤Ç¤¢¤Ã¤¿¤¿¤á¡¢-lh4-, -lh5- ¤Îξ +Êý¤ËÂбþ¤Ç¤­¤ë¤è¤¦ÊÑ¿ô¤ÎÎΰ襵¥¤¥º¤ò¹ç¤ï¤»¤¿¤À¤±¤Ç¤¢¤ë¤È»×¤¦¡£¤Ä¤Þ¤ê¡¢ +°µ½Ì½èÍý¤Ë¤ª¤¤¤Æ¤Ï¡¢-lh4- ¤Î np ¤ò 13 ¤ÈÁÛÄꤷ¤Æ¤âÌäÂê¤ÏȯÀ¸¤·¤Ê¤¤¤È»× +¤ï¤ì¤ë¡£µÕ¤ËÉü¹æ½èÍý¤Ë¤ª¤¤¤Æ¤Ï¡¢(gzip ¤Î¤è¤¦¤Ë)°µ½Ì method ¤Î¾ðÊó¤¬ÅϤµ +¤ì¤Ê¤¤¾ì¹ç¤Ï np ¤ò 14 ¤È¤¹¤ë¤·¤«¤Ê¤¤¡£¤Ê¤ª¡¢¤³¤Î¤è¤¦¤Ê(gzip ¤Î¤è¤¦¤Ê) +¾ì¹ç -lh6,7- ¤Ø¤ÎÂбþ¤Ï¤Ç¤­¤Ê¤¤¡£ºÇ½é¤Î pbit ʬ¤ÎÍ×ÁÇ¿ô¤ÎÆɤ߹þ¤ß¤Ç 4 +¥Ó¥Ã¥ÈÆɤá¤Ð¤è¤¤¤Î¤« 5 ¥Ó¥Ã¥ÈÆɤá¤Ð¤è¤¤¤Î¤«¤¬¤ï¤«¤é¤Ê¤¤¤«¤é¤Ç¤¢¤ë) + + method maxmatch dicsiz dicbit np(dicbit+1) pbit + ----------------------------------------------------------- + -lh4- 256 2^12 12 14 (or 13?) 4 (14<2^4) + -lh5- 256 2^13 13 14 4 (14<2^4) + -lh6- 256 2^15 15 16 5 (16<2^5) + -lh7- 256 2^16 16 17 5 (17<2^5) + +(13) +¤Þ¤¿¡¢t_len ¤ÈƱÍͤˡ¢p_len[i] >= 7 ¤Î·Á¼°¤Ç¤Ï¡¢1 ¤¬ 12 bit ¤è¤ê¿¤¯Ï¢ +³¤·¤¿¾ì¹ç¤ËÉÔÀµ¤Ç¤¢¤ë¡£ + +(14) +¤â¤Á¤í¤ó¡¢p_len[] ¤òÆɤ߹þ¤ó¤À¸å¤Ë¹½ÃÛ¤·¤¿ Huffman ÌÚ¤ÎÀ°¹çÀ­¤¬Êݤ¿¤ì¤Ê +¤±¤ì¤Ð¤Ê¤é¤Ê¤¤ÅÀ¤Ï¾¤Î Huffman ÌÚ¤ÈƱ¤¸¤À¡£ + +¤Ç¤Ï¡¢¼ÂºÝ¤ËÉü¹æ½èÍý¤Î¥»¥­¥å¥ê¥Æ¥£Âбþ¤ò¹Ô¤Ã¤¿¥½¡¼¥¹¤ò´ð¤Ë¼ÂÁõ¤ò³Îǧ¤·¤è¤¦¡£ + + +°Ê²¼¤Ï¡¢ + + https://bugzilla.redhat.com/show_bug.cgi?id=204676 + +¤Ë¤Æ·ÇºÜ¤µ¤ì¤¿¥Ñ¥Ã¥Á¤¢¤ë¡£¤³¤Î¥Ñ¥Ã¥Á¤Ï gzip ÍѤΥѥåÁ¤Ç¤¢¤Ã¤¿¤¬ÆâÍÆ¤Ï +¤Û¤È¤ó¤ÉƱ¤¸¤Ç¤¢¤ë¡£(gzip ¤Ï LHA ¤È¤Û¤È¤ó¤ÉƱ¤¸Éü¹æ½èÍý¤Î¥½¡¼¥¹¤ò´Þ¤ó¤Ç +¤ª¤ê¡¢LHA ¤Î°µ½Ì·Á¼°¤òÉü¹æ¤¹¤ë¤³¤È¤¬¤Ç¤­¤ë¡£¤¿¤À¡¢LHA ¥Ø¥Ã¥À¤òÆɤळ¤È +¤Ï¤Ç¤­¤Ê¤¤¤¿¤á lzh ¥Õ¥¡¥¤¥ë¤òŸ³«¤Ç¤­¤ë¤ï¤±¤Ç¤Ï¤Ê¤¤¡£¸«¤¿¤È¤³¤í +-lh4,lh5- ¤Ë¤Î¤ßÂбþ¤·¤Æ¤¤¤ë¡£) + +diff -ru gzip-1.3.5.orig/unlzh.c gzip-1.3.5/unlzh.c +--- gzip-1.3.5.orig/unlzh.c 1999-10-06 06:00:00.000000000 +0100 ++++ gzip-1.3.5/unlzh.c 2006-08-18 22:56:19.446997000 +0100 +@@ -149,13 +149,17 @@ + unsigned i, k, len, ch, jutbits, avail, nextcode, mask; + + for (i = 1; i <= 16; i++) count[i] = 0; +- for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++; ++ for (i = 0; i < (unsigned)nchar; i++) { ++ if (bitlen[i] > 16) ++ error("Bad table (case a)\n"); ++ else count[bitlen[i]]++; ++ } + +bitlen ¤Ï¡¢c_len, p_len, t_len ¤Ç¤¢¤ê¡¢¤¤¤º¤ì¤Î Huffman ÌÚ¤âºÇÂç¤Î³¬ÁØ +¤Ï 16 ¤Þ¤Ç¤Ç¤¢¤ë¤«¤é¤½¤ÎÈϰϤòĶ¤¨¤¿¤â¤Î¤¬¤Ê¤¤¤«¥Á¥§¥Ã¥¯¤·¤Æ¤¤¤ë¡£¤³¤ì +¤Ï¡¢¥»¥­¥å¥ê¥Æ¥£¥Ð¥°¤Î½ÅÍפʲþ½¤ÅÀ¤Î£±ÅÀÌܤǤ¢¤ë¡£ + + start[1] = 0; + for (i = 1; i <= 16; i++) + start[i + 1] = start[i] + (count[i] << (16 - i)); +- if ((start[17] & 0xffff) != 0) +- error("Bad table\n"); ++ if ((start[17] & 0xffff) != 0 || tablebits > 16) /* 16 for weight below */ ++ error("Bad table (case b)\n"); + + jutbits = 16 - tablebits; + for (i = 1; i <= (unsigned)tablebits; i++) { + +tablebits ¤Ï¡¢make_table() ¤ò¸Æ¤Ó½Ð¤¹¤È¤­¤Ë»ØÄꤹ¤ë°ú¿ô¤Ç°Ê²¼¤ÎÄ̤ê¸ÇÄê +ÃÍ(8 or 12)¤Ç¤¢¤ë¡£½¾¤Ã¤Æɬ¤º¤·¤âɬÍפǤϤʤ¤¡£(¤¢¤¨¤Æ¥Á¥§¥Ã¥¯¤¹¤ë¤Ê¤é +Bad table ¤Ç¤Ê¤¯ Bug ¤Èɽ¼¨¤¹¤ë¤Ù¤­¤À¤í¤¦) + + make_table(nn, pt_len, 8, pt_table); + make_table(NC, c_len, 12, c_table); + +total & 0xffff ¤Ï¤É¤ÎÄøÅÙ¤ÎÉÔÀµ¥Æ¡¼¥Ö¥ë¤ò¸¡½Ð¤¹¤ë¤Î¤À¤í¤¦¤«¡© +³ºÅö¤Î½èÍý¤ò°Ê²¼¤Ë¼¨¤½¤¦¡£ + + for (i = 1; i <= 16; i++) count[i] = 0; + for (i = 0; i < (unsigned)nchar; i++) count[bitlen[i]]++; + + start[1] = 0; + for (i = 1; i <= 16; i++) + start[i + 1] = start[i] + (count[i] << (16 - i)); + if ((start[17] & 0xffff) != 0) + error("Bad table\n"); + +¤³¤ì¤Ï¡¢LHa for UNIX ¤Ç°Ê²¼¤Î¤è¤¦¤Ë½ñ¤«¤ì¤Æ¤¤¤¿Éôʬ¤Ç¤¢¤ê¡¢¥í¥¸¥Ã¥¯¤È¤· +¤Æ¤Ï¤Þ¤Ã¤¿¤¯°ì½ï¤Ç¤¢¤ë¡£ + + /* (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"); + +Î㤨¤Ð¡¢°Ê²¼¤Î Huffman ÌڤǤϳƳ¬ÁØ¤Î½Å¤ß weight ¤ÎÃÍ(gzip ¤Î¥½¡¼¥¹¤Ç¡¢ +(16 - i)¤ÎÃÍ)¤Ï + + /\ + a /\ weight[1] = 0x8000 + b c weight[2] = 0x4000 + +¤Ç¤¢¤ê¡¢Íդοô¤Ë½Å¤ß¤ò¤«¤±¤¿ÃͤÎÁíÏÂ¤Ï + +0x10000 + +¤È¤Ê¤ë¡£¤³¤ì¤ÏÀµ¤·¤¤ Huffman ÌڤˤĤ¤¤Æɬ¤ºÀ®¤êΩ¤¿¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤É¬Í× +½½Ê¬¾ò·ï¤Ç¤¢¤ë¡£ + +¤·¤«¤·¡¢´û¸¤Î½èÍý¤Ç¤ÏÎ㤨¤Ð 1 ³¬ÁØÌܤÎÍդοô¤¬ 4 ¤Ç¤¢¤ë¾ì¹ç¤Ë total ¤¬ +0x20000 ¤È¤Ê¤ê 0xffff ¤È¤ÎÏÀÍýÀѤǤϰ۾ï¤ò¸¡ÃΤǤ­¤Ê¤¤¡£ + +¤³¤³¤Ï¡¢°Ê²¼¤Î¤è¤¦¤Ë¤¹¤ë¤Ù¤­¤Ç¤¢¤í¤¦(°Ê²¼¤Ï¡¢LHa for UNIX¤Î¥½¡¼¥¹)¡£ + + /* (C) */ + /* calculate first code */ + total = 0; + for (i = 1; i <= 16; i++) { + start[i] = total; + total += weight[i] * count[i]; + if (total > 0x10000) + error("make_table()", "Bad table\n"); + } + if (total != 0x10000) + error("make_table()", "Bad table (5)\n"); + +¥ë¡¼¥×¤ÎÃæ¤Ë total ¤Î¥Á¥§¥Ã¥¯¤òÆþ¤ì¤Æ¤¤¤ë¤Î¤ÏÇ°¤Î¤¿¤á¤Ç¤¢¤ë¡£¤â¤Á¤í¤ó¡¢ +total ¤ÎÊÑ¿ô¤Î¥µ¥¤¥º¤Ï 16 bit ¤Ç¤Ï­¤ê¤Ê¤¤¤Î¤Ç 32 bit À°¿ô¤Ë¤¹¤ëɬÍפ¬ +¤¢¤ë¡£(gzip ¤Î¥½¡¼¥¹¤Ç¤Ï¡¢total ÊÑ¿ô¤ÎÂå¤ï¤ê¤Ë start[17] ¤¬»È¤ï¤ì¤Æ¤¤¤ë +¤Î¤Ç¡¢LHa for UNIX ¤Î¤è¤¦¤Ë total ÊÑ¿ô¤Ë¤¹¤ë¤«¡¢start[] ¼«ÂΤò 32 bit +À°¿ô¤ËÊѤ¨¤ëɬÍפ¬¤¢¤ë¡£) + +¤Ê¤ª¡¢32 bit À°¿ô¤Ë¤·¤¿¾ì¹ç¤Ç¤â¡¢count[1] ¤¬ 0x20000 ¤ÎÃͰʾå¤Ç¤¢¤ë¤È¤­ +total ¤¬¥ª¡¼¥Ð¡¼¥Õ¥í¡¼¤¹¤ë¶²¤ì¤¬¤¢¤ë¤¬°Ê²¼¤Î½èÍý¤è¤ê count[] ¤¬nchar ¤è +¤êÂ礭¤¯¤Ê¤ë¤³¤È¤Ï¤Ê¤¤¡£ + + /* (B) */ + /* count */ + for (i = 0; i < nchar; i++) + count[bitlen[i]]++; + +¤½¤·¤Æ¡¢Í×ÁÇ¿ô¤¬ºÇ¤âÂ礭¤¤ c_len ¤Î¾ì¹ç¤Ç nchar ¤Ï NC{510} ¤Ç¤¢¤ë¤«¤é +32 bit À°¿ô¤ÎÈϰϤò¥ª¡¼¥Ð¡¼¤¹¤ë¤³¤È¤Ï¤Ê¤¤¤À¤í¤¦¡£¤³¤Î¤³¤È¤¬¤Ï¤Ã¤­¤ê¤·¤Æ +¤¤¤ì¤Ð¥ë¡¼¥×Ãæ¤ËÆþ¤ì¤¿ + + if (total > 0x10000) + error("make_table()", "Bad table (5)\n"); + +¤Ïɬ¤º¤·¤âɬÍפǤϤʤ¤¡£¤¢¤ë¤¤¤Ï¡¢³¬ÁØ n ¤ÎÍդοô¤¬ 2^n ¤ò±Û¤¨¤Ê¤¤¤³¤È¤Î +¥Á¥§¥Ã¥¯¤ËÊѤ¨¤Æ¤âÎɤ¤¤À¤í¤¦¡£ + + /* (C) */ + /* calculate first code */ + total = 0; + for (i = 1; i <= 16; i++) { + if (count[i] > (1<> jutbits; + if (i != 0) { +- k = 1 << tablebits; +- while (i != k) table[i++] = 0; ++ k = MIN(1 << tablebits, DIST_BUFSIZE); ++ while (i < k) table[i++] = 0; + } + +tablebits ¤Ï¸ÇÄêÃͤʤΤǡ¢É¬¤º¤·¤â¤³¤Î¥Á¥§¥Ã¥¯¤ÏɬÍפǤϤʤ¤¡£ + + avail = nchar; + mask = (unsigned) 1 << (15 - tablebits); + for (ch = 0; ch < (unsigned)nchar; ch++) { + if ((len = bitlen[ch]) == 0) continue; +- nextcode = start[len] + weight[len]; ++ nextcode = MIN(start[len] + weight[len], DIST_BUFSIZE); + if (len <= (unsigned)tablebits) { + for (i = start[len]; i < nextcode; i++) table[i] = ch; + } else { + +DIST_BUFSIZE ¤Ï¡¢c_table[] ¤Î¥Ð¥Ã¥Õ¥¡¥µ¥¤¥º¤Ç 1<<12 ¤Ç¤¢¤ë¡£nextcode ¤Ï¡¢ +LHa for UNIX ¤Ç¤Î³ºÅöÊÑ¿ô¤Ï l ¤Ç¡¢Huffman Éä¹æ¤Î(ÀèƬ tablebits ¥Ó¥Ã¥È +¤Î)¼è¤êÆÀ¤ëºÇÂçÃͤǤ¢¤ë¡£¤³¤ì¤Ï¡¢ÍýÏÀ¾å + + tablebits ºÇÂç¤Î Huffman Éä¹æ m + c_len 12 1111 1111 1111{4095} 4 + p_len 8 1111 1111{255} 8 + t_len 8 1111 1111{255} 8 + +¤Ç¤¢¤ê¡¢¥ë¡¼¥×æ½Ð¾ò·ï¤¬ÉÔÀµ¤Ç¤Ê¤¤¸Â¤ê¡¢¤³¤Î¥Á¥§¥Ã¥¯¤ÏÉÔÍפǤ¢¤ë¤È»×¤ï +¤ì¤ë¡£(¤½¤â¤½¤â¡¢Ç°¤Î¤¿¤á¤È¤¤¤¦°ÕÌ£¤Ç¥Á¥§¥Ã¥¯¤·¤Æ¤¤¤ë¤Î¤Ê¤é c_len ¤Î¾ì +¹ç¤À¤±¤·¤«¹Íθ¤·¤Æ¤Ê¤¤¤Î¤âÊѤǤ¢¤ë) + +¤¿¤À¤·¡¢Àè¤Û¤É¤Î total ¥Á¥§¥Ã¥¯¤¬ÉÔ´°Á´¤Ê¤Þ¤Þ¤À¤È start[] ¤ÎÃͤ¬ +ÉÔÀµ¤Ë¤Ê¤ê¤¦¤ë¤¿¤á¡¢Ïä¬ÊѤï¤Ã¤Æ¤¯¤ë¡£ +¤½¤¦¤¤¤¦¤ï¤±¤Ç¡¢¤³¤ì¤Ï¥»¥­¥å¥ê¥Æ¥£¥Ð¥°¤Î½ÅÍפʲþ½¤ÅÀ¤Î£²ÅÀÌܤȤʤ뤬¡¢ +ËÜÅö¤Ï total ¤Î¥Á¥§¥Ã¥¯¤ÎÊý¤¬½ÅÍפǤ¢¤ë¡£ + +¤µ¤é¤Ë¡¢ÌڤηÁ¤¬Àµ¤·¤¯¤Æ¤â + + Éü¹æ¸ì¤Î¼ïÎà¿ô < Íդοô + +¤Ç¤¢¤ë¾ì¹ç¡¢ÍÕ¤ËÃͤ¬³ä¤êÅö¤Æ¤é¤ì¤Ê¤¤»Þ¤¬È¯À¸¤·¤Æ¤·¤Þ¤¦¡£¤³¤ì¤â¥Á¥§¥Ã¥¯ +¤·¤Æ¤ª¤¤¤¿Êý¤¬Îɤ¤¤À¤í¤¦¡£Éü¹æ¸ì¤Î¿ô¤Ï nchar ¤ÇÍդοô¤Ï count[] ¤ÎÁíÏ +¤Ç¤¢¤ë¤«¤é + + /* (B) */ + /* count */ + for (i = 0; i < nchar; i++) + count[bitlen[i]]++; + +¤è¤ê¡¢¤³¤Î¤³¤È¤ÏÊݾڤµ¤ì¤Æ¤¤¤ë¤è¤¦¤À(i >= nchar ¤Ç¤¢¤ë bitlen[i] ¤¬ÀßÄê +¤µ¤ì¤Æ¤¤¤Æ¤â»È¤ï¤ì¤Ê¤¤¡£¤â¤Á¤í¤óÀßÄꤵ¤ì¤¿»þÅÀ¤Ç¡¢¥¨¥é¡¼¤ò¸¡½Ð¤¹¤ëÊý¤¬ +˾¤Þ¤·¤¤¤È¤Ï»×¤¦) + +@@ -218,7 +222,7 @@ + for (i = 0; i < 256; i++) pt_table[i] = c; + } else { + i = 0; +- while (i < n) { ++ while (i < MIN(n,NPT)) { + c = bitbuf >> (BITBUFSIZ - 3); + if (c == 7) { + mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3); + +n ¤¬ t_len¡¢p_len ¤ÎÎΰè¤ÎÈÏ°ÏÆâ¤ÎÃͤȤϸ¤é¤Ê¤¤¤Î¤Ç¤½¤Î¥Á¥§¥Ã¥¯¤ò¹Ô¤Ã +¤Æ¤¤¤ë¡£¤³¤ì¤Ï¡¢¥»¥­¥å¥ê¥Æ¥£¥Ð¥°¤Î½ÅÍפʲþ½¤ÅÀ¤Î£³ÅÀÌܤǤ¢¤ë¡£ + +µ¤¤Ë¤Ê¤ë¤Î¤Ï¡¢ + +¡¦p_len, t_len ¤ÎÏÀÍýŪ¤ÊÎΰ襵¥¤¥º¤Ç¤Ê¤¯¼ÂÁõ¾å¤Î pt_len ¤ÎÎΰ襵¥¤¥º¤Ç + ¥Á¥§¥Ã¥¯¤·¤Æ¤¤¤ë¡£¤½¤Î¤¿¤á¡¢¥Ð¥Ã¥Õ¥¡¥ª¡¼¥Ð¡¼¥Õ¥í¡¼¤Î¥»¥­¥å¥ê¥Æ¥£Âкö + ¤È¤·¤Æ¤Ï½½Ê¬¤À¤¬¥¨¥é¡¼¥Á¥§¥Ã¥¯¤È¤·¤Æ¤ÏÉÔ´°Á´¤Ç¤¢¤ë(¥¨¥é¡¼¤Î¸¡½Ð¤¬ÃÙ±ä + ¤µ¤ì¤ë)¡£ + +¡¦ÉÔÀµ¤ÊÃͤò¥¨¥é¡¼¤È¤»¤º¡£½èÍý¤òºÇÂçÃͤǷѳ¤·¤Æ¤¤¤ë¡£¤½¤Î¤¿¤á¡¢°Ê²¼Æ±Ê¸¡£ + +@@ -228,7 +232,7 @@ + pt_len[i++] = c; + if (i == i_special) { + c = getbits(2); +- while (--c >= 0) pt_len[i++] = 0; ++ while (--c >= 0 && i < NPT) pt_len[i++] = 0; + } + } + while (i < nn) pt_len[i++] = 0; + +i_special ¤Ï 3 ¸ÇÄê¤Ê¤Î¤Ç¡¢¤³¤Î¥Á¥§¥Ã¥¯¤Ïɬ¤º¤·¤âɬÍפȤ¤¤¦¤ï¤±¤Ç¤Ï¤Ê¤¤¡£ +(¸·Ì©¤Ë¤Ï¡¢¼ÂÁõ¾å i_special ¤¬ -1 ¤Ç¤¢¤ë¾ì¹ç¤¬¤¢¤ë¤¬ i ¤¬ -1 ¤Ë¤Ê¤Ã¤¿»þ +ÅÀ¤Ç¥Ð¥°¤Ç¤¢¤ê¡¢¤½¤Î¿´ÇۤϤʤµ¤½¤¦¤À) + +@@ -248,7 +252,7 @@ + for (i = 0; i < 4096; i++) c_table[i] = c; + } else { + i = 0; +- while (i < n) { ++ while (i < MIN(n,NC)) { + c = pt_table[bitbuf >> (BITBUFSIZ - 8)]; + if (c >= NT) { + mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8); + +n ¤¬ c_len ¤ÎÎΰè¤ÎÈÏ°ÏÆâ¤ÎÃͤȤϸ¤é¤Ê¤¤¤Î¤Ç¡¢Æ±¾å¡£ + +@@ -256,14 +260,14 @@ + if (bitbuf & mask) c = right[c]; + else c = left [c]; + mask >>= 1; +- } while (c >= NT); ++ } while (c >= NT && (mask || c != left[c])); + } + +¤³¤Î¥ë¡¼¥×Éôʬ¤ÎÁ´ÂΤϥѥåÁÁ°¤À¤È¡¢ + + c = pt_table[bitbuf >> (BITBUFSIZ - 8)]; + if (c >= NT) { + mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8); + do { + if (bitbuf & mask) c = right[c]; + else c = left [c]; + mask >>= 1; + } while (c >= NT); + } + fillbuf((int) pt_len[c]); + +¤È¤Ê¤Ã¤Æ¤ª¤ê¡¢ + + mask == 0 && c == left[c] + +¤Î¾ò·ï¤òËþ¤¿¤·¤Æ¤·¤Þ¤¦¤è¤¦¤ÊÉÔÀµ¤ÊÌÚ¤¬¹½ÃÛ¤µ¤ì¤Æ¤¤¤ë¤È c ¤ÎÃͤÏÊѲ½¤»¤º +¤¤¤Ä¤Þ¤Ç¤â¥ë¡¼¥×¤·Â³¤±¤ë¤³¤È¤Ë¤Ê¤Ã¤Æ¤·¤Þ¤¦¡£¤½¤³¤Ç¡¢¤³¤Î¾ò·ï¤¬È¯À¸¤·¤¿ +¤È¤­¤Ë¤¹¤°¤Ë¥ë¡¼¥×¤òæ½Ð¤¹¤ë¤è¤¦¤½¤Î¾ò·ï¤ÎÈÝÄê¤Ç¤¢¤ë + + !(mask == 0 && c == left[c]) + +¤Ä¤Þ¤ê¤Ï¡¢ + + (mask || c != left[c]) + +¤ò¥ë¡¼¥×·Ñ³¤Î while ¾ò·ï¤Ë²Ã¤¨¤Æ¤¤¤ë¤è¤¦¤À¡£¤·¤«¤·¡¢mask ¤Î½é´üÃÍ¤Ï + + 1 << (BITBUFSIZ{16} - 1 - 8) {0000 0000 1000 0000} + +¤Ç¤¢¤ê¥ë¡¼¥×Ëè¤Ë + + mask >>= 1; + +¤·¤Æ¤¤¤ë¤Î¤À¤«¤é¡¢mask == 0 ¤Ë¤Ê¤Ã¤¿»þÅÀ¤Ç¡¢8 bit(ºÇ½é¤Îɽ°ú¤­¤È¹ç¤ï¤» +¤Æ 16 bit)¤Î Huffman Éä¹æ¤òÆɤ߹þ¤ó¤Ç¤ª¤ê(¤¯¤É¤¤¤«¤âÃΤì¤Ê¤¤¤¬ LHA ¤Ë¤ª +¤±¤ë Huffman Ìڤγ¬ÁؤϺÇÂç 16)¡¢mask == 0 ¤òæ½Ð¾ò·ï¤Ë²Ã¤¨¤ë¤À¤±¤ÇÎɤ¤ +¤È»×¤¦¡£ + +¤â¤Á¤í¤ó¡¢17 bit ¤ÎÉä¹æ¤òÆɤ߹þ¤ó¤À»þÅÀ¤ÇÉÔÀµ¤Ê¤Î¤À¤«¤é + + mask = (unsigned) 1 << (BITBUFSIZ - 1 - 8); + do { + if (mask == 0) error("...."); + + if (bitbuf & mask) c = right[c]; + else c = left [c]; + mask >>= 1; + } while (c >= NT); + +¤È°Û¾ï½ªÎ»¤·¤Æ¤âÌäÂê¤Ê¤¤¤È»×¤¦¡£°Ê²¼¤Î¤è¤¦¤Ë for ¤Ç½ñ¤¯¤³¤È¤â¤Ç¤­¤ë¤¬¤Þ +¤¢·ë¶É¤ÏƱ¤¸¤³¤È¤À¡£(¤³¤¦¤¹¤ë¤È¸«¤ä¤¹¤¤¤À¤í¤¦¤«¡©¤È¹Í¤¨¤Æ¤ß¤¿¤À¤±¤Ç¤¢¤ë +¤¬¡¢Æä˸ú²Ì¤Ï¤Ê¤¤¤è¤¦¤À¡£) + + for (mask = 1 <<(BITBUFSIZ-1-8); mask != 0; mask >>= 1) { + if (bitbuf & mask) c = right[c]; + else c = left[c]; + + if (c < NT) break; + } + if (mask == 0) error(...); + +¤·¤«¤· c ¤ÎÃÍ¤È left[], right[] ¤ÎÎΰ襵¥¤¥º¤È¤ÎÈæ³Ó¤ÏÎɤ¤¤Î¤À¤í¤¦¤«¡© +¡ÊÍýÏÀ¾å¤Ï Huffman Ìڤι½ÃÛ»þ¤Ë¥Á¥§¥Ã¥¯¤µ¤ì¤Æ¤¤¤ì¤ÐÌäÂê¤Ê¤¤¤Î¤Ç¡¢»ä¤ÏÌä +Âê¤Ê¤¤¤È»×¤¦¤Î¤À¤¬¡¢¤½¤ì¤ò¸À¤¦¤È¤½¤â¤½¤â̵¸Â¥ë¡¼¥×¤Î¥Á¥§¥Ã¥¯¤âÉÔÍפǤ¢ +¤ë¤È»×¤¦¡£) + + fillbuf((int) 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; ++ while (--c >= 0 && i < NC) c_len[i++] = 0; + } else c_len[i++] = c - 2; + } + while (i < NC) c_len[i++] = 0; + +c_len[] ¤ÎÈϰϳ°¤ÎÎΰè¤ËÃͤ¬ÀßÄꤵ¤ì¤Ê¤¤¤è¤¦¥Á¥§¥Ã¥¯¤·¤Æ¤¤¤ë¡£¤·¤«¤·¡¢ +¤ä¤Ï¤ê¥¨¥é¡¼¤È¤·¤Æ¸¡½Ð¤»¤º¤Ë½èÍý¤ò³¹Ô¤·¤Æ¤¤¤ë¡£ + +@@ -292,7 +296,7 @@ + if (bitbuf & mask) j = right[j]; + else j = left [j]; + mask >>= 1; +- } while (j >= NC); ++ } while (j >= NC && (mask || j != left[j])); + } + fillbuf((int) c_len[j]); + return j; + +Ʊ¾å¡£ + +@@ -309,7 +313,7 @@ + if (bitbuf & mask) j = right[j]; + else j = left [j]; + mask >>= 1; +- } while (j >= NP); ++ } while (j >= NP && (mask || j != left[j])); + } + fillbuf((int) pt_len[j]); + if (j != 0) j = ((unsigned) 1 << (j - 1)) + getbits((int) (j - 1)); + +Ʊ¾å¡£ + +@@ -356,7 +360,7 @@ + while (--j >= 0) { + buffer[r] = buffer[i]; + i = (i + 1) & (DICSIZ - 1); +- if (++r == count) return r; ++ if (++r >= count) return r; + } + for ( ; ; ) { + c = decode_c(); +@@ -366,14 +370,14 @@ + } + if (c <= UCHAR_MAX) { + buffer[r] = c; +- if (++r == count) return r; ++ if (++r >= count) return r; + } else { + j = c - (UCHAR_MAX + 1 - THRESHOLD); + i = (r - decode_p() - 1) & (DICSIZ - 1); + while (--j >= 0) { + buffer[r] = buffer[i]; + i = (i + 1) & (DICSIZ - 1); +- if (++r == count) return r; ++ if (++r >= count) return r; + } + } + } + + +¤µ¤Æ¡¢¤³¤ì¤é¥»¥­¥å¥ê¥Æ¥£Âкö¤Ï¶ñÂÎŪ¤Ë¤É¤Î¤è¤¦¤Ê¾ì¹ç¤òÁÛÄꤷ¤Æ¤¤¤ë¤Î¤À +¤í¤¦¡© + +https://bugzilla.redhat.com/show_bug.cgi?id=204676 + +¤Ë¤Ï¡¢Ìڤι½ÃÛ¤¬ÉÔÀµ¤Ë¤Ê¤ë¥·¥Ê¥ê¥ª¤È¤·¤Æ°Ê²¼¤¬½ñ¤«¤ì¤Æ¤¤¤ë¡£ + +> * Construct a pt_len[] such that pt_len[n] is 0. +> * Construct a pt_table[] such that pt_table[(code buffer) >> 16 - 8] +is n (where n>2) +> * Now c_len[] is filled with (n-2), generating exceptionally high values in +> count[n-2]. + +¤·¤«¤·¡¢¤³¤ì¤òÆɤó¤Ç¤â¤è¤¯¤ï¤«¤é¤Ê¤«¤Ã¤¿¤Î¤Ç°ì½ï¤Ë·ÇºÜ¤µ¤ì¤Æ¤¤¤¿¥µ¥ó¥× +¥ë¤ÎÉÔÀµ¤ÊÉä¹æ¤òÆɤó¤Ç¤ß¤¿¡£ + +> perl -e 'print "\x1f\xa0","\xab\xcd","\xf6\x40\x01\xc2\xcc\x36\x0c\x92\x00\x00\x00\x00","\xc8","\x00"x"2048"' | gzip -d + +\x1f\xa0 ¤Ï¥Þ¥¸¥Ã¥¯¥Ê¥ó¥Ð¡¼¤Ç¡¢gzip ¤Ë¤ª¤±¤ë LHA ¤Î°µ½Ì·Á¼°¤ò¼¨¤¹¡£¤½¤· +¤Æ¡¢LHA ¥Õ¥©¡¼¥Þ¥Ã¥È¤Ï¡¢\xab\xcd ¤«¤é»Ï¤Þ¤ë¡£¤³¤ì¤Ï¡¢blocksize ¤Ç¤¢¤ë¡£ + + blocksize = Oxabcd + +¤½¤·¤Æ¡¢t_len ¤Î½ÐÎÏ·Á¼°¤¬Â³¤¯¡£2 ¿Ê¿ô¤È¹ç¤ï¤»¤Æ²¼µ­¤Ë¼¨¤¹¡£ + + f6 40 01 c2 cc 36 + 1111 0110 0100 0000 0000 0001 1100 0010 1100 1100 0011 0110 + <----> + size of t_len + + 0c 92 00 00 00 00 + 0000 1100 1001 0010 0000 0000 0000 0000 0000 0000 0000 0000, + + c8 00 + 1100 1000, 0000 * 2048 + +¤¤¤­¤Ê¤ê¡¢t_len ¤Î¥µ¥¤¥º¤¬ÉÔÀµ(1111 0=0x1e(30) > NT{19})¤Ç¤¢¤ë¡£¤½¤·¤Æ¡¢³Æ +t_len[] ¤òÆɤ߹þ¤à¤È°Ê²¼¤Î¤è¤¦¤Ë¤Ê¤ë + + t_len[ 0] = 110 :6 + t_len[ 1] = 010 :2 + t_len[ 2] = 0 00 :0 + 00 + t_len[ 3] = 000 :0 + t_len[ 4] = 0 00 :0 + t_len[ 5] = 01 1 :3 + t_len[ 6] = 100 :4 + t_len[ 7] = 001 :1 + t_len[ 8] = 0 11 :3 + t_len[ 9] = 00 1 :1 + t_len[10] = 100 :4 + t_len[11] = 001 :1 + t_len[12] = 1 01 :5 + t_len[13] = 10 0 :4 + t_len[14] = 000 :0 + t_len[15] = 110 :6 + t_len[16] = 0 10 :2 + t_len[17] = 01 0 :2 + t_len[18] = 010 :2 + t_len[19] = 000 :0 + t_len[20] = 0 00 :0 + t_len[21] = 00 0 :0 + t_len[22] = 000 :0 + t_len[23] = 000 :0 + t_len[24] = 0 00 :0 + t_len[25] = 00 0 :0 + t_len[26] = 000 :0 + t_len[27] = 000 :0 + t_len[28] = 0 00 :0 + t_len[29] = 00, 1 :1 + +¤³¤Î t_len ¤«¤é Huffman Ìڤγ¬ÁؤÎÍդοô¤Ï¡¢°Ê²¼¤ÎÄ̤ê¤È¤Ê¤ê + + count[1] = 3 + count[2] = 4 + count[3] = 2 + count[4] = 3 + count[5] = 1 + count[6] = 2 + +°Ê²¼¤Î¤è¤¦¤ÊÌڤηÁ¤Ë¤Ê¤ë¤Î¤Ç¡¢ÉÔÀµ¤Ç¤¢¤ë(¿ÞÃæ X ¤Ï¡¢count ¤ÎÃͤ¬ÉÔÀµ¤Ê +¤¿¤á¤Ë;·×¤Ë½ÐÍ褿ÍÕ¤ò¼¨¤¹)¡£ + + . + / / \ + X . . - 1 ³¬ÁØÌÜ + / \ / \ + . .. . - 2 ³¬ÁØÌÜ + / \ + . . + \ / \ + X. . + / \ + . . + / \ + . . - 6 ³¬ÁØÌÜ + +·ë²ÌŪ¤Ë¡¢c_len[] ¤Ï¤È¤¤¤¦¤È¤³¤Á¤é¤Ï gzip ¤Î¥½¡¼¥¹¤ò½¤Àµ¤·¤Æ¼ÂºÝ¤ËÃͤò +½ÐÎϤµ¤»¤Æ¤ß¤¿¤È¤³¤í°Ê²¼¤ÎÄ̤ꤹ¤Ù¤Æ¤ÎÃͤ¬ 5 ¤Ë¤Ê¤Ã¤¿¡£¤³¤ì¤Ï¤ä¤Ï¤êÉÔÀµ +¤Ç¤¢¤ë¡£(³¬ÁØ 5 ¤ÎÍդοô¤¬ 288 ¸Ä¤¢¤ë) + + size of c_len: 100 1000, 0 0x120(288) + + c_len[0] = 5 + c_len[1] = 5 + : + c_len[287] = 5 + + +¤È¤³¤í¤Ç¡¢ËÜÅö¤Ï¤³¤¦¤·¤¿¤«¤Ã¤¿¤Î¤Ç¤Ï¤Ê¤¤¤À¤í¤¦¤«¡© + +perl -e 'print "\x1f\xa0","\xab\xcd","\x9e\x40\x01\xc2\xcc\x36\x0c\x92","\xc8","\x00"x"2048"' | gzip -d + +¤³¤ì¤Ê¤é¤Ð¡¢t_len[] ¤ÎÎΰ襵¥¤¥º¤ÏĶ¤¨¤Ê¤¤¤Î¤Ç¡¢¤³¤Î¥Á¥§¥Ã¥¯¤Ë¤Ï¤«¤«¤é +¤Ê¤¤¡£ + + blocksize: 0xabcd + + size of t_len: 0x13(19) + + t_len[ 0]: 6 + t_len[ 1]: 2 + t_len[ 2]: 0 + t_len[ 3]: 0 + t_len[ 4]: 0 + t_len[ 5]: 3 + t_len[ 6]: 4 + t_len[ 7]: 1 + t_len[ 8]: 3 + t_len[ 9]: 1 + t_len[10]: 4 + t_len[11]: 1 + t_len[12]: 5 + t_len[13]: 4 + t_len[14]: 0 + t_len[15]: 6 + t_len[16]: 2 + t_len[17]: 2 + t_len[18]: 2 + +¤½¤·¤Æ¡¢Àè¤Û¤É¤ÈƱ¤¸ count[] ¤Î·ë²Ì¤È¤Ê¤êÉÔÀµ¤ÊÌÚ¤¬¤Ç¤­¤ë¡£ + + count[1] = 3 + count[2] = 4 + count[3] = 2 + count[4] = 3 + count[5] = 1 + count[6] = 2 + +·ë²Ì¡¢c_len[] ¤¬ÉÔÀµ¤È¤Ê¤ë¡£ + + size of c_len: 0x190 (400) + + c_len[0] = 5 + c_len[1] = 5 + : + +·ë¶É¡¢¤³¤ÎÌäÂê¤ÏÌڤηÁ¤ÎÉÔÀµ¤ò¸¡½Ð¤Ç¤­¤Æ¤Ê¤¤¤¿¤á¤ËȯÀ¸¤·¤Æ¤¤¤ë¡£Ä´¤Ù¤Æ +¤ß¤¿¤È¤³¤í¡¢¤³¤ÎÎã¤Ç¤Ï total ¤¬ 0x30000 ¤Ë¤Ê¤ë¤¿¤á¤Ë¡¢ + + (total & 0xffff) != 0 + +¤Ç¸¡½Ð¤Ç¤­¤Æ¤¤¤Ê¤¤¤è¤¦¤Ç¤¢¤ë¡£½¾¤Ã¤Æ¡¢Àè¤Ë¼¨¤·¤¿¤È¤ª¤ê total ¤ò 32 bit +ÊÑ¿ô¤Ë¤·¤Æ¡¢¤³¤Î¾ò·ï¤ò + + (total != 0x10000) + +¤È¤¹¤ë¤³¤È¤Ç²ò·è¤Ç¤­¤ë¤è¤¦¤Ë»×¤¦¡£ + +# ¤Á¤Ê¤ß¤Ë¡¢¤³¤Î¾ò·ï¤Ï¡Ö¥¯¥é¥Õ¥È¤ÎÉÔÅù¼°¡×¤òÀ°¿ô¤ËÊÑ·Á¤·¤¿¤â¤Î¤Ç¤¢¤ë¤é¤·¤¤¡£ +# ³¬ÁØ 16 °Ê²¼¤Î¥Ï¥Õ¥Þ¥óÌڤǤ¢¤ì¤Ð¡¢ +# +# total == 2^16(0x10000) +# +# ¤Ïɬ¤ºÀ®¤êΩ¤Á¡¢¤Þ¤¿¡¢ +# +# total < 2^16 +# +# ¤Ç¤¢¤ì¤Ð¡¢¤³¤ÎÌڤϾéŤÊÉä¹æ¤ò³ä¤êÅö¤Æ¤Æ¤¤¤ë¤³¤È¤ò¼¨¤¹¤½¤¦¤À¡£¤½¤·¤Æ¡¢ +# +# total > 2^16 +# +# ¤Ï¡¢°ì°Õ¤ÊÉü¹æ¤¬¤Ç¤­¤Ê¤¤¤³¤È¤ò¼¨¤¹¡£ + +Ç°¤ò²¡¤·¤Æ¤ª¤¯¤¬¡¢¥»¥­¥å¥ê¥Æ¥£¥Ñ¥Ã¥Á¤¬´Ö°ã¤Ã¤Æ¤¤¤ë¤ï¤±¤Ç¤Ï¤Ê¤¤¡£¥»¥­¥å +¥ê¥Æ¥£¥Ñ¥Ã¥Á¤È¤·¤Æ¤Ï¥Ð¥Ã¥Õ¥¡¥ª¡¼¥Ð¥Õ¥í¡¼¤òËɤ²¤ÐÎɤ¤¤Î¤Çñ¤Ë¤½¤Î¤¿¤á¤Î +¥Á¥§¥Ã¥¯¤òÆþ¤ì¤¿¤À¤±¤Ç¤¢¤ë¡£¤¿¤À¤·¡¢¥×¥í¥°¥é¥Þ¤ÎΩ¾ì¤È¤·¤Æ¤Ï¥»¥­¥å¥ê¥Æ¥£ +¥Ñ¥Ã¥Á¤ÏÂоÉÎÅË¡¤Ê½¤Àµ¤Ç¤·¤«¤Ê¤¯¡¢º¬ËÜŪ¤ÊÌäÂêÅÀ¤ò²ò·è¤·¤Æ¤¤¤Ê¤¤¾ì¹ç¤¬ +¤¢¤ë¤È¤¤¤¦¤³¤È¤ò³Ð¤¨¤Æ¤ª¤¯É¬Íפ¬¤¢¤ë¡£¤È»×¤¦¡£ + + +¤³¤Î¥»¥­¥å¥ê¥Æ¥£¥Ð¥°¤ÎÊó¹ð¤ò¼õ¤±¤Æ¡¢gzip ¤È¤·¤Æ¤É¤Î¤è¤¦¤Ë½¤Àµ¤·¤Æ¤¤¤ë¤« +¤ò³Îǧ¤·¤Æ¤ß¤¿¡£°Ê²¼¤Ï¡¢ÌäÂ꤬ȯ¸«¤µ¤ì¤¿ gzip-1.3.5 ¤È¤½¤Î½¤Àµ¤¬¹Ô¤ï¤ì +¤¿ gzip-1.3.6 ¤È¤Îº¹Ê¬(unlzh.c ¤Î¤ß)¤Ç¤¢¤ë¡£ + +--- gzip-1.3.5/unlzh.c 1999-10-06 14:00:00.000000000 +0900 ++++ gzip-1.3.6/unlzh.c 2006-11-20 17:40:34.000000000 +0900 +@@ -4,7 +4,7 @@ + */ + + #ifdef RCSID +-static char rcsid[] = "$Id: unlzh.c,v 1.2 1993/06/24 10:59:01 jloup Exp $"; ++static char rcsid[] = "$Id: unlzh.c,v 1.4 2006/11/20 08:40:34 eggert Exp $"; + #endif + + #include +@@ -69,11 +69,7 @@ local void make_table OF((int nchar, uch + #define NT (CODE_BIT + 3) + #define PBIT 4 /* smallest integer such that (1U << PBIT) > NP */ + #define TBIT 5 /* smallest integer such that (1U << TBIT) > NT */ +-#if NT > NP +-# define NPT NT +-#else +-# define NPT NP +-#endif ++#define NPT (1 << TBIT) + + +¶²¤é¤¯¡¢NT ¤òĶ¤¨¤ëÃͤ¬°µ½Ìʸ¤ËËä¤á¹þ¤Þ¤ì¤Æ¤â¥Ð¥Ã¥Õ¥¡¥ª¡¼¥Ð¡¼¥Õ¥í¡¼¤·¤Ê +¤¤¤è¤¦¤Ë¤¹¤ë¤¿¤á¤Ë pt_len ¤Î¥Ð¥Ã¥Õ¥¡¥µ¥¤¥º¤òÂ礭¤¯¤·¤¿¤Î¤À¤í¤¦(½ÅÍפʲþ +½¤ÅÀ¤Î£³ÅÀÌܤòÊ̤ÊÊýË¡¤Ç²ò·è¤·¤Æ¤¤¤ë¡£¸Ä¿ÍŪ¤Ë¤Ï¤³¤Î¤è¤¦¤ÊÂнè¤Ï¹¥¤ß¤Ç +¤Ê¤¤¡£°Õ¿Þ¤¬¤ï¤«¤ê¤Ë¤¯¤¤¤«¤é¤À) + +c_len ¤ÎÎΰ襵¥¤¥º(NC)¤Ï¤È¤¤¤¦¤È¡¢gzip ¤Ç¤Ï¸µ¡¹ c_len ¤Î¥Ð¥Ã¥Õ¥¡¥µ¥¤¥º +¤Ï NC ¤è¤ê¤âÂ礭¤¤(8192 or 16384)¡£¤É¤¦¤ä¤é¾¤ÎÊÑ¿ô¤ò»È¤¤²ó¤·¤·¤Æ¤¤¤ë¤¿ +¤á¤Ë¤³¤Î¤è¤¦¤Ë¤Ê¤Ã¤Æ¤¤¤ë¤è¤¦¤À¡£ + + /* local ush left[2 * NC - 1]; */ + /* local ush right[2 * NC - 1]; */ +@@ -155,7 +151,7 @@ local void make_table(nchar, bitlen, tab + for (i = 1; i <= 16; i++) + start[i + 1] = start[i] + (count[i] << (16 - i)); + if ((start[17] & 0xffff) != 0) +- error("Bad table\n"); ++ gzip_error ("Bad table\n"); + +¤³¤³¤ÎȽÄê(Ìڤι½ÃÛ¤¬Àµ¤·¤¤¤«¤É¤¦¤«)¤ÏÊѤ¨¤Ê¤«¤Ã¤¿¤è¤¦¤À¡£ + + jutbits = 16 - tablebits; + for (i = 1; i <= (unsigned)tablebits; i++) { +@@ -179,6 +175,8 @@ local void make_table(nchar, bitlen, tab + if ((len = bitlen[ch]) == 0) continue; + nextcode = start[len] + weight[len]; + if (len <= (unsigned)tablebits) { ++ if ((unsigned) 1 << tablebits < nextcode) ++ gzip_error ("Bad table\n"); + for (i = start[len]; i < nextcode; i++) table[i] = ch; + } else { + k = start[len]; + +Âå¤ï¤ê¤Ë¡¢table[] ¤ÎÎΰèÈϰϤòĶ¤¨¤ëÉä¹æ¤¬¸½¤ì¤¿¾ì¹ç¤Ë¥¨¥é¡¼¤Ë¤Ê¤ë¤è¤¦ +¤Ë¤·¤Æ¤¤¤ë(½ÅÍפʲþ½¤ÅÀ¤Î£²ÅÀÌÜ¡£¤Á¤ã¤ó¤È¡¢c_len ¤À¤±¤Ç¤Ê¤¯¡¢pt_len ¤Î +¾ì¹ç¤â¥Á¥§¥Ã¥¯¤µ¤ì¤ë¤³¤È¤Ë¤Ê¤ë)¡£ + +@@ -223,6 +221,8 @@ local void read_pt_len(nn, nbit, i_speci + if (c == 7) { + mask = (unsigned) 1 << (BITBUFSIZ - 1 - 3); + while (mask & bitbuf) { mask >>= 1; c++; } ++ if (16 < c) ++ gzip_error ("Bad table\n"); + } + fillbuf((c < 7) ? 3 : c - 3); + pt_len[i++] = c; + +p_len, t_len ¤Ë¤Ä¤¤¤Æ Huffman Éä¹æŤè¤êÂ礭¤¤Ãͤ¬Éü¹æ¸ì¤È¤Ê¤ë¾ì¹ç¤Ë¥¨ +¥é¡¼¤È¤·¤Æ¤¤¤ë¡£(½ÅÍפʲþ½¤ÅÀ¤Î£±ÅÀÌÜ) + +¥Ñ¥Ã¥Á¤Ç¤Ï¡¢make_table() Æâ¤Ç¥Á¥§¥Ã¥¯¤·¤Æ¤¤¤¿¤È¤³¤í¤ò¼ÂºÝ¤ËÃͤòÆɤ߹þ¤à +²Õ½ê¤Ë°Ü¤·¤¿¤Î¤À¤í¤¦¡£¤½¤·¤Æ¡¢c_len ¤Î¾ì¹ç¤Ï¡¢t_len ¤ÎÉü¹æ¤ÇÌڤι½ÃÛ +¥Á¥§¥Ã¥¯¤Ë¤Æ¥¨¥é¡¼¤¬¸¡½Ð¤µ¤ì¤Ê¤±¤ì¤ÐÌäÂê¤Ê¤¤¤È¤ß¤Ê¤·¤Æ¤¤¤ë¤Î¤À¤í¤¦¤È»× +¤¦¡£ + +¤É¤¦¤ä¤éÊý¿Ë¤È¤·¤Æ¤ÏºÇÄã¸Â¤Î¥Á¥§¥Ã¥¯¤ÇºÑ¤Þ¤»¤Æ¤¤¤ë¤é¤·¤¤¡£¤µ¤¹¤¬¤Ë¥¢¥ë +¥´¥ê¥º¥à¤ò½ÏÃΤ·¤¿¾å¤Ç¤Î½¤Àµ¤Î¤è¤¦¤Ë¸«¤¨¤ë¤¬¡¢¤³¤ì¤ÇÎɤ¤¤Î¤«¤¤¤Þ¤Ò¤È¤Ä +³Î¿®¤¬»ý¤Æ¤Ê¤¤¡£¤Þ¤¢¡¢gzip ¤Ë¤Ä¤¤¤Æ¤Ï¤³¤ì°Ê¾å¤Ï¿¨¤ì¤Ê¤¤¤Ç¤ª¤³¤¦¡£ + + # Local Variables: # mode : indented-text # indent-tabs-mode: nil