lzmaencoder.cpp

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

// LZMA/Encoder.cpp

#include "StdAfx.h"

#include <stdio.h>

#ifdef _WIN32
#define USE_ALLOCA
#endif

#ifdef USE_ALLOCA
#ifdef _WIN32
#include <malloc.h>
#else
#include <stdlib.h>
#endif
#endif

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

#include "LZMAEncoder.h"

// extern "C" { #include "../../../../C/7zCrc.h" }

// #define SHOW_STAT


namespace NCompress {
namespace NLZMA {

// struct CCrcInit { CCrcInit() { InitCrcTable(); } } g_CrcInit;

const int kDefaultDictionaryLogSize = 22;
const UInt32 kNumFastBytesDefault = 0x20;

#ifndef LZMA_LOG_BSR
Byte g_FastPos[1 << kNumLogBits];

class CFastPosInit
{
public:
  CFastPosInit() { Init(); }
  void Init()
  {
    const Byte kFastSlots = kNumLogBits * 2;
    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;
#endif

void CLiteralEncoder2::Encode(NRangeCoder::CEncoder *rangeEncoder, Byte symbol)
{
  UInt32 context = 1;
  int i = 8;
  do 
  {
    i--;
    UInt32 bit = (symbol >> i) & 1;
    _encoders[context].Encode(rangeEncoder, bit);
    context = (context << 1) | bit;
  }
  while(i != 0);
}

void CLiteralEncoder2::EncodeMatched(NRangeCoder::CEncoder *rangeEncoder, 
    Byte matchByte, Byte symbol)
{
  UInt32 context = 1;
  int i = 8;
  do 
  {
    i--;
    UInt32 bit = (symbol >> i) & 1;
    UInt32 matchBit = (matchByte >> i) & 1;
    _encoders[0x100 + (matchBit << 8) + context].Encode(rangeEncoder, bit);
    context = (context << 1) | bit;
    if (matchBit != bit)
    {
      while(i != 0)
      {
        i--;
        UInt32 bit = (symbol >> i) & 1;
        _encoders[context].Encode(rangeEncoder, bit);
        context = (context << 1) | bit;
      }
      break;
    }
  }
  while(i != 0);
}

UInt32 CLiteralEncoder2::GetPrice(bool matchMode, Byte matchByte, Byte symbol) const
{
  UInt32 price = 0;
  UInt32 context = 1;
  int i = 8;
  if (matchMode)
  {
    do 
    {
      i--;
      UInt32 matchBit = (matchByte >> i) & 1;
      UInt32 bit = (symbol >> i) & 1;
      price += _encoders[0x100 + (matchBit << 8) + context].GetPrice(bit);
      context = (context << 1) | bit;
      if (matchBit != bit)
        break;
    }
    while (i != 0);
  }
  while(i != 0)
  {
    i--;
    UInt32 bit = (symbol >> i) & 1;
    price += _encoders[context].GetPrice(bit);
    context = (context << 1) | bit;
  }
  return price;
};


namespace NLength {

void CEncoder::Init(UInt32 numPosStates)
{
  _choice.Init();
  _choice2.Init();
  for (UInt32 posState = 0; posState < numPosStates; posState++)
  {
    _lowCoder[posState].Init();
    _midCoder[posState].Init();
  }
  _highCoder.Init();
}

void CEncoder::Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState)
{
  if(symbol < kNumLowSymbols)
  {
    _choice.Encode(rangeEncoder, 0);
    _lowCoder[posState].Encode(rangeEncoder, symbol);
  }
  else
  {
    _choice.Encode(rangeEncoder, 1);
    if(symbol < kNumLowSymbols + kNumMidSymbols)
    {
      _choice2.Encode(rangeEncoder, 0);
      _midCoder[posState].Encode(rangeEncoder, symbol - kNumLowSymbols);
    }
    else
    {
      _choice2.Encode(rangeEncoder, 1);
      _highCoder.Encode(rangeEncoder, symbol - kNumLowSymbols - kNumMidSymbols);
    }
  }
}

void CEncoder::SetPrices(UInt32 posState, UInt32 numSymbols, UInt32 *prices) const
{
  UInt32 a0 = _choice.GetPrice0();
  UInt32 a1 = _choice.GetPrice1();
  UInt32 b0 = a1 + _choice2.GetPrice0();
  UInt32 b1 = a1 + _choice2.GetPrice1();
  UInt32 i = 0;
  for (i = 0; i < kNumLowSymbols; i++)
  {
    if (i >= numSymbols)
      return;
    prices[i] = a0 + _lowCoder[posState].GetPrice(i);
  }
  for (; i < kNumLowSymbols + kNumMidSymbols; i++)
  {
    if (i >= numSymbols)
      return;
    prices[i] = b0 + _midCoder[posState].GetPrice(i - kNumLowSymbols);
  }
  for (; i < numSymbols; i++)
    prices[i] = b1 + _highCoder.GetPrice(i - kNumLowSymbols - kNumMidSymbols);
}

}

CEncoder::CEncoder():
  _numFastBytes(kNumFastBytesDefault),
  _distTableSize(kDefaultDictionaryLogSize * 2),
  _posStateBits(2),
  _posStateMask(4 - 1),
  _numLiteralPosStateBits(0),
  _numLiteralContextBits(3),
  _dictionarySize(1 << kDefaultDictionaryLogSize),
  _matchFinderCycles(0),
  #ifdef COMPRESS_MF_MT
  _multiThread(false),
  #endif
  _writeEndMark(false)
{
  MatchFinder_Construct(&_matchFinderBase);
  // _maxMode = false;
  _fastMode = false;
  #ifdef COMPRESS_MF_MT
  MatchFinderMt_Construct(&_matchFinderMt);
  _matchFinderMt.MatchFinder = &_matchFinderBase;
  #endif
}


static void *SzAlloc(size_t size) { return BigAlloc(size); }
static void SzFree(void *address) { BigFree(address); }
ISzAlloc g_Alloc = { SzAlloc, SzFree };

CEncoder::~CEncoder()
{
  #ifdef COMPRESS_MF_MT
  MatchFinderMt_Destruct(&_matchFinderMt, &g_Alloc);
  #endif
  MatchFinder_Free(&_matchFinderBase, &g_Alloc);
}

static const UInt32 kBigHashDicLimit = (UInt32)1 << 24;

HRESULT CEncoder::Create()
{
  if (!_rangeEncoder.Create(1 << 20))
    return E_OUTOFMEMORY;
  bool btMode = (_matchFinderBase.btMode != 0);
  #ifdef COMPRESS_MF_MT
  _mtMode = (_multiThread && !_fastMode && btMode);
  #endif
  
  if (!_literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits))
    return E_OUTOFMEMORY;

