lzmaencoder.cpp

7-Zip 3.11的源码

  return i;
}
*/

UINT32 CEncoder::GetOptimum(UINT32 &backRes, UINT32 position)
{
  if(_optimumEndIndex != _optimumCurrentIndex)
  {
    UINT32 len = _optimum[_optimumCurrentIndex].PosPrev - _optimumCurrentIndex;
    backRes = _optimum[_optimumCurrentIndex].BackPrev;
    _optimumCurrentIndex = _optimum[_optimumCurrentIndex].PosPrev;
    return len;
  }
  _optimumCurrentIndex = 0;
  _optimumEndIndex = 0; // test it;
  
  UINT32 lenMain;
  if (!_longestMatchWasFound)
    lenMain = ReadMatchDistances();
  else
  {
    lenMain = _longestMatchLength;
    _longestMatchWasFound = false;
  }


  UINT32 reps[kNumRepDistances];
  UINT32 repLens[kNumRepDistances];
  UINT32 repMaxIndex = 0;
  int i;
  for(i = 0; i < kNumRepDistances; i++)
  {
    reps[i] = _repDistances[i];
    repLens[i] = _matchFinder->GetMatchLen(0 - 1, reps[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)
  {
    UINT32 backMain = (lenMain < _numFastBytes) ? _matchDistances[lenMain] :
        _matchDistances[_numFastBytes];
    backRes = backMain + kNumRepDistances; 
    MovePos(lenMain - 1);
    return lenMain;
  }
  BYTE currentByte = _matchFinder->GetIndexByte(0 - 1);

  _optimum[0].State = _state;

  BYTE matchByte;
  
  matchByte = _matchFinder->GetIndexByte(0 - _repDistances[0] - 1 - 1);

  UINT32 posState = (position & _posStateMask);

  _optimum[1].Price = _mainChoiceEncoders[_state.Index][posState].GetPrice(kMainChoiceLiteralIndex) + 
      _literalEncoder.GetPrice(position, _previousByte, _peviousIsMatch, matchByte, currentByte);
  _optimum[1].MakeAsChar();

  _optimum[1].PosPrev = 0;

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

  UINT32 matchPrice = _mainChoiceEncoders[_state.Index][posState].GetPrice(kMainChoiceMatchIndex);
  UINT32 repMatchPrice = matchPrice + 
      _matchChoiceEncoders[_state.Index].GetPrice(kMatchChoiceRepetitionIndex);

  if(matchByte == currentByte)
  {
    UINT32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);
    if(shortRepPrice < _optimum[1].Price)
    {
      _optimum[1].Price = shortRepPrice;
      _optimum[1].MakeAsShortRep();
    }
  }
  if(lenMain < 2)
  {
    backRes = _optimum[1].BackPrev;
    return 1;
  }

  
  UINT32 normalMatchPrice = matchPrice + 
      _matchChoiceEncoders[_state.Index].GetPrice(kMatchChoiceDistanceIndex);

  if (lenMain <= repLens[repMaxIndex])
    lenMain = 0;

  UINT32 len;
  for(len = 2; len <= lenMain; len++)
  {
    _optimum[len].PosPrev = 0;
    _optimum[len].BackPrev = _matchDistances[len] + kNumRepDistances;
    _optimum[len].Price = normalMatchPrice + 
        GetPosLenPrice(_matchDistances[len], len, posState);
    _optimum[len].Prev1IsChar = false;
  }

  if (lenMain < repLens[repMaxIndex])
    lenMain = repLens[repMaxIndex];

  for (; len <= lenMain; len++)
    _optimum[len].Price = kIfinityPrice;

  for(i = 0; i < kNumRepDistances; i++)
  {
    UINT repLen = repLens[i];
    for(UINT32 lenTest = 2; lenTest <= repLen; lenTest++)
    {
      UINT32 curAndLenPrice = repMatchPrice + GetRepPrice(i, lenTest, _state, posState);
      COptimal &optimum = _optimum[lenTest];
      if (curAndLenPrice < optimum.Price) 
      {
        optimum.Price = curAndLenPrice;
        optimum.PosPrev = 0;
        optimum.BackPrev = i;
        optimum.Prev1IsChar = false;
      }
    }
  }

  UINT32 cur = 0;
  UINT32 lenEnd = lenMain;

  while(true)
  {
    cur++;
    if(cur == lenEnd)  
      return Backward(backRes, cur);
    position++;
    UINT32 posPrev = _optimum[cur].PosPrev;
    CState state;
    if (_optimum[cur].Prev1IsChar)
    {
      posPrev--;
      if (_optimum[cur].Prev2)
      {
        state = _optimum[_optimum[cur].PosPrev2].State;
        if (_optimum[cur].BackPrev2 < kNumRepDistances)
          state.UpdateRep();
        else
          state.UpdateMatch();
      }
      else
        state = _optimum[posPrev].State;
      state.UpdateChar();
    }
    else
      state = _optimum[posPrev].State;
    bool prevWasMatch;
    if (posPrev == cur - 1)
    {
      if (_optimum[cur].IsShortRep())
      {
        prevWasMatch = true;
        state.UpdateShortRep();
      }
      else
      {
        prevWasMatch = false;
        state.UpdateChar();
      }
      /*
      if (_optimum[cur].Prev1IsChar)
        for(int i = 0; i < kNumRepDistances; i++)
          reps[i] = _optimum[posPrev].Backs[i];
      */
    }
    else
    {
      prevWasMatch = true;
      UINT32 pos;
      if (_optimum[cur].Prev1IsChar && _optimum[cur].Prev2)
      {
        posPrev = _optimum[cur].PosPrev2;
        pos = _optimum[cur].BackPrev2;
        state.UpdateRep();
      }
      else
      {
        pos = _optimum[cur].BackPrev;
        if (pos < kNumRepDistances)
          state.UpdateRep();
        else
          state.UpdateMatch();
      }
      if (pos < kNumRepDistances)
      {
        reps[0] = _optimum[posPrev].Backs[pos];
    		UINT32 i;
        for(i = 1; i <= pos; i++)
          reps[i] = _optimum[posPrev].Backs[i - 1];
        for(; i < kNumRepDistances; i++)
          reps[i] = _optimum[posPrev].Backs[i];
      }
      else
      {
        reps[0] = (pos - kNumRepDistances);
        for(UINT32 i = 1; i < kNumRepDistances; i++)
          reps[i] = _optimum[posPrev].Backs[i - 1];
      }
    }
    _optimum[cur].State = state;
    for(UINT32 i = 0; i < kNumRepDistances; i++)
      _optimum[cur].Backs[i] = reps[i];
    UINT32 newLen = ReadMatchDistances();
    if(newLen > _numFastBytes)
    {
      _longestMatchLength = newLen;
      _longestMatchWasFound = true;
      return Backward(backRes, cur);
    }
    UINT32 curPrice = _optimum[cur].Price; 
    // BYTE currentByte  = _matchFinder->GetIndexByte(0 - 1);
    // BYTE matchByte = _matchFinder->GetIndexByte(0 - reps[0] - 1 - 1);
    const BYTE *data = _matchFinder->GetPointerToCurrentPos() - 1;
    BYTE currentByte = *data;
    BYTE matchByte = data[0 - reps[0] - 1];

    UINT32 posState = (position & _posStateMask);

    UINT32 curAnd1Price = curPrice +
        _mainChoiceEncoders[state.Index][posState].GetPrice(kMainChoiceLiteralIndex) +
        _literalEncoder.GetPrice(position, data[-1], prevWasMatch, matchByte, currentByte);

    COptimal &nextOptimum = _optimum[cur + 1];

    bool nextIsChar = false;
    if (curAnd1Price < nextOptimum.Price) 
    {
      nextOptimum.Price = curAnd1Price;
      nextOptimum.PosPrev = cur;
      nextOptimum.MakeAsChar();
      nextIsChar = true;
    }

    UINT32 matchPrice = curPrice + _mainChoiceEncoders[state.Index][posState].GetPrice(kMainChoiceMatchIndex);
    UINT32 repMatchPrice = matchPrice + _matchChoiceEncoders[state.Index].GetPrice(kMatchChoiceRepetitionIndex);
    
    if(matchByte == currentByte &&
        !(nextOptimum.PosPrev < cur && nextOptimum.BackPrev == 0))
    {
      UINT32 shortRepPrice = repMatchPrice + GetRepLen1Price(state, posState);
      if(shortRepPrice <= nextOptimum.Price)
      {
        nextOptimum.Price = shortRepPrice;
        nextOptimum.PosPrev = cur;
        nextOptimum.MakeAsShortRep();
        // nextIsChar = false;
      }
    }
    /*
    if(newLen == 2 && _matchDistances[2] >= kDistLimit2) // test it maybe set 2000 ?
      continue;
    */

    UINT32 numAvailableBytes = _matchFinder->GetNumAvailableBytes() + 1;
    numAvailableBytes = MyMin(kNumOpts - 1 - cur, numAvailableBytes);

    if (numAvailableBytes < 2)
      continue;
    if (numAvailableBytes > _numFastBytes)
      numAvailableBytes = _numFastBytes;
    if (numAvailableBytes >= 3 && !nextIsChar)
    {
      UINT32 backOffset = reps[0] + 1;
      UINT32 temp;
      for (temp = 1; temp < numAvailableBytes; temp++)
        if (data[temp] != data[temp - backOffset])
          break;
      UINT32 lenTest2 = temp - 1;
      if (lenTest2 >= 2)
      {
        CState state2 = state;
        state2.UpdateChar();
        UINT32 posStateNext = (position + 1) & _posStateMask;
        UINT32 nextRepMatchPrice = curAnd1Price + 
            _mainChoiceEncoders[state2.Index][posStateNext].GetPrice(kMainChoiceMatchIndex) +
            _matchChoiceEncoders[state2.Index].GetPrice(kMatchChoiceRepetitionIndex);
        // for (; lenTest2 >= 2; lenTest2--)
        {
          while(lenEnd < cur + 1 + lenTest2)
            _optimum[++lenEnd].Price = kIfinityPrice;
          UINT32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(
              0, lenTest2, state2, posStateNext);
          COptimal &optimum = _optimum[cur + 1 + lenTest2];
          if (curAndLenPrice < optimum.Price) 
          {
            optimum.Price = curAndLenPrice;
            optimum.PosPrev = cur + 1;
            optimum.BackPrev = 0;
            optimum.Prev1IsChar = true;
            optimum.Prev2 = false;
          }
        }
      }
    }
    for(UINT32 repIndex = 0; repIndex < kNumRepDistances; repIndex++)
    {
      // UINT32 repLen = _matchFinder->GetMatchLen(0 - 1, reps[repIndex], newLen); // test it;
      UINT32 backOffset = reps[repIndex] + 1;
      UINT32 lenTest;
      for (lenTest = 0; lenTest < numAvailableBytes; lenTest++)
        if (data[lenTest] != data[lenTest - backOffset])
          break;
      for(; lenTest >= 2; lenTest--)
      {
        while(lenEnd < cur + lenTest)
          _optimum[++lenEnd].Price = kIfinityPrice;
        UINT32 curAndLenPrice = repMatchPrice + GetRepPrice(repIndex, lenTest, state, posState);
        COptimal &optimum = _optimum[cur + lenTest];
        if (curAndLenPrice < optimum.Price) 
        {
          optimum.Price = curAndLenPrice;
          optimum.PosPrev = cur;
          optimum.BackPrev = repIndex;
          optimum.Prev1IsChar = false;
        }

        /*
        if (_maxMode)
        {
          UINT32 temp;
          for (temp = lenTest + 1; temp < numAvailableBytes; temp++)
            if (data[temp] != data[temp - backOffset])
              break;
          UINT32 lenTest2 = temp - (lenTest + 1);
          if (lenTest2 >= 2)
          {
            CState state2 = state;
            state2.UpdateRep();
            UINT32 posStateNext = (position + lenTest) & _posStateMask;
            UINT32 curAndLenCharPrice = curAndLenPrice + 
                _mainChoiceEncoders[state2.Index][posStateNext].GetPrice(kMainChoiceLiteralIndex) +
                _literalEncoder.GetPrice(position + lenTest, data[lenTest - 1], 
                true, data[lenTest - backOffset], data[lenTest]);
            state2.UpdateChar();
            posStateNext = (position + lenTest + 1) & _posStateMask;
            UINT32 nextMatchPrice = curAndLenCharPrice + _mainChoiceEncoders[state2.Index][posStateNext].GetPrice(kMainChoiceMatchIndex);
            UINT32 nextRepMatchPrice = nextMatchPrice + _matchChoiceEncoders[state2.Index].GetPrice(kMatchChoiceRepetitionIndex);
            
            // for(; lenTest2 >= 2; lenTest2--)
            {
              UINT32 offset = lenTest + 1 + lenTest2;
              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 = repIndex;
              }
            }
          }
        }
        */
      }
    }
    
    //    for(UINT32 lenTest = 2; lenTest <= newLen; lenTest++)
    if (newLen > numAvailableBytes)
      newLen = numAvailableBytes;
    if (newLen >= 2)
    {
      if (newLen == 2 && _matchDistances[2] >= 0x80)
        continue;
      UINT32 normalMatchPrice = matchPrice + 
        _matchChoiceEncoders[state.Index].GetPrice(kMatchChoiceDistanceIndex);
      while(lenEnd < cur + newLen)
        _optimum[++lenEnd].Price = kIfinityPrice;

      for(UINT32 lenTest = newLen; lenTest >= 2; lenTest--)
      {
        UINT32 curBack = _matchDistances[lenTest];
        UINT32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(curBack, lenTest, 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)
        {
          UINT32 backOffset = curBack + 1;
          UINT32 temp;
          for (temp = lenTest + 1; temp < numAvailableBytes; temp++)
            if (data[temp] != data[temp - backOffset])
              break;
          UINT32 lenTest2 = temp - (lenTest + 1);
          if (lenTest2 >= 2)
          {
            CState state2 = state;
            state2.UpdateMatch();
            UINT32 posStateNext = (position + lenTest) & _posStateMask;
            UINT32 curAndLenCharPrice = curAndLenPrice + 
                _mainChoiceEncoders[state2.Index][posStateNext].GetPrice(kMainChoiceLiteralIndex) +
                _literalEncoder.GetPrice(position + lenTest, data[lenTest - 1], 
                true, data[lenTest - backOffset], data[lenTest]);
            state2.UpdateChar();
            posStateNext = (position + lenTest + 1) & _posStateMask;
            UINT32 nextMatchPrice = curAndLenCharPrice + _mainChoiceEncoders[state2.Index][posStateNext].GetPrice(kMainChoiceMatchIndex);
            UINT32 nextRepMatchPrice = nextMatchPrice + _matchChoiceEncoders[state2.Index].GetPrice(kMatchChoiceRepetitionIndex);
            
            // for(; lenTest2 >= 2; lenTest2--)
            {
              UINT32 offset = lenTest + 1 + lenTest2;