417 lines
12 KiB
C++
417 lines
12 KiB
C++
// ==========================================================================
|
|
// Class Implementation : COXCompressor
|
|
// ==========================================================================
|
|
|
|
// Source file :compress.cpp
|
|
|
|
// Version: 9.3
|
|
|
|
// This software along with its related components, documentation and files ("The Libraries")
|
|
// is © 1994-2007 The Code Project (1612916 Ontario Limited) and use of The Libraries is
|
|
// governed by a software license agreement ("Agreement"). Copies of the Agreement are
|
|
// available at The Code Project (www.codeproject.com), as part of the package you downloaded
|
|
// to obtain this file, or directly from our office. For a copy of the license governing
|
|
// this software, you may contact us at legalaffairs@codeproject.com, or by calling 416-849-8900.
|
|
|
|
// //////////////////////////////////////////////////////////////////////////
|
|
|
|
#include "stdafx.h" // standard MFC include
|
|
#include "oxcompr.h" // class specification
|
|
#include "oxbitbuf.h"
|
|
#include "UTB64Bit.h"
|
|
|
|
#ifdef _DEBUG
|
|
#undef THIS_FILE
|
|
static char BASED_CODE THIS_FILE[] = __FILE__;
|
|
#endif
|
|
|
|
#ifndef WIN32
|
|
typedef unsigned char UCHAR;
|
|
#endif
|
|
|
|
IMPLEMENT_DYNAMIC(COXCompressor, CObject)
|
|
|
|
#define new DEBUG_NEW
|
|
|
|
/////////////////////////////////////////////////////////////////////////////
|
|
// Definition of static members
|
|
|
|
|
|
// Data members -------------------------------------------------------------
|
|
// protected:
|
|
|
|
// private:
|
|
|
|
|
|
|
|
// Member functions ---------------------------------------------------------
|
|
// public:
|
|
|
|
COXCompressor::COXCompressor()
|
|
{
|
|
TRY
|
|
{
|
|
m_window = new unsigned char[WINDOW_SIZE];
|
|
}
|
|
CATCH(CMemoryException, e)
|
|
{
|
|
TRACE(_T("COXCompressor::COXCompressor : Memory allocation not succeeded !!"));
|
|
THROW_LAST();
|
|
}
|
|
END_CATCH
|
|
|
|
memset(&m_window[0],0,WINDOW_SIZE);
|
|
}
|
|
|
|
COXCompressor::~COXCompressor()
|
|
{
|
|
delete [] m_window;
|
|
}
|
|
|
|
|
|
int COXCompressor::Compress(const LPBYTE pInBuffer, int nInLength,
|
|
LPBYTE pOutBuffer, int nMaxOutLength)
|
|
/*
|
|
* This is the compression routine. It has to first load up the look
|
|
* ahead buffer, then go into the main compression loop. The main loop
|
|
* decides whether to output a single character or an index/length
|
|
* token that defines a phrase. Once the character or phrase has been
|
|
* sent out, another loop has to run. The second loop reads in new
|
|
* characters, deletes the strings that are overwritten by the new
|
|
* character, then adds the strings that are created by the new
|
|
* character.
|
|
*/
|
|
{
|
|
ASSERT ( pInBuffer != NULL );
|
|
ASSERT ( AfxIsValidAddress(pOutBuffer,nMaxOutLength) );
|
|
if (nInLength == 0)
|
|
{
|
|
pOutBuffer = NULL;
|
|
return 0;
|
|
}
|
|
|
|
int i;
|
|
int look_ahead_bytes;
|
|
int current_position;
|
|
int replace_count;
|
|
int match_length;
|
|
int match_position;
|
|
int counter = 0;
|
|
LPBYTE pIterateInBuffer = pInBuffer;
|
|
|
|
|
|
COXBitBuffer bitBuffer(pOutBuffer);
|
|
|
|
current_position = 1;
|
|
for ( i = 0 ; i < LOOK_AHEAD_SIZE ; i++ )
|
|
{
|
|
if ( i >= nInLength || (bitBuffer.GetCompressedLength() > nMaxOutLength) )
|
|
break;
|
|
m_window[current_position + i ] = *pIterateInBuffer++;
|
|
counter++;
|
|
}
|
|
|
|
look_ahead_bytes = i;
|
|
InitTree( current_position );
|
|
match_length = 0;
|
|
match_position = 0;
|
|
while ( look_ahead_bytes > 0 )
|
|
{
|
|
if ( match_length > look_ahead_bytes )
|
|
match_length = look_ahead_bytes;
|
|
|
|
if ( match_length <= BREAK_EVEN )
|
|
{
|
|
replace_count = 1;
|
|
bitBuffer.OutputBit( 1 );
|
|
bitBuffer.OutputBits( (unsigned long) m_window[ current_position ], 8 );
|
|
}
|
|
else
|
|
{
|
|
bitBuffer.OutputBit( 0 );
|
|
bitBuffer.OutputBits( (unsigned long) match_position, INDEX_BIT_COUNT );
|
|
bitBuffer.OutputBits( (unsigned long) ( match_length - ( BREAK_EVEN + 1 ) ),
|
|
LENGTH_BIT_COUNT );
|
|
replace_count = match_length;
|
|
}
|
|
|
|
if (bitBuffer.GetCompressedLength() >= nMaxOutLength)
|
|
return -1;
|
|
|
|
for ( i = 0 ; i < replace_count ; i++ )
|
|
{
|
|
DeleteString( MOD_WINDOW( current_position + LOOK_AHEAD_SIZE ) );
|
|
|
|
if ( counter >= nInLength )
|
|
look_ahead_bytes--;
|
|
else
|
|
{
|
|
m_window[ MOD_WINDOW( current_position + LOOK_AHEAD_SIZE ) ]
|
|
= (unsigned char) *pIterateInBuffer;
|
|
pIterateInBuffer++;
|
|
counter++;
|
|
}
|
|
current_position = MOD_WINDOW( current_position + 1 );
|
|
if (look_ahead_bytes)
|
|
match_length=AddString(current_position,&match_position);
|
|
}
|
|
};
|
|
|
|
bitBuffer.OutputBit( 0 );
|
|
bitBuffer.OutputBitsEOS( );
|
|
|
|
return (bitBuffer.GetCompressedLength() >= nMaxOutLength ? -1 :
|
|
bitBuffer.GetCompressedLength() );
|
|
}
|
|
|
|
|
|
int COXCompressor::Expand(const LPBYTE pInBuffer, int nInLength, LPBYTE pOutBuffer,
|
|
int nMaxOutLength)
|
|
/*
|
|
* This is the expansion routine for the LZSS algorithm. All it has
|
|
* to do is read in flag bits, decide whether to read in a character or
|
|
* a index/length pair, and take the appropriate action.
|
|
*/
|
|
{
|
|
ASSERT ( pInBuffer != NULL );
|
|
ASSERT ( AfxIsValidAddress(pOutBuffer,nMaxOutLength) );
|
|
ASSERT ( nInLength != 0 );
|
|
int i;
|
|
int current_position;
|
|
int c;
|
|
int match_length;
|
|
int match_position;
|
|
COXBitBuffer bitBuffer( pInBuffer, nInLength );
|
|
LPBYTE pRefOutBuffer = pOutBuffer;
|
|
for (int counter = 0; counter < nMaxOutLength; counter++)
|
|
pOutBuffer[counter] = 0;
|
|
|
|
current_position = 1;
|
|
for ( ; ; )
|
|
{
|
|
if ( bitBuffer.InputBit( ) )
|
|
{
|
|
c = (int) bitBuffer.InputBits( 8 );
|
|
*pOutBuffer = (UCHAR)c;
|
|
pOutBuffer++;
|
|
if ( (pOutBuffer - pRefOutBuffer) > nMaxOutLength)
|
|
return -1;
|
|
|
|
m_window[ current_position ] = (unsigned char) c;
|
|
current_position = MOD_WINDOW( current_position + 1 );
|
|
}
|
|
else
|
|
{
|
|
match_position = (int) bitBuffer.InputBits( INDEX_BIT_COUNT );
|
|
if ( match_position == END_OF_STREAM
|
|
&& bitBuffer.GetCompressedLength() == nInLength )
|
|
break;
|
|
|
|
ASSERT( bitBuffer.GetCompressedLength() <= nInLength );
|
|
match_length = (int) bitBuffer.InputBits( LENGTH_BIT_COUNT );
|
|
match_length += BREAK_EVEN;
|
|
for ( i = 0 ; i <= match_length ; i++ )
|
|
{
|
|
c = m_window[ MOD_WINDOW( match_position + i ) ];
|
|
*pOutBuffer = (UCHAR)c;
|
|
pOutBuffer++;
|
|
if ( (pOutBuffer - pRefOutBuffer) > nMaxOutLength)
|
|
return -1;
|
|
|
|
m_window[ current_position ] = (unsigned char) c;
|
|
current_position = MOD_WINDOW( current_position + 1 );
|
|
}
|
|
}
|
|
}
|
|
|
|
return PtrToInt(pOutBuffer - pRefOutBuffer);
|
|
}
|
|
|
|
#ifdef _DEBUG
|
|
void COXCompressor::Dump(CDumpContext& dc) const
|
|
{
|
|
CObject::Dump(dc);
|
|
}
|
|
|
|
void COXCompressor::AssertValid() const
|
|
{
|
|
CObject::AssertValid();
|
|
}
|
|
#endif
|
|
|
|
// protected:
|
|
|
|
void COXCompressor::InitTree( int r )
|
|
// --- In : r eshtablishing a root node for the tree
|
|
// --- Out :
|
|
// --- Returns :
|
|
// --- Effect : initialization of the entire tree to value NOT_USED (0),
|
|
// which is good, since 0 is the NOT_USED code.
|
|
{
|
|
for ( int counter = 0; counter < TREE_SIZE; counter++)
|
|
m_tree[ counter ].parent =
|
|
m_tree[ counter ].larger_child =
|
|
m_tree[ counter ].smaller_child = NOT_USED;
|
|
|
|
m_tree[ TREE_ROOT ].larger_child = r;
|
|
m_tree[ r ].parent = TREE_ROOT;
|
|
m_tree[ r ].larger_child = NOT_USED;
|
|
m_tree[ r ].smaller_child = NOT_USED;
|
|
}
|
|
|
|
void COXCompressor::ContractNode( int old_node, int new_node )
|
|
// --- In : old_node : node to be removed
|
|
// new_node : replacing node, child of the old node
|
|
// --- Out :
|
|
// --- Returns :
|
|
// --- Effect : This routine is used when a node is being deleted. The link to
|
|
// its descendant is broken by pulling the descendant in to overlay
|
|
// the existing link.
|
|
{
|
|
m_tree[ new_node ].parent = m_tree[ old_node ].parent;
|
|
if ( m_tree[ m_tree[ old_node ].parent ].larger_child == old_node )
|
|
m_tree[ m_tree[ old_node ].parent ].larger_child = new_node;
|
|
else
|
|
m_tree[ m_tree[ old_node ].parent ].smaller_child = new_node;
|
|
|
|
m_tree[ old_node ].parent = NOT_USED;
|
|
}
|
|
|
|
void COXCompressor::ReplaceNode( int old_node, int new_node )
|
|
// --- In : old_node : node to be removed
|
|
// new_node : replacing node, the next smaller node in the list
|
|
// --- Out :
|
|
// --- Returns :
|
|
// --- Effect : This routine is also used when a node is being deleted. However,
|
|
// in this case, it is being replaced by a node that was not previously
|
|
// in the tree.
|
|
{
|
|
int parent;
|
|
|
|
parent = m_tree[ old_node ].parent;
|
|
if ( m_tree[ parent ].smaller_child == old_node )
|
|
m_tree[ parent ].smaller_child = new_node;
|
|
else
|
|
m_tree[ parent ].larger_child = new_node;
|
|
m_tree[ new_node ] = m_tree[ old_node ];
|
|
m_tree[ m_tree[ new_node ].smaller_child ].parent = new_node;
|
|
m_tree[ m_tree[ new_node ].larger_child ].parent = new_node;
|
|
m_tree[ old_node ].parent = NOT_USED;
|
|
}
|
|
|
|
int COXCompressor::FindNextNode( int node )
|
|
// --- In : node : node being searched from
|
|
// --- Out :
|
|
// --- Returns : next smaller node
|
|
// --- Effect : This routine is used to find the next smallest node after the node
|
|
// argument. It assumes that the node has a smaller child. We find
|
|
// the next smallest child by going to the smaller_child node, then
|
|
// going to the end of the larger_child descendant chain.
|
|
{
|
|
int next;
|
|
|
|
next = m_tree[ node ].smaller_child;
|
|
while ( m_tree[ next ].larger_child != NOT_USED )
|
|
next = m_tree[ next ].larger_child;
|
|
|
|
return( next );
|
|
}
|
|
|
|
|
|
void COXCompressor::DeleteString( int p )
|
|
// --- In : p : node to be deleted
|
|
// --- Out :
|
|
// --- Returns :
|
|
// --- Effect : This routine performs the classic binary tree deletion algorithm.
|
|
// If the node to be deleted has a null link in either direction, we
|
|
// just pull the non-null link up one to replace the existing link.
|
|
// If both links exist, we instead delete the next link in order, which
|
|
// is guaranteed to have a null link, then replace the node to be deleted
|
|
// with the next link.
|
|
{
|
|
int replacement;
|
|
if ( m_tree[ p ].parent == NOT_USED )
|
|
return;
|
|
|
|
if ( m_tree[ p ].larger_child == NOT_USED )
|
|
ContractNode( p, m_tree[ p ].smaller_child );
|
|
else if ( m_tree[ p ].smaller_child == NOT_USED )
|
|
ContractNode( p, m_tree[ p ].larger_child );
|
|
else
|
|
{
|
|
replacement = FindNextNode( p );
|
|
DeleteString( replacement );
|
|
ReplaceNode( p, replacement );
|
|
}
|
|
}
|
|
|
|
int COXCompressor::AddString( int new_node, int* match_position )
|
|
// --- In : new_node : new node to be added
|
|
// match_position : tracking the string currently in the tree that best
|
|
// matches the one inserted
|
|
// --- Out :
|
|
// --- Returns : match_length : the length of the matched string
|
|
// --- Effect : This where most of the work done by the encoder takes place. This
|
|
// routine is responsible for adding the new node to the binary tree.
|
|
// It also has to find the best match among all the existing nodes in
|
|
// the tree, and return that to the calling routine. To make matters
|
|
// even more complicated, if the new_node has a duplicate in the tree,
|
|
// the old_node is deleted, for reasons of efficiency.
|
|
{
|
|
int i;
|
|
int test_node;
|
|
int match_length;
|
|
int *child;
|
|
int delta=0;
|
|
|
|
if ( new_node == END_OF_STREAM )
|
|
return( 0 );
|
|
|
|
test_node = m_tree[ TREE_ROOT ].larger_child;
|
|
match_length = 0;
|
|
for ( ; ; )
|
|
{
|
|
for ( i = 0 ; i < LOOK_AHEAD_SIZE ; i++ )
|
|
{
|
|
delta = m_window[MOD_WINDOW( new_node + i ) ] -
|
|
m_window[ MOD_WINDOW( test_node + i ) ];
|
|
if ( delta != 0 )
|
|
break;
|
|
}
|
|
|
|
if ( i >= match_length )
|
|
{
|
|
match_length = i;
|
|
*match_position = test_node;
|
|
if ( match_length >= LOOK_AHEAD_SIZE )
|
|
{
|
|
ReplaceNode( test_node, new_node );
|
|
return( match_length );
|
|
}
|
|
}
|
|
|
|
if ( delta >= 0 )
|
|
child = &m_tree[ test_node ].larger_child;
|
|
else
|
|
child = &m_tree[ test_node ].smaller_child;
|
|
|
|
if ( *child == NOT_USED )
|
|
{
|
|
*child = new_node;
|
|
m_tree[ new_node ].parent = test_node;
|
|
m_tree[ new_node ].larger_child = NOT_USED;
|
|
m_tree[ new_node ].smaller_child = NOT_USED;
|
|
|
|
return( match_length );
|
|
}
|
|
|
|
test_node = *child;
|
|
}
|
|
}
|
|
|
|
// private:
|
|
|
|
// Message handlers ---------------------------------------------------------
|
|
|
|
// ==========================================================================
|