Subversion Repositories spk

#include "literalhufftree.h"

#include <math.h>

#include <crtdbg.h>

#include <stdio.h>

#include "ByteReader.h"

#include "Macros.h"

//#include "WarnOff.h"

extern bool g_bError;

LiteralHuffTree::LiteralHuffTree(void)

{

	ZERO( m_dwOccurr );

	ZERO( m_tree );

	m_ucTreeItems           = 0;

}

LiteralHuffTree::~LiteralHuffTree(void)

{

}

//

// Purpose:

//   A root procedure

//

BOOL LiteralHuffTree::Generate( PBYTE buff, DWORD cb )

{

	if ( !buff || !cb )

		return FALSE; // ERR

	GetByteOccurrences( buff, cb );

	BuildInternalTree();

	LinkTreeElements();

	GenerateBitSequences();

	return TRUE; // OK

}

//

// Purpose:

//   A root procedure

//

BOOL LiteralHuffTree::GenerateWithOccurrences()

{

	BuildInternalTree();

	LinkTreeElements();

	return GenerateBitSequences();

}

//

// Purpose:

//   A root procedure

//

BOOL LiteralHuffTree::GenerateAdaptiveModel()

{

	//

	// init the occurrences with 1 for each symbol in the alphabet

	//

	for ( UINT i = 0; i < ARRAY_ITEMS(m_dwOccurr); i++ )

		m_dwOccurr[i] = 1;

	//

	// generate the tree, ...

	//

	BuildInternalTree();

	LinkTreeElements();

	GenerateBitSequences();

	return TRUE; // OK

}

//

// Purpose:

//   Scan the specified buffer and log the occurrence

//   of each byte

//

void LiteralHuffTree::GetByteOccurrences( PBYTE pby, DWORD cb )

{

	ZERO( m_dwOccurr );

	while( cb )

	{

		m_dwOccurr[ *pby ]++;

		--cb;

		++pby;

	}

	return;

}

//

// Purpose:

//   Transfer the occurrences array into m_tree items

//

void LiteralHuffTree::BuildInternalTree()

{

	ZERO( m_tree );

	for ( UINT u = 0; u < 256; u++ )

	{

		m_tree[u].id            = u;

		m_tree[u].dwcOccurr     = m_dwOccurr[u];

		m_tree[u].dwRightId     = (DWORD)-1;        // indicates the end of a branch

		m_tree[u].dwLeftId      = (DWORD)-1;        // indicates the end of a branch

	}

	m_ucTreeItems = 256;

	return;

}

//

// Purpose:

//   Builds the Huffman tree linkage by adding branch items in the chain

//

// Remarks:

//   (biggest probability first)

//

void LiteralHuffTree::LinkTreeElements()

{

	PLHT_ITEM   pitem1, pitem2, pitem, pLastLink;

	LHT_ITEM    branch, pseudoitem;

	if ( !m_ucTreeItems )

		return; // no items in our tree

	pseudoitem.dwcOccurr  = MAXDWORD;

	pLastLink             = NULL;

	for (;;)

	{

		//

		// search unlinked items with the lowest occurrences

		//

		pitem1 = NULL;

		pitem2 = NULL;

		pitem1 = &pseudoitem;

		UINT u;

		for ( u = 0; u < m_ucTreeItems; u++ )

		{

			pitem = &m_tree[u];

			if ( !pitem->bLinked && pitem->dwcOccurr > 0 && pitem->dwcOccurr < pitem1->dwcOccurr )

				pitem1           = pitem;

		}

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

		pitem2 = &pseudoitem;

		for ( u = 0; u < m_ucTreeItems; u++ )

		{

			pitem = &m_tree[u];

			if ( !pitem->bLinked && pitem->dwcOccurr > 0 && pitem->dwcOccurr < pitem2->dwcOccurr)

				pitem2           = pitem;

		}

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

		//

		// did we link all items ?

		//

		if ( pitem1->dwcOccurr == MAXDWORD || pitem2->dwcOccurr == MAXDWORD )

		{

			if ( pLastLink )

				pLastLink->dwDadId = MAXDWORD; // indicates root item

			break; // exit for(;;) loop

		}

		_ASSERT( m_ucTreeItems < ARRAY_ITEMS(m_tree) );

		//

		// add a branch item linking the 2

		//

		ZERO( branch )

		branch.id         = m_ucTreeItems;

		branch.bLinked    = FALSE;

		branch.dwLeftId   = pitem1->id;

		branch.dwRightId  = pitem2->id;

		branch.dwcOccurr  = pitem1->dwcOccurr + pitem2->dwcOccurr;

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

		m_tree[ m_ucTreeItems++ ] = branch;

		pLastLink = &m_tree[ m_ucTreeItems - 1 ];

	}

	return;

}

//

// Purpose:

//   Trace the tree for non-branch items to find out

//   their corresponding bit sequences

//

bool LiteralHuffTree::GenerateBitSequences()

{

	PLHT_ITEM  pitem, ptrace, ptrace2;

	DWORD      cbitsBig = 0, cbitsSmall = 0xFF;

	for ( UINT u = 0; u < m_ucTreeItems; u++ )

	{

		pitem = &m_tree[u];

		if ( !pitem->dwcOccurr )

			continue; // this literal is never used

		if ( pitem->dwLeftId == (DWORD)-1 && pitem->dwRightId == (DWORD)-1 )

		{

			//

			// handle a non-branch chain element

			//

			ptrace = pitem;

			while( ptrace->dwDadId != (DWORD)-1 )

			{

				ptrace2 = &m_tree[ ptrace->dwDadId ];

				if ( ptrace->id == ptrace2->dwRightId )

					pitem->dwSequence |= HT_RIGHT;

				else

					pitem->dwSequence |= HT_LEFT;

				++pitem->bySequLen;

				pitem->dwSequence <<= 1;

				ptrace = ptrace2;

			}			

			pitem->dwSequence >>= 1;

/*			if ( pitem->bySequLen >= 15 )

			{

				g_bError = true;

				return false;

			}*/

		}

	}

	return true;

}

//

// Purpose:

//   Calculates the number of bits that eats to

//   biggest occurrence value in the set

//

//

DWORD LiteralHuffTree::GetBitCountForOccurrence()

{

	DWORD dwMax = 0;

	// get the biggest occurrence value

	for ( UINT u = 0; u < 256; u++ )

		if ( m_tree[u].dwcOccurr > dwMax )

			dwMax = m_tree[u].dwcOccurr;

	// calculate how much bits we'll need to store this value

	float f = (float)log((double)dwMax) / (float)log(2.0f);

	DWORD c = (DWORD)f;

	if ( (float)c < f ) // is f a decimal number ?

		c++;

	return c;

}

//

// Purpose:

//   This routine returns the data field of the HT_ITEM structure

//   which is identified by reading bits form the ByteReader class

//

DWORD LiteralHuffTree::QueryLiteralByBitSequence( PByteReader reader )

{

	PLHT_ITEM pitem; 

	pitem = &m_tree[m_ucTreeItems - 1];

	while ( pitem->dwLeftId != -1 && pitem->dwRightId != -1 )

		switch( reader->ReadBit() )

		{

		case HT_LEFT:

			pitem = &m_tree[pitem->dwLeftId];

			break;

		case HT_RIGHT:

			pitem = &m_tree[pitem->dwRightId];

			break;

		}

	return pitem->id; 

}