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

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