MdeModulePkg/Library/LzmaCustomDecompressLib/Sdk/C/LzFind.c

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