Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 820 insertions, 0 deletions

diff --git a/other-licenses/7zstub/src/C/LzFindMt.c b/other-licenses/7zstub/src/C/LzFindMt.c
new file mode 100644
index 0000000000..2563824fcd
--- /dev/null
+++ b/other-licenses/7zstub/src/C/LzFindMt.c
@@ -0,0 +1,820 @@
+/* LzFindMt.c -- multithreaded Match finder for LZ algorithms

+2017-06-10 : Igor Pavlov : Public domain */

+

+#include "Precomp.h"

+

+#include "LzHash.h"

+

+#include "LzFindMt.h"

+

+static void MtSync_Construct(CMtSync *p)

+{

+  p->wasCreated = False;

+  p->csWasInitialized = False;

+  p->csWasEntered = False;

+  Thread_Construct(&p->thread);

+  Event_Construct(&p->canStart);

+  Event_Construct(&p->wasStarted);

+  Event_Construct(&p->wasStopped);

+  Semaphore_Construct(&p->freeSemaphore);

+  Semaphore_Construct(&p->filledSemaphore);

+}

+

+static void MtSync_GetNextBlock(CMtSync *p)

+{

+  if (p->needStart)

+  {

+    p->numProcessedBlocks = 1;

+    p->needStart = False;

+    p->stopWriting = False;

+    p->exit = False;

+    Event_Reset(&p->wasStarted);

+    Event_Reset(&p->wasStopped);

+

+    Event_Set(&p->canStart);

+    Event_Wait(&p->wasStarted);

+

+    // if (mt) MatchFinder_Init_LowHash(mt->MatchFinder);

+  }

+  else

+  {

+    CriticalSection_Leave(&p->cs);

+    p->csWasEntered = False;

+    p->numProcessedBlocks++;

+    Semaphore_Release1(&p->freeSemaphore);

+  }

+  Semaphore_Wait(&p->filledSemaphore);

+  CriticalSection_Enter(&p->cs);

+  p->csWasEntered = True;

+}

+

+/* MtSync_StopWriting must be called if Writing was started */

+

+static void MtSync_StopWriting(CMtSync *p)

+{

+  UInt32 myNumBlocks = p->numProcessedBlocks;

+  if (!Thread_WasCreated(&p->thread) || p->needStart)

+    return;

+  p->stopWriting = True;

+  if (p->csWasEntered)

+  {

+    CriticalSection_Leave(&p->cs);

+    p->csWasEntered = False;

+  }

+  Semaphore_Release1(&p->freeSemaphore);

+ 

+  Event_Wait(&p->wasStopped);

+

+  while (myNumBlocks++ != p->numProcessedBlocks)

+  {

+    Semaphore_Wait(&p->filledSemaphore);

+    Semaphore_Release1(&p->freeSemaphore);

+  }

+  p->needStart = True;

+}

+

+static void MtSync_Destruct(CMtSync *p)

+{

+  if (Thread_WasCreated(&p->thread))

+  {

+    MtSync_StopWriting(p);

+    p->exit = True;

+    if (p->needStart)

+      Event_Set(&p->canStart);

+    Thread_Wait(&p->thread);

+    Thread_Close(&p->thread);

+  }

+  if (p->csWasInitialized)

+  {

+    CriticalSection_Delete(&p->cs);

+    p->csWasInitialized = False;

+  }

+

+  Event_Close(&p->canStart);

+  Event_Close(&p->wasStarted);

+  Event_Close(&p->wasStopped);

+  Semaphore_Close(&p->freeSemaphore);

+  Semaphore_Close(&p->filledSemaphore);

+

+  p->wasCreated = False;

+}

+

+#define RINOK_THREAD(x) { if ((x) != 0) return SZ_ERROR_THREAD; }

+

+static SRes MtSync_Create2(CMtSync *p, THREAD_FUNC_TYPE startAddress, void *obj, UInt32 numBlocks)

+{

+  if (p->wasCreated)

+    return SZ_OK;

+

+  RINOK_THREAD(CriticalSection_Init(&p->cs));

+  p->csWasInitialized = True;

+

+  RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->canStart));

+  RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStarted));

+  RINOK_THREAD(AutoResetEvent_CreateNotSignaled(&p->wasStopped));

+  

+  RINOK_THREAD(Semaphore_Create(&p->freeSemaphore, numBlocks, numBlocks));

