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