vcs.maemo.org Git - physicsfs/blob - lzma/CPP/7zip/Compress/LZMA/LZMAEncoder.cpp

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