Subversion Repositories Kolibri OS

#include "MatchFinder.h"

/* memcpy must be inlined - we do not want to use RTL */

#include 

/*#pragma function(memcpy)

void* __cdecl memcpy(void* _Dst, const void* _Src, size_t _Size)

{

	unsigned long i;

	for (i = 0; i < _Size; i++)

		((char*)_Dst)[i] = ((char*)_Src)[i];

	return _Dst;

}*/

//#pragma intrinsic(memcpy)

#define kMaxValForNormalize (((unsigned)1<<31)-1)

/* settings for bt4:

	defined HASH_ARRAY_2

	defined HASH_ARRAY_3

*/

//#define kHash2Size 0x400

#define kNumHashDirectBytes 0

#define kNumHashBytes 3

//#define kHash3Size 0x40000

#define kHash2Size 0x10000

#define kHashSize 0x100000

#define kHashSizeSum (kHashSize+kHash2Size)

#define kHash2Offset kHashSize

static unsigned _cyclicBufferPos;

static unsigned _cyclicBufferSize;

static unsigned _matchMaxLen;

static unsigned* _hash;

static unsigned _cutValue;

#ifdef GENERIC_INPUT

static byte* _bufferBase;

static unsigned _posLimit;

static bool _streamEndWasReached;

static byte* _pointerToLastSafePosition;

static byte* _buffer;

static unsigned _blockSize;

static unsigned _pos;

static unsigned _keepSizeBefore;

static unsigned _keepSizeAfter;

static unsigned _keepSizeReserv;

static unsigned _streamPos;

#else

#define _buffer curin

#define _pos pack_pos

#define _streamPos pack_length

#endif

#ifdef GENERIC_INPUT

/* LZ Window */

static void LZInWindow_Create(unsigned keepSizeBefore,unsigned keepSizeAfter,unsigned keepSizeReserv,byte**mem)

{

	_keepSizeBefore = keepSizeBefore;

	_keepSizeAfter = keepSizeAfter;

	_keepSizeReserv = keepSizeReserv;

	_blockSize = keepSizeBefore + keepSizeAfter + keepSizeReserv;

	_bufferBase = *mem;

	_blockSize = (_blockSize + 3) & ~3;

	*mem += _blockSize;

	_pointerToLastSafePosition = _bufferBase + _blockSize - keepSizeAfter;

}

static void ReadBlock(void)

{

	if (_streamEndWasReached)

		return;

	for (;;)

	{

		unsigned size;

		size = (unsigned)(_bufferBase-_buffer) + _blockSize - _streamPos;

		if (!size) return;

		if (size > pack_length - pack_pos)

			size = pack_length - pack_pos;

		memcpy(_buffer+_streamPos,curin,size);

		curin += size;

		pack_pos += size;

		if (size == 0)

		{

			byte* pointerToPosition;

			_posLimit = _streamPos;

			pointerToPosition = _buffer + _posLimit;

			if (pointerToPosition > _pointerToLastSafePosition)

				_posLimit = _pointerToLastSafePosition - _buffer;

			_streamEndWasReached = true;

			return;

		}

		_streamPos += size;

		if (_streamPos >= _pos + _keepSizeAfter)

		{

			_posLimit = _streamPos - _keepSizeAfter;

			return;

		}

	}

}

static void LZInWindow_Init(void)

{

	_buffer = _bufferBase;

	_pos = 0;

	_streamPos = 0;

	_streamEndWasReached = false;

	ReadBlock();

}

#else

#define LZInWindow_Create(a,b,c,d) /* nothing */

#define LZInWindow_Init() _buffer--, _pos++, _streamPos++

#endif

const byte* GetPointerToCurrentPos(void) {return _buffer+_pos;}

#ifdef GENERIC_INPUT

static void MoveBlock(void)

{

	unsigned offset,numBytes;

	offset = _buffer-_bufferBase+_pos-_keepSizeBefore;

	numBytes = _buffer-_bufferBase+_streamPos-offset;

	// copying backwards: safe to use memcpy instead of memmove

	memcpy(_bufferBase,_bufferBase+offset,numBytes);

	_buffer -= offset;

}

static void LZInWindow_MovePos(void)

{

	_pos++;

	if (_pos > _posLimit)

	{

		const byte* pointerToPosition = _buffer+_pos;

		if (pointerToPosition > _pointerToLastSafePosition)

			MoveBlock();

		ReadBlock();

	}

}

