lzmaencoder.cpp

7-Zip 3.11的源码

// LZMA/Encoder.cpp

#include "StdAfx.h"

#include "../../../Common/Defs.h"

#include "LZMAEncoder.h"

#ifdef COMPRESS_MF_BT
#include "../LZ/BinTree/BinTree2.h"
#include "../LZ/BinTree/BinTree3.h"
#include "../LZ/BinTree/BinTree4.h"
#include "../LZ/BinTree/BinTree4b.h"
#endif

#ifdef COMPRESS_MF_PAT
#include "../LZ/Patricia/Pat2.h"
#include "../LZ/Patricia/Pat2H.h"
#include "../LZ/Patricia/Pat3H.h"
#include "../LZ/Patricia/Pat4H.h"
#include "../LZ/Patricia/Pat2R.h"
#endif

#ifdef COMPRESS_MF_HC
#include "../LZ/HashChain/HC3.h"
#include "../LZ/HashChain/HC4.h"
#endif

#ifdef COMPRESS_MF_MT
#include "../LZ/MT/MT.h"
#endif

namespace NCompress {
namespace NLZMA {

enum 
{
  kBT2,
  kBT3,
  kBT4,
  kBT4B,
  kPat2,
  kPat2H,
  kPat3H,
  kPat4H,
  kPat2R,
  kHC3,
  kHC4
};

static const wchar_t *kMatchFinderIDs[] = 
{
  L"BT2",
  L"BT3",
  L"BT4",
  L"BT4B",
  L"PAT2",
  L"PAT2H",
  L"PAT3H",
  L"PAT4H",
  L"PAT2R",
  L"HC3",
  L"HC4"
};

BYTE g_FastPos[1024];

class CFastPosInit
{
public:
  CFastPosInit()
  {
    const BYTE kFastSlots = 20;
    int c = 2;
    g_FastPos[0] = 0;
    g_FastPos[1] = 1;

    for (BYTE slotFast = 2; slotFast < kFastSlots; slotFast++)
    {
      UINT32 k = (1 << ((slotFast >> 1) - 1));
      for (UINT32 j = 0; j < k; j++, c++)
        g_FastPos[c] = slotFast;
    }
  }
} g_FastPosInit;

const int kDefaultDictionaryLogSize = 20;
const UINT32 kNumFastBytesDefault = 0x20;

CEncoder::CEncoder():
  _dictionarySize(1 << kDefaultDictionaryLogSize),
  _dictionarySizePrev(UINT32(-1)),
  _numFastBytes(kNumFastBytesDefault),
  _numFastBytesPrev(UINT32(-1)),
  _distTableSize(kDefaultDictionaryLogSize * 2),
  _posStateBits(2),
  _posStateMask(4 - 1),
  _numLiteralPosStateBits(0),
  _numLiteralContextBits(3),
   #ifdef COMPRESS_MF_MT
  _multiThread(false),
   #endif
  _matchFinderIndex(kBT4),
  _writeEndMark(false)
{
  _maxMode = false;
  _fastMode = false;
  _posAlignEncoder.Create(kNumAlignBits);
  for(int i = 0; i < kNumPosModels; i++)
    _posEncoders[i].Create(((kStartPosModelIndex + i) >> 1) - 1);
}

HRESULT CEncoder::Create()
{
  if (!_matchFinder)
  {
    switch(_matchFinderIndex)
    {
      #ifdef COMPRESS_MF_BT
      case kBT2:
        _matchFinder = new NBT2::CMatchFinderBinTree;
        break;
      case kBT3:
        _matchFinder = new NBT3::CMatchFinderBinTree;
        break;
      case kBT4:
        _matchFinder = new NBT4::CMatchFinderBinTree;
        break;
      case kBT4B:
        _matchFinder = new NBT4B::CMatchFinderBinTree;
        break;
      #endif
      
      #ifdef COMPRESS_MF_PAT
      case kPat2:
        _matchFinder = new NPat2::CPatricia;
        break;
      case kPat2H:
        _matchFinder = new NPat2H::CPatricia;
        break;
      case kPat3H:
        _matchFinder = new NPat3H::CPatricia;
        break;
      case kPat4H:
        _matchFinder = new NPat4H::CPatricia;
        break;
      case kPat2R:
        _matchFinder = new NPat2R::CPatricia;
        break;
      #endif

      #ifdef COMPRESS_MF_HC
      case kHC3:
        _matchFinder = new NHC3::CMatchFinderHC;
        break;
      case kHC4:
        _matchFinder = new NHC4::CMatchFinderHC;
        break;
      #endif
    }
    #ifdef COMPRESS_MF_MT
    if (_multiThread)
    {
      CMatchFinderMT *mfSpec = new CMatchFinderMT;
      CMyComPtr<IMatchFinder> mf = mfSpec;
      RINOK(mfSpec->SetMatchFinder(_matchFinder));
      _matchFinder.Release();
      _matchFinder = mf;
    }
    #endif
  }
  if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes)
    return S_OK;
  RINOK(_matchFinder->Create(_dictionarySize, kNumOpts, _numFastBytes, 
      kMatchMaxLen - _numFastBytes));
  _dictionarySizePrev = _dictionarySize;
  _numFastBytesPrev = _numFastBytes;
  _literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits);
  _lenEncoder.Create(1 << _posStateBits);
  _repMatchLenEncoder.Create(1 << _posStateBits);
  return S_OK;
}

