--- /dev/null
+ The Hacking of LHa for UNIX (1st draft)
+ -------------------------------------------
+
+ 2003-01-05 Koji Arai <mailto:jca02266@nifty.ne.jp>
+
+Ëܽñ¤Ï¡¢LHa for UNIX 1.14i ¤Î¥½¡¼¥¹¤ò²òÆɤ·¡¢¤½¤Î°µ½Ì¥¢¥ë¥´¥ê¥º¥à¤Î¼Â
+Áõ¤ò³Îǧ¤¹¤ë¤¿¤á¤Î¤â¤Î¤À¡£¤³¤ÎÀ®²Ì¤ÏÊ̤ηÁ¤Ç¤Þ¤È¤á¤Ê¤ª¤µ¤ì»ñÎÁ¤Ë¤Ê¤ë¤«
+¤â¤·¤ì¤Ê¤¤¤·¡¢¤³¤Î¤Þ¤Þ¤Î·Á¤ÇÊݴɤµ¤ì¤ë¤«¤â¤·¤ì¤Ê¤¤¤·¡¢¿·¤¿¤Ë¥½¡¼¥¹¤ò½ñ
+¤µ¯¤³¤¹¸µ¤Ë¤Ê¤ë¤«¤â¤·¤ì¤Ê¤¤¡£¤È¤Ë¤«¤¯¡¢²Ë¤ÊÀµ·îµÙ¤ß¤òÄÙ¤¹¤¿¤á¤Ë¤ä¤Ã¤Æ
+¤ß¤¿¤À¤±¤Î¤â¤Î¤À¡£(µÙ¤ß¤¬ÌÀ¤±¤ë¤È¤Þ¤¿Ë»¤·¤¯¤Ê¤ë¤Î¤Ç¡¢¤³¤ì°Ê¾å¤Þ¤Ã¤¿¤¯
+²¿¤â¤·¤Ê¤¤¤«¤â¤·¤ì¤Ê¤¤)
+
+¸½»þÅÀ¤Ç¤Ï¡¢slide.c ¤Î²òÀϤÀ¤±¤Ç¤¢¤ë¡£huf.c ¤âƱ»þ¿Ê¹Ô¤Ç²òÀÏÃæ¤À¤¬¡¢Ê¸
+ÂΤ¬°Û¤Ê¤ë(Æɤߤâ¤Î¤È¤·¤Æ¤ÎÂκۤòÀ°¤¨¤Æ¤¤¤Ê¤¤)¤Î¤Ç¸ø³«¤¹¤ë¤È¤·¤Æ¤âÊÌʸ
+½ñ¤Ë¤Ê¤ë¤À¤í¤¦(huf.c ¤Î²òÀÏʸ½ñ¤Ï¸½»þÅÀ¤Ç¥Ç¥Ð¥Ã¥¬¤Ë¤è¤ë¤ª¤Ã¤«¤±¤¬Ãæ¿´
+¤Î¥á¥â¤Ç¤·¤«¤Ê¤¤)
+
+# ËÜÅö¤Ï¡¢huf.c ¤Î²òÀϤòÀè¤Ë¹Ô¤Ã¤Æ¤¤¤¿ slide ¼½ñ¤Î encoding Éô¤Ï¤Ê¤¯
+# ¤Æ¤â LHA ¸ß´¹¥¢¡¼¥«¥¤¥Ð¤Ïºî¤ì¤½¤¦¤À¤Ã¤¿¤«¤é¤À¤¬¡¢huf.c ¤Ï slide.c
+# ¤ËÈæ¤Ù¤ÆÆñ²ò¤ÊÉôʬ¤¬Â¿¤½¤¦¤À¤«¤é¡¢¸å²ó¤·¤Ë¤·¤¿¡£
+
+Ëܽñ¤Ï¡¢¤Þ¤À̤´°À®¤Ç¤¢¤ë¡£¤Ë¤â¤«¤«¤ï¤é¤º¸ø³«¤¹¤ë¤Î¤Ï¤³¤ì°Ê¾å³¤«¤Ê¤¤¤«
+¤â¤·¤ì¤Ê¤¤¤«¤é¤Ç¤¢¤ë(µ¤¤¬¸þ¤¤¤¿¤é¤Þ¤¿Â³¤¤ò½ñ¤¯¤À¤í¤¦¡£¤¢¤ë¤¤¤Ï±þ±ç¤Î
+¤ª¼ê»æ¤¬¤¯¤ì¤Ð¤ä¤ëµ¤¤¬½Ð¤ë¤«¤â¤·¤ì¤Ê¤¤)¡£
+
+Ëܽñ¤Ï¥Õ¥ê¡¼¤Ç¤¢¤ë¡£Ê£À½¡¢²þÊÑ¡¢ºÆÇÛÉۤϼ«Í³¤Ç¤¢¤ë¤È¤¤¤¦¤³¤È¤À¡£¤¿¤À¤·
+Ëܽñ¤Ë¤è¤êÀ¸¤¸¤¿¤¢¤é¤æ¤ë»³²¡¢ÉÔÍø±×¤ËÂФ·¤Æ¤Ï°ìÀÚ¤ÎÊݾڤϤʤ¤¡£Ëܽñ¤Ë
+¤Ï±³¤¬¤¢¤ë¤«¤â¤·¤ì¤Ê¤¤¡£¤½¤ì¤ËÂФ·¤Æ±³¤ò¶µ¤¨¤é¤ì¤¿¤ÈÃø¼Ô¤òÈòÆñ¤ò¤·¤Ê¤¤
+¤Ç夤¿¤¤¡£¤·¤«¤·´Ö°ã¤¤¤Î»ØŦ¤Ï¹½¤ï¤Ê¤¤(¤¼¤Ò¤ª´ê¤¤¤·¤¿¤¤)¡¢Ãø¼Ô¤Ï°µ½Ì
+½èÍý¤Ë´Ø¤·¤Æ¤Ï̵ÃΤǤ¢¤ë¡£ÍѸì¤Î»È¤¤ÊýÅù¤ÏŬÀڤǤʤ¤¤«¤â¤·¤ì¤Ê¤¤¤Î¤Ç¤³
+¤ÎÊýÌ̤Ǥâ¸æ»ØƳ失¤ì¤Ð¹¬¤¤¤Ç¤¢¤ë¡£
+
+===============================================================================
+o ɽµ¤Ë¤Ä¤¤¤Æ
+
+* ´Ø¿ô¤Ï¡¢¤½¤ÎÄêµÁ¥½¡¼¥¹file.c ¤È´Ø¿ô̾ func() ¤ò¼¨¤¹¤Î¤Ë
+ file.c:func()
+ ¤È¤¤¤¦µ½Ò¤ò»È¤¦
+
+*
+
+o ÍѸì¤Ë¤Ä¤¤¤Æ
+
+* Éä¹æ
+ Éä¹æ²½¡¢Éä¹æ¸ì¡¢°µ½Ìʸ
+
+* Éü¹æ
+ Éü¹æ²½¡¢Éü¹æ¸ì¡¢Éü¹æʸ
+
+===============================================================================
+
+¤Þ¤º¡¢¹½Â¤¤Ë¤Ä¤¤¤Æ¹Í¤¨¤ë¡£
+
+slide¼½ñË¡¤Ï¡¢encoding ¤Ë¤µ¤Þ¤¶¤Þ¤Ê¹©Éפ¬¶Å¤é¤µ¤ì¤ë¤Î¤Ç¤È¤Æ¤âÊ£»¨¤À¤¬¡¢
+ÉáÄÌ decoding ¤Ïñ½ã¤Ç¤¢¤ë¡£decoding ¤ò²òÀϤ¹¤ë¤³¤È¤Ç¤É¤Î¤è¤¦¤Ê°µ½Ìʸ
+¤òºî¤Ã¤Æ¤¤¤ë¤Î¤«¤òÄ´¤Ù¤Æ¤ß¤ë¡£
+
+decoding ¤ò¹Ô¤¦½èÍý¤Ï¡¢slide.c ¤Î decode() ¤Ç¤¢¤ë¡£¤³¤Î½èÍý¤ò¸«¤Æ¤ß¤ë
+¤È»×¤Ã¤¿Ä̤ê´Êñ¤Ë²òÆɤǤ¤¿(°Ê²¼)
+
+ 1. huffman coding ¤Ë¤è¤êÉü¹æ¤·¤¿Ê¸»ú¤ò´Ä¾õ¥Ð¥Ã¥Õ¥¡ dtext ¤Ë½ñ¤¹þ¤à
+ Ä̾ï¤Îʸ»ú c ¤Ï¡¢c < 256 ¤Çɽ¸½¤µ¤ì¤Æ¤¤¤ë(¤Ä¤Þ¤ê¤½¤Î¤Þ¤Þ)
+
+ 2. Ä̾ï¤Îʸ»ú¤Ç¤Ê¤¤¤â¤Î¤¬¸½¤ì¤¿¤é¡¢¤½¤ì¤ÏŤµ¤Ç¤¢¤ë¡£Ä¹¤µ len ¤Ï¡¢
+ len > 255 ¤Çɽ¸½¤µ¤ì¤Æ¤¤¤ë¡£len ¤«¤é 0xfd(253) ¤ò°ú¤¤¤¿Ãͤ¬
+ ¼ÂºÝ¤ÎŤµ¤òɽ¤¹(-lzs- method ¤Î¾ì¹ç¤Ï¡¢0xfe(254)¤ò°ú¤¯)
+ ¡ÖŤµ¡×¤¬¡¢¸½¤ì¤¿¤é¤½¤Îľ¸å¤Ë¤Ï¡Ö°ÌÃ֡פ¬½ñ¤«¤ì¤Æ¤¤¤ë¤Î¤Ç¤½¤ì¤ò
+ Æɤࡣ¤³¤¦¤·¤Æ¡¢Ä¹¤µ¤È°ÌÃ֤Υڥ¢<len, pt>¤òÆÀ¤ë
+
+ dtext ¤«¤é pt+1 ¥Ð¥¤¥ÈÁ°¤Î len ¥Ð¥¤¥È¤òÆɤߡ¢dtext ¤ËÄɲäǽñ¤¹þ¤à
+
+ 3. dtext ¤¬°ìÇÕ(dicsiz)¤Ë¤Ê¤Ã¤¿¤é¥Õ¥¡¥¤¥ë¤Ë½ñ¤½Ð¤¹
+
+¤³¤ì¤Î·«¤êÊÖ¤·¤Ç¤¢¤ë¡£¤Ä¤Þ¤ê¡¢slide ¼½ñË¡¤Î°µ½Ìʸ¤Ï¡¢Ê¸»ú c ¤È<len,
+pt> ¤ÎʤӤǤ¢¤ë¤³¤È¤¬¤ï¤«¤ë¡£Î㤨¤Ð¡¢Ê¸»úÎó c1 c2 c1 c2 ¤Ï¡¢°Ê²¼¤Î¤è
+¤¦¤Ëɽ¸½¤µ¤ì¤Æ¤¤¤ë¤Ï¤º¤Ç¤¢¤ë¡£(ËÜÅö¤Ï¡¢Ä¹¤µ¤¬ 2 °Ê²¼¤Ç¤Ï°µ½Ì¤¬µ¯¤³¤é¤Ê
+¤¤¤Î¤Çʿʸ¤Î¤Þ¤Þ½ÐÎϤ¹¤ë¡£Ä¹¤µ¤ÏºÇÄã¤Ç¤â 3 ¤ÏɬÍ×)
+
+ +----+----+--------+
+ | c1 | c2 | <2, 1> |
+ +----+----+--------+
+
+¤Ç¤Ï¡¢¤³¤Î¹½Â¤¤òºîÀ®¤¹¤ë°µ½Ì½èÍý¤Ë¤Ä¤¤¤Æ¹Í¤¨¤ë¡£slide ¼½ñË¡¤Ç¤Ï¡¢¥Õ¥¡
+¥¤¥ë¤«¤éÆɤ߹þ¤ó¤Àʸ»úÎó token ¤¬¡¢°ÊÁ°¤ËÆɤ߹þ¤ó¤À¼½ñ¤Ë¸ºß¤¹¤ì¤Ð
+<len, pt> ¤Î¥Ú¥¢¤ò½ÐÎϤ·¡¢Â¸ºß¤·¤Ê¤±¤ì¤Ð token ¤ò¤½¤Î¤Þ¤Þ½ÐÎϤ¹¤ë¡£ÆÉ
+¤ß¹þ¤ó¤À token ¤Ï¡¢¼½ñ¤ËÄɲä·¡¢¼½ñ¤Î¸ì¤¬°î¤ì¤¿¤é¸Å¤¤¾ðÊó¤ò¼Î¤Æ¤ë¡£
+
+²¿¤âͽÈ÷Ã챤¬¤Ê¤¤¾õÂ֤ǽñ¤±¤Ð
+
+ while (read_file(&token, tokensiz)) {
+ len = search_dict(dict, token, &pt);
+ if (len == -1) {
+ print_token(token);
+ else
+ print_pair(len, pt);
+ update_dict(dict, token);
+ }
+
+¤Î¤è¤¦¤Ë¤Ê¤ë¤Ï¤º¡£¤³¤³¤Ç¡¢tokensiz ¤Ï token ¤ÎºÇÂ祵¥¤¥º¤Ç¡¢ºÇĹ°ìÃ×Ĺ
+¤òɽ¤¹¡£¤³¤ÎÃͤ¬Â礤±¤ì¤ÐÂ礤¤Äø¡¢°µ½Ì¸úΨ¤ÏÎɤ¯¤Ê¤ë¤Ï¤º¤Ç¡¢lha ¤Ç¤Ï¡¢
+¤³¤ì¤Ï MAXMATCH{256}¤Ç¤¢¤ë¡£¤Þ¤¿¡¢dict ¤Ï¼½ñ¤Ç¤³¤Î¥µ¥¤¥º¤Ï lha ¤Î
+-lz5- ¥á¥½¥Ã¥É¤Ç¤Ï¡¢8192 ¤È¤Ê¤Ã¤Æ¤¤¤ë¡£¤³¤Î¼½ñ¤âÂ礤±¤ì¤ÐÂ礤¤ÄøÎÉ
+¤¤¤Ï¤º¤À¡£¤½¤ÎÊý¤¬°ìÃ×ʸ»úÎ󤬸«¤Ä¤«¤ê¤ä¤¹¤¤¡£(¤¿¤À¤·¡¢¼½ñ¤¬Â礤¤¤È
+°ìÃ×°ÌÃÖ¤ò¼¨¤¹¾ðÊó <len, pt> ¤Î¾ðÊóÎ̤¬Áý¤¨¤ë¤Ï¤º¤À¤·¡¢Â®ÅÙ¤âÃÙ¤¯¤Ê¤ë
+¤À¤í¤¦¡£¸å¤Ç¸¡¾Ú¤¹¤ë)
+
+¤Ç¡¢¼ÂºÝ¤Ë¥½¡¼¥¹¤ò¸«¤Æ¤ß¤ë¤È(slide.c:encode())¡¦¡¦¡¦¡¢¤Þ¤Ã¤¿¤¯¤³¤Î¤è¤¦
+¤Ê¹½Â¤¤Ë¤Ï¤Ê¤Ã¤Æ¤Ê¤¤¤è¤¦¤Ë¸«¤¨¤ë¡£²¿¤ä¤é¤ä¤ä¤³¤·¤¤¤³¤È¤Ð¤«¤ê¤Ç¤Þ¤Ã¤¿¤¯
+¤ï¤«¤é¤Ê¤¤¡£¤Ê¤¼¤³¤³¤Þ¤Ç¤ä¤ä¤³¤·¤¤¤Î¤«¤Èµã¤¤¿¤¯¤Ê¤Ã¤Æ¤¯¤ë¤¬¡¢¤½¤ì¤Ï®
+Å٤Τ¿¤á¤Ç¤¢¤ë(ËÜÅö¡©)¡£¾åµ¤Î¥³¡¼¥É¤Ç¡¢search_dict() ¤Ï¡¢Ã±¤Ë dict ¤«
+¤é token ¤Ë°ìÃפ¹¤ë°ÌÃÖ¤ò¸¡º÷¤¹¤ë¤À¤±¤ÇÎɤµ¤½¤¦(¼ÂºÝ¤Ë¤½¤ì¤Ç¤âÎɤ¤)¤À
+¤¬¡¢¤³¤ì¤Ç¤Ï¤Þ¤Ã¤¿¤¯Â®ÅÙ¤¬½Ð¤Ê¤¤¡£¤³¤Î¤¢¤¿¤ê¤Î¹©Éפ¬ slide ¼½ñË¡¤Î¥
+¥â¤Ç¤¢¤ë¡£
+
+¤½¤¦¤¤¤¦¤ï¤±¤Ç¡¢¤³¤ÎÉôʬ¤òÆɤ߲ò¤¯¤³¤È¤Ë¤¹¤ë¡£¤Ê¤ª¡¢Í½È÷Ãμ±¤È¤·¤Æ lha
+¤Ç¤Ï¡¢¼½ñ¤«¤é token ¤òõ¤¹¤Î¤Ë¥Ï¥Ã¥·¥å¤¬»È¤ï¤ì¤Æ¤¤¤ë¤é¤·¤¤¤³¤È¤òµ¤·
+¤Æ¤ª¤¯¡£
+
+¤³¤³¤Ç¤Ï¼ÂºÝ¤Ë¥Ç¥Ð¥Ã¥¬¤ÇÆ°ºî¤µ¤»¤Ê¤¬¤é²òÆɤ¹¤ë¤Î¤Ç¤Ï¤Ê¤¯¡¢¥½¡¼¥¹¤òÆɤà
+¤À¤±¤ÇÍý²ò¤Ç¤¤ë¤«¤ò»î¤¹¤³¤È¤Ë¤¹¤ë¡£¤Þ¤¿¡¢ËÜʸ¤ÏË¿½ñ(Ææ)¤Î¥Î¥ê¤ò¥Þ¥Í¤Æ
+¤¤¤ë¤È»ØŦ¤¹¤ëÊý¤¬¤¤¤ë¤«¤â¤·¤ì¤Ê¤¤¡¦¡¦¡¦¤¬¤Þ¤Ã¤¿¤¯¤½¤ÎÄ̤ê¤À¡£
+
+¤Þ¤º¡¢¤½¤Î¤â¤Î¤º¤Ð¤ê¤Î encode() (slide.c) ¤ò¸«¤ë¡£°Ê²¼¤¬¤³¤Î´Ø¿ô¤À¤¬
+½èÍý¤ÎÍ×ÅÀ¤À¤±¤ËÃåÌܤ¹¤ë¤¿¤á¤ËÉÔÍפ½¤¦¤ÊÉôʬ¤Ï(¸½»þÅÀ¤Çͽ¬¤Ç)ºï¤Ã¤¿¡£
+
+unsigned int
+encode()
+{
+ int lastmatchlen;
+ unsigned int lastmatchoffset;
+
+ /* (A) */
+ init_slide();
+
+ /* (B) */
+ remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
+ encoded_origsize = remainder;
+ matchlen = THRESHOLD - 1;
+
+ pos = dicsiz;
+
+ if (matchlen > remainder) matchlen = remainder;
+
+ /* (C) */
+ hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
+ ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
+
+ /* (D) */
+ insert();
+
+ while (remainder > 0 && ! unpackable) {
+ /* (E) */
+ lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1;
+ --matchlen;
+
+ /* (F) */ /* (G) */
+ get_next(); match_insert();
+ if (matchlen > remainder) matchlen = remainder;
+
+ /* (H) */
+ if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
+ /* (H.1) */
+ encode_set.output(text[pos - 1], 0);
+ count++;
+ } else {
+ /* (H.2) */
+ encode_set.output(lastmatchlen + (UCHAR_MAX + 1 - THRESHOLD),
+ (lastmatchoffset) & (dicsiz-1) );
+ --lastmatchlen;
+
+ while (--lastmatchlen > 0) {
+ get_next(); insert();
+ count++;
+ }
+ get_next();
+ matchlen = THRESHOLD - 1;
+ match_insert();
+ if (matchlen > remainder) matchlen = remainder;
+ }
+ }
+}
+
+¤Þ¤º¡¢¤³¤Î´Ø¿ô¤«¤é³µ´Ñ¤ò¸«¤Æ¤ß¤ë¤È¡¢¥ë¡¼¥×¤ÎÁ°¤Ë½é´ü²½½èÍý¤È¤·¤Æ
+°Ê²¼¤¬¹Ô¤ï¤ì¤Æ¤¤¤ë¡£
+
+(A) init_slide() ½é´ü²½¤¹¤ë
+(B) ¥Õ¥¡¥¤¥ë¤òÆɤ߹þ¤ß text[] ¤Ë³ÊǼ¤¹¤ë¡£
+(C) ¥Ï¥Ã¥·¥åÃÍ hval ¤ò·×»»¤¹¤ë¡£
+(D) insert() ¤¹¤ë (¤¤Ã¤È¼½ñ¤Ë token ¤òÄɲ䷤Ƥ¤¤ë¤Î¤À¤í¤¦)
+
+¤½¤·¤Æ¡¢¥ë¡¼¥×½èÍý¤Ç¤Ï°Ê²¼¤Î½èÍý¤¬¹Ô¤ï¤ì¤Æ¤¤¤ë
+
+(E) lastmatchlen, lastmatchoffset, matchlen ¤ò¹¹¿·¤¹¤ë¡£
+(F) get_next() (¼¡¤Î token ¤òÆɤࡣ¤¿¤Ö¤ó)
+(G) match_insert() (¼½ñ¤ËÄɲ乤롣¤¿¤Ö¤ó)
+
+(H) matchlen > lastmatchlen || lastmatchlen < THRESHOLD ¤Ê¤é
+
+(H.1) output() ¤¹¤ë¡£(¥Þ¥Ã¥Á¤·¤Ê¤«¤Ã¤¿¤é¤½¤Î¤Þ¤Þ½ÐÎϤ·¤Æ¤¤¤ë¤Î¤À¤í¤¦¡£¤¿¤Ö¤ó)
+(H.2) ¤½¤¦¤Ç¤Ê¤±¤ì¤Ð(¥Þ¥Ã¥Á¤·¤¿¤Ê¤é)¡¢output()¤·¡¢²¿¤«¤¤¤í¤¤¤í¤¹¤ë¡£
+
+¸½»þÅÀ¤Ç¡¢(H.2) ¤ÎÉôʬ¤Ï¤è¤¯²òÆɤǤ¤Ê¤«¤Ã¤¿¡£²¿¤ä¤éºÆÅÙ get_next() ¤¬
+¸Æ¤Ð¤ì¤Æ¤¤¤¿¤ê¤·¤Æ»×¤Ã¤¿Ä̤ê¤Î½èÍý¥Õ¥í¡¼¤Ë¤Ï¤Ê¤Ã¤Æ¤¤¤Ê¤¤¡£¤À¤¬¡¢¤³¤³¤Ç
+¤Ï¾Ç¤é¤ºÊüÃÖ¤¹¤ë¤³¤È¤Ë¤·¤Æ¡¢¤³¤³¤Þ¤ÇͽÁۤǽñ¤¤¤¿Éôʬ¤ÎºÙÉô¤Ë¿¨¤ì¤ë¤³¤È
+¤Ë¤¹¤ë(ñ¤Ë¤³¤³¤Þ¤Ç¤ÎͽÁÛ¤¬´Ö°ã¤Ã¤Æ¤¤¤ë¤À¤±¤«¤â¤·¤ì¤Ê¤¤¤Î¤À¤«¤é¡¢¤ï¤«
+¤é¤Ê¤¤Éôʬ¤ò̵Íý¤Ë¤ï¤«¤ë¤è¤¦¤Ë´èÄ¥¤ëɬÍפϤʤ«¤í¤¦)
+
+´Ø¿ô¤ÎºÙÉô¤Ë¿¨¤ì¤ëÁ°¤Ë¥Ç¡¼¥¿¹½Â¤¤Ë¤Ä¤¤¤ÆÄ´¤Ù¤Æ¤ª¤¯¡£¥Ç¡¼¥¿¹½Â¤¤ËÂФ·¤Æ
+¤ÎÍý²ò¤¬¿¼¤Þ¤ì¤Ð¥¢¥ë¥´¥ê¥º¥à¤Î80%¤Ïʬ¤«¤Ã¤¿¤âƱÁ³¤À(¸ØÄ¥)¡£slide.c ¤Ç
+»ÈÍѤµ¤ì¤Æ¤¤¤ë¥Ç¡¼¥¿¹½Â¤¤Ï°Ê²¼¤ÎÄ̤ê¤À¡£(ÉÔÍפ½¤¦¤À¤È»×¤¦¤â¤Î¤Ï½ü¤¤¤Æ
+¤¢¤ë)
+
+static unsigned int *hash;
+static unsigned int *prev;
+unsigned char *too_flag;
+static unsigned int txtsiz;
+static unsigned long dicsiz;
+static unsigned int hval;
+static int matchlen;
+static unsigned int matchpos;
+static unsigned int pos;
+static unsigned int remainder;
+
+too_flag ¤À¤±¡¢static ¤¬¤Ä¤¤¤Æ¤Ê¤¤¤¬¡¢Â¾¤Î¥½¡¼¥¹¤ò grep ¤·¤Æ¤â¤³¤ÎÊÑ¿ô
+¤ò»È¤Ã¤Æ¤¤¤ë²Õ½ê¤Ï¤Ê¤¤¡¢Ã±¤Ë static ¤ÎÉÕ¤±Ëº¤ì¤À¤í¤¦¡£
+
+¤³¤ì¤é¤ÎÊÑ¿ô¤Ï¡¢encode() ¤ÎËÁƬ init_slide() ¤Ç½é´ü²½¤µ¤ì¤Æ¤¤¤ë¡¦¡¦¤Î
+¤«¤È»×¤Ã¤¿¤é°ã¤Ã¤¿¡£slide.c:encode_alloc() ¤Ç¹Ô¤ï¤ì¤Æ¤¤¤ë¡£
+
+int
+encode_alloc(method)
+ int method;
+{
+ if (method == LZHUFF1_METHOD_NUM) { /* Changed N.Watazaki */
+ encode_set = encode_define[0];
+ maxmatch = 60;
+ dicbit = 12; /* 12 Changed N.Watazaki */
+ } else { /* method LH4(12),LH5(13),LH6(15) */
+ encode_set = encode_define[1];
+ maxmatch = MAXMATCH;
+ if (method == LZHUFF7_METHOD_NUM)
+ dicbit = MAX_DICBIT; /* 16 bits */
+ else if (method == LZHUFF6_METHOD_NUM)
+ dicbit = MAX_DICBIT-1; /* 15 bits */
+ else /* LH5 LH4 is not used */
+ dicbit = MAX_DICBIT - 3; /* 13 bits */
+ }
+
+ dicsiz = (((unsigned long)1) << dicbit);
+ txtsiz = dicsiz*2+maxmatch;
+
+ if (hash) return method;
+
+ if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
+
+ hash = (unsigned int*)malloc(HSHSIZ * sizeof(unsigned int));
+ prev = (unsigned int*)malloc(DICSIZ * sizeof(unsigned int));
+ text = (unsigned char*)malloc(TXTSIZ);
+ too_flag = (unsigned char*)malloc(HSHSIZ);
+
+ if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
+ exit(207);
+
+ return method;
+}
+
+°ú¿ô¤ËÅϤµ¤ì¤¿ method (¤³¤ì¤Ï¡¢lh1, lh5, lh6, lh7 ¤Ê¤É¤ò¼¨¤¹)¤Ë¤è¤Ã¤Æ¡¢
+½é´ü²½¤µ¤ì¤ëÆâÍƤ¬ÊѤï¤ë(encode_alloc()Á°È¾Éôʬ)¡£¤³¤Î¤³¤È¤«¤é³ÆÊÑ¿ô¤Î
+ÍÑÅÓ¤â¤ï¤«¤ë¡£
+
+ method maxmatch dicbit
+ ----------------------------
+ -lh1- 60 12
+ -lh5- 256 13
+ -lh6- 256 15
+ -lh7- 256 16
+
+¤È¤¤¤¦¤³¤È¤é¤·¤¤¡£dicbit ¤È¤¤¤¦¤Î¤Ï¼½ñ¥µ¥¤¥º¤Îbit¥µ¥¤¥º¤Ç¡¢¼½ñ¥µ¥¤¥º
+¤Ï 2^dicbit ¤Çɽ¤µ¤ì¤Æ¤¤¤ë¡£lh5 ¤¬ 8KB(2^13)¡¢lh6 ¤¬ 32KB(2^15)¡¢lh7
+¤¬ 64KB(2^16) ¤Î¼½ñ¥µ¥¤¥º¤òÍøÍѤ¹¤ë¤È¸À¤¦¤Î¤ÏͽÈ÷Ãμ±¤Ç¤¢¤ë¡£maxmatch
+¤È¤¤¤¦¤Î¤Ï¡¢token ¤ÎºÇĹ°ìÃ׍Ǥ¢¤ë¡£¤³¤Î¤³¤È¤âͽÈ÷Ãμ±¤È¤·¤Æ¾ÜºÙ¤Ë¤Ï
+¿¨¤ì¤Ê¤¤¡£(¤È¤³¤í¤Ç¡¢Ëܽñ¤Ç¤ÏÅöÌÌ¡¢lh5, 6, 7 ¤Î¤³¤È¤·¤«¸ÀµÚ¤·¤Ê¤¤)
+
+encode_set, encode_define ¤È¤¤¤¦¤Î¤¬¤¢¤ë¤¬¡¢method ¤Ë¤è¤Ã¤Æ¡¢Huffman
+coding ¤ÎÊýË¡¤òÊѤ¨¤Æ¤¤¤ë¤³¤È¤Ï¤Á¤ç¤Ã¤È¸«¤ì¤Ð¤¹¤°¤Ë¤ï¤«¤ë¤·¡¢Â礷¤¿¤³
+¤È¤Ç¤Ï¤Ê¤¤¡£°Ê¹ß̵»ë¤¹¤ë¡£
+
+encode_alloc() ¤Î¸åȾ¤Ç¤Ï¡¢Â¾¤ÎÊÑ¿ô¤Î½é´ü²½(¥Ð¥Ã¥Õ¥¡¤Î³ä¤êÅö¤Æ)¤¬¹Ô¤ï¤ì¤ë¡£
+
+ dicsiz = (((unsigned long)1) << dicbit);
+
+dicsiz ¤Ï¤½¤Î¤â¤Î¤º¤Ð¤ê¼½ñ¥µ¥¤¥º¤Ç¤¢¤ë¡£
+
+ txtsiz = dicsiz*2+maxmatch;
+
+¸½»þÅÀ¤Ç txtsiz ¤¬²¿¤Ê¤Î¤«¤Ï¤ï¤«¤é¤Ê¤¤¡£
+
+ if (hash) return method;
+
+hash ¤Ï¤³¤Îľ¸å¤Ç³ä¤êÅö¤Æ¤é¤ì¤ë¡£¤Ä¤Þ¤ê¡¢°ìÅÙ³äÅö¤ò¹Ô¤Ã¤¿¤é¡¢
+encode_alloc() ¤Ï¡¢°Ê¹ß¥á¥â¥ê¤Î³äÅö¤ò¹Ô¤ï¤Ê¤¤¡£¤¿¤À¤½¤ì¤À¤±¤À¡£
+
+ if (alloc_buf() == NULL) exit(207); /* I don't know this 207. */
+
+alloc_buf() ¤Ï¡¢huf.c ¤ÇÄêµÁ¤µ¤ì¤¿´Ø¿ô¡£¤³¤Î¤³¤È¤«¤é Huffman coding ¤Î
+¤¿¤á¤Î¥Ð¥Ã¥Õ¥¡¤ò³ä¤êÅö¤Æ¤Æ¤¤¤ë¤Î¤À¤í¤¦¡£¤³¤³¤Ç¤Ï̵»ë¡£(¤·¤«¤·¡¢207 ¤È
+¤¤¤¦¤Î¤Ï²¿¤Ê¤Î¤À¤í¤¦¡©)
+
+ hash = (unsigned int*)malloc(HSHSIZ * sizeof(unsigned int));
+ prev = (unsigned int*)malloc(DICSIZ * sizeof(unsigned int));
+ text = (unsigned char*)malloc(TXTSIZ);
+ too_flag = (unsigned char*)malloc(HSHSIZ);
+
+ if (hash == NULL || prev == NULL || text == NULL || too_flag == NULL)
+ exit(207);
+
+hash ¤Ï¡¢¥Ï¥Ã¥·¥åÍѤβ¿¤«¡¢HSHSIZ ¤Ï¡¢¸ÇÄêÃÍ¤Ç 2^15 ¤Ç¤¢¤ë¡£
+
+prev ¤Ï¡¢DICSIZ¤«¤é¼½ñ¤À¤í¤¦¡£Í×ÁǤη¿¤¬ char ¤Ç¤Ê¤¯ int ¤Ç¤¢¤ë¤³¤È¤Ë
+¤âÃíÌܤ·¤Æ¤ª¤¯¡£DICSIZ ¤Ï dicsiz ¤Ç¤â¹½¤ï¤Ê¤¤¤Ï¤º¡£Ã±¤Ë¡ÖÂç¤Ï¾®¤ò·ó¤Í
+¤ë¡×¤ò¼ÂÁ©¤·¤Æ¤¤¤ë¤À¤±¤Ç¤¢¤í¤¦¡¢TXTSIZ ¤âƱÍͤǤ¢¤ë¡£¤ª¤½¤é¤¯¡¢°ìÅÙ¤Î
+¼Â¹Ô¤ÇÊ£¿ô¤Î°µ½Ì¥á¥½¥Ã¥É¤ò»ÈÍѤ·¤¿¾ì¹ç¡¢¤½¤Î¥á¥½¥Ã¥ÉËè¤ËÎΰè¤ò³ä¤êÅö¤Æ
+¤ë¤è¤ê¤ÏºÇÂç¤ÎÃͤò¤¢¤é¤«¤¸¤á°ìÅÙ¤À¤±³ä¤êÅö¤Æ¤¿Êý¤¬Îɤ¤¤È¹Í¤¨¤¿¤Î¤À¤í¤¦¡£
+¤·¤«¤·¡¢¥½¡¼¥¹¤ò»²¾È¤¹¤ë¤È¤¤ÏÈË»¨¤Ë¤Ê¤ë¤Î¤Ç°Ê¹ß¡¢
+ DICSIZ == dicsiz
+ TXTSIZ == txtsiz
+¤Ç¤¢¤ë¤È¤¹¤ë¡£¤³¤ì½ÅÍס£
+
+text ¤Ï¡¢¸½»þÅÀ¤Ç¤ÏÉÔÌÀ
+
+too_flag ¤âÉÔÌÀ
+
+¤Ã¤È¤Ê¤ë¡£¤Þ¤À¡¢Îɤ¯Ê¬¤«¤é¤Ê¤¤¤¬¡¢°Ê²¼¤Î¿Þ¤ò½ñ¤¤¤Æ¤ª¤³¤¦¡£¸å¤Ç²¿Å٤⸫
+¤ë¤³¤È¤Ë¤Ê¤ë¤À¤í¤¦¡£¤³¤Î¿Þ¤Ï¥¹¥±¡¼¥ë¤¬ lh7 ¤Î¾ì¹ç¤òÁÛÄꤷ¤Æ¤¤¤ë¤¬¡£¤³
+¤Î¤³¤È¤ÏÂ礷¤¿¤³¤È¤Ç¤Ï¤Ê¤¤¤Ï¤º¤À¡£¤Þ¤¿¡¢too_flag ¤È hash ¤Î¥¹¥±¡¼¥ë¤¬
+°ì½ï¤À¤¬¤³¤ì¤Ï¥µ¥¤¥º(Îΰè¤Î¥Ð¥¤¥È¿ô)¤¬°ì½ï¤Ê¤Î¤Ç¤Ï¤Ê¤¯¡¢Í×ÁÇ¿ô¤¬°ì½ï¤Ç
+¤¢¤ë¤³¤È¤ò¼¨¤·¤Æ¤¤¤ë¡£¤Û¤È¤ó¤É¤Î¾ì¹çÍ×ÁǤη¿¤Î°ã¤¤¤È¤¤¤¦¤Î¤Ï½èÍýÆâÍƤË
+¤È¤Ã¤Æ½ÅÍפʤ³¤È¤Ç¤Ï¤Ê¤¤¤Ï¤º¤À¡£
+
+----------------------------------------------------------------------------
+
+ 0 2^15=32768
+ +-------------+
+ hash | |
+ +-------------+ dicsiz=2^dicbit
+ +-------------+-------------+ 2*2^dicbit
+ prev | | | |
+ +-------------+-------------+ v txtsiz
+ +-------------+-------------+-------------+-------------+---+
+ text | | | | | |
+ +-------------+-------------+-------------+-------------+---+
+ <--->
+ maxmatch{256}
+ too_flag 2^15
+ +-------------+
+ | |
+ +-------------+
+----------------------------------------------------------------------------
+
+
+Àè¤Ë¼¨¤·¤¿ÊÑ¿ô¤ÎÃæ¤Ç¤Þ¤À½é´ü²½¤Ë¤Ï¸½¤ì¤Æ¤¤¤Ê¤¤¤â¤Î¤¬¤¢¤ë¡£Îóµó¤¹¤ë¤È
+
+static unsigned int hval;
+static int matchlen;
+static unsigned int matchpos;
+static unsigned int pos;
+static unsigned int remainder;
+
+¤À¡¢¤¶¤Ã¤È¥½¡¼¥¹¤òį¤á¤ë¤È slide.c:insert() ¤È¤¤¤¦´Ø¿ô¤Ë
+ hash[hval] = pos;
+¤È¤¤¤¦¤Î¤¬¸½¤ì¤Æ¤¤¤ë¤«¤é¡¢hval ¤Ï¡¢hash[] ¤Î°ÌÃÖ¤ò»Ø¤·¡¢hash ¤Ë¤Ï¡¢pos
+¤ò³ÊǼ¤¹¤ë¤È¿ä¬¤µ¤ì¤ë¡£Æ±ÍͤË
+ prev[pos & (dicsiz - 1)] = hash[hval];
+¤È¤¤¤¦¤Î¤â¸½¤ì¤Æ¤¤¤ë¤«¤é pos ¤Ï¡¢prev[] ¤Î°ÌÃÖ¤ò»Ø¤·¡¢prev ¤Ë¤Ï¡¢
+hash[hval] ¤Ä¤Þ¤ê¡¢pos ¤ò³ÊǼ¤·¤Æ¤¤¤ë¤è¤¦¤À¡£¤³¤ì¤Ï¾¯¤·Ææ¤Ê½èÍý¤À¤¬¡¢
+insert() ¤ÎÁ´ËƤÏû¤¤(¤È¤¤¤¦¤«¤³¤ì¤À¤±)¤Ê¤Î¤Ç¡¢¤Á¤ç¤Ã¤È²£Æ»¤Ë¤½¤ì¤Æ¾Ü
+ºÙ¤Ë¸«¤Æ¤ß¤è¤¦¡£(¸½ºß¤Î²òÀϤμñ»Ý¤Ï¡¢ÊÑ¿ô¤ÎÍÑÅӤγµÍפòͽÁÛ¤¹¤ë¤³¤È)
+
+/* ¸½ºß¤Îʸ»úÎó¤ò¥Á¥§¡¼¥ó¤ËÄɲ乤ë */
+
+static void insert()
+{
+ prev[pos & (dicsiz - 1)] = hash[hval];
+ hash[hval] = pos;
+}
+
+¥³¥á¥ó¥È¤Ï¤Þ¤Ã¤¿¤¯°ÕÌ£ÉÔÌÀ¤À¤¬¡¢Ìµ»ë¤·¤Æ½èÍýÆâÍƤËÃåÌܤ¹¤ë¡£prev[] ¤Î
+¥¤¥ó¥Ç¥Ã¥¯¥¹ pos & (dicsiz - 1) ¤Ï¡¢dicsiz ¤¬ 2^n ¤Ç¤¢¤ë¤³¤È¤«¤édicsiz
+¤Ï¥Ó¥Ã¥È¥Þ¥¹¥¯¤Ç¤¢¤ë¤³¤È¤¬¤ï¤«¤ë¡£Î㤨¤Ð²¾¤Ë dicsiz ¤¬ 2^8 ¤À¤È
+dicsiz - 1 ¤Ï¡¢
+
+ 8 7 6 5 4 3 2 1 0 bit
+ --------------------------
+ dicsiz 1 0 0 0 0 0 0 0 0
+ dicsiz-1 1 1 1 1 1 1 1 1
+
+¤Ç¤¢¤ë¡£¤³¤Î¤¹¤Ù¤Æ 1 ¤¬Î©¤Ã¤¿¥Ó¥Ã¥È¥Þ¥¹¥¯¤È pos ¤ò & ¤¹¤ë¤È¡¢¤É¤Î¤è¤¦
+¤Ê pos ¤ÎÃͤËÂФ·¤Æ¤â pos & (dicsiz - 1) ¤Ï¡¢prev[] ¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤ÎÈÏ
+°Ï¤ËǼ¤Þ¤ë¡£¤â¤¦¾¯¤·¸À¤¦¤È pos ¤¬²¾¤Ë¥¤¥ó¥Ç¥Ã¥¯¥¹¤ÎºÇÂçÃÍ+1¤À¤Ã¤¿¾ì¹ç¡¢
+pos & (dicsiz - 1) ¤Ï¡¢0 ¤Ë¤Ê¤ë¡£¤³¤ì¤Ë¤è¤ê¼¡¤ÎͽÁÛ¤¬Î©¤Ä¡£
+
+ o pos ¤¬¡¢prev[] ¤Î°ÌÃÖ¤ò»Ø¤¹¤Î¤Ç¤Ï¤Ê¤¯¡¢pos & (dicsiz - 1) ¤¬
+ prev[]¤Î°ÌÃÖ¤ò»Ø¤¹¡£(pos ¤Ï¡¢¤³¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤ÎÈϰϤò±Û¤¨¤ë²ÄǽÀ¤¬¤¢¤ë)
+ o ¤½¤ì¤ËÈ¿¤·¤Æ¡¢prev[] ¤Ï´Ä¾õ¥Ð¥Ã¥Õ¥¡¤é¤·¤¤¤È¤¤¤¦Í½ÁÛ¤¬Î©¤Æ¤Ð¤ä¤Ï¤ê
+ pos ¤Ï¡¢prev ¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤Ç¤¢¤ë¡£
+
+prev ¤¬´Ä¾õ¥Ð¥Ã¥Õ¥¡¤Ç¤¢¤ë¤ÈͽÁÛ¤¬ÉÕ¤±¤ÐÏä¬Áᤤ¡£pos & (dicsiz-1) ¤Ï¡¢
+pos ¤ÈƱµÁ¤À¤È²ò¼á²Äǽ¤À¤«¤é¤Ç¤¢¤ë(prev ¤¬´Ä¾õ¥Ð¥Ã¥Õ¥¡¤Ç¤Ê¤¯Ìµ¸ÂĹ¤Î¥Ð¥Ã
+¥Õ¥¡¤Ç¤¢¤ë¤ÈÁÛÁü¤·¤è¤¦)¤½¤·¤Æ¡¢pos & (dicsiz-1) ¤ò pos ¤ËÃÖ¤´¹¤¨¤Æ¡¢
+ºÆÅÙ½èÍýÆâÍƤËÃåÌܤ¹¤ë¤È
+
+ prev[pos] = hash[hval];
+ hash[hval] = pos;
+
+¤È¤¤¤¦¤³¤È¤«¤é¡¢
+ 1. (¤³¤Î´Ø¿ô¤ËÍè¤ëÁ°¤Ë) pos ¤¬¹¹¿·¤µ¤ì¤ë¡£(ͽÁÛ)
+ 2. prev[pos] ¤Ë°ÊÁ°¤Î hash[hval] (°ÊÁ°¤Î pos)¤ò³ÊǼ¤¹¤ë
+ 3. hash[hval] ¤Ë¿·¤·¤¤ pos ¤ò½ñ¤¯¡£
+¤È¤¤¤Ã¤¿½èÍý¤Ç¤¢¤ë¤³¤È¤¬Í½ÁÛ¤µ¤ì¤ë¡£¥³¥á¥ó¥È¤Î¡Ö¥Á¥§¡¼¥ó¡×¤â¤Ê¤ó¤È¤Ê¤¯
+ǼÆÀ¤Ç¤¤ë¡£¿·¤¿¤Ê»ö¼Â(¤Þ¤ÀͽÁÛ¤À¤¬)¤¬Ê¬¤«¤Ã¤¿¤Î¤Ç¡¢¿Þ¤Ë½ñ¤µ¤½¤¦¡£
+
+----------------------------------------------------------------------------
+ 0 2^15=32768
+ +-+---+-------+
+ hash | |pos|... |
+ +-+---+-------+
+ `-hval
+
+ +----+----+--------------------
+ prev | |ppos| . . .
+ +----+----+--------------------
+ `- pos
+
+ * hash ¤Î¼è¤êÆÀ¤ëÃÍ¤Ï pos ¤½¤Î°ÌÃÖ¤Ï hval
+ * ppos ¤Ï°ÊÁ°¤Î pos ¤ò¼¨¤¹¡£prev ¤Ï̵¸ÂĹ¤Î¥Ð¥Ã¥Õ¥¡(ËÜÅö¤Ï´Ä¾õ¥Ð¥Ã¥Õ¥¡)
+----------------------------------------------------------------------------
+
+¤Þ¤À¡¢²òÀϤǤ¤Æ¤Ê¤¤ÊÑ¿ô¤¬»Ä¤Ã¤Æ¤¤¤ë¡£
+
+static int matchlen;
+static unsigned int matchpos;
+static unsigned int remainder;
+
+¤·¤«¤·¤³¤ì¤é¤Ï¤É¤¦¤Ë¤â¥Ñ¥Ã¤È¸«¤Ç¤Ï¤ï¤«¤é¤Ê¤¤¡£½èÍýÆâÍƤòÄɤ¤¤«¤±¤Ê¤¤¤È
+¤À¤á¤½¤¦¤À¡£»ÅÊý¤Ê¤¤¤Î¤ÇÊÑ¿ô̾¤ÇͽÁÛ¤·¤è¤¦¡£(¹¬¤¤Á°¤ÎÊÑ¿ô̾¤È°ã¤Ã¤Æͽ
+ÁÛ¤·¤ä¤¹¤¤)°Ê²¼
+
+----------------------------------------------------------------------------
+ * matchlen °ìÃפ·¤¿Ê¸»úÎóĹ
+ * matchpos °ìÃפ·¤¿¼½ñ¾å¤Î°ÌÃÖ
+ * remainder token ¤Î»Ä¤ê¥µ¥¤¥º
+----------------------------------------------------------------------------
+
+¤Ï¤¿¤·¤Æ¡¢Í½ÁۤϤ¢¤Ã¤Æ¤¤¤ë¤Î¤«¡¢º£¤Ï¤Þ¤Àʬ¤«¤é¤Ê¤¤¡£
+
+slide.c ¤ò¸«¤ë¸Â¤ê¥Ç¡¼¥¿¹½Â¤¤ÏÌÖÍå¤Ç¤¤¿¡£·ë¶Éʬ¤«¤Ã¤¿¤Î¤«Ê¬¤«¤é¤Ê¤¤¤Î
+¤«Îɤ¯Ê¬¤«¤é¤Ê¤¤¤¬¾¯¤·¤º¤Ä¤Ç¤âÁ°¿Ê¤Ï¤·¤Æ¤¤¤ë¤Ï¤º¤À¡£¤³¤³¤Ç¡¢ºÆÅÙ
+encode() ¤Î½èÍý¤òÄɤ¤¤«¤±¤è¤¦¡£º£Å٤ϺÙÉô¤Ë¤âÃåÌܤ¹¤ë¡£
+
+Á°¤Ë¡¢encode() ¤Î¥½¡¼¥¹¤Ë¤Ï (A) ¡Á (H) ¤Þ¤Ç¤Îµ¹æ¤òµ¤·¤¿¡£¤³¤Î½çÈÖ¤Ë
+²òÀϤò¿Ê¤á¤è¤¦¡£
+
+ /* (A) */
+ init_slide();
+
+¤Þ¤¢¡¢½é´ü²½¤Ç¤¢¤ë¡£ÆâÍƤò¸«¤Æ¤ß¤ë¤È
+
+ for (i = 0; i < HSHSIZ; i++) {
+ hash[i] = NIL;
+ too_flag[i] = 0;
+ }
+
+¤À¤±¤Ç¤¢¤ë¡£NIL ¤È¤¤¤¦¤Î¤Ï¡¢0 ¤Ç¤¢¤ë¤È slide.c ¤ÇÄêµÁ¤µ¤ì¤Æ¤¤¤ë¡£ÉáÄÌ
+¤³¤Î¤è¤¦¤Ê½é´üÃͤϡ¢Ä̾ï¤ÎÃͤ¬¼è¤êÆÀ¤Ê¤¤Ãͤò¼¨¤·¤Æ¤¤¤ë¡£NIL ¤¬ 0 ¤Ê¤é
+hash[] ¤Ë³ÊǼ¤µ¤ì¤ë pos ¤Ï 0 ¤Ë¤Ê¤é¤Ê¤¤²ÄǽÀ¤¬¤¢¤ë¡£¤Þ¤¢¡¢Í½ÁۤФ«¤ê
+½ñ¤¤¤Æ¤â»ÅÊý¤Ê¤¤¤Î¤Ç¡¢¤³¤Î´Ø¿ô¤Ï½ª¤í¤¦¡£Í¾Ã̤À¤¬¡¢nil ¤Ï null ¤ÈƱ¤¸¤Ç¡£
+¡Ö¤Ê¤¤¡×¤Î°ÕÌ£¤À¤¬¡¢NULL ¤¬C¸À¸ì¤Ç¤Ï¥Ý¥¤¥ó¥¿¤À¤«¤é¡£Ê̤Υޥ¯¥í̾¤Ë¤·¤¿
+¤Î¤«¤âÃΤì¤Ê¤¤¡£¤¤¤º¤ì¤Ë¤·¤Æ¤â¤³¤ÎÄøÅ٤ϥޥ¯¥í¤Ë¤¹¤ëɬÍפâ¤Ê¤«¤í¤¦¤È¤Ï
+»×¤¦¤Î¤Ï¡¢Í¾·×¤Ê¤ªÀ¤Ï䫤⤷¤ì¤Ê¤¤¡£
+
+ /* (B) */
+ remainder = fread_crc(&text[dicsiz], txtsiz-dicsiz, infile);
+ encoded_origsize = remainder;
+ matchlen = THRESHOLD - 1;
+
+ pos = dicsiz;
+
+ if (matchlen > remainder) matchlen = remainder;
+
+¥Õ¥¡¥¤¥ë¤òÆɤ߹þ¤ß¡¢³ÆÊÑ¿ô¤Î½é´üÃͤòÀßÄꤷ¤Æ¤¤¤ë¡£ÃíÌܤ¹¤Ù¤¤Ï¥Õ¥¡¥¤¥ë
+¤òÆɤ߹þ¤ó¤À¥Ð¥Ã¥Õ¥¡¤Î°ÌÃ֤Ǥ¢¤ë¡£fread_crc() ¤Ï¡¢crcio.c ¤ÇÄêµÁ¤µ¤ì¤¿
+ÈÆÍÑ´Ø¿ô¤Ç¡¢CRCÃͤò·×»»¤·¤¿¤ê´Á»ú¥³¡¼¥ÉÊÑ´¹¤ò¤·¤¿¤ê¤ò½ü¤±¤Ð¡¢fread()
+¤ÈƱ¤¸¤Ç¤¢¤ë¡£¤Ä¤Þ¤ê¡¢¥Õ¥¡¥¤¥ë¤ÏºÇ½é¡¢
+
+ &text[dicsiz] ¤Î°ÌÃ֤ˡ¢txtsiz-dicsiz ʬ¤À¤±Æɤޤì¤ë¡£
+
+¤³¤È¤ò¼¨¤¹¡£¿Þ¼¨¤·¤è¤¦¡£
+
+----------------------------------------------------------------------------
+< ½é´ü¾õÂÖ >
+
+ dicsiz=2^dicbit 2*2^dicbit
+ v v txtsiz
+ +-------------+-------------+-------------+-------------+---+
+ text | | | | | |
+ +-------------+-------------+-------------+-------------+---+
+ `-pos <--->
+ maxmatch{256}
+
+ <------ remainder -------------->
+
+ |--- ¤³¤Î°ÌÃ֤˺ǽé¤Î ---------|
+ ¥Ç¡¼¥¿¤¬Æɤޤì¤Æ¤¤¤ë
+----------------------------------------------------------------------------
+
+¤Þ¤¹¤Þ¤¹¡¢text[] ¤ÎÍÑÅÓ¤¬ÉÔÌÀ¤À¤¬¡¢slide ¼½ñË¡¤Îŵ·¿Åª¤ÊÆɤ߹þ¤ß½èÍý
+¤Î¤³¤È¤ò¹Í¤¨¤ë¤È¤¢¤ëÄøÅÙͽÁÛ¤¬¤Ä¤¯(¤½¤ì¤òÀè¤Ë¼¨¤·¤¿Êý¤¬Îɤ¤¤«¡©)¡£¤Þ¤¢¡¢
+¤³¤³¤Ç¤Ï¥Õ¡¼¥ó¤Ã¤ÈÉ¡¤ÇǼÆÀ¤·¤ÆºÑ¤Þ¤½¤¦¡£
+
+fread_crc() ¤Ï¡¢Æɤ߹þ¤ó¤À¥Ð¥Ã¥Õ¥¡Ä¹¤òÊÖ¤¹¡£remainder ¤¬¤½¤ÎÃͤǡ¢´û¤Ë
+¿Þ¼¨¤·¤Æ¤¢¤ë¡£encoded_origsize ¤Ï¡¢¥½¡¼¥¹¤ò¸«¤ë¤È¡¢¸µ¤Î¥Õ¥¡¥¤¥ë¤Î¥µ¥¤
+¥º¤òɽ¤¹¤¿¤á¤À¤±¤ÎÊÑ¿ô¤Î¤è¤¦¤À¡£°Ê¹ß¤Ï̵»ë¤·¤è¤¦¡£
+
+¤È¤³¤í¤Ç¡¢¥Õ¥¡¥¤¥ë¥µ¥¤¥º¤¬¾®¤µ¤¤¾ì¹ç¿Þ¤ÎÄ̤ê¤Ë¤Ê¤é¤Ê¤¤¤Ã¤È¹Í¤¨¤ë¤«¤âÃÎ
+¤ì¤Ê¤¤¡£¤½¤ÎÄ̤ê¤Ê¤Î¤À¤¬¡¢Îã³°¾ò·ï¤Ï¾¯¤Ê¤¤Êý¤¬¥½¡¼¥¹¤ÏÍý²ò¤·¤ä¤¹¤¤¡£Ã±
+½ã¤Ê¾ì¹ç¤À¤±¤ò¹Í¤¨¤¿Êý¤¬¡¢¤¢¤ì¤³¤ì¹Í¤¨¤ò¤á¤°¤é¤¹É¬Íפ¬¤Ê¤¤¤«¤é¤À¡£¤Ê¤Ë
+¤·¤í´û¤ËÆ°¤¯¥½¡¼¥¹¤ò¸«¤Æ¤¤¤ë¤Î¤À¤«¤é¡¢ºÙ¤«¤¤¤³¤È¤ËÌܤò¤Ä¤Ö¤Ã¤Æ¤â¥¨¥ó¥Ð
+¥°¤¹¤ë¤³¤È¤Ï¤Ê¤¤¤Î¤Ç¤¢¤ë¡£¤½¤¦¤¤¤¦¤ï¤±¤Ç¡¢ÅöÌ̤Ϥ³¤Î¿Þ¤¬Í£°ì¤Î½é´ü¾õÂÖ
+¤Ç¤¢¤ë¤È¹Í¤¨¤ë¡£
+
+(B) ¤ÎÉôʬ¤Ï¤â¤¦¾¯¤·ÃíÌܤ¹¤Ù¤²Õ½ê¤¬¤¢¤ë¡£
+
+ matchlen = THRESHOLD - 1;
+
+matchlen ¤Ï¡¢¡Ö°ìÃפ·¤¿Ê¸»úÎóĹ¡×¤Ç¤¢¤ë¤ÈͽÁÛ¤·¤¿¤¬ THRESHOLD ¤ÎÃÍ¤Ï 3
+(¸ÇÄêÃÍ)¤Ç¤¢¤ë¤«¤é¡¢matchlen ¤Î½é´üÃÍ¤Ï 2 ¤À¡£¤¤¤¤Ê¤êͽÁÛ¤¬¤Ï¤º¤ì¤¿µ¤
+¤¬¤¹¤ë¡£Í½ÁÛ¤òΩ¤Æľ¤½¤¦¡£2 ¤È¤¤¤¦Ææ¤Ê¿ôÃÍ¤È match*len* ¤Ë¤Ä¤¤¤Æ¹Í¤¨¤ë
+¤È¡¢ËÁƬ¤Ç <len, pt> ¤Î¥Ú¥¢¤Î len ¤Ï 2 ¤Ç¤¢¤ë¤³¤È¤Ï¤Ê¤¤¤ÈÀâÌÀ¤·¤¿¡£Ìµ
+°ÕÌ£¤À¤«¤é¤Ç¤¢¤ë¤¬¡¢matchlen ¤Î½é´üÃͤϤ³¤Î 2 ¤È´ØÏ¢¤¹¤ë¤«¤â¤·¤ì¤Ê¤¤¡£
+¤½¤³¤Ç¡¢matchlen ¤ÎÍÑÅÓ¤ò°Ê²¼¤Î¤è¤¦¤ËͽÁÛ¤·¤Ê¤ª¤¹¤³¤È¤Ë¤¹¤ë¡£°Ê²¼¤Î¤è
+¤¦¤Ë¥á¥â¤ò¹¹¿·¤·¤è¤¦¡£THRESHOLD(threshold ¤ÏïçÃͤΰÕ)¤â°ì½ï¤ËͽÁÛ¤·¤¿¡£
+
+----------------------------------------------------------------------------
+* matchlen ºÇÄã¸Â°ìÃפ·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤Ä¹¤µ-1
+* THRESHOLD ºÇÄã¸Â°ìÃפ·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤Ä¹¤µ
+----------------------------------------------------------------------------
+
+¤¦¡¼¤ó¡¢ËÜÅö¤À¤í¤¦¤«¡©
+
+(B) ¤Î»Ä¤ê¤ÎÉôʬ¤òÊÒÉÕ¤±¤è¤¦
+
+ pos = dicsiz;
+
+ if (matchlen > remainder) matchlen = remainder;
+
+pos ¤¬ dicsiz ¤Ç¤¢¤ë¤³¤È¤«¤é¤É¤¦¤ä¤é¡¢pos ¤Ï¡¢text[] ¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤é
+¤·¤¤¡£Á°¤ÎͽÁÛ¤Ç pos ¤Ï¡¢prev[] ¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤Ç¤â¤¢¤ê¡¢hash[] ¤ÎÃͤÇ
+¤â¤¢¤ë¤ÈͽÁÛ¤·¤¿¤Î¤À¤¬(¤³¤ì¤Ï¤â¤Á¤í¤ó´Ö°ã¤¤¤Ç¤Ï¤Ê¤«¤í¤¦¤¬)¡£¤É¤¦¤ä¤é
+ËÜÅö¤Î°ÕÌ£¤Ï¡¢½èÍý¤¹¤ë¥Æ¥¥¹¥È¤ÎÀèƬ¤ò¼¨¤·¤Æ¤¤¤ë¤Î¤Ç¤Ï¤Ê¤¤¤«¤È¤â»×¤¨¤ë¡£
+¤Þ¤¢¡¢¤³¤³¤Ç¤Ï̵Æñ¤Ë¡Ötext[] ¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹(¤Ç¤â¤¢¤ë)¡×¤È¤À¤±Íý²ò¤·¤è¤¦¡£
+´û¤Ë¿Þ¤Ë¤Ï½ñ¤¹þ¤ó¤Ç¤¢¤ë¡£
+
+¼¡¤Î if ¤À¤¬¡¢remainder ¤¬ matchlen ¤è¤ê¤â¾®¤µ¤¤¾ì¹ç¤Î¾ò·ï¤À¡£¤Þ¤¿¡¢
+matchlen ¤ÎͽÁÛ¤¬Ê¤¤µ¤ì¤½¤¦¤Êͽ´¶¤¬¤·¤Ê¤¤¤Ç¤â¤Ê¤¤¤¬¡¢¤³¤Î if ʸ¤Ï*Îã³°
+¾ò·ï*¤Ê¤Î¤Ç̵»ë¤¹¤ë¤³¤È¤Ë¤·¤¿¡£ÅÔ¹ç¤Î°¤¤¤³¤È¤Ï¸«¤Ê¤¤Êý¤¬Îɤ¤¤Î¤À¡£
+
+ /* (C) */
+ hval = ((((text[dicsiz] << 5) ^ text[dicsiz + 1]) << 5)
+ ^ text[dicsiz + 2]) & (unsigned)(HSHSIZ - 1);
+
+(C) ¤Ç¤¢¤ë¡£¤³¤ì¤ÏÆñ²ò¤Ç¤¢¤ë¡£Ê£»¨¤Ê¿ô¼°¤Ï¶ì¼ê¤Ç¤¢¤ë¤¬¡¢¤¸¤Ã¤¯¤ê¹Í¤¨¤è
+¤¦¡£¤Þ¤ºµá¤á¤ëÃÍ¤Ï hval ¤Ç¤¢¤ë¡£¤³¤ì¤Ï hash[] ¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤Ê¤Î¤À¤¬¡¢
+¤³¤Î¤è¤¦¤ÊÊ£»¨¤Ê¼°¤Çµá¤Þ¤ë¥¤¥ó¥Ç¥Ã¥¯¥¹¤Ê¤ó¤ÆÁÛÁü¤â¤Ä¤«¤Ê¤¤¡£¤Þ¤º¡¢ºÇ½é
+¤Î¥¤¥ó¥¹¥Ô¥ì¡¼¥·¥ç¥ó¤òÂç»ö¤Ë¤¹¤ë¤³¤È¤Ë¤·¤è¤¦¡£ËÁƬ¤Ç¡¢(C) ¤Î½èÍý¤Ï¡Ö¥Ï¥Ã
+¥·¥åÃÍ hval ¤ò·×»»¤¹¤ë¡£¡×¤Ã¤È¶ì¤â¤Ê¤¯Í½ÁÛ¤·¤¿¡£¤½¤·¤Æ¤³¤ì¤Ï´Ö°ã¤¤¤Ç¤Ï
+¤Ê¤¤¤À¤í¤¦(¤¤Ã¤È)¡£hash[] ¤È¤Î´ØÏ¢¤ò¤³¤³¤Ç¹Í¤¨¤Æ¤â¤ï¤«¤é¤Ê¤¤¤«¤é¡¢¤³
+¤Î¥Ï¥Ã¥·¥åÃͤη׻»¤À¤±¤ò¹Í¤¨¤ë¤³¤È¤Ë¤·¤è¤¦¡£
+
+¼°¤ò¤¸¤Ã¤¯¤ê¸«¤Æ¤ß¤ë¡£¡£¡£¤¸¤Ã¤¯¤ê¸«¤Æ¤ß¤ë¤È°Ê²¼¤Î¤³¤È¤¬¤ï¤«¤ë¡£
+
+ x(i) = text[dicsiz + i]
+¤È¤¹¤ë¤È
+ hval = ((x(0) << 5) ^ (x(1) << 5) ^ (x(2) << 0))
+ & (unsigned)(HSHSIZ - 1);
+
+¤Ç¤¢¤ë¡£ºÇ¸å¤Î & (unsigned)(HSHSIZ - 1) ¤Ï¡¢Á°¤Ë¤â»÷¤¿¤è¤¦¤Ê¼°¤¬½Ð¤¿¤¬
+¤³¤ì¤Ï¤¢¤ëÈϰϤοôÃÍ(¤³¤³¤Ç¤Ï¡¢0 ¡Á HSHSIZ{2^15}-1)¤òÃê½Ð¤¹¤ë¤¿¤á¤Î¥Ó¥Ã
+¥È¥Þ¥¹¥¯¤Ç¤¢¤ë¡£¥Ï¥Ã¥·¥å´Ø¿ô¤È¸À¤¦¤Î¤Ï¤¢¤ëÉä¹æ¤ò¤¢¤ë½¸¹ç¤ÎÉä¹æ¤Ë¼ÌÁü¤¹
+¤ë´Ø¿ô¤Ç¤¢¤ë¤«¤é¤³¤Î¤è¤¦¤Ê¥Ó¥Ã¥È¥Þ¥¹¥¯¤ÏÅöÁ³É¬ÍפÀ¤·¡¢Îɤ¯¹Ô¤ï¤ì¤ë»ö¤À
+(ÉáÄÌ¤Ï mod ÁÇ¿ô¤ò¹Ô¤¦¤ó¤À¤±¤É)¡£¤Þ¤¿¡¢hval ¤Ï¡¢hash[] ¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹
+¤Ê¤Î¤À¤«¤é¡¢¼ÌÁü¤¹¤ë½¸¹ç¤È¤Ï hash[] ¤Î¥¤¥ó¥Ç¥Ã¥¯¥¹¤À¡£¤ª¤Ã¡¢°Æ³°´Êñ¤Ë
+¤ï¤«¤Ã¤¿¡£x(i) ¤¬ text[dicsiz + i] ¤Ç¡¢¥Ï¥Ã¥·¥å´Ø¿ô¤ÎÊÑ¿ô¤Ï x(0),
+x(1), x(2) ¤À¤«¤é¡¢ÀèƬ¤Î 3 ¥Ð¥¤¥È¤Îʸ»úÎó(ʿʸ)¤Î¥Ï¥Ã¥·¥åÃͤòµá¤á¤Æ¤¤
+¤ë¤ï¤±¤À¡£¤½¤Î¾¤Î·×»»(<< 5 ¤È¤« ^ ¤È¤«) ¤ÏÂ礷¤¿¤³¤È¤Ç¤Ï¤Ê¤¤¡£Ìµ»ë¤·
+¤è¤¦¡£¤Þ¤¿¡¢Â³¤±¤Æ (D) ¤Î½èÍý¤â¸«¤ë¤¬¡¢
+
+ /* (D) */
+ insert();
+
+insert() ¤Ï¡¢¹¬¤¤²òÆɤº¤ß¤Ç¤¢¤ë pos ¤ò hash[] ¤Ë³ÊǼ¤¹¤ë½èÍý¤À¡£
+ͽÁÛ¤ÎÃʳ¬¤Ç¤Ï¡¢(C) ¤È (D) ¤òÊ̸ĤνèÍý¤È¹Í¤¨¤Æ¤¤¤¿¤Î¤À¤¬¤³¤ì¤Ï
+¤É¤¦¤ä¤é¥»¥Ã¥È¤Ç¤¢¤ë¡£
+
+ (C) pos ¤Î°ÌÃ֤Π3 ʸ»ú¤Î¥Ï¥Ã¥·¥åÃͤò·×»»¤·
+ (D) hash[¥Ï¥Ã¥·¥åÃÍ] = pos ¤ò¹Ô¤¦
+
+¤â¤¦¾¯¤·Ãí°Õ¿¼¤¯¸¡Æ¤¤¹¤ë¤È¡Öpos¤Î°ÌÃÖ¤Î3ʸ»ú¡×¤È¡¢µá¤á¤¿¡Ö¥Ï¥Ã¥·¥åÃÍ¡×
+¤ÏÏÀÍýŪ¤Ë¤Ï = ¤Ç¤¢¤ë¡£
+
+¤Ä¤Þ¤ê¡¢(C) (D) ¤Î½èÍý¤Ï
+
+ hash[ʸ»úÎó] = °ÌÃÖ
+
+¤È¤¤¤¦½èÍý¤ò¹Ô¤Ã¤Æ¤¤¤ë¡£¥Ï¥Ã¥·¥åÃͤξ×ÆͤϤ³¤³¤Ç¤Ï¹Í¤¨¤Ê¤¤¡£slide ¼½ñ
+Ë¡¤Ç¤Ï¡¢¤¢¤ëʸ»úÎó¤ËÂФ·°ÊÁ°¤½¤Îʸ»úÎ󤬸½¤ì¤¿¤«¤É¤¦¤«¤ò¸¡º÷¤·¡¢¤½¤Î°Ì
+ÃÖ¤òµá¤á¤ëɬÍפ¬¤¢¤ë¤Î¤À¤¬¡¢¤³¤ÎºÇ½é¤Î 3 ʸ»ú¤Ë´Ø¤·¤Æ¤Ï¸½»þÅÀ¤Ç¤½¤ÎÍÑ
+·ï(°ÌÃÖ¤òµá¤á¤ë)¤òËþ¤¿¤¹»ö¤¬¤Ç¤¤Æ¤¤¤ë¡£¤³¤³¤Þ¤Ç¤Ç¼«¤º¤È encode() ¤ÎÁ´
+ÂÎÁü¤âͽÁÛ¤¬¤Ä¤¤½¤¦¤Êµ¤¤¬¤¹¤ë¡£
+
+# ¾×ÆͤϹͤ¨¤Ê¤¤¤Ã¤È¤·¤¿¤¬ prev[pos] ¤Ë°ÊÁ°¤Î¥Ï¥Ã¥·¥åÃͤ¬³ÊǼ¤µ¤ì¤Æ¤¤
+# ¤ë¤³¤È¤«¤é´Êñ¤Ë¤ï¤«¤ë¡£¥Á¥§¡¼¥óË¡¤À¡£Ææ¤ÏÁ´¤Æ²ò¤±¤¿¡£
+
+# ¤½¤ì¤Ë¤Ä¤±¤Æ¤â¡¢(C) ¤È (D) ¤ÎÉôʬ¤ò¸«¤ë¤À¤±¤Ç¤â¤³¤Î¥½¡¼¥¹¤¬¤Á¤ç¤Ã¤È
+# ±ø¤¤¤³¤È¤¬¤ï¤«¤ë¡£¤â¤¦¾¯¤·¡¢°ú¿ô¤È¤«Ìá¤êÃͤȤ«¹Í¤¨¤Æ¤¯¤ì¤Æ¤âÎɤ«¤Ã
+# ¤¿¤Ï¤º¤À¡£¥Ï¥Ã¥·¥å´Ø¿ô¤Ë¤·¤Æ¤â¾¯¤Ê¤¯¤È¤â¥Þ¥¯¥í¤°¤é¤¤¤Ë¤Ï¤·¤è¤¦¤è¡£
+
+(E) ¡Á (H) ¤Ë°Ü¤í¤¦¤³¤ì¤Ï¥ë¡¼¥×¤ÎÃæ¿È¤Ç¡¢½èÍý¤ÎËÜÂê¤À¡£¤Þ¤º¥ë¡¼¥×¤Îæ
+½Ð¾ò·ï¤ò¸«¤Æ¤ß¤ë¤È
+
+ while (remainder > 0 && ! unpackable) {
+
+remainder ¤Ï¡¢¥Ð¥Ã¥Õ¥¡¾å¤ËÆɤ߹þ¤ó¤Àʿʸ¤ÎŤµ¤Ç¤¢¤ë¤«¤é¤³¤ì¤¬¤Ê¤¯¤Ê¤ë
+¤Þ¤Ç¥ë¡¼¥×¤¹¤ë¤³¤È¤Ë¤Ê¤ë¡£¤µ¤é¤Ë unpackable ¤È¤¤¤¦¤Î¤Ï¡¢crcio.c ¤Î
+putcode() ¤Ç¤½¤ÎÃͤòÀßÄꤷ¤Æ¤¤¤ë²Õ½ê¤¬½Ð¤ÆÍè¤ë¤Î¤À¤¬¡¢Éä¹æ²½¤·¤¿½ÐÎÏ¥µ
+¥¤¥º¤¬¸µ¤Î¥µ¥¤¥º¤ò±Û¤¨¤¿¤È¤¤Ë¿¿¤Ë¤Ê¤ë¡£¤Ä¤Þ¤ê¡¢¤³¤ì°Ê¾å½èÍý¤·¤Æ¤â°µ½Ì
+¤Î°ÕÌ£¤¬¤Ê¤¤¤È¤ï¤«¤Ã¤¿¤é¥ë¡¼¥×¤òÈ´¤±¤ë¤ï¤±¤À¡£
+
+¤Ç¤Ï¡¢(E)¤ò¸«¤è¤¦¡£
+
+ /* (E) */
+ lastmatchlen = matchlen; lastmatchoffset = pos - matchpos - 1;
+ --matchlen;
+
+¤Á¤ç¤Ã¤È¸«¤¿¤À¤±¤Ç¤Ï¤ä¤Ï¤ê¤ï¤«¤é¤Ê¤¤¡£¤³¤ì¤é¤ÎÊÑ¿ô¤Ï¤Þ¤ÀͽÁÛ¤·¤«¤·¤Æ¤Ê
+¤¤¤«¤é¤Ç¤¢¤ë¡£¤¬¡¢¤ï¤«¤ë¤À¤±¤Î¾ðÊó¤Ï½ñ¤¤·¤ë¤½¤¦¡£
+
+----------------------------------------------------------------------------
+lastmatchlen °ÊÁ°¤Î matchlen ¤ÎÃÍ (ÊÑ¿ô̾¤«¤é)
+lastmatchoffset °ÊÁ°¥Þ¥Ã¥Á¤·¤¿°ÌÃÖ (ÊÑ¿ô̾¤«¤é)
+----------------------------------------------------------------------------
+
+°ÊÁ°¤ÎÃͤòlast¡Á¤ËÂàÈò¤·¡¢¿·¤¿¤ÊÃͤòÀßÄꤹ¤ë½àÈ÷¤ò¤·¤Æ¤¤¤ë¤ï¤±¤À¡£¤½¤·
+¤Æ¡¢¡Ö¿·¤¿¤ÊÃͤÎÀßÄê¡×¤Ï¡¢--matchlen ¤ÇÁ᮹Ԥï¤ì¤Æ¤¤¤ë¡£¤·¤«¤·¡¢¡Ö¥Þ¥Ã
+¥Á¤·¤¿Ä¹¤µ¡×¤ò¤Þ¤À²¿¤â¤·¤Æ¤Ê¤¤¤Î¤Ë -1 ¤¹¤ë¤È¤¤¤¦¤Î¤Ï¤¤¤Ã¤¿¤¤¤É¤¦¤¤¤¦¤³
+¤È¤À¤í¤¦¡© matchlen ¤Ï¥ë¡¼¥×¤ÎƬ¤Ç 2 ¤ËÀßÄꤵ¤ì¤Æ¤¤¤ë¡£¤³¤ì¤¬ 1 ¤Ë¤Ê¤Ã
+¤¿¡£ËÜÅö¤Î½é´üÃÍ¤Ï 1 ¤Ê¤Î¤«¡©
+
+----------------------------------------------------------------------------
+< ³ÆÊÑ¿ô¤Î½é´üÃÍ >
+
+ matchlen = 1
+ matchpos = 0
+ pos = dicsiz
+
+ lastmatchlen = 2
+ lastmatchoffset = dicsiz - 1 (pos - matchpos - 1)
+----------------------------------------------------------------------------
+
+¤³¤Î (E) ¤Ï¤Þ¤¿¸å¤Ç¸«¤ë»ö¤Ë¤Ê¤ë¤À¤í¤¦¡£
+
+(F) (G) ¤Ç¤¢¤ë¡£¤Þ¤¿¡¢¤½¤Îľ¸å¤Ë¤Ï°ÊÁ°¤Ë¤â¸«¤¿¶³¦¾ò·ï¤¬¤¢¤ë¡£
+
+ /* (F) */ /* (G) */
+ get_next(); match_insert();
+ if (matchlen > remainder) matchlen = remainder;
+
+if ʸ ¤Ï̵»ë¤·¤Æ´Ø¿ô¤ÎÃæ¿È¤À¤±¤òÄɤ¤¤«¤±¤Æ¤ß¤è¤¦¡£¤Þ¤º¡¢get_next() ¤³
+¤ì¤Ï ¼¡¤Î token ¤ò¼è¤Ã¤Æ¤¯¤ë½èÍý¤À¤ÈͽÁÛ¤·¤Æ¤¢¤ë¡£¤Ï¤¿¤·¤Æ¤É¤¦¤À¤í¤¦¤«¡©
+
+static void get_next()
+{
+ remainder--;
+ if (++pos >= txtsiz - maxmatch) {
+ update();
+ }
+ hval = ((hval << 5) ^ text[pos + 2]) & (unsigned)(HSHSIZ - 1);
+}
+
+remainder ¤ò¾ÃÈñ¤·¡¢pos ¤ò¿Ê¤á¤Æ¤¤¤ë¡£Í½ÁÛÄ̤ê¤À¡£¤Ò¤È¤Þ¤º if ¤Î¾ò·ï¤Ï
+̵»ë¤¹¤ë¤Èľ¸å¤Ç hash Ãͤòµá¤áľ¤·¤Æ¤¤¤ë¡£¤³¤Î¥Ï¥Ã¥·¥å´Ø¿ô¤Ï¡¢°ÊÁ°¤Î¥Ï¥Ã
+¥·¥åÃͤòÍøÍѤ·¤Æ¤¤¤ë¤¬¡¢¤³¤ì¤Ï pos ¤¬°ÊÁ°¤è¤ê + 1 ¤µ¤ì¤Æ¤¤¤ë¤³¤È¤ò¹Í¤¨
+¤ë¤È´ØÏ¢¤¬¸«¤¨¤ÆÍè¤ë¡£°ÊÁ°¤Îhash´Ø¿ô¤ò pos ¤Î´Ø¿ô¤È¤·¤Æ½ñ¤Ä¾¤¹¤È
+
+ x(pos+i) = text[pos + i]
+
+ hval(pos) = (x(pos+0) << 5) ^ (x(pos+1) << 5) ^ (x(pos+2) << 0)
+ & (unsigned)(HSHSIZ - 1);
+
+¤Ç¤¢¤ê¡¢¤Þ¤¿¡¢º£Å٤Υϥå·¥å´Ø¿ô¤Ï¡¢
+
+ hval(pos+1) = (hval(pos) << 5) ^ (x(pos+1 + 2) << 0)
+ & (unsigned)(HSHSIZ - 1);
+
+¤À¡¢ÈË»¨¤Ê¤Î¤Ç & (HSHSIZE-1) ¤ò³°¤¹¤È¡¢(µ¤¤ò¤¤«¤·¤Æ << 0 ¤È¤¤¤¦¤Î¤â½ñ
+¤¤¤Æ¤¤¤¿¤¬¤É¤¦¤ä¤é°ÕÌ£¤¬¤Ê¤¤¤Î¤Ç³°¤·¤¿)
+
+ hval(pos+1) = (x(pos+0) << 5)
+ ^ (x(pos+1) << 5)
+ ^ x(pos+2)
+ ^ x(pos+3)
+
+¤Ã¤È¤Ê¤ë¡£¤³¤Î¼¡ get_next() ¤¬¸Æ¤Ó½Ð¤µ¤ì¤ì¤Ð¡¢
+
+ hval(pos+2) = (x(pos+0) << 5)
+ ^ (x(pos+1) << 5)
+ ^ x(pos+2)
+ ^ x(pos+3)
+ ^ x(pos+4)
+
+¤Ç¤¢¤ë¡£½ç¤Ë¥Ï¥Ã¥·¥åÃͤòµá¤á¤ëʸ»úÎóŤòÁý¤ä¤·¤Æ¤¤¤ë¡£¤È¤Ë¤«¤¯¡¢
+get_next() ¤Ï¡¢pos ¤ò¿Ê¤á¡¢remainder ¤ò½Ì¤á¡¢¿·¤¿¤Ê(°ÊÁ°¤è¤ê1ʸ»úŤ¤)
+ʸ»úÎó¤Î¥Ï¥Ã¥·¥åÃÍ hval ¤òµá¤á¤ë´Ø¿ô¤Î¤è¤¦¤À¡£
+
+¤·¤«¤·¡¢¤¤¤Ä¤Þ¤Ç¤â hash Ãͤθµ¤È¤Ê¤ëʸ»úÎó¤ò¿¤Ð¤·¤Æ¤â¤·¤ç¤¦¤¬¤Ê¤¤¤À¤í
+¤¦¡£hval ¤Ï¤É¤³¤«¤Ç¤Þ¤¿¥ê¥»¥Ã¥È¤µ¤ì¤ë¤Ï¤º¤À¡£¤Ã¤È»×¤Ã¤Æ¥½¡¼¥¹¤òõ¤·¤Æ
+¤ß¤¿¤¬¤½¤Î¤è¤¦¤Ê²Õ½ê¤Ï¸«Åö¤¿¤é¤Ê¤¤¡£¤Ê¤¼¤À¤í¤¦¡©¹Í¤¨¤Æ¤ß¤ë¡¦¡¦¡¦¹Í¤¨¤Æ
+¤ß¤¿¤¬¤ï¤«¤é¤Ê¤«¤Ã¤¿¡£»ÅÊý¤Ê¤¤¤Î¤Ç¸å¤Ë¤·¤è¤¦¡£
+
+¤È¤³¤í¤Ç¡¢Á°²ó¡¢hval ¤Î·×»»¤Èinsert() ¤Ï¥»¥Ã¥È¤À¤È¸À¤Ã¤¿¡£º£²ó¤Ï¤É¤¦¤À
+¤í¤¦¡©¼¡¤Î match_insert() ¤ò¸«¤Æ¤ß¤ë¡£
+
+/* ¸½ºß¤Îʸ»úÎó¤ÈºÇĹ°ìÃפ¹¤ëʸ»úÎó¤ò¸¡º÷¤·¡¢¥Á¥§¡¼¥ó¤ËÄɲ乤ë */
+
+static void match_insert()
+{
+ ... ¾Êά ...
+
+ prev[pos & (dicsiz - 1)] = hash[hval];
+ hash[hval] = pos;
+}
+
+¡¦¡¦¡¦¶¯Å¨¤Ç¤¢¤Ã¤¿¡£¶¯Å¨¤¹¤®¤¿¤Î¤Çƨ¤²¤Æ¡¢ºÇ¸å¤Î2 ¹Ô¤À¤±¤ËÃåÌܤ·¤¿¡£¤³
+¤ì¤Ï¡¢insert()¤ÈƱ¤¸¤À¡£Í½ÁÛ¤ÏÅö¤¿¤Ã¤Æ¤¤¤ë¡£get_next() ¤Ç hval ¤ò¹¹¿·
+¤·¤¿¸å¤Ï¡¢¤³¤Î match_insert() ¤Ç¡¢prev[] ¤È hash[] ¤ò¹¹¿·¤¹¤ë¤ï¤±¤À¡£
+¤½¤·¤Æ¡¢match_insert() ¤Î¾Êά¤·¤¿Éôʬ¤Ï¡¢¤É¤¦¤ä¤é matchpos, matchlen,
+too_flag ¤ò¹¹¿·¤·¤Æ¤¤¤ë¤À¤±¤Î¤è¤¦¤À¡£¤³¤ì¤¬ËÜÅö¤Ê¤é match_insert()¤Ç¡¢
+insert()¤Î½èÍý¤ò¤»¤º¡¢´Ø¿ô¤òʬ¤±¤ë¤«¤·¤¿Êý¤¬Îɤµ¤½¤¦¤À¡£(¿¿µ¶¤ÎÄø¤Ï¾Ü
+ºÙ¤ò¸«¤Æ¤«¤é¤Ë¤Ê¤ë)
+
+¤ª¤â¤à¤í¤Ë¸å³¤Î½èÍý (H) ¤ò¸«¤ë¤È¡¢
+
+ /* (H) */
+ if (matchlen > lastmatchlen || lastmatchlen < THRESHOLD) {
+
+¤³¤ì¤¬¿¿¤Ê¤é¡Ö¸«¤Ä¤«¤é¤Ê¤«¤Ã¤¿¾õÂ֡פÈͽÁÛ¤·¤¿(¤Ê¤¼¤À¤í¡©)¡£¤½¤·¤Æ¡¢
+lastmatchlen ¤Ï½é´ü¾õÂÖ¤Ç¤Ï 2 ¤Ç¤¢¤ë¡£Í½ÁÛ¤·¤¿¾ò·ï¤ÏµÕ¤«¡© matchlen ¤Þ
+¤ï¤ê¤ÏͽÁۤФ«¤ê¤Ç¿Ê¤á¤¹¤®¤¿¡£¤½¤·¤Æ¤É¤¦¤ä¤é match_insert() ¤òÆɤߤȤ«
+¤Ê¤±¤ì¤Ð¤³¤ÎÀè¤âʬ¤«¤é¤º¤¸¤Þ¤¤¤Ë¤Ê¤ê¤½¤¦¤À¡£
+
+¤³¤Î¤Þ¤Þ match_insert() ¤ò¾ÜºÙ¤Ë²òÀϤ¹¤ë»ö¤Ë¤·¤è¤¦¡£
OSDN Git Service
