vcs.maemo.org Git - physicsfs/blob - lzma/C/Compress/Lz/MatchFinder.c

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