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