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