lzmaencoder.cpp

nsis是一个流传比较广的程序安装和解安装封装软件

        if (curBack < kNumFullDistances)
          curAndLenPrice += _distancesPrices[lenToPosState][curBack];
        else
          curAndLenPrice += _posSlotPrices[lenToPosState][posSlot] + _alignPrices[curBack & kAlignMask];
  
        curAndLenPrice += _lenEncoder.GetPrice(lenTest - kMatchMinLen, posState);
        
        COptimal &optimum = _optimum[cur + lenTest];
        if (curAndLenPrice < optimum.Price) 
        {
          optimum.Price = curAndLenPrice;
          optimum.PosPrev = cur;
          optimum.BackPrev = curBack + kNumRepDistances;
          optimum.Prev1IsChar = false;
        }

        if (/*_maxMode && */lenTest == matchDistances[offs])
        {
          // Try Match + Literal + Rep0
          UInt32 backOffset = curBack + 1;
          UInt32 lenTest2 = lenTest + 1;
          UInt32 limit = MyMin(numAvailableBytesFull, lenTest2 + _numFastBytes);
          for (; lenTest2 < limit && 
              data[lenTest2] == data[(size_t)lenTest2 - backOffset]; lenTest2++);
          lenTest2 -= lenTest + 1;
          if (lenTest2 >= 2)
          {
            CState state2 = state;
            state2.UpdateMatch();
            UInt32 posStateNext = (position + lenTest) & _posStateMask;
            UInt32 curAndLenCharPrice = curAndLenPrice + 
                _isMatch[state2.Index][posStateNext].GetPrice0() +
                _literalEncoder.GetSubCoder(position + lenTest, data[(size_t)lenTest - 1])->GetPrice( 
                true, data[(size_t)lenTest - backOffset], data[lenTest]);
            state2.UpdateChar();
            posStateNext = (posStateNext + 1) & _posStateMask;
            UInt32 nextRepMatchPrice = curAndLenCharPrice + 
                _isMatch[state2.Index][posStateNext].GetPrice1() +
                _isRep[state2.Index].GetPrice1();
            
            // for(; lenTest2 >= 2; lenTest2--)
            {
              UInt32 offset = cur + lenTest + 1 + lenTest2;
              while(lenEnd < offset)
                _optimum[++lenEnd].Price = kIfinityPrice;
              UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(0, lenTest2, state2, posStateNext);
              COptimal &optimum = _optimum[offset];
              if (curAndLenPrice < optimum.Price) 
              {
                optimum.Price = curAndLenPrice;
                optimum.PosPrev = cur + lenTest + 1;
                optimum.BackPrev = 0;
                optimum.Prev1IsChar = true;
                optimum.Prev2 = true;
                optimum.PosPrev2 = cur;
                optimum.BackPrev2 = curBack + kNumRepDistances;
              }
            }
          }
          offs += 2;
          if (offs == numDistancePairs)
            break;
          curBack = matchDistances[offs + 1];
          if (curBack >= kNumFullDistances)
            posSlot = GetPosSlot2(curBack);
        }
      }
    }
  }
}

static inline bool ChangePair(UInt32 smallDist, UInt32 bigDist)
{
  return ((bigDist >> 7) > smallDist);
}


HRESULT CEncoder::ReadMatchDistances(UInt32 &lenRes, UInt32 &numDistancePairs)
{
  lenRes = 0;
  RINOK(_matchFinder->GetMatches(_matchDistances));
  numDistancePairs = _matchDistances[0];
  if (numDistancePairs > 0)
  {
    lenRes = _matchDistances[1 + numDistancePairs - 2];
    if (lenRes == _numFastBytes)
      lenRes += _matchFinder->GetMatchLen(lenRes - 1, _matchDistances[1 + numDistancePairs - 1], 
          kMatchMaxLen - lenRes);
  }
  _additionalOffset++;
  return S_OK;
}