+  RINOK_THREAD(Semaphore_Create(&p->filledSemaphore, 0, numBlocks));

+

+  p->needStart = True;

+  

+  RINOK_THREAD(Thread_Create(&p->thread, startAddress, obj));

+  p->wasCreated = True;

+  return SZ_OK;

+}

+

+static SRes MtSync_Create(CMtSync *p, THREAD_FUNC_TYPE startAddress, void *obj, UInt32 numBlocks)

+{

+  SRes res = MtSync_Create2(p, startAddress, obj, numBlocks);

+  if (res != SZ_OK)

+    MtSync_Destruct(p);

+  return res;

+}

+

+void MtSync_Init(CMtSync *p) { p->needStart = True; }

+

+#define kMtMaxValForNormalize 0xFFFFFFFF

+

+#define DEF_GetHeads2(name, v, action) \

+  static void GetHeads ## name(const Byte *p, UInt32 pos, \

+      UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads, const UInt32 *crc) \

+    { action; for (; numHeads != 0; numHeads--) { \

+      const UInt32 value = (v); p++; *heads++ = pos - hash[value]; hash[value] = pos++;  } }

+

+#define DEF_GetHeads(name, v) DEF_GetHeads2(name, v, ;)

+

+DEF_GetHeads2(2,  (p[0] | ((UInt32)p[1] << 8)), UNUSED_VAR(hashMask); UNUSED_VAR(crc); )

+DEF_GetHeads(3,  (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8)) & hashMask)

+DEF_GetHeads(4,  (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5)) & hashMask)

+DEF_GetHeads(4b, (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ ((UInt32)p[3] << 16)) & hashMask)

+/* DEF_GetHeads(5,  (crc[p[0]] ^ p[1] ^ ((UInt32)p[2] << 8) ^ (crc[p[3]] << 5) ^ (crc[p[4]] << 3)) & hashMask) */

+

+static void HashThreadFunc(CMatchFinderMt *mt)

+{

+  CMtSync *p = &mt->hashSync;

+  for (;;)

+  {

+    UInt32 numProcessedBlocks = 0;

+    Event_Wait(&p->canStart);

+    Event_Set(&p->wasStarted);

+

+    MatchFinder_Init_HighHash(mt->MatchFinder);

+

+    for (;;)

+    {

+      if (p->exit)

+        return;

+      if (p->stopWriting)

+      {

+        p->numProcessedBlocks = numProcessedBlocks;

+        Event_Set(&p->wasStopped);

+        break;

+      }

+

+      {

+        CMatchFinder *mf = mt->MatchFinder;

+        if (MatchFinder_NeedMove(mf))

+        {

+          CriticalSection_Enter(&mt->btSync.cs);

+          CriticalSection_Enter(&mt->hashSync.cs);

+          {

+            const Byte *beforePtr = Inline_MatchFinder_GetPointerToCurrentPos(mf);

+            ptrdiff_t offset;

+            MatchFinder_MoveBlock(mf);

+            offset = beforePtr - Inline_MatchFinder_GetPointerToCurrentPos(mf);

+            mt->pointerToCurPos -= offset;

+            mt->buffer -= offset;

+          }

+          CriticalSection_Leave(&mt->btSync.cs);

+          CriticalSection_Leave(&mt->hashSync.cs);

+          continue;

+        }

+

+        Semaphore_Wait(&p->freeSemaphore);

+

+        MatchFinder_ReadIfRequired(mf);

+        if (mf->pos > (kMtMaxValForNormalize - kMtHashBlockSize))

+        {

+          UInt32 subValue = (mf->pos - mf->historySize - 1);

+          MatchFinder_ReduceOffsets(mf, subValue);

+          MatchFinder_Normalize3(subValue, mf->hash + mf->fixedHashSize, (size_t)mf->hashMask + 1);

+        }

+        {

+          UInt32 *heads = mt->hashBuf + ((numProcessedBlocks++) & kMtHashNumBlocksMask) * kMtHashBlockSize;

+          UInt32 num = mf->streamPos - mf->pos;

+          heads[0] = 2;

+          heads[1] = num;

+          if (num >= mf->numHashBytes)

+          {

+            num = num - mf->numHashBytes + 1;

+            if (num > kMtHashBlockSize - 2)

+              num = kMtHashBlockSize - 2;

+            mt->GetHeadsFunc(mf->buffer, mf->pos, mf->hash + mf->fixedHashSize, mf->hashMask, heads + 2, num, mf->crc);

+            heads[0] = 2 + num;

+          }

+          mf->pos += num;

+          mf->buffer += num;

+        }

+      }

+

+      Semaphore_Release1(&p->filledSemaphore);

+    }

+  }

+}

