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

}

}