lzss.cpp

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

// Lzss.cpp

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

#define END_OF_STREAM 0
#ifdef UNUSED
#undef UNUSED
#endif
#define UNUSED 0

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

	memset( ucWindow, 0, WINDOW_SIZE );
	m_pExtraBuffer = (unsigned char *) new unsigned char [16000];
	m_dwExtra = 0;
	m_nCompressionType = LZSS;
	m_bInitialized = FALSE;
	m_nStoreLookAhead = 0;
	m_dwPointer = 0L;
	m_nCurrentPosition = 1;
	return( CCompressedFile::Open( pszFileName, nOpenFlags, pError ) );

}

void CLzssFile::Close( void )
{

	if( m_pExtraBuffer != NULL ) delete [] m_pExtraBuffer;
	m_pExtraBuffer = NULL;

	if( m_nFlags != CFile::modeRead ){
		OutputBit( 0 );
		OutputBits( (DWORD) END_OF_STREAM, INDEX_BIT_COUNT );
		}

	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 CLzssFile::Read( void far *lpBuf, unsigned int nCount )
{
	unsigned char *pTransfer;
	unsigned int nBytesRead = 0;
	int c;

	pTransfer = (unsigned char *) lpBuf;
	m_dwPointer = 0L;
	m_nCurrentPosition = 1;
	
	while( m_dwExtra && m_dwPointer < (DWORD) nCount ){
		pTransfer[m_dwPointer++] = m_pExtraBuffer[m_dwExtraPointer];
		m_dwExtraPointer++;
		m_dwExtra--;
		nBytesRead++;
		}

	for ( ; ; ){
		if( InputBit() ){
			c = (int) InputBits( 8 );
			pTransfer[m_dwPointer++] = (unsigned char) c;
			ucWindow[m_nCurrentPosition] = (unsigned char) c;
			m_nCurrentPosition = MOD_WINDOW( m_nCurrentPosition + 1 );
			nBytesRead++;
			}
		else{
			m_nMatchPosition = (int) InputBits( INDEX_BIT_COUNT );
			if( m_nMatchPosition == END_OF_STREAM ) break;
			m_nMatchLength = (int) InputBits( LENGTH_BIT_COUNT );
			m_nMatchLength += BREAK_EVEN;
			m_dwExtraPointer = 0L;
			for( int i=0; i<=m_nMatchLength; i++ ){
				c = (int) ucWindow[MOD_WINDOW(m_nMatchPosition+i)];
				if( m_dwPointer < (DWORD) nCount ){
					nBytesRead++;
					pTransfer[m_dwPointer++] = (unsigned char) c;
					}
				else if( m_pExtraBuffer ){
					m_pExtraBuffer[m_dwExtra++] = (unsigned char) c;
					}
				ucWindow[m_nCurrentPosition] = (unsigned char) c;
				m_nCurrentPosition = MOD_WINDOW( m_nCurrentPosition + 1 );
				}
			}
		if( m_dwPointer >= (DWORD) nCount ) break;
		}

	return( nBytesRead );

}

void CLzssFile::Write( void *lpBuf, unsigned int nCount )
{

	m_dwBytesToEncode = (DWORD) nCount;
	m_dwPointer = 0L;
	EncodeSymbols( (unsigned char *) lpBuf );
	m_dwUncompressedSize += (DWORD) nCount;

}

void CLzssFile::EncodeSymbols( unsigned char *lpBuf, BOOL bEndFlag )
{
	int i, c;

	if( !m_bInitialized ){
		while( m_nStoreLookAhead < LOOK_AHEAD_SIZE && !bEndFlag && m_dwBytesToEncode ){
			ucWindow[++m_nStoreLookAhead] = lpBuf[m_dwPointer++];
			m_dwBytesToEncode--;
			}
		if( !bEndFlag && m_nStoreLookAhead < LOOK_AHEAD_SIZE ) return;
		m_nLookAheadBytes = m_nStoreLookAhead;
		InitializeTree();
		m_nMatchLength = m_nMatchPosition = 0;
		m_bInitialized = 1;
		}

	if( m_bInitialized == 2 ) goto LZSSEntry;

	m_bInitialized = 2;
	while( m_nLookAheadBytes > 0 ){
		if( m_nMatchLength > m_nLookAheadBytes ) m_nMatchLength = m_nLookAheadBytes;
		if( m_nMatchLength <= BREAK_EVEN ){
			m_nReplaceCount = 1;
			OutputBit( 1 );
			OutputBits( (DWORD) ucWindow[m_nCurrentPosition], 8 );
			}
		else{
			OutputBit( 0 );
			OutputBits( (DWORD) m_nMatchPosition, INDEX_BIT_COUNT );
			OutputBits( (DWORD) ( m_nMatchLength - ( BREAK_EVEN + 1 ) ), LENGTH_BIT_COUNT );
			m_nReplaceCount = m_nMatchLength;
			}
		for( i=0; i<m_nReplaceCount; i++ ){
			DeleteString( MOD_WINDOW( m_nCurrentPosition + LOOK_AHEAD_SIZE ) );

LZSSEntry:
			if( m_dwBytesToEncode ){
				c = (int) lpBuf[m_dwPointer++], m_dwBytesToEncode--;
				ucWindow[MOD_WINDOW(m_nCurrentPosition+LOOK_AHEAD_SIZE)] = (unsigned char) c;
				}
			else m_nLookAheadBytes--;
			m_nCurrentPosition = MOD_WINDOW( m_nCurrentPosition + 1 );
			if( m_nLookAheadBytes ) m_nMatchLength = AddString( m_nCurrentPosition, &m_nMatchPosition );
			}
		}

}

void CLzssFile::InitializeTree( void )
{

	for( int i=0; i<WINDOW_SIZE+1; i++ ) memset ( &Tree[i], 0, sizeof( LZSS_TREE ) );

	Tree[TREE_ROOT].nLargerChild = 1;
	Tree[1].nParent = TREE_ROOT;
	Tree[1].nLargerChild = UNUSED;
	Tree[1].nSmallerChild = UNUSED;

}

void CLzssFile::ContractNode( int nOldNode, int nNewNode )
{

	Tree[nNewNode].nParent = Tree[nOldNode].nParent;
	if( Tree[Tree[nOldNode].nParent].nLargerChild == nOldNode ) Tree[Tree[nOldNode].nParent].nLargerChild = nNewNode;
	else Tree[Tree[nOldNode].nParent].nSmallerChild = nNewNode;
	Tree[nOldNode].nParent = UNUSED;

}

void CLzssFile::ReplaceNode( int nOldNode, int nNewNode )
{
	int nParent;

	nParent = Tree[nOldNode].nParent;
	if( Tree[nParent].nSmallerChild == nOldNode ) Tree[nParent].nSmallerChild = nNewNode;
	else Tree[nParent].nLargerChild = nNewNode;
	Tree[nNewNode] = Tree[nOldNode];
	Tree[Tree[nNewNode].nSmallerChild].nParent = nNewNode;
	Tree[Tree[nNewNode].nLargerChild].nParent = nNewNode;
	Tree[nOldNode].nParent = UNUSED;

}

int CLzssFile::FindNextNode( int nNode )
{
	int nNext;

	nNext = Tree[nNode].nSmallerChild;

	while( Tree[nNext].nLargerChild != UNUSED ) nNext = Tree[nNext].nLargerChild;

	return( nNext );

}

void CLzssFile::DeleteString( int p )
{
	int nReplacement;

	if( Tree[p].nParent == UNUSED ) return;

	if( Tree[p].nLargerChild == UNUSED ) ContractNode( p, Tree[p].nSmallerChild );
	else if( Tree[p].nSmallerChild == UNUSED ) ContractNode( p, Tree[p].nLargerChild );
	else{
		nReplacement = FindNextNode( p );
		DeleteString( nReplacement );
		ReplaceNode( p, nReplacement );
		}

}

int CLzssFile::AddString( int nNewNode, int *pnMatchPosition )
{
	int i;
	int nDelta;
	int nMatchLength;
	int *pnChild;
	int nTestNode;
	
	if( nNewNode == END_OF_STREAM ) return( 0 );

	nTestNode = Tree[TREE_ROOT].nLargerChild;
	nMatchLength = 0;
	for( ; ; ){
		for( i=0; i<LOOK_AHEAD_SIZE; i++ ){
			nDelta = ucWindow[MOD_WINDOW(nNewNode+i)] - ucWindow[MOD_WINDOW(nTestNode+i)];
			if( nDelta ) break;
			}
		if( i >= nMatchLength ){
			nMatchLength = i;
			*pnMatchPosition = nTestNode;
			if( nMatchLength >= LOOK_AHEAD_SIZE ){
				ReplaceNode( nTestNode, nNewNode );
				return( nMatchLength );
				}
			}
		if( nDelta >= 0 ) pnChild = &Tree[nTestNode].nLargerChild;
		else pnChild = &Tree[nTestNode].nSmallerChild;
		if( *pnChild == UNUSED ){
			*pnChild = nNewNode;
			Tree[nNewNode].nParent = nTestNode;
			Tree[nNewNode].nLargerChild = UNUSED;
			Tree[nNewNode].nSmallerChild = UNUSED;
			return( nMatchLength );
			}
		nTestNode = *pnChild;
		}

	return( 0 );

}