all repos — mgba @ dab12cf5c674542cae0db7708c333035255fbc65

mGBA Game Boy Advance Emulator

src/third-party/lzma/LzFind.c (view raw)

   1/* LzFind.c -- Match finder for LZ algorithms
   22015-10-15 : Igor Pavlov : Public domain */
   3
   4#include "Precomp.h"
   5
   6#include <string.h>
   7
   8#include "LzFind.h"
   9#include "LzHash.h"
  10
  11#define kEmptyHashValue 0
  12#define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
  13#define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
  14#define kNormalizeMask (~(UInt32)(kNormalizeStepMin - 1))
  15#define kMaxHistorySize ((UInt32)7 << 29)
  16
  17#define kStartMaxLen 3
  18
  19static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
  20{
  21  if (!p->directInput)
  22  {
  23    alloc->Free(alloc, p->bufferBase);
  24    p->bufferBase = NULL;
  25  }
  26}
  27
  28/* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
  29
  30static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)
  31{
  32  UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
  33  if (p->directInput)
  34  {
  35    p->blockSize = blockSize;
  36    return 1;
  37  }
  38  if (!p->bufferBase || p->blockSize != blockSize)
  39  {
  40    LzInWindow_Free(p, alloc);
  41    p->blockSize = blockSize;
  42    p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
  43  }
  44  return (p->bufferBase != NULL);
  45}
  46
  47Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
  48
  49UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
  50
  51void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
  52{
  53  p->posLimit -= subValue;
  54  p->pos -= subValue;
  55  p->streamPos -= subValue;
  56}
  57
  58static void MatchFinder_ReadBlock(CMatchFinder *p)
  59{
  60  if (p->streamEndWasReached || p->result != SZ_OK)
  61    return;
  62
  63  /* We use (p->streamPos - p->pos) value. (p->streamPos < p->pos) is allowed. */
  64
  65  if (p->directInput)
  66  {
  67    UInt32 curSize = 0xFFFFFFFF - (p->streamPos - p->pos);
  68    if (curSize > p->directInputRem)
  69      curSize = (UInt32)p->directInputRem;
  70    p->directInputRem -= curSize;
  71    p->streamPos += curSize;
  72    if (p->directInputRem == 0)
  73      p->streamEndWasReached = 1;
  74    return;
  75  }
  76  
  77  for (;;)
  78  {
  79    Byte *dest = p->buffer + (p->streamPos - p->pos);
  80    size_t size = (p->bufferBase + p->blockSize - dest);
  81    if (size == 0)
  82      return;
  83
  84    p->result = p->stream->Read(p->stream, dest, &size);
  85    if (p->result != SZ_OK)
  86      return;
  87    if (size == 0)
  88    {
  89      p->streamEndWasReached = 1;
  90      return;
  91    }
  92    p->streamPos += (UInt32)size;
  93    if (p->streamPos - p->pos > p->keepSizeAfter)
  94      return;
  95  }
  96}
  97
  98void MatchFinder_MoveBlock(CMatchFinder *p)
  99{
 100  memmove(p->bufferBase,
 101      p->buffer - p->keepSizeBefore,
 102      (size_t)(p->streamPos - p->pos) + p->keepSizeBefore);
 103  p->buffer = p->bufferBase + p->keepSizeBefore;
 104}
 105
 106int MatchFinder_NeedMove(CMatchFinder *p)
 107{
 108  if (p->directInput)
 109    return 0;
 110  /* if (p->streamEndWasReached) return 0; */
 111  return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
 112}
 113
 114void 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
 122static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
 123{
 124  if (MatchFinder_NeedMove(p))
 125    MatchFinder_MoveBlock(p);
 126  MatchFinder_ReadBlock(p);
 127}
 128
 129static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
 130{
 131  p->cutValue = 32;
 132  p->btMode = 1;
 133  p->numHashBytes = 4;
 134  p->bigHash = 0;
 135}
 136
 137#define kCrcPoly 0xEDB88320
 138
 139void MatchFinder_Construct(CMatchFinder *p)
 140{
 141  UInt32 i;
 142  p->bufferBase = NULL;
 143  p->directInput = 0;
 144  p->hash = NULL;
 145  MatchFinder_SetDefaultSettings(p);
 146
 147  for (i = 0; i < 256; i++)
 148  {
 149    UInt32 r = i;
 150    unsigned j;
 151    for (j = 0; j < 8; j++)
 152      r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
 153    p->crc[i] = r;
 154  }
 155}
 156
 157static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
 158{
 159  alloc->Free(alloc, p->hash);
 160  p->hash = NULL;
 161}
 162
 163void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
 164{
 165  MatchFinder_FreeThisClassMemory(p, alloc);
 166  LzInWindow_Free(p, alloc);
 167}
 168
 169static CLzRef* AllocRefs(size_t num, ISzAlloc *alloc)
 170{
 171  size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
 172  if (sizeInBytes / sizeof(CLzRef) != num)
 173    return NULL;
 174  return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
 175}
 176
 177int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
 178    UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
 179    ISzAlloc *alloc)
 180{
 181  UInt32 sizeReserv;
 182  
 183  if (historySize > kMaxHistorySize)
 184  {
 185    MatchFinder_Free(p, alloc);
 186    return 0;
 187  }
 188  
 189  sizeReserv = historySize >> 1;
 190       if (historySize >= ((UInt32)3 << 30)) sizeReserv = historySize >> 3;
 191  else if (historySize >= ((UInt32)2 << 30)) sizeReserv = historySize >> 2;
 192  
 193  sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
 194
 195  p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
 196  p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
 197  
 198  /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
 199  
 200  if (LzInWindow_Create(p, sizeReserv, alloc))
 201  {
 202    UInt32 newCyclicBufferSize = historySize + 1;
 203    UInt32 hs;
 204    p->matchMaxLen = matchMaxLen;
 205    {
 206      p->fixedHashSize = 0;
 207      if (p->numHashBytes == 2)
 208        hs = (1 << 16) - 1;
 209      else
 210      {
 211        hs = historySize - 1;
 212        hs |= (hs >> 1);
 213        hs |= (hs >> 2);
 214        hs |= (hs >> 4);
 215        hs |= (hs >> 8);
 216        hs >>= 1;
 217        hs |= 0xFFFF; /* don't change it! It's required for Deflate */
 218        if (hs > (1 << 24))
 219        {
 220          if (p->numHashBytes == 3)
 221            hs = (1 << 24) - 1;
 222          else
 223            hs >>= 1;
 224          /* if (bigHash) mode, GetHeads4b() in LzFindMt.c needs (hs >= ((1 << 24) - 1))) */
 225        }
 226      }
 227      p->hashMask = hs;
 228      hs++;
 229      if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
 230      if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
 231      if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
 232      hs += p->fixedHashSize;
 233    }
 234
 235    {
 236      size_t newSize;
 237      size_t numSons;
 238      p->historySize = historySize;
 239      p->hashSizeSum = hs;
 240      p->cyclicBufferSize = newCyclicBufferSize;
 241      
 242      numSons = newCyclicBufferSize;
 243      if (p->btMode)
 244        numSons <<= 1;
 245      newSize = hs + numSons;
 246
 247      if (p->hash && p->numRefs == newSize)
 248        return 1;
 249      
 250      MatchFinder_FreeThisClassMemory(p, alloc);
 251      p->numRefs = newSize;
 252      p->hash = AllocRefs(newSize, alloc);
 253      
 254      if (p->hash)
 255      {
 256        p->son = p->hash + p->hashSizeSum;
 257        return 1;
 258      }
 259    }
 260  }
 261
 262  MatchFinder_Free(p, alloc);
 263  return 0;
 264}
 265
 266static void MatchFinder_SetLimits(CMatchFinder *p)
 267{
 268  UInt32 limit = kMaxValForNormalize - p->pos;
 269  UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
 270  
 271  if (limit2 < limit)
 272    limit = limit2;
 273  limit2 = p->streamPos - p->pos;
 274  
 275  if (limit2 <= p->keepSizeAfter)
 276  {
 277    if (limit2 > 0)
 278      limit2 = 1;
 279  }
 280  else
 281    limit2 -= p->keepSizeAfter;
 282  
 283  if (limit2 < limit)
 284    limit = limit2;
 285  
 286  {
 287    UInt32 lenLimit = p->streamPos - p->pos;
 288    if (lenLimit > p->matchMaxLen)
 289      lenLimit = p->matchMaxLen;
 290    p->lenLimit = lenLimit;
 291  }
 292  p->posLimit = p->pos + limit;
 293}
 294
 295void MatchFinder_Init_2(CMatchFinder *p, int readData)
 296{
 297  UInt32 i;
 298  UInt32 *hash = p->hash;
 299  UInt32 num = p->hashSizeSum;
 300  for (i = 0; i < num; i++)
 301    hash[i] = kEmptyHashValue;
 302  
 303  p->cyclicBufferPos = 0;
 304  p->buffer = p->bufferBase;
 305  p->pos = p->streamPos = p->cyclicBufferSize;
 306  p->result = SZ_OK;
 307  p->streamEndWasReached = 0;
 308  
 309  if (readData)
 310    MatchFinder_ReadBlock(p);
 311  
 312  MatchFinder_SetLimits(p);
 313}
 314
 315void MatchFinder_Init(CMatchFinder *p)
 316{
 317  MatchFinder_Init_2(p, True);
 318}
 319  
 320static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
 321{
 322  return (p->pos - p->historySize - 1) & kNormalizeMask;
 323}
 324
 325void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, size_t numItems)
 326{
 327  size_t i;
 328  for (i = 0; i < numItems; i++)
 329  {
 330    UInt32 value = items[i];
 331    if (value <= subValue)
 332      value = kEmptyHashValue;
 333    else
 334      value -= subValue;
 335    items[i] = value;
 336  }
 337}
 338
 339static void MatchFinder_Normalize(CMatchFinder *p)
 340{
 341  UInt32 subValue = MatchFinder_GetSubValue(p);
 342  MatchFinder_Normalize3(subValue, p->hash, p->numRefs);
 343  MatchFinder_ReduceOffsets(p, subValue);
 344}
 345
 346static void MatchFinder_CheckLimits(CMatchFinder *p)
 347{
 348  if (p->pos == kMaxValForNormalize)
 349    MatchFinder_Normalize(p);
 350  if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
 351    MatchFinder_CheckAndMoveAndRead(p);
 352  if (p->cyclicBufferPos == p->cyclicBufferSize)
 353    p->cyclicBufferPos = 0;
 354  MatchFinder_SetLimits(p);
 355}
 356
 357static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 358    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
 359    UInt32 *distances, UInt32 maxLen)
 360{
 361  son[_cyclicBufferPos] = curMatch;
 362  for (;;)
 363  {
 364    UInt32 delta = pos - curMatch;
 365    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 366      return distances;
 367    {
 368      const Byte *pb = cur - delta;
 369      curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
 370      if (pb[maxLen] == cur[maxLen] && *pb == *cur)
 371      {
 372        UInt32 len = 0;
 373        while (++len != lenLimit)
 374          if (pb[len] != cur[len])
 375            break;
 376        if (maxLen < len)
 377        {
 378          *distances++ = maxLen = len;
 379          *distances++ = delta - 1;
 380          if (len == lenLimit)
 381            return distances;
 382        }
 383      }
 384    }
 385  }
 386}
 387
 388UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 389    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
 390    UInt32 *distances, UInt32 maxLen)
 391{
 392  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 393  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
 394  UInt32 len0 = 0, len1 = 0;
 395  for (;;)
 396  {
 397    UInt32 delta = pos - curMatch;
 398    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 399    {
 400      *ptr0 = *ptr1 = kEmptyHashValue;
 401      return distances;
 402    }
 403    {
 404      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
 405      const Byte *pb = cur - delta;
 406      UInt32 len = (len0 < len1 ? len0 : len1);
 407      if (pb[len] == cur[len])
 408      {
 409        if (++len != lenLimit && pb[len] == cur[len])
 410          while (++len != lenLimit)
 411            if (pb[len] != cur[len])
 412              break;
 413        if (maxLen < len)
 414        {
 415          *distances++ = maxLen = len;
 416          *distances++ = delta - 1;
 417          if (len == lenLimit)
 418          {
 419            *ptr1 = pair[0];
 420            *ptr0 = pair[1];
 421            return distances;
 422          }
 423        }
 424      }
 425      if (pb[len] < cur[len])
 426      {
 427        *ptr1 = curMatch;
 428        ptr1 = pair + 1;
 429        curMatch = *ptr1;
 430        len1 = len;
 431      }
 432      else
 433      {
 434        *ptr0 = curMatch;
 435        ptr0 = pair;
 436        curMatch = *ptr0;
 437        len0 = len;
 438      }
 439    }
 440  }
 441}
 442
 443static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
 444    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
 445{
 446  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 447  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
 448  UInt32 len0 = 0, len1 = 0;
 449  for (;;)
 450  {
 451    UInt32 delta = pos - curMatch;
 452    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
 453    {
 454      *ptr0 = *ptr1 = kEmptyHashValue;
 455      return;
 456    }
 457    {
 458      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
 459      const Byte *pb = cur - delta;
 460      UInt32 len = (len0 < len1 ? len0 : len1);
 461      if (pb[len] == cur[len])
 462      {
 463        while (++len != lenLimit)
 464          if (pb[len] != cur[len])
 465            break;
 466        {
 467          if (len == lenLimit)
 468          {
 469            *ptr1 = pair[0];
 470            *ptr0 = pair[1];
 471            return;
 472          }
 473        }
 474      }
 475      if (pb[len] < cur[len])
 476      {
 477        *ptr1 = curMatch;
 478        ptr1 = pair + 1;
 479        curMatch = *ptr1;
 480        len1 = len;
 481      }
 482      else
 483      {
 484        *ptr0 = curMatch;
 485        ptr0 = pair;
 486        curMatch = *ptr0;
 487        len0 = len;
 488      }
 489    }
 490  }
 491}
 492
 493#define MOVE_POS \
 494  ++p->cyclicBufferPos; \
 495  p->buffer++; \
 496  if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
 497
 498#define MOVE_POS_RET MOVE_POS return offset;
 499
 500static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
 501
 502#define GET_MATCHES_HEADER2(minLen, ret_op) \
 503  UInt32 lenLimit; UInt32 hv; const Byte *cur; UInt32 curMatch; \
 504  lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
 505  cur = p->buffer;
 506
 507#define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
 508#define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)
 509
 510#define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
 511
 512#define GET_MATCHES_FOOTER(offset, maxLen) \
 513  offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
 514  distances + offset, maxLen) - distances); MOVE_POS_RET;
 515
 516#define SKIP_FOOTER \
 517  SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
 518
 519#define UPDATE_maxLen { \
 520    ptrdiff_t diff = (ptrdiff_t)0 - d2; \
 521    const Byte *c = cur + maxLen; \
 522    const Byte *lim = cur + lenLimit; \
 523    for (; c != lim; c++) if (*(c + diff) != *c) break; \
 524    maxLen = (UInt32)(c - cur); }
 525
 526static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 527{
 528  UInt32 offset;
 529  GET_MATCHES_HEADER(2)
 530  HASH2_CALC;
 531  curMatch = p->hash[hv];
 532  p->hash[hv] = p->pos;
 533  offset = 0;
 534  GET_MATCHES_FOOTER(offset, 1)
 535}
 536
 537UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 538{
 539  UInt32 offset;
 540  GET_MATCHES_HEADER(3)
 541  HASH_ZIP_CALC;
 542  curMatch = p->hash[hv];
 543  p->hash[hv] = p->pos;
 544  offset = 0;
 545  GET_MATCHES_FOOTER(offset, 2)
 546}
 547
 548static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 549{
 550  UInt32 h2, d2, maxLen, offset, pos;
 551  UInt32 *hash;
 552  GET_MATCHES_HEADER(3)
 553
 554  HASH3_CALC;
 555
 556  hash = p->hash;
 557  pos = p->pos;
 558
 559  d2 = pos - hash[h2];
 560
 561  curMatch = hash[kFix3HashSize + hv];
 562  
 563  hash[h2] = pos;
 564  hash[kFix3HashSize + hv] = pos;
 565
 566  maxLen = 2;
 567  offset = 0;
 568
 569  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 570  {
 571    UPDATE_maxLen
 572    distances[0] = maxLen;
 573    distances[1] = d2 - 1;
 574    offset = 2;
 575    if (maxLen == lenLimit)
 576    {
 577      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
 578      MOVE_POS_RET;
 579    }
 580  }
 581  
 582  GET_MATCHES_FOOTER(offset, maxLen)
 583}
 584
 585static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 586{
 587  UInt32 h2, h3, d2, d3, maxLen, offset, pos;
 588  UInt32 *hash;
 589  GET_MATCHES_HEADER(4)
 590
 591  HASH4_CALC;
 592
 593  hash = p->hash;
 594  pos = p->pos;
 595
 596  d2 = pos - hash[                h2];
 597  d3 = pos - hash[kFix3HashSize + h3];
 598
 599  curMatch = hash[kFix4HashSize + hv];
 600
 601  hash[                h2] = pos;
 602  hash[kFix3HashSize + h3] = pos;
 603  hash[kFix4HashSize + hv] = pos;
 604
 605  maxLen = 0;
 606  offset = 0;
 607  
 608  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 609  {
 610    distances[0] = maxLen = 2;
 611    distances[1] = d2 - 1;
 612    offset = 2;
 613  }
 614  
 615  if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 616  {
 617    maxLen = 3;
 618    distances[offset + 1] = d3 - 1;
 619    offset += 2;
 620    d2 = d3;
 621  }
 622  
 623  if (offset != 0)
 624  {
 625    UPDATE_maxLen
 626    distances[offset - 2] = maxLen;
 627    if (maxLen == lenLimit)
 628    {
 629      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
 630      MOVE_POS_RET;
 631    }
 632  }
 633  
 634  if (maxLen < 3)
 635    maxLen = 3;
 636  
 637  GET_MATCHES_FOOTER(offset, maxLen)
 638}
 639
 640/*
 641static UInt32 Bt5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 642{
 643  UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos;
 644  UInt32 *hash;
 645  GET_MATCHES_HEADER(5)
 646
 647  HASH5_CALC;
 648
 649  hash = p->hash;
 650  pos = p->pos;
 651
 652  d2 = pos - hash[                h2];
 653  d3 = pos - hash[kFix3HashSize + h3];
 654  d4 = pos - hash[kFix4HashSize + h4];
 655
 656  curMatch = hash[kFix5HashSize + hv];
 657
 658  hash[                h2] = pos;
 659  hash[kFix3HashSize + h3] = pos;
 660  hash[kFix4HashSize + h4] = pos;
 661  hash[kFix5HashSize + hv] = pos;
 662
 663  maxLen = 0;
 664  offset = 0;
 665
 666  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 667  {
 668    distances[0] = maxLen = 2;
 669    distances[1] = d2 - 1;
 670    offset = 2;
 671    if (*(cur - d2 + 2) == cur[2])
 672      distances[0] = maxLen = 3;
 673    else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 674    {
 675      distances[2] = maxLen = 3;
 676      distances[3] = d3 - 1;
 677      offset = 4;
 678      d2 = d3;
 679    }
 680  }
 681  else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 682  {
 683    distances[0] = maxLen = 3;
 684    distances[1] = d3 - 1;
 685    offset = 2;
 686    d2 = d3;
 687  }
 688  
 689  if (d2 != d4 && d4 < p->cyclicBufferSize
 690      && *(cur - d4) == *cur
 691      && *(cur - d4 + 3) == *(cur + 3))
 692  {
 693    maxLen = 4;
 694    distances[offset + 1] = d4 - 1;
 695    offset += 2;
 696    d2 = d4;
 697  }
 698  
 699  if (offset != 0)
 700  {
 701    UPDATE_maxLen
 702    distances[offset - 2] = maxLen;
 703    if (maxLen == lenLimit)
 704    {
 705      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
 706      MOVE_POS_RET;
 707    }
 708  }
 709
 710  if (maxLen < 4)
 711    maxLen = 4;
 712  
 713  GET_MATCHES_FOOTER(offset, maxLen)
 714}
 715*/
 716
 717static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 718{
 719  UInt32 h2, h3, d2, d3, maxLen, offset, pos;
 720  UInt32 *hash;
 721  GET_MATCHES_HEADER(4)
 722
 723  HASH4_CALC;
 724
 725  hash = p->hash;
 726  pos = p->pos;
 727  
 728  d2 = pos - hash[                h2];
 729  d3 = pos - hash[kFix3HashSize + h3];
 730  
 731  curMatch = hash[kFix4HashSize + hv];
 732
 733  hash[                h2] = pos;
 734  hash[kFix3HashSize + h3] = pos;
 735  hash[kFix4HashSize + hv] = pos;
 736
 737  maxLen = 0;
 738  offset = 0;
 739
 740  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 741  {
 742    distances[0] = maxLen = 2;
 743    distances[1] = d2 - 1;
 744    offset = 2;
 745  }
 746  
 747  if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 748  {
 749    maxLen = 3;
 750    distances[offset + 1] = d3 - 1;
 751    offset += 2;
 752    d2 = d3;
 753  }
 754  
 755  if (offset != 0)
 756  {
 757    UPDATE_maxLen
 758    distances[offset - 2] = maxLen;
 759    if (maxLen == lenLimit)
 760    {
 761      p->son[p->cyclicBufferPos] = curMatch;
 762      MOVE_POS_RET;
 763    }
 764  }
 765  
 766  if (maxLen < 3)
 767    maxLen = 3;
 768
 769  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 770      distances + offset, maxLen) - (distances));
 771  MOVE_POS_RET
 772}
 773
 774/*
 775static UInt32 Hc5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 776{
 777  UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos
 778  UInt32 *hash;
 779  GET_MATCHES_HEADER(5)
 780
 781  HASH5_CALC;
 782
 783  hash = p->hash;
 784  pos = p->pos;
 785  
 786  d2 = pos - hash[                h2];
 787  d3 = pos - hash[kFix3HashSize + h3];
 788  d4 = pos - hash[kFix4HashSize + h4];
 789
 790  curMatch = hash[kFix5HashSize + hv];
 791
 792  hash[                h2] = pos;
 793  hash[kFix3HashSize + h3] = pos;
 794  hash[kFix4HashSize + h4] = pos;
 795  hash[kFix5HashSize + hv] = pos;
 796
 797  maxLen = 0;
 798  offset = 0;
 799
 800  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
 801  {
 802    distances[0] = maxLen = 2;
 803    distances[1] = d2 - 1;
 804    offset = 2;
 805    if (*(cur - d2 + 2) == cur[2])
 806      distances[0] = maxLen = 3;
 807    else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 808    {
 809      distances[2] = maxLen = 3;
 810      distances[3] = d3 - 1;
 811      offset = 4;
 812      d2 = d3;
 813    }
 814  }
 815  else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
 816  {
 817    distances[0] = maxLen = 3;
 818    distances[1] = d3 - 1;
 819    offset = 2;
 820    d2 = d3;
 821  }
 822  
 823  if (d2 != d4 && d4 < p->cyclicBufferSize
 824      && *(cur - d4) == *cur
 825      && *(cur - d4 + 3) == *(cur + 3))
 826  {
 827    maxLen = 4;
 828    distances[offset + 1] = d4 - 1;
 829    offset += 2;
 830    d2 = d4;
 831  }
 832  
 833  if (offset != 0)
 834  {
 835    UPDATE_maxLen
 836    distances[offset - 2] = maxLen;
 837    if (maxLen == lenLimit)
 838    {
 839      p->son[p->cyclicBufferPos] = curMatch;
 840      MOVE_POS_RET;
 841    }
 842  }
 843  
 844  if (maxLen < 4)
 845    maxLen = 4;
 846
 847  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 848      distances + offset, maxLen) - (distances));
 849  MOVE_POS_RET
 850}
 851*/
 852
 853UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
 854{
 855  UInt32 offset;
 856  GET_MATCHES_HEADER(3)
 857  HASH_ZIP_CALC;
 858  curMatch = p->hash[hv];
 859  p->hash[hv] = p->pos;
 860  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
 861      distances, 2) - (distances));
 862  MOVE_POS_RET
 863}
 864
 865static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 866{
 867  do
 868  {
 869    SKIP_HEADER(2)
 870    HASH2_CALC;
 871    curMatch = p->hash[hv];
 872    p->hash[hv] = p->pos;
 873    SKIP_FOOTER
 874  }
 875  while (--num != 0);
 876}
 877
 878void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 879{
 880  do
 881  {
 882    SKIP_HEADER(3)
 883    HASH_ZIP_CALC;
 884    curMatch = p->hash[hv];
 885    p->hash[hv] = p->pos;
 886    SKIP_FOOTER
 887  }
 888  while (--num != 0);
 889}
 890
 891static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 892{
 893  do
 894  {
 895    UInt32 h2;
 896    UInt32 *hash;
 897    SKIP_HEADER(3)
 898    HASH3_CALC;
 899    hash = p->hash;
 900    curMatch = hash[kFix3HashSize + hv];
 901    hash[h2] =
 902    hash[kFix3HashSize + hv] = p->pos;
 903    SKIP_FOOTER
 904  }
 905  while (--num != 0);
 906}
 907
 908static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 909{
 910  do
 911  {
 912    UInt32 h2, h3;
 913    UInt32 *hash;
 914    SKIP_HEADER(4)
 915    HASH4_CALC;
 916    hash = p->hash;
 917    curMatch = hash[kFix4HashSize + hv];
 918    hash[                h2] =
 919    hash[kFix3HashSize + h3] =
 920    hash[kFix4HashSize + hv] = p->pos;
 921    SKIP_FOOTER
 922  }
 923  while (--num != 0);
 924}
 925
 926/*
 927static void Bt5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 928{
 929  do
 930  {
 931    UInt32 h2, h3, h4;
 932    UInt32 *hash;
 933    SKIP_HEADER(5)
 934    HASH5_CALC;
 935    hash = p->hash;
 936    curMatch = hash[kFix5HashSize + hv];
 937    hash[                h2] =
 938    hash[kFix3HashSize + h3] =
 939    hash[kFix4HashSize + h4] =
 940    hash[kFix5HashSize + hv] = p->pos;
 941    SKIP_FOOTER
 942  }
 943  while (--num != 0);
 944}
 945*/
 946
 947static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 948{
 949  do
 950  {
 951    UInt32 h2, h3;
 952    UInt32 *hash;
 953    SKIP_HEADER(4)
 954    HASH4_CALC;
 955    hash = p->hash;
 956    curMatch = hash[kFix4HashSize + hv];
 957    hash[                h2] =
 958    hash[kFix3HashSize + h3] =
 959    hash[kFix4HashSize + hv] = p->pos;
 960    p->son[p->cyclicBufferPos] = curMatch;
 961    MOVE_POS
 962  }
 963  while (--num != 0);
 964}
 965
 966/*
 967static void Hc5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 968{
 969  do
 970  {
 971    UInt32 h2, h3, h4;
 972    UInt32 *hash;
 973    SKIP_HEADER(5)
 974    HASH5_CALC;
 975    hash = p->hash;
 976    curMatch = p->hash[kFix5HashSize + hv];
 977    hash[                h2] =
 978    hash[kFix3HashSize + h3] =
 979    hash[kFix4HashSize + h4] =
 980    hash[kFix5HashSize + hv] = p->pos;
 981    p->son[p->cyclicBufferPos] = curMatch;
 982    MOVE_POS
 983  }
 984  while (--num != 0);
 985}
 986*/
 987
 988void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
 989{
 990  do
 991  {
 992    SKIP_HEADER(3)
 993    HASH_ZIP_CALC;
 994    curMatch = p->hash[hv];
 995    p->hash[hv] = p->pos;
 996    p->son[p->cyclicBufferPos] = curMatch;
 997    MOVE_POS
 998  }
 999  while (--num != 0);
1000}
1001
1002void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
1003{
1004  vTable->Init = (Mf_Init_Func)MatchFinder_Init;
1005  vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
1006  vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
1007  if (!p->btMode)
1008  {
1009    /* if (p->numHashBytes <= 4) */
1010    {
1011      vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
1012      vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
1013    }
1014    /*
1015    else
1016    {
1017      vTable->GetMatches = (Mf_GetMatches_Func)Hc5_MatchFinder_GetMatches;
1018      vTable->Skip = (Mf_Skip_Func)Hc5_MatchFinder_Skip;
1019    }
1020    */
1021  }
1022  else if (p->numHashBytes == 2)
1023  {
1024    vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
1025    vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
1026  }
1027  else if (p->numHashBytes == 3)
1028  {
1029    vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
1030    vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
1031  }
1032  else /* if (p->numHashBytes == 4) */
1033  {
1034    vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
1035    vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
1036  }
1037  /*
1038  else
1039  {
1040    vTable->GetMatches = (Mf_GetMatches_Func)Bt5_MatchFinder_GetMatches;
1041    vTable->Skip = (Mf_Skip_Func)Bt5_MatchFinder_Skip;
1042  }
1043  */
1044}