1 /* LzFind.c -- Match finder for LZ algorithms 2 2015-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 19 static 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 30 static 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 47 Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; } 48 49 UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; } 50 51 void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue) 52 { 53 p->posLimit -= subValue; 54 p->pos -= subValue; 55 p->streamPos -= subValue; 56 } 57 58 static 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 98 void 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 106 int 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 114 void 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 122 static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p) 123 { 124 if (MatchFinder_NeedMove(p)) 125 MatchFinder_MoveBlock(p); 126 MatchFinder_ReadBlock(p); 127 } 128 129 static 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 139 void 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 157 static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc) 158 { 159 alloc->Free(alloc, p->hash); 160 p->hash = NULL; 161 } 162 163 void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc) 164 { 165 MatchFinder_FreeThisClassMemory(p, alloc); 166 LzInWindow_Free(p, alloc); 167 } 168 169 static 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 177 int 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 266 static 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 295 void 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 315 void MatchFinder_Init(CMatchFinder *p) 316 { 317 MatchFinder_Init_2(p, True); 318 } 319 320 static UInt32 MatchFinder_GetSubValue(CMatchFinder *p) 321 { 322 return (p->pos - p->historySize - 1) & kNormalizeMask; 323 } 324 325 void 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 339 static 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 346 static 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 357 static 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 388 UInt32 * 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 443 static 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 500 static 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 526 static 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 537 UInt32 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 548 static 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 585 static 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 /* 641 static 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 717 static 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 /* 775 static 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 853 UInt32 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 865 static 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 878 void 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 891 static 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 908 static 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 /* 927 static 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 947 static 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 /* 967 static 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 988 void 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 1002 void 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 } 1045
