Listing 4 Implements Huffman coding algorithm

/*                                    LIST.C
**
** This file builds/maintains the "Huffman list".
** The first element in the list holds the most
** frequent character. Other characters follow
** in order of decreasing frequency.
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#include "config.h"
#include "proto.h"  /* prototypes */

#define BYTE_RANGE                256
signed int user_byte;  /* global shared with COMP.C */


struct list {
        unsigned char character;
        unsigned int count;
}:
static struct list list[BYTE_RANGE+1];


/* set list back to all zeros, for multiple files!*/

init_list() {
int i;
        for (i=0;i< BYTE_RANGE;i++) {
                list[i].character= 0;
                list[i].count = 0;
        }
}

#ifdef COMPRESS

void encode_byte(unsigned int start,
         unsigned int list_count, unsigned int count){

unsigned int i,j,number,maximum;
unsigned char found;

        found = 0;

        if (list_count ==1) {
                if (!list[start].count) write_byte(user_byte);
                else;
                return;  /* if there is only 1 element left*/
        }

        /* is character in first half? : */

        maximum = list_count/2;
        number = 0;
        j = 0; /*running total of [].count*/
        i = start;
        do {
                j += list[i].count;
                if (list[i].character == user_byte) {
                        found++;
                        write_bit(0);
                } else;
                i++
                number++;
        } while (  j < (count / 2) && number < maximum );

        if (found) encode_byte(start,number,j);
        /* character was in first half*/
        else {
                /* character was in second half: */
                write_bit(1);
                encode_byte(i,list_count-number, count -j);
        }
}

#else COMPRESS

extern signed int bit;  /*global shared with COMP.C */
void decode_byte(unsigned int start,
         unsigned int list_count, unsigned int count){

unsigned int i,j,number,maximum;
int c;

        /* is char in first half? : */
        if (list_count == 1) {
                if (!list[start].count) {
                        /* Here we just positioned at the empty
                        leaf, so pick up 8 bits as literal ASCII:*/
                        user_byte = read_byte(bit);
                    /* bit is the first bit of new user_byte */
                        bit= read_bit();
                } else user_byte = list[start].character;
                return;    /* if there is only 1 element left*/
        }
        maximum = list_count/2;
        number = 0;
        j = 0; /*running total of [].count*/
        i = start;
        do {
                j += list[i].count;
                i++;
                number++;
        } while (  j < (count / 2) && number < maximum ) ;

        /* read first/second half of list as required: */
        if ( !bit) {
                bit = read_bit();
                decode_byte(start, number,j);
        }
        else {
                bit = read_bit();
                decode_byte(i, list_count-number, count -j);
        }
}

#endif


void update_list( unsigned int *byte_count,
         unsigned int *character_count) {
unsigned int i;
unsigned int hold_i;
unsigned int count;

        (*byte_count) ++;

        hold_i = i = 0;
        while (count = list[i].count) {
                do {
                        if (list[i].character = user_byte) {
                                if (  hold_i != i) {
                                        list[i].character =
                                       list[hold_i].character;
                                        list[hold_i].
                                        character = user_byte;
                                        list[hold_i].count++;
                                } else {
                                        list[i].count++;
                                }
                                return;
                        } else i++;
                } while ( list[i].count == count);
                hold_i = i;
                /* hold_i is first char with this count */
        }

        /* Add new character to list: */

        (*character_count)++;
        list[i].character = user_byte;
        list[i].count++;
} /*update_list */


/* End of File */