+

+static void MatchFinderMt_GetNextBlock_Hash(CMatchFinderMt *p)

+{

+  MtSync_GetNextBlock(&p->hashSync);

+  p->hashBufPosLimit = p->hashBufPos = ((p->hashSync.numProcessedBlocks - 1) & kMtHashNumBlocksMask) * kMtHashBlockSize;

+  p->hashBufPosLimit += p->hashBuf[p->hashBufPos++];

+  p->hashNumAvail = p->hashBuf[p->hashBufPos++];

+}

+

+#define kEmptyHashValue 0

+

+/* #define MFMT_GM_INLINE */

+

+#ifdef MFMT_GM_INLINE

+

+#define NO_INLINE MY_FAST_CALL

+

+static Int32 NO_INLINE GetMatchesSpecN(UInt32 lenLimit, UInt32 pos, const Byte *cur, CLzRef *son,

+    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue,

+    UInt32 *_distances, UInt32 _maxLen, const UInt32 *hash, Int32 limit, UInt32 size, UInt32 *posRes)

+{

+  do

+  {

+  UInt32 *distances = _distances + 1;

+  UInt32 curMatch = pos - *hash++;

+

+  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;

+  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);

+  UInt32 len0 = 0, len1 = 0;

+  UInt32 cutValue = _cutValue;

+  UInt32 maxLen = _maxLen;

+  for (;;)

+  {

+    UInt32 delta = pos - curMatch;

+    if (cutValue-- == 0 || delta >= _cyclicBufferSize)

+    {

+      *ptr0 = *ptr1 = kEmptyHashValue;

+      break;

+    }

+    {

+      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);

+      const Byte *pb = cur - delta;

+      UInt32 len = (len0 < len1 ? len0 : len1);

+      if (pb[len] == cur[len])

+      {

+        if (++len != lenLimit && pb[len] == cur[len])

+          while (++len != lenLimit)

+            if (pb[len] != cur[len])

+              break;

+        if (maxLen < len)

+        {

+          *distances++ = maxLen = len;

+          *distances++ = delta - 1;

+          if (len == lenLimit)

+          {

+            *ptr1 = pair[0];

+            *ptr0 = pair[1];

+            break;

+          }

+        }

+      }

+      if (pb[len] < cur[len])

+      {

+        *ptr1 = curMatch;

+        ptr1 = pair + 1;

+        curMatch = *ptr1;

+        len1 = len;

+      }

+      else

+      {

+        *ptr0 = curMatch;

+        ptr0 = pair;

+        curMatch = *ptr0;

+        len0 = len;

+      }

+    }

+  }

+  pos++;

+  _cyclicBufferPos++;

+  cur++;

+  {

+    UInt32 num = (UInt32)(distances - _distances);

+    *_distances = num - 1;

+    _distances += num;

+    limit -= num;

+  }

+  }

+  while (limit > 0 && --size != 0);

+  *posRes = pos;

+  return limit;

+}

+

+#endif

+

+static void BtGetMatches(CMatchFinderMt *p, UInt32 *distances)

