lzmaencoder.cpp

7-Zip 3.11的源码

              while(lenEnd < cur + offset)
                _optimum[++lenEnd].Price = kIfinityPrice;
              UINT32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(
                  0, lenTest2, state2, posStateNext);
              COptimal &optimum = _optimum[cur + 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;
              }
            }
          }
        }
      }
    }
  }
}

static inline bool ChangePair(UINT32 smallDist, UINT32 bigDist)
{
  const int kDif = 7;
  return (smallDist < (UINT32(1) << (32-kDif)) && bigDist >= (smallDist << kDif));
}


UINT32 CEncoder::GetOptimumFast(UINT32 &backRes, UINT32 position)
{
  UINT32 lenMain;
  if (!_longestMatchWasFound)
    lenMain = ReadMatchDistances();
  else
  {
    lenMain = _longestMatchLength;
    _longestMatchWasFound = false;
  }
  UINT32 repLens[kNumRepDistances];
  UINT32 repMaxIndex = 0;
  for(int i = 0; i < kNumRepDistances; i++)
  {
    repLens[i] = _matchFinder->GetMatchLen(0 - 1, _repDistances[i], kMatchMaxLen);
    if (i == 0 || repLens[i] > repLens[repMaxIndex])
      repMaxIndex = i;
  }
  if(repLens[repMaxIndex] >= _numFastBytes)
  {
    backRes = repMaxIndex;
    MovePos(repLens[repMaxIndex] - 1);
    return repLens[repMaxIndex];
  }
  if(lenMain >= _numFastBytes)
  {
    backRes = _matchDistances[_numFastBytes] + kNumRepDistances; 
    MovePos(lenMain - 1);
    return lenMain;
  }
  while (lenMain > 2)
  {
    if (!ChangePair(_matchDistances[lenMain - 1], _matchDistances[lenMain]))
      break;
    lenMain--;
  }
  if (lenMain == 2 && _matchDistances[2] >= 0x80)
    lenMain = 1;

  UINT32 backMain = _matchDistances[lenMain];
  if (repLens[repMaxIndex] >= 2)
  {
    if (repLens[repMaxIndex] + 1 >= lenMain || 
        repLens[repMaxIndex] + 2 >= lenMain && (backMain > (1<<12)))
    {
      backRes = repMaxIndex;
      MovePos(repLens[repMaxIndex] - 1);
      return repLens[repMaxIndex];
    }
  }
  

  if (lenMain >= 2)
  {
    _longestMatchLength = ReadMatchDistances();
    if (_longestMatchLength >= 2 &&
      (
        (_longestMatchLength >= lenMain && 
          _matchDistances[lenMain] < backMain) || 
        _longestMatchLength == lenMain + 1 && 
          !ChangePair(backMain, _matchDistances[_longestMatchLength]) ||
        _longestMatchLength > lenMain + 1 ||
        _longestMatchLength + 1 >= lenMain && 
          ChangePair(_matchDistances[lenMain - 1], backMain)
      )
      )
    {
      _longestMatchWasFound = true;
      backRes = UINT32(-1);
      return 1;
    }
    for(int i = 0; i < kNumRepDistances; i++)
    {
      UINT32 repLen = _matchFinder->GetMatchLen(0 - 1, _repDistances[i], kMatchMaxLen);
      if (repLen >= 2 && repLen + 1 >= lenMain)
      {
        _longestMatchWasFound = true;
        backRes = UINT32(-1);
        return 1;
      }
    }
    backRes = backMain + kNumRepDistances; 
    MovePos(lenMain - 2);
    return lenMain;
  }
  backRes = UINT32(-1);
  return 1;
}

STDMETHODIMP CEncoder::InitMatchFinder(IMatchFinder *matchFinder)
{
  _matchFinder = matchFinder;
  return S_OK;
}

HRESULT CEncoder::Flush()
{
  _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;

  _mainChoiceEncoders[_state.Index][posState].Encode(&_rangeEncoder, kMainChoiceMatchIndex);
  _matchChoiceEncoders[_state.Index].Encode(&_rangeEncoder, kMatchChoiceDistanceIndex);
  _state.UpdateMatch();
  UINT32 len = kMatchMinLen; // kMatchMaxLen;
  _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState);
  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.Encode(&_rangeEncoder, posReduced & kAlignMask);
}

