// LZ.BinTree

package com.badlogic.gdx.utils.compression.lz;

import java.io.IOException;

public class BinTree extends InWindow {
	int _cyclicBufferPos;
	int _cyclicBufferSize = 0;
	int _matchMaxLen;

	int[] _son;
	int[] _hash;

	int _cutValue = 0xFF;
	int _hashMask;
	int _hashSizeSum = 0;

	boolean HASH_ARRAY = true;

	static final int kHash2Size = 1 << 10;
	static final int kHash3Size = 1 << 16;
	static final int kBT2HashSize = 1 << 16;
	static final int kStartMaxLen = 1;
	static final int kHash3Offset = kHash2Size;
	static final int kEmptyHashValue = 0;
	static final int kMaxValForNormalize = (1 << 30) - 1;

	int kNumHashDirectBytes = 0;
	int kMinMatchCheck = 4;
	int 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 void Init () throws IOException {
		super.Init();
		for (int i = 0; i < _hashSizeSum; i++)
			_hash[i] = kEmptyHashValue;
		_cyclicBufferPos = 0;
		ReduceOffsets(-1);
	}

	public void MovePos () throws IOException {
		if (++_cyclicBufferPos >= _cyclicBufferSize) _cyclicBufferPos = 0;
		super.MovePos();
		if (_pos == kMaxValForNormalize) Normalize();
	}

	public boolean Create (int historySize, int keepAddBufferBefore, int matchMaxLen, int keepAddBufferAfter) {
		if (historySize > kMaxValForNormalize - 256) return false;
		_cutValue = 16 + (matchMaxLen >> 1);

		int windowReservSize = (historySize + keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + 256;

		super.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize);

		_matchMaxLen = matchMaxLen;

		int cyclicBufferSize = historySize + 1;
		if (_cyclicBufferSize != cyclicBufferSize) _son = new int[(_cyclicBufferSize = cyclicBufferSize) * 2];

		int 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 int[_hashSizeSum = hs];
		return true;
	}

	public int GetMatches (int[] distances) throws IOException {
		int lenLimit;
		if (_pos + _matchMaxLen <= _streamPos)
			lenLimit = _matchMaxLen;
		else {
			lenLimit = _streamPos - _pos;
			if (lenLimit < kMinMatchCheck) {
				MovePos();
				return 0;
			}
		}

		int offset = 0;
		int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
		int cur = _bufferOffset + _pos;
		int maxLen = kStartMaxLen; // to avoid items for len < hashSize;
		int hashValue, hash2Value = 0, hash3Value = 0;

		if (HASH_ARRAY) {
			int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF);
			hash2Value = temp & (kHash2Size - 1);
			temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8);
			hash3Value = temp & (kHash3Size - 1);
			hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask;
		} else
			hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8));

		int curMatch = _hash[kFixHashSize + hashValue];
		if (HASH_ARRAY) {
			int curMatch2 = _hash[hash2Value];
			int 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;

		int ptr0 = (_cyclicBufferPos << 1) + 1;
		int ptr1 = (_cyclicBufferPos << 1);

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

		int count = _cutValue;

		while (true) {
			if (curMatch <= matchMinPos || count-- == 0) {
				_son[ptr0] = _son[ptr1] = kEmptyHashValue;
				break;
			}
			int delta = _pos - curMatch;
			int cyclicPos = ((delta <= _cyclicBufferPos) ? (_cyclicBufferPos - delta)
				: (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;

			int pby1 = _bufferOffset + curMatch;
			int 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] & 0xFF) < (_bufferBase[cur + len] & 0xFF)) {
				_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 (int num) throws IOException {
		do {
			int lenLimit;
			if (_pos + _matchMaxLen <= _streamPos)
				lenLimit = _matchMaxLen;
			else {
				lenLimit = _streamPos - _pos;
				if (lenLimit < kMinMatchCheck) {
					MovePos();
					continue;
				}
			}

			int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
			int cur = _bufferOffset + _pos;

			int hashValue;

			if (HASH_ARRAY) {
				int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF);
				int hash2Value = temp & (kHash2Size - 1);
				_hash[hash2Value] = _pos;
				temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8);
				int hash3Value = temp & (kHash3Size - 1);
				_hash[kHash3Offset + hash3Value] = _pos;
				hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask;
			} else
				hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8));

			int curMatch = _hash[kFixHashSize + hashValue];
			_hash[kFixHashSize + hashValue] = _pos;

			int ptr0 = (_cyclicBufferPos << 1) + 1;
			int ptr1 = (_cyclicBufferPos << 1);

			int len0, len1;
			len0 = len1 = kNumHashDirectBytes;

			int count = _cutValue;
			while (true) {
				if (curMatch <= matchMinPos || count-- == 0) {
					_son[ptr0] = _son[ptr1] = kEmptyHashValue;
					break;
				}

				int delta = _pos - curMatch;
				int cyclicPos = ((delta <= _cyclicBufferPos) ? (_cyclicBufferPos - delta)
					: (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;

				int pby1 = _bufferOffset + curMatch;
				int 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] & 0xFF) < (_bufferBase[cur + len] & 0xFF)) {
					_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 (int[] items, int numItems, int subValue) {
		for (int i = 0; i < numItems; i++) {
			int value = items[i];
			if (value <= subValue)
				value = kEmptyHashValue;
			else
				value -= subValue;
			items[i] = value;
		}
	}

	void Normalize () {
		int subValue = _pos - _cyclicBufferSize;
		NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
		NormalizeLinks(_hash, _hashSizeSum, subValue);
		ReduceOffsets(subValue);
	}

	public void SetCutValue (int cutValue) {
		_cutValue = cutValue;
	}

	private static final int[] CrcTable = new int[256];

	static {
		for (int i = 0; i < 256; i++) {
			int r = i;
			for (int j = 0; j < 8; j++)
				if ((r & 1) != 0)
					r = (r >>> 1) ^ 0xEDB88320;
				else
					r >>>= 1;
			CrcTable[i] = r;
		}
	}
}
