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