lzmaencoder.cpp

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

      case NCoderPropID::kDictionarySize:
      {
        const int kDicLogSizeMaxCompress = 30; // must be <= ((kNumLogBits - 1) * 2) + 7 = 31;
        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 < (UInt32)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 > (UInt32)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 > (UInt32)kNumLitPosStatesBitsEncodingMax)
          return E_INVALIDARG;
        _numLiteralPosStateBits = value;
        break;
      }
      case NCoderPropID::kLitContextBits:
      {
        if (prop.vt != VT_UI4)
          return E_INVALIDARG;
        UInt32 value = prop.ulVal;
        if (value > (UInt32)kNumLitContextBitsMax)
          return E_INVALIDARG;
        _numLiteralContextBits = value;
        break;
      }
      case NCoderPropID::kEndMarker:
      {
        if (prop.vt != VT_BOOL)
          return E_INVALIDARG;
        SetWriteEndMarkerMode(prop.boolVal == VARIANT_TRUE);
        break;
      }
      default:
        return E_INVALIDARG;
    }
  }
  return S_OK;
}

STDMETHODIMP CEncoder::WriteCoderProperties(ISequentialOutStream *outStream)
{ 
  const UInt32 kPropSize = 5;
  Byte properties[kPropSize];
  properties[0] = (Byte)((_posStateBits * 5 + _numLiteralPosStateBits) * 9 + _numLiteralContextBits);
  for (int i = 0; i < 4; i++)
    properties[1 + i] = Byte(_dictionarySize >> (8 * i));
  return WriteStream(outStream, properties, kPropSize, NULL);
}

STDMETHODIMP CEncoder::SetOutStream(ISequentialOutStream *outStream)
{
  _rangeEncoder.SetStream(outStream);
  return S_OK;
}

STDMETHODIMP CEncoder::ReleaseOutStream()
{
  _rangeEncoder.ReleaseStream();
  return S_OK;
}

HRESULT CEncoder::Init()
{
  CBaseState::Init();

  _rangeEncoder.Init();

  for(int i = 0; i < kNumStates; i++)
  {
    for (UInt32 j = 0; j <= _posStateMask; j++)
    {
      _isMatch[i][j].Init();
      _isRep0Long[i][j].Init();
    }
    _isRep[i].Init();
    _isRepG0[i].Init();
    _isRepG1[i].Init();
    _isRepG2[i].Init();
  }

  _literalEncoder.Init();

  {
    for(UInt32 i = 0; i < kNumLenToPosStates; i++)
      _posSlotEncoder[i].Init();
  }
  {
    for(UInt32 i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)
      _posEncoders[i].Init();
  }

  _lenEncoder.Init(1 << _posStateBits);
  _repMatchLenEncoder.Init(1 << _posStateBits);

  _posAlignEncoder.Init();

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

  return S_OK;
}

#ifdef SHOW_STAT
static int ttt = 0;
#endif

void CEncoder::MovePos(UInt32 num)
{
  #ifdef SHOW_STAT
  ttt += num;
  printf("\n MovePos %d", num);
  #endif
  if (num != 0)
  {
    _additionalOffset += num;
    _matchFinder.Skip(_matchFinderObj, num);
  }
}

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

/*
Out:
  (lenRes == 1) && (backRes == 0xFFFFFFFF) means Literal
*/

