[mirror_edk2.git] / BaseTools / Source / C / LzmaCompress / Sdk / C / LzFindMt.c

/* LzFindMt.c -- multithreaded Match finder for LZ algorithms\r
2017-06-10 : Igor Pavlov : Public domain */\r
\r
#include "Precomp.h"\r
\r
#include "LzHash.h"\r
\r
#include "LzFindMt.h"\r
\r
static void MtSync_Construct(CMtSync *p)\r
{\r
  p->wasCreated = False;\r
  p->csWasInitialized = False;\r
  p->csWasEntered = False;\r
  Thread_Construct(&p->thread);\r
  Event_Construct(&p->canStart);\r
  Event_Construct(&p->wasStarted);\r
  Event_Construct(&p->wasStopped);\r
  Semaphore_Construct(&p->freeSemaphore);\r
  Semaphore_Construct(&p->filledSemaphore);\r
}\r
\r
static void MtSync_GetNextBlock(CMtSync *p)\r
{\r
  if (p->needStart)\r
  {\r
    p->numProcessedBlocks = 1;\r
    p->needStart = False;\r
    p->stopWriting = False;\r
    p->exit = False;\r
    Event_Reset(&p->wasStarted);\r
    Event_Reset(&p->wasStopped);\r
\r
    Event_Set(&p->canStart);\r
    Event_Wait(&p->wasStarted);\r
\r
    // if (mt) MatchFinder_Init_LowHash(mt->MatchFinder);\r
  }\r
  else\r
  {\r
    CriticalSection_Leave(&p->cs);\r
    p->csWasEntered = False;\r
    p->numProcessedBlocks++;\r
    Semaphore_Release1(&p->freeSemaphore);\r
  }\r
  Semaphore_Wait(&p->filledSemaphore);\r
  CriticalSection_Enter(&p->cs);\r
  p->csWasEntered = True;\r
}\r
\r
/* MtSync_StopWriting must be called if Writing was started */\r
\r
static void MtSync_StopWriting(CMtSync *p)\r
{\r
  UInt32 myNumBlocks = p->numProcessedBlocks;\r
  if (!Thread_WasCreated(&p->thread) || p->needStart)\r
    return;\r
  p->stopWriting = True;\r
  if (p->csWasEntered)\r
  {\r
    CriticalSection_Leave(&p->cs);\r
    p->csWasEntered = False;\r
  }\r
  Semaphore_Release1(&p->freeSemaphore);\r
 \r
  Event_Wait(&p->wasStopped);\r
\r
  while (myNumBlocks++ != p->numProcessedBlocks)\r
  {\r
    Semaphore_Wait(&p->filledSemaphore);\r
    Semaphore_Release1(&p->freeSemaphore);\r
  }\r
  p->needStart = True;\r
}\r
\r
static void MtSync_Destruct(CMtSync *p)\r
{\r
  if (Thread_WasCreated(&p->thread))\r
  {\r
    MtSync_StopWriting(p);\r
    p->exit = True;\r
    if (p->needStart)\r
      Event_Set(&p->canStart);\r
    Thread_Wait(&p->thread);\r
    Thread_Close(&p->thread);\r
  }\r
  if (p->csWasInitialized)\r
  {\r
    CriticalSection_Delete(&p->cs);\r
    p->csWasInitialized = False;\r
  }\r
\r
  Event_Close(&p->canStart);\r
  Event_Close(&p->wasStarted);\r
  Event_Close(&p->wasStopped);\r
  Semaphore_Close(&p->freeSemaphore);\r
  Semaphore_Close(&p->filledSemaphore);\r
\r
  p->wasCreated = False;\r
}\r
\r
#define RINOK_THREAD(x) { if ((x) != 0) return SZ_ERROR_THREAD; }\r
\r
static SRes MtSync_Create2(CMtSync *p, THREAD_FUNC_TYPE startAddress, void *obj, UInt32 numBlocks)\r
{\r
  if (p->wasCreated)\r
    return SZ_OK;\r
\r
  RINOK_THREAD(CriticalSection_Init(&p->cs));\r
  p->csWasInitialized = True;\r
\r
  RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->canStart));\r
  RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStarted));\r
  RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStopped));\r
  \r
  RINOK_THREAD(Semaphore_Create(&p->freeSemaphore, numBlocks, numBlocks));\r
  RINOK_THREAD(Semaphore_Create(&p->filledSemaphore, 0, numBlocks));\r
