C/LzFind.c

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