?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
allow coexistance of N build and AC build.
[tomato.git] / release / src-rt-6.x / linux / linux-2.6 / scripts / squashfs / lzma / CS / 7zip / Compress / LZ / LzBinTree.cs
blob5151a505177dd6d01c4a77c9ce8d46fd6a663958
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;
11 UInt32 _historySize;
12 UInt32 _matchMaxLen;
13
14 // UInt32 []_dummy;
15 UInt32[] _son;
16
17 UInt32[] _hash;
18 UInt32[] _hash2;
19 UInt32[] _hash3;
20
21 UInt32 _cutValue = 0xFF;
22
23 bool HASH_ARRAY = true;
24 bool HASH_BIG = false;
25
26 const UInt32 kHash3Size = 1 << 18;
27
28 const UInt32 kBT2HashSize = 1 << 16;
29 const UInt32 kBT4Hash2Size = 1 << 10;
30 const UInt32 kBT4Hash4Size = 1 << 20;
31 const UInt32 kBT4bHash4Size = 1 << 23;
32 const UInt32 kBT2NumHashDirectBytes = 2;
33 const UInt32 kBT4NumHashDirectBytes = 0;
34
35 UInt32 kHash2Size = kBT4Hash2Size;
36 UInt32 kNumHashDirectBytes = kBT4NumHashDirectBytes;
37 UInt32 kNumHashBytes = 4;
38 UInt32 kHashSize = kBT4Hash4Size;
39
40 public void SetType(int numHashBytes, bool big)
41 {
42 HASH_ARRAY = numHashBytes > 2;
43 HASH_BIG = big;
44 if (HASH_ARRAY)
45 {
46 kHash2Size = kBT4Hash2Size;
47 kNumHashDirectBytes = kBT4NumHashDirectBytes;
48 kNumHashBytes = 4;
49 kHashSize = HASH_BIG ? kBT4bHash4Size : kBT4Hash4Size;
50 }
51 else
52 {
53 kNumHashDirectBytes = kBT2NumHashDirectBytes;
54 kNumHashBytes = 2;
55 kHashSize = kBT2HashSize;
56 }
57 }
58
59 const UInt32 kEmptyHashValue = 0;
60
61 const UInt32 kMaxValForNormalize = ((UInt32)1 << 31) - 1;
62
63 UInt32 Hash(UInt32 offset, out UInt32 hash2Value, out UInt32 hash3Value)
64 {
65 UInt32 temp = CRC.Table[_bufferBase[offset]] ^ _bufferBase[offset + 1];
66 hash2Value = temp & (kHash2Size - 1);
67 temp ^= ((UInt32)(_bufferBase[offset + 2]) << 8);
68 hash3Value = temp & (kHash3Size - 1);
69 return (temp ^ (CRC.Table[_bufferBase[offset + 3]] << 5)) & (kHashSize - 1);
70 }
71
72 UInt32 Hash(UInt32 offset)
73 {
74 return _bufferBase[offset] ^ ((UInt32)(_bufferBase[offset + 1]) << 8);
75 }
76
77 public new void Init(System.IO.Stream inStream)
78 {
79 base.Init(inStream);
80 UInt32 i;
81 for (i = 0; i < kHashSize; i++)
82 _hash[i] = kEmptyHashValue;
83 if (HASH_ARRAY)
84 {
85 for (i = 0; i < kHash2Size; i++)
86 _hash2[i] = kEmptyHashValue;
87 for (i = 0; i < kHash3Size; i++)
88 _hash3[i] = kEmptyHashValue;
89 }
90 _cyclicBufferPos = 0;
91 ReduceOffsets(-1);
92 }
93
94 public new void ReleaseStream() { base.ReleaseStream(); }
95
96 public new void MovePos()
97 {
98 _cyclicBufferPos++;
99 if (_cyclicBufferPos >= _cyclicBufferSize)
100 _cyclicBufferPos = 0;
101 base.MovePos();
102 if (_pos == kMaxValForNormalize)
103 Normalize();
104 }
105
106 public new Byte GetIndexByte(Int32 index) { return base.GetIndexByte(index); }
107
108 public new UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit)
109 { return base.GetMatchLen(index, distance, limit); }
110
111 public new UInt32 GetNumAvailableBytes() { return base.GetNumAvailableBytes(); }
112
113 public void Create(UInt32 historySize, UInt32 keepAddBufferBefore,
114 UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
115 {
116 // _dummy = new UInt32[matchMaxLen + 1];
117 UInt32 windowReservSize = (historySize + keepAddBufferBefore +
118 matchMaxLen + keepAddBufferAfter) / 2 + 256;
119
120 _son = null;
121 _hash = null;
122 _hash2 = null;
123 _hash3 = null;
124
125 base.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize);
126
127 if (_blockSize + 256 > kMaxValForNormalize)
128 throw new Exception();
129
130 _historySize = historySize;
131 _matchMaxLen = matchMaxLen;
132
133 _cyclicBufferSize = historySize + 1;
134 _son = new UInt32[_cyclicBufferSize * 2];
135
136 _hash = new UInt32[kHashSize];
137 if (HASH_ARRAY)
138 {
139 _hash2 = new UInt32[kHash2Size];
140 _hash3 = new UInt32[kHash3Size];
141 }
142 }
143
144 public UInt32 GetLongestMatch(UInt32[] distances)
145 {
146 UInt32 lenLimit;
147 if (_pos + _matchMaxLen <= _streamPos)
148 lenLimit = _matchMaxLen;
149 else
150 {
151 lenLimit = _streamPos - _pos;
152 if (lenLimit < kNumHashBytes)
153 return 0;
154 }
155
156 UInt32 matchMinPos = (_pos > _historySize) ? (_pos - _historySize) : 1;
157
158 UInt32 cur = _bufferOffset + _pos;
159
160 UInt32 matchHashLenMax = 0;
161
162 UInt32 hashValue, hash2Value = 0, hash3Value = 0;
163
164 if (HASH_ARRAY)
165 hashValue = Hash(cur, out hash2Value, out hash3Value);
166 else
167 hashValue = Hash(cur);
168
169 UInt32 curMatch = _hash[hashValue];
170 UInt32 curMatch2 = 0, curMatch3 = 0;
171 UInt32 len2Distance = 0;
172 UInt32 len3Distance = 0;
173 bool matchLen2Exist = false;
174 bool matchLen3Exist = false;
175 if (HASH_ARRAY)
176 {
177 curMatch2 = _hash2[hash2Value];
178 curMatch3 = _hash3[hash3Value];
179 _hash2[hash2Value] = _pos;
180 if (curMatch2 >= matchMinPos)
181 {
182 if (_bufferBase[_bufferOffset + curMatch2] == _bufferBase[cur])
183 {
184 len2Distance = _pos - curMatch2 - 1;
185 matchHashLenMax = 2;
186 matchLen2Exist = true;
187 }
188 }
189 {
190 _hash3[hash3Value] = _pos;
191 if (curMatch3 >= matchMinPos)
192 {
193 if (_bufferBase[_bufferOffset + curMatch3] == _bufferBase[cur])
194 {
195 len3Distance = _pos - curMatch3 - 1;
196 matchHashLenMax = 3;
197 matchLen3Exist = true;
198 if (matchLen2Exist)
199 {
200 if (len3Distance < len2Distance)
201 len2Distance = len3Distance;
202 }
203 else
204 {
205 len2Distance = len3Distance;
206 matchLen2Exist = true;
207 }
208 }
209 }
210 }
211 }
212
213 _hash[hashValue] = _pos;
214
215 if (curMatch < matchMinPos)
216 {
217 _son[(_cyclicBufferPos << 1)] = kEmptyHashValue;
218 _son[(_cyclicBufferPos << 1) + 1] = kEmptyHashValue;
219
220 if (HASH_ARRAY)
221 {
222 distances[2] = len2Distance;
223 distances[3] = len3Distance;
224 }
225 return matchHashLenMax;
226 }
227 UInt32 ptrLeft = (_cyclicBufferPos << 1) + 1;
228 UInt32 ptrRight = (_cyclicBufferPos << 1);
229
230 UInt32 maxLen, minLeft, minRight;
231 maxLen = minLeft = minRight = kNumHashDirectBytes;
232
233 distances[maxLen] = _pos - curMatch - 1;
234
235 for (UInt32 count = _cutValue; count > 0; count--)
236 {
237 UInt32 pby1 = _bufferOffset + curMatch;
238 UInt32 currentLen = Math.Min(minLeft, minRight);
239 for (; currentLen < lenLimit; currentLen++)
240 if (_bufferBase[pby1 + currentLen] != _bufferBase[cur + currentLen])
241 break;
242 UInt32 delta = _pos - curMatch;
243 while (currentLen > maxLen)
244 distances[++maxLen] = delta - 1;
245
246 UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ?
247 (_cyclicBufferPos - delta) :
248 (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
249
250 if (currentLen != lenLimit)
251 {
252 if (_bufferBase[pby1 + currentLen] < _bufferBase[cur + currentLen])
253 {
254 _son[ptrRight] = curMatch;
255 ptrRight = cyclicPos + 1;
256 curMatch = _son[ptrRight];
257 if (currentLen > minLeft)
258 minLeft = currentLen;
259 }
260 else
261 {
262 _son[ptrLeft] = curMatch;
263 ptrLeft = cyclicPos;
264 curMatch = _son[ptrLeft];
265 if (currentLen > minRight)
266 minRight = currentLen;
267 }
268 }
269 else
270 {
271 if (currentLen < _matchMaxLen)
272 {
273 _son[ptrLeft] = curMatch;
274 ptrLeft = cyclicPos;
275 curMatch = _son[ptrLeft];
276 if (currentLen > minRight)
277 minRight = currentLen;
278 }
279 else
280 {
281 _son[ptrLeft] = _son[cyclicPos + 1];
282 _son[ptrRight] = _son[cyclicPos];
283
284 if (HASH_ARRAY)
285 {
286 if (matchLen2Exist && len2Distance < distances[2])
287 distances[2] = len2Distance;
288 if (matchLen3Exist && len3Distance < distances[3])
289 distances[3] = len3Distance;
290 }
291 return maxLen;
292 }
293 }
294 if (curMatch < matchMinPos)
295 break;
296 }
297 _son[ptrLeft] = kEmptyHashValue;
298 _son[ptrRight] = kEmptyHashValue;
299
300 if (HASH_ARRAY)
301 {
302 if (matchLen2Exist)
303 {
304 if (maxLen < 2)
305 {
306 distances[2] = len2Distance;
307 maxLen = 2;
308 }
309 else if (len2Distance < distances[2])
310 distances[2] = len2Distance;
311 }
312 {
313 if (matchLen3Exist)
314 {
315 if (maxLen < 3)
316 {
317 distances[3] = len3Distance;
318 maxLen = 3;
319 }
320 else if (len3Distance < distances[3])
321 distances[3] = len3Distance;
322 }
323 }
324 }
325 return maxLen;
326 }
327
328 public void DummyLongestMatch()
329 {
330 // GetLongestMatch(_dummy);
331
332 UInt32 lenLimit;
333 if (_pos + _matchMaxLen <= _streamPos)
334 lenLimit = _matchMaxLen;
335 else
336 {
337 lenLimit = _streamPos - _pos;
338 if (lenLimit < kNumHashBytes)
339 return;
340 }
341
342 UInt32 matchMinPos = (_pos > _historySize) ? (_pos - _historySize) : 1;
343
344 UInt32 cur = _bufferOffset + _pos;
345
346 UInt32 hashValue, hash2Value = 0, hash3Value = 0;
347
348 if (HASH_ARRAY)
349 hashValue = Hash(cur, out hash2Value, out hash3Value);
350 else
351 hashValue = Hash(cur);
352
353 UInt32 curMatch = _hash[hashValue];
354 UInt32 curMatch2 = 0, curMatch3 = 0;
355 if (HASH_ARRAY)
356 {
357 curMatch2 = _hash2[hash2Value];
358 curMatch3 = _hash3[hash3Value];
359 _hash2[hash2Value] = _pos;
360 _hash3[hash3Value] = _pos;
361 }
362 _hash[hashValue] = _pos;
363
364 if (curMatch < matchMinPos)
365 {
366 _son[(_cyclicBufferPos << 1)] = kEmptyHashValue;
367 _son[(_cyclicBufferPos << 1) + 1] = kEmptyHashValue;
368 return;
369 }
370 UInt32 ptrLeft = (_cyclicBufferPos << 1) + 1;
371 UInt32 ptrRight = (_cyclicBufferPos << 1);
372
373 UInt32 minLeft, minRight;
374 minLeft = minRight = kNumHashDirectBytes;
375
376 for (UInt32 count = _cutValue; count > 0; count--)
377 {
378 UInt32 pby1 = _bufferOffset + curMatch;
379 UInt32 currentLen = Math.Min(minLeft, minRight);
380 for (; currentLen < lenLimit; currentLen++)
381 if (_bufferBase[pby1 + currentLen] != _bufferBase[cur + currentLen])
382 break;
383 UInt32 delta = _pos - curMatch;
384
385 UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ?
386 (_cyclicBufferPos - delta) :
387 (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
388
389 if (currentLen != lenLimit)
390 {
391 if (_bufferBase[pby1 + currentLen] < _bufferBase[cur + currentLen])
392 {
393 _son[ptrRight] = curMatch;
394 ptrRight = cyclicPos + 1;
395 curMatch = _son[ptrRight];
396 if (currentLen > minLeft)
397 minLeft = currentLen;
398 }
399 else
400 {
401 _son[ptrLeft] = curMatch;
402 ptrLeft = cyclicPos;
403 curMatch = _son[ptrLeft];
404 if (currentLen > minRight)
405 minRight = currentLen;
406 }
407 }
408 else
409 {
410 if (currentLen < _matchMaxLen)
411 {
412 _son[ptrLeft] = curMatch;
413 ptrLeft = cyclicPos;
414 curMatch = _son[ptrLeft];
415 if (currentLen > minRight)
416 minRight = currentLen;
417 }
418 else
419 {
420 _son[ptrLeft] = _son[cyclicPos + 1];
421 _son[ptrRight] = _son[cyclicPos];
422 return;
423 }
424 }
425 if (curMatch < matchMinPos)
426 break;
427 }
428 _son[ptrLeft] = kEmptyHashValue;
429 _son[ptrRight] = kEmptyHashValue;
430 }
431
432 void NormalizeLinks(UInt32[] items, UInt32 numItems, UInt32 subValue)
433 {
434 for (UInt32 i = 0; i < numItems; i++)
435 {
436 UInt32 value = items[i];
437 if (value <= subValue)
438 value = kEmptyHashValue;
439 else
440 value -= subValue;
441 items[i] = value;
442 }
443 }
444
445 void Normalize()
446 {
447 UInt32 startItem = _pos - _historySize;
448 UInt32 subValue = startItem - 1;
449 NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
450
451 NormalizeLinks(_hash, kHashSize, subValue);
452
453 if (HASH_ARRAY)
454 {
455 NormalizeLinks(_hash2, kHash2Size, subValue);
456 NormalizeLinks(_hash3, kHash3Size, subValue);
457 }
458 ReduceOffsets((Int32)subValue);
459 }
460
461 public void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; }
462 }
463 }
Tomato firmware and modifications.