001: // LZ.BinTree
002:
003: package SevenZip.Compression.lz;
004:
005: import java.io.IOException;
006:
007: public class BinTree extends InWindow {
008: int _cyclicBufferPos;
009: int _cyclicBufferSize = 0;
010: int _matchMaxLen;
011:
012: int[] _son;
013: int[] _hash;
014:
015: int _cutValue = 0xFF;
016: int _hashMask;
017: int _hashSizeSum = 0;
018:
019: boolean HASH_ARRAY = true;
020:
021: static final int kHash2Size = 1 << 10;
022: static final int kHash3Size = 1 << 16;
023: static final int kBT2HashSize = 1 << 16;
024: static final int kStartMaxLen = 1;
025: static final int kHash3Offset = kHash2Size;
026: static final int kEmptyHashValue = 0;
027: static final int kMaxValForNormalize = (1 << 30) - 1;
028:
029: int kNumHashDirectBytes = 0;
030: int kMinMatchCheck = 4;
031: int kFixHashSize = kHash2Size + kHash3Size;
032:
033: public void SetType(int numHashBytes) {
034: HASH_ARRAY = (numHashBytes > 2);
035: if (HASH_ARRAY) {
036: kNumHashDirectBytes = 0;
037: kMinMatchCheck = 4;
038: kFixHashSize = kHash2Size + kHash3Size;
039: } else {
040: kNumHashDirectBytes = 2;
041: kMinMatchCheck = 2 + 1;
042: kFixHashSize = 0;
043: }
044: }
045:
046: public void Init() throws IOException {
047: super .Init();
048: for (int i = 0; i < _hashSizeSum; i++)
049: _hash[i] = kEmptyHashValue;
050: _cyclicBufferPos = 0;
051: ReduceOffsets(-1);
052: }
053:
054: public void MovePos() throws IOException {
055: if (++_cyclicBufferPos >= _cyclicBufferSize)
056: _cyclicBufferPos = 0;
057: super .MovePos();
058: if (_pos == kMaxValForNormalize)
059: Normalize();
060: }
061:
062: public boolean Create(int historySize, int keepAddBufferBefore,
063: int matchMaxLen, int keepAddBufferAfter) {
064: if (historySize > kMaxValForNormalize - 256)
065: return false;
066: _cutValue = 16 + (matchMaxLen >> 1);
067:
068: int windowReservSize = (historySize + keepAddBufferBefore
069: + matchMaxLen + keepAddBufferAfter) / 2 + 256;
070:
071: super .Create(historySize + keepAddBufferBefore, matchMaxLen
072: + keepAddBufferAfter, windowReservSize);
073:
074: _matchMaxLen = matchMaxLen;
075:
076: int cyclicBufferSize = historySize + 1;
077: if (_cyclicBufferSize != cyclicBufferSize)
078: _son = new int[(_cyclicBufferSize = cyclicBufferSize) * 2];
079:
080: int hs = kBT2HashSize;
081:
082: if (HASH_ARRAY) {
083: hs = historySize - 1;
084: hs |= (hs >> 1);
085: hs |= (hs >> 2);
086: hs |= (hs >> 4);
087: hs |= (hs >> 8);
088: hs >>= 1;
089: hs |= 0xFFFF;
090: if (hs > (1 << 24))
091: hs >>= 1;
092: _hashMask = hs;
093: hs++;
094: hs += kFixHashSize;
095: }
096: if (hs != _hashSizeSum)
097: _hash = new int[_hashSizeSum = hs];
098: return true;
099: }
100:
101: public int GetMatches(int[] distances) throws IOException {
102: int lenLimit;
103: if (_pos + _matchMaxLen <= _streamPos)
104: lenLimit = _matchMaxLen;
105: else {
106: lenLimit = _streamPos - _pos;
107: if (lenLimit < kMinMatchCheck) {
108: MovePos();
109: return 0;
110: }
111: }
112:
113: int offset = 0;
114: int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize)
115: : 0;
116: int cur = _bufferOffset + _pos;
117: int maxLen = kStartMaxLen; // to avoid items for len < hashSize;
118: int hashValue, hash2Value = 0, hash3Value = 0;
119:
120: if (HASH_ARRAY) {
121: int temp = CrcTable[_bufferBase[cur] & 0xFF]
122: ^ (_bufferBase[cur + 1] & 0xFF);
123: hash2Value = temp & (kHash2Size - 1);
124: temp ^= ((_bufferBase[cur + 2] & 0xFF) << 8);
125: hash3Value = temp & (kHash3Size - 1);
126: hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5))
127: & _hashMask;
128: } else
129: hashValue = ((_bufferBase[cur] & 0xFF) ^ ((_bufferBase[cur + 1] & 0xFF) << 8));
130:
131: int curMatch = _hash[kFixHashSize + hashValue];
132: if (HASH_ARRAY) {
133: int curMatch2 = _hash[hash2Value];
134: int curMatch3 = _hash[kHash3Offset + hash3Value];
135: _hash[hash2Value] = _pos;
136: _hash[kHash3Offset + hash3Value] = _pos;
137: if (curMatch2 > matchMinPos)
138: if (_bufferBase[_bufferOffset + curMatch2] == _bufferBase[cur]) {
139: distances[offset++] = maxLen = 2;
140: distances[offset++] = _pos - curMatch2 - 1;
141: }
142: if (curMatch3 > matchMinPos)
143: if (_bufferBase[_bufferOffset + curMatch3] == _bufferBase[cur]) {
144: if (curMatch3 == curMatch2)
145: offset -= 2;
146: distances[offset++] = maxLen = 3;
147: distances[offset++] = _pos - curMatch3 - 1;
148: curMatch2 = curMatch3;
149: }
150: if (offset != 0 && curMatch2 == curMatch) {
151: offset -= 2;
152: maxLen = kStartMaxLen;
153: }
154: }
155:
156: _hash[kFixHashSize + hashValue] = _pos;
157:
158: int ptr0 = (_cyclicBufferPos << 1) + 1;
159: int ptr1 = (_cyclicBufferPos << 1);
160:
161: int len0, len1;
162: len0 = len1 = kNumHashDirectBytes;
163:
164: if (kNumHashDirectBytes != 0) {
165: if (curMatch > matchMinPos) {
166: if (_bufferBase[_bufferOffset + curMatch
167: + kNumHashDirectBytes] != _bufferBase[cur
168: + kNumHashDirectBytes]) {
169: distances[offset++] = maxLen = kNumHashDirectBytes;
170: distances[offset++] = _pos - curMatch - 1;
171: }
172: }
173: }
174:
175: int count = _cutValue;
176:
177: while (true) {
178: if (curMatch <= matchMinPos || count-- == 0) {
179: _son[ptr0] = _son[ptr1] = kEmptyHashValue;
180: break;
181: }
182: int delta = _pos - curMatch;
183: int cyclicPos = ((delta <= _cyclicBufferPos) ? (_cyclicBufferPos - delta)
184: : (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
185:
186: int pby1 = _bufferOffset + curMatch;
187: int len = Math.min(len0, len1);
188: if (_bufferBase[pby1 + len] == _bufferBase[cur + len]) {
189: while (++len != lenLimit)
190: if (_bufferBase[pby1 + len] != _bufferBase[cur
191: + len])
192: break;
193: if (maxLen < len) {
194: distances[offset++] = maxLen = len;
195: distances[offset++] = delta - 1;
196: if (len == lenLimit) {
197: _son[ptr1] = _son[cyclicPos];
198: _son[ptr0] = _son[cyclicPos + 1];
199: break;
200: }
201: }
202: }
203: if ((_bufferBase[pby1 + len] & 0xFF) < (_bufferBase[cur
204: + len] & 0xFF)) {
205: _son[ptr1] = curMatch;
206: ptr1 = cyclicPos + 1;
207: curMatch = _son[ptr1];
208: len1 = len;
209: } else {
210: _son[ptr0] = curMatch;
211: ptr0 = cyclicPos;
212: curMatch = _son[ptr0];
213: len0 = len;
214: }
215: }
216: MovePos();
217: return offset;
218: }
219:
220: public void Skip(int num) throws IOException {
221: do {
222: int lenLimit;
223: if (_pos + _matchMaxLen <= _streamPos)
224: lenLimit = _matchMaxLen;
225: else {
226: lenLimit = _streamPos - _pos;
227: if (lenLimit < kMinMatchCheck) {
228: MovePos();
229: continue;
230: }
231: }
232:
233: int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize)
234: : 0;
235: int cur = _bufferOffset + _pos;
236:
237: int hashValue;
238:
239: if (HASH_ARRAY) {
240: int temp = CrcTable[_bufferBase[cur] & 0xFF]
241: ^ (_bufferBase[cur + 1] & 0xFF);
242: int hash2Value = temp & (kHash2Size - 1);
243: _hash[hash2Value] = _pos;
244: temp ^= ((_bufferBase[cur + 2] & 0xFF) << 8);
245: int hash3Value = temp & (kHash3Size - 1);
246: _hash[kHash3Offset + hash3Value] = _pos;
247: hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5))
248: & _hashMask;
249: } else
250: hashValue = ((_bufferBase[cur] & 0xFF) ^ ((_bufferBase[cur + 1] & 0xFF) << 8));
251:
252: int curMatch = _hash[kFixHashSize + hashValue];
253: _hash[kFixHashSize + hashValue] = _pos;
254:
255: int ptr0 = (_cyclicBufferPos << 1) + 1;
256: int ptr1 = (_cyclicBufferPos << 1);
257:
258: int len0, len1;
259: len0 = len1 = kNumHashDirectBytes;
260:
261: int count = _cutValue;
262: while (true) {
263: if (curMatch <= matchMinPos || count-- == 0) {
264: _son[ptr0] = _son[ptr1] = kEmptyHashValue;
265: break;
266: }
267:
268: int delta = _pos - curMatch;
269: int cyclicPos = ((delta <= _cyclicBufferPos) ? (_cyclicBufferPos - delta)
270: : (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
271:
272: int pby1 = _bufferOffset + curMatch;
273: int len = Math.min(len0, len1);
274: if (_bufferBase[pby1 + len] == _bufferBase[cur + len]) {
275: while (++len != lenLimit)
276: if (_bufferBase[pby1 + len] != _bufferBase[cur
277: + len])
278: break;
279: if (len == lenLimit) {
280: _son[ptr1] = _son[cyclicPos];
281: _son[ptr0] = _son[cyclicPos + 1];
282: break;
283: }
284: }
285: if ((_bufferBase[pby1 + len] & 0xFF) < (_bufferBase[cur
286: + len] & 0xFF)) {
287: _son[ptr1] = curMatch;
288: ptr1 = cyclicPos + 1;
289: curMatch = _son[ptr1];
290: len1 = len;
291: } else {
292: _son[ptr0] = curMatch;
293: ptr0 = cyclicPos;
294: curMatch = _son[ptr0];
295: len0 = len;
296: }
297: }
298: MovePos();
299: } while (--num != 0);
300: }
301:
302: void NormalizeLinks(int[] items, int numItems, int subValue) {
303: for (int i = 0; i < numItems; i++) {
304: int value = items[i];
305: if (value <= subValue)
306: value = kEmptyHashValue;
307: else
308: value -= subValue;
309: items[i] = value;
310: }
311: }
312:
313: void Normalize() {
314: int subValue = _pos - _cyclicBufferSize;
315: NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
316: NormalizeLinks(_hash, _hashSizeSum, subValue);
317: ReduceOffsets(subValue);
318: }
319:
320: public void SetCutValue(int cutValue) {
321: _cutValue = cutValue;
322: }
323:
324: private static final int[] CrcTable = new int[256];
325:
326: static {
327: for (int i = 0; i < 256; i++) {
328: int r = i;
329: for (int j = 0; j < 8; j++)
330: if ((r & 1) != 0)
331: r = (r >>> 1) ^ 0xEDB88320;
332: else
333: r >>>= 1;
334: CrcTable[i] = r;
335: }
336: }
337: }
|