huffman.cpp

< VC++编程宝典> 编程必备,适合初学者!

// Huffman.cpp

#include "stdafx.h"
#include "CompressedFile.h"

#define END_OF_STREAM 256

BOOL CHuffmanFile::Open( const char *pszFileName, unsigned int nOpenFlags, CFileException *pError )
{

	m_nCompressionType = HUFF;
	InitializeTree();
	return( CCompressedFile::Open( pszFileName, nOpenFlags, pError ) );

}

void CHuffmanFile::Close( void )
{

	if( m_nFlags != CFile::modeRead ) EncodeSymbol( END_OF_STREAM );
	CCompressedFile::Close();
	if( m_nFlags == ( CFile::modeCreate | CFile::modeWrite ) || m_nFlags == CFile::modeWrite ){
		CFile cf;
		cf.Open( m_szFilename, CFile::modeWrite );
		cf.Seek( m_dwSeekTo, CFile::begin );
		cf.Write( &m_dwUncompressedSize, sizeof( DWORD ) );
		cf.Write( &m_dwCompressedSize, sizeof( DWORD ) );
		cf.Close();
		}
		
}

unsigned int CHuffmanFile::Read( void far *lpBuf, unsigned int nCount )
{
	unsigned char *pTransfer;
	int nSymbol;
	unsigned int nBytesRead = 0;

	pTransfer = (unsigned char *) lpBuf;

	for( unsigned int i=0; i<nCount; i++ ){
		nSymbol = DecodeSymbol();
		if( nSymbol == END_OF_STREAM ) i = nCount;
		else{
			pTransfer[i] = (unsigned char) nSymbol;
			nBytesRead++;
			UpdateModel( nSymbol );
			}
		}

	return( nBytesRead );

}

void CHuffmanFile::Write( void *lpBuf, unsigned int nCount )
{
	unsigned char *pTransfer;

	pTransfer = (unsigned char *) lpBuf;

	for( unsigned int i=0; i<nCount; i++ ){
		EncodeSymbol( (int) pTransfer[i] );
		UpdateModel( (int) pTransfer[i] );
		}
	m_dwUncompressedSize += (DWORD) nCount;

}

void CHuffmanFile::InitializeTree( void )
{

	memset( &Tree, 0, sizeof( TREE ) );

	Tree.nodes[ROOT_NODE].nChild = ROOT_NODE + 1;
	Tree.nodes[ROOT_NODE].nChildIsLeaf = FALSE;
	Tree.nodes[ROOT_NODE].nWeight = 2;
	Tree.nodes[ROOT_NODE].nParent = -1;

	Tree.nodes[ROOT_NODE+1].nChild = END_OF_STREAM;
	Tree.nodes[ROOT_NODE+1].nChildIsLeaf = TRUE;
	Tree.nodes[ROOT_NODE+1].nWeight = 1;
	Tree.nodes[ROOT_NODE+1].nParent = ROOT_NODE;
	Tree.nLeaf[END_OF_STREAM] = ROOT_NODE + 1;

	Tree.nodes[ROOT_NODE+2].nChild = ESCAPE;
	Tree.nodes[ROOT_NODE+2].nChildIsLeaf = TRUE;
	Tree.nodes[ROOT_NODE+2].nWeight = 1;
	Tree.nodes[ROOT_NODE+2].nParent = ROOT_NODE;

	Tree.nLeaf[ESCAPE] = ROOT_NODE + 2;
	Tree.nNextFreeNode = ROOT_NODE + 3;

	for( int i=0; i<END_OF_STREAM; i++ ) Tree.nLeaf[i] = -1;

}

void CHuffmanFile::UpdateModel( int nSymbol )
{
	int nCurrentNode;
	int nNewNode;
	
	if( Tree.nodes[ROOT_NODE].nWeight == MAX_WEIGHT ) RebuildTree();
	
	nCurrentNode = Tree.nLeaf[nSymbol];
	
	while( nCurrentNode != -1 ){
		Tree.nodes[nCurrentNode].nWeight++;
		for( nNewNode=nCurrentNode; nNewNode>ROOT_NODE; nNewNode-- )
			if( Tree.nodes[nNewNode-1].nWeight >= Tree.nodes[nCurrentNode].nWeight) break;
		if( nCurrentNode != nNewNode ){
			SwapNodes( nCurrentNode, nNewNode );
			nCurrentNode = nNewNode;
			}
		nCurrentNode = Tree.nodes[nCurrentNode].nParent;
		}
		
}