HRESULT CEncoder::GetOptimumFast(UInt32 position, UInt32 &backRes, UInt32 &lenRes)
{
  UInt32 lenMain, numDistancePairs;
  if (!_longestMatchWasFound)
  {
    RINOK(ReadMatchDistances(lenMain, numDistancePairs));
  }
  else
  {
    lenMain = _longestMatchLength;
    numDistancePairs = _numDistancePairs;
    _longestMatchWasFound = false;
  }

  const Byte *data = _matchFinder->GetPointerToCurrentPos() - 1;
  UInt32 numAvailableBytes = _matchFinder->GetNumAvailableBytes() + 1;
  if (numAvailableBytes > kMatchMaxLen)
    numAvailableBytes = kMatchMaxLen;
  if (numAvailableBytes < 2)
  {
    backRes = (UInt32)(-1);
    lenRes = 1;
    return S_OK;
  }

  UInt32 repLens[kNumRepDistances];
  UInt32 repMaxIndex = 0;

  for(UInt32 i = 0; i < kNumRepDistances; i++)
  {
    UInt32 backOffset = _repDistances[i] + 1;
    if (data[0] != data[(size_t)0 - backOffset] || data[1] != data[(size_t)1 - backOffset])
    {
      repLens[i] = 0;
      continue;
    }
    UInt32 len;
    for (len = 2; len < numAvailableBytes && data[len] == data[(size_t)len - backOffset]; len++);
    if(len >= _numFastBytes)
    {
      backRes = i;
      lenRes = len;
      return MovePos(lenRes - 1);
    }
    repLens[i] = len;
    if (len > repLens[repMaxIndex])
      repMaxIndex = i;
  }
  UInt32 *matchDistances = _matchDistances + 1;
  if(lenMain >= _numFastBytes)
  {
    backRes = matchDistances[numDistancePairs - 1] + kNumRepDistances; 
    lenRes = lenMain;
    return MovePos(lenMain - 1);
  }

  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;
      lenRes = repLens[repMaxIndex];
      return MovePos(lenRes - 1);
    }
  }
  
  if (lenMain >= 2 && numAvailableBytes > 2)
  {
    RINOK(ReadMatchDistances(_longestMatchLength, _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);
        lenRes = 1;
        return S_OK;
      }
    }
    data++;
    numAvailableBytes--;
    for(UInt32 i = 0; i < kNumRepDistances; i++)
    {
      UInt32 backOffset = _repDistances[i] + 1;
      if (data[1] != data[(size_t)1 - backOffset] || data[2] != data[(size_t)2 - backOffset])
      {
        repLens[i] = 0;
        continue;
      }
      UInt32 len;
      for (len = 2; len < numAvailableBytes && data[len] == data[(size_t)len - backOffset]; len++);
      if (len + 1 >= lenMain)
      {
        _longestMatchWasFound = true;
        backRes = UInt32(-1);
        lenRes = 1;
        return S_OK;
      }
    }
    backRes = backMain + kNumRepDistances; 
    lenRes = lenMain;
    return MovePos(lenMain - 2);
  }
  backRes = UInt32(-1);
  lenRes = 1;
  return S_OK;
}

HRESULT CEncoder::Flush(UInt32 nowPos)
{
  ReleaseMFStream();
  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;
  CCoderReleaser coderReleaser(this);
  RINOK(SetStreams(inStream, outStream, inSize, outSize));
  while(true)
  {
    UInt64 processedInSize;
    UInt64 processedOutSize;
    Int32 finished;
    RINOK(CodeOneBlock(&processedInSize, &processedOutSize, &finished));
    if (finished != 0)
      return S_OK;
    if (progress != 0)
    {
      RINOK(progress->SetRatioInfo(&processedInSize, &processedOutSize));
    }
  }
}

HRESULT CEncoder::SetStreams(ISequentialInStream *inStream,
      ISequentialOutStream *outStream, 
      const UInt64 *inSize, const UInt64 *outSize)
{
  _inStream = inStream;
  _finished = false;
  RINOK(Create());
  RINOK(SetOutStream(outStream));
  RINOK(Init());
  
  // CCoderReleaser releaser(this);

  /*
  if (_matchFinder->GetNumAvailableBytes() == 0)
    return Flush();
  */

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

HRESULT CEncoder::CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished)
{
  if (_inStream != 0)
  {
    RINOK(_matchFinder->SetStream(_inStream));
    RINOK(_matchFinder->Init());
    _needReleaseMFStream = true;
    _inStream = 0;
  }


  *finished = 1;
  if (_finished)
    return S_OK;
  _finished = true;

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

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

  if (_matchFinder->GetNumAvailableBytes() == 0)
    return Flush(nowPos32);

  while(true)
  {
    #ifdef _NO_EXCEPTIONS
    if (_rangeEncoder.Stream.ErrorCode != S_OK)
      return _rangeEncoder.Stream.ErrorCode;
    #endif
    UInt32 pos, len;
    HRESULT result;
    if (_fastMode)
      result = GetOptimumFast(nowPos32, pos, len);
    else
      result = GetOptimum(nowPos32, pos, len);
    RINOK(result);

    UInt32 posState = nowPos32 & _posStateMask;
    if(len == 1 && pos == 0xFFFFFFFF)
    {
      _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0);
      Byte curByte = _matchFinder->GetIndexByte(0 - _additionalOffset);
      CLiteralEncoder2 *subCoder = _literalEncoder.GetSubCoder(nowPos32, _previousByte);
      if(_state.IsCharState())
        subCoder->Encode(&_rangeEncoder, curByte);
      else
      {
        Byte matchByte = _matchFinder->GetIndexByte(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(len - 1 - _additionalOffset);
    }
    _additionalOffset -= len;
    nowPos32 += len;
    if (_additionalOffset == 0)
    {
      if (!_fastMode)
      {
        if (_matchPriceCount >= (1 << 7))
          FillDistancesPrices();
        if (_alignPriceCount >= kAlignTableSize)
          FillAlignPrices();
      }
      if (_matchFinder->GetNumAvailableBytes() == 0)
        return Flush(nowPos32);
      if (nowPos32 - progressPosValuePrev >= (1 << 14))
      {
        nowPos64 += nowPos32 - progressPosValuePrev;
        *inSize = nowPos64;
        *outSize = _rangeEncoder.GetProcessedSize();
        _finished = false;
        *finished = 0;
        return S_OK;
      }
    }
  }
}

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

}}