hash.cpp

My (so called) HiP compression algorithm as console mode utility. It s a hybrid of Lempel-Ziv 77 a

#include "hash.h"

#include "WarnOff.h"

//
// constants
//
#define HASH_BITS       16
#define HASH_MASK       ((1 << HASH_BITS)-1)
#define HASH_SIZE       (1 << 16)

#define PRE_HASH_CNT    5

//
// macros
//
#define UPDATE_KEY( k, c ) (DWORD)((( k << 2) ^ c ) & HASH_MASK )
#define INSERT_HASH( key, indexvalue ) (*(PDWORD)((DWORD)m_Hash + (DWORD)key*4) = (DWORD)indexvalue)
#define HASH_VALUE( key )  ( *(PDWORD)((DWORD)m_Hash + (DWORD)key*4) )

Hash::Hash(void)
{
	m_Hash   = NULL;
}

Hash::~Hash(void)
{
	Dispose();
}

//
// Purpose:
//   Root cleanup member function
//
void Hash::Dispose()
{
	if ( m_Hash )
	{
		free( m_Hash );
		m_Hash = NULL;
	}
	return;
}

BOOL Hash::Assign( PBYTE buffer, DWORD cb )
{
	this->m_Buff    = buffer;
	this->m_cbBuff  = cb;

	Dispose();

	m_Hash = (BYTE**)malloc( HASH_SIZE*sizeof(DWORD) );
	if ( !m_Hash )
		return FALSE; // ERR
	memset( (void*)m_Hash, 0, HASH_SIZE*4 );

	return TRUE; // OK
}

//
// Purpose:
//   The core string comparision via node tracing
//
BOOL Hash::FindMatch(IN  PBYTE pbyWin, IN DWORD cbWin, IN PBYTE pData, IN DWORD cbData, 
						   OUT DWORD &dwDistance, OUT DWORD &dwLength )
{
	DWORD key = pData[0];
	DWORD value;

	// pre-initialize the output vars
	dwDistance  = 0;
	dwLength    = 0;

	if ( cbData < 2 )
		return FALSE; // ERR

	UINT i = 1;
	do
	{
		key = UPDATE_KEY( key, pData[i] );
		value = HASH_VALUE( key );
		if ( value == 0 )
			break;
		i++;
		if ( value >= (DWORD)pbyWin &&
			 value < (DWORD)pbyWin + cbWin &&
			 *(PWORD)pData == *(PWORD)value )
		{
			dwLength    = i;
			dwDistance  = (DWORD)pData - value;
		}
		if ( dwLength >= cbData )
			return TRUE; // OK
	} while( i < PRE_HASH_CNT );

	return (dwLength >= 2) ? TRUE : FALSE;
}

//
// Purpose:
//   Shape member function for HashSearch::FindMatch
//
BOOL Hash::FindLongestMatch(IN  PBYTE pbyWin, IN PBYTE pData, IN DWORD cbData, 
						   IN DWORD cbMin2Match, IN BOOL bAddNode, OUT DWORD &dwDistance, OUT DWORD &dwLength )
{
	// validate input variables
	if ( cbData < cbMin2Match )
		return FALSE; // ERR

	BOOL bRet = FindMatch(
		pbyWin, (DWORD)pData - (DWORD)pbyWin,
		pData, cbData,
		dwDistance, dwLength );

	// minimal match length reached ?
	if ( dwLength < cbMin2Match )
		bRet = FALSE;

	// correct too big matches
//	dwLength = min( dwLength, cbWin );

	// add node for current position of non-last + wanted
	if ( bAddNode && cbData > 1 )
		InsertHash( pData, cbData );

	return bRet;
}

//
// Purpose:
//   Calls HashSearch::AddNode for the specified number of bytes
//   at the specified data position
//
void Hash::UpdateNodesForRange( PBYTE pby, DWORD cbAdd, DWORD cbMax )
{
	for ( UINT i = 0; i < cbAdd; i++ )
		InsertHash( pby++, cbMax-i );

	return;
}

BOOL Hash::InsertHash( void* p, DWORD cbMax )
{
	PBYTE ptr = (PBYTE)p;

	if ( cbMax < 2 )
		return FALSE; // ERR

	DWORD key = ptr[0];
	for ( UINT i = 1; i < PRE_HASH_CNT,i < cbMax; i++ )
	{
		key = UPDATE_KEY( key, ptr[i] );
		INSERT_HASH( key, p );
	}	

	return TRUE; // OK
}