context: // LzmaEncoder.cs
  /*
  LZMA SDK is in the public domain
  
  LZMA SDK is written and placed in the public domain by Igor Pavlov.
  
  Some code in LZMA SDK is based on public domain code from another developers:
    1) PPMd var.H (2001): Dmitry Shkarin
    2) SHA-256: Wei Dai (Crypto++ library)
  */
  using System;
  
  namespace SevenZip.Compression.LZMA
  {
  	using RangeCoder;
  
  	public class Encoder : ICoder, ISetCoderProperties, IWriteCoderProperties
  	{
  		enum EMatchFinderType
  		{
  			BT2,
  			BT4,
  		};
  
  		const UInt32 kIfinityPrice = 0xFFFFFFF;
  
  		static Byte[] g_FastPos = new Byte[1 << 11];
  
  		static Encoder()
  		{
  			const Byte kFastSlots = 22;
  			int c = 2;
  			g_FastPos[0] = 0;
  			g_FastPos[1] = 1;
  			for (Byte slotFast = 2; slotFast < kFastSlots; slotFast++)
  			{
  				UInt32 k = ((UInt32)1 << ((slotFast >> 1) - 1));
  				for (UInt32 j = 0; j < k; j++, c++)
  					g_FastPos[c] = slotFast;
  			}
  		}
  
  		static UInt32 GetPosSlot(UInt32 pos)
  		{
  			if (pos < (1 << 11))
  				return g_FastPos[pos];
  			if (pos < (1 << 21))
  				return (UInt32)(g_FastPos[pos >> 10] + 20);
  			return (UInt32)(g_FastPos[pos >> 20] + 40);
  		}
  
  		static UInt32 GetPosSlot2(UInt32 pos)
  		{
  			if (pos < (1 << 17))
  				return (UInt32)(g_FastPos[pos >> 6] + 12);
  			if (pos < (1 << 27))
  				return (UInt32)(g_FastPos[pos >> 16] + 32);
  			return (UInt32)(g_FastPos[pos >> 26] + 52);
  		}
  
  		Base.State _state = new Base.State();
  		Byte _previousByte;
  		UInt32[] _repDistances = new UInt32[Base.kNumRepDistances];
  
  		void BaseInit()
  		{
  			_state.Init();
  			_previousByte = 0;
  			for (UInt32 i = 0; i < Base.kNumRepDistances; i++)
  				_repDistances[i] = 0;
  		}
  
  		const int kDefaultDictionaryLogSize = 22;
  		const UInt32 kNumFastBytesDefault = 0x20;
  
  		class LiteralEncoder
  		{
  			public struct Encoder2
  			{
  				BitEncoder[] m_Encoders;
  
  				public void Create() { m_Encoders = new BitEncoder[0x300]; }
  
  				public void Init() { for (int i = 0; i < 0x300; i++) m_Encoders[i].Init(); }
  
  				public void Encode(RangeCoder.Encoder rangeEncoder, byte symbol)
  				{
  					uint context = 1;
  					for (int i = 7; i >= 0; i--)
  					{
  						uint bit = (uint)((symbol >> i) & 1);
  						m_Encoders[context].Encode(rangeEncoder, bit);
  						context = (context << 1) | bit;
  					}
  				}
  
  				public void EncodeMatched(RangeCoder.Encoder rangeEncoder, byte matchByte, byte symbol)
  				{
  					uint context = 1;
  					bool same = true;
  					for (int i = 7; i >= 0; i--)
  					{
  						uint bit = (uint)((symbol >> i) & 1);
  						uint state = context;
  						if (same)
  						{
  							uint matchBit = (uint)((matchByte >> i) & 1);
  							state += ((1 + matchBit) << 8);
  							same = (matchBit == bit);
  						}
  						m_Encoders[state].Encode(rangeEncoder, bit);
  						context = (context << 1) | bit;
  					}
  				}
  
  				public uint GetPrice(bool matchMode, byte matchByte, byte symbol)
  				{
  					uint price = 0;
  					uint context = 1;
  					int i = 7;
  					if (matchMode)
  					{
  						for (; i >= 0; i--)
  						{
  							uint matchBit = (uint)(matchByte >> i) & 1;
  							uint bit = (uint)(symbol >> i) & 1;
  							price += m_Encoders[((1 + matchBit) << 8) + context].GetPrice(bit);
  							context = (context << 1) | bit;
  							if (matchBit != bit)
  							{
  								i--;
  								break;
  							}
  						}
  					}
  					for (; i >= 0; i--)
  					{
  						uint bit = (uint)(symbol >> i) & 1;
  						price += m_Encoders[context].GetPrice(bit);
  						context = (context << 1) | bit;
  					}
  					return price;
  				}
  			}
  
  			Encoder2[] m_Coders;
  			int m_NumPrevBits;
  			int m_NumPosBits;
  			uint m_PosMask;
  
  			public void Create(int numPosBits, int numPrevBits)
  			{
  				if (m_Coders != null && m_NumPrevBits == numPrevBits && m_NumPosBits == numPosBits)
  					return;
  				m_NumPosBits = numPosBits;
  				m_PosMask = ((uint)1 << numPosBits) - 1;
  				m_NumPrevBits = numPrevBits;
  				uint numStates = (uint)1 << (m_NumPrevBits + m_NumPosBits);
  				m_Coders = new Encoder2[numStates];
  				for (uint i = 0; i < numStates; i++)
  					m_Coders[i].Create();
  			}
  
  			public void Init()
  			{
  				uint numStates = (uint)1 << (m_NumPrevBits + m_NumPosBits);
  				for (uint i = 0; i < numStates; i++)
  					m_Coders[i].Init();
  			}
  
  			public Encoder2 GetSubCoder(UInt32 pos, Byte prevByte)
  			{ return m_Coders[((pos & m_PosMask) << m_NumPrevBits) + (uint)(prevByte >> (8 - m_NumPrevBits))]; }
  		}
  
  		class LenEncoder
  		{
  			RangeCoder.BitEncoder _choice = new RangeCoder.BitEncoder();
  			RangeCoder.BitEncoder _choice2 = new RangeCoder.BitEncoder();
  			RangeCoder.BitTreeEncoder[] _lowCoder = new RangeCoder.BitTreeEncoder[Base.kNumPosStatesEncodingMax];
  			RangeCoder.BitTreeEncoder[] _midCoder = new RangeCoder.BitTreeEncoder[Base.kNumPosStatesEncodingMax];
  			RangeCoder.BitTreeEncoder _highCoder = new RangeCoder.BitTreeEncoder(Base.kNumHighLenBits);
  
  			public LenEncoder()
  			{
  				for (UInt32 posState = 0; posState < Base.kNumPosStatesEncodingMax; posState++)
  				{
  					_lowCoder[posState] = new RangeCoder.BitTreeEncoder(Base.kNumLowLenBits);
  					_midCoder[posState] = new RangeCoder.BitTreeEncoder(Base.kNumMidLenBits);
  				}
  			}
  
  			public void Init(UInt32 numPosStates)
  			{
  				_choice.Init();
  				_choice2.Init();
  				for (UInt32 posState = 0; posState < numPosStates; posState++)
  				{
  					_lowCoder[posState].Init();
  					_midCoder[posState].Init();
  				}
  				_highCoder.Init();
  			}
  
  			public void Encode(RangeCoder.Encoder rangeEncoder, UInt32 symbol, UInt32 posState)
  			{
  				if (symbol < Base.kNumLowLenSymbols)
  				{
  					_choice.Encode(rangeEncoder, 0);
  					_lowCoder[posState].Encode(rangeEncoder, symbol);
  				}
  				else
  				{
  					symbol -= Base.kNumLowLenSymbols;
  					_choice.Encode(rangeEncoder, 1);
  					if (symbol < Base.kNumMidLenSymbols)
  					{
  						_choice2.Encode(rangeEncoder, 0);
  						_midCoder[posState].Encode(rangeEncoder, symbol);
  					}
  					else
  					{
  						_choice2.Encode(rangeEncoder, 1);
  						_highCoder.Encode(rangeEncoder, symbol - Base.kNumMidLenSymbols);
  					}
  				}
  			}
  
  			public void SetPrices(UInt32 posState, UInt32 numSymbols, UInt32[] prices, UInt32 st)
  			{
  				UInt32 a0 = _choice.GetPrice0();
  				UInt32 a1 = _choice.GetPrice1();
  				UInt32 b0 = a1 + _choice2.GetPrice0();
  				UInt32 b1 = a1 + _choice2.GetPrice1();
  				UInt32 i = 0;
  				for (i = 0; i < Base.kNumLowLenSymbols; i++)
  				{
  					if (i >= numSymbols)
  						return;
  					prices[st + i] = a0 + _lowCoder[posState].GetPrice(i);
  				}
  				for (; i < Base.kNumLowLenSymbols + Base.kNumMidLenSymbols; i++)
  				{
  					if (i >= numSymbols)
  						return;
  					prices[st + i] = b0 + _midCoder[posState].GetPrice(i - Base.kNumLowLenSymbols);
  				}
  				for (; i < numSymbols; i++)
  					prices[st + i] = b1 + _highCoder.GetPrice(i - Base.kNumLowLenSymbols - Base.kNumMidLenSymbols);
  			}
  		};
  
  		const UInt32 kNumLenSpecSymbols = Base.kNumLowLenSymbols + Base.kNumMidLenSymbols;
  
  		class LenPriceTableEncoder : LenEncoder
  		{
  			UInt32[] _prices = new UInt32[Base.kNumLenSymbols << Base.kNumPosStatesBitsEncodingMax];
  			UInt32 _tableSize;
  			UInt32[] _counters = new UInt32[Base.kNumPosStatesEncodingMax];
  
  			public void SetTableSize(UInt32 tableSize) { _tableSize = tableSize; }
  
  			public UInt32 GetPrice(UInt32 symbol, UInt32 posState)
  			{
  				return _prices[posState * Base.kNumLenSymbols + symbol];
  			}
  
  			void UpdateTable(UInt32 posState)
  			{
  				SetPrices(posState, _tableSize, _prices, posState * Base.kNumLenSymbols);
  				_counters[posState] = _tableSize;
  			}
  
  			public void UpdateTables(UInt32 numPosStates)
  			{
  				for (UInt32 posState = 0; posState < numPosStates; posState++)
  					UpdateTable(posState);
  			}
  
  			public new void Encode(RangeCoder.Encoder rangeEncoder, UInt32 symbol, UInt32 posState)
  			{
  				base.Encode(rangeEncoder, symbol, posState);
  				if (--_counters[posState] == 0)
  					UpdateTable(posState);
  			}
  		}
  
  		const UInt32 kNumOpts = 1 << 12;
  		class Optimal
  		{
  			public Base.State State;
  
  			public bool Prev1IsChar;
  			public bool Prev2;
  
  			public UInt32 PosPrev2;
  			public UInt32 BackPrev2;
  
  			public UInt32 Price;
  			public UInt32 PosPrev;
  			public UInt32 BackPrev;
  
  			public UInt32 Backs0;
  			public UInt32 Backs1;
  			public UInt32 Backs2;
  			public UInt32 Backs3;
  
  			public void MakeAsChar() { BackPrev = 0xFFFFFFFF; Prev1IsChar = false; }
  			public void MakeAsShortRep() { BackPrev = 0; ; Prev1IsChar = false; }
  			public bool IsShortRep() { return (BackPrev == 0); }
  		};
  		Optimal[] _optimum = new Optimal[kNumOpts];
  		LZ.IMatchFinder _matchFinder = null;
  		RangeCoder.Encoder _rangeEncoder = new RangeCoder.Encoder();
  
  		RangeCoder.BitEncoder[] _isMatch = new RangeCoder.BitEncoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
  		RangeCoder.BitEncoder[] _isRep = new RangeCoder.BitEncoder[Base.kNumStates];
  		RangeCoder.BitEncoder[] _isRepG0 = new RangeCoder.BitEncoder[Base.kNumStates];
  		RangeCoder.BitEncoder[] _isRepG1 = new RangeCoder.BitEncoder[Base.kNumStates];
  		RangeCoder.BitEncoder[] _isRepG2 = new RangeCoder.BitEncoder[Base.kNumStates];
  		RangeCoder.BitEncoder[] _isRep0Long = new RangeCoder.BitEncoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
  
  		RangeCoder.BitTreeEncoder[] _posSlotEncoder = new RangeCoder.BitTreeEncoder[Base.kNumLenToPosStates];
  		
  		RangeCoder.BitEncoder[] _posEncoders = new RangeCoder.BitEncoder[Base.kNumFullDistances - Base.kEndPosModelIndex];
  		RangeCoder.BitTreeEncoder _posAlignEncoder = new RangeCoder.BitTreeEncoder(Base.kNumAlignBits);
  
  		LenPriceTableEncoder _lenEncoder = new LenPriceTableEncoder();
  		LenPriceTableEncoder _repMatchLenEncoder = new LenPriceTableEncoder();
  
  		LiteralEncoder _literalEncoder = new LiteralEncoder();
  
  		UInt32[] _matchDistances = new UInt32[Base.kMatchMaxLen * 2 + 2];
  		
  		UInt32 _numFastBytes = kNumFastBytesDefault;
  		UInt32 _longestMatchLength;
  		UInt32 _numDistancePairs;
  
  		UInt32 _additionalOffset;
  
  		UInt32 _optimumEndIndex;
  		UInt32 _optimumCurrentIndex;
  
  		bool _longestMatchWasFound;
  
  		UInt32[] _posSlotPrices = new UInt32[1 << (Base.kNumPosSlotBits + Base.kNumLenToPosStatesBits)];
  		UInt32[] _distancesPrices = new UInt32[Base.kNumFullDistances << Base.kNumLenToPosStatesBits];
  		UInt32[] _alignPrices = new UInt32[Base.kAlignTableSize];
  		UInt32 _alignPriceCount;
  
  		UInt32 _distTableSize = (kDefaultDictionaryLogSize * 2);
  
  		int _posStateBits = 2;
  		UInt32 _posStateMask = (4 - 1);
  		int _numLiteralPosStateBits = 0;
  		int _numLiteralContextBits = 3;
  
  		UInt32 _dictionarySize = (1 << kDefaultDictionaryLogSize);
  		UInt32 _dictionarySizePrev = 0xFFFFFFFF;
  		UInt32 _numFastBytesPrev = 0xFFFFFFFF;
  
  		Int64 nowPos64;
  		bool _finished;
  		System.IO.Stream _inStream;
  
  		EMatchFinderType _matchFinderType = EMatchFinderType.BT4;
  		bool _writeEndMark = false;
  		
  		bool _needReleaseMFStream;
  
  		void Create()
  		{
  			if (_matchFinder == null)
  			{
  				LZ.BinTree bt = new LZ.BinTree();
  				int numHashBytes = 4;
  				if (_matchFinderType == EMatchFinderType.BT2)
  					numHashBytes = 2;
  				bt.SetType(numHashBytes);
  				_matchFinder = bt;
  			}
  			_literalEncoder.Create(_numLiteralPosStateBits, _numLiteralContextBits);
  
  			if (_dictionarySize == _dictionarySizePrev && _numFastBytesPrev == _numFastBytes)
  				return;
  			_matchFinder.Create(_dictionarySize, kNumOpts, _numFastBytes, Base.kMatchMaxLen + 1);
  			_dictionarySizePrev = _dictionarySize;
  			_numFastBytesPrev = _numFastBytes;
  		}
  
  		public Encoder()
  		{
  			for (int i = 0; i < kNumOpts; i++)
  				_optimum[i] = new Optimal();
  			for (int i = 0; i < Base.kNumLenToPosStates; i++)
  				_posSlotEncoder[i] = new RangeCoder.BitTreeEncoder(Base.kNumPosSlotBits);
  		}
  
  		void SetWriteEndMarkerMode(bool writeEndMarker)
  		{
  			_writeEndMark = writeEndMarker;
  		}
  
  		void Init()
  		{
  			BaseInit();
  			_rangeEncoder.Init();
  
  			uint i;
  			for (i = 0; i < Base.kNumStates; i++)
  			{
  				for (uint j = 0; j <= _posStateMask; j++)
  				{
  					uint complexState = (i << Base.kNumPosStatesBitsMax) + j;
  					_isMatch[complexState].Init();
  					_isRep0Long[complexState].Init();
  				}
  				_isRep[i].Init();
  				_isRepG0[i].Init();
  				_isRepG1[i].Init();
  				_isRepG2[i].Init();
  			}
  			_literalEncoder.Init();
  			for (i = 0; i < Base.kNumLenToPosStates; i++)
  				_posSlotEncoder[i].Init();
  			for (i = 0; i < Base.kNumFullDistances - Base.kEndPosModelIndex; i++)
  				_posEncoders[i].Init();
  
  			_lenEncoder.Init((UInt32)1 << _posStateBits);
  			_repMatchLenEncoder.Init((UInt32)1 << _posStateBits);
  
  			_posAlignEncoder.Init();
  
  			_longestMatchWasFound = false;
  			_optimumEndIndex = 0;
  			_optimumCurrentIndex = 0;
  			_additionalOffset = 0;
  		}
  
  		void ReadMatchDistances(out UInt32 lenRes, out UInt32 numDistancePairs)
  		{
  			lenRes = 0;
  			numDistancePairs = _matchFinder.GetMatches(_matchDistances);
  			if (numDistancePairs > 0)
  			{
  				lenRes = _matchDistances[numDistancePairs - 2];
  				if (lenRes == _numFastBytes)
  					lenRes += _matchFinder.GetMatchLen((int)lenRes - 1, _matchDistances[numDistancePairs - 1],
  						Base.kMatchMaxLen - lenRes);
  			}
  			_additionalOffset++;
  		}
  
  
  		void MovePos(UInt32 num)
  		{
  			if (num > 0)
  			{
  				_matchFinder.Skip(num);
  				_additionalOffset += num;
  			}
  		}
  
  		UInt32 GetRepLen1Price(Base.State state, UInt32 posState)
  		{
  			return _isRepG0[state.Index].GetPrice0() +
  					_isRep0Long[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice0();
  		}
  
  		UInt32 GetPureRepPrice(UInt32 repIndex, Base.State state, UInt32 posState)
  		{
  			UInt32 price;
  			if (repIndex == 0)
  			{
  				price = _isRepG0[state.Index].GetPrice0();
  				price += _isRep0Long[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice1();
  			}
  			else
  			{
  				price = _isRepG0[state.Index].GetPrice1();
  				if (repIndex == 1)
  					price += _isRepG1[state.Index].GetPrice0();
  				else
  				{
  					price += _isRepG1[state.Index].GetPrice1();
  					price += _isRepG2[state.Index].GetPrice(repIndex - 2);
  				}
  			}
  			return price;
  		}
  
  		UInt32 GetRepPrice(UInt32 repIndex, UInt32 len, Base.State state, UInt32 posState)
  		{
  			UInt32 price = _repMatchLenEncoder.GetPrice(len - Base.kMatchMinLen, posState);
  			return price + GetPureRepPrice(repIndex, state, posState);
  		}
  	
  		UInt32 GetPosLenPrice(UInt32 pos, UInt32 len, UInt32 posState)
  		{
  			UInt32 price;
  			UInt32 lenToPosState = Base.GetLenToPosState(len);
  			if (pos < Base.kNumFullDistances)
  				price = _distancesPrices[(lenToPosState * Base.kNumFullDistances) + pos];
  			else
  				price = _posSlotPrices[(lenToPosState << Base.kNumPosSlotBits) + GetPosSlot2(pos)] +
  					_alignPrices[pos & Base.kAlignMask];
  			return price + _lenEncoder.GetPrice(len - Base.kMatchMinLen, posState);
  		}
  
  		UInt32 Backward(out UInt32 backRes, UInt32 cur)
  		{
  			_optimumEndIndex = cur;
  			UInt32 posMem = _optimum[cur].PosPrev;
  			UInt32 backMem = _optimum[cur].BackPrev;
  			do
  			{
  				if (_optimum[cur].Prev1IsChar)
  				{
  					_optimum[posMem].MakeAsChar();
  					_optimum[posMem].PosPrev = posMem - 1;
  					if (_optimum[cur].Prev2)
  					{
  						_optimum[posMem - 1].Prev1IsChar = false;
  						_optimum[posMem - 1].PosPrev = _optimum[cur].PosPrev2;
  						_optimum[posMem - 1].BackPrev = _optimum[cur].BackPrev2;
  					}
  				}
  				UInt32 posPrev = posMem;
  				UInt32 backCur = backMem;
  
  				backMem = _optimum[posPrev].BackPrev;
  				posMem = _optimum[posPrev].PosPrev;
  
  				_optimum[posPrev].BackPrev = backCur;
  				_optimum[posPrev].PosPrev = cur;
  				cur = posPrev;
  			}
  			while (cur > 0);
  			backRes = _optimum[0].BackPrev;
  			_optimumCurrentIndex = _optimum[0].PosPrev;
  			return _optimumCurrentIndex;
  		}
  
  		UInt32[] reps = new UInt32[Base.kNumRepDistances];
  		UInt32[] repLens = new UInt32[Base.kNumRepDistances];
  
  
  		UInt32 GetOptimum(UInt32 position, out UInt32 backRes)
  		{
  			if (_optimumEndIndex != _optimumCurrentIndex)
  			{
  				UInt32 lenRes = _optimum[_optimumCurrentIndex].PosPrev - _optimumCurrentIndex;
  				backRes = _optimum[_optimumCurrentIndex].BackPrev;
  				_optimumCurrentIndex = _optimum[_optimumCurrentIndex].PosPrev;
  				return lenRes;
  			}
  			_optimumCurrentIndex = _optimumEndIndex = 0;
  
  			UInt32 lenMain, numDistancePairs;
  			if (!_longestMatchWasFound)
  			{
  				ReadMatchDistances(out lenMain, out numDistancePairs);
  			}
  			else
  			{
  				lenMain = _longestMatchLength;
  				numDistancePairs = _numDistancePairs;
  				_longestMatchWasFound = false;
  			}
  
  			UInt32 numAvailableBytes = _matchFinder.GetNumAvailableBytes() + 1;
  			if (numAvailableBytes < 2)
  			{
  				backRes = 0xFFFFFFFF;
  				return 1;
  			}
  			if (numAvailableBytes > Base.kMatchMaxLen)
  				numAvailableBytes = Base.kMatchMaxLen;
  
  			UInt32 repMaxIndex = 0;
  			UInt32 i;			
  			for (i = 0; i < Base.kNumRepDistances; i++)
  			{
  				reps[i] = _repDistances[i];
  				repLens[i] = _matchFinder.GetMatchLen(0 - 1, reps[i], Base.kMatchMaxLen);
  				if (repLens[i] > repLens[repMaxIndex])
  					repMaxIndex = i;
  			}
  			if (repLens[repMaxIndex] >= _numFastBytes)
  			{
  				backRes = repMaxIndex;
  				UInt32 lenRes = repLens[repMaxIndex];
  				MovePos(lenRes - 1);
  				return lenRes;
  			}
  
  			if (lenMain >= _numFastBytes)
  			{
  				backRes = _matchDistances[numDistancePairs - 1] + Base.kNumRepDistances;
  				MovePos(lenMain - 1);
  				return lenMain;
  			}
  			
  			Byte currentByte = _matchFinder.GetIndexByte(0 - 1);
  			Byte matchByte = _matchFinder.GetIndexByte((Int32)(0 - _repDistances[0] - 1 - 1));
  
  			if (lenMain < 2 && currentByte != matchByte && repLens[repMaxIndex] < 2)
  			{
  				backRes = (UInt32)0xFFFFFFFF;
  				return 1;
  			}
  
  			_optimum[0].State = _state;
  
  			UInt32 posState = (position & _posStateMask);
  
  			_optimum[1].Price = _isMatch[(_state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice0() +
  					_literalEncoder.GetSubCoder(position, _previousByte).GetPrice(!_state.IsCharState(), matchByte, currentByte);
  			_optimum[1].MakeAsChar();
  
  			UInt32 matchPrice = _isMatch[(_state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice1();
  			UInt32 repMatchPrice = matchPrice + _isRep[_state.Index].GetPrice1();
  
  			if (matchByte == currentByte)
  			{
  				UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(_state, posState);
  				if (shortRepPrice < _optimum[1].Price)
  				{
  					_optimum[1].Price = shortRepPrice;
  					_optimum[1].MakeAsShortRep();
  				}
  			}
  
  			UInt32 lenEnd = ((lenMain >= repLens[repMaxIndex]) ? lenMain : repLens[repMaxIndex]);
  
  			if(lenEnd < 2)
  			{
  				backRes = _optimum[1].BackPrev;
  				return 1;
  			}
  			
  			_optimum[1].PosPrev = 0;
  
  			_optimum[0].Backs0 = reps[0];
  			_optimum[0].Backs1 = reps[1];
  			_optimum[0].Backs2 = reps[2];
  			_optimum[0].Backs3 = reps[3];
  
  			UInt32 len = lenEnd;
  			do
  				_optimum[len--].Price = kIfinityPrice;
  			while (len >= 2);
  
  			for (i = 0; i < Base.kNumRepDistances; i++)
  			{
  				UInt32 repLen = repLens[i];
  				if (repLen < 2)
  					continue;
  				UInt32 price = repMatchPrice + GetPureRepPrice(i, _state, posState);
  				do
  				{
  					UInt32 curAndLenPrice = price + _repMatchLenEncoder.GetPrice(repLen - 2, posState);
  					Optimal optimum = _optimum[repLen];
  					if (curAndLenPrice < optimum.Price)
  					{
  						optimum.Price = curAndLenPrice;
  						optimum.PosPrev = 0;
  						optimum.BackPrev = i;
  						optimum.Prev1IsChar = false;
  					}
  				}
  				while (--repLen >= 2);
  			}
  
  			UInt32 normalMatchPrice = matchPrice + _isRep[_state.Index].GetPrice0();
  			
  			len = ((repLens[0] >= 2) ? repLens[0] + 1 : 2);
  			if (len <= lenMain)
  			{
  				UInt32 offs = 0;
  				while (len > _matchDistances[offs])
  					offs += 2;
  				for (; ; len++)
  				{
  					UInt32 distance = _matchDistances[offs + 1];
  					UInt32 curAndLenPrice = normalMatchPrice + GetPosLenPrice(distance, len, posState);
  					Optimal optimum = _optimum[len];
  					if (curAndLenPrice < optimum.Price)
  					{
  						optimum.Price = curAndLenPrice;
  						optimum.PosPrev = 0;
  						optimum.BackPrev = distance + Base.kNumRepDistances;
  						optimum.Prev1IsChar = false;
  					}
  					if (len == _matchDistances[offs])
  					{
  						offs += 2;
  						if (offs == numDistancePairs)
  							break;
  					}
  				}
  			}
  
  			UInt32 cur = 0;
  
  			while (true)
  			{
  				cur++;
  				if (cur == lenEnd)
  					return Backward(out backRes, cur);
  				UInt32 newLen;
  				ReadMatchDistances(out newLen, out numDistancePairs);
  				if (newLen >= _numFastBytes)
  				{
  					_numDistancePairs = numDistancePairs;
  					_longestMatchLength = newLen;
  					_longestMatchWasFound = true;
  					return Backward(out backRes, cur);
  				}
  				position++;
  				UInt32 posPrev = _optimum[cur].PosPrev;
  				Base.State state;
  				if (_optimum[cur].Prev1IsChar)
  				{
  					posPrev--;
  					if (_optimum[cur].Prev2)
  					{
  						state = _optimum[_optimum[cur].PosPrev2].State;
  						if (_optimum[cur].BackPrev2 < Base.kNumRepDistances)
  							state.UpdateRep();
  						else
  							state.UpdateMatch();
  					}
  					else
  						state = _optimum[posPrev].State;
  					state.UpdateChar();
  				}
  				else
  					state = _optimum[posPrev].State;
  				if (posPrev == cur - 1)
  				{
  					if (_optimum[cur].IsShortRep())
  						state.UpdateShortRep();
  					else
  						state.UpdateChar();
  				}
  				else
  				{
  					UInt32 pos;
  					if (_optimum[cur].Prev1IsChar && _optimum[cur].Prev2)
  					{
  						posPrev = _optimum[cur].PosPrev2;
  						pos = _optimum[cur].BackPrev2;
  						state.UpdateRep();
  					}
  					else
  					{
  						pos = _optimum[cur].BackPrev;
  						if (pos < Base.kNumRepDistances)
  							state.UpdateRep();
  						else
  							state.UpdateMatch();
  					}
  					Optimal opt = _optimum[posPrev];
  					if (pos < Base.kNumRepDistances)
  					{
  						if (pos == 0)
  						{
  							reps[0] = opt.Backs0;
  							reps[1] = opt.Backs1;
  							reps[2] = opt.Backs2;
  							reps[3] = opt.Backs3;
  						}
  						else if (pos == 1)
  						{
  							reps[0] = opt.Backs1;
  							reps[1] = opt.Backs0;
  							reps[2] = opt.Backs2;
  							reps[3] = opt.Backs3;
  						}
  						else if (pos == 2)
  						{
  							reps[0] = opt.Backs2;
  							reps[1] = opt.Backs0;
  							reps[2] = opt.Backs1;
  							reps[3] = opt.Backs3;
  						}
  						else
  						{
  							reps[0] = opt.Backs3;
  							reps[1] = opt.Backs0;
  							reps[2] = opt.Backs1;
  							reps[3] = opt.Backs2;
  						}
  					}
  					else
  					{
  						reps[0] = (pos - Base.kNumRepDistances);
  						reps[1] = opt.Backs0;
  						reps[2] = opt.Backs1;
  						reps[3] = opt.Backs2;
  					}
  				}
  				_optimum[cur].State = state;
  				_optimum[cur].Backs0 = reps[0];
  				_optimum[cur].Backs1 = reps[1];
  				_optimum[cur].Backs2 = reps[2];
  				_optimum[cur].Backs3 = reps[3];
  				UInt32 curPrice = _optimum[cur].Price;
  
  				currentByte = _matchFinder.GetIndexByte(0 - 1);
  				matchByte = _matchFinder.GetIndexByte((Int32)(0 - reps[0] - 1 - 1));
  
  				posState = (position & _posStateMask);
  
  				UInt32 curAnd1Price = curPrice +
  					_isMatch[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice0() +
  					_literalEncoder.GetSubCoder(position, _matchFinder.GetIndexByte(0 - 2)).
  					GetPrice(!state.IsCharState(), matchByte, currentByte);
  
  				Optimal nextOptimum = _optimum[cur + 1];
  
  				bool nextIsChar = false;
  				if (curAnd1Price < nextOptimum.Price)
  				{
  					nextOptimum.Price = curAnd1Price;
  					nextOptimum.PosPrev = cur;
  					nextOptimum.MakeAsChar();
  					nextIsChar = true;
  				}
  
  				matchPrice = curPrice + _isMatch[(state.Index << Base.kNumPosStatesBitsMax) + posState].GetPrice1();
  				repMatchPrice = matchPrice + _isRep[state.Index].GetPrice1();
  
  				if (matchByte == currentByte &&
  					!(nextOptimum.PosPrev < cur && nextOptimum.BackPrev == 0))
  				{
  					UInt32 shortRepPrice = repMatchPrice + GetRepLen1Price(state, posState);
  					if (shortRepPrice <= nextOptimum.Price)
  					{
  						nextOptimum.Price = shortRepPrice;
  						nextOptimum.PosPrev = cur;
  						nextOptimum.MakeAsShortRep();
  						nextIsChar = true;
  					}
  				}
  
  				UInt32 numAvailableBytesFull = _matchFinder.GetNumAvailableBytes() + 1;
  				numAvailableBytesFull = Math.Min(kNumOpts - 1 - cur, numAvailableBytesFull);
  				numAvailableBytes = numAvailableBytesFull;
  
  				if (numAvailableBytes < 2)
  					continue;
  				if (numAvailableBytes > _numFastBytes)
  					numAvailableBytes = _numFastBytes;
  				if (!nextIsChar && matchByte != currentByte)
  				{
  					// try Literal + rep0
  					UInt32 t = Math.Min(numAvailableBytesFull - 1, _numFastBytes);
  					UInt32 lenTest2 = _matchFinder.GetMatchLen(0, reps[0], t);
  					if (lenTest2 >= 2)
  					{
  						Base.State state2 = state;
  						state2.UpdateChar();
  
gt: 						UInt32 posStateNext = (position + 1) & _posStateMask;