ahuff.c

huffman coding and decoding adaptive huffman coding and decoding it is a assignment from my cours

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

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

void RebuildTree( tree )
TREE *tree;
{
    int i;
    int j;
    int k;
    unsigned int weight;

/*
 * 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.
 */
    printf( "R" );
    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 ) / 2;
            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 internal nodes at j.  Every time
 * I add a new internal node 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 = FALSE;
        for ( k = j + 1 ; weight < tree->nodes[ k ].weight ; k++ )
            ;
        k--;
        memmove( &tree->nodes[ j ], &tree->nodes[ j + 1 ],
                 ( k - j ) * sizeof( struct node ) );
        tree->nodes[ k ].weight = weight;
        tree->nodes[ k ].child = i;
        tree->nodes[ k ].child_is_leaf = FALSE;
    }
/*
 * 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;
        }
    }
}

/*
 * Swapping nodes takes place when a node has grown too big for its
 * spot in the tree.  When swapping nodes i and j, we rearrange the
 * tree by exchanging the children under i with the children under j.
 */

void swap_nodes( tree, i, j )
TREE *tree;
int i;
int j;
{
    struct node temp;

    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;
    }
    temp = tree->nodes[ i ];
    tree->nodes[ i ] = tree->nodes[ j ];
    tree->nodes[ i ].parent = temp.parent;
    temp.parent = tree->nodes[ j ].parent;
    tree->nodes[ j ] = temp;
}

/*
 * 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.
 */
void add_new_node( tree, c )
TREE *tree;
int c;
{
    int lightest_node;
    int new_node;
    int zero_weight_node;

    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 = FALSE;

    tree->nodes[ zero_weight_node ].child           = c;
    tree->nodes[ zero_weight_node ].child_is_leaf   = TRUE;
    tree->nodes[ zero_weight_node ].weight          = 0;
    tree->nodes[ zero_weight_node ].parent          = lightest_node;
    tree->leaf[ c ] = zero_weight_node;
}

/*
 * All the code from here down is concerned with printing the tree.
 * Printing the tree out is basically a process of walking down through
 * all the nodes, with each new node to be printed getting nudged over
 * far enough to make room for everything that has come before.
 */

/*
 * This array is used to keep track of all the nodes that are in a given
 * row.  The nodes are kept in a linked list.  This array is used to keep
 * track of the first member.  The subsequent members will be found in
 * a linked list in the positions[] array.
 */

struct row {
    int first_member;
    int count;
} rows[ 32 ];

/*
 * The positions[] array is used to keep track of the row and column of each
 * node in the tree.  The next_member element points to the next node
 * in the row for the given node.  The column is calculated on the fly,
 * and represents the actual column that a given number is to be printed in.
 * Note that the column for a node is not an actual column on the page.  For
 * purposes of analysis, it is assumed that each node takes up exactly one
 * column.  So, if printing out the actual values in a node takes up for
 * spaces on the printed page, we might want to allocate five physical print
 * columns for each column in the array.
 */

struct location {
    int row;
    int next_member;
    int column;
} positions[ NODE_TABLE_COUNT ];

/*
 * This is the main routine called to print out a Huffman tree.  It first
 * calls the print_codes function, which prints out the binary codes
 * for each symbol.  After that, it calculates the row and column that
 * each node will be printed in, then prints the tree out.  This code
 * is not documented in the book, since it is essentially irrelevant to
 * the data compression process.  However, it is nice to be able to
 * print out the tree.
 */
void PrintTree( tree )
TREE *tree;
{
    int i;
    int min;

    print_codes( tree );
    for ( i = 0 ; i < 32 ; i++ ) {
        rows[ i ].count = 0;
        rows[ i ].first_member = -1;
    }
    calculate_rows( tree, ROOT_NODE, 0 );
    calculate_columns( tree, ROOT_NODE, 0 );

    min = find_minimum_column( tree, ROOT_NODE, 31 );
    rescale_columns( min );
    print_tree( tree, 0, 31 );
}

/*
 * This routine is called to print out the Huffman code for each symbol.
 * The real work is done by the print_code routine, which racks up the
 * bits and puts them out in the right order.
 */

void print_codes( tree )
TREE *tree;
{
    int i;

    printf( "\n" );
    for ( i = 0 ; i < SYMBOL_COUNT  ; i++ )
        if ( tree->leaf[ i ] != -1 ) {
             if ( isprint( i ) )
                 printf( "%5c: ", i );
             else
                 printf( "<%3d>: ", i );
            printf( "%5u", tree->nodes[ tree->leaf[ i ] ].weight );
            printf( " " );
            print_code( tree, i );
            printf( "\n" );
        }
}

/*
 * print_code is a workhorse routine that prints out the Huffman code for
 * a given symbol.  It ends up looking a lot like EncodeSymbol(), since
 * it more or less has to do the same work.  The major difference is that
 * instead of calling OutputBit, this routine calls putc, with a character
 * argument.
 */

void print_code( tree, c )
TREE *tree;
int c;
{
    unsigned long code;
    unsigned long current_bit;
    int code_size;
    int current_node;
    int i;

    code = 0;
    current_bit = 1;
    code_size = 0;
    current_node = tree->leaf[ c ];
    while ( current_node != ROOT_NODE ) {
        if ( current_node & 1 )
            code |= current_bit;
        current_bit <<= 1;
        code_size++;
        current_node = tree->nodes[ current_node ].parent;
    };
    for ( i = 0 ; i < code_size ; i++ ) {
        current_bit >>= 1;
        if ( code & current_bit )
            putc( '1', stdout );
        else
            putc( '0', stdout );
    }
}

/*
 * In order to print out the tree, I need to calculate the row and column
 * where each node will be printed.  The rows are easier than the columns,
 * and I do them first.  It is easy to keep track of what row a node is
 * in as I walk through the tree.  As I walk through the tree, I also keep
 * track of the order the nodes appear in a given row, by adding them to
 * a linked list in the proper order.  After calculate_rows() has been
 * recursively called all the way through the tree, I have a linked list of
 * nodes for each row.  This same linked list is used later to calculate
 * which column each node appears in.
 */

void calculate_rows( tree, node, level )
TREE *tree;
int node;
int level;
{
    if ( rows[ level ].first_member == -1 ) {
        rows[ level ].first_member = node;
        rows[ level ].count = 0;
        positions[ node ].row = level;
        positions[ node ].next_member = -1;
    } else {
        positions[ node ].row = level;
        positions[ node ].next_member = rows[ level ].first_member;
        rows[ level ].first_member = node;
        rows[ level ].count++;
    }
    if ( !tree->nodes[ node ].child_is_leaf ) {
        calculate_rows( tree, tree->nodes[ node ].child, level + 1 );
        calculate_rows( tree, tree->nodes[ node ].child + 1, level + 1 );
    }
}

/*
 * After I know which row each of the nodes is in, I can start the
 * hard work, which is calculating the columns.  This routine gets