tor-browser

LzBinTree.cs (9637B)

---

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