USER$DISK2:[GRIFFIN.COURSE.COMP]COMPRESS.C;13
 
/*
**
**	TITLE:         COMPRESS
**	AUTHOR:        Brian S. Griffin
**	VERSION:       1.0
**
*/
#define VERSION (1.0)

/*
 * compress a file using huffman coding
 */

#include <stdio.h>
#include "freq.h"

extern debug;

compress(b,out)
struct hcode b[];
int out;
{
    register int t, i;
    register char *code;
    register unsigned char byte;
    long b_count, in_count;

    rewind (stdin);

    in_count = b_count = byte = i = 0;
    while ((t = getc(stdin)) != EOF) {
	in_count++;
	code = b[t & 0xff].code;
	while (*code != 0) {
	    byte <<= 1;
	    byte |= *code++ == '0' ? 0 : 1;
	    if (++i == 8) {
		if (out) putc(byte,stdout);
		if (debug) fprintf(stderr,":%02x:\n",byte);
		b_count++;
		byte = i = 0;
	    }
	}
    }
    if (i > 0) {
	b_count++;
	if (out) putc(byte,stdout);
	if (debug) fprintf (stderr,"Flush->:%02x:\n",byte);
    }
    if (out) putc(i,stdout);
    fprintf (stderr,"Input count: %d\n", in_count);
    fprintf (stderr,"Output count: %d\n", b_count);
}
 
USER$DISK2:[GRIFFIN.COURSE.COMP]HCOMP.C;7
 
/*
**
**	TITLE:         HCOMP
**	AUTHOR:        Brian S. Griffin
**	VERSION:       1.0
**
*/
#define VERSION	(1.0)

/*
 * Main routine for file compression using Huffman encoding
 */

#include <stdio.h>
#include "freq.h"

int debug;
struct hcode bytes[256];

main(argc,argv)
int argc;
char *argv[];
{
    struct tnode *root, *tree();
    struct hcode *b;
    int t, i;
    char *infile, *outfile;
    FILE *freopen();

    fprintf(stderr,
     "HCOMP Version %6.1f, RCA \n",
                  VERSION);
    infile = outfile = NULL;
    debug = FALSE;
    for (i=1; i<argc; i++) {
	if (*argv[i] == '-') {
	    switch (*++argv[i]) {
		case 'd': debug = TRUE;
			  break;
		default:  printf ("Unknown switch '%c'\n", *argv[i]);
			  printf ("Option ignored\n");
			  break;
	    }
	}
	else {
	    if (infile == NULL) infile = argv[i];
	    else outfile = argv[i];
	}
    }

    if (infile != NULL) {
	if (freopen(infile, "r", stdin) == NULL) {
	    perror("Infile failed open");
	    exit (2);
	}
    }
    if (outfile != NULL) {
	if (freopen(outfile, "w", stdout) == NULL) {
	    perror("Outfile failed open");
	    exit (2);
	}
    }

    for (b = bytes; b<&bytes[256];)
	(b++)->count = 0;
    while ((t = getc(stdin)) != EOF) {
	(bytes[t&0xff]).count += 1;
    }
    for (t = 0, b = bytes; b<&bytes[256]; t++, b++) {
	if (outfile != NULL) putw(b->count, stdout);
	if (b->count > 0)
	    if (debug) fprintf (stderr,"%6d %02x\n", b->count, t);
    }
    root = huffman(bytes);
    htreeprint(root,bytes);
    compress(bytes,outfile!=NULL);
}
 
USER$DISK2:[GRIFFIN.COURSE.COMP]HTREEPRINT.C;17
 
/*
**
**	TITLE:         HTREEPRINT
**	AUTHOR:        Brian S. Griffin
**	VERSION:       1.0
**
*/
#define VERSION	(1.0)

/*
 * Generate codes from Huffman tree. 
 * Prints the tree if debug is set.
 */

#include <stdio.h>
#include "freq.h"

extern debug;
static char buffer[100], *bptr = buffer;

htreeprint(p,b)	/* print tree p recursively */
struct tnode *p;
struct hcode b[];
{
    char *strsave();

