vbf_huffmanpersist.h

数据压缩的实例

// HuffmanFile.h: interface for the CHuffmanPersist class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_HUFFMANFILE_H__7CDC1502_63B7_44C7_8D05_5DDFC0E956F2__INCLUDED_)
#define AFX_HUFFMANFILE_H__7CDC1502_63B7_44C7_8D05_5DDFC0E956F2__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "VBF_CompressedPersist.h"
// Huffman defines and structures follow...

#define SYMBOL_COUNT 258
#define NODE_TABLE_COUNT ( ( SYMBOL_COUNT * 2 ) - 1 )

#pragma pack(1)

typedef struct node
{
	unsigned int nWeight;
	int nParent;
	int nChildIsLeaf;
	int nChild;
} NODE;
	
typedef struct tree
{
	int nLeaf[SYMBOL_COUNT];
	int nNextFreeNode;
	struct node nodes[NODE_TABLE_COUNT];
} TREE;

#define ROOT_NODE 0
#define ESCAPE 257
#define MAX_WEIGHT 0x8000

#ifdef END_OF_STREAM
#undef END_OF_STREAM
#endif
#define END_OF_STREAM 256

template <class TYPE> 
class CHuffmanPersist : public CCompressedPersist <TYPE> 
{
public:
	CHuffmanPersist();
	virtual ~CHuffmanPersist();
public:
	virtual unsigned int Read( void far *, unsigned int );
	virtual void Write( void far *, unsigned int );

	virtual BOOL Open( TYPE* pPersist, unsigned int);
	virtual void Close( void );
	
private:
	void UpdateModel( int );
	void EncodeSymbol( unsigned int );
	void AddNewNode( int );
	int DecodeSymbol( void );
	void InitializeTree( void );
	void RebuildTree( void );
	void SwapNodes( int, int );

	TREE Tree;
};

template <class TYPE> 
CHuffmanPersist<TYPE>::CHuffmanPersist()
{

}
template <class TYPE> 

CHuffmanPersist<TYPE>::~CHuffmanPersist()
{

}
template <class TYPE> 
BOOL CHuffmanPersist<TYPE>::Open( TYPE* pPersist, unsigned int nMode )
{

	m_nCompressionType = VBF_COMPRESS_HUFF;
	InitializeTree();
	return( CCompressedPersist<TYPE>::Open( pPersist, nMode) );

}
template <class TYPE> 
void CHuffmanPersist<TYPE>::Close( void )
{

	if( m_nMode != MODE_READ ) EncodeSymbol( END_OF_STREAM );
	CCompressedPersist<TYPE>::Close();
		
}
template <class TYPE> 
unsigned int CHuffmanPersist<TYPE>::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 );

}

template <class TYPE> 
void CHuffmanPersist<TYPE>::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;

}

template <class TYPE> 
void CHuffmanPersist<TYPE>::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;

}

template <class TYPE> 
void CHuffmanPersist<TYPE>::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;
		}
		
}

template <class TYPE> 
void CHuffmanPersist<TYPE>::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 );
		}

}

template <class TYPE> 
void CHuffmanPersist<TYPE>::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;

}

template <class TYPE> 
int CHuffmanPersist<TYPE>::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 );

}

template <class TYPE> 
void CHuffmanPersist<TYPE>::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;
			}
		}

}

template <class TYPE> 
void CHuffmanPersist<TYPE>::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;

}


#endif // !defined(AFX_HUFFMANFILE_H__7CDC1502_63B7_44C7_8D05_5DDFC0E956F2__INCLUDED_)