ahuff.c

数据压缩Huffman算法

 *
 * In addition to setting up the root node and its two children, this
 * routine also initializes the leaf array.
 */

void AHuff_InitializeTree( struct AHuffInfo * AHI )
{
long i;
struct AHuffTree * Tree;

Tree = AHI->Tree;

Tree->nodes[ ROOT_NODE ].child         = ESCAPE;
Tree->nodes[ ROOT_NODE ].child_is_leaf = 1;
Tree->nodes[ ROOT_NODE ].weight        = 1;
Tree->nodes[ ROOT_NODE ].parent        = NODE_NONE;
Tree->leaf[ ESCAPE ]                   = ROOT_NODE;
Tree->next_free_node                   = ROOT_NODE + 1;

for ( i = 0 ; i < AHI->NumSymbols ; i++ )
  Tree->leaf[ i ] = NODE_NONE;
}

/*
 * This routine is responsible for taking a symbol, and converting
 * it into the sequence of bits dictated by the Huffman Tree.  The
 * only complication is that we are working are way up from the leaf
 * to the root, and hence are getting the bits in reverse order.  This
 * means we have to rack up the bits in an integer and then send them
 * out after they are all accumulated.  In this version of the program,
 * we keep our codes in a long integer, so the maximum count is set
 * to an arbitray limit of 0x8000.  It could be set as high as 65535
 * if desired.
 */

void __regargs __inline AHuff_EncodeC(struct AHuffInfo *AHI,long c)
{
register struct AHuffTree * Tree;
long current_node;

Tree = AHI->Tree;

	{
	register ulong code=0;
	register ulong current_bit=1;
	register long code_size=0;
	register struct BitIOInfo * BII;

	BII = AHI->BII;

	current_node = Tree->leaf[ c ];
	if ( current_node == NODE_NONE ) current_node = Tree->leaf[ ESCAPE ];
	while ( current_node != ROOT_NODE )
		{
	  if ( ( current_node & 1 ) == 0 ) code += current_bit;
  	current_bit += current_bit;
	  code_size++;
  	current_node = Tree->nodes[ current_node ].parent;

	  /* <> could update the tree while we descend (if basenode != ESCAPE) */
		};
	BitIO_WriteBits(BII,code,code_size);
	}

if ( Tree->leaf[ c ] == NODE_NONE ) 
	{
		{
		register struct BitIOInfo * BII;
		BII = AHI->BII;
		BitIO_WriteBits(BII,c,8);
		}
		{
		register long lightest_node,new_node,zero_weight_node;
  	add_new_node( Tree, c );
		}
	}

	{
	register long new_node,current_node;
	AHuff_UpdateModel_Macro( AHI, Tree, c );
	}

}

/*
 * Decoding symbols is easy.  We start at the root node, then go down
 * the Tree until we reach a leaf.  At each node, we decide which
 * child to take based on the next input bit.  After getting to the
 * leaf, we check to see if we read in the ESCAPE code.  If we did,
 * it means that the next symbol is going to come through in the next
 * eight bits, unencoded.  If that is the case, we read it in here,
 * and add the new symbol to the table.
 */

long AHuff_DecodeC( struct AHuffInfo *AHI )
{
long current_node;
long c;
bool bit;
struct AHuffTree * Tree;

Tree = AHI->Tree;

current_node = ROOT_NODE;
while ( !Tree->nodes[ current_node ].child_is_leaf ) 
	{
  current_node = Tree->nodes[ current_node ].child;
	BitIO_ReadBit(AHI->BII,bit);
	if ( bit ) current_node++;
	}
c = Tree->nodes[ current_node ].child;
if ( c == ESCAPE ) 
	{
	BitIO_ReadBits(AHI->BII,c,8);
  add_new_node( Tree, c );
	}

AHuff_UpdateModel_Macro( AHI, Tree, c );

return( c );
}