    if (p->byte == -1) {
	*bptr++ = '0';
	htreeprint(p->left,b);
	*bptr++ = '1';
	htreeprint(p->right,b);
    }
    else {
	*bptr = 0;
	if (debug) fprintf(stderr,"%4d %02x - %s\n", p->count, p->byte, buffer);
	b[p->byte & 0xff].code = strsave(buffer);
    }
    bptr--;
}

char *
strsave(str)
char *str;
{
	char *malloc();

	return(strcpy(malloc(strlen(str)+1),str));
}
 
USER$DISK2:[GRIFFIN.COURSE.COMP]HUFFMAN.C;7
 
/*
**
**	TITLE:         HUFFMAN
**	AUTHOR:        Brian S. Griffin
**	VERSION:       1.0
**
*/
#define VERSION (1.0)

/*
 * build a huffman tree 
 */

#include <stdio.h>
#include "freq.h"

struct tnode *list[256];
struct tnode *tadd();

extern debug;

struct tnode *
huffman(p)
struct hcode *p;
{
    register int i;
    register int small, next_small;
    register int llen;
    struct tnode ttmp;

    llen = bytes_to_list(p);
    do {
	small = next_small = 0;
	for (i=0; i<llen; i++)
	    if ((i != next_small) && ((list[i])->count <= (list[small])->count))
		small = i;
	if (next_small == small) next_small++;
	for (i=0; i<llen; i++)
	    if ((i != small) && ((list[i])->count <= (list[next_small])->count))
		next_small = i;

	ttmp.count = (list[small])->count + (list[next_small])->count;
	ttmp.byte = -1;
	ttmp.left = list[small];
	ttmp.right = list[next_small];
	list[small] = tadd(&ttmp);

	llen--;
	for (i=next_small; i < llen; i++)
	    list[i] = list[i+1];
    } while (llen > 1);
    if (debug) fprintf (stderr,"Final Node: %d\n",(list[0])->count);
    return (list[0]);
}

struct tnode *
tadd(p)			/* add a node to the tree */
struct tnode *p;
{
    register struct tnode *htree;

    htree = (struct tnode *) malloc(sizeof(struct tnode));
    *htree = *p;
    return (htree);
}

int
bytes_to_list(p)	/* build end nodes of tree */
struct hcode p[];	/* and list of pointers to them */
{
    register int j;
    register int i = 0;
    struct tnode ttmp;
    for (j=0; j<256; j++) {
	if (p[j].count > 0) {
	    ttmp.byte = j;
	    ttmp.count = p[j].count;
	    ttmp.left = ttmp.right = NULL;
	    list[i++] = tadd(&ttmp);
	}
    }
    list[i] = 0;
    return (i);
}

 
USER$DISK2:[GRIFFIN.COURSE.COMP]UNCOMP.C;6
 
/*
**
**	TITLE:         UNCOMP
**	AUTHOR:        Brian S. Griffin
**	VERSION:       1.0
**
*/
#define VERSION (1.0)

/*
 * Uncompresses a file 
 */

#include <stdio.h>
#include "freq.h"

int debug;
struct hcode bytes[256];

main(argc,argv)
int argc;
char *argv[];
{
    struct tnode *root, *tree();
    struct hcode *b;
    int t, i;
    char *infile, *outfile;
    FILE *freopen();

    fprintf(stderr,
     "UNCOMP Version %6.1f, BG\n",
                    VERSION);
    infile = outfile = NULL;
    debug = FALSE;
    for (i=1; i<argc; i++) {
	if (*argv[i] == '-') {
	    switch (*++argv[i]) {
		case 'd': debug = TRUE;
			  break;
		default:  printf ("Unknown switch '%c'\n", *argv[i]);
			  printf ("Option ignored\n");
			  break;
	    }
	}
	else {
	    if (infile == NULL) infile = argv[i];
	    else outfile = argv[i];
	}
    }

    if (infile != NULL) {
	if (freopen(infile, "r", stdin) == NULL) {
	    perror("Infile failed open");
	    exit (2);
	}
    }
    if (outfile != NULL) {
	if (freopen(outfile, "w", stdout) == NULL) {
	    perror("Outfile failed open");
	    exit (2);
	}
    }

    for (b = bytes; b<&bytes[256];)
	(b++)->count = getw(stdin);
    if (feof(stdin)) {
	perror ("Unexpected EOF");
	exit (2);
    }
    if (debug) 
      for (t = 0, b = bytes; b<&bytes[256]; t++, b++) {
	if (b->count > 0)
	    fprintf (stderr,"%6d %02x\n", b->count, t);
    }
    root = huffman(bytes);
    htreeprint(root,bytes);
    uncompress(root,outfile!=NULL);
}
 
