/*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.