matchfindermt.c

一个7ZIP的解压源码。比较详细。里面含有四种语言的实现代码。

  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)
{ 
  MtSync_StopWriting(&p->btSync);
  /* p->MatchFinder->ReleaseStream(); */
}

void MatchFinderMt_Normalize(CMatchFinderMt *p)
{
  MatchFinder_Normalize3(p->lzPos - p->historySize - 1, p->hash, p->fixedHashSize);
  p->lzPos = p->historySize + 1;
}

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

const Byte * MatchFinderMt_GetPointerToCurrentPos(CMatchFinderMt *p)
{
  return p->pointerToCurPos;
}

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

UInt32 MatchFinderMt_GetNumAvailableBytes(CMatchFinderMt *p)
{ 
  GET_NEXT_BLOCK_IF_REQUIRED;
  return p->btNumAvailBytes;
}

Byte MatchFinderMt_GetIndexByte(CMatchFinderMt *p, Int32 index)
{ 
  return p->pointerToCurPos[index]; 
}

UInt32 * MixMatches2(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
{
  UInt32 hash2Value, curMatch2;
  UInt32 *hash = p->hash;
  const Byte *cur = p->pointerToCurPos;
  UInt32 lzPos = p->lzPos; 
  MT_HASH2_CALC
      
  curMatch2 = hash[hash2Value];
  hash[hash2Value] = lzPos;

  if (curMatch2 >= matchMinPos) 
    if (cur[(ptrdiff_t)curMatch2 - lzPos] == cur[0])
    {
      *distances++ = 2; 
      *distances++ = lzPos - curMatch2 - 1;
    }
  return distances;
}

UInt32 * MixMatches3(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
{
  UInt32 hash2Value, hash3Value, curMatch2, curMatch3;
  UInt32 *hash = p->hash;
  const Byte *cur = p->pointerToCurPos;
  UInt32 lzPos = p->lzPos; 
  MT_HASH3_CALC

  curMatch2 = hash[                hash2Value];
  curMatch3 = hash[kFix3HashSize + hash3Value];
  
  hash[                hash2Value] = 
  hash[kFix3HashSize + hash3Value] = 
    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;
}

/*
UInt32 *MixMatches4(CMatchFinderMt *p, UInt32 matchMinPos, UInt32 *distances)
{
  UInt32 hash2Value, hash3Value, hash4Value, curMatch2, curMatch3, curMatch4;
  UInt32 *hash = p->hash;
  const Byte *cur = p->pointerToCurPos;
  UInt32 lzPos = p->lzPos; 
  MT_HASH4_CALC
      
  curMatch2 = hash[                hash2Value];
  curMatch3 = hash[kFix3HashSize + hash3Value];
  curMatch4 = hash[kFix4HashSize + hash4Value];
  
  hash[                hash2Value] = 
  hash[kFix3HashSize + hash3Value] = 
  hash[kFix4HashSize + hash4Value] = 
    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++;

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)
    {
      *distances++ = *btBuf++;
      *distances++ = *btBuf++;
    }
  }
  INCREASE_LZ_POS
  return len;
}

UInt32 MatchFinderMt_GetMatches(CMatchFinderMt *p, UInt32 *distances)
{ 
  const UInt32 *btBuf = p->btBuf + p->btBufPos;
  UInt32 len = *btBuf++;
  p->btBufPos += 1 + len;

  if (len == 0)
  {
    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 
    {
      *distances2++ = *btBuf++;
      *distances2++ = *btBuf++;
    }
    while ((len -= 2) != 0);
    len  = (UInt32)(distances2 - (distances));
  }
  INCREASE_LZ_POS
  return len;
}

#define SKIP_HEADER2  do { GET_NEXT_BLOCK_IF_REQUIRED
#define SKIP_HEADER(n) SKIP_HEADER2 if (p->btNumAvailBytes-- >= (n)) { const Byte *cur = p->pointerToCurPos; UInt32 *hash = p->hash;
#define SKIP_FOOTER } INCREASE_LZ_POS p->btBufPos += p->btBuf[p->btBufPos] + 1; } while(--num != 0);

void MatchFinderMt0_Skip(CMatchFinderMt *p, UInt32 num)
{ 
  SKIP_HEADER2 { p->btNumAvailBytes--;
  SKIP_FOOTER
}

void MatchFinderMt2_Skip(CMatchFinderMt *p, UInt32 num)
{ 
  SKIP_HEADER(2)
      UInt32 hash2Value;
      MT_HASH2_CALC
      hash[hash2Value] = p->lzPos;
  SKIP_FOOTER
}

void MatchFinderMt3_Skip(CMatchFinderMt *p, UInt32 num)
{ 
  SKIP_HEADER(3)
      UInt32 hash2Value, hash3Value;
      MT_HASH3_CALC
      hash[kFix3HashSize + hash3Value] = 
      hash[                hash2Value] = 
        p->lzPos;
  SKIP_FOOTER
}

/*
void MatchFinderMt4_Skip(CMatchFinderMt *p, UInt32 num)
{ 
  SKIP_HEADER(4)
      UInt32 hash2Value, hash3Value, hash4Value;
      MT_HASH4_CALC
      hash[kFix4HashSize + hash4Value] = 
      hash[kFix3HashSize + hash3Value] = 
      hash[                hash2Value] = 
        p->lzPos;
  SKIP_FOOTER
}
*/

void MatchFinderMt_CreateVTable(CMatchFinderMt *p, IMatchFinder *vTable)
{
  vTable->Init = (Mf_Init_Func)MatchFinderMt_Init;
  vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinderMt_GetIndexByte;
  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)0;
      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->GetHeadsFunc = 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;
    */
  }
}