LzmaDecoder.cs revision cd66d540cead3f8200b0c73bad9c276d67896c3d 
1// LzmaDecoder.cs
2
3using System;
4
5namespace SevenZip.Compression.LZMA
6{
7	using RangeCoder;
8
9	public class Decoder : ICoder, ISetDecoderProperties // ,System.IO.Stream
10	{
11		class LenDecoder
12		{
13			BitDecoder m_Choice = new BitDecoder();
14			BitDecoder m_Choice2 = new BitDecoder();
15			BitTreeDecoder[] m_LowCoder = new BitTreeDecoder[Base.kNumPosStatesMax];
16			BitTreeDecoder[] m_MidCoder = new BitTreeDecoder[Base.kNumPosStatesMax];
17			BitTreeDecoder m_HighCoder = new BitTreeDecoder(Base.kNumHighLenBits);
18			uint m_NumPosStates = 0;
19
20			public void Create(uint numPosStates)
21			{
22				for (uint posState = m_NumPosStates; posState < numPosStates; posState++)
23				{
24					m_LowCoder[posState] = new BitTreeDecoder(Base.kNumLowLenBits);
25					m_MidCoder[posState] = new BitTreeDecoder(Base.kNumMidLenBits);
26				}
27				m_NumPosStates = numPosStates;
28			}
29
30			public void Init()
31			{
32				m_Choice.Init();
33				for (uint posState = 0; posState < m_NumPosStates; posState++)
34				{
35					m_LowCoder[posState].Init();
36					m_MidCoder[posState].Init();
37				}
38				m_Choice2.Init();
39				m_HighCoder.Init();
40			}
41
42			public uint Decode(RangeCoder.Decoder rangeDecoder, uint posState)
43			{
44				if (m_Choice.Decode(rangeDecoder) == 0)
45					return m_LowCoder[posState].Decode(rangeDecoder);
46				else
47				{
48					uint symbol = Base.kNumLowLenSymbols;
49					if (m_Choice2.Decode(rangeDecoder) == 0)
50						symbol += m_MidCoder[posState].Decode(rangeDecoder);
51					else
52					{
53						symbol += Base.kNumMidLenSymbols;
54						symbol += m_HighCoder.Decode(rangeDecoder);
55					}
56					return symbol;
57				}
58			}
59		}
60
61		class LiteralDecoder
62		{
63			struct Decoder2
64			{
65				BitDecoder[] m_Decoders;
66				public void Create() { m_Decoders = new BitDecoder[0x300]; }
67				public void Init() { for (int i = 0; i < 0x300; i++) m_Decoders[i].Init(); }
68
69				public byte DecodeNormal(RangeCoder.Decoder rangeDecoder)
70				{
71					uint symbol = 1;
72					do
73						symbol = (symbol << 1) | m_Decoders[symbol].Decode(rangeDecoder);
74					while (symbol < 0x100);
75					return (byte)symbol;
76				}
77
78				public byte DecodeWithMatchByte(RangeCoder.Decoder rangeDecoder, byte matchByte)
79				{
80					uint symbol = 1;
81					do
82					{
83						uint matchBit = (uint)(matchByte >> 7) & 1;
84						matchByte <<= 1;
85						uint bit = m_Decoders[((1 + matchBit) << 8) + symbol].Decode(rangeDecoder);
86						symbol = (symbol << 1) | bit;
87						if (matchBit != bit)
88						{
89							while (symbol < 0x100)
90								symbol = (symbol << 1) | m_Decoders[symbol].Decode(rangeDecoder);
91							break;
92						}
93					}
94					while (symbol < 0x100);
95					return (byte)symbol;
96				}
97			}
98
99			Decoder2[] m_Coders;
100			int m_NumPrevBits;
101			int m_NumPosBits;
102			uint m_PosMask;
103
104			public void Create(int numPosBits, int numPrevBits)
105			{
106				if (m_Coders != null && m_NumPrevBits == numPrevBits &&
107					m_NumPosBits == numPosBits)
108					return;
109				m_NumPosBits = numPosBits;
110				m_PosMask = ((uint)1 << numPosBits) - 1;
111				m_NumPrevBits = numPrevBits;
112				uint numStates = (uint)1 << (m_NumPrevBits + m_NumPosBits);
113				m_Coders = new Decoder2[numStates];
114				for (uint i = 0; i < numStates; i++)
115					m_Coders[i].Create();
116			}
117
118			public void Init()
119			{
120				uint numStates = (uint)1 << (m_NumPrevBits + m_NumPosBits);
121				for (uint i = 0; i < numStates; i++)
122					m_Coders[i].Init();
123			}
124
125			uint GetState(uint pos, byte prevByte)
126			{ return ((pos & m_PosMask) << m_NumPrevBits) + (uint)(prevByte >> (8 - m_NumPrevBits)); }
127
128			public byte DecodeNormal(RangeCoder.Decoder rangeDecoder, uint pos, byte prevByte)
129			{ return m_Coders[GetState(pos, prevByte)].DecodeNormal(rangeDecoder); }
130
131			public byte DecodeWithMatchByte(RangeCoder.Decoder rangeDecoder, uint pos, byte prevByte, byte matchByte)
132			{ return m_Coders[GetState(pos, prevByte)].DecodeWithMatchByte(rangeDecoder, matchByte); }
133		};
134
135		LZ.OutWindow m_OutWindow = new LZ.OutWindow();
136		RangeCoder.Decoder m_RangeDecoder = new RangeCoder.Decoder();
137
138		BitDecoder[] m_IsMatchDecoders = new BitDecoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
139		BitDecoder[] m_IsRepDecoders = new BitDecoder[Base.kNumStates];
140		BitDecoder[] m_IsRepG0Decoders = new BitDecoder[Base.kNumStates];
141		BitDecoder[] m_IsRepG1Decoders = new BitDecoder[Base.kNumStates];
142		BitDecoder[] m_IsRepG2Decoders = new BitDecoder[Base.kNumStates];
143		BitDecoder[] m_IsRep0LongDecoders = new BitDecoder[Base.kNumStates << Base.kNumPosStatesBitsMax];
144
145		BitTreeDecoder[] m_PosSlotDecoder = new BitTreeDecoder[Base.kNumLenToPosStates];
146		BitDecoder[] m_PosDecoders = new BitDecoder[Base.kNumFullDistances - Base.kEndPosModelIndex];
147
148		BitTreeDecoder m_PosAlignDecoder = new BitTreeDecoder(Base.kNumAlignBits);
149
150		LenDecoder m_LenDecoder = new LenDecoder();
151		LenDecoder m_RepLenDecoder = new LenDecoder();
152
153		LiteralDecoder m_LiteralDecoder = new LiteralDecoder();
154
155		uint m_DictionarySize;
156		uint m_DictionarySizeCheck;
157
158		uint m_PosStateMask;
159
160		public Decoder()
161		{
162			m_DictionarySize = 0xFFFFFFFF;
163			for (int i = 0; i < Base.kNumLenToPosStates; i++)
164				m_PosSlotDecoder[i] = new BitTreeDecoder(Base.kNumPosSlotBits);
165		}
166
167		void SetDictionarySize(uint dictionarySize)
168		{
169			if (m_DictionarySize != dictionarySize)
170			{
171				m_DictionarySize = dictionarySize;
172				m_DictionarySizeCheck = Math.Max(m_DictionarySize, 1);
173				uint blockSize = Math.Max(m_DictionarySizeCheck, (1 << 12));
174				m_OutWindow.Create(blockSize);
175			}
176		}
177
178		void SetLiteralProperties(int lp, int lc)
179		{
180			if (lp > 8)
181				throw new InvalidParamException();
182			if (lc > 8)
183				throw new InvalidParamException();
184			m_LiteralDecoder.Create(lp, lc);
185		}
186
187		void SetPosBitsProperties(int pb)
188		{
189			if (pb > Base.kNumPosStatesBitsMax)
190				throw new InvalidParamException();
191			uint numPosStates = (uint)1 << pb;
192			m_LenDecoder.Create(numPosStates);
193			m_RepLenDecoder.Create(numPosStates);
194			m_PosStateMask = numPosStates - 1;
195		}
196
197		bool _solid = false;
198		void Init(System.IO.Stream inStream, System.IO.Stream outStream)
199		{
200			m_RangeDecoder.Init(inStream);
201			m_OutWindow.Init(outStream, _solid);
202
203			uint i;
204			for (i = 0; i < Base.kNumStates; i++)
205			{
206				for (uint j = 0; j <= m_PosStateMask; j++)
207				{
208					uint index = (i << Base.kNumPosStatesBitsMax) + j;
209					m_IsMatchDecoders[index].Init();
210					m_IsRep0LongDecoders[index].Init();
211				}
212				m_IsRepDecoders[i].Init();
213				m_IsRepG0Decoders[i].Init();
214				m_IsRepG1Decoders[i].Init();
215				m_IsRepG2Decoders[i].Init();
216			}
217
218			m_LiteralDecoder.Init();
219			for (i = 0; i < Base.kNumLenToPosStates; i++)
220				m_PosSlotDecoder[i].Init();
221			// m_PosSpecDecoder.Init();
222			for (i = 0; i < Base.kNumFullDistances - Base.kEndPosModelIndex; i++)
223				m_PosDecoders[i].Init();
224
225			m_LenDecoder.Init();
226			m_RepLenDecoder.Init();
227			m_PosAlignDecoder.Init();
228		}
229
230		public void Code(System.IO.Stream inStream, System.IO.Stream outStream,
231			Int64 inSize, Int64 outSize, ICodeProgress progress)
232		{
233			Init(inStream, outStream);
234
235			Base.State state = new Base.State();
236			state.Init();
237			uint rep0 = 0, rep1 = 0, rep2 = 0, rep3 = 0;
238
239			UInt64 nowPos64 = 0;
240			UInt64 outSize64 = (UInt64)outSize;
241			if (nowPos64 < outSize64)
242			{
243				if (m_IsMatchDecoders[state.Index << Base.kNumPosStatesBitsMax].Decode(m_RangeDecoder) != 0)
244					throw new DataErrorException();
245				state.UpdateChar();
246				byte b = m_LiteralDecoder.DecodeNormal(m_RangeDecoder, 0, 0);
247				m_OutWindow.PutByte(b);
248				nowPos64++;
249			}
250			while (nowPos64 < outSize64)
251			{
252				// UInt64 next = Math.Min(nowPos64 + (1 << 18), outSize64);
253					// while(nowPos64 < next)
254				{
255					uint posState = (uint)nowPos64 & m_PosStateMask;
256					if (m_IsMatchDecoders[(state.Index << Base.kNumPosStatesBitsMax) + posState].Decode(m_RangeDecoder) == 0)
257					{
258						byte b;
259						byte prevByte = m_OutWindow.GetByte(0);
260						if (!state.IsCharState())
261							b = m_LiteralDecoder.DecodeWithMatchByte(m_RangeDecoder,
262								(uint)nowPos64, prevByte, m_OutWindow.GetByte(rep0));
263						else
264							b = m_LiteralDecoder.DecodeNormal(m_RangeDecoder, (uint)nowPos64, prevByte);
265						m_OutWindow.PutByte(b);
266						state.UpdateChar();
267						nowPos64++;
268					}
269					else
270					{
271						uint len;
272						if (m_IsRepDecoders[state.Index].Decode(m_RangeDecoder) == 1)
273						{
274							if (m_IsRepG0Decoders[state.Index].Decode(m_RangeDecoder) == 0)
275							{
276								if (m_IsRep0LongDecoders[(state.Index << Base.kNumPosStatesBitsMax) + posState].Decode(m_RangeDecoder) == 0)
277								{
278									state.UpdateShortRep();
279									m_OutWindow.PutByte(m_OutWindow.GetByte(rep0));
280									nowPos64++;
281									continue;
282								}
283							}
284							else
285							{
286								UInt32 distance;
287								if (m_IsRepG1Decoders[state.Index].Decode(m_RangeDecoder) == 0)
288								{
289									distance = rep1;
290								}
291								else
292								{
293									if (m_IsRepG2Decoders[state.Index].Decode(m_RangeDecoder) == 0)
294										distance = rep2;
295									else
296									{
297										distance = rep3;
298										rep3 = rep2;
299									}
300									rep2 = rep1;
301								}
302								rep1 = rep0;
303								rep0 = distance;
304							}
305							len = m_RepLenDecoder.Decode(m_RangeDecoder, posState) + Base.kMatchMinLen;
306							state.UpdateRep();
307						}
308						else
309						{
310							rep3 = rep2;
311							rep2 = rep1;
312							rep1 = rep0;
313							len = Base.kMatchMinLen + m_LenDecoder.Decode(m_RangeDecoder, posState);
314							state.UpdateMatch();
315							uint posSlot = m_PosSlotDecoder[Base.GetLenToPosState(len)].Decode(m_RangeDecoder);
316							if (posSlot >= Base.kStartPosModelIndex)
317							{
318								int numDirectBits = (int)((posSlot >> 1) - 1);
319								rep0 = ((2 | (posSlot & 1)) << numDirectBits);
320								if (posSlot < Base.kEndPosModelIndex)
321									rep0 += BitTreeDecoder.ReverseDecode(m_PosDecoders,
322											rep0 - posSlot - 1, m_RangeDecoder, numDirectBits);
323								else
324								{
325									rep0 += (m_RangeDecoder.DecodeDirectBits(
326										numDirectBits - Base.kNumAlignBits) << Base.kNumAlignBits);
327									rep0 += m_PosAlignDecoder.ReverseDecode(m_RangeDecoder);
328								}
329							}
330							else
331								rep0 = posSlot;
332						}
333						if (rep0 >= m_OutWindow.TrainSize + nowPos64 || rep0 >= m_DictionarySizeCheck)
334						{
335							if (rep0 == 0xFFFFFFFF)
336								break;
337							throw new DataErrorException();
338						}
339						m_OutWindow.CopyBlock(rep0, len);
340						nowPos64 += len;
341					}
342				}
343			}
344			m_OutWindow.Flush();
345			m_OutWindow.ReleaseStream();
346			m_RangeDecoder.ReleaseStream();
347		}
348
349		public void SetDecoderProperties(byte[] properties)
350		{
351			if (properties.Length < 5)
352				throw new InvalidParamException();
353			int lc = properties[0] % 9;
354			int remainder = properties[0] / 9;
355			int lp = remainder % 5;
356			int pb = remainder / 5;
357			if (pb > Base.kNumPosStatesBitsMax)
358				throw new InvalidParamException();
359			UInt32 dictionarySize = 0;
360			for (int i = 0; i < 4; i++)
361				dictionarySize += ((UInt32)(properties[1 + i])) << (i * 8);
362			SetDictionarySize(dictionarySize);
363			SetLiteralProperties(lp, lc);
364			SetPosBitsProperties(pb);
365		}
366
367		public bool Train(System.IO.Stream stream)
368		{
369			_solid = true;
370			return m_OutWindow.Train(stream);
371		}
372
373		/*
374		public override bool CanRead { get { return true; }}
375		public override bool CanWrite { get { return true; }}
376		public override bool CanSeek { get { return true; }}
377		public override long Length { get { return 0; }}
378		public override long Position
379		{
380			get { return 0;	}
381			set { }
382		}
383		public override void Flush() { }
384		public override int Read(byte[] buffer, int offset, int count)
385		{
386			return 0;
387		}
388		public override void Write(byte[] buffer, int offset, int count)
389		{
390		}
391		public override long Seek(long offset, System.IO.SeekOrigin origin)
392		{
393			return 0;
394		}
395		public override void SetLength(long value) {}
396		*/
397	}
398}
399