HRESULT CEncoder::CodeReal(ISequentialInStream *inStream,
      ISequentialOutStream *outStream, 
      const UINT64 *inSize, const UINT64 *outSize,
      ICompressProgressInfo *progress)
{
  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(Init(outStream));
  
  // CCoderReleaser releaser(this);

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

  if (!_fastMode)
  {
    FillPosSlotPrices();
    FillDistancesPrices();
    FillAlignPrices();
  }

  _lenEncoder.SetTableSize(_numFastBytes);
  _lenEncoder.UpdateTables();
  _repMatchLenEncoder.SetTableSize(_numFastBytes);
  _repMatchLenEncoder.UpdateTables();

  lastPosSlotFillingPos = 0;
  nowPos64 = 0;
  return S_OK;
}

HRESULT CEncoder::CodeOneBlock(UINT64 *inSize, UINT64 *outSize, INT32 *finished)
{
  if (_inStream != 0)
  {
    RINOK(_matchFinder->Init(_inStream));
    _inStream = 0;
  }


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


  UINT64 progressPosValuePrev = nowPos64;
  if (nowPos64 == 0)
  {
    if (_matchFinder->GetNumAvailableBytes() == 0)
    {
      _matchFinder->ReleaseStream();
      WriteEndMarker(UINT32(nowPos64) & _posStateMask);
      return Flush();
    }
    ReadMatchDistances();
    UINT32 posState = UINT32(nowPos64) & _posStateMask;
    _mainChoiceEncoders[_state.Index][posState].Encode(&_rangeEncoder, kMainChoiceLiteralIndex);
    _state.UpdateChar();
    BYTE curByte = _matchFinder->GetIndexByte(0 - _additionalOffset);
    _literalEncoder.Encode(&_rangeEncoder, UINT32(nowPos64), _previousByte, 
      false, 0, curByte);
    _previousByte = curByte;
    _additionalOffset--;
    nowPos64++;
  }
  if (_matchFinder->GetNumAvailableBytes() == 0)
  {
    _matchFinder->ReleaseStream();
    WriteEndMarker(UINT32(nowPos64) & _posStateMask);
    return Flush();
  }
  while(true)
  {
    UINT32 pos;
    UINT32 posState = UINT32(nowPos64) & _posStateMask;

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

    if(len == 1 && pos == (-1))
    {
      _mainChoiceEncoders[_state.Index][posState].Encode(&_rangeEncoder, kMainChoiceLiteralIndex);
      _state.UpdateChar();
      BYTE matchByte;
      if(_peviousIsMatch)
        matchByte = _matchFinder->GetIndexByte(0 - _repDistances[0] - 1 - _additionalOffset);
      BYTE curByte = _matchFinder->GetIndexByte(0 - _additionalOffset);
      _literalEncoder.Encode(&_rangeEncoder, UINT32(nowPos64), _previousByte, _peviousIsMatch, 
          matchByte, curByte);
      _previousByte = curByte;
      _peviousIsMatch = false;
    }
    else
    {
      _peviousIsMatch = true;
      _mainChoiceEncoders[_state.Index][posState].Encode(&_rangeEncoder, kMainChoiceMatchIndex);
      if(pos < kNumRepDistances)
      {
        _matchChoiceEncoders[_state.Index].Encode(&_rangeEncoder, kMatchChoiceRepetitionIndex);
        if(pos == 0)
        {
          _matchRepChoiceEncoders[_state.Index].Encode(&_rangeEncoder, 0);
          if(len == 1)
            _matchRepShortChoiceEncoders[_state.Index][posState].Encode(&_rangeEncoder, 0);
          else
            _matchRepShortChoiceEncoders[_state.Index][posState].Encode(&_rangeEncoder, 1);
        }
        else
        {
          _matchRepChoiceEncoders[_state.Index].Encode(&_rangeEncoder, 1);
          if (pos == 1)
            _matchRep1ChoiceEncoders[_state.Index].Encode(&_rangeEncoder, 0);
          else
          {
            _matchRep1ChoiceEncoders[_state.Index].Encode(&_rangeEncoder, 1);
            _matchRep2ChoiceEncoders[_state.Index].Encode(&_rangeEncoder, pos - 2);
          }
        }
        if (len == 1)
          _state.UpdateShortRep();
        else
        {
          _repMatchLenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState);
          _state.UpdateRep();
        }


        UINT32 distance = _repDistances[pos];
        if (pos != 0)
        {
          for(UINT32 i = pos; i >= 1; i--)
            _repDistances[i] = _repDistances[i - 1];
          _repDistances[0] = distance;
        }
      }
      else
      {
        _matchChoiceEncoders[_state.Index].Encode(&_rangeEncoder, kMatchChoiceDistanceIndex);
        _state.UpdateMatch();
        _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState);
        pos -= kNumRepDistances;
        UINT32 posSlot = GetPosSlot(pos);
        UINT32 lenToPosState = GetLenToPosState(len);
        _posSlotEncoder[lenToPosState].Encode(&_rangeEncoder, posSlot);
        
        if (posSlot >= kStartPosModelIndex)
        {
          UINT32 footerBits = ((posSlot >> 1) - 1);
          UINT32 posReduced = pos - ((2 | (posSlot & 1)) << footerBits);

          if (posSlot < kEndPosModelIndex)
            _posEncoders[posSlot - kStartPosModelIndex].Encode(&_rangeEncoder, posReduced);
          else
          {
            _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
            _posAlignEncoder.Encode(&_rangeEncoder, posReduced & kAlignMask);
            if (!_fastMode)
              if (--_alignPriceCount == 0)
                FillAlignPrices();
          }
        }
        UINT32 distance = pos;
        for(UINT32 i = kNumRepDistances - 1; i >= 1; i--)
          _repDistances[i] = _repDistances[i - 1];
        _repDistances[0] = distance;
      }
      _previousByte = _matchFinder->GetIndexByte(len - 1 - _additionalOffset);
    }
    _additionalOffset -= len;
    nowPos64 += len;
    if (!_fastMode)
      if (nowPos64 - lastPosSlotFillingPos >= (1 << 9))
      {
        FillPosSlotPrices();
        FillDistancesPrices();
        lastPosSlotFillingPos = nowPos64;
      }
    if (_additionalOffset == 0)
    {
      *inSize = nowPos64;
      *outSize = _rangeEncoder.GetProcessedSize();
      if (_matchFinder->GetNumAvailableBytes() == 0)
      {
        _matchFinder->ReleaseStream();
        WriteEndMarker(UINT32(nowPos64) & _posStateMask);
        return Flush();
      }
      if (nowPos64 - progressPosValuePrev >= (1 << 12))
      {
        _finished = false;
        *finished = 0;
        return S_OK;
      }
    }
  }
}

