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