#nullable disable
// 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; }
	}
}