static inline bool AreStringsEqual(const wchar_t *s, const wchar_t *testString)
{
  while (true)
  {
    wchar_t c = *testString;
    if (c >= 'a' && c <= 'z')
      c -= 0x20;
    if (*s != c)
      return false;
    if (c == 0)
      return true;
    s++;
    testString++;
  }
}

// ICompressSetEncoderProperties2
STDMETHODIMP CEncoder::SetCoderProperties(const PROPID *propIDs, 
    const PROPVARIANT *properties, UINT32 numProperties)
{
  for (UINT32 i = 0; i < numProperties; i++)
  {
    const PROPVARIANT &prop = properties[i];
    switch(propIDs[i])
    {
      case NCoderPropID::kNumFastBytes:
      {
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        UINT32 numFastBytes = prop.ulVal;
        if(numFastBytes < 2 || numFastBytes > kMatchMaxLen)
          return E_INVALIDARG;
        _numFastBytes = numFastBytes;
        break;
      }
      case NCoderPropID::kAlgorithm:
      {
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        UINT32 maximize = prop.ulVal;
        _fastMode = (maximize == 0); 
        _maxMode = (maximize >= 2);
        break;
      }
      case NCoderPropID::kMatchFinder:
      {
        if (prop.vt != VT_BSTR)
          return E_INVALIDARG;
        int matchFinderIndexPrev = _matchFinderIndex;
        _matchFinderIndex = 0;
        const int kNumMFs = sizeof(kMatchFinderIDs) / sizeof(kMatchFinderIDs[0]);
        int m;
        for (m = 0; m < kNumMFs; m++)
        {
          if (AreStringsEqual(kMatchFinderIDs[m], prop.bstrVal))
          {
            _matchFinderIndex = m;
            break;
          }
        }
        if (m == kNumMFs)
          return E_INVALIDARG;
        if (!_matchFinder && matchFinderIndexPrev != _matchFinderIndex)
        {
          _dictionarySizePrev = UINT32(-1);
          _matchFinder.Release();
        }
        break;
      }
      #ifdef COMPRESS_MF_MT
      case NCoderPropID::kMultiThread:
      {
        if (prop.vt != VT_BOOL)
          return E_INVALIDARG;
        bool newMultiThread = (prop.boolVal != VARIANT_FALSE);
        if (newMultiThread != _multiThread)
        {
          _dictionarySizePrev = UINT32(-1);
          _matchFinder.Release();
        }
        _multiThread = newMultiThread;
        break;
      }
      #endif
      case NCoderPropID::kDictionarySize:
      {
        const int kDicLogSizeMaxCompress = 28;
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        UINT32 dictionarySize = prop.ulVal;
        if (dictionarySize < UINT32(1 << kDicLogSizeMin) ||
            dictionarySize > UINT32(1 << kDicLogSizeMaxCompress))
          return E_INVALIDARG;
        _dictionarySize = dictionarySize;
        UINT32 dicLogSize;
        for(dicLogSize = 0; dicLogSize < kDicLogSizeMaxCompress; dicLogSize++)
          if (dictionarySize <= (UINT32(1) << dicLogSize))
            break;
        _distTableSize = dicLogSize * 2;
        break;
      }
      case NCoderPropID::kPosStateBits:
      {
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        UINT32 value = prop.ulVal;
        if (value > NLength::kNumPosStatesBitsEncodingMax)
          return E_INVALIDARG;
        _posStateBits = value;
        _posStateMask = (1 << _posStateBits) - 1;
        break;
      }
      case NCoderPropID::kLitPosBits:
      {
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        UINT32 value = prop.ulVal;
        if (value > kNumLitPosStatesBitsEncodingMax)
          return E_INVALIDARG;
        _numLiteralPosStateBits = value;
        break;
      }
      case NCoderPropID::kLitContextBits:
      {
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        UINT32 value = prop.ulVal;
        if (value > kNumLitContextBitsMax)
          return E_INVALIDARG;
        _numLiteralContextBits = value;
        break;
      }
      default:
        return E_INVALIDARG;
    }
  }
  return S_OK;
}

