1 /* LzFindMt.c -- multithreaded Match finder for LZ algorithms 2 2015-10-15 : Igor Pavlov : Public domain */ 3 4 #include "Precomp.h" 5 6 #include "LzHash.h" 7 8 #include "LzFindMt.h" 9 10 static void MtSync_Construct(CMtSync *p) 11 { 12 p->wasCreated = False; 13 p->csWasInitialized = False; 14 p->csWasEntered = False; 15 Thread_Construct(&p->thread); 16 Event_Construct(&p->canStart); 17 Event_Construct(&p->wasStarted); 18 Event_Construct(&p->wasStopped); 19 Semaphore_Construct(&p->freeSemaphore); 20 Semaphore_Construct(&p->filledSemaphore); 21 } 22 23 static void MtSync_GetNextBlock(CMtSync *p) 24 { 25 if (p->needStart) 26 { 27 p->numProcessedBlocks = 1; 28 p->needStart = False; 29 p->stopWriting = False; 30 p->exit = False; 31 Event_Reset(&p->wasStarted); 32 Event_Reset(&p->wasStopped); 33 34 Event_Set(&p->canStart); 35 Event_Wait(&p->wasStarted); 36 } 37 else 38 { 39 CriticalSection_Leave(&p->cs); 40 p->csWasEntered = False; 41 p->numProcessedBlocks++; 42 Semaphore_Release1(&p->freeSemaphore); 43 } 44 Semaphore_Wait(&p->filledSemaphore); 45 CriticalSection_Enter(&p->cs); 46 p->csWasEntered = True; 47 } 48 49 /* MtSync_StopWriting must be called if Writing was started */ 50 51 static void MtSync_StopWriting(CMtSync *p) 52 { 53 UInt32 myNumBlocks = p->numProcessedBlocks; 54 if (!Thread_WasCreated(&p->thread) || p->needStart) 55 return; 56 p->stopWriting = True; 57 if (p->csWasEntered) 58 { 59 CriticalSection_Leave(&p->cs); 60 p->csWasEntered = False; 61 } 62 Semaphore_Release1(&p->freeSemaphore); 63 64 Event_Wait(&p->wasStopped); 65 66 while (myNumBlocks++ != p->numProcessedBlocks) 67 { 68 Semaphore_Wait(&p->filledSemaphore); 69 Semaphore_Release1(&p->freeSemaphore); 70 } 71 p->needStart = True; 72 } 73 74 static void MtSync_Destruct(CMtSync *p) 75 { 76 if (Thread_WasCreated(&p->thread)) 77 { 78 MtSync_StopWriting(p); 79 p->exit = True; 80 if (p->needStart) 81 Event_Set(&p->canStart); 82 Thread_Wait(&p->thread); 83 Thread_Close(&p->thread); 84 } 85 if (p->csWasInitialized) 86 { 87 CriticalSection_Delete(&p->cs); 88 p->csWasInitialized = False; 89 } 90 91 Event_Close(&p->canStart); 92 Event_Close(&p->wasStarted); 93 Event_Close(&p->wasStopped); 94 Semaphore_Close(&p->freeSemaphore); 95 Semaphore_Close(&p->filledSemaphore); 96 97 p->wasCreated = False; 98 } 99 100 #define RINOK_THREAD(x) { if ((x) != 0) return SZ_ERROR_THREAD; } 101 102 static SRes MtSync_Create2(CMtSync *p, THREAD_FUNC_TYPE startAddress, void *obj, UInt32 numBlocks) 103 { 104 if (p->wasCreated) 105 return SZ_OK; 106 107 RINOK_THREAD(CriticalSection_Init(&p->cs)); 108 p->csWasInitialized = True; 109 110 RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->canStart)); 111 RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStarted)); 112 RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStopped)); 113 114 RINOK_THREAD(Semaphore_Create(&p->freeSemaphore, numBlocks, numBlocks)); 115 RINOK_THREAD(Semaphore_Create(&p->filledSemaphore, 0, numBlocks)); 116 117 p->needStart = True; 118 119 RINOK_THREAD(Thread_Create(&p->thread, startAddress, obj)); 120 p->wasCreated = True; 121 return SZ_OK; 122 } 123 124 static SRes MtSync_Create(CMtSync *p, THREAD_FUNC_TYPE startAddress, void *obj, UInt32 numBlocks) 125 { 126 SRes res = MtSync_Create2(p, startAddress, obj, numBlocks); 127 if (res != SZ_OK) 128 MtSync_Destruct(p); 129 return res; 130 } 131 132 void MtSync_Init(CMtSync *p) { p->needStart = True; } 133 134 #define kMtMaxValForNormalize 0xFFFFFFFF 135 136 #define DEF_GetHeads2(name, v, action) \ 137 static void GetHeads ## name(const Byte *p, UInt32 pos, \ 138 UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads, const UInt32 *crc) \ 139 { action; for (; numHeads != 0; numHeads--) { \ 140 const UInt32 value = (v); p++; *heads++ = pos - hash[value]; hash[value] = pos++; } } 141 142 #define DEF_GetHeads(name, v) DEF_GetHeads2(name, v, ;) 143 144 DEF_GetHeads2(2, (p[0] | ((UInt32)p[1] << 8)), UNUSED_VAR(hashMask); UNUSED_VAR(crc); ) 145 DEF_GetHeads(3, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask) 146 DEF_GetHeads(4, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5)) & hashMask) 147 DEF_GetHeads(4b, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ ((UInt32)p[3] << 16)) & hashMask) 148 /* DEF_GetHeads(5, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5) ^ (crc[p[4]] << 3)) & hashMask) */ 149 150 static void HashThreadFunc(CMatchFinderMt *mt) 151 { 152 CMtSync *p = &mt->hashSync; 153 for (;;) 154 { 155 UInt32 numProcessedBlocks = 0; 156 Event_Wait(&p->canStart); 157 Event_Set(&p->wasStarted); 158 for (;;) 159 { 160 if (p->exit) 161 return; 162 if (p->stopWriting) 163 { 164 p->numProcessedBlocks = numProcessedBlocks; 165 Event_Set(&p->wasStopped); 166 break; 167 } 168 169 { 170 CMatchFinder *mf = mt->MatchFinder; 171 if (MatchFinder_NeedMove(mf)) 172 { 173 CriticalSection_Enter(&mt->btSync.cs); 174 CriticalSection_Enter(&mt->hashSync.cs); 175 { 176 const Byte *beforePtr = Inline_MatchFinder_GetPointerToCurrentPos(mf); 177 ptrdiff_t offset; 178 MatchFinder_MoveBlock(mf); 179 offset = beforePtr - Inline_MatchFinder_GetPointerToCurrentPos(mf); 180 mt->pointerToCurPos -= offset; 181 mt->buffer -= offset; 182 } 183 CriticalSection_Leave(&mt->btSync.cs); 184 CriticalSection_Leave(&mt->hashSync.cs); 185 continue; 186 } 187 188 Semaphore_Wait(&p->freeSemaphore); 189 190 MatchFinder_ReadIfRequired(mf); 191 if (mf->pos > (kMtMaxValForNormalize - kMtHashBlockSize)) 192 { 193 UInt32 subValue = (mf->pos - mf->historySize - 1); 194 MatchFinder_ReduceOffsets(mf, subValue); 195 MatchFinder_Normalize3(subValue, mf->hash + mf->fixedHashSize, (size_t)mf->hashMask + 1); 196 } 197 { 198 UInt32 *heads = mt->hashBuf + ((numProcessedBlocks++) & kMtHashNumBlocksMask) * kMtHashBlockSize; 199 UInt32 num = mf->streamPos - mf->pos; 200 heads[0] = 2; 201 heads[1] = num; 202 if (num >= mf->numHashBytes) 203 { 204 num = num - mf->numHashBytes + 1; 205 if (num > kMtHashBlockSize - 2) 206 num = kMtHashBlockSize - 2; 207 mt->GetHeadsFunc(mf->buffer, mf->pos, mf->hash + mf->fixedHashSize, mf->hashMask, heads + 2, num, mf->crc); 208 heads[0] += num; 209 } 210 mf->pos += num; 211 mf->buffer += num; 212 } 213 } 214 215 Semaphore_Release1(&p->filledSemaphore); 216 } 217 } 218 } 219 220 static void MatchFinderMt_GetNextBlock_Hash(CMatchFinderMt *p) 221 { 222 MtSync_GetNextBlock(&p->hashSync); 223 p->hashBufPosLimit = p->hashBufPos = ((p->hashSync.numProcessedBlocks - 1) & kMtHashNumBlocksMask) * kMtHashBlockSize; 224 p->hashBufPosLimit += p->hashBuf[p->hashBufPos++]; 225 p->hashNumAvail = p->hashBuf[p->hashBufPos++]; 226 } 227 228 #define kEmptyHashValue 0 229 230 /* #define MFMT_GM_INLINE */ 231 232 #ifdef MFMT_GM_INLINE 233 234 #define NO_INLINE MY_FAST_CALL 235 236 static Int32 NO_INLINE GetMatchesSpecN(UInt32 lenLimit, UInt32 pos, const Byte *cur, CLzRef *son, 237 UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue, 238 UInt32 *_distances, UInt32 _maxLen, const UInt32 *hash, Int32 limit, UInt32 size, UInt32 *posRes) 239 { 240 do 241 { 242 UInt32 *distances = _distances + 1; 243 UInt32 curMatch = pos - *hash++; 244 245 CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1; 246 CLzRef *ptr1 = son + (_cyclicBufferPos << 1); 247 UInt32 len0 = 0, len1 = 0; 248 UInt32 cutValue = _cutValue; 249 UInt32 maxLen = _maxLen; 250 for (;;) 251 { 252 UInt32 delta = pos - curMatch; 253 if (cutValue-- == 0 || delta >= _cyclicBufferSize) 254 { 255 *ptr0 = *ptr1 = kEmptyHashValue; 256 break; 257 } 258 { 259 CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1); 260 const Byte *pb = cur - delta; 261 UInt32 len = (len0 < len1 ? len0 : len1); 262 if (pb[len] == cur[len]) 263 { 264 if (++len != lenLimit && pb[len] == cur[len]) 265 while (++len != lenLimit) 266 if (pb[len] != cur[len]) 267 break; 268 if (maxLen < len) 269 { 270 *distances++ = maxLen = len; 271 *distances++ = delta - 1; 272 if (len == lenLimit) 273 { 274 *ptr1 = pair[0]; 275 *ptr0 = pair[1]; 276 break; 277 } 278 } 279 } 280 if (pb[len] < cur[len]) 281 { 282 *ptr1 = curMatch; 283 ptr1 = pair + 1; 284 curMatch = *ptr1; 285 len1 = len; 286 } 287 else 288 { 289 *ptr0 = curMatch; 290 ptr0 = pair; 291 curMatch = *ptr0; 292 len0 = len; 293 } 294 } 295 } 296 pos++; 297 _cyclicBufferPos++; 298 cur++; 299 { 300 UInt32 num = (UInt32)(distances - _distances); 301 *_distances = num - 1; 302 _distances += num; 303 limit -= num; 304 } 305 } 306 while (limit > 0 && --size != 0); 307 *posRes = pos; 308 return limit; 309 } 310 311 #endif 312 313 static void BtGetMatches(CMatchFinderMt *p, UInt32 *distances) 314 { 315 UInt32 numProcessed = 0; 316 UInt32 curPos = 2; 317 UInt32 limit = kMtBtBlockSize - (p->matchMaxLen * 2); 318 319 distances[1] = p->hashNumAvail; 320 321 while (curPos < limit) 322 { 323 if (p->hashBufPos == p->hashBufPosLimit) 324 { 325 MatchFinderMt_GetNextBlock_Hash(p); 326 distances[1] = numProcessed + p->hashNumAvail; 327 if (p->hashNumAvail >= p->numHashBytes) 328 continue; 329 distances[0] = curPos + p->hashNumAvail; 330 distances += curPos; 331 for (; p->hashNumAvail != 0; p->hashNumAvail--) 332 *distances++ = 0; 333 return; 334 } 335 { 336 UInt32 size = p->hashBufPosLimit - p->hashBufPos; 337 UInt32 lenLimit = p->matchMaxLen; 338 UInt32 pos = p->pos; 339 UInt32 cyclicBufferPos = p->cyclicBufferPos; 340 if (lenLimit >= p->hashNumAvail) 341 lenLimit = p->hashNumAvail; 342 { 343 UInt32 size2 = p->hashNumAvail - lenLimit + 1; 344 if (size2 < size) 345 size = size2; 346 size2 = p->cyclicBufferSize - cyclicBufferPos; 347 if (size2 < size) 348 size = size2; 349 } 350 351 #ifndef MFMT_GM_INLINE 352 while (curPos < limit && size-- != 0) 353 { 354 UInt32 *startDistances = distances + curPos; 355 UInt32 num = (UInt32)(GetMatchesSpec1(lenLimit, pos - p->hashBuf[p->hashBufPos++], 356 pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue, 357 startDistances + 1, p->numHashBytes - 1) - startDistances); 358 *startDistances = num - 1; 359 curPos += num; 360 cyclicBufferPos++; 361 pos++; 362 p->buffer++; 363 } 364 #else 365 { 366 UInt32 posRes; 367 curPos = limit - GetMatchesSpecN(lenLimit, pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue, 368 distances + curPos, p->numHashBytes - 1, p->hashBuf + p->hashBufPos, (Int32)(limit - curPos), size, &posRes); 369 p->hashBufPos += posRes - pos; 370 cyclicBufferPos += posRes - pos; 371 p->buffer += posRes - pos; 372 pos = posRes; 373 } 374 #endif 375 376 numProcessed += pos - p->pos; 377 p->hashNumAvail -= pos - p->pos; 378 p->pos = pos; 379 if (cyclicBufferPos == p->cyclicBufferSize) 380 cyclicBufferPos = 0; 381 p->cyclicBufferPos = cyclicBufferPos; 382 } 383 } 384 385 distances[0] = curPos; 386 } 387 388 static void BtFillBlock(CMatchFinderMt *p, UInt32 globalBlockIndex) 389 { 390 CMtSync *sync = &p->hashSync; 391 if (!sync->needStart) 392 { 393 CriticalSection_Enter(&sync->cs); 394 sync->csWasEntered = True; 395 } 396 397 BtGetMatches(p, p->btBuf + (globalBlockIndex & kMtBtNumBlocksMask) * kMtBtBlockSize); 398 399 if (p->pos > kMtMaxValForNormalize - kMtBtBlockSize) 400 { 401 UInt32 subValue = p->pos - p->cyclicBufferSize; 402 MatchFinder_Normalize3(subValue, p->son, (size_t)p->cyclicBufferSize * 2); 403 p->pos -= subValue; 404 } 405 406 if (!sync->needStart) 407 { 408 CriticalSection_Leave(&sync->cs); 409 sync->csWasEntered = False; 410 } 411 } 412 413 void BtThreadFunc(CMatchFinderMt *mt) 414 { 415 CMtSync *p = &mt->btSync; 416 for (;;) 417 { 418 UInt32 blockIndex = 0; 419 Event_Wait(&p->canStart); 420 Event_Set(&p->wasStarted); 421 for (;;) 422 { 423 if (p->exit) 424 return; 425 if (p->stopWriting) 426 { 427 p->numProcessedBlocks = blockIndex; 428 MtSync_StopWriting(&mt->hashSync); 429 Event_Set(&p->wasStopped); 430 break; 431 } 432 Semaphore_Wait(&p->freeSemaphore); 433 BtFillBlock(mt, blockIndex++); 434 Semaphore_Release1(&p->filledSemaphore); 435 } 436 } 437 } 438 439 void MatchFinderMt_Construct(CMatchFinderMt *p) 440 { 441 p->hashBuf = NULL; 442 MtSync_Construct(&p->hashSync); 443 MtSync_Construct(&p->btSync); 444 } 445 446 static void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAlloc *alloc) 447 { 448 alloc->Free(alloc, p->hashBuf); 449 p->hashBuf = NULL; 450 } 451 452 void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAlloc *alloc) 453 { 454 MtSync_Destruct(&p->hashSync); 455 MtSync_Destruct(&p->btSync); 456 MatchFinderMt_FreeMem(p, alloc); 457 } 458 459 #define kHashBufferSize (kMtHashBlockSize * kMtHashNumBlocks) 460 #define kBtBufferSize (kMtBtBlockSize * kMtBtNumBlocks) 461 462 static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p); return 0; } 463 static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE BtThreadFunc2(void *p) 464 { 465 Byte allocaDummy[0x180]; 466 unsigned i = 0; 467 for (i = 0; i < 16; i++) 468 allocaDummy[i] = (Byte)0; 469 if (allocaDummy[0] == 0) 470 BtThreadFunc((CMatchFinderMt *)p); 471 return 0; 472 } 473 474 SRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore, 475 UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAlloc *alloc) 476 { 477 CMatchFinder *mf = p->MatchFinder; 478 p->historySize = historySize; 479 if (kMtBtBlockSize <= matchMaxLen * 4) 480 return SZ_ERROR_PARAM; 481 if (!p->hashBuf) 482 { 483 p->hashBuf = (UInt32 *)alloc->Alloc(alloc, (kHashBufferSize + kBtBufferSize) * sizeof(UInt32)); 484 if (!p->hashBuf) 485 return SZ_ERROR_MEM; 486 p->btBuf = p->hashBuf + kHashBufferSize; 487 } 488 keepAddBufferBefore += (kHashBufferSize + kBtBufferSize); 489 keepAddBufferAfter += kMtHashBlockSize; 490 if (!MatchFinder_Create(mf, historySize, keepAddBufferBefore, matchMaxLen, keepAddBufferAfter, alloc)) 491 return SZ_ERROR_MEM; 492 493 RINOK(MtSync_Create(&p->hashSync, HashThreadFunc2, p, kMtHashNumBlocks)); 494 RINOK(MtSync_Create(&p->btSync, BtThreadFunc2, p, kMtBtNumBlocks)); 495 return SZ_OK; 496 } 497 498 /* Call it after ReleaseStream / SetStream */ 499 void MatchFinderMt_Init(CMatchFinderMt *p) 500 { 501 CMatchFinder *mf = p->MatchFinder; 502 p->btBufPos = p->btBufPosLimit = 0; 503 p->hashBufPos = p->hashBufPosLimit = 0; 504 505 /* Init without data reading. We don't want to read data in this thread */ 506 MatchFinder_Init_2(mf, False); 507 508 p->pointerToCurPos = Inline_MatchFinder_GetPointerToCurrentPos(mf); 509 p->btNumAvailBytes = 0; 510 p->lzPos = p->historySize + 1; 511 512 p->hash = mf->hash; 513 p->fixedHashSize = mf->fixedHashSize; 514 p->crc = mf->crc; 515 516 p->son = mf->son; 517 p->matchMaxLen = mf->matchMaxLen; 518 p->numHashBytes = mf->numHashBytes; 519 p->pos = mf->pos; 520 p->buffer = mf->buffer; 521 p->cyclicBufferPos = mf->cyclicBufferPos; 522 p->cyclicBufferSize = mf->cyclicBufferSize; 523 p->cutValue = mf->cutValue; 524 } 525 526 /* ReleaseStream is required to finish multithreading */ 527 void MatchFinderMt_ReleaseStream(CMatchFinderMt *p) 528 { 529 MtSync_StopWriting(&p->btSync); 530 /* p->MatchFinder->ReleaseStream(); */ 531 } 532 533 static void MatchFinderMt_Normalize(CMatchFinderMt *p) 534 { 535 MatchFinder_Normalize3(p->lzPos - p->historySize - 1, p->hash, p->fixedHashSize); 536 p->lzPos = p->historySize + 1; 537 } 538 539 static void MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt *p) 540 { 541 UInt32 blockIndex; 542 MtSync_GetNextBlock(&p->btSync); 543 blockIndex = ((p->btSync.numProcessedBlocks - 1) & kMtBtNumBlocksMask); 544 p->btBufPosLimit = p->btBufPos = blockIndex * kMtBtBlockSize; 545 p->btBufPosLimit += p->btBuf[p->btBufPos++]; 546 p->btNumAvailBytes = p->btBuf[p->btBufPos++]; 547 if (p->lzPos >= kMtMaxValForNormalize - kMtBtBlockSize) 548 MatchFinderMt_Normalize(p); 549 } 550 551 static const Byte * MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt *p) 552 { 553 return p->pointerToCurPos; 554 } 555 556 #define GET_NEXT_BLOCK_IF_REQUIRED if (p->btBufPos == p->btBufPosLimit) MatchFinderMt_GetNextBlock_Bt(p); 557 558 static UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p) 559 { 560 GET_NEXT_BLOCK_IF_REQUIRED; 561 return p->btNumAvailBytes; 562 } 563 564 static UInt32 * MixMatches2(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances) 565 { 566 UInt32 h2, curMatch2; 567 UInt32 *hash = p->hash; 568 const Byte *cur = p->pointerToCurPos; 569 UInt32 lzPos = p->lzPos; 570 MT_HASH2_CALC 571 572 curMatch2 = hash[h2]; 573 hash[h2] = lzPos; 574 575 if (curMatch2 >= matchMinPos) 576 if (cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0]) 577 { 578 *distances++ = 2; 579 *distances++ = lzPos - curMatch2 - 1; 580 } 581 582 return distances; 583 } 584 585 static UInt32 * MixMatches3(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances) 586 { 587 UInt32 h2, h3, curMatch2, curMatch3; 588 UInt32 *hash = p->hash; 589 const Byte *cur = p->pointerToCurPos; 590 UInt32 lzPos = p->lzPos; 591 MT_HASH3_CALC 592 593 curMatch2 = hash[ h2]; 594 curMatch3 = hash[kFix3HashSize + h3]; 595 596 hash[ h2] = lzPos; 597 hash[kFix3HashSize + h3] = lzPos; 598 599 if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0]) 600 { 601 distances[1] = lzPos - curMatch2 - 1; 602 if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2]) 603 { 604 distances[0] = 3; 605 return distances + 2; 606 } 607 distances[0] = 2; 608 distances += 2; 609 } 610 611 if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0]) 612 { 613 *distances++ = 3; 614 *distances++ = lzPos - curMatch3 - 1; 615 } 616 617 return distances; 618 } 619 620 /* 621 static UInt32 *MixMatches4(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances) 622 { 623 UInt32 h2, h3, h4, curMatch2, curMatch3, curMatch4; 624 UInt32 *hash = p->hash; 625 const Byte *cur = p->pointerToCurPos; 626 UInt32 lzPos = p->lzPos; 627 MT_HASH4_CALC 628 629 curMatch2 = hash[ h2]; 630 curMatch3 = hash[kFix3HashSize + h3]; 631 curMatch4 = hash[kFix4HashSize + h4]; 632 633 hash[ h2] = lzPos; 634 hash[kFix3HashSize + h3] = lzPos; 635 hash[kFix4HashSize + h4] = lzPos; 636 637 if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0]) 638 { 639 distances[1] = lzPos - curMatch2 - 1; 640 if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2]) 641 { 642 distances[0] = (cur[(ptrdiff_t)curMatch2 - lzPos + 3] == cur[3]) ? 4 : 3; 643 return distances + 2; 644 } 645 distances[0] = 2; 646 distances += 2; 647 } 648 649 if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0]) 650 { 651 distances[1] = lzPos - curMatch3 - 1; 652 if (cur[(ptrdiff_t)curMatch3 - lzPos + 3] == cur[3]) 653 { 654 distances[0] = 4; 655 return distances + 2; 656 } 657 distances[0] = 3; 658 distances += 2; 659 } 660 661 if (curMatch4 >= matchMinPos) 662 if ( 663 cur[(ptrdiff_t)curMatch4 - lzPos] == cur[0] && 664 cur[(ptrdiff_t)curMatch4 - lzPos + 3] == cur[3] 665 ) 666 { 667 *distances++ = 4; 668 *distances++ = lzPos - curMatch4 - 1; 669 } 670 671 return distances; 672 } 673 */ 674 675 #define INCREASE_LZ_POS p->lzPos++; p->pointerToCurPos++; 676 677 static UInt32 MatchFinderMt2_GetMatches(CMatchFinderMt *p, UInt32 *distances) 678 { 679 const UInt32 *btBuf = p->btBuf + p->btBufPos; 680 UInt32 len = *btBuf++; 681 p->btBufPos += 1 + len; 682 p->btNumAvailBytes--; 683 { 684 UInt32 i; 685 for (i = 0; i < len; i += 2) 686 { 687 *distances++ = *btBuf++; 688 *distances++ = *btBuf++; 689 } 690 } 691 INCREASE_LZ_POS 692 return len; 693 } 694 695 static UInt32 MatchFinderMt_GetMatches(CMatchFinderMt *p, UInt32 *distances) 696 { 697 const UInt32 *btBuf = p->btBuf + p->btBufPos; 698 UInt32 len = *btBuf++; 699 p->btBufPos += 1 + len; 700 701 if (len == 0) 702 { 703 /* change for bt5 ! */ 704 if (p->btNumAvailBytes-- >= 4) 705 len = (UInt32)(p->MixMatchesFunc(p, p->lzPos - p->historySize, distances) - (distances)); 706 } 707 else 708 { 709 /* Condition: there are matches in btBuf with length < p->numHashBytes */ 710 UInt32 *distances2; 711 p->btNumAvailBytes--; 712 distances2 = p->MixMatchesFunc(p, p->lzPos - btBuf[1], distances); 713 do 714 { 715 *distances2++ = *btBuf++; 716 *distances2++ = *btBuf++; 717 } 718 while ((len -= 2) != 0); 719 len = (UInt32)(distances2 - (distances)); 720 } 721 INCREASE_LZ_POS 722 return len; 723 } 724 725 #define SKIP_HEADER2_MT do { GET_NEXT_BLOCK_IF_REQUIRED 726 #define SKIP_HEADER_MT(n) SKIP_HEADER2_MT if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash; 727 #define SKIP_FOOTER_MT } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while (--num != 0); 728 729 static void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num) 730 { 731 SKIP_HEADER2_MT { p->btNumAvailBytes--; 732 SKIP_FOOTER_MT 733 } 734 735 static void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num) 736 { 737 SKIP_HEADER_MT(2) 738 UInt32 h2; 739 MT_HASH2_CALC 740 hash[h2] = p->lzPos; 741 SKIP_FOOTER_MT 742 } 743 744 static void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num) 745 { 746 SKIP_HEADER_MT(3) 747 UInt32 h2, h3; 748 MT_HASH3_CALC 749 hash[kFix3HashSize + h3] = 750 hash[ h2] = 751 p->lzPos; 752 SKIP_FOOTER_MT 753 } 754 755 /* 756 static void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num) 757 { 758 SKIP_HEADER_MT(4) 759 UInt32 h2, h3, h4; 760 MT_HASH4_CALC 761 hash[kFix4HashSize + h4] = 762 hash[kFix3HashSize + h3] = 763 hash[ h2] = 764 p->lzPos; 765 SKIP_FOOTER_MT 766 } 767 */ 768 769 void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable) 770 { 771 vTable->Init = (Mf_Init_Func)MatchFinderMt_Init; 772 vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinderMt_GetNumAvailableBytes; 773 vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinderMt_GetPointerToCurrentPos; 774 vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt_GetMatches; 775 776 switch (p->MatchFinder->numHashBytes) 777 { 778 case 2: 779 p->GetHeadsFunc = GetHeads2; 780 p->MixMatchesFunc = (Mf_Mix_Matches)0; 781 vTable->Skip = (Mf_Skip_Func)MatchFinderMt0_Skip; 782 vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt2_GetMatches; 783 break; 784 case 3: 785 p->GetHeadsFunc = GetHeads3; 786 p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches2; 787 vTable->Skip = (Mf_Skip_Func)MatchFinderMt2_Skip; 788 break; 789 default: 790 /* case 4: */ 791 p->GetHeadsFunc = p->MatchFinder->bigHash ? GetHeads4b : GetHeads4; 792 p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches3; 793 vTable->Skip = (Mf_Skip_Func)MatchFinderMt3_Skip; 794 break; 795 /* 796 default: 797 p->GetHeadsFunc = GetHeads5; 798 p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches4; 799 vTable->Skip = (Mf_Skip_Func)MatchFinderMt4_Skip; 800 break; 801 */ 802 } 803 } 804