+{

+  UInt32 numProcessed = 0;

+  UInt32 curPos = 2;

+  UInt32 limit = kMtBtBlockSize - (p->matchMaxLen * 2);

+  

+  distances[1] = p->hashNumAvail;

+  

+  while (curPos < limit)

+  {

+    if (p->hashBufPos == p->hashBufPosLimit)

+    {

+      MatchFinderMt_GetNextBlock_Hash(p);

+      distances[1] = numProcessed + p->hashNumAvail;

+      if (p->hashNumAvail >= p->numHashBytes)

+        continue;

+      distances[0] = curPos + p->hashNumAvail;

+      distances += curPos;

+      for (; p->hashNumAvail != 0; p->hashNumAvail--)

+        *distances++ = 0;

+      return;

+    }

+    {

+      UInt32 size = p->hashBufPosLimit - p->hashBufPos;

+      UInt32 lenLimit = p->matchMaxLen;

+      UInt32 pos = p->pos;

+      UInt32 cyclicBufferPos = p->cyclicBufferPos;

+      if (lenLimit >= p->hashNumAvail)

+        lenLimit = p->hashNumAvail;

+      {

+        UInt32 size2 = p->hashNumAvail - lenLimit + 1;

+        if (size2 < size)

+          size = size2;

+        size2 = p->cyclicBufferSize - cyclicBufferPos;

+        if (size2 < size)

+          size = size2;

+      }

+      

+      #ifndef MFMT_GM_INLINE

+      while (curPos < limit && size-- != 0)

+      {

+        UInt32 *startDistances = distances + curPos;

+        UInt32 num = (UInt32)(GetMatchesSpec1(lenLimit, pos - p->hashBuf[p->hashBufPos++],

+            pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,

+            startDistances + 1, p->numHashBytes - 1) - startDistances);

+        *startDistances = num - 1;

+        curPos += num;

+        cyclicBufferPos++;

+        pos++;

+        p->buffer++;

+      }

+      #else

+      {

+        UInt32 posRes;

+        curPos = limit - GetMatchesSpecN(lenLimit, pos, p->buffer, p->son, cyclicBufferPos, p->cyclicBufferSize, p->cutValue,

+            distances + curPos, p->numHashBytes - 1, p->hashBuf + p->hashBufPos, (Int32)(limit - curPos), size, &posRes);

+        p->hashBufPos += posRes - pos;

+        cyclicBufferPos += posRes - pos;

+        p->buffer += posRes - pos;

+        pos = posRes;

+      }

+      #endif

+

+      numProcessed += pos - p->pos;

+      p->hashNumAvail -= pos - p->pos;

+      p->pos = pos;

+      if (cyclicBufferPos == p->cyclicBufferSize)

+        cyclicBufferPos = 0;

+      p->cyclicBufferPos = cyclicBufferPos;

+    }

+  }

+  

+  distances[0] = curPos;

+}

+

+static void BtFillBlock(CMatchFinderMt *p, UInt32 globalBlockIndex)

+{

+  CMtSync *sync = &p->hashSync;

+  if (!sync->needStart)

+  {

+    CriticalSection_Enter(&sync->cs);

+    sync->csWasEntered = True;

+  }

+  

+  BtGetMatches(p, p->btBuf + (globalBlockIndex & kMtBtNumBlocksMask) * kMtBtBlockSize);

+

+  if (p->pos > kMtMaxValForNormalize - kMtBtBlockSize)

+  {

+    UInt32 subValue = p->pos - p->cyclicBufferSize;

+    MatchFinder_Normalize3(subValue, p->son, (size_t)p->cyclicBufferSize * 2);

+    p->pos -= subValue;

+  }

+

+  if (!sync->needStart)

+  {

+    CriticalSection_Leave(&sync->cs);

+    sync->csWasEntered = False;

+  }

+}

+

+void BtThreadFunc(CMatchFinderMt *mt)

+{

+  CMtSync *p = &mt->btSync;

+  for (;;)

+  {

+    UInt32 blockIndex = 0;

+    Event_Wait(&p->canStart);

+    Event_Set(&p->wasStarted);

+    for (;;)

+    {

+      if (p->exit)

+        return;

+      if (p->stopWriting)

+      {

+        p->numProcessedBlocks = blockIndex;

+        MtSync_StopWriting(&mt->hashSync);

+        Event_Set(&p->wasStopped);

+        break;

+      }

+      Semaphore_Wait(&p->freeSemaphore);

+      BtFillBlock(mt, blockIndex++);

+      Semaphore_Release1(&p->filledSemaphore);

+    }

+  }

+}

+

+void MatchFinderMt_Construct(CMatchFinderMt *p)

+{

+  p->hashBuf = NULL;

+  MtSync_Construct(&p->hashSync);

+  MtSync_Construct(&p->btSync);

+}

+

+static void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAllocPtr alloc)

+{

+  ISzAlloc_Free(alloc, p->hashBuf);

+  p->hashBuf = NULL;

+}

+

+void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAllocPtr alloc)

+{

+  MtSync_Destruct(&p->hashSync);

+  MtSync_Destruct(&p->btSync);

+  MatchFinderMt_FreeMem(p, alloc);

+}

+

+#define kHashBufferSize (kMtHashBlockSize * kMtHashNumBlocks)

+#define kBtBufferSize (kMtBtBlockSize * kMtBtNumBlocks)

