_C PROGRAMMING COLUMN_
by Al Stevens


[LISTING ONE]

/* ------------------- htree.h -------------------- */
typedef unsigned int BYTECOUNTER;

/* ---- Huffman tree structure ---- */
struct htree    {
    unsigned char ch;       /* character value             */
    BYTECOUNTER cnt;        /* character frequency         */
    struct htree *parent;   /* pointer to parent node      */
    struct htree *right;    /* pointer to right child node */
    struct htree *left;     /* pointer to left child node  */
};
extern struct htree ht[];
extern struct htree *root;

void buildtree(void);



[LISTING TWO]

/* ------------------- htree.c -------------------- */
#include <stdio.h>
#include <stdlib.h>
#include "htree.h"

struct htree ht[512];
struct htree *root;

/* ------ build a Huffman tree from a frequency array ------ */
void buildtree(void)
{
    int treect = 256;
    int i;

    /* ---- build the huffman tree ----- */
    while (1)   {
        struct htree *h1 = NULL, *h2 = NULL;
        /* ---- find the two smallest frequencies ---- */
        for (i = 0; i < treect; i++)   {
            if (ht+i != h1) {
                if (ht[i].cnt > 0 && ht[i].parent == NULL)   {
                    if (h1 == NULL || ht[i].cnt < h1->cnt) {
                        if (h2 == NULL || h1->cnt < h2->cnt)
                            h2 = h1;
                        h1 = ht+i;
                    }
                    else if (h2 == NULL || ht[i].cnt < h2->cnt)
                        h2 = ht+i;
                }
            }
        }
        if (h2 == NULL) {
            root = h1;
            break;
        }
        /* --- combine two nodes and add one --- */
        h1->parent = ht+treect;
        h2->parent = ht+treect;
        ht[treect].cnt = h1->cnt + h2->cnt;
        ht[treect].right = h1;
        ht[treect].left = h2;
        treect++;
    }
}



[LISTING THREE]

/* ------------------- huffc.c -------------------- */
#include <stdio.h>
#include <stdlib.h>
#include "htree.h"

static void compress(FILE *fo, struct htree *h,struct htree *child);
static void outbit(FILE *fo, int bit);

void main(int argc, char *argv[])
{
    FILE *fi, *fo;
    int c;
    BYTECOUNTER bytectr = 0;
    int freqctr = 0;
    if (argc < 3)   {
        printf("\nusage: huffc infile outfile");
        exit(1);
    }

    if ((fi = fopen(argv[1], "rb")) == NULL)    {
        printf("\nCannot open %s", argv[1]);
        exit(1);
    }
    if ((fo = fopen(argv[2], "wb")) == NULL)    {
        printf("\nCannot open %s", argv[2]);
        fclose(fi);
        exit(1);
    }

    /* - read the input file and count character frequency - */
    while ((c = fgetc(fi)) != EOF)   {
        c &= 255;
        if (ht[c].cnt == 0)   {
            freqctr++;
            ht[c].ch = c;
        }
        ht[c].cnt++;
        bytectr++;
    }

    /* --- write the byte count to the output file --- */
    fwrite(&bytectr, sizeof bytectr, 1, fo);

    /* --- write the frequency count to the output file --- */
    fwrite(&freqctr, sizeof freqctr, 1, fo);

    /* -- write the frequency array to the output file -- */
    for (c = 0; c < 256; c++)   {
        if (ht[c].cnt > 0)    {
            fwrite(&ht[c].ch, sizeof(char), 1, fo);
            fwrite(&ht[c].cnt, sizeof(BYTECOUNTER), 1, fo);
        }
    }

    /* ---- build the huffman tree ---- */
    buildtree();

    /* ------ compress the file ------ */
    fseek(fi, 0L, 0);
    while ((c = fgetc(fi)) != EOF)
        compress(fo, ht + (c & 255), NULL);
    outbit(fo, -1);
    fclose(fi);
    fclose(fo);
}

/* ---- compress a character value into a bit stream ---- */
static void compress(FILE *fo, struct htree *h,
                                struct htree *child)
{
    if (h->parent != NULL)
        compress(fo, h->parent, h);
    if (child)  {
        if (child == h->right)
            outbit(fo, 0);
        else if (child == h->left)
            outbit(fo, 1);
    }
}
static char out8;
static int ct8;

/* -- collect and write bits to the compressed output file -- */
static void outbit(FILE *fo, int bit)
{
    if (ct8 == 8 || bit == -1)  {
        fputc(out8, fo);
        ct8 = 0;
    }
    out8 = (out8 << 1) | bit;
    ct8++;
}



[LISTING FOUR]

/* ------------------- huffd.c -------------------- */
#include <stdio.h>
#include <stdlib.h>
#include "htree.h"

static int decompress(FILE *fi, struct htree *root);

void main(int argc, char *argv[])
{
    FILE *fi, *fo;
    unsigned char c;
    BYTECOUNTER bytectr;
    int freqctr;
    if (argc < 3)   {
        printf("\nusage: huffd infile outfile");
        exit(1);
    }
    if ((fi = fopen(argv[1], "rb")) == NULL)    {
        printf("\nCannot open %s", argv[1]);
        exit(1);
    }
    if ((fo = fopen(argv[2], "wb")) == NULL)    {
        printf("\nCannot open %s", argv[2]);
        fclose(fi);
        exit(1);
    }

    /* ----- read the byte count ------ */
    fread(&bytectr, sizeof bytectr, 1, fi);

    /* ----- read the frequency count ------ */
    fread(&freqctr, sizeof freqctr, 1, fi);

    while (freqctr--)   {
        fread(&c, sizeof(char), 1, fi);
        ht[c].ch = c;
        fread(&ht[c].cnt, sizeof(BYTECOUNTER), 1, fi);
    }

    /* ---- build the huffman tree ----- */
    buildtree();

    /* ----- decompress the file ------ */
    while (bytectr--)
        fputc(decompress(fi, root), fo);
    fclose(fo);
    fclose(fi);
}
static int in8;
static int ct8 = 8;

/* ---- read a bit at a time from a file ---- */
static int inbit(FILE *fi)
{
    int obit;
    if (ct8 == 8)   {
        in8 = fgetc(fi);
        ct8 = 0;
    }
    obit = in8 & 0x80;
    in8 <<= 1;
    ct8++;
    return obit;
}

/* ----- decompress file bits into characters ------ */
static int decompress(FILE *fi, struct htree *h)
{
    while (h->right != NULL)
        if (inbit(fi))
            h = h->left;
        else
            h = h->right;
    return h->ch;
}