The Hacking of LHa for UNIX (1st draft)
-------------------------------------------
- 2003-01-05 Koji Arai <mailto:jca02266@nifty.ne.jp>
+$Id$
+ Koji Arai <mailto:jca02266@nifty.ne.jp>
Ëܽñ¤Ï¡¢LHa for UNIX 1.14i ¤Î¥½¡¼¥¹¤ò²òÆɤ·¡¢¤½¤Î°µ½Ì¥¢¥ë¥´¥ê¥º¥à¤Î¼Â
Áõ¤ò³Îǧ¤¹¤ë¤¿¤á¤Î¤â¤Î¤À¡£¤³¤ÎÀ®²Ì¤ÏÊ̤ηÁ¤Ç¤Þ¤È¤á¤Ê¤ª¤µ¤ì»ñÎÁ¤Ë¤Ê¤ë¤«
·ï(°ÌÃÖ¤òµá¤á¤ë)¤òËþ¤¿¤¹»ö¤¬¤Ç¤¤Æ¤¤¤ë¡£¤³¤³¤Þ¤Ç¤Ç¼«¤º¤È encode() ¤ÎÁ´
ÂÎÁü¤âͽÁÛ¤¬¤Ä¤¤½¤¦¤Êµ¤¤¬¤¹¤ë¡£
-# ¾×ÆͤϹͤ¨¤Ê¤¤¤Ã¤È¤·¤¿¤¬ prev[pos] ¤Ë°ÊÁ°¤Î¥Ï¥Ã¥·¥åÃͤ¬³ÊǼ¤µ¤ì¤Æ¤¤
-# ¤ë¤³¤È¤«¤é´Êñ¤Ë¤ï¤«¤ë¡£¥Á¥§¡¼¥óË¡¤À¡£Ææ¤ÏÁ´¤Æ²ò¤±¤¿¡£
+¾×ÆͤϹͤ¨¤Ê¤¤¤Ã¤È¤·¤¿¤¬¡¢¤Á¤ç¤Ã¤È¹Í¤¨¤¿¤é¤¹¤°¤ï¤«¤Ã¤¿¡£prev[] ¤Ë¤Ï¡¢
+°ÊÁ°¤Î¥Ï¥Ã¥·¥åÃͤǵá¤á¤¿Ê¸»úÎó¤Î°ÌÃÖ¤¬Æþ¤Ã¤Æ¤¤¤ë¡£¤Ä¤Þ¤ê¡¢prev[] ¤Ï¥Ï¥Ã
+¥·¥å¤¬¾×Æͤ·¤¿¤È¤¤Î¤¿¤á¤Î¥Ð¥Ã¥Õ¥¡¤À¡£¤³¤Î¥Ï¥Ã¥·¥å¤Ï¥Á¥§¡¼¥óÊý¤À¡£
+
+Î㤨¤Ð¡¢insert() ¤Ç¡¢
+ prev[pos] = hash[hval];
+ hash[hval] = pos;
+¤Ã¤È½èÍý¤ò¤·¤Æ¤¤¤ë¤Î¤À¤«¤é
+
+ hash[hval] = pos1
+ |
+ v
+ prev[pos1] = pos2
+ |
+ v
+ prev[pos2] = pos3
+ ...
+
+¤È¤¤¤Ã¤¿Ãͤ¬Æþ¤ë»ö¤Ë¤Ê¤ë¡£¤¢¤ëʸ»úÎó(¤Î¥Ï¥Ã¥·¥åÃÍ) hval ¤ËÂФ·¤Æ¡¢¤½¤Î
+¼½ñ¾å¤Î°ÌÃÖ¤Ï pos1, pos2, pos3 ¤È¤¤¤¦¸õÊ䤬¤¢¤ë¤ï¤±¤À¡£¼ÂºÝ¤Ë¤É¤Î pos
+¤òÁª¤Ö¤«¤ÏÈæ³Ó¤Ë¤è¤Ã¤Æ¹Ô¤ï¤ì¤ë¤Î¤À¤í¤¦¡£
# ¤½¤ì¤Ë¤Ä¤±¤Æ¤â¡¢(C) ¤È (D) ¤ÎÉôʬ¤ò¸«¤ë¤À¤±¤Ç¤â¤³¤Î¥½¡¼¥¹¤¬¤Á¤ç¤Ã¤È
# ±ø¤¤¤³¤È¤¬¤ï¤«¤ë¡£¤â¤¦¾¯¤·¡¢°ú¿ô¤È¤«Ìá¤êÃͤȤ«¹Í¤¨¤Æ¤¯¤ì¤Æ¤âÎɤ«¤Ã
¤¤¤«¤é¤Ç¤¢¤ë¡£¤¬¡¢¤ï¤«¤ë¤À¤±¤Î¾ðÊó¤Ï½ñ¤¤·¤ë¤½¤¦¡£
----------------------------------------------------------------------------
-lastmatchlen °ÊÁ°¤Î matchlen ¤ÎÃÍ (ÊÑ¿ô̾¤«¤é)
-lastmatchoffset °ÊÁ°¥Þ¥Ã¥Á¤·¤¿°ÌÃÖ (ÊÑ¿ô̾¤«¤é)
+* lastmatchlen °ÊÁ°¤Î matchlen ¤ÎÃÍ (ÊÑ¿ô̾¤«¤é)
+* lastmatchoffset °ÊÁ°¥Þ¥Ã¥Á¤·¤¿°ÌÃÖ (ÊÑ¿ô̾¤«¤é)
----------------------------------------------------------------------------
°ÊÁ°¤ÎÃͤòlast¡Á¤ËÂàÈò¤·¡¢¿·¤¿¤ÊÃͤòÀßÄꤹ¤ë½àÈ÷¤ò¤·¤Æ¤¤¤ë¤ï¤±¤À¡£¤½¤·
¤È¤³¤í¤Ç¡¢Á°²ó¡¢hval ¤Î·×»»¤Èinsert() ¤Ï¥»¥Ã¥È¤À¤È¸À¤Ã¤¿¡£º£²ó¤Ï¤É¤¦¤À
¤í¤¦¡©¼¡¤Î match_insert() ¤ò¸«¤Æ¤ß¤ë¡£
-/* ¸½ºß¤Îʸ»úÎó¤ÈºÇĹ°ìÃפ¹¤ëʸ»úÎó¤ò¸¡º÷¤·¡¢¥Á¥§¡¼¥ó¤ËÄɲ乤ë */
-
static void match_insert()
{
... ¾Êά ...
¤ï¤ê¤ÏͽÁۤФ«¤ê¤Ç¿Ê¤á¤¹¤®¤¿¡£¤½¤·¤Æ¤É¤¦¤ä¤é match_insert() ¤òÆɤߤȤ«
¤Ê¤±¤ì¤Ð¤³¤ÎÀè¤âʬ¤«¤é¤º¤¸¤Þ¤¤¤Ë¤Ê¤ê¤½¤¦¤À¡£
-¤³¤Î¤Þ¤Þ match_insert() ¤ò¾ÜºÙ¤Ë²òÀϤ¹¤ë»ö¤Ë¤·¤è¤¦¡£
+¤³¤Î¤Þ¤Þ match_insert() ¤ò¾ÜºÙ¤Ë²òÀϤ¹¤ë»ö¤Ë¤·¤è¤¦¡£match_insert()
+¤ò¤¹¤Ù¤ÆºÆ·Ç¤¹¤ë¡£
+
+/* ¸½ºß¤Îʸ»úÎó¤ÈºÇĹ°ìÃפ¹¤ëʸ»úÎó¤ò¸¡º÷¤·¡¢¥Á¥§¡¼¥ó¤ËÄɲ乤ë */
+
+static void match_insert()
+{
+ unsigned int scan_pos, scan_end, len;
+ unsigned char *a, *b;
+ unsigned int chain, off, h, max;
+
+ max = maxmatch; /* MAXMATCH; */
+ if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
+ matchpos = pos;
+
+ off = 0;
+ for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
+ h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
+ }
+ if (off == maxmatch - THRESHOLD) off = 0;
+ for (;;) {
+ chain = 0;
+ scan_pos = hash[h];
+ scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
+ while (scan_pos > scan_end) {
+ chain++;
+
+ if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
+ {
+ a = text + scan_pos - off; b = text + pos;
+ for (len = 0; len < max && *a++ == *b++; len++);
+ }
+
+ if (len > matchlen) {
+ matchpos = scan_pos - off;
+ if ((matchlen = len) == max) {
+ break;
+ }
+ }
+ }
+ scan_pos = prev[scan_pos & (dicsiz - 1)];
+ }
+
+ if (chain >= LIMIT)
+ too_flag[h] = 1;
+
+ if (matchlen > off + 2 || off == 0)
+ break;
+ max = off + 2;
+ off = 0;
+ h = hval;
+ }
+ prev[pos & (dicsiz - 1)] = hash[hval];
+ hash[hval] = pos;
+}
+
+¤Þ¤º¡¢½é´ü²½Éôʬ¤ÎÁ°È¾
+
+ max = maxmatch; /* MAXMATCH; */
+ if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
+ matchpos = pos;
+
+ off = 0;
+
+maxmatch ¤Ï¡¢¸ÇÄêÃÍ¤Ç 256 ¤À¡¢¤À¤«¤é max ¤â 256
+2¹ÔÌܤΠif ʸ¤Ï¡¢¤³¤ì¤Þ¤Ç¤·¤Ä¤³¤¤¤¯¤é¤¤¤Ë½Ð¤ÆÍ褿¾ò·ï¤Ë»÷¤Æ¤¤¤ë¤¬¡¢º£
+²ó¤Ï¾ò·ï¤òËþ¤¿¤¹¤é¤·¤¤¡£¤³¤ì¤Þ¤Ç¤Ï¡¢
+
+ if (matchlen > remainder) matchlen = remainder;
+
+¤È¤¤¤¦¾ò·ï¤À¤Ã¤¿¡£¤½¤·¤Æº£²ó¤Ï¡¢
+
+ if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
+
+¤À¤«¤é¡¢Á´ÂÎŪ¤Ë matchlen ¤ÎÃͤϡ¢
+
+ THRESHOLD-1 <= matchlen <= remainder
+
+¤Ä¤Þ¤ê¡¢
+
+ 2 <= matchlen <= ¥Ð¥Ã¥Õ¥¡¤Ë»Ä¤Ã¤¿¥Æ¥¥¹¥ÈĹ
+
+¤ÎÈϰϤËǼ¤á¤é¤ì¤ë¤è¤¦¤À¡£¤³¤³¤Ç¤Ï¡¢matchlen ¤Ï²¼¸ÂÃͤò²¼²ó¤ë¤Î¤Ç2 ¤Ë
+ÀßÄꤵ¤ì¤ë¡£¼¡¤Ë matchpos, off ¤¬½é´ü²½¤µ¤ì¡£°Ê²¼¤Î¿Þ¤Î¾õÂ֤ˤʤ롣
+(pos, remainder ¤Ï¡¢get_next() ¤Ç¹¹¿·¤µ¤ì¤Æ¤¤¤ë¤³¤È¤ËÃí°Õ)
+
+----------------------------------------------------------------------------
+
+ dicsiz=2^dicbit 2*2^dicbit
+ v v txtsiz
+ +-------------+-------------+-------------+-------------+---+
+ text | | | | | |
+ +-------------+-------------+-------------+-------------+---+
+ `-pos(=dicsiz+1) <--->
+ matchpos(=pos) maxmatch{256}
+ off(=0)
+
+ <------ remainder ------------>
+
+ |--- ¤³¤Î°ÌÃ֤˺ǽé¤Î ---------|
+ ¥Ç¡¼¥¿¤¬Æɤޤì¤Æ¤¤¤ë
+----------------------------------------------------------------------------
+
+½é´ü²½Éôʬ¤Î¸åȾ
+
+ for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
+ h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
+ }
+ if (off == maxmatch - THRESHOLD) off = 0;
+
+h ¤Ï¡¢too_flag[] ¤¬º£¤Î¤È¤³¤í¤¹¤Ù¤Æ0¤À¤«¤é hval ¤À¡£(too_flag ¤Ï¡¢h ¤Ä
+¤Þ¤ê hval ¤ò¥¤¥ó¥Ç¥Ã¥¯¥¹¤Ë¼è¤ë¤é¤·¤¤¡£hash[] ¤ÈƱ¤¸¤À¡£ºÆ·Ç¤Ï¤·¤Ê¤¤¤¬
+¥á¥â¤Ë½ñ¤²Ã¤¨¤Æ¤ª¤³¤¦)
+
+off ¤Ï¡¢pos ¤Î°ÌÃÖ¤«¤é¤Î¥ª¥Õ¥»¥Ã¥È¤Î¤è¤¦¤À(h ¤ò¹¹¿·¤¹¤ë for ʸ¤ÎÃæ¿È¤«
+¤é)¡£¿Þ¤â¤½¤Î°ÌÃ֤˽ñ¤¤¤¿¡£ºÇ¸å¤Î if ʸ¤Ï off ¤¬¾å¸Â¤Ë㤷¤¿¾ì¹ç¤Ë0 ¤Ë
+ºÆ½é´ü²½¤·¤Æ¤¤¤ë¡£¤è¤¯¤ï¤«¤é¤Ê¤¤¤Î¤Ç̵»ë¤·¤è¤¦¡£for ʸ¤ÎÃæ¿È¤«¤éh ¤ä
+off ¤ÎÍÑÅӤϤɤ¦¤âÀèÆɤߤ·¤¿¥Ï¥Ã¥·¥åÃͤȤ½¤ÎÀèÆɤߤΰÌÃ֤ʤΤǤϤʤ¤¤«
+¤ÈÁÛÁü¤¹¤ë¡£too_flag[] ¤Î¾õÂ֤ˤè¤Ã¤ÆÀèÆɤߤ¹¤Ù¤Ãͤ¬ÊѤï¤ë¤Î¤À¤í¤¦¤«¡©
+
+¤È¤Ë¤«¤¯½èÍý¤ÎËÜÂê¤ËÆþ¤ë»ö¤Ë¤·¤è¤¦¡£¤Þ¤º¡¢¤³¤Î´Ø¿ô¤Ë¸½¤ì¤ë¶É½êÊÑ¿ô¤òÎó
+µó¤·¤Æ¤ª¤³¤¦
+
+ unsigned int scan_pos, scan_end, len;
+ unsigned char *a, *b;
+ unsigned int chain, off, h, max;
+
+¤È¤ê¤¢¤¨¤º¡¢off, h, max ¤Ï¤¹¤Ç¤Ë½Ð¤ÆÍ褿¤Î¤Ç»Ä¤ê¤Ï
+
+ scan_pos, scan_end, len, a, b, chain
+
+¤À¡¢¤³¤ì¤À¤±¤ÎÊÑ¿ô¤Î°ÕÌ£¤ò²òÆɤ·¤Ê¤¯¤Æ¤Ï¤Ê¤é¤Ê¤¤¡£ÊÑ¿ô¤Ï¾õÂÖ¤òɽ¤¹¤«¤é¡¢
+¤½¤Î¿ô¤¬Â¿¤¤¤È¸À¤¦¤Î¤Ï¤½¤ì¤À¤±Ê£»¨¤Ê½èÍý¤À¤È¤¤¤¦¤³¤È¤À¡£¤á¤²¤ë¡£
+
+¤³¤Î´Ø¿ô¤Î¥á¥¤¥ó¤È¤Ê¤ë¥ë¡¼¥×¤ÎÃæ¤ò¤¶¤Ã¤Èį¤á¤Æ¤ß¤ë¤µ¤é¤ËÆâÉô¤Ë¥ë¡¼¥×¤¬
+¤¢¤ë¡£¤Ò¤È¤Þ¤º¡¢Æó½Å¥ë¡¼¥×¤ÎÃæ¿È¤ò¾Êά¤·¤è¤¦¡£
+
+ for (;;) {
+ chain = 0;
+ scan_pos = hash[h];
+ scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
+
+ while (scan_pos > scan_end) {
+ chain++;
+ ... ά ...
+ }
+
+ if (chain >= LIMIT)
+ too_flag[h] = 1;
+
+ if (matchlen > off + 2 || off == 0)
+ break;
+ max = off + 2;
+ off = 0;
+ h = hval;
+ }
+
+¤Þ¤º¡¢Á°È¾Éôʬ¤«¤é
+
+ chain = 0;
+ scan_pos = hash[h];
+ scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
+
+chain, scan_pos, scan_end ¤Ï¤¹¤Ù¤Æ while ¥ë¡¼¥×¤ËÅϤµ¤ì¤ë¤Ù¤ÊÑ¿ô¤À¡£
+¤µ¤é¤Ë¡¢while ¤Î¸å¤Ë¤Ï¡¢scan_pos, scan_end ¤Ï¸½¤ì¤Ê¤¤¤«¤é(²¾¤Ë while
+¥ë¡¼¥×¤¬1¤Ä¤Î´Ø¿ô¤À¤Ã¤¿¤È¤¹¤ë¤È)¤³¤ì¤é¤Ï while ¥ë¡¼¥×Éô¤Î°ú¿ô(ÆþÎÏ)¤À¡£
+¤³¤Î2¤Ä¤ÎÊÑ¿ô¤Ï¤É¤¦¤ä¤ê¤¯¤ê¤·¤è¤¦¤È¤â¡¢while ¥ë¡¼¥×ÉôÆâ¤Î¾õÂÖ¤·¤«É½¤µ
+¤Ê¤¤¤Î¤Ç¡¢¤³¤³¤Ç¤Ï̵»ë¤·¤è¤¦¡£
+
+while ¥ë¡¼¥×¤Î¸å¤ò¸«¤Æ¤ß¤ë¤È
+
+ if (chain >= LIMIT)
+ too_flag[h] = 1;
+
+ if (matchlen > off + 2 || off == 0)
+ break;
+ max = off + 2;
+ off = 0;
+ h = hval;
+
+chain ¤¬ LIMIT¤ò±Û¤¨¤¿¾ì¹ç¡¢too_flag[h] = 1 ¤È¤·¤Æ¤¤¤ë¡£chain ¤Ï¡¢¤¶¤Ã
+¤È¸«¤Æ¡¢while ¥ë¡¼¥×¤Î¥«¥¦¥ó¥¿¤é¤·¤¤¤¬¡¢LIMIT ¤Ï 0x100 ¤À¡£¤É¤¦¤Ë¤âÎã
+³°¾ò·ï¤Ã¤Ý¤¤(LIMIT¤È¤¤¤¦Ì¾Á°¤ä¿ôÃͤ¬¤½¤¦»×¤ï¤»¤ë)¤Î¤Ç¤³¤³¤Ç¤Ï̵»ë¤·¤è
+¤¦¡£while ¥ë¡¼¥×¤¬ 256°Ê¾å²ó¤ë²ÄǽÀ¤¬¤¢¤ëÅÀ¤À¤±¿´¤Ë¤È¤É¤á¤Æ¤ª¤³¤¦¡£
+
+¼¡¤Î¾ò·ï¤Ç¤Ï¡¢matchlen ¤È off ¤¬¾ò·ïȽÃǤµ¤ì¤Æ¤¤¤ë¡£¤È¤¤¤¦¤³¤È¤Ï¤³¤Î¤É
+¤Á¤é¤«¡¢¤¢¤ë¤¤¤ÏξÊý¤Ï while ¥ë¡¼¥×¤ÎÊÖ¤êÃÍ(½ÐÎÏ)¤À¡£¤¶¤Ã¤È
+match_insert()Á´ÂΤò¸«¤Æ¤ß¤ë¤È off ¤ÏºÇ½é¤È¤³¤Îľ¸å¤Ç¤·¤«¹¹¿·¤µ¤ì¤Ê¤¤
+¤é¤·¤¤¡£¤Ä¤Þ¤ê¡¢while ¥ë¡¼¥×Éô¤ÎÊÖ¤êÃͤÏmatchlen ¤ÎÊý¤À¡£
+¤³¤Î¾ò·ï¤Ï for () ¥ë¡¼¥×¤Îæ½Ð¾ò·ï¤Ç¤â¤¢¤ë¡£¿´¤Ë¤È¤É¤á¤Æ¡¢¼¡¤Ë¿Ê¤à¡£
+
+ max = off + 2;
+ off = 0;
+ h = hval;
+
+¤Õ¤à¡£¤è¤¯¤ï¤«¤é¤Ê¤¤¡£¤·¤«¤·ÃíÌܤ¹¤Ù¤ÅÀ¤Ï¤¢¤ë¡£off ¤Ï¤³¤³¤Ç¡¢0 ¤Ë¤Ê¤ë
+¤¬¤³¤ì°Ê¹ß¤Ï off ¤ÎÃͤÏÊѤï¤é¤Ê¤¤¡£¤Ä¤Þ¤ê¡¢off ¤ÏºÇ½é¤Ï²¿¤é¤«¤ÎÃͤÇ
+while ¥ë¡¼¥×Éô¤ËÅϤµ¤ì¤ë¤¬¡¢¤½¤Î¼¡¤«¤é¤Ï¡¢0 ¤À¡£¤³¤Î for ¥ë¡¼¥×¤¬²¿ÅÙ
+²ó¤í¤¦¤È¤â 0 ¤À¡£h ¤âƱ¤¸¤ÇºÇ½é¤Ï²¿¤é¤«¤ÎÃͤò»ý¤Ä¤¬¡¢2²óÌܤΥ롼¥×°Ê¹ß¡¢
+h ¤Ï hval ¤À¡£max ¤Ï¡¢off ¤ò 0 ¤Ë¤¹¤ëľÁ°¤Ë¹¹¿·¤·¤Æ¤¤¤ë¤«¤é¡¢h ¤ä off
+¤È»ö¤Ê¤ê¡¢3¤Ä¤Î¾õÂÖ¤ò»ý¤Ä¡¢¤¹¤Ê¤ï¤Á¡£maxmatch, off+2, 2 ¤À¡£
+
+¤¤¤ä¡¢Ã¦½Ð¾ò·ï¤ò¸«¤Æ¤ß¤ë¤È off == 0 ¤Ê¤é break ¤È¤¢¤ë¡£¤Ä¤Þ¤ê¡¢¤³¤Î
+for ¥ë¡¼¥×¤Ï¤É¤ó¤Ê¤Ë´èÄ¥¤Ã¤Æ¤â2²ó¤·¤«²ó¤é¤Ê¤¤¤é¤·¤¤¡£¤ä¤Ã¤Ñ¤ê max ¤â 2
+¤Ä¤Î¾õÂÖ¤·¤«»ý¤¿¤Ê¤¤¤è¤¦¤À¡£
+
+¤³¤ì¤Ç¡¢1 ²óÌÜ¡¢2²óÌÜ¤Ë while ¥ë¡¼¥×Éô¤ËÆþ¤ëľÁ°¤Î¾õÂÖ¤¬½ñ¤±¤ë¡£¤³¤Î´Ø
+¿ô match_insert() ¤Ï¡¢while ¥ë¡¼¥×Éô¤ò1²ó¤«2²ó¼Â¹Ô¤¹¤ë½èÍý¤È¸À¤¦¤ï¤±¤À¡£
+
+¤³¤³¤Ç̵»ë¤·¤Æ¤¤¤¿¡£while ¥ë¡¼¥×Éô¤ÎÆþÎϤȤʤë scan_pos, scan_end
+¤â¤½¤ì¤¾¤ì¤É¤Î¤è¤¦¤Ê¾õÂ֤ˤʤ뤫½ñ¤¤¤Æ¤ª¤¯
+
+----------------------------------------------------------------------------
+< 1²óÌÜ >
+ h = ²¿¤«
+ off = ²¿¤«
+ max = maxmatch
+
+ scan_pos = hash[h]
+ scan_end = pos + off - dicsiz (¤¢¤ë¤¤¤Ï¡¢off)
+
+ matchlen = 2
+ matchpos = pos
+< 2²óÌÜ >
+ h = hval
+ off = 0
+ max = Á°¤Î off + 2
+
+ scan_pos = hash[hval]
+ scan_end = pos - dicsiz (¤¢¤ë¤¤¤Ï¡¢0)
+
+ matchlen = ?
+ matchpos = ?
+----------------------------------------------------------------------------
+
+¾åµ¤Ï°ìÈ̲½¤·¤¿¾ì¹ç¤À¤¬¡¢º£²ó(½é²ó)¤Î¾ì¹ç¡¢h ¤ä off ¤ÎÃͤϡ¢hval ¤Ç¤¢
+¤ê¡¢0 ¤À¤Ã¤¿¡£2²óÌܥ롼¥×¤Î¤È¤¤Î¾õÂÖ¤ÈƱ¤¸¤Ç¤¢¤ë¡£2²ó¤Î¥ë¡¼¥×¤Î°ã¤¤¤Ï
+max ¤ÎÃͤ¬matchpos ¤Ç¤¢¤ë¤« off+2 (¤¹¤Ê¤ï¤Á2)¤Ç¤¢¤ë¤«¤Î°ã¤¤¤·¤«¤Ê¤¤¤è¤¦¤À¡£
+
+¤³¤³¤Ï¡¢¾ò·ï¤ò¾¯¤Ê¤¯¤¹¤ë¤¿¤á¤Ë¤³¤Î¾ì¹ç¤À¤±¤Ë¤·¤Ü¤Ã¤Æ½èÍý¤ò¹Í¤¨¤è¤¦¡£
+while ¥ë¡¼¥×¤Î2²ó¤Î¸Æ¤Ó½Ð¤·¤ò¹Ô¤¦ºÝ¤Î¾õÂ֤ϰʲ¼¤ÎÄ̤ê¤Ë½ñ¤Ä¾¤»¤ë¡£
+
+----------------------------------------------------------------------------
+< 1²óÌÜ >
+ h = hval
+ off = 0
+ max = maxmatch
+
+ scan_pos = hash[hval]
+ scan_end = pos - dicsiz (¤¢¤ë¤¤¤Ï¡¢0)
+
+ matchlen = 2
+ matchpos = pos
+< 2²óÌÜ >
+ h = hval
+ off = 0
+ max = 2
+
+ scan_pos = hash[hval]
+ scan_end = pos - dicsiz (¤¢¤ë¤¤¤Ï¡¢0)
+
+ matchlen = ?
+ matchpos = ?
+----------------------------------------------------------------------------
+
+¤¦¡¼¤ó¡¢¤Þ¤À¡¢¤¹¤Ã¤¤ê¤·¤Ê¤¤¡£²¿¤¬¤¹¤Ã¤¤ê¤·¤Ê¤¤¤«¤È¤¤¤¦¤È scan_end ¤Î
+ÃͤÀ¡£¤³¤ì¤¬²¿¤ò°ÕÌ£¤¹¤ë¤Î¤«¤¬¤è¤¯¤ï¤«¤é¤Ê¤¤¡£scan_pos ¤Ï¡¢¤ï¤«¤ë¤Î¤«¡©
+¤È¤¤¤¦¤È¡¢¤ï¤«¤ë¡£hash[hval]¤À¤«¤é¸½ºß¤Îʸ»úÎó¤ÈƱ¤¸Ê¸»úÎó¤Î¼½ñ¾å¤Î°Ì
+ÃÖ¤À¡£¤µ¤é¤Ë¡¢¸½»þÅÀ¤Ç¤Ï get_next() ¤Ç¡¢hval ¤ò¹¹¿·¤·¤Æ¤«¤é insert()
+¤ò¹Ô¤Ã¤Æ¤¤¤Ê¤¤¤Î¤Ç¡¢hash[hval] ¤Ë¤Ï²¿¤âÆþ¤Ã¤Æ¤¤¤Ê¤¤¡£¤¹¤Ê¤ï¤Á 0 ¤À¡£
+
+ scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
+
+¤ò¹Í¤¨¤è¤¦¡£off ¤Ï¡¢0 ¤À¤«¤é
+
+ scan_end = (pos > dicsiz) ? pos - dicsiz : 0;
+
+¤Ê¤ï¤±¤À¡£¤µ¤é¤Ë¡¢pos¤Ï¸½»þÅÀ¤Ç dicbit+1 ¤Ç¤¢¤ë¤«¤é¡¢1 ¤À¡£¿Þ¤Ë½ñ¤³¤¦¡£
+
+----------------------------------------------------------------------------
+
+ dicsiz=2^dicbit 2*2^dicbit
+ v v txtsiz
+ +-------------+-------------+-------------+-------------+---+
+ text | | | | | |
+ +-------------+-------------+-------------+-------------+---+
+ ^ ^ `-pos(=dicsiz+1)
+ | |
+ | scan_end ¤Ï¤³¤ÎÊÕ(1)
+ scan_pos ¤Ï¤³¤ÎÊÕ(0)
+
+ h = hval
+ off = 0
+ max = 2
+
+----------------------------------------------------------------------------
+
+¤Ä¤¤¤Ë¡¢text[] ¥Ð¥Ã¥Õ¥¡¤Îº¸È¾Ê¬¤Ë»Ø¤·¤«¤«¤ë¡£¤³¤ì¤¬²¿¤Ê¤Î¤«¤Ï¸½»þÅÀ¤Ç
+¤ÏÌÀ³Î¤Ë½ñ¤¤¤Æ¤Ê¤«¤Ã¤¿¤¬Í½ÁÛ¤¹¤ë¤È¤³¤Îº¸È¾Ê¬¤Ï¥º¥Ð¥ê¼½ñ¤À¡£¸À¤¤ÀڤäÆ
+¤ä¤í¤¦¡£º£¤Þ¤Ç¼½ñ¤é¤·¤¤(dicsiz¤Î¥µ¥¤¥º¤ò»ý¤Ä)¥Ð¥Ã¥Õ¥¡¤Ï hash[] ¤ä
+prev[] ¤¬¤¢¤Ã¤¿¤¬¡¢hash[], prev[] ¤ÎÍÑÅӤϤ⤦ÌÀ³Î¤Ç¤¢¤ë¡£¼½ñ¤È¤Ê¤êÆÀ
+¤ë¥Ð¥Ã¥Õ¥¡¤Ï¤â¤¦¤³¤Î text[] ¤·¤«¤Ê¤¤¤Î¤À¡£
+
+¤µ¤é¤Ë¡¢º¸È¾Ê¬¤Ë¸Â¤é¤º¤³¤Î text[] Á´ÂΤ¬¼½ñ¤Ç¤¢¤í¤¦¤ÈͽÁÛ¤¹¤ë¡£¤³¤ì¤Ï
+¤¿¤À¤Î´ª¤À¤¬ text[] ¤Ï´Ä¾õ¥Ð¥Ã¥Õ¥¡¤Ê¤Î¤Ç¤Ï¤Ê¤«¤í¤¦¤«¤È¹Í¤¨¤Æ¤¤¤ë¡£
+
+# ºÇ½é¤ÎÊý¤Ç prev[] ¤¬¼½ñ¤À¤ÈͽÁÛ¤·¤¿¤¬´Ö°ã¤Ã¤¿Í½ÁÛ¤ò¤·¤Æ¤¤¤¿¤³¤È¤Ë¤³
+# ¤Î»þÅÀ¤Çµ¤¤Å¤¤¤¿¡£prev[] ¤¬¼½ñ¤ÈƱ¤¸¥µ¥¤¥º¤ò»ý¤ÄÍýͳ¤Ï¤Þ¤À¤è¤¯¤ï¤«
+# ¤é¤Ê¤¤¡£
+
+¤³¤Î»þÅÀ¤Ç¤Ï¤Þ¤À scan_pos ¤ä scan_end ¤Î¿¿¤Î°ÕÌ£¤Ï¤ï¤«¤é¤Ê¤¤¡£off ¤Î¤³
+¤È¤ò̵»ë¤·¤Æ¤¤¤ë¤«¤éͽÁÛ¤âΩ¤Á¤Ë¤¯¤¤¤¬¡¢¤Ò¤È¤Þ¤º½é´ü¾õÂÖ¤¬¤É¤¦¤¤¤Ã¤¿¤â
+¤Î¤«¤Ï¤ï¤«¤Ã¤¿¤Î¤Ç¤³¤Î¤Þ¤Þ¡¢while ¥ë¡¼¥×Éô¤ò¸«¤Æ¤ß¤¿¤¤¤È»×¤¦¡£
+
+ while (scan_pos > scan_end) {
+ chain++;
+
+ if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
+ {
+ a = text + scan_pos - off; b = text + pos;
+ for (len = 0; len < max && *a++ == *b++; len++);
+ }
+
+ if (len > matchlen) {
+ matchpos = scan_pos - off;
+ if ((matchlen = len) == max) {
+ break;
+ }
+ }
+ }
+ scan_pos = prev[scan_pos & (dicsiz - 1)];
+ }
+
+¤Þ¤º¡¢if ʸ¤Î¾ò·ï¤òËþ¤¿¤µ¤Ê¤¤¾ì¹ç¤À¤±¤ò¹Í¤¨¤ë¡£
+
+ while (scan_pos > scan_end) {
+ chain++;
+
+ if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
+ ...
+ }
+ scan_pos = prev[scan_pos & (dicsiz - 1)];
+ }
+
+
+off¤Ï 0 ¤Ê¤Î¤Ç¡¢text[scan_pos + matchlen] != text[pos + matchlen] ¤È¤¤¤¦¾ò·ï¤Î¾ì¹ç¤òÁÛÄꤹ¤ë¤ï¤±¤À¤¬¡¢
+
+text[scan_pos + matchlen]
+
+¤È
+
+text[pos + matchlen]
+
+¤òÈæ¤Ù¤Æ¤¤¤ë
+
+text[scan_pos] ¼½ñ¾å¤Îʸ»úÎó¤Î*ÀèƬ*
+text[pos] ¸½ºß¤Îʸ»úÎó¤Î*ÀèƬ*
+
+¤òÈæ¤Ù¤Ê¤¤¤Î¤Ï matchlen ¤¬Á°¤ËͽÁÛ¤·¤¿¡ÖºÇÄã¸Â°ìÃפ·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤Ä¹¤µ-1¡×
+¤À¤«¤é¤Ç¤¢¤í¤¦¡£¸½»þÅÀ¤Ç¡¢matchlen ¤¬ 2 ¤À¤«¤é
+
+text[scan_pos + 0] == text[pos + 0]
+text[scan_pos + 1] == text[pos + 1]
+
+¤Ç¤¢¤Ã¤¿¤È¤·¤Æ¤â¡¢
+
+text[scan_pos + 2] != text[pos + 2]
+
+¤Ç¤¢¤ì¤Ð¡¢¡ÖºÇÄã¸Â°ìÃפ·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤Ä¹¤µ¡×¤È¤¤¤¦¾ò·ï¤òËþ¤¿¤µ¤Ê¤¤¤Î
+¤Ç¤¢¤ë¡£¤Ê¤Î¤Ç matchlen ¤Î°ÌÃÖ¤«¤éÀè¤ËÈæ³Ó¤·¤Æ̵Â̤ÊÈæ³Ó¤ò¤·¤Ê¤¤¤è¤¦¤Ë
+¤·¤Æ¤¤¤ë¡£¸å¤Ç¤Á¤ã¤ó¤È¤·¤¿Èæ³Ó¤Î½èÍý¤¬½Ð¤ÆÍè¤ë¤À¤í¤¦¡£¤³¤Î¤è¤¦¤Ê½èÍý¤Ï
+½èÍý¤È¤·¤Æ¤Ï¸úΨ¤¬Îɤ¤¤Î¤À¤¬¡¢¤³¤È¥½¡¼¥¹Íý²ò¤È¸À¤¦ÅÀ¤Ç¤Ï¾éŤǤ¢¤ë¡£¤ï
+¤«¤ê¤Ë¤¯¤¤¤Î¤À¡£»ÅÊý¤Ê¤¤¤Î¤À¤±¤É¡£
+
+# matchlen ¤Î°ÕÌ£¤ÎͽÁۤϤɤ¦¤ä¤éÅö¤¿¤Ã¤Æ¤¤¤ë¤è¤¦¤À¡£matchlen ¤ÏºÇû°ì
+# Ã×Ĺ¤Ç¡¢minmatchlen ¤Ã¤È̾ÉÕ¤±¤Æ¤âÎɤµ¤½¤¦¤ÊÊÑ¿ô¤À¡£
+
+¤½¤·¤Æ¡¢Èæ³Ó¤Ë¼ºÇÔ¤·¤¿¤é scan_pos ¤ò¹¹¿·¤¹¤ë¡£
+
+ scan_pos = prev[scan_pos & (dicsiz - 1)];
+
+¥Ï¥Ã¥·¥å¤Î¥Á¥§¡¼¥ó¤ò¤¿¤É¤Ã¤Æ¤¤¤ë¡¢¤Ä¤Þ¤ê¼¡¤Î¸õÊä¤ò¼½ñ¤«¤é¼è¤ê½Ð¤·¤Æ¤¤
+¤ë¤ï¤±¤À¡£¤³¤³¤Þ¤Ç¤Ç¡¢while ¥ë¡¼¥×¤Î½èÍýÆâÍƤÎÁÛÁü¤Ï¤Ä¤¤¤¿¡£¤³¤Î¥ë¡¼¥×
+¤Ï¼½ñ¤«¤é(ºÇĹ)°ìÃפ¹¤ëʸ»úÎó¤òõ¤·¤Æ¤¤¤ë¤Î¤À¤í¤¦¡£
+
+½çÈÖ¤¬Á°¸å¤·¤¿¤¬¡¢while ¥ë¡¼¥×¤Îæ½Ð¾ò·ï¤ò¸«¤Æ¤ß¤ë
+
+ while (scan_pos > scan_end) {
+
+¤³¤ì¤Ï¤É¤¦¤¤¤¦¤³¤È¤À¤í¤¦¡© scan_pos ¤Ï¡¢¥Ï¥Ã¥·¥å¤Î¥Á¥§¡¼¥ó¤ò¤¿¤É¤Ã¤ÆƱ
+¤¸¥Ï¥Ã¥·¥åÃͤò»ý¤Äʸ»úÎó¤Î°ÌÃÖ¤òõ¤¹¡¢¤³¤ÎÃͤϤÀ¤ó¤À¤ó¤È¾®¤µ¤¯¤Ê¤Ã¤Æ¹Ô
+¤¯¤â¤Î¤Ê¤Î¤À¤í¤¦¤«¡©
+¤½¤ÎÄ̤ê¤Ç¤¢¤ë¡£hash[] ¤Ø¤Î³ÊǼ¤Ï¥Õ¥¡¥¤¥ë¤«¤é¼è¤Ã¤ÆÍ褿ʸ»úÎó¤ò½ç¤Ë³Ê
+Ǽ¤·¤Æ¹Ô¤¯¤Î¤Ç¥Á¥§¡¼¥ó¤Î±ü¤Ë¤Ï¡¢¤è¤êÁ°¤ÎÊý¤Î°ÌÃÖ¤¬½ñ¤«¤ì¤Æ¤¤¤ë¤Ï¤º¤À¡£
+µÕ¤Ë¥Á¥§¡¼¥ó¤ÎÀõ¤¤Éôʬ¤Ë¤Ï¤è¤ê¸½ºß°ÌÃ֤˶ᤤ¡¢°ÌÃÖ¤¬½ñ¤«¤ì¤Æ¤¤¤ë¤Î¤À¤í
+¤¦¡£¤Ç¤Ï¡¢¤½¤Î¶³¦ scan_end ¤Ï¤É¤¦¤ä¤Ã¤Æ¤ï¤«¤ë¤Î¤À¤í¤¦¤«¡©¤³¤ì¤Ï¸å¤Ç¤Þ
+¤¿¸¡¾Ú¤·¤è¤¦¡£
+
+¤Ç¤Ï¡¢½èÍý¤ÎËܼÁ if ʸ¤ÎÃæ¤ò¸«¤ë»ö¤Ë¤·¤è¤¦
+
+ if (text[scan_pos + matchlen - off] == text[pos + matchlen]) {
+ {
+ a = text + scan_pos - off; b = text + pos;
+ for (len = 0; len < max && *a++ == *b++; len++);
+ }
+
+ if (len > matchlen) {
+ matchpos = scan_pos - off;
+ if ((matchlen = len) == max) {
+ break;
+ }
+ }
+ }
+
+ºÇ½é¤Î°ÕÌ£¤â¤Ê¤¯¥Ö¥í¥Ã¥¯¤Ë¤Ê¤Ã¤Æ¤¤¤ëÉôʬ¤ò¸«¤ë¡¢
+
+ {
+ a = text + scan_pos - off; b = text + pos;
+ for (len = 0; len < max && *a++ == *b++; len++);
+ }
+
+¤³¤Î½èÍý¤Ç¤Ï a, b ¤È¤¤¤¦¤¤¤«¤Ë¤â¶É½ê¤Ê̾Á°¤ÎÊÑ¿ô¤¬»È¤ï¤ì¤Æ¤¤¤ë¡£¤³¤ì¤Ï¡¢
+ËÜÅö¤Ë¤³¤Î¥Ö¥í¥Ã¥¯Æâ¤Ë¤Ç¶É½êŪ¤Ê¤â¤Î¤Î¤è¤¦¤À¡£¤Ê¤é¤ÐÄêµÁ°ÌÃ֤⤳¤Î¥Ö¥í¥Ã
+¥¯Æâ¤Ë¤·¤ÆËÜÅö¤Ë¶É½êŪ¤Ë¤·¤ÆÍߤ·¤«¤Ã¤¿¡£
+
+¤µ¤é¤Ë¡¢¤³¤Î½èÍý¤Ïñ¤Ëʸ»úÎó a, b ¤òÈæ³Ó¤·¤Æ¤¤¤ë¤À¤±¤Î¤è¤¦¤À¡£memcmp()
+¤Ç¤Ï¤Þ¤º¤¤¤Î¤«¤È¸À¤¦¤È¤³¤³¤Çµá¤á¤Æ¤¤¤ë¤â¤Î¤¬¡Ö¤É¤³¤Þ¤Ç°ìÃפ·¤¿¤«(len)¡×
+¤Î¤è¤¦¤Ê¤Î¤Ç¡¢memcmp() ¤Ç¤ÏÌòÉÔ¤À¡£»ÅÊý¤Ê¤¤¤Î¤Ç´Ø¿ô¤ò¤Ç¤Ã¤Á¤¢¤²¤ÆÃê
+¾Ý²½¤ò¤Ï¤«¤í¤¦¡£memcmp_ret_len()(²æ¤Ê¤¬¤éÊѤÊ̾Á°¤À)¤È¤¤¤¦´Ø¿ô¤¬¤¢¤Ã¤¿
+¤È¤¹¤ë¤È¤³¤ÎÉôʬ¤Ï
+ len = memcmp_ret_len(&text[scan_pos-off], &text[pos], max);
+
+¤Ã¤È¤Ê¤ë¡£ÊÖ¤êÃͤϰìÃפ·¤¿Ê¸»úÎóŤÀ¡£
+
+¤½¤Î¼¡¤Î½èÍý¡¢
+
+ if (len > matchlen) {
+ matchpos = scan_pos - off;
+ if ((matchlen = len) == max) {
+ break;
+ }
+ }
+
+¤Ç¡¢matchlen (ºÇÄã°ìÃ×Ĺ)¤è¤êÂ礤¤¾ì¹ç¤Ë¾ò·ï¤òËþ¤¿¤¹¡£¾ò·ï¤òËþ¤¿¤µ¤Ê
+¤±¤ì¤Ð¡¢scan_pos ¤ò¹¹¿·¤¹¤ëʬ¤±¤À¤¬¡¢¤³¤Î if ¤Î³°Â¦¤Î if ¤ÈƱ¤¸¾ò·ïȽ
+ÃǤò¹Ô¤Ã¤Æ¤¤¤ë¡£³°Â¦¤Î if ¤Ïñ¤Ë¸úΨ¤Î¤¿¤á¤Î¾éĹ¤Ê½èÍý¤À¤Ã¤¿¤Î¤ÏÁ°¤Ë¤â
+½ñ¤¤¤¿¤È¤ª¤ê¤À¡£º£¹¹¤À¤¬¡¢³°Â¦¤Î if ¤Ï¥½¡¼¥¹²òÀϤȸÀ¤¦ÅÀ¤Ç¤Ï̵»ë¤·¤Æ¤â
+Îɤ¤¤â¤Î¤À¤Ã¤¿¡£¤µ¤Æ¡¢¤È¤Ë¤«¤¯¤³¤Î if ʸ¤ò¸«¤Æ¤ß¤è¤¦¡£¤Þ¤ººÇû°ìÃ׍Î
+°ìÃ×¾ò·ï¤òËþ¤¿¤·¤¿¾ì¹ç¡¢matchpos ¤È matchlen ¤ò¹¹¿·¤¹¤ë¡£
+
+matchpos ¤Ï¥Þ¥Ã¥Á¤·¤¿°ÌÃÖ¡¢
+matchlen ¤Ï¥Þ¥Ã¥Á¤·¤¿Ä¹¤µ
+
+¤Ç¡¢matchlen ¤¬ max ¤Ê¤éºÇĹ°ìÃ׍Ë㤷¤Æ¤¤¤ë¤Î¤Ç¡¢¤³¤ì°Ê¾åõº÷¤Ï¤·¤Ê
+¤¤¡£matchlen ¤ÏºÇû°ìÃ׍Ǥ¢¤ê¤Ê¤¬¤é¡¢°ìÃ×Ĺ¤Ç¤â¤¢¤ëÊÑ¿ô¤Î¤è¤¦¤À¡£
+(¤É¤¦¤ä¤é°ÊÁ°¤Î2¤Ä¤ÎͽÁۤϤɤÁ¤é¤âÅö¤¿¤Ã¤Æ¤¤¤¿ÌÏÍÍ)
+
+¤È¤Ë¤«¤¯ while ¥ë¡¼¥×Éô¤Î½ÐÎϤϡ¢¤³¤Î matchpos ¤È matchlen ¤Î¤è¤¦¤À¡£
+Á°¤Ë½ñ¤¤¤¿Ä̤ꤳ¤Î¥ë¡¼¥×¤Ï¡ÖºÇĹ°ìÃ×ʸ»úÎó¤òµá¤á¤ë½èÍý¡×¤À¡£
+
+match_insert() ¤ÎÁ´ÂΤò¤â¤¦°ìÅÙ¸«¤Æ¤ß¤è¤¦¡£¤¿¤À¤·¡¢°Ê²¼¤Î½ñ¤´¹¤¨¤ò¹Ô¤¦¡£
+
+o while ¥ë¡¼¥×Éô¤Ï search_dict(pos, scan_pos, scan_end, max) ¤È¤¤¤¦´Ø¿ô
+ ¤ËÃÖ¤´¹¤¨¤¿¤â¤Î¤È¤¹¤ë¡£
+
+o ËöÈø¤Î insert() ¤ÈƱÅù¤Î½èÍý¤ò¹Ô¤Ã¤Æ¤¤¤ëÉôʬ¤â insert() ¤Î¸Æ¤Ó½Ð¤·¤Ë
+ ¤¹¤êÂؤ¨¤è¤¦¡£(match_insert() ´Ø¿ô¤ÎÃæ¤Ç insert() ½èÍý¤òËÜÅö¤Ë¹Ô¤¦¤Ù
+ ¤¤â¤Î¤Ê¤Î¤«¤É¤¦¤«¤¬µ¿Ìä¤À¤¬)
+
+o chain ¤È¤¤¤¦ÊÑ¿ô¤Ë¤«¤«¤ï¤ë½èÍý¤â±£¤·¤¿(search_dictÆâ¤Ç¹Ô¤¦)
+
+static void match_insert()
+{
+ unsigned int off, h, max;
+
+ max = maxmatch; /* MAXMATCH; */
+ if (matchlen < THRESHOLD - 1) matchlen = THRESHOLD - 1;
+ matchpos = pos;
+
+ off = 0;
+ for (h = hval; too_flag[h] && off < maxmatch - THRESHOLD; ) {
+ h = ((h << 5) ^ text[pos + (++off) + 2]) & (unsigned)(HSHSIZ - 1);
+ }
+ if (off == maxmatch - THRESHOLD) off = 0;
+ for (;;) {
+ unsigned int scan_end;
+
+ scan_end = (pos > dicsiz) ? pos + off - dicsiz : off;
+
+ search_dict(pos, hash[h], scan_end, max);
+
+ if (matchlen > off + 2 || off == 0)
+ break;
+ max = off + 2;
+ off = 0;
+ h = hval;
+ }
+
+ insert();
+}
+
+¤À¤¤¤Ö¤¹¤Ã¤¤ê¤·¤¿¡£¤Þ¤À¡¢off ¤Ë¤«¤«¤ï¤ëÉôʬ¤¬¤è¤¯Ê¬¤«¤é¤Ê¤¤¤¬¡¢¤Ò¤È¤Þ
+¤ºÎɤ¤¤À¤í¤¦¡£¤³¤Î´Ø¿ô¤Î²òÀϤϤ³¤ì¤Ç½ª¤Ã¤ÆÎɤ¤¤À¤í¤¦¤«¡£
+
+¤¤¤ä¡¢Îɤ¯¤Ê¤¤¡£´Î¿´¤Î match_insert() ¤Î½ÐÎϤ¬¤è¤¯¤ï¤«¤é¤Ê¤¤¡£¤³¤Î´Ø¿ô
+¤Ï¡ÖºÇĹ°ìÃ×ʸ»úÎó¤òõ¤·¡¢hash ¤ò¹¹¿·¤¹¤ë½èÍý¡×(¤¯¤É¤¤¤è¤¦¤À¤¬¡¢hash¤ò
+¹¹¿·¤¹¤ë¤Ï;·×¤Ë»×¤¦)¤Ê¤Î¤À¤í¤¦¤¬¡¢ºÇĹ°ìÃ×ʸ»úÎ󤬸«¤Ä¤«¤é¤Ê¤«¤Ã¤¿¤È
+¤¤¤¦¤Î¤Ï¤É¤¦È½ÃǤµ¤ì¤ë¤Î¤À¤í¤¦¡©
+
+¤Þ¤º¡¢search_dict() ¤Ç¸«¤Ä¤«¤é¤Ê¤«¤Ã¤¿¾ì¹ç¡¢matchlen, matchpos ¤Ï¹¹¿·
+¤µ¤ì¤Ê¤¤¡£¤½¤·¤Æ¡¢¤ª¤½¤é¤¯ 2 ÅÙÌܤΠfor ¥ë¡¼¥×¤¬¹Ô¤ï¤ì¤ë¤¬¡¢too_flag[]
+¤È¤¤¤¦¤Î¤Ç¡¢È½ÃǤǤ¤½¤¦¤Êµ¤¤â¤¹¤ë¤¬¤³¤ì¤Ï¤à¤·¤í¥Ï¥Ã¥·¥å¤Î¥Á¥§¡¼¥ó¤ò¤¿
+¤É¤ê¤¹¤®¤ë¤Î¤ò»ß¤á¤ë¤¿¤á¤Î¥Õ¥é¥°¤Ç¤¢¤ë¤è¤¦¤Ë»×¤¨¤ë¡£
+
+2ÅÙÌܤΥ롼¥×¤Ç¡¢max ¤ÎÃͤ¬ÊѤï¤ë¤Î¤¬¸°¤À¤í¤¦¤«¡©¡£º£²ó¤Î¾ì¹ç¡¢max ¤Ï
+256 ¤«¤é 2 ¤Ë¤Ê¤ë¡£ºÇĹ°ìÃ×Ĺ¤È¤·¤Æ 2 ¤¬¸Â³¦Ãͤˤʤë¤È¡¢search_dict()
+¤ÎÆ°ºî¤ÏÊѤï¤ë¤À¤í¤¦¤«¡©¤¤¤ä¡¢¤ä¤Ï¤êÊѤï¤é¤Ê¤¤¡£¤É¤¦¤Ë¤â¤³¤Î´Ø¿ô¤À¤±¤Ç
+¤Ï¸«¤Ä¤«¤Ã¤¿¤«¸«¤Ä¤«¤é¤Ê¤«¤Ã¤¿¤«¤È¤¤¤¦È½ÃǤϤǤ¤Ê¤¤¤è¤¦¤À¡£
+
+µ¤»ý°¤¤¤¬¤ä¤Ï¤ê¤³¤Î´Ø¿ô¤Î²òÀϤò½ª¤¨¡¢¼¡¤Ë°Ü¤ë»ö¤Ë¤·¤è¤¦¡£
OSDN Git Service
