lib/LzFind.c

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