rlm@1: /* LzFindMt.c -- multithreaded Match finder for LZ algorithms
rlm@1: 2008-10-04 : Igor Pavlov : Public domain */
rlm@1: 
rlm@1: #include "LzHash.h"
rlm@1: 
rlm@1: #include "LzFindMt.h"
rlm@1: 
rlm@1: void MtSync_Construct(CMtSync *p)
rlm@1: {
rlm@1:   p->wasCreated = False;
rlm@1:   p->csWasInitialized = False;
rlm@1:   p->csWasEntered = False;
rlm@1:   Thread_Construct(&p->thread);
rlm@1:   Event_Construct(&p->canStart);
rlm@1:   Event_Construct(&p->wasStarted);
rlm@1:   Event_Construct(&p->wasStopped);
rlm@1:   Semaphore_Construct(&p->freeSemaphore);
rlm@1:   Semaphore_Construct(&p->filledSemaphore);
rlm@1: }
rlm@1: 
rlm@1: void MtSync_GetNextBlock(CMtSync *p)
rlm@1: {
rlm@1:   if (p->needStart)
rlm@1:   {
rlm@1:     p->numProcessedBlocks = 1;
rlm@1:     p->needStart = False;
rlm@1:     p->stopWriting = False;
rlm@1:     p->exit = False;
rlm@1:     Event_Reset(&p->wasStarted);
rlm@1:     Event_Reset(&p->wasStopped);
rlm@1: 
rlm@1:     Event_Set(&p->canStart);
rlm@1:     Event_Wait(&p->wasStarted);
rlm@1:   }
rlm@1:   else
rlm@1:   {
rlm@1:     CriticalSection_Leave(&p->cs);
rlm@1:     p->csWasEntered = False;
rlm@1:     p->numProcessedBlocks++;
rlm@1:     Semaphore_Release1(&p->freeSemaphore);
rlm@1:   }
rlm@1:   Semaphore_Wait(&p->filledSemaphore);
rlm@1:   CriticalSection_Enter(&p->cs);
rlm@1:   p->csWasEntered = True;
rlm@1: }
rlm@1: 
rlm@1: /* MtSync_StopWriting must be called if Writing was started */
rlm@1: 
rlm@1: void MtSync_StopWriting(CMtSync *p)
rlm@1: {
rlm@1:   UInt32 myNumBlocks = p->numProcessedBlocks;
rlm@1:   if (!Thread_WasCreated(&p->thread) || p->needStart)
rlm@1:     return;
rlm@1:   p->stopWriting = True;
rlm@1:   if (p->csWasEntered)
rlm@1:   {
rlm@1:     CriticalSection_Leave(&p->cs);
rlm@1:     p->csWasEntered = False;
rlm@1:   }
rlm@1:   Semaphore_Release1(&p->freeSemaphore);
rlm@1:  
rlm@1:   Event_Wait(&p->wasStopped);
rlm@1: 
rlm@1:   while (myNumBlocks++ != p->numProcessedBlocks)
rlm@1:   {
rlm@1:     Semaphore_Wait(&p->filledSemaphore);
rlm@1:     Semaphore_Release1(&p->freeSemaphore);
rlm@1:   }
rlm@1:   p->needStart = True;
rlm@1: }
rlm@1: 
rlm@1: void MtSync_Destruct(CMtSync *p)
rlm@1: {
rlm@1:   if (Thread_WasCreated(&p->thread))
rlm@1:   {
rlm@1:     MtSync_StopWriting(p);
rlm@1:     p->exit = True;
rlm@1:     if (p->needStart)
rlm@1:       Event_Set(&p->canStart);
rlm@1:     Thread_Wait(&p->thread);
rlm@1:     Thread_Close(&p->thread);
rlm@1:   }
rlm@1:   if (p->csWasInitialized)
rlm@1:   {
rlm@1:     CriticalSection_Delete(&p->cs);
rlm@1:     p->csWasInitialized = False;
rlm@1:   }
rlm@1: 
rlm@1:   Event_Close(&p->canStart);
rlm@1:   Event_Close(&p->wasStarted);
rlm@1:   Event_Close(&p->wasStopped);
rlm@1:   Semaphore_Close(&p->freeSemaphore);
rlm@1:   Semaphore_Close(&p->filledSemaphore);
rlm@1: 
rlm@1:   p->wasCreated = False;
rlm@1: }
rlm@1: 
rlm@1: #define RINOK_THREAD(x) { if ((x) != 0) return SZ_ERROR_THREAD; }
rlm@1: 
rlm@1: static SRes MtSync_Create2(CMtSync *p, unsigned (MY_STD_CALL *startAddress)(void *), void *obj, UInt32 numBlocks)
rlm@1: {
rlm@1:   if (p->wasCreated)
rlm@1:     return SZ_OK;
rlm@1: 
rlm@1:   RINOK_THREAD(CriticalSection_Init(&p->cs));
rlm@1:   p->csWasInitialized = True;
rlm@1: 
rlm@1:   RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->canStart));
rlm@1:   RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStarted));
rlm@1:   RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStopped));
rlm@1:   
rlm@1:   RINOK_THREAD(Semaphore_Create(&p->freeSemaphore, numBlocks, numBlocks));
rlm@1:   RINOK_THREAD(Semaphore_Create(&p->filledSemaphore, 0, numBlocks));
rlm@1: 
rlm@1:   p->needStart = True;
rlm@1:   
rlm@1:   RINOK_THREAD(Thread_Create(&p->thread, startAddress, obj));
rlm@1:   p->wasCreated = True;
rlm@1:   return SZ_OK;
rlm@1: }
rlm@1: 
rlm@1: static SRes MtSync_Create(CMtSync *p, unsigned (MY_STD_CALL *startAddress)(void *), void *obj, UInt32 numBlocks)
rlm@1: {
rlm@1:   SRes res = MtSync_Create2(p, startAddress, obj, numBlocks);
rlm@1:   if (res != SZ_OK)
rlm@1:     MtSync_Destruct(p);
rlm@1:   return res;
rlm@1: }
rlm@1: 
rlm@1: void MtSync_Init(CMtSync *p) { p->needStart = True; }
rlm@1: 
rlm@1: #define kMtMaxValForNormalize 0xFFFFFFFF
rlm@1: 
rlm@1: #define DEF_GetHeads2(name, v, action) \
rlm@1: static void GetHeads ## name(const Byte *p, UInt32 pos, \
rlm@1: UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads, const UInt32 *crc) \
rlm@1: { action; for (; numHeads != 0; numHeads--) { \
rlm@1: const UInt32 value = (v); p++; *heads++ = pos - hash[value]; hash[value] = pos++;  } }
rlm@1: 
rlm@1: #define DEF_GetHeads(name, v) DEF_GetHeads2(name, v, ;)
rlm@1: 
rlm@1: DEF_GetHeads2(2,  (p[0] | ((UInt32)p[1] << 8)), hashMask = hashMask; crc = crc; )
rlm@1: DEF_GetHeads(3,  (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask)
rlm@1: DEF_GetHeads(4,  (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5)) & hashMask)
rlm@1: DEF_GetHeads(4b, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ ((UInt32)p[3] << 16)) & hashMask)
rlm@1: DEF_GetHeads(5,  (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5) ^ (crc[p[4]] << 3)) & hashMask)
rlm@1: 
rlm@1: void HashThreadFunc(CMatchFinderMt *mt)
rlm@1: {
rlm@1:   CMtSync *p = &mt->hashSync;
rlm@1:   for (;;)
rlm@1:   {
rlm@1:     UInt32 numProcessedBlocks = 0;
rlm@1:     Event_Wait(&p->canStart);
rlm@1:     Event_Set(&p->wasStarted);
rlm@1:     for (;;)
rlm@1:     {
rlm@1:       if (p->exit)
rlm@1:         return;
rlm@1:       if (p->stopWriting)
rlm@1:       {
rlm@1:         p->numProcessedBlocks = numProcessedBlocks;
rlm@1:         Event_Set(&p->wasStopped);
rlm@1:         break;
rlm@1:       }
rlm@1: 
rlm@1:       {
rlm@1:         CMatchFinder *mf = mt->MatchFinder;
rlm@1:         if (MatchFinder_NeedMove(mf))
rlm@1:         {
rlm@1:           CriticalSection_Enter(&mt->btSync.cs);
rlm@1:           CriticalSection_Enter(&mt->hashSync.cs);
rlm@1:           {
rlm@1:             const Byte *beforePtr = MatchFinder_GetPointerToCurrentPos(mf);
rlm@1:             const Byte *afterPtr;
rlm@1:             MatchFinder_MoveBlock(mf);
rlm@1:             afterPtr = MatchFinder_GetPointerToCurrentPos(mf);
rlm@1:             mt->pointerToCurPos -= beforePtr - afterPtr;
rlm@1:             mt->buffer -= beforePtr - afterPtr;
rlm@1:           }
rlm@1:           CriticalSection_Leave(&mt->btSync.cs);
rlm@1:           CriticalSection_Leave(&mt->hashSync.cs);
rlm@1:           continue;
rlm@1:         }
rlm@1: 
rlm@1:         Semaphore_Wait(&p->freeSemaphore);
rlm@1: 
rlm@1:         MatchFinder_ReadIfRequired(mf);
rlm@1:         if (mf->pos > (kMtMaxValForNormalize - kMtHashBlockSize))
rlm@1:         {
rlm@1:           UInt32 subValue = (mf->pos - mf->historySize - 1);
rlm@1:           MatchFinder_ReduceOffsets(mf, subValue);
rlm@1:           MatchFinder_Normalize3(subValue, mf->hash + mf->fixedHashSize, mf->hashMask + 1);
rlm@1:         }
rlm@1:         {
rlm@1:           UInt32 *heads = mt->hashBuf + ((numProcessedBlocks++) & kMtHashNumBlocksMask) * kMtHashBlockSize;
rlm@1:           UInt32 num = mf->streamPos - mf->pos;
rlm@1:           heads[0] = 2;
rlm@1:           heads[1] = num;
rlm@1:           if (num >= mf->numHashBytes)
rlm@1:           {
rlm@1:             num = num - mf->numHashBytes + 1;
rlm@1:             if (num > kMtHashBlockSize - 2)
rlm@1:               num = kMtHashBlockSize - 2;
rlm@1:             mt->GetHeadsFunc(mf->buffer, mf->pos, mf->hash + mf->fixedHashSize, mf->hashMask, heads + 2, num, mf->crc);
rlm@1:             heads[0] += num;
rlm@1:           }
rlm@1:           mf->pos += num;
rlm@1:           mf->buffer += num;
rlm@1:         }
rlm@1:       }
rlm@1: 
rlm@1:       Semaphore_Release1(&p->filledSemaphore);
rlm@1:     }
rlm@1:   }
rlm@1: }
rlm@1: 
rlm@1: void MatchFinderMt_GetNextBlock_Hash(CMatchFinderMt *p)
rlm@1: {
rlm@1:   MtSync_GetNextBlock(&p->hashSync);
rlm@1:   p->hashBufPosLimit = p->hashBufPos = ((p->hashSync.numProcessedBlocks - 1) & kMtHashNumBlocksMask) * kMtHashBlockSize;
rlm@1:   p->hashBufPosLimit += p->hashBuf[p->hashBufPos++];
rlm@1:   p->hashNumAvail = p->hashBuf[p->hashBufPos++];
rlm@1: }
rlm@1: 
rlm@1: #define kEmptyHashValue 0
rlm@1: 
rlm@1: /* #define MFMT_GM_INLINE */
rlm@1: 
rlm@1: #ifdef MFMT_GM_INLINE
rlm@1: 
rlm@1: #define NO_INLINE MY_FAST_CALL
rlm@1: 
rlm@1: Int32 NO_INLINE GetMatchesSpecN(UInt32 lenLimit, UInt32 pos, const Byte *cur, CLzRef *son,
rlm@1:     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue,
rlm@1:     UInt32 *_distances, UInt32 _maxLen, const UInt32 *hash, Int32 limit, UInt32 size, UInt32 *posRes)
rlm@1: {
rlm@1:   do
rlm@1:   {
rlm@1:   UInt32 *distances = _distances + 1;
rlm@1:   UInt32 curMatch = pos - *hash++;
rlm@1: 
rlm@1:   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
rlm@1:   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
rlm@1:   UInt32 len0 = 0, len1 = 0;
rlm@1:   UInt32 cutValue = _cutValue;
rlm@1:   UInt32 maxLen = _maxLen;
rlm@1:   for (;;)
rlm@1:   {
rlm@1:     UInt32 delta = pos - curMatch;
rlm@1:     if (cutValue-- == 0 || delta >= _cyclicBufferSize)
rlm@1:     {
rlm@1:       *ptr0 = *ptr1 = kEmptyHashValue;
rlm@1:       break;
rlm@1:     }
rlm@1:     {
rlm@1:       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
rlm@1:       const Byte *pb = cur - delta;
rlm@1:       UInt32 len = (len0 < len1 ? len0 : len1);
rlm@1:       if (pb[len] == cur[len])
rlm@1:       {
rlm@1:         if (++len != lenLimit && pb[len] == cur[len])
rlm@1:           while (++len != lenLimit)
rlm@1:             if (pb[len] != cur[len])
rlm@1:               break;
rlm@1:         if (maxLen < len)
rlm@1:         {
rlm@1:           *distances++ = maxLen = len;
rlm@1:           *distances++ = delta - 1;
rlm@1:           if (len == lenLimit)
rlm@1:           {
rlm@1:             *ptr1 = pair[0];
rlm@1:             *ptr0 = pair[1];
rlm@1:             break;
rlm@1:           }
rlm@1:         }
rlm@1:       }
rlm@1:       if (pb[len] < cur[len])
rlm@1:       {
rlm@1:         *ptr1 = curMatch;
rlm@1:         ptr1 = pair + 1;
rlm@1:         curMatch = *ptr1;
rlm@1:         len1 = len;
rlm@1:       }
rlm@1:       else
rlm@1:       {
rlm@1:         *ptr0 = curMatch;
rlm@1:         ptr0 = pair;
rlm@1:         curMatch = *ptr0;
rlm@1:         len0 = len;
rlm@1:       }
rlm@1:     }
rlm@1:   }
rlm@1:   pos++;
rlm@1:   _cyclicBufferPos++;
rlm@1:   cur++;
rlm@1:   {
rlm@1:     UInt32 num = (UInt32)(distances - _distances);
rlm@1:     *_distances = num - 1;
rlm@1:     _distances += num;
rlm@1:     limit -= num;
rlm@1:   }
rlm@1:   }
rlm@1:   while (limit > 0 && --size != 0);
rlm@1:   *posRes = pos;
rlm@1:   return limit;
rlm@1: }
rlm@1: 
rlm@1: #endif
rlm@1: 
rlm@1: void BtGetMatches(CMatchFinderMt *p, UInt32 *distances)
rlm@1: {
rlm@1:   UInt32 numProcessed = 0;
rlm@1:   UInt32 curPos = 2;
rlm@1:   UInt32 limit = kMtBtBlockSize - (p->matchMaxLen * 2);
rlm@1:   distances[1] = p->hashNumAvail;
rlm@1:   while (curPos < limit)
rlm@1:   {
rlm@1:     if (p->hashBufPos == p->hashBufPosLimit)
rlm@1:     {
rlm@1:       MatchFinderMt_GetNextBlock_Hash(p);
rlm@1:       distances[1] = numProcessed + p->hashNumAvail;
rlm@1:       if (p->hashNumAvail >= p->numHashBytes)
rlm@1:         continue;
rlm@1:       for (; p->hashNumAvail != 0; p->hashNumAvail--)
rlm@1:         distances[curPos++] = 0;
rlm@1:       break;
rlm@1:     }
rlm@1:     {
rlm@1:       UInt32 size = p->hashBufPosLimit - p->hashBufPos;
rlm@1:       UInt32 lenLimit = p->matchMaxLen;
rlm@1:       UInt32 pos = p->pos;
rlm@1:       UInt32 cyclicBufferPos = p->cyclicBufferPos;
rlm@1:       if (lenLimit >= p->hashNumAvail)
rlm@1:         lenLimit = p->hashNumAvail;
rlm@1:       {
rlm@1:         UInt32 size2 = p->hashNumAvail - lenLimit + 1;
rlm@1:         if (size2 < size)
rlm@1:           size = size2;
rlm@1:         size2 = p->cyclicBufferSize - cyclicBufferPos;
rlm@1:         if (size2 < size)
rlm@1:           size = size2;
rlm@1:       }
rlm@1:       #ifndef MFMT_GM_INLINE
rlm@1:       while (curPos < limit && size-- != 0)
rlm@1:       {
rlm@1:         UInt32 *startDistances = distances + curPos;
rlm@1:         UInt32 num = (UInt32)(GetMatchesSpec1(lenLimit, pos - p->hashBuf[p->hashBufPos++],
rlm@1:           pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,
rlm@1:           startDistances + 1, p->numHashBytes - 1) - startDistances);
rlm@1:         *startDistances = num - 1;
rlm@1:         curPos += num;
rlm@1:         cyclicBufferPos++;
rlm@1:         pos++;
rlm@1:         p->buffer++;
rlm@1:       }
rlm@1:       #else
rlm@1:       {
rlm@1:         UInt32 posRes;
rlm@1:         curPos = limit - GetMatchesSpecN(lenLimit, pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,
rlm@1:           distances + curPos, p->numHashBytes - 1, p->hashBuf + p->hashBufPos, (Int32)(limit - curPos) , size, &posRes);
rlm@1:         p->hashBufPos += posRes - pos;
rlm@1:         cyclicBufferPos += posRes - pos;
rlm@1:         p->buffer += posRes - pos;
rlm@1:         pos = posRes;
rlm@1:       }
rlm@1:       #endif
rlm@1: 
rlm@1:       numProcessed += pos - p->pos;
rlm@1:       p->hashNumAvail -= pos - p->pos;
rlm@1:       p->pos = pos;
rlm@1:       if (cyclicBufferPos == p->cyclicBufferSize)
rlm@1:         cyclicBufferPos = 0;
rlm@1:       p->cyclicBufferPos = cyclicBufferPos;
rlm@1:     }
rlm@1:   }
rlm@1:   distances[0] = curPos;
rlm@1: }
rlm@1: 
rlm@1: void BtFillBlock(CMatchFinderMt *p, UInt32 globalBlockIndex)
rlm@1: {
rlm@1:   CMtSync *sync = &p->hashSync;
rlm@1:   if (!sync->needStart)
rlm@1:   {
rlm@1:     CriticalSection_Enter(&sync->cs);
rlm@1:     sync->csWasEntered = True;
rlm@1:   }
rlm@1:   
rlm@1:   BtGetMatches(p, p->btBuf + (globalBlockIndex & kMtBtNumBlocksMask) * kMtBtBlockSize);
rlm@1: 
rlm@1:   if (p->pos > kMtMaxValForNormalize - kMtBtBlockSize)
rlm@1:   {
rlm@1:     UInt32 subValue = p->pos - p->cyclicBufferSize;
rlm@1:     MatchFinder_Normalize3(subValue, p->son, p->cyclicBufferSize * 2);
rlm@1:     p->pos -= subValue;
rlm@1:   }
rlm@1: 
rlm@1:   if (!sync->needStart)
rlm@1:   {
rlm@1:     CriticalSection_Leave(&sync->cs);
rlm@1:     sync->csWasEntered = False;
rlm@1:   }
rlm@1: }
rlm@1: 
rlm@1: void BtThreadFunc(CMatchFinderMt *mt)
rlm@1: {
rlm@1:   CMtSync *p = &mt->btSync;
rlm@1:   for (;;)
rlm@1:   {
rlm@1:     UInt32 blockIndex = 0;
rlm@1:     Event_Wait(&p->canStart);
rlm@1:     Event_Set(&p->wasStarted);
rlm@1:     for (;;)
rlm@1:     {
rlm@1:       if (p->exit)
rlm@1:         return;
rlm@1:       if (p->stopWriting)
rlm@1:       {
rlm@1:         p->numProcessedBlocks = blockIndex;
rlm@1:         MtSync_StopWriting(&mt->hashSync);
rlm@1:         Event_Set(&p->wasStopped);
rlm@1:         break;
rlm@1:       }
rlm@1:       Semaphore_Wait(&p->freeSemaphore);
rlm@1:       BtFillBlock(mt, blockIndex++);
rlm@1:       Semaphore_Release1(&p->filledSemaphore);
rlm@1:     }
rlm@1:   }
rlm@1: }
rlm@1: 
rlm@1: void MatchFinderMt_Construct(CMatchFinderMt *p)
rlm@1: {
rlm@1:   p->hashBuf = 0;
rlm@1:   MtSync_Construct(&p->hashSync);
rlm@1:   MtSync_Construct(&p->btSync);
rlm@1: }
rlm@1: 
rlm@1: void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAlloc *alloc)
rlm@1: {
rlm@1:   alloc->Free(alloc, p->hashBuf);
rlm@1:   p->hashBuf = 0;
rlm@1: }
rlm@1: 
rlm@1: void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAlloc *alloc)
rlm@1: {
rlm@1:   MtSync_Destruct(&p->hashSync);
rlm@1:   MtSync_Destruct(&p->btSync);
rlm@1:   MatchFinderMt_FreeMem(p, alloc);
rlm@1: }
rlm@1: 
rlm@1: #define kHashBufferSize (kMtHashBlockSize * kMtHashNumBlocks)
rlm@1: #define kBtBufferSize (kMtBtBlockSize * kMtBtNumBlocks)
rlm@1: 
rlm@1: static unsigned MY_STD_CALL HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p);  return 0; }
rlm@1: static unsigned MY_STD_CALL BtThreadFunc2(void *p)
rlm@1: {
rlm@1:   Byte allocaDummy[0x180];
rlm@1:   int i = 0;
rlm@1:   for (i = 0; i < 16; i++)
rlm@1:     allocaDummy[i] = (Byte)i;
rlm@1:   BtThreadFunc((CMatchFinderMt *)p);
rlm@1:   return 0;
rlm@1: }
rlm@1: 
rlm@1: SRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore,
rlm@1:     UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAlloc *alloc)
rlm@1: {
rlm@1:   CMatchFinder *mf = p->MatchFinder;
rlm@1:   p->historySize = historySize;
rlm@1:   if (kMtBtBlockSize <= matchMaxLen * 4)
rlm@1:     return SZ_ERROR_PARAM;
rlm@1:   if (p->hashBuf == 0)
rlm@1:   {
rlm@1:     p->hashBuf = (UInt32 *)alloc->Alloc(alloc, (kHashBufferSize + kBtBufferSize) * sizeof(UInt32));
rlm@1:     if (p->hashBuf == 0)
rlm@1:       return SZ_ERROR_MEM;
rlm@1:     p->btBuf = p->hashBuf + kHashBufferSize;
rlm@1:   }
rlm@1:   keepAddBufferBefore += (kHashBufferSize + kBtBufferSize);
rlm@1:   keepAddBufferAfter += kMtHashBlockSize;
rlm@1:   if (!MatchFinder_Create(mf, historySize, keepAddBufferBefore, matchMaxLen, keepAddBufferAfter, alloc))
rlm@1:     return SZ_ERROR_MEM;
rlm@1: 
rlm@1:   RINOK(MtSync_Create(&p->hashSync, HashThreadFunc2, p, kMtHashNumBlocks));
rlm@1:   RINOK(MtSync_Create(&p->btSync, BtThreadFunc2, p, kMtBtNumBlocks));
rlm@1:   return SZ_OK;
rlm@1: }
rlm@1: 
rlm@1: /* Call it after ReleaseStream / SetStream */
rlm@1: void MatchFinderMt_Init(CMatchFinderMt *p)
rlm@1: {
rlm@1:   CMatchFinder *mf = p->MatchFinder;
rlm@1:   p->btBufPos = p->btBufPosLimit = 0;
rlm@1:   p->hashBufPos = p->hashBufPosLimit = 0;
rlm@1:   MatchFinder_Init(mf);
rlm@1:   p->pointerToCurPos = MatchFinder_GetPointerToCurrentPos(mf);
rlm@1:   p->btNumAvailBytes = 0;
rlm@1:   p->lzPos = p->historySize + 1;
rlm@1: 
rlm@1:   p->hash = mf->hash;
rlm@1:   p->fixedHashSize = mf->fixedHashSize;
rlm@1:   p->crc = mf->crc;
rlm@1: 
rlm@1:   p->son = mf->son;
rlm@1:   p->matchMaxLen = mf->matchMaxLen;
rlm@1:   p->numHashBytes = mf->numHashBytes;
rlm@1:   p->pos = mf->pos;
rlm@1:   p->buffer = mf->buffer;
rlm@1:   p->cyclicBufferPos = mf->cyclicBufferPos;
rlm@1:   p->cyclicBufferSize = mf->cyclicBufferSize;
rlm@1:   p->cutValue = mf->cutValue;
rlm@1: }
rlm@1: 
rlm@1: /* ReleaseStream is required to finish multithreading */
rlm@1: void MatchFinderMt_ReleaseStream(CMatchFinderMt *p)
rlm@1: {
rlm@1:   MtSync_StopWriting(&p->btSync);
rlm@1:   /* p->MatchFinder->ReleaseStream(); */
rlm@1: }
rlm@1: 
rlm@1: void MatchFinderMt_Normalize(CMatchFinderMt *p)
rlm@1: {
rlm@1:   MatchFinder_Normalize3(p->lzPos - p->historySize - 1, p->hash, p->fixedHashSize);
rlm@1:   p->lzPos = p->historySize + 1;
rlm@1: }
rlm@1: 
rlm@1: void MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt *p)
rlm@1: {
rlm@1:   UInt32 blockIndex;
rlm@1:   MtSync_GetNextBlock(&p->btSync);
rlm@1:   blockIndex = ((p->btSync.numProcessedBlocks - 1) & kMtBtNumBlocksMask);
rlm@1:   p->btBufPosLimit = p->btBufPos = blockIndex * kMtBtBlockSize;
rlm@1:   p->btBufPosLimit += p->btBuf[p->btBufPos++];
rlm@1:   p->btNumAvailBytes = p->btBuf[p->btBufPos++];
rlm@1:   if (p->lzPos >= kMtMaxValForNormalize - kMtBtBlockSize)
rlm@1:     MatchFinderMt_Normalize(p);
rlm@1: }
rlm@1: 
rlm@1: const Byte * MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt *p)
rlm@1: {
rlm@1:   return p->pointerToCurPos;
rlm@1: }
rlm@1: 
rlm@1: #define GET_NEXT_BLOCK_IF_REQUIRED if (p->btBufPos == p->btBufPosLimit) MatchFinderMt_GetNextBlock_Bt(p);
rlm@1: 
rlm@1: UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p)
rlm@1: {
rlm@1:   GET_NEXT_BLOCK_IF_REQUIRED;
rlm@1:   return p->btNumAvailBytes;
rlm@1: }
rlm@1: 
rlm@1: Byte MatchFinderMt_GetIndexByte(CMatchFinderMt *p, Int32 index)
rlm@1: {
rlm@1:   return p->pointerToCurPos[index];
rlm@1: }
rlm@1: 
rlm@1: UInt32 * MixMatches2(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
rlm@1: {
rlm@1:   UInt32 hash2Value, curMatch2;
rlm@1:   UInt32 *hash = p->hash;
rlm@1:   const Byte *cur = p->pointerToCurPos;
rlm@1:   UInt32 lzPos = p->lzPos;
rlm@1:   MT_HASH2_CALC
rlm@1:       
rlm@1:   curMatch2 = hash[hash2Value];
rlm@1:   hash[hash2Value] = lzPos;
rlm@1: 
rlm@1:   if (curMatch2 >= matchMinPos)
rlm@1:     if (cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
rlm@1:     {
rlm@1:       *distances++ = 2;
rlm@1:       *distances++ = lzPos - curMatch2 - 1;
rlm@1:     }
rlm@1:   return distances;
rlm@1: }
rlm@1: 
rlm@1: UInt32 * MixMatches3(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
rlm@1: {
rlm@1:   UInt32 hash2Value, hash3Value, curMatch2, curMatch3;
rlm@1:   UInt32 *hash = p->hash;
rlm@1:   const Byte *cur = p->pointerToCurPos;
rlm@1:   UInt32 lzPos = p->lzPos;
rlm@1:   MT_HASH3_CALC
rlm@1: 
rlm@1:   curMatch2 = hash[                hash2Value];
rlm@1:   curMatch3 = hash[kFix3HashSize + hash3Value];
rlm@1:   
rlm@1:   hash[                hash2Value] =
rlm@1:   hash[kFix3HashSize + hash3Value] =
rlm@1:     lzPos;
rlm@1: 
rlm@1:   if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
rlm@1:   {
rlm@1:     distances[1] = lzPos - curMatch2 - 1;
rlm@1:     if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])
rlm@1:     {
rlm@1:       distances[0] = 3;
rlm@1:       return distances + 2;
rlm@1:     }
rlm@1:     distances[0] = 2;
rlm@1:     distances += 2;
rlm@1:   }
rlm@1:   if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])
rlm@1:   {
rlm@1:     *distances++ = 3;
rlm@1:     *distances++ = lzPos - curMatch3 - 1;
rlm@1:   }
rlm@1:   return distances;
rlm@1: }
rlm@1: 
rlm@1: /*
rlm@1: UInt32 *MixMatches4(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
rlm@1: {
rlm@1:   UInt32 hash2Value, hash3Value, hash4Value, curMatch2, curMatch3, curMatch4;
rlm@1:   UInt32 *hash = p->hash;
rlm@1:   const Byte *cur = p->pointerToCurPos;
rlm@1:   UInt32 lzPos = p->lzPos;
rlm@1:   MT_HASH4_CALC
rlm@1:       
rlm@1:   curMatch2 = hash[                hash2Value];
rlm@1:   curMatch3 = hash[kFix3HashSize + hash3Value];
rlm@1:   curMatch4 = hash[kFix4HashSize + hash4Value];
rlm@1:   
rlm@1:   hash[                hash2Value] =
rlm@1:   hash[kFix3HashSize + hash3Value] =
rlm@1:   hash[kFix4HashSize + hash4Value] =
rlm@1:     lzPos;
rlm@1: 
rlm@1:   if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
rlm@1:   {
rlm@1:     distances[1] = lzPos - curMatch2 - 1;
rlm@1:     if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])
rlm@1:     {
rlm@1:       distances[0] =  (cur[(ptrdiff_t)curMatch2 - lzPos + 3] == cur[3]) ? 4 : 3;
rlm@1:       return distances + 2;
rlm@1:     }
rlm@1:     distances[0] = 2;
rlm@1:     distances += 2;
rlm@1:   }
rlm@1:   if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])
rlm@1:   {
rlm@1:     distances[1] = lzPos - curMatch3 - 1;
rlm@1:     if (cur[(ptrdiff_t)curMatch3 - lzPos + 3] == cur[3])
rlm@1:     {
rlm@1:       distances[0] = 4;
rlm@1:       return distances + 2;
rlm@1:     }
rlm@1:     distances[0] = 3;
rlm@1:     distances += 2;
rlm@1:   }
rlm@1: 
rlm@1:   if (curMatch4 >= matchMinPos)
rlm@1:     if (
rlm@1:       cur[(ptrdiff_t)curMatch4 - lzPos] == cur[0] &&
rlm@1:       cur[(ptrdiff_t)curMatch4 - lzPos + 3] == cur[3]
rlm@1:       )
rlm@1:     {
rlm@1:       *distances++ = 4;
rlm@1:       *distances++ = lzPos - curMatch4 - 1;
rlm@1:     }
rlm@1:   return distances;
rlm@1: }
rlm@1: */
rlm@1: 
rlm@1: #define INCREASE_LZ_POS p->lzPos++; p->pointerToCurPos++;
rlm@1: 
rlm@1: UInt32 MatchFinderMt2_GetMatches(CMatchFinderMt *p, UInt32 *distances)
rlm@1: {
rlm@1:   const UInt32 *btBuf = p->btBuf + p->btBufPos;
rlm@1:   UInt32 len = *btBuf++;
rlm@1:   p->btBufPos += 1 + len;
rlm@1:   p->btNumAvailBytes--;
rlm@1:   {
rlm@1:     UInt32 i;
rlm@1:     for (i = 0; i < len; i += 2)
rlm@1:     {
rlm@1:       *distances++ = *btBuf++;
rlm@1:       *distances++ = *btBuf++;
rlm@1:     }
rlm@1:   }
rlm@1:   INCREASE_LZ_POS
rlm@1:   return len;
rlm@1: }
rlm@1: 
rlm@1: UInt32 MatchFinderMt_GetMatches(CMatchFinderMt *p, UInt32 *distances)
rlm@1: {
rlm@1:   const UInt32 *btBuf = p->btBuf + p->btBufPos;
rlm@1:   UInt32 len = *btBuf++;
rlm@1:   p->btBufPos += 1 + len;
rlm@1: 
rlm@1:   if (len == 0)
rlm@1:   {
rlm@1:     if (p->btNumAvailBytes-- >= 4)
rlm@1:       len = (UInt32)(p->MixMatchesFunc(p, p->lzPos - p->historySize, distances) - (distances));
rlm@1:   }
rlm@1:   else
rlm@1:   {
rlm@1:     /* Condition: there are matches in btBuf with length < p->numHashBytes */
rlm@1:     UInt32 *distances2;
rlm@1:     p->btNumAvailBytes--;
rlm@1:     distances2 = p->MixMatchesFunc(p, p->lzPos - btBuf[1], distances);
rlm@1:     do
rlm@1:     {
rlm@1:       *distances2++ = *btBuf++;
rlm@1:       *distances2++ = *btBuf++;
rlm@1:     }
rlm@1:     while ((len -= 2) != 0);
rlm@1:     len  = (UInt32)(distances2 - (distances));
rlm@1:   }
rlm@1:   INCREASE_LZ_POS
rlm@1:   return len;
rlm@1: }
rlm@1: 
rlm@1: #define SKIP_HEADER2  do { GET_NEXT_BLOCK_IF_REQUIRED
rlm@1: #define SKIP_HEADER(n) SKIP_HEADER2 if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash;
rlm@1: #define SKIP_FOOTER } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while (--num != 0);
rlm@1: 
rlm@1: void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num)
rlm@1: {
rlm@1:   SKIP_HEADER2 { p->btNumAvailBytes--;
rlm@1:   SKIP_FOOTER
rlm@1: }
rlm@1: 
rlm@1: void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num)
rlm@1: {
rlm@1:   SKIP_HEADER(2)
rlm@1:       UInt32 hash2Value;
rlm@1:       MT_HASH2_CALC
rlm@1:       hash[hash2Value] = p->lzPos;
rlm@1:   SKIP_FOOTER
rlm@1: }
rlm@1: 
rlm@1: void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num)
rlm@1: {
rlm@1:   SKIP_HEADER(3)
rlm@1:       UInt32 hash2Value, hash3Value;
rlm@1:       MT_HASH3_CALC
rlm@1:       hash[kFix3HashSize + hash3Value] =
rlm@1:       hash[                hash2Value] =
rlm@1:         p->lzPos;
rlm@1:   SKIP_FOOTER
rlm@1: }
rlm@1: 
rlm@1: /*
rlm@1: void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num)
rlm@1: {
rlm@1:   SKIP_HEADER(4)
rlm@1:       UInt32 hash2Value, hash3Value, hash4Value;
rlm@1:       MT_HASH4_CALC
rlm@1:       hash[kFix4HashSize + hash4Value] =
rlm@1:       hash[kFix3HashSize + hash3Value] =
rlm@1:       hash[                hash2Value] =
rlm@1:         p->lzPos;
rlm@1:   SKIP_FOOTER
rlm@1: }
rlm@1: */
rlm@1: 
rlm@1: void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable)
rlm@1: {
rlm@1:   vTable->Init = (Mf_Init_Func)MatchFinderMt_Init;
rlm@1:   vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinderMt_GetIndexByte;
rlm@1:   vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinderMt_GetNumAvailableBytes;
rlm@1:   vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinderMt_GetPointerToCurrentPos;
rlm@1:   vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt_GetMatches;
rlm@1:   switch(p->MatchFinder->numHashBytes)
rlm@1:   {
rlm@1:     case 2:
rlm@1:       p->GetHeadsFunc = GetHeads2;
rlm@1:       p->MixMatchesFunc = (Mf_Mix_Matches)0;
rlm@1:       vTable->Skip = (Mf_Skip_Func)MatchFinderMt0_Skip;
rlm@1:       vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt2_GetMatches;
rlm@1:       break;
rlm@1:     case 3:
rlm@1:       p->GetHeadsFunc = GetHeads3;
rlm@1:       p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches2;
rlm@1:       vTable->Skip = (Mf_Skip_Func)MatchFinderMt2_Skip;
rlm@1:       break;
rlm@1:     default:
rlm@1:     /* case 4: */
rlm@1:       p->GetHeadsFunc = p->MatchFinder->bigHash ? GetHeads4b : GetHeads4;
rlm@1:       /* p->GetHeadsFunc = GetHeads4; */
rlm@1:       p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches3;
rlm@1:       vTable->Skip = (Mf_Skip_Func)MatchFinderMt3_Skip;
rlm@1:       break;
rlm@1:     /*
rlm@1:     default:
rlm@1:       p->GetHeadsFunc = GetHeads5;
rlm@1:       p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches4;
rlm@1:       vTable->Skip = (Mf_Skip_Func)MatchFinderMt4_Skip;
rlm@1:       break;
rlm@1:     */
rlm@1:   }
rlm@1: }