repo sync | baa3858 | 2013-07-26 17:53:31 -0700 | [diff] [blame] | 1 | /* LzFindMt.c -- multithreaded Match finder for LZ algorithms
|
| 2 | 2009-09-20 : Igor Pavlov : Public domain */
|
| 3 |
|
| 4 | #include "LzHash.h"
|
| 5 |
|
| 6 | #include "LzFindMt.h"
|
| 7 |
|
| 8 | void 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 |
|
| 21 | void 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 |
|
| 49 | void 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 |
|
| 72 | void 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 |
|
| 100 | static 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 |
|
| 122 | static 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 |
|
| 130 | void MtSync_Init(CMtSync *p) { p->needStart = True; }
|
| 131 |
|
| 132 | #define kMtMaxValForNormalize 0xFFFFFFFF
|
| 133 |
|
| 134 | #define DEF_GetHeads2(name, v, action) \
|
| 135 | static void GetHeads ## name(const Byte *p, UInt32 pos, \
|
| 136 | UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads, const UInt32 *crc) \
|
| 137 | { action; for (; numHeads != 0; numHeads--) { \
|
| 138 | const UInt32 value = (v); p++; *heads++ = pos - hash[value]; hash[value] = pos++; } }
|
| 139 |
|
| 140 | #define DEF_GetHeads(name, v) DEF_GetHeads2(name, v, ;)
|
| 141 |
|
| 142 | DEF_GetHeads2(2, (p[0] | ((UInt32)p[1] << 8)), hashMask = hashMask; crc = crc; )
|
| 143 | DEF_GetHeads(3, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask)
|
| 144 | DEF_GetHeads(4, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5)) & hashMask)
|
| 145 | DEF_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 |
|
| 148 | void 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 |
|
| 218 | void 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 |
|
| 234 | Int32 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 |
|
| 311 | void 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 |
|
| 380 | void 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 |
|
| 405 | void 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 |
|
| 431 | void MatchFinderMt_Construct(CMatchFinderMt *p)
|
| 432 | {
|
| 433 | p->hashBuf = 0;
|
| 434 | MtSync_Construct(&p->hashSync);
|
| 435 | MtSync_Construct(&p->btSync);
|
| 436 | }
|
| 437 |
|
| 438 | void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAlloc *alloc)
|
| 439 | {
|
| 440 | alloc->Free(alloc, p->hashBuf);
|
| 441 | p->hashBuf = 0;
|
| 442 | }
|
| 443 |
|
| 444 | void 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 |
|
| 454 | static unsigned MY_STD_CALL HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p); return 0; }
|
| 455 | static 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 |
|
| 465 | SRes 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 */
|
| 490 | void 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 */
|
| 515 | void MatchFinderMt_ReleaseStream(CMatchFinderMt *p)
|
| 516 | {
|
| 517 | MtSync_StopWriting(&p->btSync);
|
| 518 | /* p->MatchFinder->ReleaseStream(); */
|
| 519 | }
|
| 520 |
|
| 521 | void 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 |
|
| 527 | void 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 |
|
| 539 | const 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 |
|
| 546 | UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p)
|
| 547 | {
|
| 548 | GET_NEXT_BLOCK_IF_REQUIRED;
|
| 549 | return p->btNumAvailBytes;
|
| 550 | }
|
| 551 |
|
| 552 | Byte MatchFinderMt_GetIndexByte(CMatchFinderMt *p, Int32 index)
|
| 553 | {
|
| 554 | return p->pointerToCurPos[index];
|
| 555 | }
|
| 556 |
|
| 557 | UInt32 * 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 |
|
| 577 | UInt32 * 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 | /*
|
| 612 | UInt32 *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 |
|
| 667 | UInt32 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 |
|
| 685 | UInt32 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 |
|
| 718 | void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num)
|
| 719 | {
|
| 720 | SKIP_HEADER2_MT { p->btNumAvailBytes--;
|
| 721 | SKIP_FOOTER_MT
|
| 722 | }
|
| 723 |
|
| 724 | void 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 |
|
| 733 | void 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 | /*
|
| 745 | void 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 |
|
| 758 | void 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 | }
|