usr/src/common/lzma/LzFind.c

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