lzmaencoder.cpp

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

    MovePos(lenMain - 1);
    return lenMain;
  }

  UInt32 backMain = 0; // for GCC
  if (lenMain >= 2)
  {
    backMain = matchDistances[numDistancePairs - 1];
    while (numDistancePairs > 2 && lenMain == matchDistances[numDistancePairs - 4] + 1)
    {
      if (!ChangePair(matchDistances[numDistancePairs - 3], backMain))
        break;
      numDistancePairs -= 2;
      lenMain = matchDistances[numDistancePairs - 2];
      backMain = matchDistances[numDistancePairs - 1];
    }
    if (lenMain == 2 && backMain >= 0x80)
      lenMain = 1;
  }

  if (repLens[repMaxIndex] >= 2)
  {
    if (repLens[repMaxIndex] + 1 >= lenMain || 
        repLens[repMaxIndex] + 2 >= lenMain && (backMain > (1 << 9)) ||
        repLens[repMaxIndex] + 3 >= lenMain && (backMain > (1 << 15)))
    {
      backRes = repMaxIndex;
      UInt32 lenRes = repLens[repMaxIndex];
      MovePos(lenRes - 1);
      return lenRes;
    }
  }
  
  if (lenMain >= 2 && numAvailableBytes > 2)
  {
    numAvailableBytes = _matchFinder.GetNumAvailableBytes(_matchFinderObj);
    _longestMatchLength = ReadMatchDistances(_numDistancePairs);
    if (_longestMatchLength >= 2)
    {
      UInt32 newDistance = matchDistances[_numDistancePairs - 1];
      if (_longestMatchLength >= lenMain && newDistance < backMain || 
          _longestMatchLength == lenMain + 1 && !ChangePair(backMain, newDistance) ||
          _longestMatchLength > lenMain + 1 ||
          _longestMatchLength + 1 >= lenMain && lenMain >= 3 && ChangePair(newDistance, backMain))
      {
        _longestMatchWasFound = true;
        backRes = UInt32(-1);
        return 1;
      }
    }
    data = _matchFinder.GetPointerToCurrentPos(_matchFinderObj) - 1;
    for(UInt32 i = 0; i < kNumRepDistances; i++)
    {
      const Byte *data2 = data - (_repDistances[i] + 1);
      if (data[1] != data2[1] || data[2] != data2[2])
      {
        repLens[i] = 0;
        continue;
      }
      UInt32 len;
      for (len = 2; len < numAvailableBytes && data[len] == data2[len]; len++);
      if (len + 1 >= lenMain)
      {
        _longestMatchWasFound = true;
        backRes = UInt32(-1);
        return 1;
      }
    }
    backRes = backMain + kNumRepDistances; 
    MovePos(lenMain - 2);
    return lenMain;
  }
  backRes = UInt32(-1);
  return 1;
}

HRESULT CEncoder::Flush(UInt32 nowPos)
{
  // ReleaseMFStream();
  if (_matchFinderBase.result != SZ_OK)
    return _matchFinderBase.result;
  WriteEndMarker(nowPos & _posStateMask);
  _rangeEncoder.FlushData();
  return _rangeEncoder.FlushStream();
}

void CEncoder::WriteEndMarker(UInt32 posState)
{
  // This function for writing End Mark for stream version of LZMA. 
  // In current version this feature is not used.
  if (!_writeEndMark)
    return;

  _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1);
  _isRep[_state.Index].Encode(&_rangeEncoder, 0);
  _state.UpdateMatch();
  UInt32 len = kMatchMinLen; // kMatchMaxLen;
  _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode);
  UInt32 posSlot = (1 << kNumPosSlotBits)  - 1;
  UInt32 lenToPosState = GetLenToPosState(len);
  _posSlotEncoder[lenToPosState].Encode(&_rangeEncoder, posSlot);
  UInt32 footerBits = 30;
  UInt32 posReduced = (UInt32(1) << footerBits) - 1;
  _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
  _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask);
}

HRESULT CEncoder::CodeReal(ISequentialInStream *inStream,
      ISequentialOutStream *outStream, 
      const UInt64 *inSize, const UInt64 *outSize,
      ICompressProgressInfo *progress)
{
  // _needReleaseMFStream = false;
  #ifdef COMPRESS_MF_MT
  #ifdef USE_ALLOCA
  alloca(0x300);
  #endif
  #endif
  CCoderReleaser coderReleaser(this);
  RINOK(SetStreams(inStream, outStream, inSize, outSize));
  for (;;)
  {
    UInt64 processedInSize;
    UInt64 processedOutSize;
    Int32 finished;
    RINOK(CodeOneBlock(&processedInSize, &processedOutSize, &finished));
    if (finished != 0)
      break;
    if (progress != 0)
    {
      RINOK(progress->SetRatioInfo(&processedInSize, &processedOutSize));
    }
  }
  return S_OK;
}

