util/romtool/tools/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp

   1 // LZMA/Encoder.cpp\r
   2 \r
   3 #include "StdAfx.h"\r
   4 \r
   5 #include "../../../Common/Defs.h"\r
   6 #include "../../Common/StreamUtils.h"\r
   7 \r
   8 #include "LZMAEncoder.h"\r
   9 \r
  10 // for minimal compressing code size define these:\r
  11 // #define COMPRESS_MF_BT\r
  12 // #define COMPRESS_MF_BT4\r
  13 \r
  14 #if !defined(COMPRESS_MF_BT) && !defined(COMPRESS_MF_HC)\r
  15 #define COMPRESS_MF_BT\r
  16 #define COMPRESS_MF_HC\r
  17 #endif\r
  18 \r
  19 #ifdef COMPRESS_MF_BT\r
  20 #if !defined(COMPRESS_MF_BT2) && !defined(COMPRESS_MF_BT3) && !defined(COMPRESS_MF_BT4)\r
  21 #define COMPRESS_MF_BT2\r
  22 #define COMPRESS_MF_BT3\r
  23 #define COMPRESS_MF_BT4\r
  24 #endif\r
  25 #ifdef COMPRESS_MF_BT2\r
  26 #include "../LZ/BinTree/BinTree2.h"\r
  27 #endif\r
  28 #ifdef COMPRESS_MF_BT3\r
  29 #include "../LZ/BinTree/BinTree3.h"\r
  30 #endif\r
  31 #ifdef COMPRESS_MF_BT4\r
  32 #include "../LZ/BinTree/BinTree4.h"\r
  33 #endif\r
  34 #endif\r
  35 \r
  36 #ifdef COMPRESS_MF_HC\r
  37 #include "../LZ/HashChain/HC4.h"\r
  38 #endif\r
  39 \r
  40 #ifdef COMPRESS_MF_MT\r
  41 #include "../LZ/MT/MT.h"\r
  42 #endif\r
  43 \r
  44 namespace NCompress {\r
  45 namespace NLZMA {\r
  46 \r
  47 const int kDefaultDictionaryLogSize = 22;\r
  48 const UInt32 kNumFastBytesDefault = 0x20;\r
  49 \r
  50 enum \r
  51 {\r
  52   kBT2,\r
  53   kBT3,\r
  54   kBT4,\r
  55   kHC4\r
  56 };\r
  57 \r
  58 static const wchar_t *kMatchFinderIDs[] = \r
  59 {\r
  60   L"BT2",\r
  61   L"BT3",\r
  62   L"BT4",\r
  63   L"HC4"\r
  64 };\r
  65 \r
  66 Byte g_FastPos[1 << 11];\r
  67 \r
  68 class CFastPosInit\r
  69 {\r
  70 public:\r
  71   CFastPosInit() { Init(); }\r
  72   void Init()\r
  73   {\r
  74     const Byte kFastSlots = 22;\r
  75     int c = 2;\r
  76     g_FastPos[0] = 0;\r
  77     g_FastPos[1] = 1;\r
  78 \r
  79     for (Byte slotFast = 2; slotFast < kFastSlots; slotFast++)\r
  80     {\r
  81       UInt32 k = (1 << ((slotFast >> 1) - 1));\r
  82       for (UInt32 j = 0; j < k; j++, c++)\r
  83         g_FastPos[c] = slotFast;\r
  84     }\r
  85   }\r
  86 } g_FastPosInit;\r
  87 \r
  88 \r
  89 void CLiteralEncoder2::Encode(NRangeCoder::CEncoder *rangeEncoder, Byte symbol)\r
  90 {\r
  91   UInt32 context = 1;\r
  92   int i = 8;\r
  93   do \r
  94   {\r
  95     i--;\r
  96     UInt32 bit = (symbol >> i) & 1;\r
  97     _encoders[context].Encode(rangeEncoder, bit);\r
  98     context = (context << 1) | bit;\r
  99   }\r
 100   while(i != 0);\r
 101 }\r
 102 \r
 103 void CLiteralEncoder2::EncodeMatched(NRangeCoder::CEncoder *rangeEncoder, \r
 104     Byte matchByte, Byte symbol)\r
 105 {\r
 106   UInt32 context = 1;\r
 107   int i = 8;\r
 108   do \r
 109   {\r
 110     i--;\r
 111     UInt32 bit = (symbol >> i) & 1;\r
 112     UInt32 matchBit = (matchByte >> i) & 1;\r
 113     _encoders[0x100 + (matchBit << 8) + context].Encode(rangeEncoder, bit);\r
 114     context = (context << 1) | bit;\r
 115     if (matchBit != bit)\r
 116     {\r
 117       while(i != 0)\r
 118       {\r
 119         i--;\r
 120         UInt32 bit = (symbol >> i) & 1;\r
 121         _encoders[context].Encode(rangeEncoder, bit);\r
 122         context = (context << 1) | bit;\r
 123       }\r
 124       break;\r
 125     }\r
 126   }\r
 127   while(i != 0);\r
 128 }\r
 129 \r
 130 UInt32 CLiteralEncoder2::GetPrice(bool matchMode, Byte matchByte, Byte symbol) const\r
 131 {\r
 132   UInt32 price = 0;\r
 133   UInt32 context = 1;\r
 134   int i = 8;\r
 135   if (matchMode)\r
 136   {\r
 137     do \r
 138     {\r
 139       i--;\r
 140       UInt32 matchBit = (matchByte >> i) & 1;\r
 141       UInt32 bit = (symbol >> i) & 1;\r
 142       price += _encoders[0x100 + (matchBit << 8) + context].GetPrice(bit);\r
 143       context = (context << 1) | bit;\r
 144       if (matchBit != bit)\r
 145         break;\r
 146     }\r
 147     while (i != 0);\r
 148   }\r
 149   while(i != 0)\r
 150   {\r
 151     i--;\r
 152     UInt32 bit = (symbol >> i) & 1;\r
 153     price += _encoders[context].GetPrice(bit);\r
 154     context = (context << 1) | bit;\r
 155   }\r
 156   return price;\r
 157 };\r
 158 \r
 159 \r
 160 namespace NLength {\r
 161 \r
 162 void CEncoder::Init(UInt32 numPosStates)\r
 163 {\r
 164   _choice.Init();\r
 165   _choice2.Init();\r
 166   for (UInt32 posState = 0; posState < numPosStates; posState++)\r
 167   {\r
 168     _lowCoder[posState].Init();\r
 169     _midCoder[posState].Init();\r
 170   }\r
 171   _highCoder.Init();\r
 172 }\r
 173 \r
 174 void CEncoder::Encode(NRangeCoder::CEncoder *rangeEncoder, UInt32 symbol, UInt32 posState)\r
 175 {\r
 176   if(symbol < kNumLowSymbols)\r
 177   {\r
 178     _choice.Encode(rangeEncoder, 0);\r
 179     _lowCoder[posState].Encode(rangeEncoder, symbol);\r
 180   }\r
 181   else\r
 182   {\r
 183     _choice.Encode(rangeEncoder, 1);\r
 184     if(symbol < kNumLowSymbols + kNumMidSymbols)\r
 185     {\r
 186       _choice2.Encode(rangeEncoder, 0);\r
 187       _midCoder[posState].Encode(rangeEncoder, symbol - kNumLowSymbols);\r
 188     }\r
 189     else\r
 190     {\r
 191       _choice2.Encode(rangeEncoder, 1);\r
 192       _highCoder.Encode(rangeEncoder, symbol - kNumLowSymbols - kNumMidSymbols);\r
 193     }\r
 194   }\r
 195 }\r
 196 \r
 197 void CEncoder::SetPrices(UInt32 posState, UInt32 numSymbols, UInt32 *prices) const\r
 198 {\r
 199   UInt32 a0 = _choice.GetPrice0();\r
 200   UInt32 a1 = _choice.GetPrice1();\r
 201   UInt32 b0 = a1 + _choice2.GetPrice0();\r
 202   UInt32 b1 = a1 + _choice2.GetPrice1();\r
 203   UInt32 i = 0;\r
 204   for (i = 0; i < kNumLowSymbols; i++)\r
 205   {\r
 206     if (i >= numSymbols)\r
 207       return;\r
 208     prices[i] = a0 + _lowCoder[posState].GetPrice(i);\r
 209   }\r
 210   for (; i < kNumLowSymbols + kNumMidSymbols; i++)\r
 211   {\r
 212     if (i >= numSymbols)\r
 213       return;\r
 214     prices[i] = b0 + _midCoder[posState].GetPrice(i - kNumLowSymbols);\r
 215   }\r
 216   for (; i < numSymbols; i++)\r
 217     prices[i] = b1 + _highCoder.GetPrice(i - kNumLowSymbols - kNumMidSymbols);\r
 218 }\r
 219 \r
 220 }\r
 221 CEncoder::CEncoder():\r
 222   _numFastBytes(kNumFastBytesDefault),\r
 223   _distTableSize(kDefaultDictionaryLogSize * 2),\r
 224   _posStateBits(2),\r
 225   _posStateMask(4 - 1),\r
 226   _numLiteralPosStateBits(0),\r
 227   _numLiteralContextBits(3),\r
 228   _dictionarySize(1 << kDefaultDictionaryLogSize),\r
 229   _dictionarySizePrev(UInt32(-1)),\r
 230   _numFastBytesPrev(UInt32(-1)),\r
 231   _matchFinderCycles(0),\r
 232   _matchFinderIndex(kBT4),\r
 233    #ifdef COMPRESS_MF_MT\r
 234   _multiThread(false),\r
 235    #endif\r
 236   _writeEndMark(false),\r
 237   setMfPasses(0)\r
 238 {\r
 239   // _maxMode = false;\r
 240   _fastMode = false;\r
 241 }\r
 242 \r
 243 HRESULT CEncoder::Create()\r
 244 {\r
 245   if (!_rangeEncoder.Create(1 << 20))\r
 246     return E_OUTOFMEMORY;\r
 247   if (!_matchFinder)\r
 248   {\r
 249     switch(_matchFinderIndex)\r
 250     {\r
 251       #ifdef COMPRESS_MF_BT\r
 252       #ifdef COMPRESS_MF_BT2\r
 253       case kBT2:\r
 254       {\r
 255         NBT2::CMatchFinder *mfSpec = new NBT2::CMatchFinder;\r
 256         setMfPasses = mfSpec;\r
 257         _matchFinder = mfSpec;\r
 258         break;\r
 259       }\r
 260       #endif\r
 261       #ifdef COMPRESS_MF_BT3\r
 262       case kBT3:\r
 263       {\r
 264         NBT3::CMatchFinder *mfSpec = new NBT3::CMatchFinder;\r
 265         setMfPasses = mfSpec;\r
 266         _matchFinder = mfSpec;\r
 267         break;\r
 268       }\r
 269       #endif\r
 270       #ifdef COMPRESS_MF_BT4\r
 271       case kBT4:\r
 272       {\r
 273         NBT4::CMatchFinder *mfSpec = new NBT4::CMatchFinder;\r
 274         setMfPasses = mfSpec;\r
 275         _matchFinder = mfSpec;\r
 276         break;\r
 277       }\r
 278       #endif\r
 279       #endif\r
 280       \r
 281       #ifdef COMPRESS_MF_HC\r
 282       case kHC4:\r
 283       {\r
 284         NHC4::CMatchFinder *mfSpec = new NHC4::CMatchFinder;\r
 285         setMfPasses = mfSpec;\r
 286         _matchFinder = mfSpec;\r
 287         break;\r
 288       }\r
 289       #endif\r
 290     }\r
 291     if (_matchFinder == 0)\r
 292       return E_OUTOFMEMORY;\r
 293 \r
 294     #ifdef COMPRESS_MF_MT\r
 295     if (_multiThread && !(_fastMode && (_matchFinderIndex == kHC4)))\r
 296     {\r
 297       CMatchFinderMT *mfSpec = new CMatchFinderMT;\r
 298       if (mfSpec == 0)\r
 299         return E_OUTOFMEMORY;\r
 300       CMyComPtr<IMatchFinder> mf = mfSpec;\r
 301       RINOK(mfSpec->SetMatchFinder(_matchFinder));\r
 302       _matchFinder.Release();\r
 303       _matchFinder = mf;\r
 304     }\r
 305     #endif\r
 306   }\r
 307   \r
 308   if (!_literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits))\r
 309     return E_OUTOFMEMORY;\r
 310 \r
 311   if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes)\r
 312     return S_OK;\r
 313   RINOK(_matchFinder->Create(_dictionarySize, kNumOpts, _numFastBytes, kMatchMaxLen + 1)); // actually it's + _numFastBytes - _numFastBytes\r
 314   if (_matchFinderCycles != 0 && setMfPasses != 0)\r
 315     setMfPasses->SetNumPasses(_matchFinderCycles);\r
 316   _dictionarySizePrev = _dictionarySize;\r
 317   _numFastBytesPrev = _numFastBytes;\r
 318   return S_OK;\r
 319 }\r
 320 \r
 321 static bool AreStringsEqual(const wchar_t *base, const wchar_t *testString)\r
 322 {\r
 323   while (true)\r
 324   {\r
 325     wchar_t c = *testString;\r
 326     if (c >= 'a' && c <= 'z')\r
 327       c -= 0x20;\r
 328     if (*base != c)\r
 329       return false;\r
 330     if (c == 0)\r
 331       return true;\r
 332     base++;\r
 333     testString++;\r
 334   }\r
 335 }\r
 336 \r
 337 static int FindMatchFinder(const wchar_t *s)\r
 338 {\r
 339   for (int m = 0; m < (int)(sizeof(kMatchFinderIDs) / sizeof(kMatchFinderIDs[0])); m++)\r
 340     if (AreStringsEqual(kMatchFinderIDs[m], s))\r
 341       return m;\r
 342   return -1;\r
 343 }\r
 344 \r
 345 STDMETHODIMP CEncoder::SetCoderProperties(const PROPID *propIDs, \r
 346     const PROPVARIANT *properties, UInt32 numProperties)\r
 347 {\r
 348   for (UInt32 i = 0; i < numProperties; i++)\r
 349   {\r
 350     const PROPVARIANT &prop = properties[i];\r
 351     switch(propIDs[i])\r
 352     {\r
 353       case NCoderPropID::kNumFastBytes:\r
 354       {\r
 355         if (prop.vt != VT_UI4)\r
 356           return E_INVALIDARG;\r
 357         UInt32 numFastBytes = prop.ulVal;\r
 358         if(numFastBytes < 5 || numFastBytes > kMatchMaxLen)\r
 359           return E_INVALIDARG;\r
 360         _numFastBytes = numFastBytes;\r
 361         break;\r
 362       }\r
 363       case NCoderPropID::kMatchFinderCycles:\r
 364       {\r
 365         if (prop.vt != VT_UI4)\r
 366           return E_INVALIDARG;\r
 367         _matchFinderCycles = prop.ulVal;\r
 368         break;\r
 369       }\r
 370       case NCoderPropID::kAlgorithm:\r
 371       {\r
 372         if (prop.vt != VT_UI4)\r
 373           return E_INVALIDARG;\r
 374         UInt32 maximize = prop.ulVal;\r
 375         _fastMode = (maximize == 0); \r
 376         // _maxMode = (maximize >= 2);\r
 377         break;\r
 378       }\r
 379       case NCoderPropID::kMatchFinder:\r
 380       {\r
 381         if (prop.vt != VT_BSTR)\r
 382           return E_INVALIDARG;\r
 383         int matchFinderIndexPrev = _matchFinderIndex;\r
 384         int m = FindMatchFinder(prop.bstrVal);\r
 385         if (m < 0)\r
 386           return E_INVALIDARG;\r
 387         _matchFinderIndex = m;\r
 388         if (_matchFinder && matchFinderIndexPrev != _matchFinderIndex)\r
 389         {\r
 390           _dictionarySizePrev = (UInt32)-1;\r
 391           ReleaseMatchFinder();\r
 392         }\r
 393         break;\r
 394       }\r
 395       #ifdef COMPRESS_MF_MT\r
 396       case NCoderPropID::kMultiThread:\r
 397       {\r
 398         if (prop.vt != VT_BOOL)\r
 399           return E_INVALIDARG;\r
 400         bool newMultiThread = (prop.boolVal == VARIANT_TRUE);\r
 401         if (newMultiThread != _multiThread)\r
 402         {\r
 403           _dictionarySizePrev = (UInt32)-1;\r
 404           ReleaseMatchFinder();\r
 405           _multiThread = newMultiThread;\r
 406         }\r
 407         break;\r
 408       }\r
 409       case NCoderPropID::kNumThreads:\r
 410       {\r
 411         if (prop.vt != VT_UI4)\r
 412           return E_INVALIDARG;\r
 413         bool newMultiThread = (prop.ulVal > 1);\r
 414         if (newMultiThread != _multiThread)\r
 415         {\r
 416           _dictionarySizePrev = (UInt32)-1;\r
 417           ReleaseMatchFinder();\r
 418           _multiThread = newMultiThread;\r
 419         }\r
 420         break;\r
 421       }\r
 422       #endif\r
 423       case NCoderPropID::kDictionarySize:\r
 424       {\r
 425         const int kDicLogSizeMaxCompress = 30;\r
 426         if (prop.vt != VT_UI4)\r
 427           return E_INVALIDARG;\r
 428         UInt32 dictionarySize = prop.ulVal;\r
 429         if (dictionarySize < UInt32(1 << kDicLogSizeMin) ||\r
 430             dictionarySize > UInt32(1 << kDicLogSizeMaxCompress))\r
 431           return E_INVALIDARG;\r
 432         _dictionarySize = dictionarySize;\r
 433         UInt32 dicLogSize;\r
 434         for(dicLogSize = 0; dicLogSize < (UInt32)kDicLogSizeMaxCompress; dicLogSize++)\r
 435           if (dictionarySize <= (UInt32(1) << dicLogSize))\r
 436             break;\r
 437         _distTableSize = dicLogSize * 2;\r
 438         break;\r
 439       }\r
 440       case NCoderPropID::kPosStateBits:\r
 441       {\r
 442         if (prop.vt != VT_UI4)\r
 443           return E_INVALIDARG;\r
 444         UInt32 value = prop.ulVal;\r
 445         if (value > (UInt32)NLength::kNumPosStatesBitsEncodingMax)\r
 446           return E_INVALIDARG;\r
 447         _posStateBits = value;\r
 448         _posStateMask = (1 << _posStateBits) - 1;\r
 449         break;\r
 450       }\r
 451       case NCoderPropID::kLitPosBits:\r
 452       {\r
 453         if (prop.vt != VT_UI4)\r
 454           return E_INVALIDARG;\r
 455         UInt32 value = prop.ulVal;\r
 456         if (value > (UInt32)kNumLitPosStatesBitsEncodingMax)\r
 457           return E_INVALIDARG;\r
 458         _numLiteralPosStateBits = value;\r
 459         break;\r
 460       }\r
 461       case NCoderPropID::kLitContextBits:\r
 462       {\r
 463         if (prop.vt != VT_UI4)\r
 464           return E_INVALIDARG;\r
 465         UInt32 value = prop.ulVal;\r
 466         if (value > (UInt32)kNumLitContextBitsMax)\r
 467           return E_INVALIDARG;\r
 468         _numLiteralContextBits = value;\r
 469         break;\r
 470       }\r
 471       case NCoderPropID::kEndMarker:\r
 472       {\r
 473         if (prop.vt != VT_BOOL)\r
 474           return E_INVALIDARG;\r
 475         SetWriteEndMarkerMode(prop.boolVal == VARIANT_TRUE);\r
 476         break;\r
 477       }\r
 478       default:\r
 479         return E_INVALIDARG;\r
 480     }\r
 481   }\r
 482   return S_OK;\r
 483 }\r
 484 \r
 485 STDMETHODIMP CEncoder::WriteCoderProperties(ISequentialOutStream *outStream)\r
 486 { \r
 487   const UInt32 kPropSize = 5;\r
 488   Byte properties[kPropSize];\r
 489   properties[0] = (_posStateBits * 5 + _numLiteralPosStateBits) * 9 + _numLiteralContextBits;\r
 490   for (int i = 0; i < 4; i++)\r
 491     properties[1 + i] = Byte(_dictionarySize >> (8 * i));\r
 492   return WriteStream(outStream, properties, kPropSize, NULL);\r
 493 }\r
 494 \r
 495 STDMETHODIMP CEncoder::SetOutStream(ISequentialOutStream *outStream)\r
 496 {\r
 497   _rangeEncoder.SetStream(outStream);\r
 498   return S_OK;\r
 499 }\r
 500 \r
 501 STDMETHODIMP CEncoder::ReleaseOutStream()\r
 502 {\r
 503   _rangeEncoder.ReleaseStream();\r
 504   return S_OK;\r
 505 }\r
 506 \r
 507 HRESULT CEncoder::Init()\r
 508 {\r
 509   CBaseState::Init();\r
 510 \r
 511   // RINOK(_matchFinder->Init(inStream));\r
 512   _rangeEncoder.Init();\r
 513 \r
 514   for(int i = 0; i < kNumStates; i++)\r
 515   {\r
 516     for (UInt32 j = 0; j <= _posStateMask; j++)\r
 517     {\r
 518       _isMatch[i][j].Init();\r
 519       _isRep0Long[i][j].Init();\r
 520     }\r
 521     _isRep[i].Init();\r
 522     _isRepG0[i].Init();\r
 523     _isRepG1[i].Init();\r
 524     _isRepG2[i].Init();\r
 525   }\r
 526 \r
 527   _literalEncoder.Init();\r
 528 \r
 529   {\r
 530     for(UInt32 i = 0; i < kNumLenToPosStates; i++)\r
 531       _posSlotEncoder[i].Init();\r
 532   }\r
 533   {\r
 534     for(UInt32 i = 0; i < kNumFullDistances - kEndPosModelIndex; i++)\r
 535       _posEncoders[i].Init();\r
 536   }\r
 537 \r
 538   _lenEncoder.Init(1 << _posStateBits);\r
 539   _repMatchLenEncoder.Init(1 << _posStateBits);\r
 540 \r
 541   _posAlignEncoder.Init();\r
 542 \r
 543   _longestMatchWasFound = false;\r
 544   _optimumEndIndex = 0;\r
 545   _optimumCurrentIndex = 0;\r
 546   _additionalOffset = 0;\r
 547 \r
 548   return S_OK;\r
 549 }\r
 550 \r
 551 HRESULT CEncoder::MovePos(UInt32 num)\r
 552 {\r
 553   if (num == 0)\r
 554     return S_OK;\r
 555   _additionalOffset += num;\r
 556   return _matchFinder->Skip(num);\r
 557 }\r
 558 \r
 559 UInt32 CEncoder::Backward(UInt32 &backRes, UInt32 cur)\r
 560 {\r
 561   _optimumEndIndex = cur;\r
 562   UInt32 posMem = _optimum[cur].PosPrev;\r
 563   UInt32 backMem = _optimum[cur].BackPrev;\r
 564   do\r
 565   {\r
 566     if (_optimum[cur].Prev1IsChar)\r
 567     {\r
 568       _optimum[posMem].MakeAsChar();\r
 569       _optimum[posMem].PosPrev = posMem - 1;\r
 570       if (_optimum[cur].Prev2)\r
 571       {\r
 572         _optimum[posMem - 1].Prev1IsChar = false;\r
 573         _optimum[posMem - 1].PosPrev = _optimum[cur].PosPrev2;\r
 574         _optimum[posMem - 1].BackPrev = _optimum[cur].BackPrev2;\r
 575       }\r
 576     }\r
 577     UInt32 posPrev = posMem;\r
 578     UInt32 backCur = backMem;\r
 579 \r
 580     backMem = _optimum[posPrev].BackPrev;\r
 581     posMem = _optimum[posPrev].PosPrev;\r
 582 \r
 583     _optimum[posPrev].BackPrev = backCur;\r
 584     _optimum[posPrev].PosPrev = cur;\r
 585     cur = posPrev;\r
 586   }\r
 587   while(cur != 0);\r
 588   backRes = _optimum[0].BackPrev;\r
 589   _optimumCurrentIndex  = _optimum[0].PosPrev;\r
 590   return _optimumCurrentIndex; \r
 591 }\r
 592 \r
 593 /*\r
 594 Out:\r
 595   (lenRes == 1) && (backRes == 0xFFFFFFFF) means Literal\r
 596 */\r
 597 \r
 598 HRESULT CEncoder::GetOptimum(UInt32 position, UInt32 &backRes, UInt32 &lenRes)\r
 599 {\r
 600   if(_optimumEndIndex != _optimumCurrentIndex)\r
 601   {\r
 602     const COptimal &optimum = _optimum[_optimumCurrentIndex];\r
 603     lenRes = optimum.PosPrev - _optimumCurrentIndex;\r
 604     backRes = optimum.BackPrev;\r
 605     _optimumCurrentIndex = optimum.PosPrev;\r
 606     return S_OK;\r
 607   }\r
 608   _optimumCurrentIndex = _optimumEndIndex = 0;\r
 609   \r
 610   UInt32 lenMain, numDistancePairs;\r
 611   if (!_longestMatchWasFound)\r
 612   {\r
 613     RINOK(ReadMatchDistances(lenMain, numDistancePairs));\r
 614   }\r
 615   else\r
 616   {\r
 617     lenMain = _longestMatchLength;\r
 618     numDistancePairs = _numDistancePairs;\r
 619     _longestMatchWasFound = false;\r
 620   }\r
 621 \r
 622   const Byte *data = _matchFinder->GetPointerToCurrentPos() - 1;\r
 623   UInt32 numAvailableBytes = _matchFinder->GetNumAvailableBytes() + 1;\r
 624   if (numAvailableBytes < 2)\r
 625   {\r
 626     backRes = (UInt32)(-1);\r
 627     lenRes = 1;\r
 628     return S_OK;\r
 629   }\r
 630   if (numAvailableBytes > kMatchMaxLen)\r
 631     numAvailableBytes = kMatchMaxLen;\r
 632 \r
 633   UInt32 reps[kNumRepDistances];\r
 634   UInt32 repLens[kNumRepDistances];\r
 635   UInt32 repMaxIndex = 0;\r
 636   UInt32 i;\r
 637   for(i = 0; i < kNumRepDistances; i++)\r
 638   {\r
 639     reps[i] = _repDistances[i];\r
 640     UInt32 backOffset = reps[i] + 1;\r
 641     if (data[0] != data[(size_t)0 - backOffset] || data[1] != data[(size_t)1 - backOffset])\r
 642     {\r
 643       repLens[i] = 0;\r
 644       continue;\r
 645     }\r
 646     UInt32 lenTest;\r
 647     for (lenTest = 2; lenTest < numAvailableBytes && \r
 648         data[lenTest] == data[(size_t)lenTest - backOffset]; lenTest++);\r
 649     repLens[i] = lenTest;\r
 650     if (lenTest > repLens[repMaxIndex])\r
 651       repMaxIndex = i;\r
 652   }\r
 653   if(repLens[repMaxIndex] >= _numFastBytes)\r
 654   {\r
 655     backRes = repMaxIndex;\r
 656     lenRes = repLens[repMaxIndex];\r
 657     return MovePos(lenRes - 1);\r
 658   }\r
 659 \r
 660   UInt32 *matchDistances = _matchDistances + 1;\r
 661   if(lenMain >= _numFastBytes)\r
 662   {\r
 663     backRes = matchDistances[numDistancePairs - 1] + kNumRepDistances; \r
 664     lenRes = lenMain;\r
 665     return MovePos(lenMain - 1);\r
 666   }\r
 667   Byte currentByte = *data;\r
 668   Byte matchByte = data[(size_t)0 - reps[0] - 1];\r
 669 \r
 670   if(lenMain < 2 && currentByte != matchByte && repLens[repMaxIndex] < 2)\r
 671   {\r
 672     backRes = (UInt32)-1;\r
 673     lenRes = 1;\r
 674     return S_OK;\r
 675   }\r
 676 \r
 677   _optimum[0].State = _state;\r
 678 \r
 679   UInt32 posState = (position & _posStateMask);\r
 680 \r
 681   _optimum[1].Price = _isMatch[_state.Index][posState].GetPrice0() + \r
 682       _literalEncoder.GetSubCoder(position, _previousByte)->GetPrice(!_state.IsCharState(), matchByte, currentByte);\r
 683   _optimum[1].MakeAsChar();\r
 684 \r
 685   UInt32 matchPrice = _isMatch[_state.Index][posState].GetPrice1();\r
 686   UInt32 repMatchPrice = matchPrice + _isRep[_state.Index].GetPrice1();\r
 687 \r
 688   if(matchByte == currentByte)\r
 689   {\r
 690     UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);\r
 691     if(shortRepPrice < _optimum[1].Price)\r
 692     {\r
 693       _optimum[1].Price = shortRepPrice;\r
 694       _optimum[1].MakeAsShortRep();\r
 695     }\r
 696   }\r
 697   UInt32 lenEnd = ((lenMain >= repLens[repMaxIndex]) ? lenMain : repLens[repMaxIndex]);\r
 698 \r
 699   if(lenEnd < 2)\r
 700   {\r
 701     backRes = _optimum[1].BackPrev;\r
 702     lenRes = 1;\r
 703     return S_OK;\r
 704   }\r
 705 \r
 706   _optimum[1].PosPrev = 0;\r
 707   for (i = 0; i < kNumRepDistances; i++)\r
 708     _optimum[0].Backs[i] = reps[i];\r
 709 \r
 710   UInt32 len = lenEnd;\r
 711   do\r
 712     _optimum[len--].Price = kIfinityPrice;\r
 713   while (len >= 2);\r
 714 \r
 715   for(i = 0; i < kNumRepDistances; i++)\r
 716   {\r
 717     UInt32 repLen = repLens[i];\r
 718     if (repLen < 2)\r
 719       continue;\r
 720     UInt32 price = repMatchPrice + GetPureRepPrice(i, _state, posState);\r
 721     do\r
 722     {\r
 723       UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(repLen - 2, posState);\r
 724       COptimal &optimum = _optimum[repLen];\r
 725       if (curAndLenPrice < optimum.Price) \r
 726       {\r
 727         optimum.Price = curAndLenPrice;\r
 728         optimum.PosPrev = 0;\r
 729         optimum.BackPrev = i;\r
 730         optimum.Prev1IsChar = false;\r
 731       }\r
 732     }\r
 733     while(--repLen >= 2);\r
 734   }\r
 735 \r
 736   UInt32 normalMatchPrice = matchPrice + _isRep[_state.Index].GetPrice0();\r
 737 \r
 738   len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);\r
 739   if (len <= lenMain)\r
 740   {\r
 741     UInt32 offs = 0;\r
 742     while (len > matchDistances[offs])\r
 743       offs += 2;\r
 744     for(; ; len++)\r
 745     {\r
 746       UInt32 distance = matchDistances[offs + 1];\r
 747       UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(distance, len, posState);\r
 748       COptimal &optimum = _optimum[len];\r
 749       if (curAndLenPrice < optimum.Price) \r
 750       {\r
 751         optimum.Price = curAndLenPrice;\r
 752         optimum.PosPrev = 0;\r
 753         optimum.BackPrev = distance + kNumRepDistances;\r
 754         optimum.Prev1IsChar = false;\r
 755       }\r
 756       if (len == matchDistances[offs])\r
 757       {\r
 758         offs += 2;\r
 759         if (offs == numDistancePairs)\r
 760           break;\r
 761       }\r
 762     }\r
 763   }\r
 764 \r
 765   UInt32 cur = 0;\r
 766 \r
 767   while(true)\r
 768   {\r
 769     cur++;\r
 770     if(cur == lenEnd)\r
 771     {\r
 772       lenRes = Backward(backRes, cur);\r
 773       return S_OK;\r
 774     }\r
 775     UInt32 newLen, numDistancePairs;\r
 776     RINOK(ReadMatchDistances(newLen, numDistancePairs));\r
 777     if(newLen >= _numFastBytes)\r
 778     {\r
 779       _numDistancePairs = numDistancePairs;\r
 780       _longestMatchLength = newLen;\r
 781       _longestMatchWasFound = true;\r
 782       lenRes = Backward(backRes, cur);\r
 783       return S_OK;\r
 784     }\r
 785     position++;\r
 786     COptimal &curOptimum = _optimum[cur];\r
 787     UInt32 posPrev = curOptimum.PosPrev;\r
 788     CState state;\r
 789     if (curOptimum.Prev1IsChar)\r
 790     {\r
 791       posPrev--;\r
 792       if (curOptimum.Prev2)\r
 793       {\r
 794         state = _optimum[curOptimum.PosPrev2].State;\r
 795         if (curOptimum.BackPrev2 < kNumRepDistances)\r
 796           state.UpdateRep();\r
 797         else\r
 798           state.UpdateMatch();\r
 799       }\r
 800       else\r
 801         state = _optimum[posPrev].State;\r
 802       state.UpdateChar();\r
 803     }\r
 804     else\r
 805       state = _optimum[posPrev].State;\r
 806     if (posPrev == cur - 1)\r
 807     {\r
 808       if (curOptimum.IsShortRep())\r
 809         state.UpdateShortRep();\r
 810       else\r
 811         state.UpdateChar();\r
 812     }\r
 813     else\r
 814     {\r
 815       UInt32 pos;\r
 816       if (curOptimum.Prev1IsChar && curOptimum.Prev2)\r
 817       {\r
 818         posPrev = curOptimum.PosPrev2;\r
 819         pos = curOptimum.BackPrev2;\r
 820         state.UpdateRep();\r
 821       }\r
 822       else\r
 823       {\r
 824         pos = curOptimum.BackPrev;\r
 825         if (pos < kNumRepDistances)\r
 826           state.UpdateRep();\r
 827         else\r
 828           state.UpdateMatch();\r
 829       }\r
 830       const COptimal &prevOptimum = _optimum[posPrev];\r
 831       if (pos < kNumRepDistances)\r
 832       {\r
 833         reps[0] = prevOptimum.Backs[pos];\r
 834                 UInt32 i;\r
 835         for(i = 1; i <= pos; i++)\r
 836           reps[i] = prevOptimum.Backs[i - 1];\r
 837         for(; i < kNumRepDistances; i++)\r
 838           reps[i] = prevOptimum.Backs[i];\r
 839       }\r
 840       else\r
 841       {\r
 842         reps[0] = (pos - kNumRepDistances);\r
 843         for(UInt32 i = 1; i < kNumRepDistances; i++)\r
 844           reps[i] = prevOptimum.Backs[i - 1];\r
 845       }\r
 846     }\r
 847     curOptimum.State = state;\r
 848     for(UInt32 i = 0; i < kNumRepDistances; i++)\r
 849       curOptimum.Backs[i] = reps[i];\r
 850     UInt32 curPrice = curOptimum.Price; \r
 851     const Byte *data = _matchFinder->GetPointerToCurrentPos() - 1;\r
 852     const Byte currentByte = *data;\r
 853     const Byte matchByte = data[(size_t)0 - reps[0] - 1];\r
 854 \r
 855     UInt32 posState = (position & _posStateMask);\r
 856 \r
 857     UInt32 curAnd1Price = curPrice +\r
 858         _isMatch[state.Index][posState].GetPrice0() +\r
 859         _literalEncoder.GetSubCoder(position, data[(size_t)0 - 1])->GetPrice(!state.IsCharState(), matchByte, currentByte);\r
 860 \r
 861     COptimal &nextOptimum = _optimum[cur + 1];\r
 862 \r
 863     bool nextIsChar = false;\r
 864     if (curAnd1Price < nextOptimum.Price) \r
 865     {\r
 866       nextOptimum.Price = curAnd1Price;\r
 867       nextOptimum.PosPrev = cur;\r
 868       nextOptimum.MakeAsChar();\r
 869       nextIsChar = true;\r
 870     }\r
 871 \r
 872     UInt32 matchPrice = curPrice + _isMatch[state.Index][posState].GetPrice1();\r
 873     UInt32 repMatchPrice = matchPrice + _isRep[state.Index].GetPrice1();\r
 874     \r
 875     if(matchByte == currentByte &&\r
 876         !(nextOptimum.PosPrev < cur && nextOptimum.BackPrev == 0))\r
 877     {\r
 878       UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(state, posState);\r
 879       if(shortRepPrice <= nextOptimum.Price)\r
 880       {\r
 881         nextOptimum.Price = shortRepPrice;\r
 882         nextOptimum.PosPrev = cur;\r
 883         nextOptimum.MakeAsShortRep();\r
 884         nextIsChar = true;\r
 885       }\r
 886     }\r
 887     /*\r
 888     if(newLen == 2 && matchDistances[2] >= kDistLimit2) // test it maybe set 2000 ?\r
 889       continue;\r
 890     */\r
 891 \r
 892     UInt32 numAvailableBytesFull = _matchFinder->GetNumAvailableBytes() + 1;\r
 893     numAvailableBytesFull = MyMin(kNumOpts - 1 - cur, numAvailableBytesFull);\r
 894     UInt32 numAvailableBytes = numAvailableBytesFull;\r
 895 \r
 896     if (numAvailableBytes < 2)\r
 897       continue;\r
 898     if (numAvailableBytes > _numFastBytes)\r
 899       numAvailableBytes = _numFastBytes;\r
 900     if (!nextIsChar && matchByte != currentByte) // speed optimization\r
 901     {\r
 902       // try Literal + rep0\r
 903       UInt32 backOffset = reps[0] + 1;\r
 904       UInt32 limit = MyMin(numAvailableBytesFull, _numFastBytes + 1);\r
 905       UInt32 temp;\r
 906       for (temp = 1; temp < limit && \r
 907           data[temp] == data[(size_t)temp - backOffset]; temp++);\r
 908       UInt32 lenTest2 = temp - 1;\r
 909       if (lenTest2 >= 2)\r
 910       {\r
 911         CState state2 = state;\r
 912         state2.UpdateChar();\r
 913         UInt32 posStateNext = (position + 1) & _posStateMask;\r
 914         UInt32 nextRepMatchPrice = curAnd1Price + \r
 915             _isMatch[state2.Index][posStateNext].GetPrice1() +\r
 916             _isRep[state2.Index].GetPrice1();\r
 917         // for (; lenTest2 >= 2; lenTest2--)\r
 918         {\r
 919           UInt32 offset = cur + 1 + lenTest2;\r
 920           while(lenEnd < offset)\r
 921             _optimum[++lenEnd].Price = kIfinityPrice;\r
 922           UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(\r
 923               0, lenTest2, state2, posStateNext);\r
 924           COptimal &optimum = _optimum[offset];\r
 925           if (curAndLenPrice < optimum.Price) \r
 926           {\r
 927             optimum.Price = curAndLenPrice;\r
 928             optimum.PosPrev = cur + 1;\r
 929             optimum.BackPrev = 0;\r
 930             optimum.Prev1IsChar = true;\r
 931             optimum.Prev2 = false;\r
 932           }\r
 933         }\r
 934       }\r
 935     }\r
 936     \r
 937     UInt32 startLen = 2; // speed optimization \r
 938     for(UInt32 repIndex = 0; repIndex < kNumRepDistances; repIndex++)\r
 939     {\r
 940       // UInt32 repLen = _matchFinder->GetMatchLen(0 - 1, reps[repIndex], newLen); // test it;\r
 941       UInt32 backOffset = reps[repIndex] + 1;\r
 942       if (data[0] != data[(size_t)0 - backOffset] ||\r
 943           data[1] != data[(size_t)1 - backOffset])\r
 944         continue;\r
 945       UInt32 lenTest;\r
 946       for (lenTest = 2; lenTest < numAvailableBytes && \r
 947           data[lenTest] == data[(size_t)lenTest - backOffset]; lenTest++);\r
 948       while(lenEnd < cur + lenTest)\r
 949         _optimum[++lenEnd].Price = kIfinityPrice;\r
 950       UInt32 lenTestTemp = lenTest;\r
 951       UInt32 price = repMatchPrice + GetPureRepPrice(repIndex, state, posState);\r
 952       do\r
 953       {\r
 954         UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(lenTest - 2, posState);\r
 955         COptimal &optimum = _optimum[cur + lenTest];\r
 956         if (curAndLenPrice < optimum.Price) \r
 957         {\r
 958           optimum.Price = curAndLenPrice;\r
 959           optimum.PosPrev = cur;\r
 960           optimum.BackPrev = repIndex;\r
 961           optimum.Prev1IsChar = false;\r
 962         }\r
 963       }\r
 964       while(--lenTest >= 2);\r
 965       lenTest = lenTestTemp;\r
 966       \r
 967       if (repIndex == 0)\r
 968         startLen = lenTest + 1;\r
 969         \r
 970       // if (_maxMode)\r
 971         {\r
 972           UInt32 lenTest2 = lenTest + 1;\r
 973           UInt32 limit = MyMin(numAvailableBytesFull, lenTest2 + _numFastBytes);\r
 974           for (; lenTest2 < limit && \r
 975               data[lenTest2] == data[(size_t)lenTest2 - backOffset]; lenTest2++);\r
 976           lenTest2 -= lenTest + 1;\r
 977           if (lenTest2 >= 2)\r
 978           {\r
 979             CState state2 = state;\r
 980             state2.UpdateRep();\r
 981             UInt32 posStateNext = (position + lenTest) & _posStateMask;\r
 982             UInt32 curAndLenCharPrice = \r
 983                 price + _repMatchLenEncoder.GetPrice(lenTest - 2, posState) + \r
 984                 _isMatch[state2.Index][posStateNext].GetPrice0() +\r
 985                 _literalEncoder.GetSubCoder(position + lenTest, data[(size_t)lenTest - 1])->GetPrice(\r
 986                 true, data[(size_t)lenTest - backOffset], data[lenTest]);\r
 987             state2.UpdateChar();\r
 988             posStateNext = (position + lenTest + 1) & _posStateMask;\r
 989             UInt32 nextRepMatchPrice = curAndLenCharPrice + \r
 990                 _isMatch[state2.Index][posStateNext].GetPrice1() +\r
 991                 _isRep[state2.Index].GetPrice1();\r
 992             \r
 993             // for(; lenTest2 >= 2; lenTest2--)\r
 994             {\r
 995               UInt32 offset = cur + lenTest + 1 + lenTest2;\r
 996               while(lenEnd < offset)\r
 997                 _optimum[++lenEnd].Price = kIfinityPrice;\r
 998               UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(\r
 999                   0, lenTest2, state2, posStateNext);\r
1000               COptimal &optimum = _optimum[offset];\r
1001               if (curAndLenPrice < optimum.Price) \r
1002               {\r
1003                 optimum.Price = curAndLenPrice;\r
1004                 optimum.PosPrev = cur + lenTest + 1;\r
1005                 optimum.BackPrev = 0;\r
1006                 optimum.Prev1IsChar = true;\r
1007                 optimum.Prev2 = true;\r
1008                 optimum.PosPrev2 = cur;\r
1009                 optimum.BackPrev2 = repIndex;\r
1010               }\r
1011             }\r
1012           }\r
1013         }\r
1014       }\r
1015     \r
1016     //    for(UInt32 lenTest = 2; lenTest <= newLen; lenTest++)\r
1017     if (newLen > numAvailableBytes)\r
1018     {\r
1019       newLen = numAvailableBytes;\r
1020       for (numDistancePairs = 0; newLen > matchDistances[numDistancePairs]; numDistancePairs += 2);\r
1021       matchDistances[numDistancePairs] = newLen;\r
1022       numDistancePairs += 2;\r
1023     }\r
1024     if (newLen >= startLen)\r
1025     {\r
1026       UInt32 normalMatchPrice = matchPrice + _isRep[state.Index].GetPrice0();\r
1027       while(lenEnd < cur + newLen)\r
1028         _optimum[++lenEnd].Price = kIfinityPrice;\r
1029 \r
1030       UInt32 offs = 0;\r
1031       while(startLen > matchDistances[offs])\r
1032         offs += 2;\r
1033       UInt32 curBack = matchDistances[offs + 1];\r
1034       UInt32 posSlot = GetPosSlot2(curBack);\r
1035       for(UInt32 lenTest = /*2*/ startLen; ; lenTest++)\r
1036       {\r
1037         UInt32 curAndLenPrice = normalMatchPrice;\r
1038         UInt32 lenToPosState = GetLenToPosState(lenTest);\r
1039         if (curBack < kNumFullDistances)\r
1040           curAndLenPrice += _distancesPrices[lenToPosState][curBack];\r
1041         else\r
1042           curAndLenPrice += _posSlotPrices[lenToPosState][posSlot] + _alignPrices[curBack & kAlignMask];\r
1043   \r
1044         curAndLenPrice += _lenEncoder.GetPrice(lenTest - kMatchMinLen, posState);\r
1045         \r
1046         COptimal &optimum = _optimum[cur + lenTest];\r
1047         if (curAndLenPrice < optimum.Price) \r
1048         {\r
1049           optimum.Price = curAndLenPrice;\r
1050           optimum.PosPrev = cur;\r
1051           optimum.BackPrev = curBack + kNumRepDistances;\r
1052           optimum.Prev1IsChar = false;\r
1053         }\r
1054 \r
1055         if (/*_maxMode && */lenTest == matchDistances[offs])\r
1056         {\r
1057           // Try Match + Literal + Rep0\r
1058           UInt32 backOffset = curBack + 1;\r
1059           UInt32 lenTest2 = lenTest + 1;\r
1060           UInt32 limit = MyMin(numAvailableBytesFull, lenTest2 + _numFastBytes);\r
1061           for (; lenTest2 < limit && \r
1062               data[lenTest2] == data[(size_t)lenTest2 - backOffset]; lenTest2++);\r
1063           lenTest2 -= lenTest + 1;\r
1064           if (lenTest2 >= 2)\r
1065           {\r
1066             CState state2 = state;\r
1067             state2.UpdateMatch();\r
1068             UInt32 posStateNext = (position + lenTest) & _posStateMask;\r
1069             UInt32 curAndLenCharPrice = curAndLenPrice + \r
1070                 _isMatch[state2.Index][posStateNext].GetPrice0() +\r
1071                 _literalEncoder.GetSubCoder(position + lenTest, data[(size_t)lenTest - 1])->GetPrice( \r
1072                 true, data[(size_t)lenTest - backOffset], data[lenTest]);\r
1073             state2.UpdateChar();\r
1074             posStateNext = (posStateNext + 1) & _posStateMask;\r
1075             UInt32 nextRepMatchPrice = curAndLenCharPrice + \r
1076                 _isMatch[state2.Index][posStateNext].GetPrice1() +\r
1077                 _isRep[state2.Index].GetPrice1();\r
1078             \r
1079             // for(; lenTest2 >= 2; lenTest2--)\r
1080             {\r
1081               UInt32 offset = cur + lenTest + 1 + lenTest2;\r
1082               while(lenEnd < offset)\r
1083                 _optimum[++lenEnd].Price = kIfinityPrice;\r
1084               UInt32 curAndLenPrice = nextRepMatchPrice + GetRepPrice(0, lenTest2, state2, posStateNext);\r
1085               COptimal &optimum = _optimum[offset];\r
1086               if (curAndLenPrice < optimum.Price) \r
1087               {\r
1088                 optimum.Price = curAndLenPrice;\r
1089                 optimum.PosPrev = cur + lenTest + 1;\r
1090                 optimum.BackPrev = 0;\r
1091                 optimum.Prev1IsChar = true;\r
1092                 optimum.Prev2 = true;\r
1093                 optimum.PosPrev2 = cur;\r
1094                 optimum.BackPrev2 = curBack + kNumRepDistances;\r
1095               }\r
1096             }\r
1097           }\r
1098           offs += 2;\r
1099           if (offs == numDistancePairs)\r
1100             break;\r
1101           curBack = matchDistances[offs + 1];\r
1102           if (curBack >= kNumFullDistances)\r
1103             posSlot = GetPosSlot2(curBack);\r
1104         }\r
1105       }\r
1106     }\r
1107   }\r
1108 }\r
1109 \r
1110 static inline bool ChangePair(UInt32 smallDist, UInt32 bigDist)\r
1111 {\r
1112   return ((bigDist >> 7) > smallDist);\r
1113 }\r
1114 \r
1115 \r
1116 HRESULT CEncoder::ReadMatchDistances(UInt32 &lenRes, UInt32 &numDistancePairs)\r
1117 {\r
1118   lenRes = 0;\r
1119   RINOK(_matchFinder->GetMatches(_matchDistances));\r
1120   numDistancePairs = _matchDistances[0];\r
1121   if (numDistancePairs > 0)\r
1122   {\r
1123     lenRes = _matchDistances[1 + numDistancePairs - 2];\r
1124     if (lenRes == _numFastBytes)\r
1125       lenRes += _matchFinder->GetMatchLen(lenRes - 1, _matchDistances[1 + numDistancePairs - 1], \r
1126           kMatchMaxLen - lenRes);\r
1127   }\r
1128   _additionalOffset++;\r
1129   return S_OK;\r
1130 }\r
1131 \r
1132 HRESULT CEncoder::GetOptimumFast(UInt32 position, UInt32 &backRes, UInt32 &lenRes)\r
1133 {\r
1134   UInt32 lenMain, numDistancePairs;\r
1135   if (!_longestMatchWasFound)\r
1136   {\r
1137     RINOK(ReadMatchDistances(lenMain, numDistancePairs));\r
1138   }\r
1139   else\r
1140   {\r
1141     lenMain = _longestMatchLength;\r
1142     numDistancePairs = _numDistancePairs;\r
1143     _longestMatchWasFound = false;\r
1144   }\r
1145 \r
1146   const Byte *data = _matchFinder->GetPointerToCurrentPos() - 1;\r
1147   UInt32 numAvailableBytes = _matchFinder->GetNumAvailableBytes() + 1;\r
1148   if (numAvailableBytes > kMatchMaxLen)\r
1149     numAvailableBytes = kMatchMaxLen;\r
1150   if (numAvailableBytes < 2)\r
1151   {\r
1152     backRes = (UInt32)(-1);\r
1153     lenRes = 1;\r
1154     return S_OK;\r
1155   }\r
1156 \r
1157   UInt32 repLens[kNumRepDistances];\r
1158   UInt32 repMaxIndex = 0;\r
1159 \r
1160   for(UInt32 i = 0; i < kNumRepDistances; i++)\r
1161   {\r
1162     UInt32 backOffset = _repDistances[i] + 1;\r
1163     if (data[0] != data[(size_t)0 - backOffset] || data[1] != data[(size_t)1 - backOffset])\r
1164     {\r
1165       repLens[i] = 0;\r
1166       continue;\r
1167     }\r
1168     UInt32 len;\r
1169     for (len = 2; len < numAvailableBytes && data[len] == data[(size_t)len - backOffset]; len++);\r
1170     if(len >= _numFastBytes)\r
1171     {\r
1172       backRes = i;\r
1173       lenRes = len;\r
1174       return MovePos(lenRes - 1);\r
1175     }\r
1176     repLens[i] = len;\r
1177     if (len > repLens[repMaxIndex])\r
1178       repMaxIndex = i;\r
1179   }\r
1180   UInt32 *matchDistances = _matchDistances + 1;\r
1181   if(lenMain >= _numFastBytes)\r
1182   {\r
1183     backRes = matchDistances[numDistancePairs - 1] + kNumRepDistances; \r
1184     lenRes = lenMain;\r
1185     return MovePos(lenMain - 1);\r
1186   }\r
1187 \r
1188   UInt32 backMain = 0;\r
1189   if (lenMain >= 2)\r
1190   {\r
1191     backMain = matchDistances[numDistancePairs - 1];\r
1192     while (numDistancePairs > 2 && lenMain == matchDistances[numDistancePairs - 4] + 1)\r
1193     {\r
1194       if (!ChangePair(matchDistances[numDistancePairs - 3], backMain))\r
1195         break;\r
1196       numDistancePairs -= 2;\r
1197       lenMain = matchDistances[numDistancePairs - 2];\r
1198       backMain = matchDistances[numDistancePairs - 1];\r
1199     }\r
1200     if (lenMain == 2 && backMain >= 0x80)\r
1201       lenMain = 1;\r
1202   }\r
1203 \r
1204   if (repLens[repMaxIndex] >= 2)\r
1205   {\r
1206     if (repLens[repMaxIndex] + 1 >= lenMain || \r
1207         repLens[repMaxIndex] + 2 >= lenMain && (backMain > (1 << 9)) ||\r
1208         repLens[repMaxIndex] + 3 >= lenMain && (backMain > (1 << 15)))\r
1209     {\r
1210       backRes = repMaxIndex;\r
1211       lenRes = repLens[repMaxIndex];\r
1212       return MovePos(lenRes - 1);\r
1213     }\r
1214   }\r
1215   \r
1216   if (lenMain >= 2 && numAvailableBytes > 2)\r
1217   {\r
1218     RINOK(ReadMatchDistances(_longestMatchLength, _numDistancePairs));\r
1219     if (_longestMatchLength >= 2)\r
1220     {\r
1221       UInt32 newDistance = matchDistances[_numDistancePairs - 1];\r
1222       if (_longestMatchLength >= lenMain && newDistance < backMain || \r
1223           _longestMatchLength == lenMain + 1 && !ChangePair(backMain, newDistance) ||\r
1224           _longestMatchLength > lenMain + 1 ||\r
1225           _longestMatchLength + 1 >= lenMain && lenMain >= 3 && ChangePair(newDistance, backMain))\r
1226       {\r
1227         _longestMatchWasFound = true;\r
1228         backRes = UInt32(-1);\r
1229         lenRes = 1;\r
1230         return S_OK;\r
1231       }\r
1232     }\r
1233     data++;\r
1234     numAvailableBytes--;\r
1235     for(UInt32 i = 0; i < kNumRepDistances; i++)\r
1236     {\r
1237       UInt32 backOffset = _repDistances[i] + 1;\r
1238       if (data[1] != data[(size_t)1 - backOffset] || data[2] != data[(size_t)2 - backOffset])\r
1239       {\r
1240         repLens[i] = 0;\r
1241         continue;\r
1242       }\r
1243       UInt32 len;\r
1244       for (len = 2; len < numAvailableBytes && data[len] == data[(size_t)len - backOffset]; len++);\r
1245       if (len + 1 >= lenMain)\r
1246       {\r
1247         _longestMatchWasFound = true;\r
1248         backRes = UInt32(-1);\r
1249         lenRes = 1;\r
1250         return S_OK;\r
1251       }\r
1252     }\r
1253     backRes = backMain + kNumRepDistances; \r
1254     lenRes = lenMain;\r
1255     return MovePos(lenMain - 2);\r
1256   }\r
1257   backRes = UInt32(-1);\r
1258   lenRes = 1;\r
1259   return S_OK;\r
1260 }\r
1261 \r
1262 HRESULT CEncoder::Flush(UInt32 nowPos)\r
1263 {\r
1264   ReleaseMFStream();\r
1265   WriteEndMarker(nowPos & _posStateMask);\r
1266   _rangeEncoder.FlushData();\r
1267   return _rangeEncoder.FlushStream();\r
1268 }\r
1269 \r
1270 void CEncoder::WriteEndMarker(UInt32 posState)\r
1271 {\r
1272   // This function for writing End Mark for stream version of LZMA. \r
1273   // In current version this feature is not used.\r
1274   if (!_writeEndMark)\r
1275     return;\r
1276 \r
1277   _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1);\r
1278   _isRep[_state.Index].Encode(&_rangeEncoder, 0);\r
1279   _state.UpdateMatch();\r
1280   UInt32 len = kMatchMinLen; // kMatchMaxLen;\r
1281   _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode);\r
1282   UInt32 posSlot = (1 << kNumPosSlotBits)  - 1;\r
1283   UInt32 lenToPosState = GetLenToPosState(len);\r
1284   _posSlotEncoder[lenToPosState].Encode(&_rangeEncoder, posSlot);\r
1285   UInt32 footerBits = 30;\r
1286   UInt32 posReduced = (UInt32(1) << footerBits) - 1;\r
1287   _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits);\r
1288   _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask);\r
1289 }\r
1290 \r
1291 HRESULT CEncoder::CodeReal(ISequentialInStream *inStream,\r
1292       ISequentialOutStream *outStream, \r
1293       const UInt64 *inSize, const UInt64 *outSize,\r
1294       ICompressProgressInfo *progress)\r
1295 {\r
1296   _needReleaseMFStream = false;\r
1297   CCoderReleaser coderReleaser(this);\r
1298   RINOK(SetStreams(inStream, outStream, inSize, outSize));\r
1299   while(true)\r
1300   {\r
1301     UInt64 processedInSize;\r
1302     UInt64 processedOutSize;\r
1303     Int32 finished;\r
1304     RINOK(CodeOneBlock(&processedInSize, &processedOutSize, &finished));\r
1305     if (finished != 0)\r
1306       return S_OK;\r
1307     if (progress != 0)\r
1308     {\r
1309       RINOK(progress->SetRatioInfo(&processedInSize, &processedOutSize));\r
1310     }\r
1311   }\r
1312 }\r
1313 \r
1314 HRESULT CEncoder::SetStreams(ISequentialInStream *inStream,\r
1315       ISequentialOutStream *outStream, \r
1316       const UInt64 *inSize, const UInt64 *outSize)\r
1317 {\r
1318   _inStream = inStream;\r
1319   _finished = false;\r
1320   RINOK(Create());\r
1321   RINOK(SetOutStream(outStream));\r
1322   RINOK(Init());\r
1323   \r
1324   // CCoderReleaser releaser(this);\r
1325 \r
1326   /*\r
1327   if (_matchFinder->GetNumAvailableBytes() == 0)\r
1328     return Flush();\r
1329   */\r
1330 \r
1331   if (!_fastMode)\r
1332   {\r
1333     FillDistancesPrices();\r
1334     FillAlignPrices();\r
1335   }\r
1336 \r
1337   _lenEncoder.SetTableSize(_numFastBytes + 1 - kMatchMinLen);\r
1338   _lenEncoder.UpdateTables(1 << _posStateBits);\r
1339   _repMatchLenEncoder.SetTableSize(_numFastBytes + 1 - kMatchMinLen);\r
1340   _repMatchLenEncoder.UpdateTables(1 << _posStateBits);\r
1341 \r
1342   nowPos64 = 0;\r
1343   return S_OK;\r
1344 }\r
1345 \r
1346 HRESULT CEncoder::CodeOneBlock(UInt64 *inSize, UInt64 *outSize, Int32 *finished)\r
1347 {\r
1348   if (_inStream != 0)\r
1349   {\r
1350     RINOK(_matchFinder->SetStream(_inStream));\r
1351     RINOK(_matchFinder->Init());\r
1352     _needReleaseMFStream = true;\r
1353     _inStream = 0;\r
1354   }\r
1355 \r
1356 \r
1357   *finished = 1;\r
1358   if (_finished)\r
1359     return S_OK;\r
1360   _finished = true;\r
1361 \r
1362   if (nowPos64 == 0)\r
1363   {\r
1364     if (_matchFinder->GetNumAvailableBytes() == 0)\r
1365       return Flush(UInt32(nowPos64));\r
1366     UInt32 len, numDistancePairs;\r
1367     RINOK(ReadMatchDistances(len, numDistancePairs));\r
1368     UInt32 posState = UInt32(nowPos64) & _posStateMask;\r
1369     _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0);\r
1370     _state.UpdateChar();\r
1371     Byte curByte = _matchFinder->GetIndexByte(0 - _additionalOffset);\r
1372     _literalEncoder.GetSubCoder(UInt32(nowPos64), _previousByte)->Encode(&_rangeEncoder, curByte);\r
1373     _previousByte = curByte;\r
1374     _additionalOffset--;\r
1375     nowPos64++;\r
1376   }\r
1377 \r
1378   UInt32 nowPos32 = (UInt32)nowPos64;\r
1379   UInt32 progressPosValuePrev = nowPos32;\r
1380 \r
1381   if (_matchFinder->GetNumAvailableBytes() == 0)\r
1382     return Flush(nowPos32);\r
1383 \r
1384   while(true)\r
1385   {\r
1386     #ifdef _NO_EXCEPTIONS\r
1387     if (_rangeEncoder.Stream.ErrorCode != S_OK)\r
1388       return _rangeEncoder.Stream.ErrorCode;\r
1389     #endif\r
1390     UInt32 pos, len;\r
1391     HRESULT result;\r
1392     if (_fastMode)\r
1393       result = GetOptimumFast(nowPos32, pos, len);\r
1394     else\r
1395       result = GetOptimum(nowPos32, pos, len);\r
1396     RINOK(result);\r
1397 \r
1398     UInt32 posState = nowPos32 & _posStateMask;\r
1399     if(len == 1 && pos == 0xFFFFFFFF)\r
1400     {\r
1401       _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 0);\r
1402       Byte curByte = _matchFinder->GetIndexByte(0 - _additionalOffset);\r
1403       CLiteralEncoder2 *subCoder = _literalEncoder.GetSubCoder(nowPos32, _previousByte);\r
1404       if(_state.IsCharState())\r
1405         subCoder->Encode(&_rangeEncoder, curByte);\r
1406       else\r
1407       {\r
1408         Byte matchByte = _matchFinder->GetIndexByte(0 - _repDistances[0] - 1 - _additionalOffset);\r
1409         subCoder->EncodeMatched(&_rangeEncoder, matchByte, curByte);\r
1410       }\r
1411       _state.UpdateChar();\r
1412       _previousByte = curByte;\r
1413     }\r
1414     else\r
1415     {\r
1416       _isMatch[_state.Index][posState].Encode(&_rangeEncoder, 1);\r
1417       if(pos < kNumRepDistances)\r
1418       {\r
1419         _isRep[_state.Index].Encode(&_rangeEncoder, 1);\r
1420         if(pos == 0)\r
1421         {\r
1422           _isRepG0[_state.Index].Encode(&_rangeEncoder, 0);\r
1423           _isRep0Long[_state.Index][posState].Encode(&_rangeEncoder, ((len == 1) ? 0 : 1));\r
1424         }\r
1425         else\r
1426         {\r
1427           UInt32 distance = _repDistances[pos];\r
1428           _isRepG0[_state.Index].Encode(&_rangeEncoder, 1);\r
1429           if (pos == 1)\r
1430             _isRepG1[_state.Index].Encode(&_rangeEncoder, 0);\r
1431           else\r
1432           {\r
1433             _isRepG1[_state.Index].Encode(&_rangeEncoder, 1);\r
1434             _isRepG2[_state.Index].Encode(&_rangeEncoder, pos - 2);\r
1435             if (pos == 3)\r
1436               _repDistances[3] = _repDistances[2];\r
1437             _repDistances[2] = _repDistances[1];\r
1438           }\r
1439           _repDistances[1] = _repDistances[0];\r
1440           _repDistances[0] = distance;\r
1441         }\r
1442         if (len == 1)\r
1443           _state.UpdateShortRep();\r
1444         else\r
1445         {\r
1446           _repMatchLenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode);\r
1447           _state.UpdateRep();\r
1448         }\r
1449       }\r
1450       else\r
1451       {\r
1452         _isRep[_state.Index].Encode(&_rangeEncoder, 0);\r
1453         _state.UpdateMatch();\r
1454         _lenEncoder.Encode(&_rangeEncoder, len - kMatchMinLen, posState, !_fastMode);\r
1455         pos -= kNumRepDistances;\r
1456         UInt32 posSlot = GetPosSlot(pos);\r
1457         _posSlotEncoder[GetLenToPosState(len)].Encode(&_rangeEncoder, posSlot);\r
1458         \r
1459         if (posSlot >= kStartPosModelIndex)\r
1460         {\r
1461           UInt32 footerBits = ((posSlot >> 1) - 1);\r
1462           UInt32 base = ((2 | (posSlot & 1)) << footerBits);\r
1463           UInt32 posReduced = pos - base;\r
1464 \r
1465           if (posSlot < kEndPosModelIndex)\r
1466             NRangeCoder::ReverseBitTreeEncode(_posEncoders + base - posSlot - 1, \r
1467                 &_rangeEncoder, footerBits, posReduced);\r
1468           else\r
1469           {\r
1470             _rangeEncoder.EncodeDirectBits(posReduced >> kNumAlignBits, footerBits - kNumAlignBits);\r
1471             _posAlignEncoder.ReverseEncode(&_rangeEncoder, posReduced & kAlignMask);\r
1472             _alignPriceCount++;\r
1473           }\r
1474         }\r
1475         _repDistances[3] = _repDistances[2];\r
1476         _repDistances[2] = _repDistances[1];\r
1477         _repDistances[1] = _repDistances[0];\r
1478         _repDistances[0] = pos;\r
1479         _matchPriceCount++;\r
1480       }\r
1481       _previousByte = _matchFinder->GetIndexByte(len - 1 - _additionalOffset);\r
1482     }\r
1483     _additionalOffset -= len;\r
1484     nowPos32 += len;\r
1485     if (_additionalOffset == 0)\r
1486     {\r
1487       if (!_fastMode)\r
1488       {\r
1489         if (_matchPriceCount >= (1 << 7))\r
1490           FillDistancesPrices();\r
1491         if (_alignPriceCount >= kAlignTableSize)\r
1492           FillAlignPrices();\r
1493       }\r
1494       if (_matchFinder->GetNumAvailableBytes() == 0)\r
1495         return Flush(nowPos32);\r
1496       if (nowPos32 - progressPosValuePrev >= (1 << 14))\r
1497       {\r
1498         nowPos64 += nowPos32 - progressPosValuePrev;\r
1499         *inSize = nowPos64;\r
1500         *outSize = _rangeEncoder.GetProcessedSize();\r
1501         _finished = false;\r
1502         *finished = 0;\r
1503         return S_OK;\r
1504       }\r
1505     }\r
1506   }\r
1507 }\r
1508 \r
1509 STDMETHODIMP CEncoder::Code(ISequentialInStream *inStream,\r
1510     ISequentialOutStream *outStream, const UInt64 *inSize, const UInt64 *outSize,\r
1511     ICompressProgressInfo *progress)\r
1512 {\r
1513   #ifndef _NO_EXCEPTIONS\r
1514   try \r
1515   { \r
1516   #endif\r
1517     return CodeReal(inStream, outStream, inSize, outSize, progress); \r
1518   #ifndef _NO_EXCEPTIONS\r
1519   }\r
1520   catch(const COutBufferException &e) { return e.ErrorCode; }\r
1521   catch(...) { return E_FAIL; }\r
1522   #endif\r
1523 }\r
1524   \r
1525 void CEncoder::FillDistancesPrices()\r
1526 {\r
1527   UInt32 tempPrices[kNumFullDistances];\r
1528   for (UInt32 i = kStartPosModelIndex; i < kNumFullDistances; i++)\r
1529   { \r
1530     UInt32 posSlot = GetPosSlot(i);\r
1531     UInt32 footerBits = ((posSlot >> 1) - 1);\r
1532     UInt32 base = ((2 | (posSlot & 1)) << footerBits);\r
1533     tempPrices[i] = NRangeCoder::ReverseBitTreeGetPrice(_posEncoders + \r
1534       base - posSlot - 1, footerBits, i - base);\r
1535   }\r
1536 \r
1537   for (UInt32 lenToPosState = 0; lenToPosState < kNumLenToPosStates; lenToPosState++)\r
1538   {\r
1539           UInt32 posSlot;\r
1540     NRangeCoder::CBitTreeEncoder<kNumMoveBits, kNumPosSlotBits> &encoder = _posSlotEncoder[lenToPosState];\r
1541     UInt32 *posSlotPrices = _posSlotPrices[lenToPosState];\r
1542     for (posSlot = 0; posSlot < _distTableSize; posSlot++)\r
1543       posSlotPrices[posSlot] = encoder.GetPrice(posSlot);\r
1544     for (posSlot = kEndPosModelIndex; posSlot < _distTableSize; posSlot++)\r
1545       posSlotPrices[posSlot] += ((((posSlot >> 1) - 1) - kNumAlignBits) << NRangeCoder::kNumBitPriceShiftBits);\r
1546 \r
1547     UInt32 *distancesPrices = _distancesPrices[lenToPosState];\r
1548           UInt32 i;\r
1549     for (i = 0; i < kStartPosModelIndex; i++)\r
1550       distancesPrices[i] = posSlotPrices[i];\r
1551     for (; i < kNumFullDistances; i++)\r
1552       distancesPrices[i] = posSlotPrices[GetPosSlot(i)] + tempPrices[i];\r
1553   }\r
1554   _matchPriceCount = 0;\r
1555 }\r
1556 \r
1557 void CEncoder::FillAlignPrices()\r
1558 {\r
1559   for (UInt32 i = 0; i < kAlignTableSize; i++)\r
1560     _alignPrices[i] = _posAlignEncoder.ReverseGetPrice(i);\r
1561   _alignPriceCount = 0;\r
1562 }\r
1563 \r
1564 }}\r