  _matchFinderBase.bigHash = (_dictionarySize > kBigHashDicLimit);

  UInt32 numCycles = 16 + (_numFastBytes >> 1);
  if (!btMode)
    numCycles >>= 1;
  if (_matchFinderCycles != 0)
    numCycles = _matchFinderCycles;
  _matchFinderBase.cutValue = numCycles;
  #ifdef COMPRESS_MF_MT
  if (_mtMode)
  {
    RINOK(MatchFinderMt_Create(&_matchFinderMt, _dictionarySize, kNumOpts, _numFastBytes, kMatchMaxLen, &g_Alloc));
    _matchFinderObj = &_matchFinderMt;
    MatchFinderMt_CreateVTable(&_matchFinderMt, &_matchFinder);
  }
  else
  #endif
  {
    if (!MatchFinder_Create(&_matchFinderBase, _dictionarySize, kNumOpts, _numFastBytes, kMatchMaxLen, &g_Alloc))
      return E_OUTOFMEMORY;
    _matchFinderObj = &_matchFinderBase;
    MatchFinder_CreateVTable(&_matchFinderBase, &_matchFinder);
  }
  return S_OK;
}

inline wchar_t GetUpperChar(wchar_t c)
{
  if (c >= 'a' && c <= 'z')
    c -= 0x20;
  return c;
}

static int ParseMatchFinder(const wchar_t *s, int *btMode, UInt32 *numHashBytes /* , int *skipModeBits */)
{
  wchar_t c = GetUpperChar(*s++);
  if (c == L'H')
  {
    if (GetUpperChar(*s++) != L'C')
      return 0;
    int numHashBytesLoc = (int)(*s++ - L'0');
    if (numHashBytesLoc < 4 || numHashBytesLoc > 4)
      return 0;
    if (*s++ != 0)
      return 0;
    *btMode = 0;
    *numHashBytes = numHashBytesLoc;
    return 1;
  }
  if (c != L'B')
    return 0;

  if (GetUpperChar(*s++) != L'T')
    return 0;
  int numHashBytesLoc = (int)(*s++ - L'0');
  if (numHashBytesLoc < 2 || numHashBytesLoc > 4)
    return 0;
  c = GetUpperChar(*s++);
  /*
  int skipModeBitsLoc = 0;
  if (c == L'D')
  {
    skipModeBitsLoc = 2;
    c = GetUpperChar(*s++);
  }
  */
  if (c != L'\0')
    return 0;
  *btMode = 1;
  *numHashBytes = numHashBytesLoc;
  // *skipModeBits = skipModeBitsLoc;
  return 1;
}

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 < 5 || numFastBytes > kMatchMaxLen)
          return E_INVALIDARG;
        _numFastBytes = numFastBytes;
        break;
      }
      case NCoderPropID::kMatchFinderCycles:
      {
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        _matchFinderCycles = prop.ulVal;
        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;
        if (!ParseMatchFinder(prop.bstrVal, &_matchFinderBase.btMode, &_matchFinderBase.numHashBytes /* , &_matchFinderBase.skipModeBits */))
          return E_INVALIDARG;
        break;
      }
      case NCoderPropID::kMultiThread:
      {
        if (prop.vt != VT_BOOL)
          return E_INVALIDARG;
        #ifdef COMPRESS_MF_MT
        Bool newMultiThread = (prop.boolVal == VARIANT_TRUE);
        if (newMultiThread != _multiThread)
        {
          ReleaseMatchFinder();
          _multiThread = newMultiThread;
        }
        #endif
        break;
      }
      case NCoderPropID::kNumThreads:
      {
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        #ifdef COMPRESS_MF_MT
        Bool newMultiThread = (prop.ulVal > 1) ? True : False;
        if (newMultiThread != _multiThread)
        {
          ReleaseMatchFinder();
          _multiThread = newMultiThread;
        }
        #endif
        break;
      }