Mercurial > vba-linux

annotate src/win32/7zip/7z/C/LzFindMt.c @ 1:f9f4f1b99eed

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