STDMETHODIMP CEncoder::Code(ISequentialInStream *inStream,
    ISequentialOutStream *outStream, const UINT64 *inSize, const UINT64 *outSize,
    ICompressProgressInfo *progress)
{
  try { return CodeReal(inStream, outStream, inSize, outSize, progress); }
  catch(CMatchFinderException &e) { return e.ErrorCode; }
  catch(const COutBufferException &e) { return e.ErrorCode; }
  catch(...) { return E_FAIL; }
}
  
void CEncoder::FillPosSlotPrices()
{
  for (int lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
  {
	  UINT32 posSlot;
    for (posSlot = 0; posSlot < kEndPosModelIndex && posSlot < _distTableSize; posSlot++)
      _posSlotPrices[lenToPosState][posSlot] = _posSlotEncoder[lenToPosState].GetPrice(posSlot);
    for (; posSlot < _distTableSize; posSlot++)
      _posSlotPrices[lenToPosState][posSlot] = _posSlotEncoder[lenToPosState].GetPrice(posSlot) + 
      ((((posSlot >> 1) - 1) - kNumAlignBits) << NRangeCoder::kNumBitPriceShiftBits);
  }
}

void CEncoder::FillDistancesPrices()
{
  for (int lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
  {
	  UINT32 i;
    for (i = 0; i < kStartPosModelIndex; i++)
      _distancesPrices[lenToPosState][i] = _posSlotPrices[lenToPosState][i];
    for (; i < kNumFullDistances; i++)
    { 
      UINT32 posSlot = GetPosSlot(i);
      _distancesPrices[lenToPosState][i] = _posSlotPrices[lenToPosState][posSlot] +
          _posEncoders[posSlot - kStartPosModelIndex].GetPrice(i - 
          ((2 | (posSlot & 1)) << (((posSlot >> 1) - 1))));
    }
  }
}

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

}}