misc/libphysfs/lzma/CPP/7zip/Compress/LZMA/LZMAEncoder.cpp
changeset 12213 bb5522e88ab2
equal deleted inserted replaced
12212:ea891871f481 12213:bb5522e88ab2
       
     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];
       
  1136   UInt32 repMaxIndex = 0;
       
  1137 
       
  1138   for(UInt32 i = 0; i < kNumRepDistances; i++)
       
  1139   {
       
  1140     const Byte *data2 = data - (_repDistances[i] + 1);
       
  1141     if (data[0] != data2[0] || data[1] != data2[1])
       
  1142     {
       
  1143       repLens[i] = 0;
       
  1144       continue;
       
  1145     }
       
  1146     UInt32 len;
       
  1147     for (len = 2; len < numAvailableBytes && data[len] == data2[len]; len++);
       
  1148     if(len >= _numFastBytes)
       
  1149     {
       
  1150       backRes = i;
       
  1151       MovePos(len - 1);
       
  1152       return len;
       
  1153     }
       
  1154     repLens[i] = len;
       
  1155     if (len > repLens[repMaxIndex])
       
  1156       repMaxIndex = i;
       
  1157   }
       
  1158   UInt32 *matchDistances = _matchDistances;
       
  1159   if(lenMain >= _numFastBytes)
       
  1160   {
       
  1161     backRes = matchDistances[numDistancePairs - 1] + kNumRepDistances; 
       
  1162     MovePos(lenMain - 1);
       
  1163     return lenMain;
       
  1164   }
       
  1165 
       
  1166   UInt32 backMain = 0; // for GCC
       
  1167   if (lenMain >= 2)
       
  1168   {
       
  1169     backMain = matchDistances[numDistancePairs - 1];
       
  1170     while (numDistancePairs > 2 && lenMain == matchDistances[numDistancePairs - 4] + 1)
       
  1171     {
       
  1172       if (!ChangePair(matchDistances[numDistancePairs - 3], backMain))
       
  1173         break;
       
  1174       numDistancePairs -= 2;
       
  1175       lenMain = matchDistances[numDistancePairs - 2];
       
  1176       backMain = matchDistances[numDistancePairs - 1];
       
  1177     }
       
  1178     if (lenMain == 2 && backMain >= 0x80)
       
  1179       lenMain = 1;
       
  1180   }
       
  1181 
       
  1182   if (repLens[repMaxIndex] >= 2)
       
  1183   {
       
  1184     if (repLens[repMaxIndex] + 1 >= lenMain || 
       
  1185         repLens[repMaxIndex] + 2 >= lenMain && (backMain > (1 << 9)) ||
       
  1186         repLens[repMaxIndex] + 3 >= lenMain && (backMain > (1 << 15)))
       
  1187     {
       
  1188       backRes = repMaxIndex;
       
  1189       UInt32 lenRes = repLens[repMaxIndex];
       
  1190       MovePos(lenRes - 1);
       
  1191       return lenRes;
       
  1192     }
       
  1193   }
       
  1194   
       
  1195   if (lenMain >= 2 && numAvailableBytes > 2)
       
  1196   {
       
  1197     numAvailableBytes = _matchFinder.GetNumAvailableBytes(_matchFinderObj);
       
  1198     _longestMatchLength = ReadMatchDistances(_numDistancePairs);
       
  1199     if (_longestMatchLength >= 2)
       
  1200     {
       
  1201       UInt32 newDistance = matchDistances[_numDistancePairs - 1];
       
  1202       if (_longestMatchLength >= lenMain && newDistance < backMain || 
       
  1203           _longestMatchLength == lenMain + 1 && !ChangePair(backMain, newDistance) ||
       
  1204           _longestMatchLength > lenMain + 1 ||
       
  1205           _longestMatchLength + 1 >= lenMain && lenMain >= 3 && ChangePair(newDistance, backMain))
       
  1206       {
       
  1207         _longestMatchWasFound = true;
       
  1208         backRes = UInt32(-1);
       
  1209         return 1;
       
  1210       }
       
  1211     }
       
  1212     data = _matchFinder.GetPointerToCurrentPos(_matchFinderObj) - 1;
       
  1213     for(UInt32 i = 0; i < kNumRepDistances; i++)
       
  1214     {
       
  1215       const Byte *data2 = data - (_repDistances[i] + 1);
       
  1216       if (data[1] != data2[1] || data[2] != data2[2])
       
  1217       {
       
  1218         repLens[i] = 0;
       
  1219         continue;
       
  1220       }
       
  1221       UInt32 len;
       
  1222       for (len = 2; len < numAvailableBytes && data[len] == data2[len]; len++);
       
  1223       if (len + 1 >= lenMain)
       
  1224       {
       
  1225         _longestMatchWasFound = true;
       
  1226         backRes = UInt32(-1);
       
  1227         return 1;
       
  1228       }
       
  1229     }
       
  1230     backRes = backMain + kNumRepDistances; 
       
  1231     MovePos(lenMain - 2);
       
  1232     return lenMain;
       
  1233   }
       
  1234   backRes = UInt32(-1);
       
  1235   return 1;
       
  1236 }
       
  1237 
       
  1238 HRESULT CEncoder::Flush(UInt32 nowPos)
       
  1239 {
       
  1240   // ReleaseMFStream();
       
  1241   if (_matchFinderBase.result != SZ_OK)
       
  1242     return _matchFinderBase.result;
       
  1243   WriteEndMarker(nowPos & _posStateMask);
       
  1244   _rangeEncoder.FlushData();
       
  1245   return _rangeEncoder.FlushStream();
       
  1246 }
       
  1247 
       
  1248 void CEncoder::WriteEndMarker(UInt32 posState)
       
  1249 {
       
  1250   // This function for writing End Mark for stream version of LZMA. 
       
  1251   // In current version this feature is not used.
       
  1252   if (!_writeEndMark)
       
  1253     return;
       
  1254 
       
  1255   _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1);
       
  1256   _isRep[_state.Index].Encode(&_rangeEncoder, 0);
       
  1257   _state.UpdateMatch();
       
  1258   UInt32 len = kMatchMinLen; // kMatchMaxLen;
       
  1259   _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode);
       
  1260   UInt32 posSlot = (1 << kNumPosSlotBits)  - 1;
       
  1261   UInt32 lenToPosState = GetLenToPosState(len);
       
  1262   _posSlotEncoder[lenToPosState].Encode(&_rangeEncoder, posSlot);
       
  1263   UInt32 footerBits = 30;
       
  1264   UInt32 posReduced = (UInt32(1) << footerBits) - 1;
       
  1265   _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
       
  1266   _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask);
       
  1267 }
       
  1268 
       
  1269 HRESULT CEncoder::CodeReal(ISequentialInStream *inStream,
       
  1270       ISequentialOutStream *outStream, 
       
  1271       const UInt64 *inSize, const UInt64 *outSize,
       
  1272       ICompressProgressInfo *progress)
       
  1273 {
       
  1274   // _needReleaseMFStream = false;
       
  1275   #ifdef COMPRESS_MF_MT
       
  1276   #ifdef USE_ALLOCA
       
  1277   alloca(0x300);
       
  1278   #endif
       
  1279   #endif
       
  1280   CCoderReleaser coderReleaser(this);
       
  1281   RINOK(SetStreams(inStream, outStream, inSize, outSize));
       
  1282   for (;;)
       
  1283   {
       
  1284     UInt64 processedInSize;
       
  1285     UInt64 processedOutSize;
       
  1286     Int32 finished;
       
  1287     RINOK(CodeOneBlock(&processedInSize, &processedOutSize, &finished));
       
  1288     if (finished != 0)
       
  1289       break;
       
  1290     if (progress != 0)
       
  1291     {
       
  1292       RINOK(progress->SetRatioInfo(&processedInSize, &processedOutSize));
       
  1293     }
       
  1294   }
       
  1295   return S_OK;
       
  1296 }
       
  1297 
       
  1298 HRESULT CEncoder::SetStreams(ISequentialInStream *inStream,
       
  1299       ISequentialOutStream *outStream, 
       
  1300       const UInt64 * /* inSize */, const UInt64 * /* outSize */)
       
  1301 {
       
  1302   _inStream = inStream;
       
  1303   _finished = false;
       
  1304   RINOK(Create());
       
  1305   RINOK(SetOutStream(outStream));
       
  1306   RINOK(Init());
       
  1307   
       
  1308   if (!_fastMode)
       
  1309   {
       
  1310     FillDistancesPrices();
       
  1311     FillAlignPrices();
       
  1312   }
       
  1313 
       
  1314   _lenEncoder.SetTableSize(_numFastBytes + 1 - kMatchMinLen);
       
  1315   _lenEncoder.UpdateTables(1 << _posStateBits);
       
  1316   _repMatchLenEncoder.SetTableSize(_numFastBytes + 1 - kMatchMinLen);
       
  1317   _repMatchLenEncoder.UpdateTables(1 << _posStateBits);
       
  1318 
       
  1319   nowPos64 = 0;
       
  1320   return S_OK;
       
  1321 }
       
  1322 
       
  1323 static HRes MyRead(void *object, void *data, UInt32 size, UInt32 *processedSize)
       
  1324 {
       
  1325   return (HRes)((CSeqInStream *)object)->RealStream->Read(data, size, processedSize);
       
  1326 }
       
  1327 
       
  1328 HRESULT CEncoder::CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished)
       
  1329 {
       
  1330   if (_inStream != 0)
       
  1331   {
       
  1332     _seqInStream.RealStream = _inStream;
       
  1333     _seqInStream.SeqInStream.Read = MyRead;
       
  1334     _matchFinderBase.stream = &_seqInStream.SeqInStream;
       
  1335     _matchFinder.Init(_matchFinderObj);
       
  1336     _needReleaseMFStream = true;
       
  1337     _inStream = 0;
       
  1338   }
       
  1339 
       
  1340 
       
  1341   *finished = 1;
       
  1342   if (_finished)
       
  1343     return _matchFinderBase.result;
       
  1344   _finished = true;
       
  1345 
       
  1346   if (nowPos64 == 0)
       
  1347   {
       
  1348     if (_matchFinder.GetNumAvailableBytes(_matchFinderObj) == 0)
       
  1349       return Flush((UInt32)nowPos64);
       
  1350     UInt32 len, numDistancePairs;
       
  1351     len = ReadMatchDistances(numDistancePairs);
       
  1352     UInt32 posState = UInt32(nowPos64) & _posStateMask;
       
  1353     _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0);
       
  1354     _state.UpdateChar();
       
  1355     Byte curByte = _matchFinder.GetIndexByte(_matchFinderObj, 0 - _additionalOffset);
       
  1356     _literalEncoder.GetSubCoder(UInt32(nowPos64), _previousByte)->Encode(&_rangeEncoder, curByte);
       
  1357     _previousByte = curByte;
       
  1358     _additionalOffset--;
       
  1359     nowPos64++;
       
  1360   }
       
  1361 
       
  1362   UInt32 nowPos32 = (UInt32)nowPos64;
       
  1363   UInt32 progressPosValuePrev = nowPos32;
       
  1364 
       
  1365   if (_matchFinder.GetNumAvailableBytes(_matchFinderObj) == 0)
       
  1366     return Flush(nowPos32);
       
  1367 
       
  1368   for (;;)
       
  1369   {
       
  1370     #ifdef _NO_EXCEPTIONS
       
  1371     if (_rangeEncoder.Stream.ErrorCode != S_OK)
       
  1372       return _rangeEncoder.Stream.ErrorCode;
       
  1373     #endif
       
  1374     UInt32 pos, len;
       
  1375 
       
  1376     if (_fastMode)
       
  1377       len = GetOptimumFast(pos);
       
  1378     else
       
  1379       len = GetOptimum(nowPos32, pos);
       
  1380 
       
  1381     UInt32 posState = nowPos32 & _posStateMask;
       
  1382     if(len == 1 && pos == 0xFFFFFFFF)
       
  1383     {
       
  1384       _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0);
       
  1385       Byte curByte = _matchFinder.GetIndexByte(_matchFinderObj, 0 - _additionalOffset);
       
  1386       CLiteralEncoder2 *subCoder = _literalEncoder.GetSubCoder(nowPos32, _previousByte);
       
  1387       if(_state.IsCharState())
       
  1388         subCoder->Encode(&_rangeEncoder, curByte);
       
  1389       else
       
  1390       {
       
  1391         Byte matchByte = _matchFinder.GetIndexByte(_matchFinderObj, 0 - _repDistances[0] - 1 - _additionalOffset);
       
  1392         subCoder->EncodeMatched(&_rangeEncoder, matchByte, curByte);
       
  1393       }
       
  1394       _state.UpdateChar();
       
  1395       _previousByte = curByte;
       
  1396     }
       
  1397     else
       
  1398     {
       
  1399       _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1);
       
  1400       if(pos < kNumRepDistances)
       
  1401       {
       
  1402         _isRep[_state.Index].Encode(&_rangeEncoder, 1);
       
  1403         if(pos == 0)
       
  1404         {
       
  1405           _isRepG0[_state.Index].Encode(&_rangeEncoder, 0);
       
  1406           _isRep0Long[_state.Index][posState].Encode(&_rangeEncoder, ((len == 1) ? 0 : 1));
       
  1407         }
       
  1408         else
       
  1409         {
       
  1410           UInt32 distance = _repDistances[pos];
       
  1411           _isRepG0[_state.Index].Encode(&_rangeEncoder, 1);
       
  1412           if (pos == 1)
       
  1413             _isRepG1[_state.Index].Encode(&_rangeEncoder, 0);
       
  1414           else
       
  1415           {
       
  1416             _isRepG1[_state.Index].Encode(&_rangeEncoder, 1);
       
  1417             _isRepG2[_state.Index].Encode(&_rangeEncoder, pos - 2);
       
  1418             if (pos == 3)
       
  1419               _repDistances[3] = _repDistances[2];
       
  1420             _repDistances[2] = _repDistances[1];
       
  1421           }
       
  1422           _repDistances[1] = _repDistances[0];
       
  1423           _repDistances[0] = distance;
       
  1424         }
       
  1425         if (len == 1)
       
  1426           _state.UpdateShortRep();
       
  1427         else
       
  1428         {
       
  1429           _repMatchLenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode);
       
  1430           _state.UpdateRep();
       
  1431         }
       
  1432       }
       
  1433       else
       
  1434       {
       
  1435         _isRep[_state.Index].Encode(&_rangeEncoder, 0);
       
  1436         _state.UpdateMatch();
       
  1437         _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode);
       
  1438         pos -= kNumRepDistances;
       
  1439         UInt32 posSlot = GetPosSlot(pos);
       
  1440         _posSlotEncoder[GetLenToPosState(len)].Encode(&_rangeEncoder, posSlot);
       
  1441         
       
  1442         if (posSlot >= kStartPosModelIndex)
       
  1443         {
       
  1444           UInt32 footerBits = ((posSlot >> 1) - 1);
       
  1445           UInt32 base = ((2 | (posSlot & 1)) << footerBits);
       
  1446           UInt32 posReduced = pos - base;
       
  1447 
       
  1448           if (posSlot < kEndPosModelIndex)
       
  1449             NRangeCoder::ReverseBitTreeEncode(_posEncoders + base - posSlot - 1, 
       
  1450                 &_rangeEncoder, footerBits, posReduced);
       
  1451           else
       
  1452           {
       
  1453             _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits);
       
  1454             _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask);
       
  1455             _alignPriceCount++;
       
  1456           }
       
  1457         }
       
  1458         _repDistances[3] = _repDistances[2];
       
  1459         _repDistances[2] = _repDistances[1];
       
  1460         _repDistances[1] = _repDistances[0];
       
  1461         _repDistances[0] = pos;
       
  1462         _matchPriceCount++;
       
  1463       }
       
  1464       _previousByte = _matchFinder.GetIndexByte(_matchFinderObj, len - 1 - _additionalOffset);
       
  1465     }
       
  1466     _additionalOffset -= len;
       
  1467     nowPos32 += len;
       
  1468     if (_additionalOffset == 0)
       
  1469     {
       
  1470       if (!_fastMode)
       
  1471       {
       
  1472         if (_matchPriceCount >= (1 << 7))
       
  1473           FillDistancesPrices();
       
  1474         if (_alignPriceCount >= kAlignTableSize)
       
  1475           FillAlignPrices();
       
  1476       }
       
  1477       if (_matchFinder.GetNumAvailableBytes(_matchFinderObj) == 0)
       
  1478         return Flush(nowPos32);
       
  1479       if (nowPos32 - progressPosValuePrev >= (1 << 14))
       
  1480       {
       
  1481         nowPos64 += nowPos32 - progressPosValuePrev;
       
  1482         *inSize = nowPos64;
       
  1483         *outSize = _rangeEncoder.GetProcessedSize();
       
  1484         _finished = false;
       
  1485         *finished = 0;
       
  1486         return _matchFinderBase.result;
       
  1487       }
       
  1488     }
       
  1489   }
       
  1490 }
       
  1491 
       
  1492 STDMETHODIMP CEncoder::Code(ISequentialInStream *inStream,
       
  1493     ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize,
       
  1494     ICompressProgressInfo *progress)
       
  1495 {
       
  1496   #ifndef _NO_EXCEPTIONS
       
  1497   try 
       
  1498   { 
       
  1499   #endif
       
  1500     return CodeReal(inStream, outStream, inSize, outSize, progress); 
       
  1501   #ifndef _NO_EXCEPTIONS
       
  1502   }
       
  1503   catch(const COutBufferException &e) { return e.ErrorCode; }
       
  1504   catch(...) { return E_FAIL; }
       
  1505   #endif
       
  1506 }
       
  1507   
       
  1508 void CEncoder::FillDistancesPrices()
       
  1509 {
       
  1510   UInt32 tempPrices[kNumFullDistances];
       
  1511   for (UInt32 i = kStartPosModelIndex; i < kNumFullDistances; i++)
       
  1512   { 
       
  1513     UInt32 posSlot = GetPosSlot(i);
       
  1514     UInt32 footerBits = ((posSlot >> 1) - 1);
       
  1515     UInt32 base = ((2 | (posSlot & 1)) << footerBits);
       
  1516     tempPrices[i] = NRangeCoder::ReverseBitTreeGetPrice(_posEncoders + 
       
  1517       base - posSlot - 1, footerBits, i - base);
       
  1518   }
       
  1519 
       
  1520   for (UInt32 lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)
       
  1521   {
       
  1522     UInt32 posSlot;
       
  1523     NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumPosSlotBits> &encoder = _posSlotEncoder[lenToPosState];
       
  1524     UInt32 *posSlotPrices = _posSlotPrices[lenToPosState];
       
  1525     for (posSlot = 0; posSlot < _distTableSize; posSlot++)
       
  1526       posSlotPrices[posSlot] = encoder.GetPrice(posSlot);
       
  1527     for (posSlot = kEndPosModelIndex; posSlot < _distTableSize; posSlot++)
       
  1528       posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << NRangeCoder::kNumBitPriceShiftBits);
       
  1529 
       
  1530     UInt32 *distancesPrices = _distancesPrices[lenToPosState];
       
  1531     UInt32 i;
       
  1532     for (i = 0; i < kStartPosModelIndex; i++)
       
  1533       distancesPrices[i] = posSlotPrices[i];
       
  1534     for (; i < kNumFullDistances; i++)
       
  1535       distancesPrices[i] = posSlotPrices[GetPosSlot(i)] + tempPrices[i];
       
  1536   }
       
  1537   _matchPriceCount = 0;
       
  1538 }
       
  1539 
       
  1540 void CEncoder::FillAlignPrices()
       
  1541 {
       
  1542   for (UInt32 i = 0; i < kAlignTableSize; i++)
       
  1543     _alignPrices[i] = _posAlignEncoder.ReverseGetPrice(i);
       
  1544   _alignPriceCount = 0;
       
  1545 }
       
  1546 
       
  1547 }}