+

+static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p);  return 0; }

+static THREAD_FUNC_RET_TYPE THREAD_FUNC_CALL_TYPE BtThreadFunc2(void *p)

+{

+  Byte allocaDummy[0x180];

+  unsigned i = 0;

+  for (i = 0; i < 16; i++)

+    allocaDummy[i] = (Byte)0;

+  if (allocaDummy[0] == 0)

+    BtThreadFunc((CMatchFinderMt *)p);

+  return 0;

+}

+

+SRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore,

+    UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAllocPtr alloc)

+{

+  CMatchFinder *mf = p->MatchFinder;

+  p->historySize = historySize;

+  if (kMtBtBlockSize <= matchMaxLen * 4)

+    return SZ_ERROR_PARAM;

+  if (!p->hashBuf)

+  {

+    p->hashBuf = (UInt32 *)ISzAlloc_Alloc(alloc, (kHashBufferSize + kBtBufferSize) * sizeof(UInt32));

+    if (!p->hashBuf)

+      return SZ_ERROR_MEM;

+    p->btBuf = p->hashBuf + kHashBufferSize;

+  }

+  keepAddBufferBefore += (kHashBufferSize + kBtBufferSize);

+  keepAddBufferAfter += kMtHashBlockSize;

+  if (!MatchFinder_Create(mf, historySize, keepAddBufferBefore, matchMaxLen, keepAddBufferAfter, alloc))

+    return SZ_ERROR_MEM;

+

+  RINOK(MtSync_Create(&p->hashSync, HashThreadFunc2, p, kMtHashNumBlocks));

+  RINOK(MtSync_Create(&p->btSync, BtThreadFunc2, p, kMtBtNumBlocks));

+  return SZ_OK;

+}

+

+/* Call it after ReleaseStream / SetStream */

+static void MatchFinderMt_Init(CMatchFinderMt *p)

+{

+  CMatchFinder *mf = p->MatchFinder;

+  

+  p->btBufPos =

+  p->btBufPosLimit = 0;

+  p->hashBufPos =

+  p->hashBufPosLimit = 0;

+

+  /* Init without data reading. We don't want to read data in this thread */

+  MatchFinder_Init_3(mf, False);

+  MatchFinder_Init_LowHash(mf);

+  

+  p->pointerToCurPos = Inline_MatchFinder_GetPointerToCurrentPos(mf);

+  p->btNumAvailBytes = 0;

+  p->lzPos = p->historySize + 1;

+

+  p->hash = mf->hash;

+  p->fixedHashSize = mf->fixedHashSize;

+  p->crc = mf->crc;

+

+  p->son = mf->son;

+  p->matchMaxLen = mf->matchMaxLen;

+  p->numHashBytes = mf->numHashBytes;

+  p->pos = mf->pos;

+  p->buffer = mf->buffer;

+  p->cyclicBufferPos = mf->cyclicBufferPos;

+  p->cyclicBufferSize = mf->cyclicBufferSize;

+  p->cutValue = mf->cutValue;

+}

+

+/* ReleaseStream is required to finish multithreading */

+void MatchFinderMt_ReleaseStream(CMatchFinderMt *p)

+{

+  MtSync_StopWriting(&p->btSync);

+  /* p->MatchFinder->ReleaseStream(); */

+}

+

+static void MatchFinderMt_Normalize(CMatchFinderMt *p)

+{

+  MatchFinder_Normalize3(p->lzPos - p->historySize - 1, p->hash, p->fixedHashSize);

+  p->lzPos = p->historySize + 1;

+}

+

+static void MatchFinderMt_GetNextBlock_Bt(CMatchFinderMt *p)

+{

+  UInt32 blockIndex;

+  MtSync_GetNextBlock(&p->btSync);

+  blockIndex = ((p->btSync.numProcessedBlocks - 1) & kMtBtNumBlocksMask);

+  p->btBufPosLimit = p->btBufPos = blockIndex * kMtBtBlockSize;

+  p->btBufPosLimit += p->btBuf[p->btBufPos++];

+  p->btNumAvailBytes = p->btBuf[p->btBufPos++];

+  if (p->lzPos >= kMtMaxValForNormalize - kMtBtBlockSize)

+    MatchFinderMt_Normalize(p);

+}

+

+static const Byte * MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt *p)

+{

+  return p->pointerToCurPos;

+}

+

