// 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; }
}
}