vcs.maemo.org Git - physicsfs/blob - lzma/C/Compress/Lz/MatchFinderMt.c

   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 }