* * 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;	}                                                                  }