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