vbf_lzwpersist.h

数据压缩的实例

// LzwFile.h: interface for the CLzwPersist class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_LZWFILE_H__20768C3D_D3CB_43DF_BD03_D195F2B75B3F__INCLUDED_)
#define AFX_LZWFILE_H__20768C3D_D3CB_43DF_BD03_D195F2B75B3F__INCLUDED_

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

#include "VBF_CompressedPersist.h"

// LZW Defines and structs
#ifdef END_OF_STREAM
#undef END_OF_STREAM
#endif
#define END_OF_STREAM 256
#ifdef UNUSED
#undef UNUSED
#endif
#define UNUSED -1

#define BITS 15
#define MAX_CODE 0x7fff
#define TABLE_SIZE 35023L
#define TABLE_BANKS ( ( TABLE_SIZE >> 8 ) + 1 )
#define BUMP_CODE 257
#define FLUSH_CODE 258
#define FIRST_CODE 259


typedef struct
{
	int nCodeValue;
	int nParentCode;
	char nCharacter;
} DICTIONARY;

#define DICT( i ) m_Dict[i>>8][i&0x00ff]

template <class TYPE> 
class CLzwPersist : public CCompressedPersist <TYPE> 
{
public:
	CLzwPersist();
	~CLzwPersist();

	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 );

	void InitializeDictionary( void );
	void AllocateStorage( void );
	void DeleteStorage( void );
	unsigned int FindChildNode( int, int );
	unsigned int DecodeString( unsigned int, unsigned int );

	DICTIONARY *m_Dict[TABLE_BANKS]; //double-dim pointer
	char m_cbDecodeStack[TABLE_SIZE];
	unsigned int m_nNextCode;
	int m_nCurrentCodeBits;
	unsigned int m_nNextBumpCode;
	BOOL m_bStorageAllocated;
	BOOL m_bStarted;
	int m_nCharacter, m_nStringCode, m_nIndex;
	int m_nNewCode, m_nOldCode;
	unsigned int m_nCount;
	int m_nEntryPoint;


};

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

	m_bStorageAllocated = FALSE;

}
template <class TYPE>

CLzwPersist<TYPE>::~CLzwPersist()
{
	DeleteStorage();
}

template <class TYPE>
BOOL CLzwPersist<TYPE>::Open( TYPE* pPersist, unsigned int nMode)
{
	m_nCompressionType = VBF_COMPRESS_LZW;
	m_bStarted = FALSE;
	for( long i=0; i<TABLE_SIZE; i++ )
		m_cbDecodeStack[i] = 0;

	m_nNextCode   = 0;
	m_nCurrentCodeBits = 0;
	m_nNextBumpCode    = 0;
	m_nCharacter  = 0;
	m_nEntryPoint = 0;
	m_nStringCode = 0;
	m_nIndex      = 0;
	m_nNewCode    = m_nOldCode = 0;
	m_nCount = 0;
	AllocateStorage();

	if( !m_bStorageAllocated) 
		return FALSE;

	InitializeDictionary();
	return( CCompressedPersist<TYPE>::Open( pPersist, nMode) );
}

template <class TYPE>
void CLzwPersist<TYPE>::Close( void )
{
	if( m_nMode != MODE_READ )
	{
		OutputBits( (DWORD) m_nStringCode, m_nCurrentCodeBits );
		OutputBits( (DWORD) END_OF_STREAM, m_nCurrentCodeBits );
	}
	CCompressedPersist<TYPE>::Close();
	if( m_bStorageAllocated ) DeleteStorage();		
}

template <class TYPE>
unsigned int CLzwPersist<TYPE>::Read( void far *lpBuf, unsigned int nCount )
{
	unsigned int  nBytesRead = 0;
	unsigned char *pTransfer;
	unsigned int  i = 0;

	pTransfer = (unsigned char *) lpBuf;

	if( m_nEntryPoint == 1 ) goto LZW_ENTRY1a;
	if( m_nEntryPoint == 2 ) goto LZW_ENTRY2a;

	for( ; ; )
	{
		m_nEntryPoint = 1;
		InitializeDictionary();
		m_nOldCode = (unsigned int) InputBits( m_nCurrentCodeBits );
		if( m_nOldCode == END_OF_STREAM ) return( nBytesRead );
		m_nCharacter = m_nOldCode;
		pTransfer[i++] = (unsigned char) m_nOldCode;
		if( i >= nCount ) return( nBytesRead );

LZW_ENTRY1a:
		m_nEntryPoint = 2;
		for( ; ; )
		{
			m_nNewCode = (unsigned int) InputBits( m_nCurrentCodeBits );
			if( m_nNewCode == END_OF_STREAM ) return( nBytesRead );
			if( m_nNewCode == FLUSH_CODE ) break;
			if( m_nNewCode == BUMP_CODE )
			{
				m_nCurrentCodeBits++;
				continue;
			}
			if( m_nNewCode >= (int) m_nNextCode )
			{
				m_cbDecodeStack[0] = (char) m_nCharacter;
				m_nCount = DecodeString( 1, m_nOldCode );
			}
			else m_nCount = DecodeString( 0, m_nNewCode );
			m_nCharacter = m_cbDecodeStack[m_nCount-1];
			while( m_nCount > 0 )
			{
				pTransfer[i++] = m_cbDecodeStack[--m_nCount];
				if( i >= nCount ) return( nBytesRead );
LZW_ENTRY2a:
;
			}
			DICT( m_nNextCode ).nParentCode = m_nOldCode;
			DICT( m_nNextCode ).nCharacter = (char) m_nCharacter;
			m_nNextCode++;
			m_nOldCode = m_nNewCode;
		}
	}

	return( nBytesRead);

}

