lzmaencoder.cpp

著名的7zip的压缩算法,压缩比最高,但是压缩时间也比较长!

    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
      state = _optimum[posPrev].State;
    if (posPrev == cur - 1)
    {
      if (curOptimum.IsShortRep())
        state.UpdateShortRep();
      else
        state.UpdateChar();
    }
    else
    {
      UInt32 pos;
      if (curOptimum.Prev1IsChar && curOptimum.Prev2)
      {
        posPrev = curOptimum.PosPrev2;
        pos = curOptimum.BackPrev2;
        state.UpdateRep();
      }
      else
      {
        pos = curOptimum.BackPrev;
        if (pos < kNumRepDistances)
          state.UpdateRep();
        else
          state.UpdateMatch();
      }
      const COptimal &prevOptimum = _optimum[posPrev];
      if (pos < kNumRepDistances)
      {
        reps[0] = prevOptimum.Backs[pos];
    		UInt32 i;
        for(i = 1; i <= pos; i++)
          reps[i] = prevOptimum.Backs[i - 1];
        for(; i < kNumRepDistances; i++)
          reps[i] = prevOptimum.Backs[i];
      }
      else
      {
        reps[0] = (pos - kNumRepDistances);
        for(UInt32 i = 1; i < kNumRepDistances; i++)
          reps[i] = prevOptimum.Backs[i - 1];
      }
    }
    curOptimum.State = state;
    for(UInt32 i = 0; i < kNumRepDistances; i++)
      curOptimum.Backs[i] = reps[i];
    UInt32 curPrice = curOptimum.Price; 
    const Byte *data = _matchFinder->GetPointerToCurrentPos() - 1;
    const Byte currentByte = *data;
    const Byte matchByte = data[(size_t)0 - reps[0] - 1];

    UInt32 posState = (position & _posStateMask);

    UInt32 curAnd1Price = curPrice +
        _isMatch[state.Index][posState].GetPrice0() +
        _literalEncoder.GetSubCoder(position, data[(size_t)0 - 1])->GetPrice(!state.IsCharState(), 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 + _isMatch[state.Index][posState].GetPrice1();
    UInt32 repMatchPrice = matchPrice + _isRep[state.Index].GetPrice1();
    
    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 = true;
      }
    }
    /*
    if(newLen == 2 && matchDistances[2] >= kDistLimit2) // test it maybe set 2000 ?
      continue;
    */

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

    if (numAvailableBytes < 2)
      continue;
    if (numAvailableBytes > _numFastBytes)
      numAvailableBytes = _numFastBytes;
    if (!nextIsChar && matchByte != currentByte) // speed optimization
    {
      // try Literal + rep0
      UInt32 backOffset = reps[0] + 1;
      UInt32 limit = MyMin(numAvailableBytesFull, _numFastBytes + 1);
      UInt32 temp;
      for (temp = 1; temp < limit && 
          data[temp] == data[(size_t)temp - backOffset]; temp++);
      UInt32 lenTest2 = temp - 1;
      if (lenTest2 >= 2)
      {
        CState state2 = state;
        state2.UpdateChar();
        UInt32 posStateNext = (position + 1) & _posStateMask;
        UInt32 nextRepMatchPrice = curAnd1Price + 
            _isMatch[state2.Index][posStateNext].GetPrice1() +
            _isRep[state2.Index].GetPrice1();
        // for (; lenTest2 >= 2; lenTest2--)
        {
          UInt32 offset = cur + 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 + 1;
            optimum.BackPrev = 0;
            optimum.Prev1IsChar = true;
            optimum.Prev2 = false;
          }
        }
      }
    }
    
    UInt32 startLen = 2; // speed optimization 
    for(UInt32 repIndex = 0; repIndex < kNumRepDistances; repIndex++)
    {
      // UInt32 repLen = _matchFinder->GetMatchLen(0 - 1, reps[repIndex], newLen); // test it;
      UInt32 backOffset = reps[repIndex] + 1;
      if (data[0] != data[(size_t)0 - backOffset] ||
          data[1] != data[(size_t)1 - backOffset])
        continue;
      UInt32 lenTest;
      for (lenTest = 2; lenTest < numAvailableBytes && 
          data[lenTest] == data[(size_t)lenTest - backOffset]; lenTest++);
      while(lenEnd < cur + lenTest)
        _optimum[++lenEnd].Price = kIfinityPrice;
      UInt32 lenTestTemp = lenTest;
      UInt32 price = repMatchPrice + GetPureRepPrice(repIndex, state, posState);
      do
      {
        UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(lenTest - 2, posState);
        COptimal &optimum = _optimum[cur + lenTest];
        if (curAndLenPrice < optimum.Price) 
        {
          optimum.Price = curAndLenPrice;
          optimum.PosPrev = cur;
          optimum.BackPrev = repIndex;
          optimum.Prev1IsChar = false;
        }
      }
      while(--lenTest >= 2);
      lenTest = lenTestTemp;
      
      if (repIndex == 0)
        startLen = lenTest + 1;
        
      // if (_maxMode)
        {
          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.UpdateRep();
            UInt32 posStateNext = (position + lenTest) & _posStateMask;
            UInt32 curAndLenCharPrice = 
                price + _repMatchLenEncoder.GetPrice(lenTest - 2, posState) + 
                _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 = (position + lenTest + 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 = repIndex;
              }
            }
          }
        }
      }
    
    //    for(UInt32 lenTest = 2; lenTest <= newLen; lenTest++)
    if (newLen > numAvailableBytes)
    {
      newLen = numAvailableBytes;
      for (numDistancePairs = 0; newLen > matchDistances[numDistancePairs]; numDistancePairs += 2);
      matchDistances[numDistancePairs] = newLen;
      numDistancePairs += 2;
    }
    if (newLen >= startLen)
    {
      UInt32 normalMatchPrice = matchPrice + _isRep[state.Index].GetPrice0();
      while(lenEnd < cur + newLen)
        _optimum[++lenEnd].Price = kIfinityPrice;

      UInt32 offs = 0;
      while(startLen > matchDistances[offs])
        offs += 2;
      UInt32 curBack = matchDistances[offs + 1];
      UInt32 posSlot = GetPosSlot2(curBack);
      for(UInt32 lenTest = /*2*/ startLen; ; lenTest++)
      {
        UInt32 curAndLenPrice = normalMatchPrice;
        UInt32 lenToPosState = GetLenToPosState(lenTest);
        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;