HRESULT CEncoder::SetStreams(ISequentialInStream *inStream,
      ISequentialOutStream *outStream, 
      const UInt64 * /* inSize */, const UInt64 * /* outSize */)
{
  _inStream = inStream;
  _finished = false;
  RINOK(Create());
  RINOK(SetOutStream(outStream));
  RINOK(Init());
  
  if (!_fastMode)
  {
    FillDistancesPrices();
    FillAlignPrices();
  }

  _lenEncoder.SetTableSize(_numFastBytes + 1 - kMatchMinLen);
  _lenEncoder.UpdateTables(1 << _posStateBits);
  _repMatchLenEncoder.SetTableSize(_numFastBytes + 1 - kMatchMinLen);
  _repMatchLenEncoder.UpdateTables(1 << _posStateBits);

  nowPos64 = 0;
  return S_OK;
}

static HRes MyRead(void *object, void *data, UInt32 size, UInt32 *processedSize)
{
  return (HRes)((CSeqInStream *)object)->RealStream->Read(data, size, processedSize);
}

HRESULT CEncoder::CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished)
{
  if (_inStream != 0)
  {
    _seqInStream.RealStream = _inStream;
    _seqInStream.SeqInStream.Read = MyRead;
    _matchFinderBase.stream = &_seqInStream.SeqInStream;
    _matchFinder.Init(_matchFinderObj);
    _needReleaseMFStream = true;
    _inStream = 0;
  }


  *finished = 1;
  if (_finished)
    return _matchFinderBase.result;
  _finished = true;

  if (nowPos64 == 0)
  {
    if (_matchFinder.GetNumAvailableBytes(_matchFinderObj) == 0)
      return Flush((UInt32)nowPos64);
    UInt32 len, numDistancePairs;
    len = ReadMatchDistances(numDistancePairs);
    UInt32 posState = UInt32(nowPos64) & _posStateMask;
    _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0);
    _state.UpdateChar();
    Byte curByte = _matchFinder.GetIndexByte(_matchFinderObj, 0 - _additionalOffset);
    _literalEncoder.GetSubCoder(UInt32(nowPos64), _previousByte)->Encode(&_rangeEncoder, curByte);
    _previousByte = curByte;
    _additionalOffset--;
    nowPos64++;
  }

  UInt32 nowPos32 = (UInt32)nowPos64;
  UInt32 progressPosValuePrev = nowPos32;

  if (_matchFinder.GetNumAvailableBytes(_matchFinderObj) == 0)
    return Flush(nowPos32);

  for (;;)
  {
    #ifdef _NO_EXCEPTIONS
    if (_rangeEncoder.Stream.ErrorCode != S_OK)
      return _rangeEncoder.Stream.ErrorCode;
    #endif
    UInt32 pos, len;

    if (_fastMode)
      len = GetOptimumFast(pos);
    else
      len = GetOptimum(nowPos32, pos);

    UInt32 posState = nowPos32 & _posStateMask;
    if(len == 1 && pos == 0xFFFFFFFF)
    {
      _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0);
      Byte curByte = _matchFinder.GetIndexByte(_matchFinderObj, 0 - _additionalOffset);
      CLiteralEncoder2 *subCoder = _literalEncoder.GetSubCoder(nowPos32, _previousByte);
      if(_state.IsCharState())
        subCoder->Encode(&_rangeEncoder, curByte);
      else
      {
        Byte matchByte = _matchFinder.GetIndexByte(_matchFinderObj, 0 - _repDistances[0] - 1 - _additionalOffset);
        subCoder->EncodeMatched(&_rangeEncoder, matchByte, curByte);
      }
      _state.UpdateChar();
      _previousByte = curByte;
    }
    else
    {
      _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1);
      if(pos < kNumRepDistances)
      {
        _isRep[_state.Index].Encode(&_rangeEncoder, 1);
        if(pos == 0)
        {
          _isRepG0[_state.Index].Encode(&_rangeEncoder, 0);
          _isRep0Long[_state.Index][posState].Encode(&_rangeEncoder, ((len == 1) ? 0 : 1));
        }
        else
        {
          UInt32 distance = _repDistances[pos];
          _isRepG0[_state.Index].Encode(&_rangeEncoder, 1);
          if (pos == 1)
            _isRepG1[_state.Index].Encode(&_rangeEncoder, 0);
          else
          {
            _isRepG1[_state.Index].Encode(&_rangeEncoder, 1);
            _isRepG2[_state.Index].Encode(&_rangeEncoder, pos - 2);
            if (pos == 3)
              _repDistances[3] = _repDistances[2];
            _repDistances[2] = _repDistances[1];
          }
          _repDistances[1] = _repDistances[0];
          _repDistances[0] = distance;
        }
        if (len == 1)
          _state.UpdateShortRep();
        else
        {
          _repMatchLenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode);
          _state.UpdateRep();
        }
      }
      else
      {
        _isRep[_state.Index].Encode(&_rangeEncoder, 0);
        _state.UpdateMatch();
        _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode);
        pos -= kNumRepDistances;
        UInt32 posSlot = GetPosSlot(pos);
        _posSlotEncoder[GetLenToPosState(len)].Encode(&_rangeEncoder, posSlot);
        
        if (posSlot >= kStartPosModelIndex)
        {
          UInt32 footerBits = ((posSlot >> 1) - 1);
          UInt32 base = ((2 | (posSlot & 1)) << footerBits);
          UInt32 posReduced = pos - base;

          if (posSlot < kEndPosModelIndex)
            NRangeCoder::ReverseBitTreeEncode(_posEncoders + base - posSlot - 1, 
                &_rangeEncoder, footerBits, posReduced);
          else
          {
            _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
            _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask);
            _alignPriceCount++;
          }
        }
        _repDistances[3] = _repDistances[2];
        _repDistances[2] = _repDistances[1];
        _repDistances[1] = _repDistances[0];
        _repDistances[0] = pos;
        _matchPriceCount++;
      }
      _previousByte = _matchFinder.GetIndexByte(_matchFinderObj, len - 1 - _additionalOffset);
    }
    _additionalOffset -= len;
    nowPos32 += len;
    if (_additionalOffset == 0)
    {
      if (!_fastMode)
      {
        if (_matchPriceCount >= (1 << 7))
          FillDistancesPrices();
        if (_alignPriceCount >= kAlignTableSize)
          FillAlignPrices();
      }
      if (_matchFinder.GetNumAvailableBytes(_matchFinderObj) == 0)
        return Flush(nowPos32);
      if (nowPos32 - progressPosValuePrev >= (1 << 14))
      {
        nowPos64 += nowPos32 - progressPosValuePrev;
        *inSize = nowPos64;
        *outSize = _rangeEncoder.GetProcessedSize();
        _finished = false;
        *finished = 0;
        return _matchFinderBase.result;
      }
    }
  }
}

