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