STDMETHODIMP CEncoder::WriteCoderProperties(ISequentialOutStream *outStream)
{ 
  BYTE firstByte = (_posStateBits * 5 + _numLiteralPosStateBits) * 9 + _numLiteralContextBits;
  RINOK(outStream->Write(&firstByte, sizeof(firstByte), NULL));
  return outStream->Write(&_dictionarySize, sizeof(_dictionarySize), NULL);
}

STDMETHODIMP CEncoder::Init(
    ISequentialOutStream *outStream)
{
  CBaseCoder::Init();

  // RINOK(_matchFinder->Init(inStream));
  _rangeEncoder.Init(outStream);

  int i;
  for(i = 0; i < kNumStates; i++)
  {
    for (UINT32 j = 0; j <= _posStateMask; j++)
    {
      _mainChoiceEncoders[i][j].Init();
      _matchRepShortChoiceEncoders[i][j].Init();
    }
    _matchChoiceEncoders[i].Init();
    _matchRepChoiceEncoders[i].Init();
    _matchRep1ChoiceEncoders[i].Init();
    _matchRep2ChoiceEncoders[i].Init();
  }

  _literalEncoder.Init();

  // _repMatchLenEncoder.Init();
  
  for(i = 0; i < kNumLenToPosStates; i++)
    _posSlotEncoder[i].Init();

  for(i = 0; i < kNumPosModels; i++)
    _posEncoders[i].Init();

  _lenEncoder.Init();
  _repMatchLenEncoder.Init();

  _posAlignEncoder.Init();

  _longestMatchWasFound = false;
  _optimumEndIndex = 0;
  _optimumCurrentIndex = 0;
  _additionalOffset = 0;

  return S_OK;
}

void CEncoder::MovePos(UINT32 num)
{
  for (;num > 0; num--)
  {
    _matchFinder->DummyLongestMatch();
    HRESULT result = _matchFinder->MovePos();
    if (result != S_OK)
      throw CMatchFinderException(result);
    _additionalOffset++;
  }
}

UINT32 CEncoder::Backward(UINT32 &backRes, UINT32 cur)
{
  _optimumEndIndex = cur;
  UINT32 posMem = _optimum[cur].PosPrev;
  UINT32 backMem = _optimum[cur].BackPrev;
  do
  {
    if (_optimum[cur].Prev1IsChar)
    {
      _optimum[posMem].MakeAsChar();
      _optimum[posMem].PosPrev = posMem - 1;
      if (_optimum[cur].Prev2)
      {
        _optimum[posMem - 1].Prev1IsChar = false;
        _optimum[posMem - 1].PosPrev = _optimum[cur].PosPrev2;
        _optimum[posMem - 1].BackPrev = _optimum[cur].BackPrev2;
      }
    }
    UINT32 posPrev = posMem;
    UINT32 backCur = backMem;

    backMem = _optimum[posPrev].BackPrev;
    posMem = _optimum[posPrev].PosPrev;

    _optimum[posPrev].BackPrev = backCur;
    _optimum[posPrev].PosPrev = cur;
    cur = posPrev;
  }
  while(cur > 0);
  backRes = _optimum[0].BackPrev;
  _optimumCurrentIndex  = _optimum[0].PosPrev;
  return _optimumCurrentIndex; 
}

/*
inline UINT32 GetMatchLen(const BYTE *data, UINT32 back, UINT32 limit)
{  
  back++;
  for(UINT32 i = 0; i < limit && data[i] == data[i - back]; i++);