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

   1 /* LzFind.c -- Match finder for LZ algorithms
   2 2018-07-08 : 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   unsigned 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 = (UInt32)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
 374 MY_NO_INLINE
 375 static void MatchFinder_CheckLimits(CMatchFinder *p)
 376 {
 377   if (p->pos == kMaxValForNormalize)
 378     MatchFinder_Normalize(p);
 379   if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
 380     MatchFinder_CheckAndMoveAndRead(p);
 381   if (p->cyclicBufferPos == p->cyclicBufferSize)
 382     p->cyclicBufferPos = 0;
 383   MatchFinder_SetLimits(p);
 384 }
 385
 386
 387 /*
 388   (lenLimit > maxLen)
 389 */
 390 MY_FORCE_INLINE
 391 static UInt32 * Hc_GetMatchesSpec(unsigned lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 392     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
 393     UInt32 *distances, unsigned maxLen)
 394 {
 395   /*
 396   son[_cyclicBufferPos] = curMatch;
 397   for (;;)
 398   {
 399     UInt32 delta = pos - curMatch;
 400     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 401       return distances;
 402     {
 403       const Byte *pb = cur - delta;
 404       curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
 405       if (pb[maxLen] == cur[maxLen] && *pb == *cur)
 406       {
 407         UInt32 len = 0;
 408         while (++len != lenLimit)
 409           if (pb[len] != cur[len])
 410             break;
 411         if (maxLen < len)
 412         {
 413           maxLen = len;
 414           *distances++ = len;
 415           *distances++ = delta - 1;
 416           if (len == lenLimit)
 417             return distances;
 418         }
 419       }
 420     }
 421   }
 422   */
 423
 424   const Byte *lim = cur + lenLimit;
 425   son[_cyclicBufferPos] = curMatch;
 426   do
 427   {
 428     UInt32 delta = pos - curMatch;
 429     if (delta >= _cyclicBufferSize)
 430       break;
 431     {
 432       ptrdiff_t diff;
 433       curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
 434       diff = (ptrdiff_t)0 - delta;
 435       if (cur[maxLen] == cur[maxLen + diff])
 436       {
 437         const Byte *c = cur;
 438         while (*c == c[diff])
 439         {
 440           if (++c == lim)
 441           {
 442             distances[0] = (UInt32)(lim - cur);
 443             distances[1] = delta - 1;
 444             return distances + 2;
 445           }
 446         }
 447         {
 448           unsigned len = (unsigned)(c - cur);
 449           if (maxLen < len)
 450           {
 451             maxLen = len;
 452             distances[0] = (UInt32)len;
 453             distances[1] = delta - 1;
 454             distances += 2;
 455           }
 456         }
 457       }
 458     }
 459   }
 460   while (--cutValue);
 461
 462   return distances;
 463 }
 464
 465
 466 MY_FORCE_INLINE
 467 UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 468     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
 469     UInt32 *distances, UInt32 maxLen)
 470 {
 471   CLzRef *ptr0 = son + ((size_t)_cyclicBufferPos << 1) + 1;
 472   CLzRef *ptr1 = son + ((size_t)_cyclicBufferPos << 1);
 473   unsigned len0 = 0, len1 = 0;
 474   for (;;)
 475   {
 476     UInt32 delta = pos - curMatch;
 477     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 478     {
 479       *ptr0 = *ptr1 = kEmptyHashValue;
 480       return distances;
 481     }
 482     {
 483       CLzRef *pair = son + ((size_t)(_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
 484       const Byte *pb = cur - delta;
 485       unsigned len = (len0 < len1 ? len0 : len1);
 486       UInt32 pair0 = pair[0];
 487       if (pb[len] == cur[len])
 488       {
 489         if (++len != lenLimit && pb[len] == cur[len])
 490           while (++len != lenLimit)
 491             if (pb[len] != cur[len])
 492               break;
 493         if (maxLen < len)
 494         {
 495           maxLen = (UInt32)len;
 496           *distances++ = (UInt32)len;
 497           *distances++ = delta - 1;
 498           if (len == lenLimit)
 499           {
 500             *ptr1 = pair0;
 501             *ptr0 = pair[1];
 502             return distances;
 503           }
 504         }
 505       }
 506       if (pb[len] < cur[len])
 507       {
 508         *ptr1 = curMatch;
 509         ptr1 = pair + 1;
 510         curMatch = *ptr1;
 511         len1 = len;
 512       }
 513       else
 514       {
 515         *ptr0 = curMatch;
 516         ptr0 = pair;
 517         curMatch = *ptr0;
 518         len0 = len;
 519       }
 520     }
 521   }
 522 }
 523
 524 static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 525     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
 526 {
 527   CLzRef *ptr0 = son + ((size_t)_cyclicBufferPos << 1) + 1;
 528   CLzRef *ptr1 = son + ((size_t)_cyclicBufferPos << 1);
 529   unsigned len0 = 0, len1 = 0;
 530   for (;;)
 531   {
 532     UInt32 delta = pos - curMatch;
 533     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 534     {
 535       *ptr0 = *ptr1 = kEmptyHashValue;
 536       return;
 537     }
 538     {
 539       CLzRef *pair = son + ((size_t)(_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
 540       const Byte *pb = cur - delta;
 541       unsigned len = (len0 < len1 ? len0 : len1);
 542       if (pb[len] == cur[len])
 543       {
 544         while (++len != lenLimit)
 545           if (pb[len] != cur[len])
 546             break;
 547         {
 548           if (len == lenLimit)
 549           {
 550             *ptr1 = pair[0];
 551             *ptr0 = pair[1];
 552             return;
 553           }
 554         }
 555       }
 556       if (pb[len] < cur[len])
 557       {
 558         *ptr1 = curMatch;
 559         ptr1 = pair + 1;
 560         curMatch = *ptr1;
 561         len1 = len;
 562       }
 563       else
 564       {
 565         *ptr0 = curMatch;
 566         ptr0 = pair;
 567         curMatch = *ptr0;
 568         len0 = len;
 569       }
 570     }
 571   }
 572 }
 573
 574 #define MOVE_POS \
 575   ++p->cyclicBufferPos; \
 576   p->buffer++; \
 577   if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
 578
 579 #define MOVE_POS_RET MOVE_POS return (UInt32)offset;
 580
 581 static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
 582
 583 #define GET_MATCHES_HEADER2(minLen, ret_op) \
 584   unsigned lenLimit; UInt32 hv; const Byte *cur; UInt32 curMatch; \
 585   lenLimit = (unsigned)p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
 586   cur = p->buffer;
 587
 588 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
 589 #define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)
 590
 591 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
 592
 593 #define GET_MATCHES_FOOTER(offset, maxLen) \
 594   offset = (unsigned)(GetMatchesSpec1((UInt32)lenLimit, curMatch, MF_PARAMS(p), \
 595   distances + offset, (UInt32)maxLen) - distances); MOVE_POS_RET;
 596
 597 #define SKIP_FOOTER \
 598   SkipMatchesSpec((UInt32)lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
 599
 600 #define UPDATE_maxLen { \
 601     ptrdiff_t diff = (ptrdiff_t)0 - d2; \
 602     const Byte *c = cur + maxLen; \
 603     const Byte *lim = cur + lenLimit; \
 604     for (; c != lim; c++) if (*(c + diff) != *c) break; \
 605     maxLen = (unsigned)(c - cur); }
 606
 607 static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 608 {
 609   unsigned offset;
 610   GET_MATCHES_HEADER(2)
 611   HASH2_CALC;
 612   curMatch = p->hash[hv];
 613   p->hash[hv] = p->pos;
 614   offset = 0;
 615   GET_MATCHES_FOOTER(offset, 1)
 616 }
 617
 618 UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 619 {
 620   unsigned offset;
 621   GET_MATCHES_HEADER(3)
 622   HASH_ZIP_CALC;
 623   curMatch = p->hash[hv];
 624   p->hash[hv] = p->pos;
 625   offset = 0;
 626   GET_MATCHES_FOOTER(offset, 2)
 627 }
 628
 629 static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 630 {
 631   UInt32 h2, d2, pos;
 632   unsigned maxLen, offset;
 633   UInt32 *hash;
 634   GET_MATCHES_HEADER(3)
 635
 636   HASH3_CALC;
 637
 638   hash = p->hash;
 639   pos = p->pos;
 640
 641   d2 = pos - hash[h2];
 642
 643   curMatch = (hash + kFix3HashSize)[hv];
 644
 645   hash[h2] = pos;
 646   (hash + kFix3HashSize)[hv] = pos;
 647
 648   maxLen = 2;
 649   offset = 0;
 650
 651   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 652   {
 653     UPDATE_maxLen
 654     distances[0] = (UInt32)maxLen;
 655     distances[1] = d2 - 1;
 656     offset = 2;
 657     if (maxLen == lenLimit)
 658     {
 659       SkipMatchesSpec((UInt32)lenLimit, curMatch, MF_PARAMS(p));
 660       MOVE_POS_RET;
 661     }
 662   }
 663
 664   GET_MATCHES_FOOTER(offset, maxLen)
 665 }
 666
 667 static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 668 {
 669   UInt32 h2, h3, d2, d3, pos;
 670   unsigned maxLen, offset;
 671   UInt32 *hash;
 672   GET_MATCHES_HEADER(4)
 673
 674   HASH4_CALC;
 675
 676   hash = p->hash;
 677   pos = p->pos;
 678
 679   d2 = pos - hash[                h2];
 680   d3 = pos - (hash + kFix3HashSize)[h3];
 681
 682   curMatch = (hash + kFix4HashSize)[hv];
 683
 684   hash[                h2] = pos;
 685   (hash + kFix3HashSize)[h3] = pos;
 686   (hash + kFix4HashSize)[hv] = pos;
 687
 688   maxLen = 0;
 689   offset = 0;
 690
 691   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 692   {
 693     maxLen = 2;
 694     distances[0] = 2;
 695     distances[1] = d2 - 1;
 696     offset = 2;
 697   }
 698
 699   if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 700   {
 701     maxLen = 3;
 702     distances[(size_t)offset + 1] = d3 - 1;
 703     offset += 2;
 704     d2 = d3;
 705   }
 706
 707   if (offset != 0)
 708   {
 709     UPDATE_maxLen
 710     distances[(size_t)offset - 2] = (UInt32)maxLen;
 711     if (maxLen == lenLimit)
 712     {
 713       SkipMatchesSpec((UInt32)lenLimit, curMatch, MF_PARAMS(p));
 714       MOVE_POS_RET;
 715     }
 716   }
 717
 718   if (maxLen < 3)
 719     maxLen = 3;
 720
 721   GET_MATCHES_FOOTER(offset, maxLen)
 722 }
 723
 724 /*
 725 static UInt32 Bt5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 726 {
 727   UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos;
 728   UInt32 *hash;
 729   GET_MATCHES_HEADER(5)
 730
 731   HASH5_CALC;
 732
 733   hash = p->hash;
 734   pos = p->pos;
 735
 736   d2 = pos - hash[                h2];
 737   d3 = pos - (hash + kFix3HashSize)[h3];
 738   d4 = pos - (hash + kFix4HashSize)[h4];
 739
 740   curMatch = (hash + kFix5HashSize)[hv];
 741
 742   hash[                h2] = pos;
 743   (hash + kFix3HashSize)[h3] = pos;
 744   (hash + kFix4HashSize)[h4] = pos;
 745   (hash + kFix5HashSize)[hv] = pos;
 746
 747   maxLen = 0;
 748   offset = 0;
 749
 750   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 751   {
 752     distances[0] = maxLen = 2;
 753     distances[1] = d2 - 1;
 754     offset = 2;
 755     if (*(cur - d2 + 2) == cur[2])
 756       distances[0] = maxLen = 3;
 757     else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 758     {
 759       distances[2] = maxLen = 3;
 760       distances[3] = d3 - 1;
 761       offset = 4;
 762       d2 = d3;
 763     }
 764   }
 765   else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 766   {
 767     distances[0] = maxLen = 3;
 768     distances[1] = d3 - 1;
 769     offset = 2;
 770     d2 = d3;
 771   }
 772
 773   if (d2 != d4 && d4 < p->cyclicBufferSize
 774       && *(cur - d4) == *cur
 775       && *(cur - d4 + 3) == *(cur + 3))
 776   {
 777     maxLen = 4;
 778     distances[(size_t)offset + 1] = d4 - 1;
 779     offset += 2;
 780     d2 = d4;
 781   }
 782
 783   if (offset != 0)
 784   {
 785     UPDATE_maxLen
 786     distances[(size_t)offset - 2] = maxLen;
 787     if (maxLen == lenLimit)
 788     {
 789       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
 790       MOVE_POS_RET;
 791     }
 792   }
 793
 794   if (maxLen < 4)
 795     maxLen = 4;
 796
 797   GET_MATCHES_FOOTER(offset, maxLen)
 798 }
 799 */
 800
 801 static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 802 {
 803   UInt32 h2, h3, d2, d3, pos;
 804   unsigned maxLen, offset;
 805   UInt32 *hash;
 806   GET_MATCHES_HEADER(4)
 807
 808   HASH4_CALC;
 809
 810   hash = p->hash;
 811   pos = p->pos;
 812
 813   d2 = pos - hash[                h2];
 814   d3 = pos - (hash + kFix3HashSize)[h3];
 815
 816   curMatch = (hash + kFix4HashSize)[hv];
 817
 818   hash[                h2] = pos;
 819   (hash + kFix3HashSize)[h3] = pos;
 820   (hash + kFix4HashSize)[hv] = pos;
 821
 822   maxLen = 0;
 823   offset = 0;
 824
 825   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 826   {
 827     maxLen = 2;
 828     distances[0] = 2;
 829     distances[1] = d2 - 1;
 830     offset = 2;
 831   }
 832
 833   if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 834   {
 835     maxLen = 3;
 836     distances[(size_t)offset + 1] = d3 - 1;
 837     offset += 2;
 838     d2 = d3;
 839   }
 840
 841   if (offset != 0)
 842   {
 843     UPDATE_maxLen
 844     distances[(size_t)offset - 2] = (UInt32)maxLen;
 845     if (maxLen == lenLimit)
 846     {
 847       p->son[p->cyclicBufferPos] = curMatch;
 848       MOVE_POS_RET;
 849     }
 850   }
 851
 852   if (maxLen < 3)
 853     maxLen = 3;
 854
 855   offset = (unsigned)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 856       distances + offset, maxLen) - (distances));
 857   MOVE_POS_RET
 858 }
 859
 860 /*
 861 static UInt32 Hc5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 862 {
 863   UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos
 864   UInt32 *hash;
 865   GET_MATCHES_HEADER(5)
 866
 867   HASH5_CALC;
 868
 869   hash = p->hash;
 870   pos = p->pos;
 871
 872   d2 = pos - hash[                h2];
 873   d3 = pos - (hash + kFix3HashSize)[h3];
 874   d4 = pos - (hash + kFix4HashSize)[h4];
 875
 876   curMatch = (hash + kFix5HashSize)[hv];
 877
 878   hash[                h2] = pos;
 879   (hash + kFix3HashSize)[h3] = pos;
 880   (hash + kFix4HashSize)[h4] = pos;
 881   (hash + kFix5HashSize)[hv] = pos;
 882
 883   maxLen = 0;
 884   offset = 0;
 885
 886   if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 887   {
 888     distances[0] = maxLen = 2;
 889     distances[1] = d2 - 1;
 890     offset = 2;
 891     if (*(cur - d2 + 2) == cur[2])
 892       distances[0] = maxLen = 3;
 893     else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 894     {
 895       distances[2] = maxLen = 3;
 896       distances[3] = d3 - 1;
 897       offset = 4;
 898       d2 = d3;
 899     }
 900   }
 901   else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 902   {
 903     distances[0] = maxLen = 3;
 904     distances[1] = d3 - 1;
 905     offset = 2;
 906     d2 = d3;
 907   }
 908
 909   if (d2 != d4 && d4 < p->cyclicBufferSize
 910       && *(cur - d4) == *cur
 911       && *(cur - d4 + 3) == *(cur + 3))
 912   {
 913     maxLen = 4;
 914     distances[(size_t)offset + 1] = d4 - 1;
 915     offset += 2;
 916     d2 = d4;
 917   }
 918
 919   if (offset != 0)
 920   {
 921     UPDATE_maxLen
 922     distances[(size_t)offset - 2] = maxLen;
 923     if (maxLen == lenLimit)
 924     {
 925       p->son[p->cyclicBufferPos] = curMatch;
 926       MOVE_POS_RET;
 927     }
 928   }
 929
 930   if (maxLen < 4)
 931     maxLen = 4;
 932
 933   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 934       distances + offset, maxLen) - (distances));
 935   MOVE_POS_RET
 936 }
 937 */
 938
 939 UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 940 {
 941   unsigned offset;
 942   GET_MATCHES_HEADER(3)
 943   HASH_ZIP_CALC;
 944   curMatch = p->hash[hv];
 945   p->hash[hv] = p->pos;
 946   offset = (unsigned)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 947       distances, 2) - (distances));
 948   MOVE_POS_RET
 949 }
 950
 951 static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 952 {
 953   do
 954   {
 955     SKIP_HEADER(2)
 956     HASH2_CALC;
 957     curMatch = p->hash[hv];
 958     p->hash[hv] = p->pos;
 959     SKIP_FOOTER
 960   }
 961   while (--num != 0);
 962 }
 963
 964 void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 965 {
 966   do
 967   {
 968     SKIP_HEADER(3)
 969     HASH_ZIP_CALC;
 970     curMatch = p->hash[hv];
 971     p->hash[hv] = p->pos;
 972     SKIP_FOOTER
 973   }
 974   while (--num != 0);
 975 }
 976
 977 static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 978 {
 979   do
 980   {
 981     UInt32 h2;
 982     UInt32 *hash;
 983     SKIP_HEADER(3)
 984     HASH3_CALC;
 985     hash = p->hash;
 986     curMatch = (hash + kFix3HashSize)[hv];
 987     hash[h2] =
 988     (hash + kFix3HashSize)[hv] = p->pos;
 989     SKIP_FOOTER
 990   }
 991   while (--num != 0);
 992 }
 993
 994 static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 995 {
 996   do
 997   {
 998     UInt32 h2, h3;
 999     UInt32 *hash;
1000     SKIP_HEADER(4)
1001     HASH4_CALC;
1002     hash = p->hash;
1003     curMatch = (hash + kFix4HashSize)[hv];
1004     hash[                h2] =
1005     (hash + kFix3HashSize)[h3] =
1006     (hash + kFix4HashSize)[hv] = p->pos;
1007     SKIP_FOOTER
1008   }
1009   while (--num != 0);
1010 }
1011
1012 /*
1013 static void Bt5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1014 {
1015   do
1016   {
1017     UInt32 h2, h3, h4;
1018     UInt32 *hash;
1019     SKIP_HEADER(5)
1020     HASH5_CALC;
1021     hash = p->hash;
1022     curMatch = (hash + kFix5HashSize)[hv];
1023     hash[                h2] =
1024     (hash + kFix3HashSize)[h3] =
1025     (hash + kFix4HashSize)[h4] =
1026     (hash + kFix5HashSize)[hv] = p->pos;
1027     SKIP_FOOTER
1028   }
1029   while (--num != 0);
1030 }
1031 */
1032
1033 static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1034 {
1035   do
1036   {
1037     UInt32 h2, h3;
1038     UInt32 *hash;
1039     SKIP_HEADER(4)
1040     HASH4_CALC;
1041     hash = p->hash;
1042     curMatch = (hash + kFix4HashSize)[hv];
1043     hash[                h2] =
1044     (hash + kFix3HashSize)[h3] =
1045     (hash + kFix4HashSize)[hv] = p->pos;
1046     p->son[p->cyclicBufferPos] = curMatch;
1047     MOVE_POS
1048   }
1049   while (--num != 0);
1050 }
1051
1052 /*
1053 static void Hc5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1054 {
1055   do
1056   {
1057     UInt32 h2, h3, h4;
1058     UInt32 *hash;
1059     SKIP_HEADER(5)
1060     HASH5_CALC;
1061     hash = p->hash;
1062     curMatch = hash + kFix5HashSize)[hv];
1063     hash[                h2] =
1064     (hash + kFix3HashSize)[h3] =
1065     (hash + kFix4HashSize)[h4] =
1066     (hash + kFix5HashSize)[hv] = p->pos;
1067     p->son[p->cyclicBufferPos] = curMatch;
1068     MOVE_POS
1069   }
1070   while (--num != 0);
1071 }
1072 */
1073
1074 void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
1075 {
1076   do
1077   {
1078     SKIP_HEADER(3)
1079     HASH_ZIP_CALC;
1080     curMatch = p->hash[hv];
1081     p->hash[hv] = p->pos;
1082     p->son[p->cyclicBufferPos] = curMatch;
1083     MOVE_POS
1084   }
1085   while (--num != 0);
1086 }
1087
1088 void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
1089 {
1090   vTable->Init = (Mf_Init_Func)MatchFinder_Init;
1091   vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
1092   vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
1093   if (!p->btMode)
1094   {
1095     /* if (p->numHashBytes <= 4) */
1096     {
1097       vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
1098       vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
1099     }
1100     /*
1101     else
1102     {
1103       vTable->GetMatches = (Mf_GetMatches_Func)Hc5_MatchFinder_GetMatches;
1104       vTable->Skip = (Mf_Skip_Func)Hc5_MatchFinder_Skip;
1105     }
1106     */
1107   }
1108   else if (p->numHashBytes == 2)
1109   {
1110     vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
1111     vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
1112   }
1113   else if (p->numHashBytes == 3)
1114   {
1115     vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
1116     vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
1117   }
1118   else /* if (p->numHashBytes == 4) */
1119   {
1120     vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
1121     vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
1122   }
1123   /*
1124   else
1125   {
1126     vTable->GetMatches = (Mf_GetMatches_Func)Bt5_MatchFinder_GetMatches;
1127     vTable->Skip = (Mf_Skip_Func)Bt5_MatchFinder_Skip;
1128   }
1129   */
1130 }