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

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