| // LZ.BinTree | |
| package SevenZip.Compression.LZ; | |
| import java.io.IOException; | |
| public class BinTree extends InWindow | |
| { | |
| int _cyclicBufferPos; | |
| int _cyclicBufferSize = 0; | |
| int _matchMaxLen; | |
| int[] _son; | |
| int[] _hash; | |
| int _cutValue = 0xFF; | |
| int _hashMask; | |
| int _hashSizeSum = 0; | |
| boolean HASH_ARRAY = true; | |
| static final int kHash2Size = 1 << 10; | |
| static final int kHash3Size = 1 << 16; | |
| static final int kBT2HashSize = 1 << 16; | |
| static final int kStartMaxLen = 1; | |
| static final int kHash3Offset = kHash2Size; | |
| static final int kEmptyHashValue = 0; | |
| static final int kMaxValForNormalize = (1 << 30) - 1; | |
| int kNumHashDirectBytes = 0; | |
| int kMinMatchCheck = 4; | |
| int kFixHashSize = kHash2Size + kHash3Size; | |
| public void SetType(int numHashBytes) | |
| { | |
| HASH_ARRAY = (numHashBytes > 2); | |
| if (HASH_ARRAY) | |
| { | |
| kNumHashDirectBytes = 0; | |
| kMinMatchCheck = 4; | |
| kFixHashSize = kHash2Size + kHash3Size; | |
| } | |
| else | |
| { | |
| kNumHashDirectBytes = 2; | |
| kMinMatchCheck = 2 + 1; | |
| kFixHashSize = 0; | |
| } | |
| } | |
| public void Init() throws IOException | |
| { | |
| super.Init(); | |
| for (int i = 0; i < _hashSizeSum; i++) | |
| _hash[i] = kEmptyHashValue; | |
| _cyclicBufferPos = 0; | |
| ReduceOffsets(-1); | |
| } | |
| public void MovePos() throws IOException | |
| { | |
| if (++_cyclicBufferPos >= _cyclicBufferSize) | |
| _cyclicBufferPos = 0; | |
| super.MovePos(); | |
| if (_pos == kMaxValForNormalize) | |
| Normalize(); | |
| } | |
| public boolean Create(int historySize, int keepAddBufferBefore, | |
| int matchMaxLen, int keepAddBufferAfter) | |
| { | |
| if (historySize > kMaxValForNormalize - 256) | |
| return false; | |
| _cutValue = 16 + (matchMaxLen >> 1); | |
| int windowReservSize = (historySize + keepAddBufferBefore + | |
| matchMaxLen + keepAddBufferAfter) / 2 + 256; | |
| super.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize); | |
| _matchMaxLen = matchMaxLen; | |
| int cyclicBufferSize = historySize + 1; | |
| if (_cyclicBufferSize != cyclicBufferSize) | |
| _son = new int[(_cyclicBufferSize = cyclicBufferSize) * 2]; | |
| int hs = kBT2HashSize; | |
| if (HASH_ARRAY) | |
| { | |
| hs = historySize - 1; | |
| hs |= (hs >> 1); | |
| hs |= (hs >> 2); | |
| hs |= (hs >> 4); | |
| hs |= (hs >> 8); | |
| hs >>= 1; | |
| hs |= 0xFFFF; | |
| if (hs > (1 << 24)) | |
| hs >>= 1; | |
| _hashMask = hs; | |
| hs++; | |
| hs += kFixHashSize; | |
| } | |
| if (hs != _hashSizeSum) | |
| _hash = new int [_hashSizeSum = hs]; | |
| return true; | |
| } | |
| public int GetMatches(int[] distances) throws IOException | |
| { | |
| int lenLimit; | |
| if (_pos + _matchMaxLen <= _streamPos) | |
| lenLimit = _matchMaxLen; | |
| else | |
| { | |
| lenLimit = _streamPos - _pos; | |
| if (lenLimit < kMinMatchCheck) | |
| { | |
| MovePos(); | |
| return 0; | |
| } | |
| } | |
| int offset = 0; | |
| int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; | |
| int cur = _bufferOffset + _pos; | |
| int maxLen = kStartMaxLen; // to avoid items for len < hashSize; | |
| int hashValue, hash2Value = 0, hash3Value = 0; | |
| if (HASH_ARRAY) | |
| { | |
| int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF); | |
| hash2Value = temp & (kHash2Size - 1); | |
| temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8); | |
| hash3Value = temp & (kHash3Size - 1); | |
| hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask; | |
| } | |
| else | |
| hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8)); | |
| int curMatch = _hash[kFixHashSize + hashValue]; | |
| if (HASH_ARRAY) | |
| { | |
| int curMatch2 = _hash[hash2Value]; | |
| int curMatch3 = _hash[kHash3Offset + hash3Value]; | |
| _hash[hash2Value] = _pos; | |
| _hash[kHash3Offset + hash3Value] = _pos; | |
| if (curMatch2 > matchMinPos) | |
| if (_bufferBase[_bufferOffset + curMatch2] == _bufferBase[cur]) | |
| { | |
| distances[offset++] = maxLen = 2; | |
| distances[offset++] = _pos - curMatch2 - 1; | |
| } | |
| if (curMatch3 > matchMinPos) | |
| if (_bufferBase[_bufferOffset + curMatch3] == _bufferBase[cur]) | |
| { | |
| if (curMatch3 == curMatch2) | |
| offset -= 2; | |
| distances[offset++] = maxLen = 3; | |
| distances[offset++] = _pos - curMatch3 - 1; | |
| curMatch2 = curMatch3; | |
| } | |
| if (offset != 0 && curMatch2 == curMatch) | |
| { | |
| offset -= 2; | |
| maxLen = kStartMaxLen; | |
| } | |
| } | |
| _hash[kFixHashSize + hashValue] = _pos; | |
| int ptr0 = (_cyclicBufferPos << 1) + 1; | |
| int ptr1 = (_cyclicBufferPos << 1); | |
| int len0, len1; | |
| len0 = len1 = kNumHashDirectBytes; | |
| if (kNumHashDirectBytes != 0) | |
| { | |
| if (curMatch > matchMinPos) | |
| { | |
| if (_bufferBase[_bufferOffset + curMatch + kNumHashDirectBytes] != | |
| _bufferBase[cur + kNumHashDirectBytes]) | |
| { | |
| distances[offset++] = maxLen = kNumHashDirectBytes; | |
| distances[offset++] = _pos - curMatch - 1; | |
| } | |
| } | |
| } | |
| int count = _cutValue; | |
| while (true) | |
| { | |
| if (curMatch <= matchMinPos || count-- == 0) | |
| { | |
| _son[ptr0] = _son[ptr1] = kEmptyHashValue; | |
| break; | |
| } | |
| int delta = _pos - curMatch; | |
| int cyclicPos = ((delta <= _cyclicBufferPos) ? | |
| (_cyclicBufferPos - delta) : | |
| (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1; | |
| int pby1 = _bufferOffset + curMatch; | |
| int len = Math.min(len0, len1); | |
| if (_bufferBase[pby1 + len] == _bufferBase[cur + len]) | |
| { | |
| while(++len != lenLimit) | |
| if (_bufferBase[pby1 + len] != _bufferBase[cur + len]) | |
| break; | |
| if (maxLen < len) | |
| { | |
| distances[offset++] = maxLen = len; | |
| distances[offset++] = delta - 1; | |
| if (len == lenLimit) | |
| { | |
| _son[ptr1] = _son[cyclicPos]; | |
| _son[ptr0] = _son[cyclicPos + 1]; | |
| break; | |
| } | |
| } | |
| } | |
| if ((_bufferBase[pby1 + len] & 0xFF) < (_bufferBase[cur + len] & 0xFF)) | |
| { | |
| _son[ptr1] = curMatch; | |
| ptr1 = cyclicPos + 1; | |
| curMatch = _son[ptr1]; | |
| len1 = len; | |
| } | |
| else | |
| { | |
| _son[ptr0] = curMatch; | |
| ptr0 = cyclicPos; | |
| curMatch = _son[ptr0]; | |
| len0 = len; | |
| } | |
| } | |
| MovePos(); | |
| return offset; | |
| } | |
| public void Skip(int num) throws IOException | |
| { | |
| do | |
| { | |
| int lenLimit; | |
| if (_pos + _matchMaxLen <= _streamPos) | |
| lenLimit = _matchMaxLen; | |
| else | |
| { | |
| lenLimit = _streamPos - _pos; | |
| if (lenLimit < kMinMatchCheck) | |
| { | |
| MovePos(); | |
| continue; | |
| } | |
| } | |
| int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; | |
| int cur = _bufferOffset + _pos; | |
| int hashValue; | |
| if (HASH_ARRAY) | |
| { | |
| int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF); | |
| int hash2Value = temp & (kHash2Size - 1); | |
| _hash[hash2Value] = _pos; | |
| temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8); | |
| int hash3Value = temp & (kHash3Size - 1); | |
| _hash[kHash3Offset + hash3Value] = _pos; | |
| hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask; | |
| } | |
| else | |
| hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8)); | |
| int curMatch = _hash[kFixHashSize + hashValue]; | |
| _hash[kFixHashSize + hashValue] = _pos; | |
| int ptr0 = (_cyclicBufferPos << 1) + 1; | |
| int ptr1 = (_cyclicBufferPos << 1); | |
| int len0, len1; | |
| len0 = len1 = kNumHashDirectBytes; | |
| int count = _cutValue; | |
| while (true) | |
| { | |
| if (curMatch <= matchMinPos || count-- == 0) | |
| { | |
| _son[ptr0] = _son[ptr1] = kEmptyHashValue; | |
| break; | |
| } | |
| int delta = _pos - curMatch; | |
| int cyclicPos = ((delta <= _cyclicBufferPos) ? | |
| (_cyclicBufferPos - delta) : | |
| (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1; | |
| int pby1 = _bufferOffset + curMatch; | |
| int len = Math.min(len0, len1); | |
| if (_bufferBase[pby1 + len] == _bufferBase[cur + len]) | |
| { | |
| while (++len != lenLimit) | |
| if (_bufferBase[pby1 + len] != _bufferBase[cur + len]) | |
| break; | |
| if (len == lenLimit) | |
| { | |
| _son[ptr1] = _son[cyclicPos]; | |
| _son[ptr0] = _son[cyclicPos + 1]; | |
| break; | |
| } | |
| } | |
| if ((_bufferBase[pby1 + len] & 0xFF) < (_bufferBase[cur + len] & 0xFF)) | |
| { | |
| _son[ptr1] = curMatch; | |
| ptr1 = cyclicPos + 1; | |
| curMatch = _son[ptr1]; | |
| len1 = len; | |
| } | |
| else | |
| { | |
| _son[ptr0] = curMatch; | |
| ptr0 = cyclicPos; | |
| curMatch = _son[ptr0]; | |
| len0 = len; | |
| } | |
| } | |
| MovePos(); | |
| } | |
| while (--num != 0); | |
| } | |
| void NormalizeLinks(int[] items, int numItems, int subValue) | |
| { | |
| for (int i = 0; i < numItems; i++) | |
| { | |
| int value = items[i]; | |
| if (value <= subValue) | |
| value = kEmptyHashValue; | |
| else | |
| value -= subValue; | |
| items[i] = value; | |
| } | |
| } | |
| void Normalize() | |
| { | |
| int subValue = _pos - _cyclicBufferSize; | |
| NormalizeLinks(_son, _cyclicBufferSize * 2, subValue); | |
| NormalizeLinks(_hash, _hashSizeSum, subValue); | |
| ReduceOffsets(subValue); | |
| } | |
| public void SetCutValue(int cutValue) { _cutValue = cutValue; } | |
| private static final int[] CrcTable = new int[256]; | |
| static | |
| { | |
| for (int i = 0; i < 256; i++) | |
| { | |
| int r = i; | |
| for (int j = 0; j < 8; j++) | |
| if ((r & 1) != 0) | |
| r = (r >>> 1) ^ 0xEDB88320; | |
| else | |
| r >>>= 1; | |
| CrcTable[i] = r; | |
| } | |
| } | |
| } |