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
29namespace NCompress {
30namespace NLZMA {
31
32// struct CCrcInit { CCrcInit() { InitCrcTable(); } } g_CrcInit;
33
34const int kDefaultDictionaryLogSize = 22;
35const UInt32 kNumFastBytesDefault = 0x20;
36
37#ifndef LZMA_LOG_BSR
38Byte g_FastPos[1 << kNumLogBits];
39
40class CFastPosInit
41{
42public:
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
61void 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
75void 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
102UInt32 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
132namespace NLength {
133
134void 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
146void 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
169void 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
194CEncoder::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
218static void *SzAlloc(size_t size) { return BigAlloc(size); }
219static void SzFree(void *address) { BigFree(address); }
220ISzAlloc g_Alloc = { SzAlloc, SzFree };
221
222CEncoder::~CEncoder()
223{
224  #ifdef COMPRESS_MF_MT
225  MatchFinderMt_Destruct(&_matchFinderMt, &g_Alloc);
226  #endif
227  MatchFinder_Free(&_matchFinderBase, &g_Alloc);
228}
229
230static const UInt32 kBigHashDicLimit = (UInt32)1 << 24;
231
232HRESULT 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
270inline wchar_t GetUpperChar(wchar_t c)
271{
272  if (c >= 'a' && c <= 'z')
273    c -= 0x20;
274  return c;
275}
276
277static 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
318STDMETHODIMP 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
450STDMETHODIMP 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
460STDMETHODIMP CEncoder::SetOutStream(ISequentialOutStream *outStream)
461{
462  _rangeEncoder.SetStream(outStream);
463  return S_OK;
464}
465
466STDMETHODIMP CEncoder::ReleaseOutStream()
467{
468  _rangeEncoder.ReleaseStream();
469  return S_OK;
470}
471
472HRESULT 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
516static int ttt = 0;
517#endif
518
519void 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
532UInt32 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/*
567Out:
568  (lenRes == 1) && (backRes == 0xFFFFFFFF) means Literal
569*/
570
571UInt32 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
1074static inline bool ChangePair(UInt32 smallDist, UInt32 bigDist)
1075{
1076  return ((bigDist >> 7) > smallDist);
1077}
1078
1079UInt32 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
1111UInt32 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
1238HRESULT 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
1248void 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
1269HRESULT 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
1298HRESULT 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
1323static HRes MyRead(void *object, void *data, UInt32 size, UInt32 *processedSize)
1324{
1325  return (HRes)((CSeqInStream *)object)->RealStream->Read(data, size, processedSize);
1326}
1327
1328HRESULT 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
1492STDMETHODIMP 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
1508void 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
1540void CEncoder::FillAlignPrices()
1541{
1542  for (UInt32 i = 0; i < kAlignTableSize; i++)
1543    _alignPrices[i] = _posAlignEncoder.ReverseGetPrice(i);
1544  _alignPriceCount = 0;
1545}
1546
1547}}
1548