Index: third_party/lzma/v4_65/files/CS/7zip/Compress/LZ/LzBinTree.cs |
diff --git a/third_party/lzma/v4_65/files/CS/7zip/Compress/LZ/LzBinTree.cs b/third_party/lzma/v4_65/files/CS/7zip/Compress/LZ/LzBinTree.cs |
deleted file mode 100644 |
index c1c006b63a9d825d6313e399dcfd6b87c8dfe938..0000000000000000000000000000000000000000 |
--- a/third_party/lzma/v4_65/files/CS/7zip/Compress/LZ/LzBinTree.cs |
+++ /dev/null |
@@ -1,367 +0,0 @@ |
-// LzBinTree.cs |
- |
-using System; |
- |
-namespace SevenZip.Compression.LZ |
-{ |
- public class BinTree : InWindow, IMatchFinder |
- { |
- UInt32 _cyclicBufferPos; |
- UInt32 _cyclicBufferSize = 0; |
- UInt32 _matchMaxLen; |
- |
- UInt32[] _son; |
- UInt32[] _hash; |
- |
- UInt32 _cutValue = 0xFF; |
- UInt32 _hashMask; |
- UInt32 _hashSizeSum = 0; |
- |
- bool HASH_ARRAY = true; |
- |
- const UInt32 kHash2Size = 1 << 10; |
- const UInt32 kHash3Size = 1 << 16; |
- const UInt32 kBT2HashSize = 1 << 16; |
- const UInt32 kStartMaxLen = 1; |
- const UInt32 kHash3Offset = kHash2Size; |
- const UInt32 kEmptyHashValue = 0; |
- const UInt32 kMaxValForNormalize = ((UInt32)1 << 31) - 1; |
- |
- UInt32 kNumHashDirectBytes = 0; |
- UInt32 kMinMatchCheck = 4; |
- UInt32 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 new void SetStream(System.IO.Stream stream) { base.SetStream(stream); } |
- public new void ReleaseStream() { base.ReleaseStream(); } |
- |
- public new void Init() |
- { |
- base.Init(); |
- for (UInt32 i = 0; i < _hashSizeSum; i++) |
- _hash[i] = kEmptyHashValue; |
- _cyclicBufferPos = 0; |
- ReduceOffsets(-1); |
- } |
- |
- public new void MovePos() |
- { |
- if (++_cyclicBufferPos >= _cyclicBufferSize) |
- _cyclicBufferPos = 0; |
- base.MovePos(); |
- if (_pos == kMaxValForNormalize) |
- Normalize(); |
- } |
- |
- public new Byte GetIndexByte(Int32 index) { return base.GetIndexByte(index); } |
- |
- public new UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit) |
- { return base.GetMatchLen(index, distance, limit); } |
- |
- public new UInt32 GetNumAvailableBytes() { return base.GetNumAvailableBytes(); } |
- |
- public void Create(UInt32 historySize, UInt32 keepAddBufferBefore, |
- UInt32 matchMaxLen, UInt32 keepAddBufferAfter) |
- { |
- if (historySize > kMaxValForNormalize - 256) |
- throw new Exception(); |
- _cutValue = 16 + (matchMaxLen >> 1); |
- |
- UInt32 windowReservSize = (historySize + keepAddBufferBefore + |
- matchMaxLen + keepAddBufferAfter) / 2 + 256; |
- |
- base.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize); |
- |
- _matchMaxLen = matchMaxLen; |
- |
- UInt32 cyclicBufferSize = historySize + 1; |
- if (_cyclicBufferSize != cyclicBufferSize) |
- _son = new UInt32[(_cyclicBufferSize = cyclicBufferSize) * 2]; |
- |
- UInt32 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 UInt32[_hashSizeSum = hs]; |
- } |
- |
- public UInt32 GetMatches(UInt32[] distances) |
- { |
- UInt32 lenLimit; |
- if (_pos + _matchMaxLen <= _streamPos) |
- lenLimit = _matchMaxLen; |
- else |
- { |
- lenLimit = _streamPos - _pos; |
- if (lenLimit < kMinMatchCheck) |
- { |
- MovePos(); |
- return 0; |
- } |
- } |
- |
- UInt32 offset = 0; |
- UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; |
- UInt32 cur = _bufferOffset + _pos; |
- UInt32 maxLen = kStartMaxLen; // to avoid items for len < hashSize; |
- UInt32 hashValue, hash2Value = 0, hash3Value = 0; |
- |
- if (HASH_ARRAY) |
- { |
- UInt32 temp = CRC.Table[_bufferBase[cur]] ^ _bufferBase[cur + 1]; |
- hash2Value = temp & (kHash2Size - 1); |
- temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8); |
- hash3Value = temp & (kHash3Size - 1); |
- hashValue = (temp ^ (CRC.Table[_bufferBase[cur + 3]] << 5)) & _hashMask; |
- } |
- else |
- hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8); |
- |
- UInt32 curMatch = _hash[kFixHashSize + hashValue]; |
- if (HASH_ARRAY) |
- { |
- UInt32 curMatch2 = _hash[hash2Value]; |
- UInt32 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; |
- |
- UInt32 ptr0 = (_cyclicBufferPos << 1) + 1; |
- UInt32 ptr1 = (_cyclicBufferPos << 1); |
- |
- UInt32 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; |
- } |
- } |
- } |
- |
- UInt32 count = _cutValue; |
- |
- while(true) |
- { |
- if(curMatch <= matchMinPos || count-- == 0) |
- { |
- _son[ptr0] = _son[ptr1] = kEmptyHashValue; |
- break; |
- } |
- UInt32 delta = _pos - curMatch; |
- UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ? |
- (_cyclicBufferPos - delta) : |
- (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1; |
- |
- UInt32 pby1 = _bufferOffset + curMatch; |
- UInt32 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] < _bufferBase[cur + len]) |
- { |
- _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(UInt32 num) |
- { |
- do |
- { |
- UInt32 lenLimit; |
- if (_pos + _matchMaxLen <= _streamPos) |
- lenLimit = _matchMaxLen; |
- else |
- { |
- lenLimit = _streamPos - _pos; |
- if (lenLimit < kMinMatchCheck) |
- { |
- MovePos(); |
- continue; |
- } |
- } |
- |
- UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0; |
- UInt32 cur = _bufferOffset + _pos; |
- |
- UInt32 hashValue; |
- |
- if (HASH_ARRAY) |
- { |
- UInt32 temp = CRC.Table[_bufferBase[cur]] ^ _bufferBase[cur + 1]; |
- UInt32 hash2Value = temp & (kHash2Size - 1); |
- _hash[hash2Value] = _pos; |
- temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8); |
- UInt32 hash3Value = temp & (kHash3Size - 1); |
- _hash[kHash3Offset + hash3Value] = _pos; |
- hashValue = (temp ^ (CRC.Table[_bufferBase[cur + 3]] << 5)) & _hashMask; |
- } |
- else |
- hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8); |
- |
- UInt32 curMatch = _hash[kFixHashSize + hashValue]; |
- _hash[kFixHashSize + hashValue] = _pos; |
- |
- UInt32 ptr0 = (_cyclicBufferPos << 1) + 1; |
- UInt32 ptr1 = (_cyclicBufferPos << 1); |
- |
- UInt32 len0, len1; |
- len0 = len1 = kNumHashDirectBytes; |
- |
- UInt32 count = _cutValue; |
- while (true) |
- { |
- if (curMatch <= matchMinPos || count-- == 0) |
- { |
- _son[ptr0] = _son[ptr1] = kEmptyHashValue; |
- break; |
- } |
- |
- UInt32 delta = _pos - curMatch; |
- UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ? |
- (_cyclicBufferPos - delta) : |
- (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1; |
- |
- UInt32 pby1 = _bufferOffset + curMatch; |
- UInt32 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] < _bufferBase[cur + len]) |
- { |
- _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(UInt32[] items, UInt32 numItems, UInt32 subValue) |
- { |
- for (UInt32 i = 0; i < numItems; i++) |
- { |
- UInt32 value = items[i]; |
- if (value <= subValue) |
- value = kEmptyHashValue; |
- else |
- value -= subValue; |
- items[i] = value; |
- } |
- } |
- |
- void Normalize() |
- { |
- UInt32 subValue = _pos - _cyclicBufferSize; |
- NormalizeLinks(_son, _cyclicBufferSize * 2, subValue); |
- NormalizeLinks(_hash, _hashSizeSum, subValue); |
- ReduceOffsets((Int32)subValue); |
- } |
- |
- public void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; } |
- } |
-} |