USER$DISK2:[GRIFFIN.COURSE.COMP]UNCOMPRESS.C;18
 
/*
**
**	TITLE:         UNCOMPRESS
**	AUTHOR:        Brian S. Griffin
**	VERSION:       1.01
**
*/
#define VERSION (1.01)

/*
 * uncompress a file using huffman coding
 */

#include <stdio.h>
#include "freq.h"

extern debug;

uncompress(huf,out)
struct tnode *huf;
int out;
{
    register int t, i;
    register struct tnode *tp;
    register unsigned char byte;
    long b_count, in_count;

    in_count = b_count = byte = i = 0;
    tp = huf;
    while ((t = getcc(stdin)) != EOF) {
	if (debug) fprintf (stderr, "Inbyte: %02x -> ", t);
	in_count++;
	byte = t;
	for (i=0;i<8;i++) {
	    if (byte & 0x80) tp = tp->right;
	    else	     tp = tp->left;
	    if (tp->byte >= 0) {
		if (out) putc((tp->byte & 0xff), stdout);
		if (debug) fprintf (stderr, "%02x ", (tp->byte & 0xff));
		b_count++;
		tp = huf;
	    }
	    byte <<= 1;
	}
	if (debug) fprintf (stderr, "\n");
    }
    byte = getcc(stdin);
    t = getcc(stdin);
    if (debug) fprintf (stderr,"\nFinal byte: %02x, count=%d\n",byte,t);
    for (i = t; i<8; i++) byte <<= 1;
    for (i = 0; i<t; i++) {
	if (byte & 0x80) tp = tp->right;
	else		 tp = tp->left;
	if (tp->byte >= 0) {
	    if (out) putc((tp->byte & 0xff), stdout);
	    if (debug) fprintf (stderr,"Final output: %02x\n", (tp->byte & 0xff));
	    b_count++;
	    tp = huf;
	}
	byte <<= 1;
    }

    fprintf (stderr,"Input count: %d\n", in_count);
    fprintf (stderr,"Output count: %d\n", b_count);
}

static char buffer[3];
static unsigned char bi = 0;
static int end = 0;
static char first = 0;

getcc(f)
FILE *f;
{
    int t;
    unsigned char c;

    if (first == 0) {
	for (c=0; c<3; c++) {
	    buffer[bi] = getc(f);
	    bi = (bi+1) % 3;
	}
	first = 1;
    }
    if (end == 1) {
	end = 2;
	return (EOF);
    }
    else if (end > 1) {
	c = buffer[bi];
	bi = (bi + 1) % 3;
	return (c);
    }
    else {
	c = buffer[bi];
	if ((t = getc(f)) == EOF) end = 1;
	buffer[bi] = t;
	bi = (bi+1) % 3;
	return(c);
    }
}    	
 
USER$DISK2:[GRIFFIN.COURSE.COMP]FREQ.H;6
 
struct tnode {			/* the basic node */
	int byte;		/* points to the text */
	int count;		/* number of occurrences */
	struct tnode *left;	/* left child */
	struct tnode *right;	/* right child */
};

struct hcode {
	int count;
	char *code;
};

#define MAXWORD	1200
#define LETTER	'a'
#define DIGIT	'0'
 
USER$DISK2:[GRIFFIN.COURSE.COMP]LINK.COM;5
 
$link hcomp,huffman,htreeprint,compress
 
USER$DISK2:[GRIFFIN.COURSE.COMP]UNLINK.COM;1
 
$link uncomp,huffman,htreeprint,uncompress
