// LzmaEncoder.cs

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);