1 | // LZ.BinTree
|
---|
2 |
|
---|
3 | package SevenZip.Compression.LZ;
|
---|
4 | import java.io.IOException;
|
---|
5 |
|
---|
6 |
|
---|
7 | public 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 | }
|
---|