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 |
|
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 } |
|