+#define GET_NEXT_BLOCK_IF_REQUIRED if (p->btBufPos == p->btBufPosLimit) MatchFinderMt_GetNextBlock_Bt(p);

+

+static UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p)

+{

+  GET_NEXT_BLOCK_IF_REQUIRED;

+  return p->btNumAvailBytes;

+}

+

+static UInt32 * MixMatches2(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)

+{

+  UInt32 h2, curMatch2;

+  UInt32 *hash = p->hash;

+  const Byte *cur = p->pointerToCurPos;

+  UInt32 lzPos = p->lzPos;

+  MT_HASH2_CALC

+      

+  curMatch2 = hash[h2];

+  hash[h2] = lzPos;

+

+  if (curMatch2 >= matchMinPos)

+    if (cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])

+    {

+      *distances++ = 2;

+      *distances++ = lzPos - curMatch2 - 1;

+    }

+  

+  return distances;

+}

+

+static UInt32 * MixMatches3(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)

+{

+  UInt32 h2, h3, curMatch2, curMatch3;

+  UInt32 *hash = p->hash;

+  const Byte *cur = p->pointerToCurPos;

+  UInt32 lzPos = p->lzPos;

+  MT_HASH3_CALC

+

+  curMatch2 = hash[                h2];

+  curMatch3 = (hash + kFix3HashSize)[h3];

+  

+  hash[                h2] = lzPos;

+  (hash + kFix3HashSize)[h3] = lzPos;

+

+  if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])

+  {

+    distances[1] = lzPos - curMatch2 - 1;

+    if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])

+    {

+      distances[0] = 3;

+      return distances + 2;

+    }

+    distances[0] = 2;

+    distances += 2;

+  }

+  

+  if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])

+  {

+    *distances++ = 3;

+    *distances++ = lzPos - curMatch3 - 1;

+  }

+  

+  return distances;

+}

+

+/*

+static UInt32 *MixMatches4(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)

+{

+  UInt32 h2, h3, h4, curMatch2, curMatch3, curMatch4;

+  UInt32 *hash = p->hash;

+  const Byte *cur = p->pointerToCurPos;

+  UInt32 lzPos = p->lzPos;

+  MT_HASH4_CALC

+      

+  curMatch2 = hash[                h2];

+  curMatch3 = (hash + kFix3HashSize)[h3];

+  curMatch4 = (hash + kFix4HashSize)[h4];

+  

+  hash[                h2] = lzPos;

+  (hash + kFix3HashSize)[h3] = lzPos;

+  (hash + kFix4HashSize)[h4] = lzPos;

+

+  if (curMatch2 >= matchMinPos && cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])

+  {

+    distances[1] = lzPos - curMatch2 - 1;

+    if (cur[(ptrdiff_t)curMatch2 - lzPos + 2] == cur[2])

+    {

+      distances[0] = (cur[(ptrdiff_t)curMatch2 - lzPos + 3] == cur[3]) ? 4 : 3;

+      return distances + 2;

+    }

+    distances[0] = 2;

+    distances += 2;

+  }

+  

+  if (curMatch3 >= matchMinPos && cur[(ptrdiff_t)curMatch3 - lzPos] == cur[0])

+  {

+    distances[1] = lzPos - curMatch3 - 1;

+    if (cur[(ptrdiff_t)curMatch3 - lzPos + 3] == cur[3])

+    {

+      distances[0] = 4;

+      return distances + 2;

+    }

+    distances[0] = 3;

+    distances += 2;

+  }

+

+  if (curMatch4 >= matchMinPos)

+    if (

+      cur[(ptrdiff_t)curMatch4 - lzPos] == cur[0] &&

+      cur[(ptrdiff_t)curMatch4 - lzPos + 3] == cur[3]

+      )

+    {

+      *distances++ = 4;

+      *distances++ = lzPos - curMatch4 - 1;

+    }

+  

+  return distances;

+}

+*/

+

+#define INCREASE_LZ_POS p->lzPos++; p->pointerToCurPos++;

+

+static UInt32 MatchFinderMt2_GetMatches(CMatchFinderMt *p, UInt32 *distances)

