hufftree.cpp

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

#include "hufftree.h"
#include <stddef.h>
#include <math.h>
#include <crtdbg.h>
#include "HipPack.h"
#include "Macros.h"
#include "WarnOff.h"

HuffTree::HuffTree(void)
{
	m_dscItems = new DynamicStructChain( sizeof( HT_ITEM ) );
	m_dscItems->SetMemStartItemNum( DSC_START );
	m_dscItems->SetMemGrowthItemNum( DSC_GROW );
}

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

//
// Purpose:
//   Performs all required class cleanups
//
void HuffTree::Dispose()
{
	delete m_dscItems;

	return;
}

//
// Purpose:
//   Add an item in the virgin array
//
// Remarks:
//   Used in compression process
//
BOOL HuffTree::AddItem( DWORD dwData, DWORD dwcOccurrence )
{
	HT_ITEM item;

	// fill struct
	item.dwId       = (BYTE)m_dscItems->GetItemNum(); // take the index as unique ID
	item.dwData     = dwData;
	item.dwcOccurr  = dwcOccurrence;
	item.dwLeftId   = -1;                             // end of branch
	item.dwRightId  = -1;                             //
	item.bLinked    = FALSE;
	item.bySequLen  = 0;
	item.dwSequence = 0;

	// & pass it
	return m_dscItems->AddItem( &item );
}

//
// Purpose:
//   Add an item in the virgin array
//
// Remarks:
//   Overloaded
//   Used in decompression process
//
BOOL HuffTree::AddItem( DWORD Id, DWORD dwData, DWORD dwLeftId, DWORD dwRightId )
{
	HT_ITEM item;

	// fill struct
	item.dwId       = Id;
	item.dwData     = dwData;
	item.dwLeftId   = dwLeftId;
	item.dwRightId  = dwRightId;

	item.dwcOccurr  = 0;
	item.bLinked    = FALSE;
	item.bySequLen  = 0;
	item.dwSequence = 0;

	// & pass it
	return m_dscItems->AddItem( &item );
}

/*
//
// Purpose:
//   Get the number of plains being needed in a Huffman
//   tree to store the current number of elements.
//   
//   Formula:
//   max_tree_deeps = log(item_count+1) / log(2)
//
//
DWORD HuffTree::GetTreePlainCount()
{
	double d;
	DWORD  c;

	d = log( m_dscItems->GetItemNum() + 1 ) / log(2);
	c = (DWORD)d;
	if ( (double)c < d ) // is d a decimal number ? -> round up...
		c++;

	return c;
}
*/

//
// Purpose:
//   Builds the Huffman tree linkage by adding branch items in the chain
//
// Remarks:
//   Tree elements should already be in sorted state
//   (biggest probability first)
//
void HuffTree::LinkTreeElements()
{
	PHT_ITEM   pitem1, pitem2, pitem, pLastLink;
	HT_ITEM    branch, pseudoitem;

	pseudoitem.dwcOccurr  = MAXDWORD;
	for (;;)
	{
		//
		// search unlinked items with the lowest occurrences
		//
		pitem1 = NULL;
		pitem2 = NULL;
		pitem1 = &pseudoitem;
		for ( UINT u = 0; u < m_dscItems->GetItemNum(); u++ )
		{
			pitem = (PHT_ITEM)m_dscItems->GetItem( u );
			if ( !pitem->bLinked && pitem->dwcOccurr < pitem1->dwcOccurr )
				pitem1           = pitem;
		}
		pitem1->bLinked = TRUE;
		pitem2 = &pseudoitem;
		for ( UINT u = 0; u < m_dscItems->GetItemNum(); u++ )
		{
			pitem = (PHT_ITEM)m_dscItems->GetItem( u );
			if ( !pitem->bLinked && pitem->dwcOccurr < pitem2->dwcOccurr)
				pitem2           = pitem;
		}

		// mark the found items linked !
		pitem2->bLinked = TRUE; 

		//
		// did we link all items ?
		//
		if ( pitem1->dwcOccurr == MAXDWORD || pitem2->dwcOccurr == MAXDWORD )
		{
			pLastLink->dwDadId = MAXDWORD; // indicates root item
			pLastLink->dwData  = MAXDWORD; // indicates root item
			break; // exit for(;;) loop
		}

		//
		// add a branch item linking the 2
		//
		ZERO( branch )
		branch.dwId       = m_dscItems->GetItemNum();
		branch.bLinked    = FALSE;
		branch.dwLeftId   = pitem1->dwId;
		branch.dwRightId  = pitem2->dwId;
		branch.dwcOccurr  = pitem1->dwcOccurr + pitem2->dwcOccurr;

		pitem1->dwDadId = pitem2->dwDadId = branch.dwId;

		m_dscItems->AddItem( &branch );
		pLastLink = (PHT_ITEM)m_dscItems->GetItem( m_dscItems->GetItemNum() - 1 );
	}

	return;
}