STDMETHODIMP CEncoder::Code(ISequentialInStream *inStream,
    ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize,
    ICompressProgressInfo *progress)
{
  #ifndef _NO_EXCEPTIONS
  try 
  { 
  #endif
    return CodeReal(inStream, outStream, inSize, outSize, progress); 
  #ifndef _NO_EXCEPTIONS
  }
  catch(const COutBufferException &e) { return e.ErrorCode; }
  catch(...) { return E_FAIL; }
  #endif
}
  
void CEncoder::FillDistancesPrices()
{
  UInt32 tempPrices[kNumFullDistances];
  for (UInt32 i = kStartPosModelIndex; i < kNumFullDistances; i++)
  { 
    UInt32 posSlot = GetPosSlot(i);
    UInt32 footerBits = ((posSlot >> 1) - 1);
    UInt32 base = ((2 | (posSlot & 1)) << footerBits);
    tempPrices[i] = NRangeCoder::ReverseBitTreeGetPrice(_posEncoders + 
      base - posSlot - 1, footerBits, i - base);
  }

  for (UInt32 lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
  {
    UInt32 posSlot;
    NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumPosSlotBits> &encoder = _posSlotEncoder[lenToPosState];
    UInt32 *posSlotPrices = _posSlotPrices[lenToPosState];
    for (posSlot = 0; posSlot < _distTableSize; posSlot++)
      posSlotPrices[posSlot] = encoder.GetPrice(posSlot);
    for (posSlot = kEndPosModelIndex; posSlot < _distTableSize; posSlot++)
      posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << NRangeCoder::kNumBitPriceShiftBits);

    UInt32 *distancesPrices = _distancesPrices[lenToPosState];
    UInt32 i;
    for (i = 0; i < kStartPosModelIndex; i++)
      distancesPrices[i] = posSlotPrices[i];
    for (; i < kNumFullDistances; i++)
      distancesPrices[i] = posSlotPrices[GetPosSlot(i)] + tempPrices[i];
  }
  _matchPriceCount = 0;
}

void CEncoder::FillAlignPrices()
{
  for (UInt32 i = 0; i < kAlignTableSize; i++)
    _alignPrices[i] = _posAlignEncoder.ReverseGetPrice(i);
  _alignPriceCount = 0;
}

}}