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