BaseTools/Source/C/LzmaCompress/Sdk/C/LzFind.c

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