util/cbfstool/lzma/C/7zip/Compress/LZMA/LZMAEncoder.cpp

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