git.cworth.org Git - vogl/blob - src/voglcore/lzma_LzFind.cpp

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