ahuff.c

数据压缩Huffman算法

/*

two different final applications:
	archiver: mem use don't matter; speed is critical
	balrog  : mem use is critical; speed must be better than Arith

*/

/*

todo : 
	
	1. allow weights of 1 to be scaled to 0 and dropped out

*/

#include <simple/gen.h>
#include <simple/exec.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>	
#include <crb/memutil.h>
#include <crb/bitio.h>

#define ESCAPE            AHI->NumSymbols
#define SYMBOL_COUNT      (AHI->NumSymbols+1)
#define NODE_TABLE_COUNT  ( ( SYMBOL_COUNT * 2 ) - 1 )
#define ROOT_NODE         0
#define NODE_NONE					0xFFFF
#define MAX_WEIGHT 				0x8000

/*
 * This data structure is all that is needed to maintain an adaptive
 * Huffman tree for both encoding and decoding.  The leaf array is a
 * set of indices into the nodes that indicate which node is the
 * parent of a symbol.  For example, to encode 'A', we would find the
 * leaf node by way of leaf[ 'A' ].  The next_free_node index is used
 * to tell which node is the next one in the array that can be used.
 * Since nodes are allocated when characters are read in for the first
 * time, this pointer keeps track of where we are in the node array.
 * Finally, the array of nodes is the actual Huffman tree.  The child
 * index is either an index pointing to a pair of children, or an
 * actual symbol value, depending on whether 'child_is_leaf' is 1
 * or 0.
 */

struct AHuffNode
	{
  uword parent;
  uword child;
	uword weight;
  ubyte child_is_leaf; /* could merge this flag in with child */
  };

struct AHuffTree
	{
	uword next_free_node;
	uword * leaf; /* SYMBOL_COUNT of them */
		/* must be uword cuz of ESCAPE :^( */
  struct AHuffNode * nodes; /* NODE_TABLE_COUNT of them */
	}; /* 4105 bytes */

struct AHuffInfo
	{
	uword NumSymbols;
	struct BitIOInfo * BII;
	struct AHuffTree * Tree;
	};

/* externally available protos: */
struct AHuffInfo * AHuff_Init(struct BitIOInfo * inBII,long inNumSymbols);
void AHuff_CleanUp(struct AHuffInfo *AHI);
void __regargs __inline AHuff_EncodeC(struct AHuffInfo *AHI,long c);
long AHuff_DecodeC( struct AHuffInfo *AHI );
void AHuff_UpdateModel( struct AHuffInfo *AHI , long c );
void AHuff_InitializeTree( struct AHuffInfo *AHI );
void AHuff_HalveTree( struct AHuffInfo *AHI );

/* macro protos:

void swap_nodes( struct AHuffTree *Tree, long i, long j );
void add_new_node( struct AHuffTree *Tree, long c );
void AHuff_UpdateModel_Macro( struct AHuffInfo *AHI, struct AHuffTree *Tree, long c );

*/

//global workspace for macros:
struct AHuffNode TempNode;
long lightest_node,new_node,zero_weight_node,current_node;

/* macros: */
#define swap_nodes(Tree,i,j )                                              \
if ( Tree->nodes[ i ].child_is_leaf )                                      \
  Tree->leaf[ Tree->nodes[ i ].child ] = j;                                \
else                                                                       \
	{                                                                        \
  Tree->nodes[ Tree->nodes[ i ].child ].parent = j;                        \
  Tree->nodes[ Tree->nodes[ i ].child + 1 ].parent = j;                    \
	}                                                                        \
if ( Tree->nodes[ j ].child_is_leaf )                                      \
  Tree->leaf[ Tree->nodes[ j ].child ] = i;                                \
else                                                                       \
	{                                                                        \
  Tree->nodes[ Tree->nodes[ j ].child ].parent = i;                        \
  Tree->nodes[ Tree->nodes[ j ].child + 1 ].parent = i;                    \
	}                                                                        \
TempNode = Tree->nodes[ i ];                                               \
Tree->nodes[ i ] = Tree->nodes[ j ];                                       \
Tree->nodes[ i ].parent = TempNode.parent;                                 \
TempNode.parent = Tree->nodes[ j ].parent;                                 \
Tree->nodes[ j ] = TempNode;                                               \
/* end swap_nodes macro */

/*
 * Adding a new node to the Tree is pretty simple.  It is just a matter
 * of splitting the lightest-weight node in the Tree, which is the highest
 * valued node.  We split it off into two new nodes, one of which is the
 * one being added to the Tree.  We assign the new node a weight of 0,
 * so the Tree doesn't have to be adjusted.  It will be updated later when
 * the normal update process occurs.  Note that this code assumes that
 * the lightest node has a leaf as a child.  If this is not the case,
 * the Tree would be broken.
 */
