1// LzBinTree.cs
2
3using System;
4
5namespace SevenZip.Compression.LZ
6{
7	public class BinTree : InWindow, IMatchFinder
8	{
9		UInt32 _cyclicBufferPos;
10		UInt32 _cyclicBufferSize = 0;
11		UInt32 _matchMaxLen;
12
13		UInt32[] _son;
14		UInt32[] _hash;
15
16		UInt32 _cutValue = 0xFF;
17		UInt32 _hashMask;
18		UInt32 _hashSizeSum = 0;
19
20		bool HASH_ARRAY = true;
21
22		const UInt32 kHash2Size = 1 << 10;
23		const UInt32 kHash3Size = 1 << 16;
24		const UInt32 kBT2HashSize = 1 << 16;
25		const UInt32 kStartMaxLen = 1;
26		const UInt32 kHash3Offset = kHash2Size;
27		const UInt32 kEmptyHashValue = 0;
28		const UInt32 kMaxValForNormalize = ((UInt32)1 << 31) - 1;
29
30		UInt32 kNumHashDirectBytes = 0;
31		UInt32 kMinMatchCheck = 4;
32		UInt32 kFixHashSize = kHash2Size + kHash3Size;
33
34		public void SetType(int numHashBytes)
35		{
36			HASH_ARRAY = (numHashBytes > 2);
37			if (HASH_ARRAY)
38			{
39				kNumHashDirectBytes = 0;
40				kMinMatchCheck = 4;
41				kFixHashSize = kHash2Size + kHash3Size;
42			}
43			else
44			{
45				kNumHashDirectBytes = 2;
46				kMinMatchCheck = 2 + 1;
47				kFixHashSize = 0;
48			}
49		}
50
51		public new void SetStream(System.IO.Stream stream) { base.SetStream(stream); }
52		public new void ReleaseStream() { base.ReleaseStream(); }
53
54		public new void Init()
55		{
56			base.Init();
57			for (UInt32 i = 0; i < _hashSizeSum; i++)
58				_hash[i] = kEmptyHashValue;
59			_cyclicBufferPos = 0;
60			ReduceOffsets(-1);
61		}
62
63		public new void MovePos()
64		{
65			if (++_cyclicBufferPos >= _cyclicBufferSize)
66				_cyclicBufferPos = 0;
67			base.MovePos();
68			if (_pos == kMaxValForNormalize)
69				Normalize();
70		}
71
72		public new Byte GetIndexByte(Int32 index) { return base.GetIndexByte(index); }
73
74		public new UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit)
75		{ return base.GetMatchLen(index, distance, limit); }
76
77		public new UInt32 GetNumAvailableBytes() { return base.GetNumAvailableBytes(); }
78
79		public void Create(UInt32 historySize, UInt32 keepAddBufferBefore,
80				UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
81		{
82			if (historySize > kMaxValForNormalize - 256)
83				throw new Exception();
84			_cutValue = 16 + (matchMaxLen >> 1);
85
86			UInt32 windowReservSize = (historySize + keepAddBufferBefore +
87					matchMaxLen + keepAddBufferAfter) / 2 + 256;
88
89			base.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize);
90
91			_matchMaxLen = matchMaxLen;
92
93			UInt32 cyclicBufferSize = historySize + 1;
94			if (_cyclicBufferSize != cyclicBufferSize)
95				_son = new UInt32[(_cyclicBufferSize = cyclicBufferSize) * 2];
96
97			UInt32 hs = kBT2HashSize;
98
99			if (HASH_ARRAY)
100			{
101				hs = historySize - 1;
102				hs |= (hs >> 1);
103				hs |= (hs >> 2);
104				hs |= (hs >> 4);
105				hs |= (hs >> 8);
106				hs >>= 1;
107				hs |= 0xFFFF;
108				if (hs > (1 << 24))
109					hs >>= 1;
110				_hashMask = hs;
111				hs++;
112				hs += kFixHashSize;
113			}
114			if (hs != _hashSizeSum)
115				_hash = new UInt32[_hashSizeSum = hs];
116		}
117
118		public UInt32 GetMatches(UInt32[] distances)
119		{
120			UInt32 lenLimit;
121			if (_pos + _matchMaxLen <= _streamPos)
122				lenLimit = _matchMaxLen;
123			else
124			{
125				lenLimit = _streamPos - _pos;
126				if (lenLimit < kMinMatchCheck)
127				{
128					MovePos();
129					return 0;
130				}
131			}
132
133			UInt32 offset = 0;
134			UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
135			UInt32 cur = _bufferOffset + _pos;
136			UInt32 maxLen = kStartMaxLen; // to avoid items for len < hashSize;
137			UInt32 hashValue, hash2Value = 0, hash3Value = 0;
138
139			if (HASH_ARRAY)
140			{
141				UInt32 temp = CRC.Table[_bufferBase[cur]] ^ _bufferBase[cur + 1];
142				hash2Value = temp & (kHash2Size - 1);
143				temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
144				hash3Value = temp & (kHash3Size - 1);
145				hashValue = (temp ^ (CRC.Table[_bufferBase[cur + 3]] << 5)) & _hashMask;
146			}
147			else
148				hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8);
149
150			UInt32 curMatch = _hash[kFixHashSize + hashValue];
151			if (HASH_ARRAY)
152			{
153				UInt32 curMatch2 = _hash[hash2Value];
154				UInt32 curMatch3 = _hash[kHash3Offset + hash3Value];
155				_hash[hash2Value] = _pos;
156				_hash[kHash3Offset + hash3Value] = _pos;
157				if (curMatch2 > matchMinPos)
158					if (_bufferBase[_bufferOffset + curMatch2] == _bufferBase[cur])
159					{
160						distances[offset++] = maxLen = 2;
161						distances[offset++] = _pos - curMatch2 - 1;
162					}
163				if (curMatch3 > matchMinPos)
164					if (_bufferBase[_bufferOffset + curMatch3] == _bufferBase[cur])
165					{
166						if (curMatch3 == curMatch2)
167							offset -= 2;
168						distances[offset++] = maxLen = 3;
169						distances[offset++] = _pos - curMatch3 - 1;
170						curMatch2 = curMatch3;
171					}
172				if (offset != 0 && curMatch2 == curMatch)
173				{
174					offset -= 2;
175					maxLen = kStartMaxLen;
176				}
177			}
178
179			_hash[kFixHashSize + hashValue] = _pos;
180
181			UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
182			UInt32 ptr1 = (_cyclicBufferPos << 1);
183
184			UInt32 len0, len1;
185			len0 = len1 = kNumHashDirectBytes;
186
187			if (kNumHashDirectBytes != 0)
188			{
189				if (curMatch > matchMinPos)
190				{
191					if (_bufferBase[_bufferOffset + curMatch + kNumHashDirectBytes] !=
192							_bufferBase[cur + kNumHashDirectBytes])
193					{
194						distances[offset++] = maxLen = kNumHashDirectBytes;
195						distances[offset++] = _pos - curMatch - 1;
196					}
197				}
198			}
199
200			UInt32 count = _cutValue;
201
202			while(true)
203			{
204				if(curMatch <= matchMinPos || count-- == 0)
205				{
206					_son[ptr0] = _son[ptr1] = kEmptyHashValue;
207					break;
208				}
209				UInt32 delta = _pos - curMatch;
210				UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ?
211							(_cyclicBufferPos - delta) :
212							(_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
213
214				UInt32 pby1 = _bufferOffset + curMatch;
215				UInt32 len = Math.Min(len0, len1);
216				if (_bufferBase[pby1 + len] == _bufferBase[cur + len])
217				{
218					while(++len != lenLimit)
219						if (_bufferBase[pby1 + len] != _bufferBase[cur + len])
220							break;
221					if (maxLen < len)
222					{
223						distances[offset++] = maxLen = len;
224						distances[offset++] = delta - 1;
225						if (len == lenLimit)
226						{
227							_son[ptr1] = _son[cyclicPos];
228							_son[ptr0] = _son[cyclicPos + 1];
229							break;
230						}
231					}
232				}
233				if (_bufferBase[pby1 + len] < _bufferBase[cur + len])
234				{
235					_son[ptr1] = curMatch;
236					ptr1 = cyclicPos + 1;
237					curMatch = _son[ptr1];
238					len1 = len;
239				}
240				else
241				{
242					_son[ptr0] = curMatch;
243					ptr0 = cyclicPos;
244					curMatch = _son[ptr0];
245					len0 = len;
246				}
247			}
248			MovePos();
249			return offset;
250		}
251
252		public void Skip(UInt32 num)
253		{
254			do
255			{
256				UInt32 lenLimit;
257				if (_pos + _matchMaxLen <= _streamPos)
258					lenLimit = _matchMaxLen;
259				else
260				{
261					lenLimit = _streamPos - _pos;
262					if (lenLimit < kMinMatchCheck)
263					{
264						MovePos();
265						continue;
266					}
267				}
268
269				UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
270				UInt32 cur = _bufferOffset + _pos;
271
272				UInt32 hashValue;
273
274				if (HASH_ARRAY)
275				{
276					UInt32 temp = CRC.Table[_bufferBase[cur]] ^ _bufferBase[cur + 1];
277					UInt32 hash2Value = temp & (kHash2Size - 1);
278					_hash[hash2Value] = _pos;
279					temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
280					UInt32 hash3Value = temp & (kHash3Size - 1);
281					_hash[kHash3Offset + hash3Value] = _pos;
282					hashValue = (temp ^ (CRC.Table[_bufferBase[cur + 3]] << 5)) & _hashMask;
283				}
284				else
285					hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8);
286
287				UInt32 curMatch = _hash[kFixHashSize + hashValue];
288				_hash[kFixHashSize + hashValue] = _pos;
289
290				UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
291				UInt32 ptr1 = (_cyclicBufferPos << 1);
292
293				UInt32 len0, len1;
294				len0 = len1 = kNumHashDirectBytes;
295
296				UInt32 count = _cutValue;
297				while (true)
298				{
299					if (curMatch <= matchMinPos || count-- == 0)
300					{
301						_son[ptr0] = _son[ptr1] = kEmptyHashValue;
302						break;
303					}
304
305					UInt32 delta = _pos - curMatch;
306					UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ?
307								(_cyclicBufferPos - delta) :
308								(_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
309
310					UInt32 pby1 = _bufferOffset + curMatch;
311					UInt32 len = Math.Min(len0, len1);
312					if (_bufferBase[pby1 + len] == _bufferBase[cur + len])
313					{
314						while (++len != lenLimit)
315							if (_bufferBase[pby1 + len] != _bufferBase[cur + len])
316								break;
317						if (len == lenLimit)
318						{
319							_son[ptr1] = _son[cyclicPos];
320							_son[ptr0] = _son[cyclicPos + 1];
321							break;
322						}
323					}
324					if (_bufferBase[pby1 + len] < _bufferBase[cur + len])
325					{
326						_son[ptr1] = curMatch;
327						ptr1 = cyclicPos + 1;
328						curMatch = _son[ptr1];
329						len1 = len;
330					}
331					else
332					{
333						_son[ptr0] = curMatch;
334						ptr0 = cyclicPos;
335						curMatch = _son[ptr0];
336						len0 = len;
337					}
338				}
339				MovePos();
340			}
341			while (--num != 0);
342		}
343
344		void NormalizeLinks(UInt32[] items, UInt32 numItems, UInt32 subValue)
345		{
346			for (UInt32 i = 0; i < numItems; i++)
347			{
348				UInt32 value = items[i];
349				if (value <= subValue)
350					value = kEmptyHashValue;
351				else
352					value -= subValue;
353				items[i] = value;
354			}
355		}
356
357		void Normalize()
358		{
359			UInt32 subValue = _pos - _cyclicBufferSize;
360			NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
361			NormalizeLinks(_hash, _hashSizeSum, subValue);
362			ReduceOffsets((Int32)subValue);
363		}
364
365		public void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; }
366	}
367}
368