#else

#define LZInWindow_MovePos() _pos++

#endif

byte GetIndexByte(int index) {return _buffer[_pos+index];}

unsigned GetMatchLen(int index,unsigned distance,unsigned limit)

{

	const byte* pby;

	unsigned i;

#ifdef GENERIC_INPUT

	if (_streamEndWasReached)

		if ((_pos+index)+limit > _streamPos)

			limit = _streamPos - (_pos+index);

#else

	unsigned limit2 = pack_length - (pack_pos + index);

	if (limit > limit2)

		limit = limit2;

#endif

	distance++;

	pby = _buffer + _pos + index;

	for (i=0;i

	return i;

}

unsigned GetNumAvailableBytes(void) {return _streamPos-_pos;}

#ifdef GENERIC_INPUT

void ReduceOffsets(int subValue)

{

	_buffer += subValue;

	_posLimit -= subValue;

	_pos -= subValue;

	_streamPos -= subValue;

}

#else

#define ReduceOffsets(a) /* nothing */

#endif

/* Binary tree Match Finder */

static unsigned crc_table[256];

void MatchFinder_Create(unsigned historySize,unsigned keepAddBufferBefore,unsigned matchMaxLen,unsigned keepAddBufferAfter,byte**mem)

{

	unsigned sizeReserv;

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

	LZInWindow_Create(historySize+keepAddBufferBefore,matchMaxLen+keepAddBufferAfter,sizeReserv,mem);

	_matchMaxLen = matchMaxLen;

	_cyclicBufferSize = historySize+1;

	_hash = (unsigned*)*mem;

	*mem += (kHashSizeSum + _cyclicBufferSize*2) * sizeof(unsigned);

	_cutValue = 0xFF;

}

void MatchFinder_Init(void)

{

	unsigned i,j,r;

	LZInWindow_Init();

	for (i=0;i

		_hash[i] = 0;

	_cyclicBufferPos = 0;

	ReduceOffsets(-1);

	for (i=0;i<256;i++)

	{

		r = i;

		for (j=0;j<8;j++)

		{

			if (r & 1)

				r = (r>>1) ^ 0xEDB88320;

			else

				r >>= 1;

		}

		crc_table[i] = r;

	}

}

static unsigned Hash(const byte* ptr, unsigned* hash2Value)

{

	unsigned temp;

	temp = crc_table[ptr[0]] ^ ptr[1];

	*hash2Value = *(word*)ptr; //ptr[0] + ((unsigned)ptr[1] << 8);

	return (temp ^ ((unsigned)ptr[2]<<8)) & (kHashSize - 1);

}

unsigned GetLongestMatch(unsigned* distances)

{

	unsigned lenLimit,maxLen=0;

	unsigned matchMinPos;

	const byte* cur;

	unsigned hash2Value,hashValue;

	unsigned curMatch,curMatch2;

	unsigned *son,*ptr0,*ptr1;

	unsigned len0,len1,count;

	if (_pos + _matchMaxLen <= _streamPos)

		lenLimit = _matchMaxLen;

	else

	{

		lenLimit = _streamPos - _pos;

		if (lenLimit < kNumHashBytes)

			return 0;

	}

	matchMinPos = (_pos>_cyclicBufferSize) ? (_pos-_cyclicBufferSize) : 0;

	cur = _buffer+_pos;

	hashValue = Hash(cur,&hash2Value);

	curMatch = _hash[hashValue];

	curMatch2 = _hash[kHash2Offset + hash2Value];

	_hash[kHash2Offset + hash2Value] = _pos;

	distances[2] = 0xFFFFFFFF;

	if (curMatch2 > matchMinPos)

		//if (_buffer[curMatch2] == cur[0])

		{

			distances[2] = _pos - curMatch2 - 1;

			maxLen = 2;

		}

	_hash[hashValue] = _pos;

	son = _hash + kHashSizeSum;

	ptr0 = son + (_cyclicBufferPos << 1) + 1;

	ptr1 = son + (_cyclicBufferPos << 1);

	distances[kNumHashBytes] = 0xFFFFFFFF;

	len0 = len1 = kNumHashDirectBytes;

	count = _cutValue;

	for (;;)

	{

		const byte* pb;

		unsigned len,delta;

		unsigned cyclicPos;

		unsigned* pair;

		if (curMatch <= matchMinPos || count--==0)

		{

			*ptr0 = *ptr1 = 0;

			break;

		}

		pb = _buffer+curMatch;

		len = (len0

		do

			if (pb[len] != cur[len]) break;

		while (++len != lenLimit);

		delta = _pos - curMatch;

		while (maxLen < len)

			distances[++maxLen] = delta-1;

		cyclicPos = (delta <= _cyclicBufferPos) ?

			(_cyclicBufferPos - delta) :

			(_cyclicBufferPos - delta + _cyclicBufferSize);

		pair = son + (cyclicPos<<1);

		if (len != lenLimit)

		{

			if (pb[len] < cur[len])

			{

				*ptr1 = curMatch;

				ptr1 = pair+1;

				curMatch = *ptr1;

				len1 = len;

			}

			else

			{

				*ptr0 = curMatch;

				ptr0 = pair;

				curMatch = *ptr0;

				len0 = len;

			}

		}

		else

		{

			*ptr1 = pair[0];

			*ptr0 = pair[1];

			break;

		}

	}

	/*if (distances[4] < distances[3])

		distances[3] = distances[4];

	if (distances[3] < distances[2])

		distances[2] = distances[3];*/

	return maxLen;

}

void DummyLongestMatch(void)

{

	unsigned lenLimit;

	unsigned matchMinPos;

	const byte* cur;

	unsigned hash2Value,hashValue;

	unsigned curMatch;

	unsigned* son,*ptr0,*ptr1;

	unsigned len0,len1,count;

	if (_pos + _matchMaxLen <= _streamPos)

		lenLimit = _matchMaxLen;

	else

	{

		lenLimit = _streamPos - _pos;

		if (lenLimit < kNumHashBytes)

			return;

	}

	matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;

	cur = _buffer+_pos;

	hashValue = Hash(cur,&hash2Value);

	_hash[kHash2Offset + hash2Value] = _pos;

	curMatch = _hash[hashValue];

	_hash[hashValue] = _pos;

	son = _hash+kHashSizeSum;

	ptr0 = son + (_cyclicBufferPos << 1) + 1;

	ptr1 = son + (_cyclicBufferPos << 1);

	len0 = len1 = kNumHashDirectBytes;

	count = _cutValue;

	for (;;)

	{

		const byte* pb;

		unsigned len;

		unsigned delta,cyclicPos;

		unsigned* pair;

		if (curMatch <= matchMinPos || count--==0)

			break;

		pb = _buffer+curMatch;

		len = (len0

		do

			if (pb[len] != cur[len]) break;

		while (++len != lenLimit);

		delta = _pos - curMatch;

		cyclicPos = (delta <= _cyclicBufferPos) ?

			(_cyclicBufferPos - delta) :

			(_cyclicBufferPos - delta + _cyclicBufferSize);

		pair = son + (cyclicPos << 1);

		if (len != lenLimit)

		{

			if (pb[len] < cur[len])

			{

				*ptr1 = curMatch;

				ptr1 = pair+1;

				curMatch = *ptr1;

				len1 = len;

			}

			else

			{

				*ptr0 = curMatch;

				ptr0 = pair;

				curMatch = *ptr0;

				len0 = len;

			}

		}

		else

		{

			*ptr1 = pair[0];

			*ptr0 = pair[1];

			return;

		}

	}

	*ptr0 = *ptr1 = 0;

}

#ifdef GENERIC_INPUT

// for memory input size is always less than kMaxValForNormalize

static void Normalize(void)

{

	unsigned subValue;

	unsigned* items;

	unsigned i,numItems;

	subValue = _pos - _cyclicBufferSize;

	items = _hash;

	numItems = (kHashSizeSum + _cyclicBufferSize*2);

	for (i=0;i

	{

		unsigned value;

		value = items[i];

		if (value <= subValue)

			value = 0;

		else

			value -= subValue;

		items[i] = value;

	}

	ReduceOffsets(subValue);

}

#endif

void MatchFinder_MovePos(void)

{

	if (++_cyclicBufferPos == _cyclicBufferSize)

		_cyclicBufferPos = 0;

	LZInWindow_MovePos();

#ifdef GENERIC_INPUT

	if (_pos == kMaxValForNormalize)

		Normalize();

#endif

}