lzw.cpp

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

// Lzw.cpp

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

#define END_OF_STREAM 256
#ifdef UNUSED
#undef UNUSED
#endif
#define UNUSED -1

CLzwFile::CLzwFile()
{

	m_bStorageAllocated = FALSE;

}

CLzwFile::~CLzwFile()
{

	DeleteStorage();

}

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

	m_nCompressionType = 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( CCompressedFile::Open( pszFileName, nOpenFlags, pError ) );

}

void CLzwFile::Close( void )
{

	if( m_nFlags != CFile::modeRead ){
		OutputBits( (DWORD) m_nStringCode, m_nCurrentCodeBits );
		OutputBits( (DWORD) END_OF_STREAM, m_nCurrentCodeBits );
		}
	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 CLzwFile::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);

}

void CLzwFile::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;
				}
			}
		}

}

void CLzwFile::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;

}

void CLzwFile::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;

}

void CLzwFile::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;

}

unsigned int CLzwFile::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 );

}

unsigned int CLzwFile::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);

}