1 // LZMA/Encoder.cpp

     2 

     3 #include "StdAfx.h"

     4 

     5 #include <stdio.h>

     6 

     7 #ifdef _WIN32

     8 #define USE_ALLOCA

     9 #endif

    10 

    11 #ifdef USE_ALLOCA

    12 #ifdef _WIN32

    13 #include <malloc.h>

    14 #else

    15 #include <stdlib.h>

    16 #endif

    17 #endif

    18 

    19 #include "../../../Common/Defs.h"

    20 #include "../../Common/StreamUtils.h"

    21 

    22 #include "LZMAEncoder.h"

    23 

    24 // extern "C" { #include "../../../../C/7zCrc.h" }

    25 

    26 // #define SHOW_STAT

    27 

    28 

    29 namespace NCompress {

    30 namespace NLZMA {

    31 

    32 // struct CCrcInit { CCrcInit() { InitCrcTable(); } } g_CrcInit;

    33 

    34 const int kDefaultDictionaryLogSize = 22;

    35 const UInt32 kNumFastBytesDefault = 0x20;

    36 

    37 #ifndef LZMA_LOG_BSR

    38 Byte g_FastPos[1 << kNumLogBits];

    39 

    40 class CFastPosInit

    41 {

    42 public:

    43   CFastPosInit() { Init(); }

    44   void Init()

    45   {

    46     const Byte kFastSlots = kNumLogBits * 2;

    47     int c = 2;

    48     g_FastPos[0] = 0;

    49     g_FastPos[1] = 1;

    50 

    51     for (Byte slotFast = 2; slotFast < kFastSlots; slotFast++)

    52     {

    53       UInt32 k = (1 << ((slotFast >> 1) - 1));

    54       for (UInt32 j = 0; j < k; j++, c++)

    55         g_FastPos[c] = slotFast;

    56     }

    57   }

    58 } g_FastPosInit;

    59 #endif

    60 

    61 void CLiteralEncoder2::Encode(NRangeCoder::CEncoder *rangeEncoder, Byte symbol)

    62 {

    63   UInt32 context = 1;

    64   int i = 8;

    65   do 

    66   {

    67     i--;

    68     UInt32 bit = (symbol >> i) & 1;

    69     _encoders[context].Encode(rangeEncoder, bit);

    70     context = (context << 1) | bit;

    71   }

    72   while(i != 0);

    73 }

    74 

    75 void CLiteralEncoder2::EncodeMatched(NRangeCoder::CEncoder *rangeEncoder, 

    76     Byte matchByte, Byte symbol)

    77 {

    78   UInt32 context = 1;

    79   int i = 8;

    80   do 

    81   {

    82     i--;

    83     UInt32 bit = (symbol >> i) & 1;

    84     UInt32 matchBit = (matchByte >> i) & 1;

    85     _encoders[0x100 + (matchBit << 8) + context].Encode(rangeEncoder, bit);

    86     context = (context << 1) | bit;

    87     if (matchBit != bit)

    88     {

    89       while(i != 0)

    90       {

    91         i--;

    92         UInt32 bit = (symbol >> i) & 1;

    93         _encoders[context].Encode(rangeEncoder, bit);

    94         context = (context << 1) | bit;

    95       }

    96       break;

    97     }

    98   }

    99   while(i != 0);

   100 }

   101 

   102 UInt32 CLiteralEncoder2::GetPrice(bool matchMode, Byte matchByte, Byte symbol) const

   103 {

   104   UInt32 price = 0;

   105   UInt32 context = 1;

   106   int i = 8;

   107   if (matchMode)

   108   {

   109     do 

   110     {

   111       i--;

   112       UInt32 matchBit = (matchByte >> i) & 1;

   113       UInt32 bit = (symbol >> i) & 1;

   114       price += _encoders[0x100 + (matchBit << 8) + context].GetPrice(bit);

   115       context = (context << 1) | bit;

   116       if (matchBit != bit)

   117         break;

   118     }

   119     while (i != 0);

   120   }

   121   while(i != 0)

   122   {

   123     i--;

   124     UInt32 bit = (symbol >> i) & 1;

   125     price += _encoders[context].GetPrice(bit);

   126     context = (context << 1) | bit;

   127   }

   128   return price;

   129 };

   130 

   131 

   132 namespace NLength {

   133 

   134 void CEncoder::Init(UInt32 numPosStates)

   135 {

   136   _choice.Init();

   137   _choice2.Init();

   138   for (UInt32 posState = 0; posState < numPosStates; posState++)

   139   {

   140     _lowCoder[posState].Init();

   141     _midCoder[posState].Init();

   142   }

   143   _highCoder.Init();

   144 }

   145 

   146 void CEncoder::Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState)

   147 {

   148   if(symbol < kNumLowSymbols)

   149   {

   150     _choice.Encode(rangeEncoder, 0);

   151     _lowCoder[posState].Encode(rangeEncoder, symbol);

   152   }

   153   else

   154   {

   155     _choice.Encode(rangeEncoder, 1);

   156     if(symbol < kNumLowSymbols + kNumMidSymbols)

   157     {

   158       _choice2.Encode(rangeEncoder, 0);

   159       _midCoder[posState].Encode(rangeEncoder, symbol - kNumLowSymbols);

   160     }

   161     else

   162     {

   163       _choice2.Encode(rangeEncoder, 1);

   164       _highCoder.Encode(rangeEncoder, symbol - kNumLowSymbols - kNumMidSymbols);

   165     }

   166   }

   167 }

   168 

   169 void CEncoder::SetPrices(UInt32 posState, UInt32 numSymbols, UInt32 *prices) const

   170 {

   171   UInt32 a0 = _choice.GetPrice0();

   172   UInt32 a1 = _choice.GetPrice1();

   173   UInt32 b0 = a1 + _choice2.GetPrice0();

   174   UInt32 b1 = a1 + _choice2.GetPrice1();

   175   UInt32 i = 0;

   176   for (i = 0; i < kNumLowSymbols; i++)

   177   {

   178     if (i >= numSymbols)

   179       return;

   180     prices[i] = a0 + _lowCoder[posState].GetPrice(i);

   181   }

   182   for (; i < kNumLowSymbols + kNumMidSymbols; i++)

   183   {

   184     if (i >= numSymbols)

   185       return;

   186     prices[i] = b0 + _midCoder[posState].GetPrice(i - kNumLowSymbols);

   187   }

   188   for (; i < numSymbols; i++)

   189     prices[i] = b1 + _highCoder.GetPrice(i - kNumLowSymbols - kNumMidSymbols);

   190 }

   191 

   192 }

   193 

   194 CEncoder::CEncoder():

   195   _numFastBytes(kNumFastBytesDefault),

   196   _distTableSize(kDefaultDictionaryLogSize * 2),

   197   _posStateBits(2),

   198   _posStateMask(4 - 1),

   199   _numLiteralPosStateBits(0),

   200   _numLiteralContextBits(3),

   201   _dictionarySize(1 << kDefaultDictionaryLogSize),

   202   _matchFinderCycles(0),

   203   #ifdef COMPRESS_MF_MT

   204   _multiThread(false),

   205   #endif

   206   _writeEndMark(false)

   207 {

   208   MatchFinder_Construct(&_matchFinderBase);

   209   // _maxMode = false;

   210   _fastMode = false;

   211   #ifdef COMPRESS_MF_MT

   212   MatchFinderMt_Construct(&_matchFinderMt);

   213   _matchFinderMt.MatchFinder = &_matchFinderBase;

   214   #endif

   215 }

   216 

   217 

   218 static void *SzAlloc(size_t size) { return BigAlloc(size); }

   219 static void SzFree(void *address) { BigFree(address); }

   220 ISzAlloc g_Alloc = { SzAlloc, SzFree };

   221 

   222 CEncoder::~CEncoder()

   223 {

   224   #ifdef COMPRESS_MF_MT

   225   MatchFinderMt_Destruct(&_matchFinderMt, &g_Alloc);

   226   #endif

   227   MatchFinder_Free(&_matchFinderBase, &g_Alloc);

   228 }

   229 

   230 static const UInt32 kBigHashDicLimit = (UInt32)1 << 24;

   231 

   232 HRESULT CEncoder::Create()

   233 {

   234   if (!_rangeEncoder.Create(1 << 20))

   235     return E_OUTOFMEMORY;

   236   bool btMode = (_matchFinderBase.btMode != 0);

   237   #ifdef COMPRESS_MF_MT

   238   _mtMode = (_multiThread && !_fastMode && btMode);

   239   #endif

   240   

   241   if (!_literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits))

   242     return E_OUTOFMEMORY;

   243 

   244   _matchFinderBase.bigHash = (_dictionarySize > kBigHashDicLimit);

   245 

   246   UInt32 numCycles = 16 + (_numFastBytes >> 1);

   247   if (!btMode)

   248     numCycles >>= 1;

   249   if (_matchFinderCycles != 0)

   250     numCycles = _matchFinderCycles;

   251   _matchFinderBase.cutValue = numCycles;

   252   #ifdef COMPRESS_MF_MT

   253   if (_mtMode)

   254   {

   255     RINOK(MatchFinderMt_Create(&_matchFinderMt, _dictionarySize, kNumOpts, _numFastBytes, kMatchMaxLen, &g_Alloc));

   256     _matchFinderObj = &_matchFinderMt;

   257     MatchFinderMt_CreateVTable(&_matchFinderMt, &_matchFinder);

   258   }

   259   else

   260   #endif

   261   {

   262     if (!MatchFinder_Create(&_matchFinderBase, _dictionarySize, kNumOpts, _numFastBytes, kMatchMaxLen, &g_Alloc))

   263       return E_OUTOFMEMORY;

   264     _matchFinderObj = &_matchFinderBase;

   265     MatchFinder_CreateVTable(&_matchFinderBase, &_matchFinder);

   266   }

   267   return S_OK;

   268 }

   269 

   270 inline wchar_t GetUpperChar(wchar_t c)

   271 {

   272   if (c >= 'a' && c <= 'z')

   273     c -= 0x20;

   274   return c;

   275 }

   276 

   277 static int ParseMatchFinder(const wchar_t *s, int *btMode, UInt32 *numHashBytes /* , int *skipModeBits */)

   278 {

   279   wchar_t c = GetUpperChar(*s++);

   280   if (c == L'H')

   281   {

   282     if (GetUpperChar(*s++) != L'C')

   283       return 0;

   284     int numHashBytesLoc = (int)(*s++ - L'0');

   285     if (numHashBytesLoc < 4 || numHashBytesLoc > 4)

   286       return 0;

   287     if (*s++ != 0)

   288       return 0;

   289     *btMode = 0;

   290     *numHashBytes = numHashBytesLoc;

   291     return 1;

   292   }

   293   if (c != L'B')

   294     return 0;

   295 

   296   if (GetUpperChar(*s++) != L'T')

   297     return 0;

   298   int numHashBytesLoc = (int)(*s++ - L'0');

   299   if (numHashBytesLoc < 2 || numHashBytesLoc > 4)

   300     return 0;

   301   c = GetUpperChar(*s++);

   302   /*

   303   int skipModeBitsLoc = 0;

   304   if (c == L'D')

   305   {

   306     skipModeBitsLoc = 2;

   307     c = GetUpperChar(*s++);

   308   }

   309   */

   310   if (c != L'\0')

   311     return 0;

   312   *btMode = 1;

   313   *numHashBytes = numHashBytesLoc;

   314   // *skipModeBits = skipModeBitsLoc;

   315   return 1;

   316 }

   317 

   318 STDMETHODIMP CEncoder::SetCoderProperties(const PROPID *propIDs, 

   319     const PROPVARIANT *properties, UInt32 numProperties)

   320 {

   321   for (UInt32 i = 0; i < numProperties; i++)

   322   {

   323     const PROPVARIANT &prop = properties[i];

   324     switch(propIDs[i])

   325     {

   326       case NCoderPropID::kNumFastBytes:

   327       {

   328         if (prop.vt != VT_UI4)

   329           return E_INVALIDARG;

   330         UInt32 numFastBytes = prop.ulVal;

   331         if(numFastBytes < 5 || numFastBytes > kMatchMaxLen)

   332           return E_INVALIDARG;

   333         _numFastBytes = numFastBytes;

   334         break;

   335       }

   336       case NCoderPropID::kMatchFinderCycles:

   337       {

   338         if (prop.vt != VT_UI4)

   339           return E_INVALIDARG;

   340         _matchFinderCycles = prop.ulVal;

   341         break;

   342       }

   343       case NCoderPropID::kAlgorithm:

   344       {

   345         if (prop.vt != VT_UI4)

   346           return E_INVALIDARG;

   347         UInt32 maximize = prop.ulVal;

   348         _fastMode = (maximize == 0); 

   349         // _maxMode = (maximize >= 2);

   350         break;

   351       }

   352       case NCoderPropID::kMatchFinder:

   353       {

   354         if (prop.vt != VT_BSTR)

   355           return E_INVALIDARG;

   356         if (!ParseMatchFinder(prop.bstrVal, &_matchFinderBase.btMode, &_matchFinderBase.numHashBytes /* , &_matchFinderBase.skipModeBits */))

   357           return E_INVALIDARG;

   358         break;

   359       }

   360       case NCoderPropID::kMultiThread:

   361       {

   362         if (prop.vt != VT_BOOL)

   363           return E_INVALIDARG;

   364         #ifdef COMPRESS_MF_MT

   365         Bool newMultiThread = (prop.boolVal == VARIANT_TRUE);

   366         if (newMultiThread != _multiThread)

   367         {

   368           ReleaseMatchFinder();

   369           _multiThread = newMultiThread;

   370         }

   371         #endif

   372         break;

   373       }

   374       case NCoderPropID::kNumThreads:

   375       {

   376         if (prop.vt != VT_UI4)

   377           return E_INVALIDARG;

   378         #ifdef COMPRESS_MF_MT

   379         Bool newMultiThread = (prop.ulVal > 1) ? True : False;

   380         if (newMultiThread != _multiThread)

   381         {

   382           ReleaseMatchFinder();

   383           _multiThread = newMultiThread;

   384         }

   385         #endif

   386         break;

   387       }

   388       case NCoderPropID::kDictionarySize:

   389       {

   390         const int kDicLogSizeMaxCompress = 30; // must be <= ((kNumLogBits - 1) * 2) + 7 = 31;

   391         if (prop.vt != VT_UI4)

   392           return E_INVALIDARG;

   393         UInt32 dictionarySize = prop.ulVal;

   394         if (dictionarySize < UInt32(1 << kDicLogSizeMin) ||

   395             dictionarySize > UInt32(1 << kDicLogSizeMaxCompress))

   396           return E_INVALIDARG;

   397         _dictionarySize = dictionarySize;

   398         UInt32 dicLogSize;

   399         for(dicLogSize = 0; dicLogSize < (UInt32)kDicLogSizeMaxCompress; dicLogSize++)

   400           if (dictionarySize <= (UInt32(1) << dicLogSize))

   401             break;

   402         _distTableSize = dicLogSize * 2;

   403         break;

   404       }

   405       case NCoderPropID::kPosStateBits:

   406       {

   407         if (prop.vt != VT_UI4)

   408           return E_INVALIDARG;

   409         UInt32 value = prop.ulVal;

   410         if (value > (UInt32)NLength::kNumPosStatesBitsEncodingMax)

   411           return E_INVALIDARG;

   412         _posStateBits = value;

   413         _posStateMask = (1 << _posStateBits) - 1;

   414         break;

   415       }

   416       case NCoderPropID::kLitPosBits:

   417       {

   418         if (prop.vt != VT_UI4)

   419           return E_INVALIDARG;

   420         UInt32 value = prop.ulVal;

   421         if (value > (UInt32)kNumLitPosStatesBitsEncodingMax)

   422           return E_INVALIDARG;

   423         _numLiteralPosStateBits = value;

   424         break;

   425       }

   426       case NCoderPropID::kLitContextBits:

   427       {

   428         if (prop.vt != VT_UI4)

   429           return E_INVALIDARG;

   430         UInt32 value = prop.ulVal;

   431         if (value > (UInt32)kNumLitContextBitsMax)

   432           return E_INVALIDARG;

   433         _numLiteralContextBits = value;

   434         break;

   435       }

   436       case NCoderPropID::kEndMarker:

   437       {

   438         if (prop.vt != VT_BOOL)

   439           return E_INVALIDARG;

   440         SetWriteEndMarkerMode(prop.boolVal == VARIANT_TRUE);

   441         break;

   442       }

   443       default:

   444         return E_INVALIDARG;

   445     }

   446   }

   447   return S_OK;

   448 }

   449 

   450 STDMETHODIMP CEncoder::WriteCoderProperties(ISequentialOutStream *outStream)

   451 { 

   452   const UInt32 kPropSize = 5;

   453   Byte properties[kPropSize];

   454   properties[0] = (Byte)((_posStateBits * 5 + _numLiteralPosStateBits) * 9 + _numLiteralContextBits);

   455   for (int i = 0; i < 4; i++)

   456     properties[1 + i] = Byte(_dictionarySize >> (8 * i));

   457   return WriteStream(outStream, properties, kPropSize, NULL);

   458 }

   459 

   460 STDMETHODIMP CEncoder::SetOutStream(ISequentialOutStream *outStream)

   461 {

   462   _rangeEncoder.SetStream(outStream);

   463   return S_OK;

   464 }

   465 

   466 STDMETHODIMP CEncoder::ReleaseOutStream()

   467 {

   468   _rangeEncoder.ReleaseStream();

   469   return S_OK;

   470 }

   471 

   472 HRESULT CEncoder::Init()

   473 {

   474   CBaseState::Init();

   475 

   476   _rangeEncoder.Init();

   477 

   478   for(int i = 0; i < kNumStates; i++)

   479   {

   480     for (UInt32 j = 0; j <= _posStateMask; j++)

   481     {

   482       _isMatch[i][j].Init();

   483       _isRep0Long[i][j].Init();

   484     }

   485     _isRep[i].Init();

   486     _isRepG0[i].Init();

   487     _isRepG1[i].Init();

   488     _isRepG2[i].Init();

   489   }

   490 

   491   _literalEncoder.Init();

   492 

   493   {

   494     for(UInt32 i = 0; i < kNumLenToPosStates; i++)

   495       _posSlotEncoder[i].Init();

   496   }

   497   {

   498     for(UInt32 i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)

   499       _posEncoders[i].Init();

   500   }

   501 

   502   _lenEncoder.Init(1 << _posStateBits);

   503   _repMatchLenEncoder.Init(1 << _posStateBits);

   504 

   505   _posAlignEncoder.Init();

   506 

   507   _longestMatchWasFound = false;

   508   _optimumEndIndex = 0;

   509   _optimumCurrentIndex = 0;

   510   _additionalOffset = 0;

   511 

   512   return S_OK;

   513 }

   514 

   515 #ifdef SHOW_STAT

   516 static int ttt = 0;

   517 #endif

   518 

   519 void CEncoder::MovePos(UInt32 num)

   520 {

   521   #ifdef SHOW_STAT

   522   ttt += num;

   523   printf("\n MovePos %d", num);

   524   #endif

   525   if (num != 0)

   526   {

   527     _additionalOffset += num;

   528     _matchFinder.Skip(_matchFinderObj, num);

   529   }

   530 }

   531 

   532 UInt32 CEncoder::Backward(UInt32 &backRes, UInt32 cur)

   533 {

   534   _optimumEndIndex = cur;

   535   UInt32 posMem = _optimum[cur].PosPrev;

   536   UInt32 backMem = _optimum[cur].BackPrev;

   537   do

   538   {

   539     if (_optimum[cur].Prev1IsChar)

   540     {

   541       _optimum[posMem].MakeAsChar();

   542       _optimum[posMem].PosPrev = posMem - 1;

   543       if (_optimum[cur].Prev2)

   544       {

   545         _optimum[posMem - 1].Prev1IsChar = false;

   546         _optimum[posMem - 1].PosPrev = _optimum[cur].PosPrev2;

   547         _optimum[posMem - 1].BackPrev = _optimum[cur].BackPrev2;

   548       }

   549     }

   550     UInt32 posPrev = posMem;

   551     UInt32 backCur = backMem;

   552 

   553     backMem = _optimum[posPrev].BackPrev;

   554     posMem = _optimum[posPrev].PosPrev;

   555 

   556     _optimum[posPrev].BackPrev = backCur;

   557     _optimum[posPrev].PosPrev = cur;

   558     cur = posPrev;

   559   }

   560   while(cur != 0);

   561   backRes = _optimum[0].BackPrev;

   562   _optimumCurrentIndex  = _optimum[0].PosPrev;

   563   return _optimumCurrentIndex; 

   564 }

   565 

   566 /*

   567 Out:

   568   (lenRes == 1) && (backRes == 0xFFFFFFFF) means Literal

   569 */

   570 

   571 UInt32 CEncoder::GetOptimum(UInt32 position, UInt32 &backRes)

   572 {

   573   if(_optimumEndIndex != _optimumCurrentIndex)

   574   {

   575     const COptimal &optimum = _optimum[_optimumCurrentIndex];

   576     UInt32 lenRes = optimum.PosPrev - _optimumCurrentIndex;

   577     backRes = optimum.BackPrev;

   578     _optimumCurrentIndex = optimum.PosPrev;

   579     return lenRes;

   580   }

   581   _optimumCurrentIndex = _optimumEndIndex = 0;

   582   

   583   UInt32 numAvailableBytes = _matchFinder.GetNumAvailableBytes(_matchFinderObj);

   584 

   585   UInt32 lenMain, numDistancePairs;

   586   if (!_longestMatchWasFound)

   587   {

   588     lenMain = ReadMatchDistances(numDistancePairs);

   589   }

   590   else

   591   {

   592     lenMain = _longestMatchLength;

   593     numDistancePairs = _numDistancePairs;

   594     _longestMatchWasFound = false;

   595   }

   596 

   597   const Byte *data = _matchFinder.GetPointerToCurrentPos(_matchFinderObj) - 1;

   598   if (numAvailableBytes < 2)

   599   {

   600     backRes = (UInt32)(-1);

   601     return 1;

   602   }

   603   if (numAvailableBytes > kMatchMaxLen)

   604     numAvailableBytes = kMatchMaxLen;

   605 

   606   UInt32 reps[kNumRepDistances];

   607   UInt32 repLens[kNumRepDistances];

   608   UInt32 repMaxIndex = 0;

   609   UInt32 i;

   610   for(i = 0; i < kNumRepDistances; i++)

   611   {

   612     reps[i] = _repDistances[i];

   613     const Byte *data2 = data - (reps[i] + 1);

   614     if (data[0] != data2[0] || data[1] != data2[1])

   615     {

   616       repLens[i] = 0;

   617       continue;

   618     }

   619     UInt32 lenTest;

   620     for (lenTest = 2; lenTest < numAvailableBytes && data[lenTest] == data2[lenTest]; lenTest++);

   621     repLens[i] = lenTest;

   622     if (lenTest > repLens[repMaxIndex])

   623       repMaxIndex = i;

   624   }

   625   if(repLens[repMaxIndex] >= _numFastBytes)

   626   {

   627     backRes = repMaxIndex;

   628     UInt32 lenRes = repLens[repMaxIndex];

   629     MovePos(lenRes - 1);

   630     return lenRes;

   631   }

   632 

   633   UInt32 *matchDistances = _matchDistances;

   634   if(lenMain >= _numFastBytes)

   635   {

   636     backRes = matchDistances[numDistancePairs - 1] + kNumRepDistances; 

   637     MovePos(lenMain - 1);

   638     return lenMain;

   639   }

   640   Byte currentByte = *data;

   641   Byte matchByte = *(data - (reps[0] + 1));

   642 

   643   if(lenMain < 2 && currentByte != matchByte && repLens[repMaxIndex] < 2)

   644   {

   645     backRes = (UInt32)-1;

   646     return 1;

   647   }

   648 

   649   _optimum[0].State = _state;

   650 

   651   UInt32 posState = (position & _posStateMask);

   652 

   653   _optimum[1].Price = _isMatch[_state.Index][posState].GetPrice0() + 

   654       _literalEncoder.GetSubCoder(position, _previousByte)->GetPrice(!_state.IsCharState(), matchByte, currentByte);

   655   _optimum[1].MakeAsChar();

   656 

   657   UInt32 matchPrice = _isMatch[_state.Index][posState].GetPrice1();

   658   UInt32 repMatchPrice = matchPrice + _isRep[_state.Index].GetPrice1();

   659 

   660   if(matchByte == currentByte)

   661   {

   662     UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);

   663     if(shortRepPrice < _optimum[1].Price)

   664     {

   665       _optimum[1].Price = shortRepPrice;

   666       _optimum[1].MakeAsShortRep();

   667     }

   668   }

   669   UInt32 lenEnd = ((lenMain >= repLens[repMaxIndex]) ? lenMain : repLens[repMaxIndex]);

   670 

   671   if(lenEnd < 2)

   672   {

   673     backRes = _optimum[1].BackPrev;

   674     return 1;

   675   }

   676 

   677   _optimum[1].PosPrev = 0;

   678   for (i = 0; i < kNumRepDistances; i++)

   679     _optimum[0].Backs[i] = reps[i];

   680 

   681   UInt32 len = lenEnd;

   682   do

   683     _optimum[len--].Price = kIfinityPrice;

   684   while (len >= 2);

   685 

   686   for(i = 0; i < kNumRepDistances; i++)

   687   {

   688     UInt32 repLen = repLens[i];

   689     if (repLen < 2)

   690       continue;

   691     UInt32 price = repMatchPrice + GetPureRepPrice(i, _state, posState);

   692     do

   693     {

   694       UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(repLen - 2, posState);

   695       COptimal &optimum = _optimum[repLen];

   696       if (curAndLenPrice < optimum.Price) 

   697       {

   698         optimum.Price = curAndLenPrice;

   699         optimum.PosPrev = 0;

   700         optimum.BackPrev = i;

   701         optimum.Prev1IsChar = false;

   702       }

   703     }

   704     while(--repLen >= 2);

   705   }

   706 

   707   UInt32 normalMatchPrice = matchPrice + _isRep[_state.Index].GetPrice0();

   708 

   709   len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);

   710   if (len <= lenMain)

   711   {

   712     UInt32 offs = 0;

   713     while (len > matchDistances[offs])

   714       offs += 2;

   715     for(; ; len++)

   716     {

   717       UInt32 distance = matchDistances[offs + 1];

   718       UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(distance, len, posState);

   719       COptimal &optimum = _optimum[len];

   720       if (curAndLenPrice < optimum.Price) 

   721       {

   722         optimum.Price = curAndLenPrice;

   723         optimum.PosPrev = 0;

   724         optimum.BackPrev = distance + kNumRepDistances;

   725         optimum.Prev1IsChar = false;

   726       }

   727       if (len == matchDistances[offs])

   728       {

   729         offs += 2;

   730         if (offs == numDistancePairs)

   731           break;

   732       }

   733     }

   734   }

   735 

   736   UInt32 cur = 0;

   737 

   738   for (;;)

   739   {

   740     cur++;

   741     if(cur == lenEnd)

   742     {

   743       return Backward(backRes, cur);

   744     }

   745     UInt32 numAvailableBytesFull = _matchFinder.GetNumAvailableBytes(_matchFinderObj);

   746     UInt32 newLen, numDistancePairs;

   747     newLen = ReadMatchDistances(numDistancePairs);

   748     if(newLen >= _numFastBytes)

   749     {

   750       _numDistancePairs = numDistancePairs;

   751       _longestMatchLength = newLen;

   752       _longestMatchWasFound = true;

   753       return Backward(backRes, cur);

   754     }

   755     position++;

   756     COptimal &curOptimum = _optimum[cur];

   757     UInt32 posPrev = curOptimum.PosPrev;

   758     CState state;

   759     if (curOptimum.Prev1IsChar)

   760     {

   761       posPrev--;

   762       if (curOptimum.Prev2)

   763       {

   764         state = _optimum[curOptimum.PosPrev2].State;

   765         if (curOptimum.BackPrev2 < kNumRepDistances)

   766           state.UpdateRep();

   767         else

   768           state.UpdateMatch();

   769       }

   770       else

   771         state = _optimum[posPrev].State;

   772       state.UpdateChar();

   773     }

   774     else

   775       state = _optimum[posPrev].State;

   776     if (posPrev == cur - 1)

   777     {

   778       if (curOptimum.IsShortRep())

   779         state.UpdateShortRep();

   780       else

   781         state.UpdateChar();

   782     }

   783     else

   784     {

   785       UInt32 pos;

   786       if (curOptimum.Prev1IsChar && curOptimum.Prev2)

   787       {

   788         posPrev = curOptimum.PosPrev2;

   789         pos = curOptimum.BackPrev2;

   790         state.UpdateRep();

   791       }

   792       else

   793       {

   794         pos = curOptimum.BackPrev;

   795         if (pos < kNumRepDistances)

   796           state.UpdateRep();

   797         else

   798           state.UpdateMatch();

   799       }

   800       const COptimal &prevOptimum = _optimum[posPrev];

   801       if (pos < kNumRepDistances)

   802       {

   803         reps[0] = prevOptimum.Backs[pos];

   804         UInt32 i;

   805         for(i = 1; i <= pos; i++)

   806           reps[i] = prevOptimum.Backs[i - 1];

   807         for(; i < kNumRepDistances; i++)

   808           reps[i] = prevOptimum.Backs[i];

   809       }

   810       else

   811       {

   812         reps[0] = (pos - kNumRepDistances);

   813         for(UInt32 i = 1; i < kNumRepDistances; i++)

   814           reps[i] = prevOptimum.Backs[i - 1];

   815       }

   816     }

   817     curOptimum.State = state;

   818     for(UInt32 i = 0; i < kNumRepDistances; i++)

   819       curOptimum.Backs[i] = reps[i];

   820     UInt32 curPrice = curOptimum.Price; 

   821     const Byte *data = _matchFinder.GetPointerToCurrentPos(_matchFinderObj) - 1;

   822     const Byte currentByte = *data;

   823     const Byte matchByte = *(data - (reps[0] + 1));

   824 

   825     UInt32 posState = (position & _posStateMask);

   826 

   827     UInt32 curAnd1Price = curPrice +

   828         _isMatch[state.Index][posState].GetPrice0() +

   829         _literalEncoder.GetSubCoder(position, *(data - 1))->GetPrice(!state.IsCharState(), matchByte, currentByte);

   830 

   831     COptimal &nextOptimum = _optimum[cur + 1];

   832 

   833     bool nextIsChar = false;

   834     if (curAnd1Price < nextOptimum.Price) 

   835     {

   836       nextOptimum.Price = curAnd1Price;

   837       nextOptimum.PosPrev = cur;

   838       nextOptimum.MakeAsChar();

   839       nextIsChar = true;

   840     }

   841 

   842     UInt32 matchPrice = curPrice + _isMatch[state.Index][posState].GetPrice1();

   843     UInt32 repMatchPrice = matchPrice + _isRep[state.Index].GetPrice1();

   844     

   845     if(matchByte == currentByte &&

   846         !(nextOptimum.PosPrev < cur && nextOptimum.BackPrev == 0))

   847     {

   848       UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(state, posState);

   849       if(shortRepPrice <= nextOptimum.Price)

   850       {

   851         nextOptimum.Price = shortRepPrice;

   852         nextOptimum.PosPrev = cur;

   853         nextOptimum.MakeAsShortRep();

   854         nextIsChar = true;

   855       }

   856     }

   857     /*

   858     if(newLen == 2 && matchDistances[2] >= kDistLimit2) // test it maybe set 2000 ?

   859       continue;

   860     */

   861 

   862     numAvailableBytesFull = MyMin(kNumOpts - 1 - cur, numAvailableBytesFull);

   863     UInt32 numAvailableBytes = numAvailableBytesFull;

   864 

   865     if (numAvailableBytes < 2)

   866       continue;

   867     if (numAvailableBytes > _numFastBytes)

   868       numAvailableBytes = _numFastBytes;

   869     if (!nextIsChar && matchByte != currentByte) // speed optimization

   870     {

   871       // try Literal + rep0

   872       const Byte *data2 = data - (reps[0] + 1);

   873       UInt32 limit = MyMin(numAvailableBytesFull, _numFastBytes + 1);

   874       UInt32 temp;

   875       for (temp = 1; temp < limit && data[temp] == data2[temp]; temp++);

   876       UInt32 lenTest2 = temp - 1;

   877       if (lenTest2 >= 2)

   878       {

   879         CState state2 = state;

   880         state2.UpdateChar();

   881         UInt32 posStateNext = (position + 1) & _posStateMask;

   882         UInt32 nextRepMatchPrice = curAnd1Price + 

   883             _isMatch[state2.Index][posStateNext].GetPrice1() +

   884             _isRep[state2.Index].GetPrice1();

   885         // for (; lenTest2 >= 2; lenTest2--)

   886         {

   887           UInt32 offset = cur + 1 + lenTest2;

   888           while(lenEnd < offset)

   889             _optimum[++lenEnd].Price = kIfinityPrice;

   890           UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(

   891               0, lenTest2, state2, posStateNext);

   892           COptimal &optimum = _optimum[offset];

   893           if (curAndLenPrice < optimum.Price) 

   894           {

   895             optimum.Price = curAndLenPrice;

   896             optimum.PosPrev = cur + 1;

   897             optimum.BackPrev = 0;

   898             optimum.Prev1IsChar = true;

   899             optimum.Prev2 = false;

   900           }

   901         }

   902       }

   903     }

   904     

   905     UInt32 startLen = 2; // speed optimization 

   906     for(UInt32 repIndex = 0; repIndex < kNumRepDistances; repIndex++)

   907     {

   908       // UInt32 repLen = _matchFinder.GetMatchLen(0 - 1, reps[repIndex], newLen); // test it;

   909       const Byte *data2 = data - (reps[repIndex] + 1);

   910       if (data[0] != data2[0] || data[1] != data2[1])

   911         continue;

   912       UInt32 lenTest;

   913       for (lenTest = 2; lenTest < numAvailableBytes && data[lenTest] == data2[lenTest]; lenTest++);

   914       while(lenEnd < cur + lenTest)

   915         _optimum[++lenEnd].Price = kIfinityPrice;

   916       UInt32 lenTestTemp = lenTest;

   917       UInt32 price = repMatchPrice + GetPureRepPrice(repIndex, state, posState);

   918       do

   919       {

   920         UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(lenTest - 2, posState);

   921         COptimal &optimum = _optimum[cur + lenTest];

   922         if (curAndLenPrice < optimum.Price) 

   923         {

   924           optimum.Price = curAndLenPrice;

   925           optimum.PosPrev = cur;

   926           optimum.BackPrev = repIndex;

   927           optimum.Prev1IsChar = false;

   928         }

   929       }

   930       while(--lenTest >= 2);

   931       lenTest = lenTestTemp;

   932       

   933       if (repIndex == 0)

   934         startLen = lenTest + 1;

   935         

   936       // if (_maxMode)

   937         {

   938           UInt32 lenTest2 = lenTest + 1;

   939           UInt32 limit = MyMin(numAvailableBytesFull, lenTest2 + _numFastBytes);

   940           for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);

   941           lenTest2 -= lenTest + 1;

   942           if (lenTest2 >= 2)

   943           {

   944             CState state2 = state;

   945             state2.UpdateRep();

   946             UInt32 posStateNext = (position + lenTest) & _posStateMask;

   947             UInt32 curAndLenCharPrice = 

   948                 price + _repMatchLenEncoder.GetPrice(lenTest - 2, posState) + 

   949                 _isMatch[state2.Index][posStateNext].GetPrice0() +

   950                 _literalEncoder.GetSubCoder(position + lenTest, data[lenTest - 1])->GetPrice(

   951                 true, data2[lenTest], data[lenTest]);

   952             state2.UpdateChar();

   953             posStateNext = (position + lenTest + 1) & _posStateMask;

   954             UInt32 nextRepMatchPrice = curAndLenCharPrice + 

   955                 _isMatch[state2.Index][posStateNext].GetPrice1() +

   956                 _isRep[state2.Index].GetPrice1();

   957             

   958             // for(; lenTest2 >= 2; lenTest2--)

   959             {

   960               UInt32 offset = cur + lenTest + 1 + lenTest2;

   961               while(lenEnd < offset)

   962                 _optimum[++lenEnd].Price = kIfinityPrice;

   963               UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(

   964                   0, lenTest2, state2, posStateNext);

   965               COptimal &optimum = _optimum[offset];

   966               if (curAndLenPrice < optimum.Price) 

   967               {

   968                 optimum.Price = curAndLenPrice;

   969                 optimum.PosPrev = cur + lenTest + 1;

   970                 optimum.BackPrev = 0;

   971                 optimum.Prev1IsChar = true;

   972                 optimum.Prev2 = true;

   973                 optimum.PosPrev2 = cur;

   974                 optimum.BackPrev2 = repIndex;

   975               }

   976             }

   977           }

   978         }

   979       }

   980     

   981     //    for(UInt32 lenTest = 2; lenTest <= newLen; lenTest++)

   982     if (newLen > numAvailableBytes)

   983     {

   984       newLen = numAvailableBytes;

   985       for (numDistancePairs = 0; newLen > matchDistances[numDistancePairs]; numDistancePairs += 2);

   986       matchDistances[numDistancePairs] = newLen;

   987       numDistancePairs += 2;

   988     }

   989     if (newLen >= startLen)

   990     {

   991       UInt32 normalMatchPrice = matchPrice + _isRep[state.Index].GetPrice0();

   992       while(lenEnd < cur + newLen)

   993         _optimum[++lenEnd].Price = kIfinityPrice;

   994 

   995       UInt32 offs = 0;

   996       while(startLen > matchDistances[offs])

   997         offs += 2;

   998       UInt32 curBack = matchDistances[offs + 1];

   999       UInt32 posSlot = GetPosSlot2(curBack);

  1000       for(UInt32 lenTest = /*2*/ startLen; ; lenTest++)

  1001       {

  1002         UInt32 curAndLenPrice = normalMatchPrice;

  1003         UInt32 lenToPosState = GetLenToPosState(lenTest);

  1004         if (curBack < kNumFullDistances)

  1005           curAndLenPrice += _distancesPrices[lenToPosState][curBack];

  1006         else

  1007           curAndLenPrice += _posSlotPrices[lenToPosState][posSlot] + _alignPrices[curBack & kAlignMask];

  1008   

  1009         curAndLenPrice += _lenEncoder.GetPrice(lenTest - kMatchMinLen, posState);

  1010         

  1011         COptimal &optimum = _optimum[cur + lenTest];

  1012         if (curAndLenPrice < optimum.Price) 

  1013         {

  1014           optimum.Price = curAndLenPrice;

  1015           optimum.PosPrev = cur;

  1016           optimum.BackPrev = curBack + kNumRepDistances;

  1017           optimum.Prev1IsChar = false;

  1018         }

  1019 

  1020         if (/*_maxMode && */lenTest == matchDistances[offs])

  1021         {

  1022           // Try Match + Literal + Rep0

  1023           const Byte *data2 = data - (curBack + 1);

  1024           UInt32 lenTest2 = lenTest + 1;

  1025           UInt32 limit = MyMin(numAvailableBytesFull, lenTest2 + _numFastBytes);

  1026           for (; lenTest2 < limit && data[lenTest2] == data2[lenTest2]; lenTest2++);

  1027           lenTest2 -= lenTest + 1;

  1028           if (lenTest2 >= 2)

  1029           {

  1030             CState state2 = state;

  1031             state2.UpdateMatch();

  1032             UInt32 posStateNext = (position + lenTest) & _posStateMask;

  1033             UInt32 curAndLenCharPrice = curAndLenPrice + 

  1034                 _isMatch[state2.Index][posStateNext].GetPrice0() +

  1035                 _literalEncoder.GetSubCoder(position + lenTest, data[lenTest - 1])->GetPrice( 

  1036                 true, data2[lenTest], data[lenTest]);

  1037             state2.UpdateChar();

  1038             posStateNext = (posStateNext + 1) & _posStateMask;

  1039             UInt32 nextRepMatchPrice = curAndLenCharPrice + 

  1040                 _isMatch[state2.Index][posStateNext].GetPrice1() +

  1041                 _isRep[state2.Index].GetPrice1();

  1042             

  1043             // for(; lenTest2 >= 2; lenTest2--)

  1044             {

  1045               UInt32 offset = cur + lenTest + 1 + lenTest2;

  1046               while(lenEnd < offset)

  1047                 _optimum[++lenEnd].Price = kIfinityPrice;

  1048               UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(0, lenTest2, state2, posStateNext);

  1049               COptimal &optimum = _optimum[offset];

  1050               if (curAndLenPrice < optimum.Price) 

  1051               {

  1052                 optimum.Price = curAndLenPrice;

  1053                 optimum.PosPrev = cur + lenTest + 1;

  1054                 optimum.BackPrev = 0;

  1055                 optimum.Prev1IsChar = true;

  1056                 optimum.Prev2 = true;

  1057                 optimum.PosPrev2 = cur;

  1058                 optimum.BackPrev2 = curBack + kNumRepDistances;

  1059               }

  1060             }

  1061           }

  1062           offs += 2;

  1063           if (offs == numDistancePairs)

  1064             break;

  1065           curBack = matchDistances[offs + 1];

  1066           if (curBack >= kNumFullDistances)

  1067             posSlot = GetPosSlot2(curBack);

  1068         }

  1069       }

  1070     }

  1071   }

  1072 }

  1073 

  1074 static inline bool ChangePair(UInt32 smallDist, UInt32 bigDist)

  1075 {

  1076   return ((bigDist >> 7) > smallDist);

  1077 }

  1078 

  1079 UInt32 CEncoder::ReadMatchDistances(UInt32 &numDistancePairs)

  1080 {

  1081   UInt32 lenRes = 0;

  1082   numDistancePairs = _matchFinder.GetMatches(_matchFinderObj, _matchDistances);

  1083   #ifdef SHOW_STAT

  1084   printf("\n i = %d numPairs = %d    ", ttt, numDistancePairs / 2);

  1085   if (ttt >= 61994)

  1086     ttt = ttt;

  1087 

  1088   ttt++;

  1089   for (UInt32 i = 0; i < numDistancePairs; i += 2)

  1090     printf("%2d %6d   | ", _matchDistances[i], _matchDistances[i + 1]);

  1091   #endif

  1092   if (numDistancePairs > 0)

  1093   {

  1094     lenRes = _matchDistances[numDistancePairs - 2];

  1095     if (lenRes == _numFastBytes)

  1096     {

  1097       UInt32 numAvail = _matchFinder.GetNumAvailableBytes(_matchFinderObj) + 1;

  1098       const Byte *pby = _matchFinder.GetPointerToCurrentPos(_matchFinderObj) - 1;

  1099       UInt32 distance = _matchDistances[numDistancePairs - 1] + 1;

  1100       if (numAvail > kMatchMaxLen)

  1101         numAvail = kMatchMaxLen;

  1102 

  1103       const Byte *pby2 = pby - distance;

  1104       for (; lenRes < numAvail && pby[lenRes] == pby2[lenRes]; lenRes++);

  1105     }

  1106   }

  1107   _additionalOffset++;

  1108   return lenRes;

  1109 }

  1110 

  1111 UInt32 CEncoder::GetOptimumFast(UInt32 &backRes)

  1112 {

  1113   UInt32 numAvailableBytes = _matchFinder.GetNumAvailableBytes(_matchFinderObj);

  1114   UInt32 lenMain, numDistancePairs;

  1115   if (!_longestMatchWasFound)

  1116   {

  1117     lenMain = ReadMatchDistances(numDistancePairs);

  1118   }

  1119   else

  1120   {

  1121     lenMain = _longestMatchLength;

  1122     numDistancePairs = _numDistancePairs;

  1123     _longestMatchWasFound = false;

  1124   }

  1125 

  1126   const Byte *data = _matchFinder.GetPointerToCurrentPos(_matchFinderObj) - 1;

  1127   if (numAvailableBytes > kMatchMaxLen)

  1128     numAvailableBytes = kMatchMaxLen;

  1129   if (numAvailableBytes < 2)

  1130   {

  1131     backRes = (UInt32)(-1);

  1132     return 1;

  1133   }

  1134 

  1135   UInt32 repLens[kNumRepDistances];