1// LZ.BinTree
2
3package SevenZip.Compression.LZ;
4import java.io.IOException;
5
6
7public class BinTree extends InWindow
8{
9	int _cyclicBufferPos;
10	int _cyclicBufferSize = 0;
11	int _matchMaxLen;
12
13	int[] _son;
14	int[] _hash;
15
16	int _cutValue = 0xFF;
17	int _hashMask;
18	int _hashSizeSum = 0;
19
20	boolean HASH_ARRAY = true;
21
22	static final int kHash2Size = 1 << 10;
23	static final int kHash3Size = 1 << 16;
24	static final int kBT2HashSize = 1 << 16;
25	static final int kStartMaxLen = 1;
26	static final int kHash3Offset = kHash2Size;
27	static final int kEmptyHashValue = 0;
28	static final int kMaxValForNormalize = (1 << 30) - 1;
29
30	int kNumHashDirectBytes = 0;
31	int kMinMatchCheck = 4;
32	int 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
52
53
54	public void Init() throws IOException
55	{
56		super.Init();
57		for (int i = 0; i < _hashSizeSum; i++)
58			_hash[i] = kEmptyHashValue;
59		_cyclicBufferPos = 0;
60		ReduceOffsets(-1);
61	}
62
63	public void MovePos() throws IOException
64	{
65		if (++_cyclicBufferPos >= _cyclicBufferSize)
66			_cyclicBufferPos = 0;
67		super.MovePos();
68		if (_pos == kMaxValForNormalize)
69			Normalize();
70	}
71
72
73
74
75
76
77
78
79	public boolean Create(int historySize, int keepAddBufferBefore,
80			int matchMaxLen, int keepAddBufferAfter)
81	{
82		if (historySize > kMaxValForNormalize - 256)
83			return false;
84		_cutValue = 16 + (matchMaxLen >> 1);
85
86		int windowReservSize = (historySize + keepAddBufferBefore +
87				matchMaxLen + keepAddBufferAfter) / 2 + 256;
88
89		super.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize);
90
91		_matchMaxLen = matchMaxLen;
92
93		int cyclicBufferSize = historySize + 1;
94		if (_cyclicBufferSize != cyclicBufferSize)
95			_son = new int[(_cyclicBufferSize = cyclicBufferSize) * 2];
96
97		int 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 int [_hashSizeSum = hs];
116		return true;
117	}
118	public int GetMatches(int[] distances) throws IOException
119	{
120		int 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		int offset = 0;
134		int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
135		int cur = _bufferOffset + _pos;
136		int maxLen = kStartMaxLen; // to avoid items for len < hashSize;
137		int hashValue, hash2Value = 0, hash3Value = 0;
138
139		if (HASH_ARRAY)
140		{
141			int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF);
142			hash2Value = temp & (kHash2Size - 1);
143			temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8);
144			hash3Value = temp & (kHash3Size - 1);
145			hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask;
146		}
147		else
148			hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8));
149
150		int curMatch = _hash[kFixHashSize + hashValue];
151		if (HASH_ARRAY)
152		{
153			int curMatch2 = _hash[hash2Value];
154			int 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		int ptr0 = (_cyclicBufferPos << 1) + 1;
182		int ptr1 = (_cyclicBufferPos << 1);
183
184		int 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		int count = _cutValue;
201
202		while (true)
203		{
204			if (curMatch <= matchMinPos || count-- == 0)
205			{
206				_son[ptr0] = _son[ptr1] = kEmptyHashValue;
207				break;
208			}
209			int delta = _pos - curMatch;
210			int cyclicPos = ((delta <= _cyclicBufferPos) ?
211				(_cyclicBufferPos - delta) :
212				(_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
213
214			int pby1 = _bufferOffset + curMatch;
215			int 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] & 0xFF) < (_bufferBase[cur + len] & 0xFF))
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(int num) throws IOException
253	{
254		do
255		{
256			int 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			int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
270			int cur = _bufferOffset + _pos;
271
272			int hashValue;
273
274			if (HASH_ARRAY)
275			{
276				int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF);
277				int hash2Value = temp & (kHash2Size - 1);
278				_hash[hash2Value] = _pos;
279				temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8);
280				int hash3Value = temp & (kHash3Size - 1);
281				_hash[kHash3Offset + hash3Value] = _pos;
282				hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask;
283			}
284			else
285				hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8));
286
287			int curMatch = _hash[kFixHashSize + hashValue];
288			_hash[kFixHashSize + hashValue] = _pos;
289
290			int ptr0 = (_cyclicBufferPos << 1) + 1;
291			int ptr1 = (_cyclicBufferPos << 1);
292
293			int len0, len1;
294			len0 = len1 = kNumHashDirectBytes;
295
296			int count = _cutValue;
297			while (true)
298			{
299				if (curMatch <= matchMinPos || count-- == 0)
300				{
301					_son[ptr0] = _son[ptr1] = kEmptyHashValue;
302					break;
303				}
304
305				int delta = _pos - curMatch;
306				int cyclicPos = ((delta <= _cyclicBufferPos) ?
307					(_cyclicBufferPos - delta) :
308					(_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
309
310				int pby1 = _bufferOffset + curMatch;
311				int 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] & 0xFF) < (_bufferBase[cur + len] & 0xFF))
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(int[] items, int numItems, int subValue)
345	{
346		for (int i = 0; i < numItems; i++)
347		{
348			int 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		int subValue = _pos - _cyclicBufferSize;
360		NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
361		NormalizeLinks(_hash, _hashSizeSum, subValue);
362		ReduceOffsets(subValue);
363	}
364
365	public void SetCutValue(int cutValue) { _cutValue = cutValue; }
366
367	private static final int[] CrcTable = new int[256];
368
369	static
370	{
371		for (int i = 0; i < 256; i++)
372		{
373			int r = i;
374			for (int j = 0; j < 8; j++)
375				if ((r & 1) != 0)
376					r = (r >>> 1) ^ 0xEDB88320;
377				else
378					r >>>= 1;
379			CrcTable[i] = r;
380		}
381	}
382}
383