//
// Returns:
//   NULL - error
//
PHT_ITEM HuffTree::ItemId2Ptr( DWORD id )
{
	PHT_ITEM p;

	for ( UINT i = 0; i < m_dscItems->GetItemNum(); i++ )
	{
		p = (PHT_ITEM)m_dscItems->GetItem( i );
		if ( p->dwId == id ) 
			return p; // OK
	}

	return NULL; // ERR
}

//
// Purpose:
//   Trace the tree for non-branch items to find out
//   their corresponding bit sequences
//
void HuffTree::GenerateBitSequences()
{
	PHT_ITEM  pitem, ptrace, ptrace2;

	for ( UINT u = 0; u < m_dscItems->GetItemNum(); u++ )
	{
		pitem = (PHT_ITEM)m_dscItems->GetItem( u );
		if ( pitem->dwLeftId == (DWORD)-1 && pitem->dwRightId == (DWORD)-1 )
		{
			//
			// handle a non-branch chain element
			//
			ptrace = pitem;
			while( ptrace->dwDadId != (DWORD)-1 )
			{
				ptrace2 = ItemId2Ptr( ptrace->dwDadId );
				if ( ptrace->dwId == ptrace2->dwRightId )
					pitem->dwSequence &= 1;
				++pitem->bySequLen;
				pitem->dwSequence <<= 1;
				ptrace = ptrace2;
			}			
			pitem->dwSequence >>= 1;

			_ASSERT( pitem->bySequLen < 7 );
		}
	}
}

//
// Purpose:
//   Sortes the array elements & adjusts the, up to now, untouched
//   fields in the structs
//
BOOL HuffTree::Generate()
{
	m_dscItems->Sort( DSC_MAX_FIRST, offsetof(HT_ITEM, dwcOccurr) );
	LinkTreeElements();
	GenerateBitSequences();

	return TRUE; // OK
}

//
// Purpose:
//   Write the Huffman table in a compact format
//   to the specified memory area
//
// Returns:
//   Number of bytes emitted to the output buffer
//   0 means error !
//
DWORD HuffTree::Emit( BYTE* pBuff, DWORD cbBuff )
{
	DWORD           cb = 0;
	PHT_ITEM        pitem;
	PHT_ITEM_EMIT   peitem;

	// validate procedure arguments
	if ( cbBuff <= 2 )
		return 0; // ERR

	// write the number of Huffman tree chain items
	*(PWORD)pBuff = (WORD)m_dscItems->GetItemNum();
	cb += 2;

	//
	// write the Huffman chain items to the output buffer
	//
	peitem = MakePtr( PHT_ITEM_EMIT, pBuff, cb );
	for ( UINT u = 0; u < m_dscItems->GetItemNum(); u++ )
	{
		// enough space in buff ?
		if ( (cb + sizeof(HT_ITEM_EMIT)) > cbBuff )
			return 0; // ERR

		// emit
		pitem = (PHT_ITEM)m_dscItems->GetItem( u );
		peitem->Id      = (WORD)pitem->dwId;
		peitem->data    = (WORD)pitem->dwData;
		peitem->wLeft   = (WORD)pitem->dwLeftId;
		peitem->wRight  = (WORD)pitem->dwRightId;

		cb += sizeof(HT_ITEM_EMIT);
		++peitem;
	}

	return cb; // OK
}

//
// Purpose:
//   Returns the pointer to a Huffman tree element
//   if it is found by the specified data
//
PHT_ITEM HuffTree::ItemData2Ptr( DWORD dwItemData )
{
	return (PHT_ITEM)m_dscItems->FindItem( offsetof(HT_ITEM,dwData), dwItemData );
}