third_party/lzma_sdk/LzFind.c

   1 /* LzFind.c -- Match finder for LZ algorithms
   2 2009-04-22 : Igor Pavlov : Public domain */
   3
   4 #include <string.h>
   5
   6 #include "LzFind.h"
   7 #include "LzHash.h"
   8
   9 #define kEmptyHashValue 0
  10 #define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
  11 #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
  12 #define kNormalizeMask (~(kNormalizeStepMin - 1))
  13 #define kMaxHistorySize ((UInt32)3 << 30)
  14
  15 #define kStartMaxLen 3
  16
  17 static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
  18 {
  19   if (!p->directInput)
  20   {
  21     alloc->Free(alloc, p->bufferBase);
  22     p->bufferBase = 0;
  23   }
  24 }
  25
  26 /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
  27
  28 static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)
  29 {
  30   UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
  31   if (p->directInput)
  32   {
  33     p->blockSize = blockSize;
  34     return 1;
  35   }
  36   if (p->bufferBase == 0 || p->blockSize != blockSize)
  37   {
  38     LzInWindow_Free(p, alloc);
  39     p->blockSize = blockSize;
  40     p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
  41   }
  42   return (p->bufferBase != 0);
  43 }
  44
  45 Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
  46 Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[index]; }
  47
  48 UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
  49
  50 void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
  51 {
  52   p->posLimit -= subValue;
  53   p->pos -= subValue;
  54   p->streamPos -= subValue;
  55 }
  56
  57 static void MatchFinder_ReadBlock(CMatchFinder *p)
  58 {
  59   if (p->streamEndWasReached || p->result != SZ_OK)
  60     return;
  61   if (p->directInput)
  62   {
  63     UInt32 curSize = 0xFFFFFFFF - p->streamPos;
  64     if (curSize > p->directInputRem)
  65       curSize = (UInt32)p->directInputRem;
  66     p->directInputRem -= curSize;
  67     p->streamPos += curSize;
  68     if (p->directInputRem == 0)
  69       p->streamEndWasReached = 1;
  70     return;
  71   }
  72   for (;;)
  73   {
  74     Byte *dest = p->buffer + (p->streamPos - p->pos);
  75     size_t size = (p->bufferBase + p->blockSize - dest);
  76     if (size == 0)
  77       return;
  78     p->result = p->stream->Read(p->stream, dest, &size);
  79     if (p->result != SZ_OK)
  80       return;
  81     if (size == 0)
  82     {
  83       p->streamEndWasReached = 1;
  84       return;
  85     }
  86     p->streamPos += (UInt32)size;
  87     if (p->streamPos - p->pos > p->keepSizeAfter)
  88       return;
  89   }
  90 }
  91
  92 void MatchFinder_MoveBlock(CMatchFinder *p)
  93 {
  94   memmove(p->bufferBase,
  95     p->buffer - p->keepSizeBefore,
  96     (size_t)(p->streamPos - p->pos + p->keepSizeBefore));
  97   p->buffer = p->bufferBase + p->keepSizeBefore;
  98 }
  99
 100 int MatchFinder_NeedMove(CMatchFinder *p)
 101 {
 102   if (p->directInput)
 103     return 0;
 104   /* if (p->streamEndWasReached) return 0; */
 105   return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
 106 }
 107
 108 void MatchFinder_ReadIfRequired(CMatchFinder *p)
 109 {
 110   if (p->streamEndWasReached)
 111     return;
 112   if (p->keepSizeAfter >= p->streamPos - p->pos)
 113     MatchFinder_ReadBlock(p);
 114 }
 115
 116 static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
 117 {
 118   if (MatchFinder_NeedMove(p))
 119     MatchFinder_MoveBlock(p);
 120   MatchFinder_ReadBlock(p);
 121 }
 122
 123 static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
 124 {
 125   p->cutValue = 32;
 126   p->btMode = 1;
 127   p->numHashBytes = 4;
 128   p->bigHash = 0;
 129 }
 130
 131 #define kCrcPoly 0xEDB88320
 132
 133 void MatchFinder_Construct(CMatchFinder *p)
 134 {
 135   UInt32 i;
 136   p->bufferBase = 0;
 137   p->directInput = 0;
 138   p->hash = 0;
 139   MatchFinder_SetDefaultSettings(p);
 140
 141   for (i = 0; i < 256; i++)
 142   {
 143     UInt32 r = i;
 144     int j;
 145     for (j = 0; j < 8; j++)
 146       r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
 147     p->crc[i] = r;
 148   }
 149 }
 150
 151 static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
 152 {
 153   alloc->Free(alloc, p->hash);
 154   p->hash = 0;
 155 }
 156
 157 void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
 158 {
 159   MatchFinder_FreeThisClassMemory(p, alloc);
 160   LzInWindow_Free(p, alloc);
 161 }
 162
 163 static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)
 164 {
 165   size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
 166   if (sizeInBytes / sizeof(CLzRef) != num)
 167     return 0;
 168   return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
 169 }
 170
 171 int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
 172     UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
 173     ISzAlloc *alloc)
 174 {
 175   UInt32 sizeReserv;
 176   if (historySize > kMaxHistorySize)
 177   {
 178     MatchFinder_Free(p, alloc);
 179     return 0;
 180   }
 181   sizeReserv = historySize >> 1;
 182   if (historySize > ((UInt32)2 << 30))
 183     sizeReserv = historySize >> 2;
 184   sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
 185
 186   p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
 187   p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
 188   /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
 189   if (LzInWindow_Create(p, sizeReserv, alloc))
 190   {
 191     UInt32 newCyclicBufferSize = historySize + 1;
 192     UInt32 hs;
 193     p->matchMaxLen = matchMaxLen;
 194     {
 195       p->fixedHashSize = 0;
 196       if (p->numHashBytes == 2)
 197         hs = (1 << 16) - 1;
 198       else
 199       {
 200         hs = historySize - 1;
 201         hs |= (hs >> 1);
 202         hs |= (hs >> 2);
 203         hs |= (hs >> 4);
 204         hs |= (hs >> 8);
 205         hs >>= 1;
 206         hs |= 0xFFFF; /* don't change it! It's required for Deflate */
 207         if (hs > (1 << 24))
 208         {
 209           if (p->numHashBytes == 3)
 210             hs = (1 << 24) - 1;
 211           else
 212             hs >>= 1;
 213         }
 214       }
 215       p->hashMask = hs;
 216       hs++;
 217       if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
 218       if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
 219       if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
 220       hs += p->fixedHashSize;
 221     }
 222
 223     {
 224       UInt32 prevSize = p->hashSizeSum + p->numSons;
 225       UInt32 newSize;
 226       p->historySize = historySize;
 227       p->hashSizeSum = hs;
 228       p->cyclicBufferSize = newCyclicBufferSize;
 229       p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
 230       newSize = p->hashSizeSum + p->numSons;
 231       if (p->hash != 0 && prevSize == newSize)
 232         return 1;
 233       MatchFinder_FreeThisClassMemory(p, alloc);
 234       p->hash = AllocRefs(newSize, alloc);
 235       if (p->hash != 0)
 236       {
 237         p->son = p->hash + p->hashSizeSum;
 238         return 1;
 239       }
 240     }
 241   }
 242   MatchFinder_Free(p, alloc);
 243   return 0;
 244 }
 245
 246 static void MatchFinder_SetLimits(CMatchFinder *p)
 247 {
 248   UInt32 limit = kMaxValForNormalize - p->pos;
 249   UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
 250   if (limit2 < limit)
 251     limit = limit2;
 252   limit2 = p->streamPos - p->pos;
 253   if (limit2 <= p->keepSizeAfter)
 254   {
 255     if (limit2 > 0)
 256       limit2 = 1;
 257   }
 258   else
 259     limit2 -= p->keepSizeAfter;
 260   if (limit2 < limit)
 261     limit = limit2;
 262   {
 263     UInt32 lenLimit = p->streamPos - p->pos;
 264     if (lenLimit > p->matchMaxLen)
 265       lenLimit = p->matchMaxLen;
 266     p->lenLimit = lenLimit;
 267   }
 268   p->posLimit = p->pos + limit;
 269 }
 270
 271 void MatchFinder_Init(CMatchFinder *p)
 272 {
 273   UInt32 i;
 274   for (i = 0; i < p->hashSizeSum; i++)
 275     p->hash[i] = kEmptyHashValue;
 276   p->cyclicBufferPos = 0;
 277   p->buffer = p->bufferBase;
 278   p->pos = p->streamPos = p->cyclicBufferSize;
 279   p->result = SZ_OK;
 280   p->streamEndWasReached = 0;
 281   MatchFinder_ReadBlock(p);
 282   MatchFinder_SetLimits(p);
 283 }
 284
 285 static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
 286 {
 287   return (p->pos - p->historySize - 1) & kNormalizeMask;
 288 }
 289
 290 void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
 291 {
 292   UInt32 i;
 293   for (i = 0; i < numItems; i++)
 294   {
 295     UInt32 value = items[i];
 296     if (value <= subValue)
 297       value = kEmptyHashValue;
 298     else
 299       value -= subValue;
 300     items[i] = value;
 301   }
 302 }
 303
 304 static void MatchFinder_Normalize(CMatchFinder *p)
 305 {
 306   UInt32 subValue = MatchFinder_GetSubValue(p);
 307   MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
 308   MatchFinder_ReduceOffsets(p, subValue);
 309 }
 310
 311 static void MatchFinder_CheckLimits(CMatchFinder *p)
 312 {
 313   if (p->pos == kMaxValForNormalize)
 314     MatchFinder_Normalize(p);
 315   if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
 316     MatchFinder_CheckAndMoveAndRead(p);
 317   if (p->cyclicBufferPos == p->cyclicBufferSize)
 318     p->cyclicBufferPos = 0;
 319   MatchFinder_SetLimits(p);
 320 }
 321
 322 static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 323     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
 324     UInt32 *distances, UInt32 maxLen)
 325 {
 326   son[_cyclicBufferPos] = curMatch;
 327   for (;;)
 328   {
 329     UInt32 delta = pos - curMatch;
 330     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 331       return distances;
 332     {
 333       const Byte *pb = cur - delta;
 334       curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
 335       if (pb[maxLen] == cur[maxLen] && *pb == *cur)
 336       {
 337         UInt32 len = 0;
 338         while (++len != lenLimit)
 339           if (pb[len] != cur[len])
 340             break;
 341         if (maxLen < len)
 342         {
 343           *distances++ = maxLen = len;
 344           *distances++ = delta - 1;
 345           if (len == lenLimit)
 346             return distances;
 347         }
 348       }
 349     }
 350   }
 351 }
 352
 353 UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 354     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
 355     UInt32 *distances, UInt32 maxLen)
 356 {
 357   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 358   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
 359   UInt32 len0 = 0, len1 = 0;
 360   for (;;)
 361   {
 362     UInt32 delta = pos - curMatch;
 363     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 364     {
 365       *ptr0 = *ptr1 = kEmptyHashValue;
 366       return distances;
 367     }
 368     {
 369       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
 370       const Byte *pb = cur - delta;
 371       UInt32 len = (len0 < len1 ? len0 : len1);
 372       if (pb[len] == cur[len])
 373       {
 374         if (++len != lenLimit && pb[len] == cur[len])
 375           while (++len != lenLimit)
 376             if (pb[len] != cur[len])
 377               break;
 378         if (maxLen < len)
 379         {
 380           *distances++ = maxLen = len;
 381           *distances++ = delta - 1;
 382           if (len == lenLimit)
 383           {
 384             *ptr1 = pair[0];
 385             *ptr0 = pair[1];
 386             return distances;
 387           }
 388         }
 389       }
 390       if (pb[len] < cur[len])
 391       {
 392         *ptr1 = curMatch;
 393         ptr1 = pair + 1;
 394         curMatch = *ptr1;
 395         len1 = len;
 396       }
 397       else
 398       {
 399         *ptr0 = curMatch;
 400         ptr0 = pair;
 401         curMatch = *ptr0;
 402         len0 = len;
 403       }
 404     }
 405   }
 406 }
 407
 408 static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 409     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
 410 {
 411   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 412   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
 413   UInt32 len0 = 0, len1 = 0;
 414   for (;;)
 415   {
 416     UInt32 delta = pos - curMatch;
 417     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 418     {
 419       *ptr0 = *ptr1 = kEmptyHashValue;
 420       return;
 421     }
 422     {
 423       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
 424       const Byte *pb = cur - delta;
 425       UInt32 len = (len0 < len1 ? len0 : len1);
 426       if (pb[len] == cur[len])
 427       {
 428         while (++len != lenLimit)
 429           if (pb[len] != cur[len])
 430             break;
 431         {
 432           if (len == lenLimit)
 433           {
 434             *ptr1 = pair[0];
 435             *ptr0 = pair[1];
 436             return;
 437           }
 438         }
 439       }
 440       if (pb[len] < cur[len])
 441       {
 442         *ptr1 = curMatch;
 443         ptr1 = pair + 1;
 444         curMatch = *ptr1;
 445         len1 = len;
 446       }
 447       else
 448       {
 449         *ptr0 = curMatch;
 450         ptr0 = pair;
 451         curMatch = *ptr0;
 452         len0 = len;
 453       }
 454     }
 455   }
 456 }
 457
 458 #define MOVE_POS \
 459   ++p->cyclicBufferPos; \
 460   p->buffer++; \
 461   if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
 462
 463 #define MOVE_POS_RET MOVE_POS return offset;
 464
 465 static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
 466
 467 #define GET_MATCHES_HEADER2(minLen, ret_op) \
 468   UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \
 469   lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
 470   cur = p->buffer;
 471
 472 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
 473 #define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)
 474
 475 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
 476
 477 #define GET_MATCHES_FOOTER(offset, maxLen) \
 478   offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
 479   distances + offset, maxLen) - distances); MOVE_POS_RET;
 480
 481 #define SKIP_FOOTER \
 482   SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
 483
 484 static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 485 {
 486   UInt32 offset;
 487   GET_MATCHES_HEADER(2)
 488   HASH2_CALC;
 489   curMatch = p->hash[hashValue];
 490   p->hash[hashValue] = p->pos;
 491   offset = 0;
 492   GET_MATCHES_FOOTER(offset, 1)
 493 }
 494
 495 UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 496 {
 497   UInt32 offset;
 498   GET_MATCHES_HEADER(3)
 499   HASH_ZIP_CALC;
 500   curMatch = p->hash[hashValue];
 501   p->hash[hashValue] = p->pos;
 502   offset = 0;
 503   GET_MATCHES_FOOTER(offset, 2)
 504 }
 505
 506 static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 507 {
 508   UInt32 hash2Value, delta2, maxLen, offset;
 509   GET_MATCHES_HEADER(3)
 510
 511   HASH3_CALC;
 512
 513   delta2 = p->pos - p->hash[hash2Value];
 514   curMatch = p->hash[kFix3HashSize + hashValue];
 515
 516   p->hash[hash2Value] =
 517   p->hash[kFix3HashSize + hashValue] = p->pos;
 518
 519
 520   maxLen = 2;
 521   offset = 0;
 522   if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
 523   {
 524     for (; maxLen != lenLimit; maxLen++)
 525       if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
 526         break;
 527     distances[0] = maxLen;
 528     distances[1] = delta2 - 1;
 529     offset = 2;
 530     if (maxLen == lenLimit)
 531     {
 532       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
 533       MOVE_POS_RET;
 534     }
 535   }
 536   GET_MATCHES_FOOTER(offset, maxLen)
 537 }
 538
 539 static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 540 {
 541   UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
 542   GET_MATCHES_HEADER(4)
 543
 544   HASH4_CALC;
 545
 546   delta2 = p->pos - p->hash[                hash2Value];
 547   delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
 548   curMatch = p->hash[kFix4HashSize + hashValue];
 549
 550   p->hash[                hash2Value] =
 551   p->hash[kFix3HashSize + hash3Value] =
 552   p->hash[kFix4HashSize + hashValue] = p->pos;
 553
 554   maxLen = 1;
 555   offset = 0;
 556   if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
 557   {
 558     distances[0] = maxLen = 2;
 559     distances[1] = delta2 - 1;
 560     offset = 2;
 561   }
 562   if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
 563   {
 564     maxLen = 3;
 565     distances[offset + 1] = delta3 - 1;
 566     offset += 2;
 567     delta2 = delta3;
 568   }
 569   if (offset != 0)
 570   {
 571     for (; maxLen != lenLimit; maxLen++)
 572       if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
 573         break;
 574     distances[offset - 2] = maxLen;
 575     if (maxLen == lenLimit)
 576     {
 577       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
 578       MOVE_POS_RET;
 579     }
 580   }
 581   if (maxLen < 3)
 582     maxLen = 3;
 583   GET_MATCHES_FOOTER(offset, maxLen)
 584 }
 585
 586 static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 587 {
 588   UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
 589   GET_MATCHES_HEADER(4)
 590
 591   HASH4_CALC;
 592
 593   delta2 = p->pos - p->hash[                hash2Value];
 594   delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
 595   curMatch = p->hash[kFix4HashSize + hashValue];
 596
 597   p->hash[                hash2Value] =
 598   p->hash[kFix3HashSize + hash3Value] =
 599   p->hash[kFix4HashSize + hashValue] = p->pos;
 600
 601   maxLen = 1;
 602   offset = 0;
 603   if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
 604   {
 605     distances[0] = maxLen = 2;
 606     distances[1] = delta2 - 1;
 607     offset = 2;
 608   }
 609   if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
 610   {
 611     maxLen = 3;
 612     distances[offset + 1] = delta3 - 1;
 613     offset += 2;
 614     delta2 = delta3;
 615   }
 616   if (offset != 0)
 617   {
 618     for (; maxLen != lenLimit; maxLen++)
 619       if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
 620         break;
 621     distances[offset - 2] = maxLen;
 622     if (maxLen == lenLimit)
 623     {
 624       p->son[p->cyclicBufferPos] = curMatch;
 625       MOVE_POS_RET;
 626     }
 627   }
 628   if (maxLen < 3)
 629     maxLen = 3;
 630   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 631     distances + offset, maxLen) - (distances));
 632   MOVE_POS_RET
 633 }
 634
 635 UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 636 {
 637   UInt32 offset;
 638   GET_MATCHES_HEADER(3)
 639   HASH_ZIP_CALC;
 640   curMatch = p->hash[hashValue];
 641   p->hash[hashValue] = p->pos;
 642   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 643     distances, 2) - (distances));
 644   MOVE_POS_RET
 645 }
 646
 647 static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 648 {
 649   do
 650   {
 651     SKIP_HEADER(2)
 652     HASH2_CALC;
 653     curMatch = p->hash[hashValue];
 654     p->hash[hashValue] = p->pos;
 655     SKIP_FOOTER
 656   }
 657   while (--num != 0);
 658 }
 659
 660 void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 661 {
 662   do
 663   {
 664     SKIP_HEADER(3)
 665     HASH_ZIP_CALC;
 666     curMatch = p->hash[hashValue];
 667     p->hash[hashValue] = p->pos;
 668     SKIP_FOOTER
 669   }
 670   while (--num != 0);
 671 }
 672
 673 static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 674 {
 675   do
 676   {
 677     UInt32 hash2Value;
 678     SKIP_HEADER(3)
 679     HASH3_CALC;
 680     curMatch = p->hash[kFix3HashSize + hashValue];
 681     p->hash[hash2Value] =
 682     p->hash[kFix3HashSize + hashValue] = p->pos;
 683     SKIP_FOOTER
 684   }
 685   while (--num != 0);
 686 }
 687
 688 static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 689 {
 690   do
 691   {
 692     UInt32 hash2Value, hash3Value;
 693     SKIP_HEADER(4)
 694     HASH4_CALC;
 695     curMatch = p->hash[kFix4HashSize + hashValue];
 696     p->hash[                hash2Value] =
 697     p->hash[kFix3HashSize + hash3Value] = p->pos;
 698     p->hash[kFix4HashSize + hashValue] = p->pos;
 699     SKIP_FOOTER
 700   }
 701   while (--num != 0);
 702 }
 703
 704 static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 705 {
 706   do
 707   {
 708     UInt32 hash2Value, hash3Value;
 709     SKIP_HEADER(4)
 710     HASH4_CALC;
 711     curMatch = p->hash[kFix4HashSize + hashValue];
 712     p->hash[                hash2Value] =
 713     p->hash[kFix3HashSize + hash3Value] =
 714     p->hash[kFix4HashSize + hashValue] = p->pos;
 715     p->son[p->cyclicBufferPos] = curMatch;
 716     MOVE_POS
 717   }
 718   while (--num != 0);
 719 }
 720
 721 void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 722 {
 723   do
 724   {
 725     SKIP_HEADER(3)
 726     HASH_ZIP_CALC;
 727     curMatch = p->hash[hashValue];
 728     p->hash[hashValue] = p->pos;
 729     p->son[p->cyclicBufferPos] = curMatch;
 730     MOVE_POS
 731   }
 732   while (--num != 0);
 733 }
 734
 735 void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
 736 {
 737   vTable->Init = (Mf_Init_Func)MatchFinder_Init;
 738   vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
 739   vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
 740   vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
 741   if (!p->btMode)
 742   {
 743     vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
 744     vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
 745   }
 746   else if (p->numHashBytes == 2)
 747   {
 748     vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
 749     vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
 750   }
 751   else if (p->numHashBytes == 3)
 752   {
 753     vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
 754     vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
 755   }
 756   else
 757   {
 758     vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
 759     vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
 760   }
 761 }