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

   1 /** @file
   2   LzFind.c
   3
   4   Based on LZMA SDK 4.65:
   5     LzFind.c -- Match finder for LZ algorithms
   6     2008-10-04 : Igor Pavlov : Public domain
   7
   8   Copyright (c) 2009, Intel Corporation<BR>
   9   All rights reserved. This program and the accompanying materials
  10   are licensed and made available under the terms and conditions of the BSD License
  11   which accompanies this distribution.  The full text of the license may be found at
  12   http://opensource.org/licenses/bsd-license.php
  13
  14   THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  15   WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  16
  17 **/
  18
  19 #ifndef EFIAPI
  20
  21 #include <string.h>
  22
  23 #endif // !EFIAPI
  24
  25 #include "LzFind.h"
  26 #include "LzHash.h"
  27
  28 #define kEmptyHashValue 0
  29 #define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
  30 #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
  31 #define kNormalizeMask (~(kNormalizeStepMin - 1))
  32 #define kMaxHistorySize ((UInt32)3 << 30)
  33
  34 #define kStartMaxLen 3
  35
  36 static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
  37 {
  38   if (!p->directInput)
  39   {
  40     alloc->Free(alloc, p->bufferBase);
  41     p->bufferBase = 0;
  42   }
  43 }
  44
  45 /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
  46
  47 static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)
  48 {
  49   UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
  50   if (p->directInput)
  51   {
  52     p->blockSize = blockSize;
  53     return 1;
  54   }
  55   if (p->bufferBase == 0 || p->blockSize != blockSize)
  56   {
  57     LzInWindow_Free(p, alloc);
  58     p->blockSize = blockSize;
  59     p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
  60   }
  61   return (p->bufferBase != 0);
  62 }
  63
  64 Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
  65 Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[index]; }
  66
  67 UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
  68
  69 void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
  70 {
  71   p->posLimit -= subValue;
  72   p->pos -= subValue;
  73   p->streamPos -= subValue;
  74 }
  75
  76 static void MatchFinder_ReadBlock(CMatchFinder *p)
  77 {
  78   if (p->streamEndWasReached || p->result != SZ_OK)
  79     return;
  80   for (;;)
  81   {
  82     Byte *dest = p->buffer + (p->streamPos - p->pos);
  83     size_t size = (p->bufferBase + p->blockSize - dest);
  84     if (size == 0)
  85       return;
  86     p->result = p->stream->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->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->skipModeBits = 0; */
 135   p->directInput = 0;
 136   p->bigHash = 0;
 137 }
 138
 139 #define kCrcPoly 0xEDB88320
 140
 141 void MatchFinder_Construct(CMatchFinder *p)
 142 {
 143   UInt32 i;
 144   p->bufferBase = 0;
 145   p->directInput = 0;
 146   p->hash = 0;
 147   MatchFinder_SetDefaultSettings(p);
 148
 149   for (i = 0; i < 256; i++)
 150   {
 151     UInt32 r = i;
 152     int j;
 153     for (j = 0; j < 8; j++)
 154       r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
 155     p->crc[i] = r;
 156   }
 157 }
 158
 159 static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
 160 {
 161   alloc->Free(alloc, p->hash);
 162   p->hash = 0;
 163 }
 164
 165 void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
 166 {
 167   MatchFinder_FreeThisClassMemory(p, alloc);
 168   LzInWindow_Free(p, alloc);
 169 }
 170
 171 static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)
 172 {
 173   size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
 174   if (sizeInBytes / sizeof(CLzRef) != num)
 175     return 0;
 176   return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
 177 }
 178
 179 int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
 180     UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
 181     ISzAlloc *alloc)
 182 {
 183   UInt32 sizeReserv;
 184   if (historySize > kMaxHistorySize)
 185   {
 186     MatchFinder_Free(p, alloc);
 187     return 0;
 188   }
 189   sizeReserv = historySize >> 1;
 190   if (historySize > ((UInt32)2 << 30))
 191     sizeReserv = historySize >> 2;
 192   sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
 193
 194   p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
 195   p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
 196   /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
 197   if (LzInWindow_Create(p, sizeReserv, alloc))
 198   {
 199     UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;
 200     UInt32 hs;
 201     p->matchMaxLen = matchMaxLen;
 202     {
 203       p->fixedHashSize = 0;
 204       if (p->numHashBytes == 2)
 205         hs = (1 << 16) - 1;
 206       else
 207       {
 208         hs = historySize - 1;
 209         hs |= (hs >> 1);
 210         hs |= (hs >> 2);
 211         hs |= (hs >> 4);
 212         hs |= (hs >> 8);
 213         hs >>= 1;
 214         /* hs >>= p->skipModeBits; */
 215         hs |= 0xFFFF; /* don't change it! It's required for Deflate */
 216         if (hs > (1 << 24))
 217         {
 218           if (p->numHashBytes == 3)
 219             hs = (1 << 24) - 1;
 220           else
 221             hs >>= 1;
 222         }
 223       }
 224       p->hashMask = hs;
 225       hs++;
 226       if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
 227       if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
 228       if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
 229       hs += p->fixedHashSize;
 230     }
 231
 232     {
 233       UInt32 prevSize = p->hashSizeSum + p->numSons;
 234       UInt32 newSize;
 235       p->historySize = historySize;
 236       p->hashSizeSum = hs;
 237       p->cyclicBufferSize = newCyclicBufferSize;
 238       p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
 239       newSize = p->hashSizeSum + p->numSons;
 240       if (p->hash != 0 && prevSize == newSize)
 241         return 1;
 242       MatchFinder_FreeThisClassMemory(p, alloc);
 243       p->hash = AllocRefs(newSize, alloc);
 244       if (p->hash != 0)
 245       {
 246         p->son = p->hash + p->hashSizeSum;
 247         return 1;
 248       }
 249     }
 250   }
 251   MatchFinder_Free(p, alloc);
 252   return 0;
 253 }
 254
 255 static void MatchFinder_SetLimits(CMatchFinder *p)
 256 {
 257   UInt32 limit = kMaxValForNormalize - p->pos;
 258   UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
 259   if (limit2 < limit)
 260     limit = limit2;
 261   limit2 = p->streamPos - p->pos;
 262   if (limit2 <= p->keepSizeAfter)
 263   {
 264     if (limit2 > 0)
 265       limit2 = 1;
 266   }
 267   else
 268     limit2 -= p->keepSizeAfter;
 269   if (limit2 < limit)
 270     limit = limit2;
 271   {
 272     UInt32 lenLimit = p->streamPos - p->pos;
 273     if (lenLimit > p->matchMaxLen)
 274       lenLimit = p->matchMaxLen;
 275     p->lenLimit = lenLimit;
 276   }
 277   p->posLimit = p->pos + limit;
 278 }
 279
 280 void MatchFinder_Init(CMatchFinder *p)
 281 {
 282   UInt32 i;
 283   for (i = 0; i < p->hashSizeSum; i++)
 284     p->hash[i] = kEmptyHashValue;
 285   p->cyclicBufferPos = 0;
 286   p->buffer = p->bufferBase;
 287   p->pos = p->streamPos = p->cyclicBufferSize;
 288   p->result = SZ_OK;
 289   p->streamEndWasReached = 0;
 290   MatchFinder_ReadBlock(p);
 291   MatchFinder_SetLimits(p);
 292 }
 293
 294 static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
 295 {
 296   return (p->pos - p->historySize - 1) & kNormalizeMask;
 297 }
 298
 299 void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
 300 {
 301   UInt32 i;
 302   for (i = 0; i < numItems; i++)
 303   {
 304     UInt32 value = items[i];
 305     if (value <= subValue)
 306       value = kEmptyHashValue;
 307     else
 308       value -= subValue;
 309     items[i] = value;
 310   }
 311 }
 312
 313 static void MatchFinder_Normalize(CMatchFinder *p)
 314 {
 315   UInt32 subValue = MatchFinder_GetSubValue(p);
 316   MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
 317   MatchFinder_ReduceOffsets(p, subValue);
 318 }
 319
 320 static void MatchFinder_CheckLimits(CMatchFinder *p)
 321 {
 322   if (p->pos == kMaxValForNormalize)
 323     MatchFinder_Normalize(p);
 324   if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
 325     MatchFinder_CheckAndMoveAndRead(p);
 326   if (p->cyclicBufferPos == p->cyclicBufferSize)
 327     p->cyclicBufferPos = 0;
 328   MatchFinder_SetLimits(p);
 329 }
 330
 331 static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 332     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
 333     UInt32 *distances, UInt32 maxLen)
 334 {
 335   son[_cyclicBufferPos] = curMatch;
 336   for (;;)
 337   {
 338     UInt32 delta = pos - curMatch;
 339     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 340       return distances;
 341     {
 342       const Byte *pb = cur - delta;
 343       curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
 344       if (pb[maxLen] == cur[maxLen] && *pb == *cur)
 345       {
 346         UInt32 len = 0;
 347         while (++len != lenLimit)
 348           if (pb[len] != cur[len])
 349             break;
 350         if (maxLen < len)
 351         {
 352           *distances++ = maxLen = len;
 353           *distances++ = delta - 1;
 354           if (len == lenLimit)
 355             return distances;
 356         }
 357       }
 358     }
 359   }
 360 }
 361
 362 UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 363     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
 364     UInt32 *distances, UInt32 maxLen)
 365 {
 366   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 367   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
 368   UInt32 len0 = 0, len1 = 0;
 369   for (;;)
 370   {
 371     UInt32 delta = pos - curMatch;
 372     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 373     {
 374       *ptr0 = *ptr1 = kEmptyHashValue;
 375       return distances;
 376     }
 377     {
 378       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
 379       const Byte *pb = cur - delta;
 380       UInt32 len = (len0 < len1 ? len0 : len1);
 381       if (pb[len] == cur[len])
 382       {
 383         if (++len != lenLimit && pb[len] == cur[len])
 384           while (++len != lenLimit)
 385             if (pb[len] != cur[len])
 386               break;
 387         if (maxLen < len)
 388         {
 389           *distances++ = maxLen = len;
 390           *distances++ = delta - 1;
 391           if (len == lenLimit)
 392           {
 393             *ptr1 = pair[0];
 394             *ptr0 = pair[1];
 395             return distances;
 396           }
 397         }
 398       }
 399       if (pb[len] < cur[len])
 400       {
 401         *ptr1 = curMatch;
 402         ptr1 = pair + 1;
 403         curMatch = *ptr1;
 404         len1 = len;
 405       }
 406       else
 407       {
 408         *ptr0 = curMatch;
 409         ptr0 = pair;
 410         curMatch = *ptr0;
 411         len0 = len;
 412       }
 413     }
 414   }
 415 }
 416
 417 static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 418     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
 419 {
 420   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 421   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
 422   UInt32 len0 = 0, len1 = 0;
 423   for (;;)
 424   {
 425     UInt32 delta = pos - curMatch;
 426     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 427     {
 428       *ptr0 = *ptr1 = kEmptyHashValue;
 429       return;
 430     }
 431     {
 432       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
 433       const Byte *pb = cur - delta;
 434       UInt32 len = (len0 < len1 ? len0 : len1);
 435       if (pb[len] == cur[len])
 436       {
 437         while (++len != lenLimit)
 438           if (pb[len] != cur[len])
 439             break;
 440         {
 441           if (len == lenLimit)
 442           {
 443             *ptr1 = pair[0];
 444             *ptr0 = pair[1];
 445             return;
 446           }
 447         }
 448       }
 449       if (pb[len] < cur[len])
 450       {
 451         *ptr1 = curMatch;
 452         ptr1 = pair + 1;
 453         curMatch = *ptr1;
 454         len1 = len;
 455       }
 456       else
 457       {
 458         *ptr0 = curMatch;
 459         ptr0 = pair;
 460         curMatch = *ptr0;
 461         len0 = len;
 462       }
 463     }
 464   }
 465 }
 466
 467 #define MOVE_POS \
 468   ++p->cyclicBufferPos; \
 469   p->buffer++; \
 470   if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
 471
 472 #define MOVE_POS_RET MOVE_POS return offset;
 473
 474 static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
 475
 476 #define GET_MATCHES_HEADER2(minLen, ret_op) \
 477   UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \
 478   lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
 479   cur = p->buffer;
 480
 481 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
 482 #define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)
 483
 484 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
 485
 486 #define GET_MATCHES_FOOTER(offset, maxLen) \
 487   offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
 488   distances + offset, maxLen) - distances); MOVE_POS_RET;
 489
 490 #define SKIP_FOOTER \
 491   SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
 492
 493 static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 494 {
 495   UInt32 offset;
 496   GET_MATCHES_HEADER(2)
 497   HASH2_CALC;
 498   curMatch = p->hash[hashValue];
 499   p->hash[hashValue] = p->pos;
 500   offset = 0;
 501   GET_MATCHES_FOOTER(offset, 1)
 502 }
 503
 504 UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 505 {
 506   UInt32 offset;
 507   GET_MATCHES_HEADER(3)
 508   HASH_ZIP_CALC;
 509   curMatch = p->hash[hashValue];
 510   p->hash[hashValue] = p->pos;
 511   offset = 0;
 512   GET_MATCHES_FOOTER(offset, 2)
 513 }
 514
 515 static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 516 {
 517   UInt32 hash2Value, delta2, maxLen, offset;
 518   GET_MATCHES_HEADER(3)
 519
 520   HASH3_CALC;
 521
 522   delta2 = p->pos - p->hash[hash2Value];
 523   curMatch = p->hash[kFix3HashSize + hashValue];
 524
 525   p->hash[hash2Value] =
 526   p->hash[kFix3HashSize + hashValue] = p->pos;
 527
 528
 529   maxLen = 2;
 530   offset = 0;
 531   if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
 532   {
 533     for (; maxLen != lenLimit; maxLen++)
 534       if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
 535         break;
 536     distances[0] = maxLen;
 537     distances[1] = delta2 - 1;
 538     offset = 2;
 539     if (maxLen == lenLimit)
 540     {
 541       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
 542       MOVE_POS_RET;
 543     }
 544   }
 545   GET_MATCHES_FOOTER(offset, maxLen)
 546 }
 547
 548 static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 549 {
 550   UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
 551   GET_MATCHES_HEADER(4)
 552
 553   HASH4_CALC;
 554
 555   delta2 = p->pos - p->hash[                hash2Value];
 556   delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
 557   curMatch = p->hash[kFix4HashSize + hashValue];
 558
 559   p->hash[                hash2Value] =
 560   p->hash[kFix3HashSize + hash3Value] =
 561   p->hash[kFix4HashSize + hashValue] = p->pos;
 562
 563   maxLen = 1;
 564   offset = 0;
 565   if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
 566   {
 567     distances[0] = maxLen = 2;
 568     distances[1] = delta2 - 1;
 569     offset = 2;
 570   }
 571   if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
 572   {
 573     maxLen = 3;
 574     distances[offset + 1] = delta3 - 1;
 575     offset += 2;
 576     delta2 = delta3;
 577   }
 578   if (offset != 0)
 579   {
 580     for (; maxLen != lenLimit; maxLen++)
 581       if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
 582         break;
 583     distances[offset - 2] = maxLen;
 584     if (maxLen == lenLimit)
 585     {
 586       SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
 587       MOVE_POS_RET;
 588     }
 589   }
 590   if (maxLen < 3)
 591     maxLen = 3;
 592   GET_MATCHES_FOOTER(offset, maxLen)
 593 }
 594
 595 static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 596 {
 597   UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
 598   GET_MATCHES_HEADER(4)
 599
 600   HASH4_CALC;
 601
 602   delta2 = p->pos - p->hash[                hash2Value];
 603   delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
 604   curMatch = p->hash[kFix4HashSize + hashValue];
 605
 606   p->hash[                hash2Value] =
 607   p->hash[kFix3HashSize + hash3Value] =
 608   p->hash[kFix4HashSize + hashValue] = p->pos;
 609
 610   maxLen = 1;
 611   offset = 0;
 612   if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
 613   {
 614     distances[0] = maxLen = 2;
 615     distances[1] = delta2 - 1;
 616     offset = 2;
 617   }
 618   if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
 619   {
 620     maxLen = 3;
 621     distances[offset + 1] = delta3 - 1;
 622     offset += 2;
 623     delta2 = delta3;
 624   }
 625   if (offset != 0)
 626   {
 627     for (; maxLen != lenLimit; maxLen++)
 628       if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
 629         break;
 630     distances[offset - 2] = maxLen;
 631     if (maxLen == lenLimit)
 632     {
 633       p->son[p->cyclicBufferPos] = curMatch;
 634       MOVE_POS_RET;
 635     }
 636   }
 637   if (maxLen < 3)
 638     maxLen = 3;
 639   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 640     distances + offset, maxLen) - (distances));
 641   MOVE_POS_RET
 642 }
 643
 644 UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 645 {
 646   UInt32 offset;
 647   GET_MATCHES_HEADER(3)
 648   HASH_ZIP_CALC;
 649   curMatch = p->hash[hashValue];
 650   p->hash[hashValue] = p->pos;
 651   offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 652     distances, 2) - (distances));
 653   MOVE_POS_RET
 654 }
 655
 656 static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 657 {
 658   do
 659   {
 660     SKIP_HEADER(2)
 661     HASH2_CALC;
 662     curMatch = p->hash[hashValue];
 663     p->hash[hashValue] = p->pos;
 664     SKIP_FOOTER
 665   }
 666   while (--num != 0);
 667 }
 668
 669 void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 670 {
 671   do
 672   {
 673     SKIP_HEADER(3)
 674     HASH_ZIP_CALC;
 675     curMatch = p->hash[hashValue];
 676     p->hash[hashValue] = p->pos;
 677     SKIP_FOOTER
 678   }
 679   while (--num != 0);
 680 }
 681
 682 static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 683 {
 684   do
 685   {
 686     UInt32 hash2Value;
 687     SKIP_HEADER(3)
 688     HASH3_CALC;
 689     curMatch = p->hash[kFix3HashSize + hashValue];
 690     p->hash[hash2Value] =
 691     p->hash[kFix3HashSize + hashValue] = p->pos;
 692     SKIP_FOOTER
 693   }
 694   while (--num != 0);
 695 }
 696
 697 static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 698 {
 699   do
 700   {
 701     UInt32 hash2Value, hash3Value;
 702     SKIP_HEADER(4)
 703     HASH4_CALC;
 704     curMatch = p->hash[kFix4HashSize + hashValue];
 705     p->hash[                hash2Value] =
 706     p->hash[kFix3HashSize + hash3Value] = p->pos;
 707     p->hash[kFix4HashSize + hashValue] = p->pos;
 708     SKIP_FOOTER
 709   }
 710   while (--num != 0);
 711 }
 712
 713 static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 714 {
 715   do
 716   {
 717     UInt32 hash2Value, hash3Value;
 718     SKIP_HEADER(4)
 719     HASH4_CALC;
 720     curMatch = p->hash[kFix4HashSize + hashValue];
 721     p->hash[                hash2Value] =
 722     p->hash[kFix3HashSize + hash3Value] =
 723     p->hash[kFix4HashSize + hashValue] = p->pos;
 724     p->son[p->cyclicBufferPos] = curMatch;
 725     MOVE_POS
 726   }
 727   while (--num != 0);
 728 }
 729
 730 void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 731 {
 732   do
 733   {
 734     SKIP_HEADER(3)
 735     HASH_ZIP_CALC;
 736     curMatch = p->hash[hashValue];
 737     p->hash[hashValue] = p->pos;
 738     p->son[p->cyclicBufferPos] = curMatch;
 739     MOVE_POS
 740   }
 741   while (--num != 0);
 742 }
 743
 744 void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
 745 {
 746   vTable->Init = (Mf_Init_Func)MatchFinder_Init;
 747   vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
 748   vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
 749   vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
 750   if (!p->btMode)
 751   {
 752     vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
 753     vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
 754   }
 755   else if (p->numHashBytes == 2)
 756   {
 757     vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
 758     vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
 759   }
 760   else if (p->numHashBytes == 3)
 761   {
 762     vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
 763     vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
 764   }
 765   else
 766   {
 767     vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
 768     vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
 769   }
 770 }