#define add_new_node( Tree, c )                                       		 \
lightest_node = Tree->next_free_node - 1;                                  \
new_node = Tree->next_free_node;                                           \
zero_weight_node = Tree->next_free_node + 1;                               \
Tree->next_free_node += 2;                                                 \
                                                                           \
Tree->nodes[ new_node ] = Tree->nodes[ lightest_node ];                    \
Tree->nodes[ new_node ].parent = lightest_node;                            \
Tree->leaf[ Tree->nodes[ new_node ].child ] = new_node;                    \
                                                                           \
Tree->nodes[ lightest_node ].child         = new_node;                     \
Tree->nodes[ lightest_node ].child_is_leaf = 0;                            \
                                                                           \
Tree->nodes[ zero_weight_node ].child           = c;                       \
Tree->nodes[ zero_weight_node ].child_is_leaf   = 1;                       \
Tree->nodes[ zero_weight_node ].weight          = 0;                       \
Tree->nodes[ zero_weight_node ].parent          = lightest_node;           \
Tree->leaf[ c ] = zero_weight_node;                                        \
/* end add_new_node macro */

/*
 * AHuff_UpdateModel is called to increment the count for a given symbol.
 * After incrementing the symbol, this code has to work its way up
 * through the parent nodes, incrementing each one of them.  That is
 * the easy part.  The hard part is that after incrementing each
 * parent node, we have to check to see if it is now out of the proper
 * order.  If it is, it has to be moved up the Tree into its proper
 * place.
 */
#define AHuff_UpdateModel_Macro( AHI, Tree, c )                            \
if ( Tree->nodes[ ROOT_NODE].weight == MAX_WEIGHT )                        \
  AHuff_HalveTree( AHI );                                                  \
current_node = Tree->leaf[ c ];                                            \
while ( current_node != ROOT_NODE )                                        \
	{                                                                        \
  Tree->nodes[ current_node ].weight++;                                    \
  for ( new_node = current_node ; new_node > ROOT_NODE ; new_node-- )      \
    if ( Tree->nodes[ new_node - 1 ].weight >=                             \
         Tree->nodes[ current_node ].weight )                              \
      break;                                                               \
  if ( current_node != new_node )                                          \
		{                                                                      \
    swap_nodes( Tree, current_node, new_node );                            \
    current_node = new_node;                                               \
  	}                                                                      \
  current_node = Tree->nodes[ current_node ].parent;                       \
	}                                                                        \
Tree->nodes[ current_node ].weight++;                                      \
/* end AHuff_UpdateModel macro */


/*
 * The high level view of the compression routine is very simple.
 * First, we initialize the Huffman Tree, with just the ESCAPE symbol.  
 * Then, we sit in a loop, encoding symbols,
 * and adding them to the model.
 *
 */

struct AHuffInfo * AHuff_Init(struct BitIOInfo * inBII,long inNumSymbols)
{
struct AHuffInfo * AHI;

if ( (AHI = AllocMem(sizeof(struct AHuffInfo),MEMF_ANY|MEMF_CLEAR)) == NULL )
	return(NULL);

AHI->BII = inBII;
AHI->NumSymbols = inNumSymbols;

if ( (AHI->Tree = AllocMem(sizeof(struct AHuffTree),MEMF_ANY|MEMF_CLEAR)) == NULL )
	{
	AHuff_CleanUp(AHI);
	return(NULL);
	}

if ( (AHI->Tree->leaf = AllocMem(SYMBOL_COUNT*sizeof(uword),MEMF_ANY)) == NULL )
	{
	AHuff_CleanUp(AHI);
	return(NULL);
	}

if ( (AHI->Tree->nodes = AllocMem(sizeof(struct AHuffNode)*NODE_TABLE_COUNT,MEMF_ANY)) == NULL )
	{
	AHuff_CleanUp(AHI);
	return(NULL);
	}

AHuff_InitializeTree( AHI );

return(AHI);
}

void AHuff_CleanUp(struct AHuffInfo *AHI)
{
if ( AHI )
	{
	if ( AHI->Tree )
		{
		SmartFree(AHI->Tree->leaf,SYMBOL_COUNT*sizeof(uword));
		SmartFree(AHI->Tree->nodes,sizeof(struct AHuffNode)*NODE_TABLE_COUNT);
		FreeMem(AHI->Tree,sizeof(struct AHuffTree));
		}
	FreeMem(AHI,sizeof(struct AHuffInfo));
	}
}

/*
 * When performing adaptive compression, the Huffman Tree starts out
 * very nearly empty.  The only symbol present initially is the
 * ESCAPE symbol.  The ESCAPE symbol has to
 * be included so we can tell the expansion prog that we are transmitting a
 * previously unseen symbol.