void CHuffmanFile::EncodeSymbol( unsigned int nSymbol )
{
	DWORD dwCode = 0;
	DWORD dwCurrentBit = 1;
	int nCodeSize = 0;
	int nCurrentNode = Tree.nLeaf[nSymbol];

	if( nCurrentNode == -1 ) nCurrentNode = Tree.nLeaf[ESCAPE];

	while( nCurrentNode != ROOT_NODE ){
		if( !( nCurrentNode & 1 ) ) dwCode |= dwCurrentBit;
		dwCurrentBit <<= 1;
		nCodeSize++;
		nCurrentNode = Tree.nodes[nCurrentNode].nParent;
		};

	OutputBits( dwCode, nCodeSize );

	if( Tree.nLeaf[nSymbol] == -1 ){
		OutputBits( (DWORD) nSymbol, 8 );
		AddNewNode( nSymbol );
		}

}

void CHuffmanFile::AddNewNode( int nSymbol )
{
	int nLightestNode = Tree.nNextFreeNode - 1;
	int nNewNode = Tree.nNextFreeNode;
	int nZeroWeightNode = Tree.nNextFreeNode + 1;

	Tree.nNextFreeNode += 2;

	Tree.nodes[nNewNode] = Tree.nodes[nLightestNode];
	Tree.nodes[nNewNode].nParent = nLightestNode;
	Tree.nLeaf[Tree.nodes[nNewNode].nChild] = nNewNode;

	Tree.nodes[nLightestNode].nChild = nNewNode;
	Tree.nodes[nLightestNode].nChildIsLeaf = FALSE;

	Tree.nodes[nZeroWeightNode].nChild = nSymbol;
	Tree.nodes[nZeroWeightNode].nChildIsLeaf = TRUE;
	Tree.nodes[nZeroWeightNode].nWeight = 0;
	Tree.nodes[nZeroWeightNode].nParent = nLightestNode;
	Tree.nLeaf[nSymbol] = nZeroWeightNode;

}

int CHuffmanFile::DecodeSymbol( void )
{
	int nCurrentNode;
	int nSymbol;

	nCurrentNode = ROOT_NODE;

	while( !Tree.nodes[nCurrentNode].nChildIsLeaf ){
		nCurrentNode = Tree.nodes[nCurrentNode].nChild;
		nCurrentNode += (int) InputBit();
		}

	nSymbol = Tree.nodes[nCurrentNode].nChild;

	if( nSymbol == ESCAPE ){
		nSymbol = (int) InputBits( 8 );
		AddNewNode( nSymbol );
		}

	return( nSymbol );

}

void CHuffmanFile::RebuildTree( void )
{
	int i, j, k;
	unsigned int nWeight;

	j = Tree.nNextFreeNode - 1;
	for( i=j; i>=ROOT_NODE; i-- ){
		if( Tree.nodes[i].nChildIsLeaf ){
			Tree.nodes[j] = Tree.nodes[i];
			Tree.nodes[j].nWeight = ( Tree.nodes[j].nWeight + 1 ) >> 1;
			j--;
			}
		}

	for( i=Tree.nNextFreeNode-2; j>=ROOT_NODE; i-=2, j-- ){
		k = i + 1;
		Tree.nodes[j].nWeight = Tree.nodes[i].nWeight + Tree.nodes[k].nWeight;
		nWeight = Tree.nodes[j].nWeight;
		Tree.nodes[j].nChildIsLeaf = FALSE;
		for( k=j+1; nWeight<Tree.nodes[k].nWeight; k++ );
		k--;
		memmove( &Tree.nodes[j], &Tree.nodes[j+1], ( k - j ) * sizeof( struct node ) );
		Tree.nodes[k].nWeight = nWeight;
		Tree.nodes[k].nChild = i;
		Tree.nodes[k].nChildIsLeaf = FALSE;
		}

	for( i=Tree.nNextFreeNode-1; i>=ROOT_NODE; i-- ){
		if( Tree.nodes[i].nChildIsLeaf ){
			k = Tree.nodes[i].nChild;
			Tree.nLeaf[k] = i;
			}
		else{
			k = Tree.nodes[i].nChild;
			Tree.nodes[k].nParent = Tree.nodes[k+1].nParent = i;
			}
		}

}

void CHuffmanFile::SwapNodes( int i, int j )
{
	struct node temp;

	if( Tree.nodes[i].nChildIsLeaf ) Tree.nLeaf[Tree.nodes[i].nChild] = j;
	else{
		Tree.nodes[Tree.nodes[i].nChild].nParent = j;
		Tree.nodes[Tree.nodes[i].nChild+1].nParent = j;
		}

	if( Tree.nodes[j].nChildIsLeaf ) Tree.nLeaf[Tree.nodes[j].nChild] = i;
	else{
		Tree.nodes[Tree.nodes[j].nChild].nParent = i;
		Tree.nodes[Tree.nodes[j].nChild+1].nParent = i;
		}

	temp = Tree.nodes[i];
	Tree.nodes[i] = Tree.nodes[j];
	Tree.nodes[i].nParent = temp.nParent;
	temp.nParent = Tree.nodes[j].nParent;
	Tree.nodes[j] = temp;

}