/* MatchFinderMt.c */

#ifdef _WIN32

#define USE_ALLOCA

#endif

#ifdef USE_ALLOCA

#ifdef _WIN32

#include <malloc.h>

#else

#include <stdlib.h>

#endif

#endif

#include "../../7zCrc.h"

#include "LzHash.h"

#include "MatchFinderMt.h"

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);

}

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);

  }

  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 */

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;

}

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;

}

HRes MtSync_Create2(CMtSync *p, unsigned (StdCall *startAddress)(void *), void *obj, UInt32 numBlocks)

{

  if (p->wasCreated)

    return SZ_OK;

  RINOK(CriticalSection_Init(&p->cs));

  p->csWasInitialized = True;

  RINOK(AutoResetEvent_CreateNotSignaled(&p->canStart));

  RINOK(AutoResetEvent_CreateNotSignaled(&p->wasStarted));

  RINOK(AutoResetEvent_CreateNotSignaled(&p->wasStopped));

  RINOK(Semaphore_Create(&p->freeSemaphore, numBlocks, numBlocks));

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

  p->needStart = True;

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

  p->wasCreated = True;

  return SZ_OK;

}

HRes MtSync_Create(CMtSync *p, unsigned (StdCall *startAddress)(void *), void *obj, UInt32 numBlocks)

{

  HRes 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_GetHeads(name, v) \

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

UInt32 *hash, UInt32 hashMask, UInt32 *heads, UInt32 numHeads) { \

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

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

DEF_GetHeads(2,  (p[0] | ((UInt32)p[1] << 8)) & hashMask)

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

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

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

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

void HashThreadFunc(CMatchFinderMt *mt)

{

  CMtSync *p = &mt->hashSync;

  for (;;)

  {

    UInt32 numProcessedBlocks = 0;

    Event_Wait(&p->canStart);

    Event_Set(&p->wasStarted);

    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 = MatchFinder_GetPointerToCurrentPos(mf);

            const Byte *afterPtr;

            MatchFinder_MoveBlock(mf);

            afterPtr = MatchFinder_GetPointerToCurrentPos(mf);

            mt->pointerToCurPos -= beforePtr - afterPtr;

            mt->buffer -= beforePtr - afterPtr;

          }

          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, 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);

            heads[0] += num;

          }

          mf->pos += num;

          mf->buffer += num;

        }

      }

      Semaphore_Release1(&p->filledSemaphore);

    }

  }

}

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

#if _MSC_VER >= 1300

#define NO_INLINE __declspec(noinline) __fastcall 

#else

#ifdef _MSC_VER

#define NO_INLINE __fastcall 

#endif

#endif

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

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;

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

        distances[curPos++] = 0;

      break;

    }

    {

      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;

}

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, 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 = 0;

  MtSync_Construct(&p->hashSync);

  MtSync_Construct(&p->btSync);

}

void MatchFinderMt_FreeMem(CMatchFinderMt *p, ISzAlloc *alloc)

{

  alloc->Free(p->hashBuf);

  p->hashBuf = 0;

}

void MatchFinderMt_Destruct(CMatchFinderMt *p, ISzAlloc *alloc)

{

  MtSync_Destruct(&p->hashSync);

  MtSync_Destruct(&p->btSync);

  MatchFinderMt_FreeMem(p, alloc);

}

#define kHashBufferSize (kMtHashBlockSize * kMtHashNumBlocks)

#define kBtBufferSize (kMtBtBlockSize * kMtBtNumBlocks)

static unsigned StdCall HashThreadFunc2(void *p) { HashThreadFunc((CMatchFinderMt *)p);  return 0; }

static unsigned StdCall BtThreadFunc2(void *p) 

{ 

  #ifdef USE_ALLOCA

  alloca(0x180);

  #endif

  BtThreadFunc((CMatchFinderMt *)p); 

  return 0; 

}

HRes MatchFinderMt_Create(CMatchFinderMt *p, UInt32 historySize, UInt32 keepAddBufferBefore, 

    UInt32 matchMaxLen, UInt32 keepAddBufferAfter, ISzAlloc *alloc)

{ 

  CMatchFinder *mf = p->MatchFinder;

  p->historySize = historySize;

  if (kMtBtBlockSize <= matchMaxLen * 4)

    return E_INVALIDARG;

  if (p->hashBuf == 0)

  {

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

    if (p->hashBuf == 0)

      return SZE_OUTOFMEMORY;

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

  }

  keepAddBufferBefore += (kHashBufferSize + kBtBufferSize);

  keepAddBufferAfter += kMtHashBlockSize;

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

    return SZE_OUTOFMEMORY;

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

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

  return SZ_OK;

}

/* Call it after ReleaseStream / SetStream */

void MatchFinderMt_Init(CMatchFinderMt *p)

{ 

  CMatchFinder *mf = p->MatchFinder;

  p->btBufPos = p->btBufPosLimit = 0;

  p->hashBufPos = p->hashBufPosLimit = 0;

  MatchFinder_Init(mf);

  p->pointerToCurPos = MatchFinder_GetPointerToCurrentPos(mf);

  p->btNumAvailBytes = 0;

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

  p->hash = mf->hash;

  p->fixedHashSize = mf->fixedHashSize;

  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)

{