BaseTools/Source/C/LzmaCompress/Sdk/C/LzFindMt.c

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