git.cworth.org Git - vogl/blob - src/voglcore/lzma_LzFindMt.cpp

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