1 /* MatchFinderMt.c */

     2 

     3 #ifdef _WIN32

     4 #define USE_ALLOCA

     5 #endif

     6 

     7 #ifdef USE_ALLOCA

     8 #ifdef _WIN32

     9 #include <malloc.h>

    10 #else

    11 #include <stdlib.h>

    12 #endif

    13 #endif

    14 

    15 #include "../../7zCrc.h"

    16 #include "LzHash.h"

    17 

    18 #include "MatchFinderMt.h"

    19 

    20 void MtSync_Construct(CMtSync *p)

    21 {

    22   p->wasCreated = False;

    23   p->csWasInitialized = False;

    24   p->csWasEntered = False;

    25   Thread_Construct(&p->thread);

    26   Event_Construct(&p->canStart);

    27   Event_Construct(&p->wasStarted);

    28   Event_Construct(&p->wasStopped);

    29   Semaphore_Construct(&p->freeSemaphore);

    30   Semaphore_Construct(&p->filledSemaphore);

    31 }

    32 

    33 void MtSync_GetNextBlock(CMtSync *p)

    34 {

    35   if (p->needStart)

    36   {

    37     p->numProcessedBlocks = 1;

    38     p->needStart = False;

    39     p->stopWriting = False;

    40     p->exit = False;

    41     Event_Reset(&p->wasStarted);

    42     Event_Reset(&p->wasStopped);

    43 

    44     Event_Set(&p->canStart);

    45     Event_Wait(&p->wasStarted);

    46   }

    47   else

    48   {

    49     CriticalSection_Leave(&p->cs);

    50     p->csWasEntered = False;

    51     p->numProcessedBlocks++;

    52     Semaphore_Release1(&p->freeSemaphore);

    53   }

    54   Semaphore_Wait(&p->filledSemaphore);

    55   CriticalSection_Enter(&p->cs);

    56   p->csWasEntered = True;

    57 }

    58 

    59 /* MtSync_StopWriting must be called if Writing was started */

    60 

    61 void MtSync_StopWriting(CMtSync *p)

    62 { 

    63   UInt32 myNumBlocks = p->numProcessedBlocks;

    64   if (!Thread_WasCreated(&p->thread) || p->needStart)

    65     return;

    66   p->stopWriting = True;

    67   if (p->csWasEntered)

    68   {

    69     CriticalSection_Leave(&p->cs);

    70     p->csWasEntered = False;

    71   }

    72   Semaphore_Release1(&p->freeSemaphore);

    73  

    74   Event_Wait(&p->wasStopped);

    75 

    76   while (myNumBlocks++ != p->numProcessedBlocks)

    77   {

    78     Semaphore_Wait(&p->filledSemaphore);

    79     Semaphore_Release1(&p->freeSemaphore);

    80   }

    81   p->needStart = True;

    82 }

    83 

    84 void MtSync_Destruct(CMtSync *p)

    85 {

    86   if (Thread_WasCreated(&p->thread))

    87   {

    88     MtSync_StopWriting(p);

    89     p->exit = True;

    90     if (p->needStart)

    91       Event_Set(&p->canStart);

    92     Thread_Wait(&p->thread);

    93     Thread_Close(&p->thread);

    94   }

    95   if (p->csWasInitialized)

    96   {

    97     CriticalSection_Delete(&p->cs);

    98     p->csWasInitialized = False;

    99   }

   100 

   101   Event_Close(&p->canStart);

   102   Event_Close(&p->wasStarted);

   103   Event_Close(&p->wasStopped);

   104   Semaphore_Close(&p->freeSemaphore);

   105   Semaphore_Close(&p->filledSemaphore);

   106 

   107   p->wasCreated = False;

   108 }

   109 

   110 HRes MtSync_Create2(CMtSync *p, unsigned (StdCall *startAddress)(void *), void *obj, UInt32 numBlocks)

   111 {

   112   if (p->wasCreated)

   113     return SZ_OK;

   114 

   115   RINOK(CriticalSection_Init(&p->cs));

   116   p->csWasInitialized = True;

   117 

   118   RINOK(AutoResetEvent_CreateNotSignaled(&p->canStart));

   119   RINOK(AutoResetEvent_CreateNotSignaled(&p->wasStarted));

   120   RINOK(AutoResetEvent_CreateNotSignaled(&p->wasStopped));

   121   

   122   RINOK(Semaphore_Create(&p->freeSemaphore, numBlocks, numBlocks));

   123   RINOK(Semaphore_Create(&p->filledSemaphore, 0, numBlocks));

   124 

   125   p->needStart = True;

   126   

   127   RINOK(Thread_Create(&p->thread, startAddress, obj));

   128   p->wasCreated = True;

   129   return SZ_OK;

   130 }

   131 

   132 HRes MtSync_Create(CMtSync *p, unsigned (StdCall *startAddress)(void *), void *obj, UInt32 numBlocks)

   133 {

   134   HRes res = MtSync_Create2(p, startAddress, obj, numBlocks);

   135   if (res != SZ_OK)

   136     MtSync_Destruct(p);

   137   return res;

   138 }

   139 

   140 

   141 void MtSync_Init(CMtSync *p) { p->needStart = True; }

   142 

   143 #define kMtMaxValForNormalize 0xFFFFFFFF

   144 

   145 #define DEF_GetHeads(name, v) \

   146 static void GetHeads ## name(const Byte *p, UInt32 pos, \

   147 UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads) { \

   148 for (; numHeads != 0; numHeads--) { \

   149 const UInt32 value = (v); p++; *heads++ = pos - hash[value]; hash[value] = pos++;  } }

   150 

   151 DEF_GetHeads(2,  (p[0] | ((UInt32)p[1] << 8)) & hashMask)

   152 DEF_GetHeads(3,  (g_CrcTable[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask)

   153 DEF_GetHeads(4,  (g_CrcTable[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (g_CrcTable[p[3]] << 5)) & hashMask)

   154 DEF_GetHeads(4b, (g_CrcTable[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ ((UInt32)p[3] << 16)) & hashMask)

   155 DEF_GetHeads(5,  (g_CrcTable[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (g_CrcTable[p[3]] << 5) ^ (g_CrcTable[p[4]] << 3)) & hashMask)

   156 

   157 void HashThreadFunc(CMatchFinderMt *mt)

   158 {

   159   CMtSync *p = &mt->hashSync;

   160   for (;;)

   161   {

   162     UInt32 numProcessedBlocks = 0;

   163     Event_Wait(&p->canStart);

   164     Event_Set(&p->wasStarted);

   165     for (;;)

   166     {

   167       if (p->exit)

   168         return;

   169       if (p->stopWriting)

   170       {

   171         p->numProcessedBlocks = numProcessedBlocks;

   172         Event_Set(&p->wasStopped);

   173         break;

   174       }

   175 

   176       {

   177         CMatchFinder *mf = mt->MatchFinder;

   178         if (MatchFinder_NeedMove(mf))

   179         {

   180           CriticalSection_Enter(&mt->btSync.cs);

   181           CriticalSection_Enter(&mt->hashSync.cs);

   182           {

   183             const Byte *beforePtr = MatchFinder_GetPointerToCurrentPos(mf);

   184             const Byte *afterPtr;

   185             MatchFinder_MoveBlock(mf);

   186             afterPtr = MatchFinder_GetPointerToCurrentPos(mf);

   187             mt->pointerToCurPos -= beforePtr - afterPtr;

   188             mt->buffer -= beforePtr - afterPtr;

   189           }

   190           CriticalSection_Leave(&mt->btSync.cs);

   191           CriticalSection_Leave(&mt->hashSync.cs);

   192           continue;

   193         }

   194 

   195         Semaphore_Wait(&p->freeSemaphore);

   196 

   197         MatchFinder_ReadIfRequired(mf);

   198         if (mf->pos > (kMtMaxValForNormalize - kMtHashBlockSize))

   199         {

   200           UInt32 subValue = (mf->pos - mf->historySize - 1);

   201           MatchFinder_ReduceOffsets(mf, subValue);

   202           MatchFinder_Normalize3(subValue, mf->hash + mf->fixedHashSize, mf->hashMask + 1);

   203         }

   204         {

   205           UInt32 *heads = mt->hashBuf + ((numProcessedBlocks++) & kMtHashNumBlocksMask) * kMtHashBlockSize;

   206           UInt32 num = mf->streamPos - mf->pos;

   207           heads[0] = 2;

   208           heads[1] = num;

   209           if (num >= mf->numHashBytes)

   210           {

   211             num = num - mf->numHashBytes + 1;

   212             if (num > kMtHashBlockSize - 2)

   213               num = kMtHashBlockSize - 2;

   214             mt->GetHeadsFunc(mf->buffer, mf->pos, mf->hash + mf->fixedHashSize, mf->hashMask, heads + 2, num);

   215             heads[0] += num;

   216           }

   217           mf->pos += num;

   218           mf->buffer += num;

   219         }

   220       }

   221 

   222       Semaphore_Release1(&p->filledSemaphore);

   223     }

   224   }

   225 }

   226 

   227 void MatchFinderMt_GetNextBlock_Hash(CMatchFinderMt *p)

   228 {

   229   MtSync_GetNextBlock(&p->hashSync);

   230   p->hashBufPosLimit = p->hashBufPos = ((p->hashSync.numProcessedBlocks - 1) & kMtHashNumBlocksMask) * kMtHashBlockSize;

   231   p->hashBufPosLimit += p->hashBuf[p->hashBufPos++];

   232   p->hashNumAvail = p->hashBuf[p->hashBufPos++];

   233 }

   234 

   235 #define kEmptyHashValue 0

   236 

   237 /* #define MFMT_GM_INLINE */

   238 

   239 #ifdef MFMT_GM_INLINE

   240 

   241 #if _MSC_VER >= 1300

   242 #define NO_INLINE __declspec(noinline) __fastcall 

   243 #else

   244 #ifdef _MSC_VER

   245 #define NO_INLINE __fastcall 

   246 #endif

   247 #endif

   248 

   249 Int32 NO_INLINE GetMatchesSpecN(UInt32 lenLimit, UInt32 pos, const Byte *cur, CLzRef *son, 

   250     UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue, 

   251     UInt32 *_distances, UInt32 _maxLen, const UInt32 *hash, Int32 limit, UInt32 size, UInt32 *posRes)

   252 {

   253   do

   254   {

   255   UInt32 *distances = _distances + 1;

   256   UInt32 curMatch = pos - *hash++;

   257 

   258   CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;

   259   CLzRef *ptr1 = son + (_cyclicBufferPos << 1);

   260   UInt32 len0 = 0, len1 = 0;

   261   UInt32 cutValue = _cutValue;

   262   UInt32 maxLen = _maxLen;

   263   for (;;)

   264   {

   265     UInt32 delta = pos - curMatch;

   266     if (cutValue-- == 0 || delta >= _cyclicBufferSize)

   267     {

   268       *ptr0 = *ptr1 = kEmptyHashValue;

   269       break;

   270     }

   271     {

   272       CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);

   273       const Byte *pb = cur - delta;

   274       UInt32 len = (len0 < len1 ? len0 : len1);

   275       if (pb[len] == cur[len])

   276       {

   277         if (++len != lenLimit && pb[len] == cur[len])

   278           while(++len != lenLimit)

   279             if (pb[len] != cur[len])

   280               break;

   281         if (maxLen < len)

   282         {

   283           *distances++ = maxLen = len;

   284           *distances++ = delta - 1;

   285           if (len == lenLimit)

   286           {

   287             *ptr1 = pair[0];

   288             *ptr0 = pair[1];

   289             break;

   290           }

   291         }

   292       }

   293       if (pb[len] < cur[len])

   294       {

   295         *ptr1 = curMatch;

   296         ptr1 = pair + 1;

   297         curMatch = *ptr1;

   298         len1 = len;

   299       }

   300       else

   301       {

   302         *ptr0 = curMatch;

   303         ptr0 = pair;

   304         curMatch = *ptr0;

   305         len0 = len;

   306       }

   307     }

   308   }

   309   pos++;

   310   _cyclicBufferPos++;

   311   cur++;

   312   {

   313     UInt32 num = (UInt32)(distances - _distances);

   314     *_distances = num - 1;

   315     _distances += num;

   316     limit -= num;

   317   }

   318   }

   319   while (limit > 0 && --size != 0);

   320   *posRes = pos;

   321   return limit;

   322 }

   323 

   324 #endif

   325 

   326 void BtGetMatches(CMatchFinderMt *p, UInt32 *distances)

   327 {

   328   UInt32 numProcessed = 0;

   329   UInt32 curPos = 2;

   330   UInt32 limit = kMtBtBlockSize - (p->matchMaxLen * 2);

   331   distances[1] = p->hashNumAvail;

   332   while (curPos < limit)

   333   {

   334     if (p->hashBufPos == p->hashBufPosLimit)

   335     {

   336       MatchFinderMt_GetNextBlock_Hash(p);

   337       distances[1] = numProcessed + p->hashNumAvail;

   338       if (p->hashNumAvail >= p->numHashBytes)

   339         continue;

   340       for (; p->hashNumAvail != 0; p->hashNumAvail--)

   341         distances[curPos++] = 0;

   342       break;

   343     }

   344     {

   345       UInt32 size = p->hashBufPosLimit - p->hashBufPos;

   346       UInt32 lenLimit = p->matchMaxLen;

   347       UInt32 pos = p->pos;

   348       UInt32 cyclicBufferPos = p->cyclicBufferPos;

   349       if (lenLimit >= p->hashNumAvail)

   350         lenLimit = p->hashNumAvail;

   351       {

   352         UInt32 size2 = p->hashNumAvail - lenLimit + 1;

   353         if (size2 < size)

   354           size = size2;

   355         size2 = p->cyclicBufferSize - cyclicBufferPos;

   356         if (size2 < size)

   357           size = size2;

   358       }

   359       #ifndef MFMT_GM_INLINE

   360       while (curPos < limit && size-- != 0)

   361       {

   362         UInt32 *startDistances = distances + curPos;

   363         UInt32 num = (UInt32)(GetMatchesSpec1(lenLimit, pos - p->hashBuf[p->hashBufPos++], 

   364           pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue, 

   365           startDistances + 1, p->numHashBytes - 1) - startDistances);

   366         *startDistances = num - 1;

   367         curPos += num;

   368         cyclicBufferPos++;

   369         pos++;

   370         p->buffer++;

   371       }

   372       #else

   373       {

   374         UInt32 posRes;

   375         curPos = limit - GetMatchesSpecN(lenLimit, pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue, 

   376           distances + curPos, p->numHashBytes - 1, p->hashBuf + p->hashBufPos, (Int32)(limit - curPos) , size, &posRes);

   377         p->hashBufPos += posRes - pos;

   378         cyclicBufferPos += posRes - pos;

   379         p->buffer += posRes - pos;

   380         pos = posRes;

   381       }

   382       #endif

   383 

   384       numProcessed += pos - p->pos;

   385       p->hashNumAvail -= pos - p->pos;

   386       p->pos = pos;

   387       if (cyclicBufferPos == p->cyclicBufferSize)

   388         cyclicBufferPos = 0;

   389       p->cyclicBufferPos = cyclicBufferPos;

   390     }

   391   }

   392   distances[0] = curPos;

   393 }

   394 

   395 void BtFillBlock(CMatchFinderMt *p, UInt32 globalBlockIndex)

   396 {

   397   CMtSync *sync = &p->hashSync;

   398   if (!sync->needStart)

   399   {

   400     CriticalSection_Enter(&sync->cs);

   401     sync->csWasEntered = True;

   402   }

   403   

   404   BtGetMatches(p, p->btBuf + (globalBlockIndex & kMtBtNumBlocksMask) * kMtBtBlockSize);

   405 

   406   if (p->pos > kMtMaxValForNormalize - kMtBtBlockSize)

   407   {

   408     UInt32 subValue = p->pos - p->cyclicBufferSize;

   409     MatchFinder_Normalize3(subValue, p->son, p->cyclicBufferSize * 2);

   410     p->pos -= subValue;

   411   }

   412 

   413   if (!sync->needStart)

   414   {

   415     CriticalSection_Leave(&sync->cs);

   416     sync->csWasEntered = False;

   417   }

   418 }

   419 

   420 void BtThreadFunc(CMatchFinderMt *mt)

   421 {

   422   CMtSync *p = &mt->btSync;

   423   for (;;)

   424   {

   425     UInt32 blockIndex = 0;

   426     Event_Wait(&p->canStart);

   427     Event_Set(&p->wasStarted);

   428     for (;;)

   429     {

   430       if (p->exit)

   431         return;

   432       if (p->stopWriting)

   433       {

   434         p->numProcessedBlocks = blockIndex;

   435         MtSync_StopWriting(&mt->hashSync);

   436         Event_Set(&p->wasStopped);

   437         break;

   438       }

   439       Semaphore_Wait(&p->freeSemaphore);

   440       BtFillBlock(mt, blockIndex++);

   441       Semaphore_Release1(&p->filledSemaphore);

   442     }

   443   }

   444 }

   445 

   446 void MatchFinderMt_Construct(CMatchFinderMt *p)

   447 {

   448   p->hashBuf = 0;

   449   MtSync_Construct(&p->hashSync);

   450   MtSync_Construct(&p->btSync);

   451 }

   452 

   453 void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAlloc *alloc)

   454 {

   455   alloc->Free(p->hashBuf);

   456   p->hashBuf = 0;

   457 }

   458 

   459 void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAlloc *alloc)

   460 {

   461   MtSync_Destruct(&p->hashSync);

   462   MtSync_Destruct(&p->btSync);

   463   MatchFinderMt_FreeMem(p, alloc);

   464 }

   465 

   466 #define kHashBufferSize (kMtHashBlockSize * kMtHashNumBlocks)

   467 #define kBtBufferSize (kMtBtBlockSize * kMtBtNumBlocks)

   468 

   469 static unsigned StdCall HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p);  return 0; }

   470 static unsigned StdCall BtThreadFunc2(void *p) 

   471 { 

   472   #ifdef USE_ALLOCA

   473   alloca(0x180);

   474   #endif

   475   BtThreadFunc((CMatchFinderMt *)p); 

   476   return 0; 

   477 }

   478 

   479 HRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore, 

   480     UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAlloc *alloc)

   481 { 

   482   CMatchFinder *mf = p->MatchFinder;

   483   p->historySize = historySize;

   484   if (kMtBtBlockSize <= matchMaxLen * 4)

   485     return E_INVALIDARG;

   486   if (p->hashBuf == 0)

   487   {

   488     p->hashBuf = (UInt32 *)alloc->Alloc((kHashBufferSize + kBtBufferSize) * sizeof(UInt32));

   489     if (p->hashBuf == 0)

   490       return SZE_OUTOFMEMORY;

   491     p->btBuf = p->hashBuf + kHashBufferSize;

   492   }

   493   keepAddBufferBefore += (kHashBufferSize + kBtBufferSize);

   494   keepAddBufferAfter += kMtHashBlockSize;

   495   if (!MatchFinder_Create(mf, historySize, keepAddBufferBefore, matchMaxLen, keepAddBufferAfter, alloc))

   496     return SZE_OUTOFMEMORY;

   497 

   498   RINOK(MtSync_Create(&p->hashSync, HashThreadFunc2, p, kMtHashNumBlocks));

   499   RINOK(MtSync_Create(&p->btSync, BtThreadFunc2, p, kMtBtNumBlocks));

   500   return SZ_OK;

   501 }

   502 

   503 /* Call it after ReleaseStream / SetStream */

   504 void MatchFinderMt_Init(CMatchFinderMt *p)

   505 { 

   506   CMatchFinder *mf = p->MatchFinder;

   507   p->btBufPos = p->btBufPosLimit = 0;

   508   p->hashBufPos = p->hashBufPosLimit = 0;

   509   MatchFinder_Init(mf);

   510   p->pointerToCurPos = MatchFinder_GetPointerToCurrentPos(mf);

   511   p->btNumAvailBytes = 0;

   512   p->lzPos = p->historySize + 1;

   513 

   514   p->hash = mf->hash;

   515   p->fixedHashSize = mf->fixedHashSize;

   516 

   517   p->son = mf->son;

   518   p->matchMaxLen = mf->matchMaxLen;

   519   p->numHashBytes = mf->numHashBytes;

   520   p->pos = mf->pos;

   521   p->buffer = mf->buffer;

   522   p->cyclicBufferPos = mf->cyclicBufferPos;

   523   p->cyclicBufferSize = mf->cyclicBufferSize;

   524   p->cutValue = mf->cutValue;

   525 }

   526 

   527 /* ReleaseStream is required to finish multithreading */

   528 void MatchFinderMt_ReleaseStream(CMatchFinderMt *p)

   529 { 

   530   MtSync_StopWriting(&p->btSync);

   531   /* p->MatchFinder->ReleaseStream(); */

   532 }

   533 

   534 void MatchFinderMt_Normalize(CMatchFinderMt *p)

   535 {

   536   MatchFinder_Normalize3(p->lzPos - p->historySize - 1, p->hash, p->fixedHashSize);

   537   p->lzPos = p->historySize + 1;

   538 }

   539 

   540 void MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt *p)

   541 {

   542   UInt32 blockIndex;

   543   MtSync_GetNextBlock(&p->btSync);

   544   blockIndex = ((p->btSync.numProcessedBlocks - 1) & kMtBtNumBlocksMask);

   545   p->btBufPosLimit = p->btBufPos = blockIndex * kMtBtBlockSize;

   546   p->btBufPosLimit += p->btBuf[p->btBufPos++];

   547   p->btNumAvailBytes = p->btBuf[p->btBufPos++];

   548   if (p->lzPos >= kMtMaxValForNormalize - kMtBtBlockSize) 

   549     MatchFinderMt_Normalize(p);

   550 }

   551 

   552 const Byte * MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt *p)

   553 {

   554   return p->pointerToCurPos;

   555 }

   556 

   557 #define GET_NEXT_BLOCK_IF_REQUIRED if (p->btBufPos == p->btBufPosLimit) MatchFinderMt_GetNextBlock_Bt(p);

   558 

   559 UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p)

   560 { 

   561   GET_NEXT_BLOCK_IF_REQUIRED;

   562   return p->btNumAvailBytes;

   563 }

   564 

   565 Byte MatchFinderMt_GetIndexByte(CMatchFinderMt *p, Int32 index)

   566 { 

   567   return p->pointerToCurPos[index]; 

   568 }

   569 

   570 UInt32 * MixMatches2(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)

   571 {

   572   UInt32 hash2Value, curMatch2;

   573   UInt32 *hash = p->hash;

   574   const Byte *cur = p->pointerToCurPos;

   575   UInt32 lzPos = p->lzPos; 

   576   MT_HASH2_CALC

   577       

   578   curMatch2 = hash[hash2Value];

   579   hash[hash2Value] = lzPos;

   580 

   581   if (curMatch2 >= matchMinPos) 

   582     if (cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])

   583     {

   584       *distances++ = 2; 

   585       *distances++ = lzPos - curMatch2 - 1;

   586     }

   587   return distances;

   588 }

   589 

   590 UInt32 * MixMatches3(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)

   591 {

   592   UInt32 hash2Value, hash3Value, curMatch2, curMatch3;

   593   UInt32 *hash = p->hash;

   594   const Byte *cur = p->pointerToCurPos;

   595   UInt32 lzPos = p->lzPos; 

   596   MT_HASH3_CALC

   597 

   598   curMatch2 = hash[                hash2Value];

   599   curMatch3 = hash[kFix3HashSize + hash3Value];

   600   

   601   hash[                hash2Value] = 

   602   hash[kFix3HashSize + hash3Value] = 

   603     lzPos;

   604 

   605   if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])

   606   { 

   607     distances[1] = lzPos - curMatch2 - 1;

   608     if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])

   609     {

   610       distances[0] = 3;

   611       return distances + 2;

   612     }

   613     distances[0] = 2; 

   614     distances += 2;

   615   }

   616   if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])

   617   { 

   618     *distances++ = 3; 

   619     *distances++ = lzPos - curMatch3 - 1; 

   620   }

   621   return distances;

   622 }

   623 

   624 /*

   625 UInt32 *MixMatches4(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)

   626 {

   627   UInt32 hash2Value, hash3Value, hash4Value, curMatch2, curMatch3, curMatch4;

   628   UInt32 *hash = p->hash;

   629   const Byte *cur = p->pointerToCurPos;

   630   UInt32 lzPos = p->lzPos; 

   631   MT_HASH4_CALC

   632       

   633   curMatch2 = hash[                hash2Value];

   634   curMatch3 = hash[kFix3HashSize + hash3Value];

   635   curMatch4 = hash[kFix4HashSize + hash4Value];

   636   

   637   hash[                hash2Value] = 

   638   hash[kFix3HashSize + hash3Value] = 

   639   hash[kFix4HashSize + hash4Value] = 

   640     lzPos;

   641 

   642   if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])

   643   {

   644     distances[1] = lzPos - curMatch2 - 1;

   645     if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])

   646     {

   647       distances[0] =  (cur[(ptrdiff_t)curMatch2 - lzPos + 3] == cur[3]) ? 4 : 3;

   648       return distances + 2;

   649     }

   650     distances[0] = 2;

   651     distances += 2;

   652   }

   653   if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])

   654   {

   655     distances[1] = lzPos - curMatch3 - 1;

   656     if (cur[(ptrdiff_t)curMatch3 - lzPos + 3] == cur[3])

   657     {

   658       distances[0] = 4;

   659       return distances + 2;

   660     }

   661     distances[0] = 3;

   662     distances += 2;

   663   }

   664 

   665   if (curMatch4 >= matchMinPos)

   666     if (

   667       cur[(ptrdiff_t)curMatch4 - lzPos] == cur[0] &&

   668       cur[(ptrdiff_t)curMatch4 - lzPos + 3] == cur[3]

   669       )

   670     {

   671       *distances++ = 4;

   672       *distances++ = lzPos - curMatch4 - 1;

   673     }

   674   return distances;

   675 }

   676 */

   677 

   678 #define INCREASE_LZ_POS p->lzPos++; p->pointerToCurPos++;

   679 

   680 UInt32 MatchFinderMt2_GetMatches(CMatchFinderMt *p, UInt32 *distances)

   681 { 

   682   const UInt32 *btBuf = p->btBuf + p->btBufPos;

   683   UInt32 len = *btBuf++;

   684   p->btBufPos += 1 + len;

   685   p->btNumAvailBytes--;

   686   {

   687     UInt32 i;

   688     for (i = 0; i < len; i += 2)

   689     {

   690       *distances++ = *btBuf++;

   691       *distances++ = *btBuf++;

   692     }

   693   }

   694   INCREASE_LZ_POS

   695   return len;

   696 }

   697 

   698 UInt32 MatchFinderMt_GetMatches(CMatchFinderMt *p, UInt32 *distances)

   699 { 

   700   const UInt32 *btBuf = p->btBuf + p->btBufPos;

   701   UInt32 len = *btBuf++;

   702   p->btBufPos += 1 + len;

   703 

   704   if (len == 0)

   705   {

   706     if (p->btNumAvailBytes-- >= 4) 

   707       len = (UInt32)(p->MixMatchesFunc(p, p->lzPos - p->historySize, distances) - (distances));

   708   }

   709   else

   710   {

   711     /* Condition: there are matches in btBuf with length < p->numHashBytes */

   712     UInt32 *distances2;

   713     p->btNumAvailBytes--;

   714     distances2 = p->MixMatchesFunc(p, p->lzPos - btBuf[1], distances);

   715     do 

   716     {

   717       *distances2++ = *btBuf++;

   718       *distances2++ = *btBuf++;

   719     }

   720     while ((len -= 2) != 0);

   721     len  = (UInt32)(distances2 - (distances));

   722   }

   723   INCREASE_LZ_POS

   724   return len;

   725 }

   726 

   727 #define SKIP_HEADER2  do { GET_NEXT_BLOCK_IF_REQUIRED

   728 #define SKIP_HEADER(n) SKIP_HEADER2 if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash;

   729 #define SKIP_FOOTER } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while(--num != 0);

   730 

   731 void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num)

   732 { 

   733   SKIP_HEADER2 { p->btNumAvailBytes--;

   734   SKIP_FOOTER

   735 }

   736 

   737 void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num)

   738 { 

   739   SKIP_HEADER(2)

   740       UInt32 hash2Value;

   741       MT_HASH2_CALC

   742       hash[hash2Value] = p->lzPos;

   743   SKIP_FOOTER

   744 }

   745 

   746 void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num)

   747 { 

   748   SKIP_HEADER(3)

   749       UInt32 hash2Value, hash3Value;

   750       MT_HASH3_CALC

   751       hash[kFix3HashSize + hash3Value] = 

   752       hash[                hash2Value] = 

   753         p->lzPos;

   754   SKIP_FOOTER

   755 }

   756 

   757 /*

   758 void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num)

   759 { 

   760   SKIP_HEADER(4)

   761       UInt32 hash2Value, hash3Value, hash4Value;

   762       MT_HASH4_CALC

   763       hash[kFix4HashSize + hash4Value] = 

   764       hash[kFix3HashSize + hash3Value] = 

   765       hash[                hash2Value] = 

   766         p->lzPos;

   767   SKIP_FOOTER

   768 }

   769 */

   770 

   771 void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable)

   772 {

   773   vTable->Init = (Mf_Init_Func)MatchFinderMt_Init;

   774   vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinderMt_GetIndexByte;

   775   vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinderMt_GetNumAvailableBytes;

   776   vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinderMt_GetPointerToCurrentPos;

   777   vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt_GetMatches;

   778   switch(p->MatchFinder->numHashBytes)

   779   {

   780     case 2:

   781       p->GetHeadsFunc = GetHeads2;

   782       p->MixMatchesFunc = (Mf_Mix_Matches)0;

   783       vTable->Skip = (Mf_Skip_Func)MatchFinderMt0_Skip;

   784       vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt2_GetMatches;

   785       break;

   786     case 3:

   787       p->GetHeadsFunc = GetHeads3;

   788       p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches2;

   789       vTable->Skip = (Mf_Skip_Func)MatchFinderMt2_Skip;

   790       break;

   791     default:

   792     /* case 4: */

   793       p->GetHeadsFunc = p->MatchFinder->bigHash ? GetHeads4b : GetHeads4;

   794       /* p->GetHeadsFunc = GetHeads4; */

   795       p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches3;

   796       vTable->Skip = (Mf_Skip_Func)MatchFinderMt3_Skip;

   797       break;

   798     /*

   799     default:

   800       p->GetHeadsFunc = GetHeads5;

   801       p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches4;

   802       vTable->Skip = (Mf_Skip_Func)MatchFinderMt4_Skip;

   803       break;

   804     */

   805   }

   806 }