\r
  p->needStart = True;\r
  \r
  RINOK_THREAD(Thread_Create(&p->thread, startAddress, obj));\r
  p->wasCreated = True;\r
  return SZ_OK;\r
}\r
\r
static SRes MtSync_Create(CMtSync *p, THREAD_FUNC_TYPE startAddress, void *obj, UInt32 numBlocks)\r
{\r
  SRes res = MtSync_Create2(p, startAddress, obj, numBlocks);\r
  if (res != SZ_OK)\r
    MtSync_Destruct(p);\r
  return res;\r
}\r
\r
void MtSync_Init(CMtSync *p) { p->needStart = True; }\r
\r
#define kMtMaxValForNormalize 0xFFFFFFFF\r
\r
#define DEF_GetHeads2(name, v, action) \\r
  static void GetHeads ## name(const Byte *p, UInt32 pos, \\r
      UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads, const UInt32 *crc) \\r
    { action; for (; numHeads != 0; numHeads--) { \\r
      const UInt32 value = (v); p++; *heads++ = pos - hash[value]; hash[value] = pos++;  } }\r
\r
#define DEF_GetHeads(name, v) DEF_GetHeads2(name, v, ;)\r
\r
DEF_GetHeads2(2,  (p[0] | ((UInt32)p[1] << 8)), UNUSED_VAR(hashMask); UNUSED_VAR(crc); )\r
DEF_GetHeads(3,  (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask)\r
DEF_GetHeads(4,  (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5)) & hashMask)\r
DEF_GetHeads(4b, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ ((UInt32)p[3] << 16)) & hashMask)\r
/* DEF_GetHeads(5,  (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5) ^ (crc[p[4]] << 3)) & hashMask) */\r
\r
static void HashThreadFunc(CMatchFinderMt *mt)\r
{\r
  CMtSync *p = &mt->hashSync;\r
  for (;;)\r
  {\r
    UInt32 numProcessedBlocks = 0;\r
    Event_Wait(&p->canStart);\r
    Event_Set(&p->wasStarted);\r
\r
    MatchFinder_Init_HighHash(mt->MatchFinder);\r
\r
    for (;;)\r
    {\r
      if (p->exit)\r
        return;\r
      if (p->stopWriting)\r
      {\r
        p->numProcessedBlocks = numProcessedBlocks;\r
        Event_Set(&p->wasStopped);\r
        break;\r
      }\r
\r
      {\r
        CMatchFinder *mf = mt->MatchFinder;\r
        if (MatchFinder_NeedMove(mf))\r
        {\r
          CriticalSection_Enter(&mt->btSync.cs);\r
          CriticalSection_Enter(&mt->hashSync.cs);\r
          {\r
            const Byte *beforePtr = Inline_MatchFinder_GetPointerToCurrentPos(mf);\r
            ptrdiff_t offset;\r
            MatchFinder_MoveBlock(mf);\r
            offset = beforePtr - Inline_MatchFinder_GetPointerToCurrentPos(mf);\r
            mt->pointerToCurPos -= offset;\r
            mt->buffer -= offset;\r
          }\r
          CriticalSection_Leave(&mt->btSync.cs);\r
          CriticalSection_Leave(&mt->hashSync.cs);\r
          continue;\r
        }\r
\r
        Semaphore_Wait(&p->freeSemaphore);\r
\r
        MatchFinder_ReadIfRequired(mf);\r
        if (mf->pos > (kMtMaxValForNormalize - kMtHashBlockSize))\r
        {\r
          UInt32 subValue = (mf->pos - mf->historySize - 1);\r
          MatchFinder_ReduceOffsets(mf, subValue);\r
          MatchFinder_Normalize3(subValue, mf->hash + mf->fixedHashSize, (size_t)mf->hashMask + 1);\r
        }\r
        {\r
          UInt32 *heads = mt->hashBuf + ((numProcessedBlocks++) & kMtHashNumBlocksMask) * kMtHashBlockSize;\r
          UInt32 num = mf->streamPos - mf->pos;\r
          heads[0] = 2;\r
          heads[1] = num;\r
          if (num >= mf->numHashBytes)\r
          {\r
            num = num - mf->numHashBytes + 1;\r
            if (num > kMtHashBlockSize - 2)\r
              num = kMtHashBlockSize - 2;\r
            mt->GetHeadsFunc(mf->buffer, mf->pos, mf->hash + mf->fixedHashSize, mf->hashMask, heads + 2, num, mf->crc);\r
            heads[0] = 2 + num;\r
          }\r
          mf->pos += num;\r
          mf->buffer += num;\r
        }\r
      }\r
\r
      Semaphore_Release1(&p->filledSemaphore);\r
    }\r
  }\r
}\r
\r
static void MatchFinderMt_GetNextBlock_Hash(CMatchFinderMt *p)\r
{\r
  MtSync_GetNextBlock(&p->hashSync);\r
  p->hashBufPosLimit = p->hashBufPos = ((p->hashSync.numProcessedBlocks - 1) & kMtHashNumBlocksMask) * kMtHashBlockSize;\r
  p->hashBufPosLimit += p->hashBuf[p->hashBufPos++];\r
  p->hashNumAvail = p->hashBuf[p->hashBufPos++];\r
}\r
\r
#define kEmptyHashValue 0\r
\r
/* #define MFMT_GM_INLINE */\r
\r
#ifdef MFMT_GM_INLINE\r
\r
#define NO_INLINE MY_FAST_CALL\r
\r
static Int32 NO_INLINE GetMatchesSpecN(UInt32 lenLimit, UInt32 pos, const Byte *cur, CLzRef *son,\r
    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue,\r
    UInt32 *_distances, UInt32 _maxLen, const UInt32 *hash, Int32 limit, UInt32 size, UInt32 *posRes)\r
{\r
  do\r
  {\r
  UInt32 *distances = _distances + 1;\r
  UInt32 curMatch = pos - *hash++;\r
\r
  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;\r
  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);\r
  UInt32 len0 = 0, len1 = 0;\r
  UInt32 cutValue = _cutValue;\r
  UInt32 maxLen = _maxLen;\r
  for (;;)\r
  {\r
    UInt32 delta = pos - curMatch;\r
    if (cutValue-- == 0 || delta >= _cyclicBufferSize)\r
    {\r
      *ptr0 = *ptr1 = kEmptyHashValue;\r
      break;\r
    }\r
    {\r
      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);\r
      const Byte *pb = cur - delta;\r
      UInt32 len = (len0 < len1 ? len0 : len1);\r
      if (pb[len] == cur[len])\r
      {\r
        if (++len != lenLimit && pb[len] == cur[len])\r
          while (++len != lenLimit)\r
            if (pb[len] != cur[len])\r
              break;\r
        if (maxLen < len)\r
        {\r
          *distances++ = maxLen = len;\r
          *distances++ = delta - 1;\r
          if (len == lenLimit)\r
          {\r
            *ptr1 = pair[0];\r
            *ptr0 = pair[1];\r
            break;\r
          }\r
        }\r
      }\r
      if (pb[len] < cur[len])\r
      {\r
        *ptr1 = curMatch;\r
        ptr1 = pair + 1;\r
        curMatch = *ptr1;\r
        len1 = len;\r
      }\r
      else\r
      {\r
        *ptr0 = curMatch;\r
        ptr0 = pair;\r
        curMatch = *ptr0;\r
        len0 = len;\r
      }\r
    }\r
  }\r
  pos++;\r
  _cyclicBufferPos++;\r
  cur++;\r
  {\r
    UInt32 num = (UInt32)(distances - _distances);\r
    *_distances = num - 1;\r
    _distances += num;\r
    limit -= num;\r
  }\r
  }\r
  while (limit > 0 && --size != 0);\r
  *posRes = pos;\r
  return limit;\r
}\r
\r
#endif\r
\r
static void BtGetMatches(CMatchFinderMt *p, UInt32 *distances)\r
{\r
  UInt32 numProcessed = 0;\r
  UInt32 curPos = 2;\r
  UInt32 limit = kMtBtBlockSize - (p->matchMaxLen * 2);\r
  \r
  distances[1] = p->hashNumAvail;\r
  \r
  while (curPos < limit)\r
  {\r
    if (p->hashBufPos == p->hashBufPosLimit)\r
    {\r
      MatchFinderMt_GetNextBlock_Hash(p);\r
      distances[1] = numProcessed + p->hashNumAvail;\r
      if (p->hashNumAvail >= p->numHashBytes)\r
        continue;\r
      distances[0] = curPos + p->hashNumAvail;\r
      distances += curPos;\r
      for (; p->hashNumAvail != 0; p->hashNumAvail--)\r
        *distances++ = 0;\r
      return;\r
    }\r
    {\r
      UInt32 size = p->hashBufPosLimit - p->hashBufPos;\r
      UInt32 lenLimit = p->matchMaxLen;\r
      UInt32 pos = p->pos;\r
      UInt32 cyclicBufferPos = p->cyclicBufferPos;\r
      if (lenLimit >= p->hashNumAvail)\r
        lenLimit = p->hashNumAvail;\r
      {\r
        UInt32 size2 = p->hashNumAvail - lenLimit + 1;\r
        if (size2 < size)\r
          size = size2;\r
        size2 = p->cyclicBufferSize - cyclicBufferPos;\r
        if (size2 < size)\r
          size = size2;\r
      }\r
      \r
      #ifndef MFMT_GM_INLINE\r
      while (curPos < limit && size-- != 0)\r
      {\r
        UInt32 *startDistances = distances + curPos;\r
        UInt32 num = (UInt32)(GetMatchesSpec1(lenLimit, pos - p->hashBuf[p->hashBufPos++],\r
            pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,\r
            startDistances + 1, p->numHashBytes - 1) - startDistances);\r
        *startDistances = num - 1;\r
        curPos += num;\r
        cyclicBufferPos++;\r
        pos++;\r
        p->buffer++;\r
      }\r
      #else\r
      {\r
        UInt32 posRes;\r
        curPos = limit - GetMatchesSpecN(lenLimit, pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,\r
            distances + curPos, p->numHashBytes - 1, p->hashBuf + p->hashBufPos, (Int32)(limit - curPos), size, &posRes);\r
        p->hashBufPos += posRes - pos;\r
        cyclicBufferPos += posRes - pos;\r
        p->buffer += posRes - pos;\r
        pos = posRes;\r
      }\r
      #endif\r
\r
      numProcessed += pos - p->pos;\r
      p->hashNumAvail -= pos - p->pos;\r
      p->pos = pos;\r
      if (cyclicBufferPos == p->cyclicBufferSize)\r
        cyclicBufferPos = 0;\r
      p->cyclicBufferPos = cyclicBufferPos;\r
    }\r
  }\r
  \r
  distances[0] = curPos;\r
}\r
\r
static void BtFillBlock(CMatchFinderMt *p, UInt32 globalBlockIndex)\r
{\r
  CMtSync *sync = &p->hashSync;\r
  if (!sync->needStart)\r
  {\r
    CriticalSection_Enter(&sync->cs);\r
    sync->csWasEntered = True;\r
  }\r
  \r
  BtGetMatches(p, p->btBuf + (globalBlockIndex & kMtBtNumBlocksMask) * kMtBtBlockSize);\r
\r
  if (p->pos > kMtMaxValForNormalize - kMtBtBlockSize)\r
  {\r
    UInt32 subValue = p->pos - p->cyclicBufferSize;\r
    MatchFinder_Normalize3(subValue, p->son, (size_t)p->cyclicBufferSize * 2);\r
    p->pos -= subValue;\r
  }\r
\r
  if (!sync->needStart)\r
  {\r
    CriticalSection_Leave(&sync->cs);\r
    sync->csWasEntered = False;\r
  }\r
}\r
\r
void BtThreadFunc(CMatchFinderMt *mt)\r
{\r
  CMtSync *p = &mt->btSync;\r
  for (;;)\r
  {\r
    UInt32 blockIndex = 0;\r
    Event_Wait(&p->canStart);\r
    Event_Set(&p->wasStarted);\r
    for (;;)\r
    {\r
      if (p->exit)\r
        return;\r
      if (p->stopWriting)\r
      {\r
        p->numProcessedBlocks = blockIndex;\r
        MtSync_StopWriting(&mt->hashSync);\r
        Event_Set(&p->wasStopped);\r
        break;\r
      }\r
      Semaphore_Wait(&p->freeSemaphore);\r
      BtFillBlock(mt, blockIndex++);\r
      Semaphore_Release1(&p->filledSemaphore);\r
    }\r
  }\r
}\r
\r
void MatchFinderMt_Construct(CMatchFinderMt *p)\r
{\r
  p->hashBuf = NULL;\r
  MtSync_Construct(&p->hashSync);\r
  MtSync_Construct(&p->btSync);\r
}\r
\r
static void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAllocPtr alloc)\r
{\r
  ISzAlloc_Free(alloc, p->hashBuf);\r
  p->hashBuf = NULL;\r
}\r
\r
void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAllocPtr alloc)\r
{\r
  MtSync_Destruct(&p->hashSync);\r
  MtSync_Destruct(&p->btSync);\r
  MatchFinderMt_FreeMem(p, alloc);\r
}\r
\r
#define kHashBufferSize (kMtHashBlockSize * kMtHashNumBlocks)\r
#define kBtBufferSize (kMtBtBlockSize * kMtBtNumBlocks)\r
\r
static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p);  return 0; }\r
static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE BtThreadFunc2(void *p)\r
{\r
  Byte allocaDummy[0x180];\r
  unsigned i = 0;\r
  for (i = 0; i < 16; i++)\r
    allocaDummy[i] = (Byte)0;\r
  if (allocaDummy[0] == 0)\r
    BtThreadFunc((CMatchFinderMt *)p);\r
  return 0;\r
}\r
\r
SRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore,\r
    UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAllocPtr alloc)\r
{\r
  CMatchFinder *mf = p->MatchFinder;\r
  p->historySize = historySize;\r
  if (kMtBtBlockSize <= matchMaxLen * 4)\r
    return SZ_ERROR_PARAM;\r
  if (!p->hashBuf)\r
  {\r
    p->hashBuf = (UInt32 *)ISzAlloc_Alloc(alloc, (kHashBufferSize + kBtBufferSize) * sizeof(UInt32));\r
    if (!p->hashBuf)\r
      return SZ_ERROR_MEM;\r
    p->btBuf = p->hashBuf + kHashBufferSize;\r
  }\r
  keepAddBufferBefore += (kHashBufferSize + kBtBufferSize);\r
  keepAddBufferAfter += kMtHashBlockSize;\r
  if (!MatchFinder_Create(mf, historySize, keepAddBufferBefore, matchMaxLen, keepAddBufferAfter, alloc))\r
    return SZ_ERROR_MEM;\r
\r
  RINOK(MtSync_Create(&p->hashSync, HashThreadFunc2, p, kMtHashNumBlocks));\r
  RINOK(MtSync_Create(&p->btSync, BtThreadFunc2, p, kMtBtNumBlocks));\r
  return SZ_OK;\r
}\r
\r
/* Call it after ReleaseStream / SetStream */\r
static void MatchFinderMt_Init(CMatchFinderMt *p)\r
{\r
  CMatchFinder *mf = p->MatchFinder;\r
  \r
  p->btBufPos =\r
  p->btBufPosLimit = 0;\r
  p->hashBufPos =\r
  p->hashBufPosLimit = 0;\r
\r
  /* Init without data reading. We don't want to read data in this thread */\r
  MatchFinder_Init_3(mf, False);\r
  MatchFinder_Init_LowHash(mf);\r
  \r
  p->pointerToCurPos = Inline_MatchFinder_GetPointerToCurrentPos(mf);\r
  p->btNumAvailBytes = 0;\r
  p->lzPos = p->historySize + 1;\r
\r
  p->hash = mf->hash;\r
  p->fixedHashSize = mf->fixedHashSize;\r
  p->crc = mf->crc;\r
\r
  p->son = mf->son;\r
  p->matchMaxLen = mf->matchMaxLen;\r
  p->numHashBytes = mf->numHashBytes;\r
  p->pos = mf->pos;\r
  p->buffer = mf->buffer;\r
  p->cyclicBufferPos = mf->cyclicBufferPos;\r
  p->cyclicBufferSize = mf->cyclicBufferSize;\r
  p->cutValue = mf->cutValue;\r
}\r
\r
/* ReleaseStream is required to finish multithreading */\r
void MatchFinderMt_ReleaseStream(CMatchFinderMt *p)\r
{\r
  MtSync_StopWriting(&p->btSync);\r
  /* p->MatchFinder->ReleaseStream(); */\r
}\r
\r
static void MatchFinderMt_Normalize(CMatchFinderMt *p)\r
{\r
  MatchFinder_Normalize3(p->lzPos - p->historySize - 1, p->hash, p->fixedHashSize);\r
  p->lzPos = p->historySize + 1;\r
}\r
\r
static void MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt *p)\r
{\r
  UInt32 blockIndex;\r
  MtSync_GetNextBlock(&p->btSync);\r
  blockIndex = ((p->btSync.numProcessedBlocks - 1) & kMtBtNumBlocksMask);\r
  p->btBufPosLimit = p->btBufPos = blockIndex * kMtBtBlockSize;\r
  p->btBufPosLimit += p->btBuf[p->btBufPos++];\r
  p->btNumAvailBytes = p->btBuf[p->btBufPos++];\r
  if (p->lzPos >= kMtMaxValForNormalize - kMtBtBlockSize)\r
    MatchFinderMt_Normalize(p);\r
}\r
\r
static const Byte * MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt *p)\r
{\r
  return p->pointerToCurPos;\r
}\r
\r
#define GET_NEXT_BLOCK_IF_REQUIRED if (p->btBufPos == p->btBufPosLimit) MatchFinderMt_GetNextBlock_Bt(p);\r
\r
static UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p)\r
{\r
  GET_NEXT_BLOCK_IF_REQUIRED;\r
  return p->btNumAvailBytes;\r
}\r
\r
static UInt32 * MixMatches2(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)\r
{\r
  UInt32 h2, curMatch2;\r
  UInt32 *hash = p->hash;\r
  const Byte *cur = p->pointerToCurPos;\r
  UInt32 lzPos = p->lzPos;\r
  MT_HASH2_CALC\r
      \r
  curMatch2 = hash[h2];\r
  hash[h2] = lzPos;\r
\r
  if (curMatch2 >= matchMinPos)\r
    if (cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])\r
    {\r
      *distances++ = 2;\r
      *distances++ = lzPos - curMatch2 - 1;\r
    }\r
  \r
  return distances;\r
}\r
\r
static UInt32 * MixMatches3(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)\r
{\r
  UInt32 h2, h3, curMatch2, curMatch3;\r
  UInt32 *hash = p->hash;\r
  const Byte *cur = p->pointerToCurPos;\r
  UInt32 lzPos = p->lzPos;\r
  MT_HASH3_CALC\r
\r
  curMatch2 = hash[                h2];\r
  curMatch3 = (hash + kFix3HashSize)[h3];\r
  \r
  hash[                h2] = lzPos;\r
  (hash + kFix3HashSize)[h3] = lzPos;\r
\r
  if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])\r
  {\r
    distances[1] = lzPos - curMatch2 - 1;\r
    if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])\r
    {\r
      distances[0] = 3;\r
      return distances + 2;\r
    }\r
    distances[0] = 2;\r
    distances += 2;\r
  }\r
  \r
  if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])\r
  {\r
    *distances++ = 3;\r
    *distances++ = lzPos - curMatch3 - 1;\r
  }\r
  \r
  return distances;\r
}\r
\r
/*\r
static UInt32 *MixMatches4(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)\r
{\r
  UInt32 h2, h3, h4, curMatch2, curMatch3, curMatch4;\r
  UInt32 *hash = p->hash;\r
  const Byte *cur = p->pointerToCurPos;\r
  UInt32 lzPos = p->lzPos;\r
  MT_HASH4_CALC\r
      \r
  curMatch2 = hash[                h2];\r
  curMatch3 = (hash + kFix3HashSize)[h3];\r
  curMatch4 = (hash + kFix4HashSize)[h4];\r
  \r
  hash[                h2] = lzPos;\r
  (hash + kFix3HashSize)[h3] = lzPos;\r
  (hash + kFix4HashSize)[h4] = lzPos;\r
\r
  if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])\r
  {\r
    distances[1] = lzPos - curMatch2 - 1;\r
    if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])\r
    {\r
      distances[0] = (cur[(ptrdiff_t)curMatch2 - lzPos + 3] == cur[3]) ? 4 : 3;\r
      return distances + 2;\r
    }\r
    distances[0] = 2;\r
    distances += 2;\r
  }\r
  \r
  if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])\r
  {\r
    distances[1] = lzPos - curMatch3 - 1;\r
    if (cur[(ptrdiff_t)curMatch3 - lzPos + 3] == cur[3])\r
    {\r
      distances[0] = 4;\r
      return distances + 2;\r
    }\r
    distances[0] = 3;\r
    distances += 2;\r
  }\r
\r
  if (curMatch4 >= matchMinPos)\r
    if (\r
      cur[(ptrdiff_t)curMatch4 - lzPos] == cur[0] &&\r
      cur[(ptrdiff_t)curMatch4 - lzPos + 3] == cur[3]\r
      )\r
    {\r
      *distances++ = 4;\r
      *distances++ = lzPos - curMatch4 - 1;\r
    }\r
  \r
  return distances;\r
}\r
*/\r
\r
#define INCREASE_LZ_POS p->lzPos++; p->pointerToCurPos++;\r
\r
static UInt32 MatchFinderMt2_GetMatches(CMatchFinderMt *p, UInt32 *distances)\r
{\r
  const UInt32 *btBuf = p->btBuf + p->btBufPos;\r
  UInt32 len = *btBuf++;\r
  p->btBufPos += 1 + len;\r
  p->btNumAvailBytes--;\r
  {\r
    UInt32 i;\r
    for (i = 0; i < len; i += 2)\r
    {\r
      UInt32 v0 = btBuf[0];\r
      UInt32 v1 = btBuf[1];\r
      btBuf += 2;\r
      distances[0] = v0;\r
      distances[1] = v1;\r
      distances += 2;\r
    }\r
  }\r
  INCREASE_LZ_POS\r
  return len;\r
}\r
\r
static UInt32 MatchFinderMt_GetMatches(CMatchFinderMt *p, UInt32 *distances)\r
{\r
  const UInt32 *btBuf = p->btBuf + p->btBufPos;\r
  UInt32 len = *btBuf++;\r
  p->btBufPos += 1 + len;\r
\r
  if (len == 0)\r
  {\r
    /* change for bt5 ! */\r
    if (p->btNumAvailBytes-- >= 4)\r
      len = (UInt32)(p->MixMatchesFunc(p, p->lzPos - p->historySize, distances) - (distances));\r
  }\r
  else\r
  {\r
    /* Condition: there are matches in btBuf with length < p->numHashBytes */\r
    UInt32 *distances2;\r
    p->btNumAvailBytes--;\r
    distances2 = p->MixMatchesFunc(p, p->lzPos - btBuf[1], distances);\r
    do\r
    {\r
      UInt32 v0 = btBuf[0];\r
      UInt32 v1 = btBuf[1];\r
      btBuf += 2;\r
      distances2[0] = v0;\r
      distances2[1] = v1;\r
      distances2 += 2;\r
    }\r
    while ((len -= 2) != 0);\r
    len = (UInt32)(distances2 - (distances));\r
  }\r
  INCREASE_LZ_POS\r
  return len;\r
}\r
\r
#define SKIP_HEADER2_MT  do { GET_NEXT_BLOCK_IF_REQUIRED\r
#define SKIP_HEADER_MT(n) SKIP_HEADER2_MT if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash;\r
#define SKIP_FOOTER_MT } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while (--num != 0);\r
\r
static void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num)\r
{\r
  SKIP_HEADER2_MT { p->btNumAvailBytes--;\r
  SKIP_FOOTER_MT\r
}\r
\r
static void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num)\r
{\r
  SKIP_HEADER_MT(2)\r
      UInt32 h2;\r
      MT_HASH2_CALC\r
      hash[h2] = p->lzPos;\r
  SKIP_FOOTER_MT\r
}\r
\r
static void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num)\r
{\r
  SKIP_HEADER_MT(3)\r
      UInt32 h2, h3;\r
      MT_HASH3_CALC\r
      (hash + kFix3HashSize)[h3] =\r
      hash[                h2] =\r
        p->lzPos;\r
  SKIP_FOOTER_MT\r
}\r
\r
/*\r
static void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num)\r
{\r
  SKIP_HEADER_MT(4)\r
      UInt32 h2, h3, h4;\r
      MT_HASH4_CALC\r
      (hash + kFix4HashSize)[h4] =\r
      (hash + kFix3HashSize)[h3] =\r
      hash[                h2] =\r
        p->lzPos;\r
  SKIP_FOOTER_MT\r
}\r
*/\r
\r
void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable)\r
{\r
  vTable->Init = (Mf_Init_Func)MatchFinderMt_Init;\r
  vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinderMt_GetNumAvailableBytes;\r
  vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinderMt_GetPointerToCurrentPos;\r
  vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt_GetMatches;\r
  \r
  switch (p->MatchFinder->numHashBytes)\r
  {\r
    case 2:\r
      p->GetHeadsFunc = GetHeads2;\r
      p->MixMatchesFunc = (Mf_Mix_Matches)NULL;\r
      vTable->Skip = (Mf_Skip_Func)MatchFinderMt0_Skip;\r
      vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt2_GetMatches;\r
      break;\r
    case 3:\r
      p->GetHeadsFunc = GetHeads3;\r
      p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches2;\r
      vTable->Skip = (Mf_Skip_Func)MatchFinderMt2_Skip;\r
      break;\r
    default:\r
    /* case 4: */\r
      p->GetHeadsFunc = p->MatchFinder->bigHash ? GetHeads4b : GetHeads4;\r
      p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches3;\r
      vTable->Skip = (Mf_Skip_Func)MatchFinderMt3_Skip;\r
      break;\r
    /*\r
    default:\r
      p->GetHeadsFunc = GetHeads5;\r
      p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches4;\r
      vTable->Skip = (Mf_Skip_Func)MatchFinderMt4_Skip;\r
      break;\r
    */\r
  }\r
}\r