UInt32 CEncoder::GetOptimum(UInt32 position, UInt32 &backRes)
{
  if(_optimumEndIndex != _optimumCurrentIndex)
  {
    const COptimal &optimum = _optimum[_optimumCurrentIndex];
    UInt32 lenRes = optimum.PosPrev - _optimumCurrentIndex;
    backRes = optimum.BackPrev;
    _optimumCurrentIndex = optimum.PosPrev;
    return lenRes;
  }
  _optimumCurrentIndex = _optimumEndIndex = 0;
  
  UInt32 numAvailableBytes = _matchFinder.GetNumAvailableBytes(_matchFinderObj);

  UInt32 lenMain, numDistancePairs;
  if (!_longestMatchWasFound)
  {
    lenMain = ReadMatchDistances(numDistancePairs);
  }
  else
  {
    lenMain = _longestMatchLength;
    numDistancePairs = _numDistancePairs;
    _longestMatchWasFound = false;
  }

  const Byte *data = _matchFinder.GetPointerToCurrentPos(_matchFinderObj) - 1;
  if (numAvailableBytes < 2)
  {
    backRes = (UInt32)(-1);
    return 1;
  }
  if (numAvailableBytes > kMatchMaxLen)
    numAvailableBytes = kMatchMaxLen;

  UInt32 reps[kNumRepDistances];
  UInt32 repLens[kNumRepDistances];
  UInt32 repMaxIndex = 0;
  UInt32 i;
  for(i = 0; i < kNumRepDistances; i++)
  {
    reps[i] = _repDistances[i];
    const Byte *data2 = data - (reps[i] + 1);
    if (data[0] != data2[0] || data[1] != data2[1])
    {
      repLens[i] = 0;
      continue;
    }
    UInt32 lenTest;
    for (lenTest = 2; lenTest < numAvailableBytes && data[lenTest] == data2[lenTest]; lenTest++);
    repLens[i] = lenTest;
    if (lenTest > repLens[repMaxIndex])
      repMaxIndex = i;
  }
  if(repLens[repMaxIndex] >= _numFastBytes)
  {
    backRes = repMaxIndex;
    UInt32 lenRes = repLens[repMaxIndex];
    MovePos(lenRes - 1);
    return lenRes;
  }

  UInt32 *matchDistances = _matchDistances;
  if(lenMain >= _numFastBytes)
  {
    backRes = matchDistances[numDistancePairs - 1] + kNumRepDistances; 
    MovePos(lenMain - 1);
    return lenMain;
  }
  Byte currentByte = *data;
  Byte matchByte = *(data - (reps[0] + 1));

  if(lenMain < 2 && currentByte != matchByte && repLens[repMaxIndex] < 2)
  {
    backRes = (UInt32)-1;
    return 1;
  }

  _optimum[0].State = _state;

  UInt32 posState = (position & _posStateMask);

  _optimum[1].Price = _isMatch[_state.Index][posState].GetPrice0() + 
      _literalEncoder.GetSubCoder(position, _previousByte)->GetPrice(!_state.IsCharState(), matchByte, currentByte);
  _optimum[1].MakeAsChar();

  UInt32 matchPrice = _isMatch[_state.Index][posState].GetPrice1();
  UInt32 repMatchPrice = matchPrice + _isRep[_state.Index].GetPrice1();

  if(matchByte == currentByte)
  {
    UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);
    if(shortRepPrice < _optimum[1].Price)
    {
      _optimum[1].Price = shortRepPrice;
      _optimum[1].MakeAsShortRep();
    }
  }
  UInt32 lenEnd = ((lenMain >= repLens[repMaxIndex]) ? lenMain : repLens[repMaxIndex]);

  if(lenEnd < 2)
  {
    backRes = _optimum[1].BackPrev;
    return 1;
  }

  _optimum[1].PosPrev = 0;
  for (i = 0; i < kNumRepDistances; i++)
    _optimum[0].Backs[i] = reps[i];

  UInt32 len = lenEnd;
  do
    _optimum[len--].Price = kIfinityPrice;
  while (len >= 2);

  for(i = 0; i < kNumRepDistances; i++)
  {
    UInt32 repLen = repLens[i];
    if (repLen < 2)
      continue;
    UInt32 price = repMatchPrice + GetPureRepPrice(i, _state, posState);
    do
    {
      UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(repLen - 2, posState);
      COptimal &optimum = _optimum[repLen];
      if (curAndLenPrice < optimum.Price) 
      {
        optimum.Price = curAndLenPrice;
        optimum.PosPrev = 0;
        optimum.BackPrev = i;
        optimum.Prev1IsChar = false;
      }
    }
    while(--repLen >= 2);
  }

  UInt32 normalMatchPrice = matchPrice + _isRep[_state.Index].GetPrice0();

  len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);
  if (len <= lenMain)
  {
    UInt32 offs = 0;
    while (len > matchDistances[offs])
      offs += 2;
    for(; ; len++)
    {
      UInt32 distance = matchDistances[offs + 1];
      UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(distance, len, posState);
      COptimal &optimum = _optimum[len];
      if (curAndLenPrice < optimum.Price) 
      {
        optimum.Price = curAndLenPrice;
        optimum.PosPrev = 0;
        optimum.BackPrev = distance + kNumRepDistances;
        optimum.Prev1IsChar = false;
      }
      if (len == matchDistances[offs])
      {
        offs += 2;
        if (offs == numDistancePairs)
          break;
      }
    }
  }

  UInt32 cur = 0;

  for (;;)
  {
    cur++;
    if(cur == lenEnd)
    {
      return Backward(backRes, cur);
    }
    UInt32 numAvailableBytesFull = _matchFinder.GetNumAvailableBytes(_matchFinderObj);
    UInt32 newLen, numDistancePairs;
    newLen = ReadMatchDistances(numDistancePairs);
    if(newLen >= _numFastBytes)
    {
      _numDistancePairs = numDistancePairs;
      _longestMatchLength = newLen;
      _longestMatchWasFound = true;
      return Backward(backRes, cur);
    }
    position++;
    COptimal &curOptimum = _optimum[cur];
    UInt32 posPrev = curOptimum.PosPrev;
    CState state;
    if (curOptimum.Prev1IsChar)
    {
      posPrev--;
      if (curOptimum.Prev2)
      {
        state = _optimum[curOptimum.PosPrev2].State;
        if (curOptimum.BackPrev2 < kNumRepDistances)
          state.UpdateRep();
        else
          state.UpdateMatch();
      }
      else
        state = _optimum[posPrev].State;
      state.UpdateChar();
    }
    else