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