deps/lzma-16.04/C/LzFindMt.c

   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