+{

+  const UInt32 *btBuf = p->btBuf + p->btBufPos;

+  UInt32 len = *btBuf++;

+  p->btBufPos += 1 + len;

+  p->btNumAvailBytes--;

+  {

+    UInt32 i;

+    for (i = 0; i < len; i += 2)

+    {

+      UInt32 v0 = btBuf[0];

+      UInt32 v1 = btBuf[1];

+      btBuf += 2;

+      distances[0] = v0;

+      distances[1] = v1;

+      distances += 2;

+    }

+  }

+  INCREASE_LZ_POS

+  return len;

+}

+

+static UInt32 MatchFinderMt_GetMatches(CMatchFinderMt *p, UInt32 *distances)

+{

+  const UInt32 *btBuf = p->btBuf + p->btBufPos;

+  UInt32 len = *btBuf++;

+  p->btBufPos += 1 + len;

+

+  if (len == 0)

+  {

+    /* change for bt5 ! */

+    if (p->btNumAvailBytes-- >= 4)

+      len = (UInt32)(p->MixMatchesFunc(p, p->lzPos - p->historySize, distances) - (distances));

+  }

+  else

+  {

+    /* Condition: there are matches in btBuf with length < p->numHashBytes */

+    UInt32 *distances2;

+    p->btNumAvailBytes--;

+    distances2 = p->MixMatchesFunc(p, p->lzPos - btBuf[1], distances);

+    do

+    {

+      UInt32 v0 = btBuf[0];

+      UInt32 v1 = btBuf[1];

+      btBuf += 2;

+      distances2[0] = v0;

+      distances2[1] = v1;

+      distances2 += 2;

+    }

+    while ((len -= 2) != 0);

+    len = (UInt32)(distances2 - (distances));

+  }

+  INCREASE_LZ_POS

+  return len;

+}

+

+#define SKIP_HEADER2_MT  do { GET_NEXT_BLOCK_IF_REQUIRED

+#define SKIP_HEADER_MT(n) SKIP_HEADER2_MT if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash;

+#define SKIP_FOOTER_MT } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while (--num != 0);

+

+static void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num)

+{

+  SKIP_HEADER2_MT { p->btNumAvailBytes--;

+  SKIP_FOOTER_MT

+}

+

+static void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num)

+{

+  SKIP_HEADER_MT(2)

+      UInt32 h2;

+      MT_HASH2_CALC

+      hash[h2] = p->lzPos;

+  SKIP_FOOTER_MT

+}

+

+static void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num)

+{

+  SKIP_HEADER_MT(3)

+      UInt32 h2, h3;

+      MT_HASH3_CALC

+      (hash + kFix3HashSize)[h3] =

+      hash[                h2] =

+        p->lzPos;

+  SKIP_FOOTER_MT

+}

+

+/*

+static void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num)

+{

+  SKIP_HEADER_MT(4)

+      UInt32 h2, h3, h4;

+      MT_HASH4_CALC

+      (hash + kFix4HashSize)[h4] =

+      (hash + kFix3HashSize)[h3] =

+      hash[                h2] =

+        p->lzPos;

+  SKIP_FOOTER_MT

+}

+*/

+

+void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable)

+{

+  vTable->Init = (Mf_Init_Func)MatchFinderMt_Init;

+  vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinderMt_GetNumAvailableBytes;

+  vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinderMt_GetPointerToCurrentPos;

+  vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt_GetMatches;

+  

+  switch (p->MatchFinder->numHashBytes)

+  {

+    case 2:

+      p->GetHeadsFunc = GetHeads2;

+      p->MixMatchesFunc = (Mf_Mix_Matches)NULL;

+      vTable->Skip = (Mf_Skip_Func)MatchFinderMt0_Skip;

+      vTable->GetMatches = (Mf_GetMatches_Func)MatchFinderMt2_GetMatches;

+      break;

+    case 3:

+      p->GetHeadsFunc = GetHeads3;

+      p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches2;

+      vTable->Skip = (Mf_Skip_Func)MatchFinderMt2_Skip;

+      break;

+    default:

+    /* case 4: */

+      p->GetHeadsFunc = p->MatchFinder->bigHash ? GetHeads4b : GetHeads4;

+      p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches3;

+      vTable->Skip = (Mf_Skip_Func)MatchFinderMt3_Skip;

+      break;

+    /*

+    default:

+      p->GetHeadsFunc = GetHeads5;

+      p->MixMatchesFunc = (Mf_Mix_Matches)MixMatches4;

+      vTable->Skip = (Mf_Skip_Func)MatchFinderMt4_Skip;

+      break;

+    */

+  }

+}