template <class TYPE>
void CLzwPersist<TYPE>::Write( void *lpBuf, unsigned int nCount )
{
	unsigned char *pTransfer;
	unsigned int nStart = 0;

	pTransfer = (unsigned char *) lpBuf;
	m_dwUncompressedSize += (DWORD) nCount;

	if( !m_bStarted ){
		m_nStringCode = (int) pTransfer[nStart++];
		m_nStringCode &= 0x00ff;
		m_bStarted = TRUE;
		}

	for( unsigned int i=nStart; i<nCount; i++ ){
		m_nCharacter = (int) pTransfer[i];
		m_nCharacter &= 0x00ff;
		m_nIndex = FindChildNode( m_nStringCode, m_nCharacter );
		if( DICT( m_nIndex ).nCodeValue != -1 )
			m_nStringCode = DICT( m_nIndex ).nCodeValue;
		else
		{
			DICT( m_nIndex ).nCodeValue = m_nNextCode++;
			DICT( m_nIndex ).nParentCode = m_nStringCode;
			DICT( m_nIndex ).nCharacter = (char) m_nCharacter;
			OutputBits( (DWORD) m_nStringCode, m_nCurrentCodeBits );
			m_nStringCode = m_nCharacter;
			if( m_nNextCode > MAX_CODE ){
				OutputBits( (DWORD) FLUSH_CODE, m_nCurrentCodeBits );
				InitializeDictionary();
				}
			else if( m_nNextCode > m_nNextBumpCode )
			{
				OutputBits( (DWORD) BUMP_CODE, m_nCurrentCodeBits );
				m_nCurrentCodeBits++;
				m_nNextBumpCode <<= 1;
				m_nNextBumpCode |= 1;
			}
		}
	}

}

template <class TYPE>
void CLzwPersist<TYPE>::InitializeDictionary( void )
{
	unsigned int i;

	for( i=0; i<TABLE_SIZE; i++ ) 
		DICT( i ).nCodeValue = UNUSED;

	m_nNextCode = FIRST_CODE;
	m_nCurrentCodeBits = 9;
	m_nNextBumpCode = 511;

}

template <class TYPE>
void CLzwPersist<TYPE>::AllocateStorage( void )
{
	int i;

	if( m_bStorageAllocated ) DeleteStorage();

	for( i=0; i<TABLE_BANKS; i++ ) m_Dict[i] = NULL;

	for( i=0; i<TABLE_BANKS; i++)
	{
		m_Dict[i] = (DICTIONARY *) new DICTIONARY [256];
		if( !m_Dict[i] ) return;
		memset( m_Dict[i], 0, sizeof( DICTIONARY ) * 256 );
	}

	m_bStorageAllocated = TRUE;

}
template <class TYPE>

void CLzwPersist<TYPE>::DeleteStorage( void )
{
	int i;

	for( i=0; i<TABLE_BANKS; i++ )
	{
		if( m_Dict[i] ) delete [] m_Dict[i];
		m_Dict[i] = NULL;
	}

	m_bStorageAllocated = FALSE;

}

template <class TYPE>
unsigned int CLzwPersist<TYPE>::FindChildNode( int nParentNode, int nChildCharacter )
{
	unsigned int nIndex;
	int nOffset;

	nIndex = ( nChildCharacter << ( BITS - 8 ) ) ^ nParentNode;
	if( !nIndex ) nOffset = 1;
	else nOffset = (int) ( TABLE_SIZE - nIndex );

	for( ; ; )
	{
		if( DICT( nIndex ).nCodeValue == UNUSED)
			return( (unsigned int) nIndex );

		if( DICT( nIndex ).nParentCode == nParentNode &&
			DICT( nIndex).nCharacter == (char) nChildCharacter ) 
			return( (unsigned int) nIndex );
		
		if( nIndex >= (unsigned int) nOffset )
			nIndex -= (unsigned int) nOffset;
		else 
			nIndex += (unsigned int) ( TABLE_SIZE - nOffset );
	}

	return( 0 );

}

template <class TYPE>
unsigned int CLzwPersist<TYPE>::DecodeString( unsigned int nCount, unsigned int nCode )
{

	while( nCode > 255 )
	{
		m_cbDecodeStack[nCount++] = DICT( nCode ).nCharacter;
		nCode = DICT( nCode ).nParentCode;
	}

	m_cbDecodeStack[nCount++] = (char) nCode;

	return( nCount);

}


#endif // !defined(AFX_LZWFILE_H__20768C3D_D3CB_43DF_BD03_D195F2B75B3F__INCLUDED_)