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