deps/lzma-16.04/C/LzFind.c

   1 /* LzFind.c -- Match finder for LZ algorithms\r
   2 2015-10-15 : Igor Pavlov : Public domain */\r
   3 \r
   4 #include "Precomp.h"\r
   5 \r
   6 #include <string.h>\r
   7 \r
   8 #include "LzFind.h"\r
   9 #include "LzHash.h"\r
  10 \r
  11 #define kEmptyHashValue 0\r
  12 #define kMaxValForNormalize ((UInt32)0xFFFFFFFF)\r
  13 #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */\r
  14 #define kNormalizeMask (~(UInt32)(kNormalizeStepMin - 1))\r
  15 #define kMaxHistorySize ((UInt32)7 << 29)\r
  16 \r
  17 #define kStartMaxLen 3\r
  18 \r
  19 static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)\r
  20 {\r
  21   if (!p->directInput)\r
  22   {\r
  23     alloc->Free(alloc, p->bufferBase);\r
  24     p->bufferBase = NULL;\r
  25   }\r
  26 }\r
  27 \r
  28 /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */\r
  29 \r
  30 static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)\r
  31 {\r
  32   UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;\r
  33   if (p->directInput)\r
  34   {\r
  35     p->blockSize = blockSize;\r
  36     return 1;\r
  37   }\r
  38   if (!p->bufferBase || p->blockSize != blockSize)\r
  39   {\r
  40     LzInWindow_Free(p, alloc);\r
  41     p->blockSize = blockSize;\r
  42     p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);\r
  43   }\r
  44   return (p->bufferBase != NULL);\r
  45 }\r
  46 \r
  47 Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }\r
  48 \r
  49 UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }\r
  50 \r
  51 void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)\r
  52 {\r
  53   p->posLimit -= subValue;\r
  54   p->pos -= subValue;\r
  55   p->streamPos -= subValue;\r
  56 }\r
  57 \r
  58 static void MatchFinder_ReadBlock(CMatchFinder *p)\r
  59 {\r
  60   if (p->streamEndWasReached || p->result != SZ_OK)\r
  61     return;\r
  62 \r
  63   /* We use (p->streamPos - p->pos) value. (p->streamPos < p->pos) is allowed. */\r
  64 \r
  65   if (p->directInput)\r
  66   {\r
  67     UInt32 curSize = 0xFFFFFFFF - (p->streamPos - p->pos);\r
  68     if (curSize > p->directInputRem)\r
  69       curSize = (UInt32)p->directInputRem;\r
  70     p->directInputRem -= curSize;\r
  71     p->streamPos += curSize;\r
  72     if (p->directInputRem == 0)\r
  73       p->streamEndWasReached = 1;\r
  74     return;\r
  75   }\r
  76   \r
  77   for (;;)\r
  78   {\r
  79     Byte *dest = p->buffer + (p->streamPos - p->pos);\r
  80     size_t size = (p->bufferBase + p->blockSize - dest);\r
  81     if (size == 0)\r
  82       return;\r
  83 \r
  84     p->result = p->stream->Read(p->stream, dest, &size);\r
  85     if (p->result != SZ_OK)\r
  86       return;\r
  87     if (size == 0)\r
  88     {\r
  89       p->streamEndWasReached = 1;\r
  90       return;\r
  91     }\r
  92     p->streamPos += (UInt32)size;\r
  93     if (p->streamPos - p->pos > p->keepSizeAfter)\r
  94       return;\r
  95   }\r
  96 }\r
  97 \r
  98 void MatchFinder_MoveBlock(CMatchFinder *p)\r
  99 {\r
 100   memmove(p->bufferBase,\r
 101       p->buffer - p->keepSizeBefore,\r
 102       (size_t)(p->streamPos - p->pos) + p->keepSizeBefore);\r
 103   p->buffer = p->bufferBase + p->keepSizeBefore;\r
 104 }\r
 105 \r
 106 int MatchFinder_NeedMove(CMatchFinder *p)\r
 107 {\r
 108   if (p->directInput)\r
 109     return 0;\r
 110   /* if (p->streamEndWasReached) return 0; */\r
 111   return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);\r
 112 }\r
 113 \r
 114 void MatchFinder_ReadIfRequired(CMatchFinder *p)\r
 115 {\r
 116   if (p->streamEndWasReached)\r
 117     return;\r
 118   if (p->keepSizeAfter >= p->streamPos - p->pos)\r
 119     MatchFinder_ReadBlock(p);\r
 120 }\r
 121 \r
 122 static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)\r
 123 {\r
 124   if (MatchFinder_NeedMove(p))\r
 125     MatchFinder_MoveBlock(p);\r
 126   MatchFinder_ReadBlock(p);\r
 127 }\r
 128 \r
 129 static void MatchFinder_SetDefaultSettings(CMatchFinder *p)\r
 130 {\r
 131   p->cutValue = 32;\r
 132   p->btMode = 1;\r
 133   p->numHashBytes = 4;\r
 134   p->bigHash = 0;\r
 135 }\r
 136 \r
 137 #define kCrcPoly 0xEDB88320\r
 138 \r
 139 void MatchFinder_Construct(CMatchFinder *p)\r
 140 {\r
 141   UInt32 i;\r
 142   p->bufferBase = NULL;\r
 143   p->directInput = 0;\r
 144   p->hash = NULL;\r
 145   MatchFinder_SetDefaultSettings(p);\r
 146 \r
 147   for (i = 0; i < 256; i++)\r
 148   {\r
 149     UInt32 r = i;\r
 150     unsigned j;\r
 151     for (j = 0; j < 8; j++)\r
 152       r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));\r
 153     p->crc[i] = r;\r
 154   }\r
 155 }\r
 156 \r
 157 static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)\r
 158 {\r
 159   alloc->Free(alloc, p->hash);\r
 160   p->hash = NULL;\r
 161 }\r
 162 \r
 163 void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)\r
 164 {\r
 165   MatchFinder_FreeThisClassMemory(p, alloc);\r
 166   LzInWindow_Free(p, alloc);\r
 167 }\r
 168 \r
 169 static CLzRef* AllocRefs(size_t num, ISzAlloc *alloc)\r
 170 {\r
 171   size_t sizeInBytes = (size_t)num * sizeof(CLzRef);\r
 172   if (sizeInBytes / sizeof(CLzRef) != num)\r
 173     return NULL;\r
 174   return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);\r
 175 }\r
 176 \r
 177 int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,\r
 178     UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,\r
 179     ISzAlloc *alloc)\r
 180 {\r
 181   UInt32 sizeReserv;\r
 182   \r
 183   if (historySize > kMaxHistorySize)\r
 184   {\r
 185     MatchFinder_Free(p, alloc);\r
 186     return 0;\r
 187   }\r
 188   \r
 189   sizeReserv = historySize >> 1;\r
 190        if (historySize >= ((UInt32)3 << 30)) sizeReserv = historySize >> 3;\r
 191   else if (historySize >= ((UInt32)2 << 30)) sizeReserv = historySize >> 2;\r
 192   \r
 193   sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);\r
 194 \r
 195   p->keepSizeBefore = historySize + keepAddBufferBefore + 1;\r
 196   p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;\r
 197   \r
 198   /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */\r
 199   \r
 200   if (LzInWindow_Create(p, sizeReserv, alloc))\r
 201   {\r
 202     UInt32 newCyclicBufferSize = historySize + 1;\r
 203     UInt32 hs;\r
 204     p->matchMaxLen = matchMaxLen;\r
 205     {\r
 206       p->fixedHashSize = 0;\r
 207       if (p->numHashBytes == 2)\r
 208         hs = (1 << 16) - 1;\r
 209       else\r
 210       {\r
 211         hs = historySize - 1;\r
 212         hs |= (hs >> 1);\r
 213         hs |= (hs >> 2);\r
 214         hs |= (hs >> 4);\r
 215         hs |= (hs >> 8);\r
 216         hs >>= 1;\r
 217         hs |= 0xFFFF; /* don't change it! It's required for Deflate */\r
 218         if (hs > (1 << 24))\r
 219         {\r
 220           if (p->numHashBytes == 3)\r
 221             hs = (1 << 24) - 1;\r
 222           else\r
 223             hs >>= 1;\r
 224           /* if (bigHash) mode, GetHeads4b() in LzFindMt.c needs (hs >= ((1 << 24) - 1))) */\r
 225         }\r
 226       }\r
 227       p->hashMask = hs;\r
 228       hs++;\r
 229       if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;\r
 230       if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;\r
 231       if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;\r
 232       hs += p->fixedHashSize;\r
 233     }\r
 234 \r
 235     {\r
 236       size_t newSize;\r
 237       size_t numSons;\r
 238       p->historySize = historySize;\r
 239       p->hashSizeSum = hs;\r
 240       p->cyclicBufferSize = newCyclicBufferSize;\r
 241       \r
 242       numSons = newCyclicBufferSize;\r
 243       if (p->btMode)\r
 244         numSons <<= 1;\r
 245       newSize = hs + numSons;\r
 246 \r
 247       if (p->hash && p->numRefs == newSize)\r
 248         return 1;\r
 249       \r
 250       MatchFinder_FreeThisClassMemory(p, alloc);\r
 251       p->numRefs = newSize;\r
 252       p->hash = AllocRefs(newSize, alloc);\r
 253       \r
 254       if (p->hash)\r
 255       {\r
 256         p->son = p->hash + p->hashSizeSum;\r
 257         return 1;\r
 258       }\r
 259     }\r
 260   }\r
 261 \r
 262   MatchFinder_Free(p, alloc);\r
 263   return 0;\r
 264 }\r
 265 \r
 266 static void MatchFinder_SetLimits(CMatchFinder *p)\r
 267 {\r
 268   UInt32 limit = kMaxValForNormalize - p->pos;\r
 269   UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;\r
 270   \r
 271   if (limit2 < limit)\r
 272     limit = limit2;\r
 273   limit2 = p->streamPos - p->pos;\r
 274   \r
 275   if (limit2 <= p->keepSizeAfter)\r
 276   {\r
 277     if (limit2 > 0)\r
 278       limit2 = 1;\r
 279   }\r
 280   else\r
 281     limit2 -= p->keepSizeAfter;\r
 282   \r
 283   if (limit2 < limit)\r
 284     limit = limit2;\r
 285   \r
 286   {\r
 287     UInt32 lenLimit = p->streamPos - p->pos;\r
 288     if (lenLimit > p->matchMaxLen)\r
 289       lenLimit = p->matchMaxLen;\r
 290     p->lenLimit = lenLimit;\r
 291   }\r
 292   p->posLimit = p->pos + limit;\r
 293 }\r
 294 \r
 295 void MatchFinder_Init_2(CMatchFinder *p, int readData)\r
 296 {\r
 297   UInt32 i;\r
 298   UInt32 *hash = p->hash;\r
 299   UInt32 num = p->hashSizeSum;\r
 300   for (i = 0; i < num; i++)\r
 301     hash[i] = kEmptyHashValue;\r
 302   \r
 303   p->cyclicBufferPos = 0;\r
 304   p->buffer = p->bufferBase;\r
 305   p->pos = p->streamPos = p->cyclicBufferSize;\r
 306   p->result = SZ_OK;\r
 307   p->streamEndWasReached = 0;\r
 308   \r
 309   if (readData)\r
 310     MatchFinder_ReadBlock(p);\r
 311   \r
 312   MatchFinder_SetLimits(p);\r
 313 }\r
 314 \r
 315 void MatchFinder_Init(CMatchFinder *p)\r
 316 {\r
 317   MatchFinder_Init_2(p, True);\r
 318 }\r
 319   \r
 320 static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)\r
 321 {\r
 322   return (p->pos - p->historySize - 1) & kNormalizeMask;\r
 323 }\r
 324 \r
 325 void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, size_t numItems)\r
 326 {\r
 327   size_t i;\r
 328   for (i = 0; i < numItems; i++)\r
 329   {\r
 330     UInt32 value = items[i];\r
 331     if (value <= subValue)\r
 332       value = kEmptyHashValue;\r
 333     else\r
 334       value -= subValue;\r
 335     items[i] = value;\r
 336   }\r
 337 }\r
 338 \r
 339 static void MatchFinder_Normalize(CMatchFinder *p)\r
 340 {\r
 341   UInt32 subValue = MatchFinder_GetSubValue(p);\r
 342   MatchFinder_Normalize3(subValue, p->hash, p->numRefs);\r
 343   MatchFinder_ReduceOffsets(p, subValue);\r
 344 }\r
 345 \r
 346 static void MatchFinder_CheckLimits(CMatchFinder *p)\r
 347 {\r
 348   if (p->pos == kMaxValForNormalize)\r
 349     MatchFinder_Normalize(p);\r
 350   if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)\r
 351     MatchFinder_CheckAndMoveAndRead(p);\r
 352   if (p->cyclicBufferPos == p->cyclicBufferSize)\r
 353     p->cyclicBufferPos = 0;\r
 354   MatchFinder_SetLimits(p);\r
 355 }\r
 356 \r
 357 static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,\r
 358     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,\r
 359     UInt32 *distances, UInt32 maxLen)\r
 360 {\r
 361   son[_cyclicBufferPos] = curMatch;\r
 362   for (;;)\r
 363   {\r
 364     UInt32 delta = pos - curMatch;\r
 365     if (cutValue-- == 0 || delta >= _cyclicBufferSize)\r
 366       return distances;\r
 367     {\r
 368       const Byte *pb = cur - delta;\r
 369       curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];\r
 370       if (pb[maxLen] == cur[maxLen] && *pb == *cur)\r
 371       {\r
 372         UInt32 len = 0;\r
 373         while (++len != lenLimit)\r
 374           if (pb[len] != cur[len])\r
 375             break;\r
 376         if (maxLen < len)\r
 377         {\r
 378           *distances++ = maxLen = len;\r
 379           *distances++ = delta - 1;\r
 380           if (len == lenLimit)\r
 381             return distances;\r
 382         }\r
 383       }\r
 384     }\r
 385   }\r
 386 }\r
 387 \r
 388 UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,\r
 389     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,\r
 390     UInt32 *distances, UInt32 maxLen)\r
 391 {\r
 392   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;\r
 393   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);\r
 394   UInt32 len0 = 0, len1 = 0;\r
 395   for (;;)\r
 396   {\r
 397     UInt32 delta = pos - curMatch;\r
 398     if (cutValue-- == 0 || delta >= _cyclicBufferSize)\r
 399     {\r
 400       *ptr0 = *ptr1 = kEmptyHashValue;\r
 401       return distances;\r
 402     }\r
 403     {\r
 404       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);\r
 405       const Byte *pb = cur - delta;\r
 406       UInt32 len = (len0 < len1 ? len0 : len1);\r
 407       if (pb[len] == cur[len])\r
 408       {\r
 409         if (++len != lenLimit && pb[len] == cur[len])\r
 410           while (++len != lenLimit)\r
 411             if (pb[len] != cur[len])\r
 412               break;\r
 413         if (maxLen < len)\r
 414         {\r
 415           *distances++ = maxLen = len;\r
 416           *distances++ = delta - 1;\r
 417           if (len == lenLimit)\r
 418           {\r
 419             *ptr1 = pair[0];\r
 420             *ptr0 = pair[1];\r
 421             return distances;\r
 422           }\r
 423         }\r
 424       }\r
 425       if (pb[len] < cur[len])\r
 426       {\r
 427         *ptr1 = curMatch;\r
 428         ptr1 = pair + 1;\r
 429         curMatch = *ptr1;\r
 430         len1 = len;\r
 431       }\r
 432       else\r
 433       {\r
 434         *ptr0 = curMatch;\r
 435         ptr0 = pair;\r
 436         curMatch = *ptr0;\r
 437         len0 = len;\r
 438       }\r
 439     }\r
 440   }\r
 441 }\r
 442 \r
 443 static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,\r
 444     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)\r
 445 {\r
 446   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;\r
 447   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);\r
 448   UInt32 len0 = 0, len1 = 0;\r
 449   for (;;)\r
 450   {\r
 451     UInt32 delta = pos - curMatch;\r
 452     if (cutValue-- == 0 || delta >= _cyclicBufferSize)\r
 453     {\r
 454       *ptr0 = *ptr1 = kEmptyHashValue;\r
 455       return;\r
 456     }\r
 457     {\r
 458       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);\r
 459       const Byte *pb = cur - delta;\r
 460       UInt32 len = (len0 < len1 ? len0 : len1);\r
 461       if (pb[len] == cur[len])\r
 462       {\r
 463         while (++len != lenLimit)\r
 464           if (pb[len] != cur[len])\r
 465             break;\r
 466         {\r
 467           if (len == lenLimit)\r
 468           {\r
 469             *ptr1 = pair[0];\r
 470             *ptr0 = pair[1];\r
 471             return;\r
 472           }\r
 473         }\r
 474       }\r
 475       if (pb[len] < cur[len])\r
 476       {\r
 477         *ptr1 = curMatch;\r
 478         ptr1 = pair + 1;\r
 479         curMatch = *ptr1;\r
 480         len1 = len;\r
 481       }\r
 482       else\r
 483       {\r
 484         *ptr0 = curMatch;\r
 485         ptr0 = pair;\r
 486         curMatch = *ptr0;\r
 487         len0 = len;\r
 488       }\r
 489     }\r
 490   }\r
 491 }\r
 492 \r
 493 #define MOVE_POS \\r
 494   ++p->cyclicBufferPos; \\r
 495   p->buffer++; \\r
 496   if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);\r
 497 \r
 498 #define MOVE_POS_RET MOVE_POS return offset;\r
 499 \r
 500 static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }\r
 501 \r
 502 #define GET_MATCHES_HEADER2(minLen, ret_op) \\r
 503   UInt32 lenLimit; UInt32 hv; const Byte *cur; UInt32 curMatch; \\r
 504   lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \\r
 505   cur = p->buffer;\r
 506 \r
 507 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)\r
 508 #define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)\r
 509 \r
 510 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue\r
 511 \r
 512 #define GET_MATCHES_FOOTER(offset, maxLen) \\r
 513   offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \\r
 514   distances + offset, maxLen) - distances); MOVE_POS_RET;\r
 515 \r
 516 #define SKIP_FOOTER \\r
 517   SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;\r
 518 \r
 519 #define UPDATE_maxLen { \\r
 520     ptrdiff_t diff = (ptrdiff_t)0 - d2; \\r
 521     const Byte *c = cur + maxLen; \\r
 522     const Byte *lim = cur + lenLimit; \\r
 523     for (; c != lim; c++) if (*(c + diff) != *c) break; \\r
 524     maxLen = (UInt32)(c - cur); }\r
 525 \r
 526 static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r
 527 {\r
 528   UInt32 offset;\r
 529   GET_MATCHES_HEADER(2)\r
 530   HASH2_CALC;\r
 531   curMatch = p->hash[hv];\r
 532   p->hash[hv] = p->pos;\r
 533   offset = 0;\r
 534   GET_MATCHES_FOOTER(offset, 1)\r
 535 }\r
 536 \r
 537 UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r
 538 {\r
 539   UInt32 offset;\r
 540   GET_MATCHES_HEADER(3)\r
 541   HASH_ZIP_CALC;\r
 542   curMatch = p->hash[hv];\r
 543   p->hash[hv] = p->pos;\r
 544   offset = 0;\r
 545   GET_MATCHES_FOOTER(offset, 2)\r
 546 }\r
 547 \r
 548 static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r
 549 {\r
 550   UInt32 h2, d2, maxLen, offset, pos;\r
 551   UInt32 *hash;\r
 552   GET_MATCHES_HEADER(3)\r
 553 \r
 554   HASH3_CALC;\r
 555 \r
 556   hash = p->hash;\r
 557   pos = p->pos;\r
 558 \r
 559   d2 = pos - hash[h2];\r
 560 \r
 561   curMatch = hash[kFix3HashSize + hv];\r
 562   \r
 563   hash[h2] = pos;\r
 564   hash[kFix3HashSize + hv] = pos;\r
 565 \r
 566   maxLen = 2;\r
 567   offset = 0;\r
 568 \r
 569   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r
 570   {\r
 571     UPDATE_maxLen\r
 572     distances[0] = maxLen;\r
 573     distances[1] = d2 - 1;\r
 574     offset = 2;\r
 575     if (maxLen == lenLimit)\r
 576     {\r
 577       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));\r
 578       MOVE_POS_RET;\r
 579     }\r
 580   }\r
 581   \r
 582   GET_MATCHES_FOOTER(offset, maxLen)\r
 583 }\r
 584 \r
 585 static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r
 586 {\r
 587   UInt32 h2, h3, d2, d3, maxLen, offset, pos;\r
 588   UInt32 *hash;\r
 589   GET_MATCHES_HEADER(4)\r
 590 \r
 591   HASH4_CALC;\r
 592 \r
 593   hash = p->hash;\r
 594   pos = p->pos;\r
 595 \r
 596   d2 = pos - hash[                h2];\r
 597   d3 = pos - hash[kFix3HashSize + h3];\r
 598 \r
 599   curMatch = hash[kFix4HashSize + hv];\r
 600 \r
 601   hash[                h2] = pos;\r
 602   hash[kFix3HashSize + h3] = pos;\r
 603   hash[kFix4HashSize + hv] = pos;\r
 604 \r
 605   maxLen = 0;\r
 606   offset = 0;\r
 607   \r
 608   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r
 609   {\r
 610     distances[0] = maxLen = 2;\r
 611     distances[1] = d2 - 1;\r
 612     offset = 2;\r
 613   }\r
 614   \r
 615   if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r
 616   {\r
 617     maxLen = 3;\r
 618     distances[offset + 1] = d3 - 1;\r
 619     offset += 2;\r
 620     d2 = d3;\r
 621   }\r
 622   \r
 623   if (offset != 0)\r
 624   {\r
 625     UPDATE_maxLen\r
 626     distances[offset - 2] = maxLen;\r
 627     if (maxLen == lenLimit)\r
 628     {\r
 629       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));\r
 630       MOVE_POS_RET;\r
 631     }\r
 632   }\r
 633   \r
 634   if (maxLen < 3)\r
 635     maxLen = 3;\r
 636   \r
 637   GET_MATCHES_FOOTER(offset, maxLen)\r
 638 }\r
 639 \r
 640 /*\r
 641 static UInt32 Bt5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r
 642 {\r
 643   UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos;\r
 644   UInt32 *hash;\r
 645   GET_MATCHES_HEADER(5)\r
 646 \r
 647   HASH5_CALC;\r
 648 \r
 649   hash = p->hash;\r
 650   pos = p->pos;\r
 651 \r
 652   d2 = pos - hash[                h2];\r
 653   d3 = pos - hash[kFix3HashSize + h3];\r
 654   d4 = pos - hash[kFix4HashSize + h4];\r
 655 \r
 656   curMatch = hash[kFix5HashSize + hv];\r
 657 \r
 658   hash[                h2] = pos;\r
 659   hash[kFix3HashSize + h3] = pos;\r
 660   hash[kFix4HashSize + h4] = pos;\r
 661   hash[kFix5HashSize + hv] = pos;\r
 662 \r
 663   maxLen = 0;\r
 664   offset = 0;\r
 665 \r
 666   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r
 667   {\r
 668     distances[0] = maxLen = 2;\r
 669     distances[1] = d2 - 1;\r
 670     offset = 2;\r
 671     if (*(cur - d2 + 2) == cur[2])\r
 672       distances[0] = maxLen = 3;\r
 673     else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r
 674     {\r
 675       distances[2] = maxLen = 3;\r
 676       distances[3] = d3 - 1;\r
 677       offset = 4;\r
 678       d2 = d3;\r
 679     }\r
 680   }\r
 681   else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r
 682   {\r
 683     distances[0] = maxLen = 3;\r
 684     distances[1] = d3 - 1;\r
 685     offset = 2;\r
 686     d2 = d3;\r
 687   }\r
 688   \r
 689   if (d2 != d4 && d4 < p->cyclicBufferSize\r
 690       && *(cur - d4) == *cur\r
 691       && *(cur - d4 + 3) == *(cur + 3))\r
 692   {\r
 693     maxLen = 4;\r
 694     distances[offset + 1] = d4 - 1;\r
 695     offset += 2;\r
 696     d2 = d4;\r
 697   }\r
 698   \r
 699   if (offset != 0)\r
 700   {\r
 701     UPDATE_maxLen\r
 702     distances[offset - 2] = maxLen;\r
 703     if (maxLen == lenLimit)\r
 704     {\r
 705       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));\r
 706       MOVE_POS_RET;\r
 707     }\r
 708   }\r
 709 \r
 710   if (maxLen < 4)\r
 711     maxLen = 4;\r
 712   \r
 713   GET_MATCHES_FOOTER(offset, maxLen)\r
 714 }\r
 715 */\r
 716 \r
 717 static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r
 718 {\r
 719   UInt32 h2, h3, d2, d3, maxLen, offset, pos;\r
 720   UInt32 *hash;\r
 721   GET_MATCHES_HEADER(4)\r
 722 \r
 723   HASH4_CALC;\r
 724 \r
 725   hash = p->hash;\r
 726   pos = p->pos;\r
 727   \r
 728   d2 = pos - hash[                h2];\r
 729   d3 = pos - hash[kFix3HashSize + h3];\r
 730   \r
 731   curMatch = hash[kFix4HashSize + hv];\r
 732 \r
 733   hash[                h2] = pos;\r
 734   hash[kFix3HashSize + h3] = pos;\r
 735   hash[kFix4HashSize + hv] = pos;\r
 736 \r
 737   maxLen = 0;\r
 738   offset = 0;\r
 739 \r
 740   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r
 741   {\r
 742     distances[0] = maxLen = 2;\r
 743     distances[1] = d2 - 1;\r
 744     offset = 2;\r
 745   }\r
 746   \r
 747   if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r
 748   {\r
 749     maxLen = 3;\r
 750     distances[offset + 1] = d3 - 1;\r
 751     offset += 2;\r
 752     d2 = d3;\r
 753   }\r
 754   \r
 755   if (offset != 0)\r
 756   {\r
 757     UPDATE_maxLen\r
 758     distances[offset - 2] = maxLen;\r
 759     if (maxLen == lenLimit)\r
 760     {\r
 761       p->son[p->cyclicBufferPos] = curMatch;\r
 762       MOVE_POS_RET;\r
 763     }\r
 764   }\r
 765   \r
 766   if (maxLen < 3)\r
 767     maxLen = 3;\r
 768 \r
 769   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),\r
 770       distances + offset, maxLen) - (distances));\r
 771   MOVE_POS_RET\r
 772 }\r
 773 \r
 774 /*\r
 775 static UInt32 Hc5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r
 776 {\r
 777   UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos\r
 778   UInt32 *hash;\r
 779   GET_MATCHES_HEADER(5)\r
 780 \r
 781   HASH5_CALC;\r
 782 \r
 783   hash = p->hash;\r
 784   pos = p->pos;\r
 785   \r
 786   d2 = pos - hash[                h2];\r
 787   d3 = pos - hash[kFix3HashSize + h3];\r
 788   d4 = pos - hash[kFix4HashSize + h4];\r
 789 \r
 790   curMatch = hash[kFix5HashSize + hv];\r
 791 \r
 792   hash[                h2] = pos;\r
 793   hash[kFix3HashSize + h3] = pos;\r
 794   hash[kFix4HashSize + h4] = pos;\r
 795   hash[kFix5HashSize + hv] = pos;\r
 796 \r
 797   maxLen = 0;\r
 798   offset = 0;\r
 799 \r
 800   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)\r
 801   {\r
 802     distances[0] = maxLen = 2;\r
 803     distances[1] = d2 - 1;\r
 804     offset = 2;\r
 805     if (*(cur - d2 + 2) == cur[2])\r
 806       distances[0] = maxLen = 3;\r
 807     else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r
 808     {\r
 809       distances[2] = maxLen = 3;\r
 810       distances[3] = d3 - 1;\r
 811       offset = 4;\r
 812       d2 = d3;\r
 813     }\r
 814   }\r
 815   else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)\r
 816   {\r
 817     distances[0] = maxLen = 3;\r
 818     distances[1] = d3 - 1;\r
 819     offset = 2;\r
 820     d2 = d3;\r
 821   }\r
 822   \r
 823   if (d2 != d4 && d4 < p->cyclicBufferSize\r
 824       && *(cur - d4) == *cur\r
 825       && *(cur - d4 + 3) == *(cur + 3))\r
 826   {\r
 827     maxLen = 4;\r
 828     distances[offset + 1] = d4 - 1;\r
 829     offset += 2;\r
 830     d2 = d4;\r
 831   }\r
 832   \r
 833   if (offset != 0)\r
 834   {\r
 835     UPDATE_maxLen\r
 836     distances[offset - 2] = maxLen;\r
 837     if (maxLen == lenLimit)\r
 838     {\r
 839       p->son[p->cyclicBufferPos] = curMatch;\r
 840       MOVE_POS_RET;\r
 841     }\r
 842   }\r
 843   \r
 844   if (maxLen < 4)\r
 845     maxLen = 4;\r
 846 \r
 847   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),\r
 848       distances + offset, maxLen) - (distances));\r
 849   MOVE_POS_RET\r
 850 }\r
 851 */\r
 852 \r
 853 UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)\r
 854 {\r
 855   UInt32 offset;\r
 856   GET_MATCHES_HEADER(3)\r
 857   HASH_ZIP_CALC;\r
 858   curMatch = p->hash[hv];\r
 859   p->hash[hv] = p->pos;\r
 860   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),\r
 861       distances, 2) - (distances));\r
 862   MOVE_POS_RET\r
 863 }\r
 864 \r
 865 static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r
 866 {\r
 867   do\r
 868   {\r
 869     SKIP_HEADER(2)\r
 870     HASH2_CALC;\r
 871     curMatch = p->hash[hv];\r
 872     p->hash[hv] = p->pos;\r
 873     SKIP_FOOTER\r
 874   }\r
 875   while (--num != 0);\r
 876 }\r
 877 \r
 878 void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r
 879 {\r
 880   do\r
 881   {\r
 882     SKIP_HEADER(3)\r
 883     HASH_ZIP_CALC;\r
 884     curMatch = p->hash[hv];\r
 885     p->hash[hv] = p->pos;\r
 886     SKIP_FOOTER\r
 887   }\r
 888   while (--num != 0);\r
 889 }\r
 890 \r
 891 static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r
 892 {\r
 893   do\r
 894   {\r
 895     UInt32 h2;\r
 896     UInt32 *hash;\r
 897     SKIP_HEADER(3)\r
 898     HASH3_CALC;\r
 899     hash = p->hash;\r
 900     curMatch = hash[kFix3HashSize + hv];\r
 901     hash[h2] =\r
 902     hash[kFix3HashSize + hv] = p->pos;\r
 903     SKIP_FOOTER\r
 904   }\r
 905   while (--num != 0);\r
 906 }\r
 907 \r
 908 static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r
 909 {\r
 910   do\r
 911   {\r
 912     UInt32 h2, h3;\r
 913     UInt32 *hash;\r
 914     SKIP_HEADER(4)\r
 915     HASH4_CALC;\r
 916     hash = p->hash;\r
 917     curMatch = hash[kFix4HashSize + hv];\r
 918     hash[                h2] =\r
 919     hash[kFix3HashSize + h3] =\r
 920     hash[kFix4HashSize + hv] = p->pos;\r
 921     SKIP_FOOTER\r
 922   }\r
 923   while (--num != 0);\r
 924 }\r
 925 \r
 926 /*\r
 927 static void Bt5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r
 928 {\r
 929   do\r
 930   {\r
 931     UInt32 h2, h3, h4;\r
 932     UInt32 *hash;\r
 933     SKIP_HEADER(5)\r
 934     HASH5_CALC;\r
 935     hash = p->hash;\r
 936     curMatch = hash[kFix5HashSize + hv];\r
 937     hash[                h2] =\r
 938     hash[kFix3HashSize + h3] =\r
 939     hash[kFix4HashSize + h4] =\r
 940     hash[kFix5HashSize + hv] = p->pos;\r
 941     SKIP_FOOTER\r
 942   }\r
 943   while (--num != 0);\r
 944 }\r
 945 */\r
 946 \r
 947 static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r
 948 {\r
 949   do\r
 950   {\r
 951     UInt32 h2, h3;\r
 952     UInt32 *hash;\r
 953     SKIP_HEADER(4)\r
 954     HASH4_CALC;\r
 955     hash = p->hash;\r
 956     curMatch = hash[kFix4HashSize + hv];\r
 957     hash[                h2] =\r
 958     hash[kFix3HashSize + h3] =\r
 959     hash[kFix4HashSize + hv] = p->pos;\r
 960     p->son[p->cyclicBufferPos] = curMatch;\r
 961     MOVE_POS\r
 962   }\r
 963   while (--num != 0);\r
 964 }\r
 965 \r
 966 /*\r
 967 static void Hc5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r
 968 {\r
 969   do\r
 970   {\r
 971     UInt32 h2, h3, h4;\r
 972     UInt32 *hash;\r
 973     SKIP_HEADER(5)\r
 974     HASH5_CALC;\r
 975     hash = p->hash;\r
 976     curMatch = p->hash[kFix5HashSize + hv];\r
 977     hash[                h2] =\r
 978     hash[kFix3HashSize + h3] =\r
 979     hash[kFix4HashSize + h4] =\r
 980     hash[kFix5HashSize + hv] = p->pos;\r
 981     p->son[p->cyclicBufferPos] = curMatch;\r
 982     MOVE_POS\r
 983   }\r
 984   while (--num != 0);\r
 985 }\r
 986 */\r
 987 \r
 988 void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)\r
 989 {\r
 990   do\r
 991   {\r
 992     SKIP_HEADER(3)\r
 993     HASH_ZIP_CALC;\r
 994     curMatch = p->hash[hv];\r
 995     p->hash[hv] = p->pos;\r
 996     p->son[p->cyclicBufferPos] = curMatch;\r
 997     MOVE_POS\r
 998   }\r
 999   while (--num != 0);\r
1000 }\r
1001 \r
1002 void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)\r
1003 {\r
1004   vTable->Init = (Mf_Init_Func)MatchFinder_Init;\r
1005   vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;\r
1006   vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;\r
1007   if (!p->btMode)\r
1008   {\r
1009     /* if (p->numHashBytes <= 4) */\r
1010     {\r
1011       vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;\r
1012       vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;\r
1013     }\r
1014     /*\r
1015     else\r
1016     {\r
1017       vTable->GetMatches = (Mf_GetMatches_Func)Hc5_MatchFinder_GetMatches;\r
1018       vTable->Skip = (Mf_Skip_Func)Hc5_MatchFinder_Skip;\r
1019     }\r
1020     */\r
1021   }\r
1022   else if (p->numHashBytes == 2)\r
1023   {\r
1024     vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;\r
1025     vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;\r
1026   }\r
1027   else if (p->numHashBytes == 3)\r
1028   {\r
1029     vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;\r
1030     vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;\r
1031   }\r
1032   else /* if (p->numHashBytes == 4) */\r
1033   {\r
1034     vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;\r
1035     vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;\r
1036   }\r
1037   /*\r
1038   else\r
1039   {\r
1040     vTable->GetMatches = (Mf_GetMatches_Func)Bt5_MatchFinder_GetMatches;\r
1041     vTable->Skip = (Mf_Skip_Func)Bt5_MatchFinder_Skip;\r
1042   }\r
1043   */\r
1044 }\r