/*
 * Rebuilding the Tree takes place when the counts have gone too
 * high.  From a simple point of view, rebuilding the Tree just means that
 * we divide every count by two.  Unfortunately, due to truncation effects,
 * this means that the Tree's shape might change.  Some nodes might move
 * up due to cumulative increases, while others may move down.
 */
/* <> this is very slow */
void AHuff_HalveTree( struct AHuffInfo *AHI )
{
long i;
long j;
long k;
long weight;
struct AHuffTree * Tree;

Tree = AHI->Tree;

/*
 * To start rebuilding the table,  I collect all the leaves of the Huffman
 * Tree and put them in the end of the Tree.  While I am doing that, I
 * scale the counts down by a factor of 2.
 */

j = Tree->next_free_node - 1;
for ( i = j ; i >= ROOT_NODE ; i-- ) 
	{
  if ( Tree->nodes[ i ].child_is_leaf ) 
		{
    Tree->nodes[ j ] = Tree->nodes[ i ];
    Tree->nodes[ j ].weight = ( Tree->nodes[ j ].weight + 1 ) >> 1;
		/* <> todo : allow weights of 1 to be scaled to 0 and dropped out */
    j--;
    }
  }

/*
 * At this point, j points to the first free node.  I now have all the
 * leaves defined, and need to start building the higher nodes on the
 * Tree. I will start adding the new internalnodes at j.  Every time
 * I add a new internalnode to the top of the Tree, I have to check to
 * see where it really belongs in the Tree.  It might stay at the top,
 * but there is a good chance I might have to move it back down.  If it
 * does have to go down, I use the memmove() function to scoot everyone
 * bigger up by one node.  Note that memmove() may have to be change
 * to memcpy() on some UNIX systems.  The parameters are unchanged, as
 * memmove and  memcpy have the same set of parameters.
 */
for ( i = Tree->next_free_node - 2 ; j >= ROOT_NODE ; i -= 2, j-- ) 
	{
  k = i + 1;
  Tree->nodes[ j ].weight = Tree->nodes[ i ].weight +
                            Tree->nodes[ k ].weight;
  weight = Tree->nodes[ j ].weight;
  Tree->nodes[ j ].child_is_leaf = 0;
  for ( k = j + 1 ; weight < Tree->nodes[ k ].weight ; k++ ) ;
  k--;
  memmove( &Tree->nodes[ j ], &Tree->nodes[ j + 1 ],
           ( k - j ) * sizeof( struct AHuffNode ) );
  Tree->nodes[ k ].weight = weight;
  Tree->nodes[ k ].child = i;
  Tree->nodes[ k ].child_is_leaf = 0;
  }

/*
 * The final step in Tree reconstruction is to go through and set up
 * all of the leaf and parent members.  This can be safely done now
 * that every node is in its final position in the Tree.
 */
for ( i = Tree->next_free_node - 1 ; i >= ROOT_NODE ; i-- ) 
	{
  if ( Tree->nodes[ i ].child_is_leaf ) 
		{
    k = Tree->nodes[ i ].child;
    Tree->leaf[ k ] = i;
		}
	else 
		{
    k = Tree->nodes[ i ].child;
    Tree->nodes[ k ].parent = Tree->nodes[ k + 1 ].parent = i;
  	}
  }

}

void AHuff_UpdateModel( struct AHuffInfo *AHI , long c )
{
long new_node,current_node;
struct AHuffTree * Tree;

Tree = AHI->Tree;

if ( Tree->nodes[ ROOT_NODE].weight == MAX_WEIGHT )                  
  AHuff_HalveTree( AHI );                                            
current_node = Tree->leaf[ c ];                                      
for(;;)
	{                                                                  
  Tree->nodes[ current_node ].weight++;
	/* <> this for loop is mondo slowness (20% of exec. time) */
  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 ); /* 8% of exec time */
    current_node = new_node;                                         
  	}                                                                
  current_node = Tree->nodes[ current_node ].parent;
	if ( current_node == NODE_NONE ) break;
	}                                                                  
}