Index: third_party/lzma/v4_65/files/Java/SevenZip/Compression/LZ/BinTree.java |
diff --git a/third_party/lzma/v4_65/files/Java/SevenZip/Compression/LZ/BinTree.java b/third_party/lzma/v4_65/files/Java/SevenZip/Compression/LZ/BinTree.java |
deleted file mode 100644 |
index e2074e9a8a90f17bf494ab6c94114c775f7a3429..0000000000000000000000000000000000000000 |
--- a/third_party/lzma/v4_65/files/Java/SevenZip/Compression/LZ/BinTree.java |
+++ /dev/null |
@@ -1,382 +0,0 @@ |
-// 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; |
- } |
- } |
-} |