1 // LzBinTree.cs
2 
3 using System;
4 
5 namespace 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 
SetType(int numHashBytes)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 
SetStream(System.IO.Stream stream)51 		public new void SetStream(System.IO.Stream stream) { base.SetStream(stream); }
ReleaseStream()52 		public new void ReleaseStream() { base.ReleaseStream(); }
53 
Init()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 
MovePos()63 		public new void MovePos()
64 		{
65 			if (++_cyclicBufferPos >= _cyclicBufferSize)
66 				_cyclicBufferPos = 0;
67 			base.MovePos();
68 			if (_pos == kMaxValForNormalize)
69 				Normalize();
70 		}
71 
GetIndexByte(Int32 index)72 		public new Byte GetIndexByte(Int32 index) { return base.GetIndexByte(index); }
73 
GetMatchLen(Int32 index, UInt32 distance, UInt32 limit)74 		public new UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit)
75 		{ return base.GetMatchLen(index, distance, limit); }
76 
GetNumAvailableBytes()77 		public new UInt32 GetNumAvailableBytes() { return base.GetNumAvailableBytes(); }
78 
Create(UInt32 historySize, UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter)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 
GetMatches(UInt32[] distances)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 
Skip(UInt32 num)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 
NormalizeLinks(UInt32[] items, UInt32 numItems, UInt32 subValue)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 
Normalize()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 
SetCutValue(UInt32 cutValue)365 		public void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; }
366 	}
367 }
368