🚀 go-pugleaf

Sample implementation of Huffman two-pass algorithm.
Original sources taken from DDJ October, 1992.

# This is a shell archive.  Save it in a file, remove anything before
# this line, and then unpack it by entering "sh file".  Note, it may
# create directories; files and directories will be owned by you and
# have default permissions.
#
# This archive contains:
#
#	Makefile
#	huff.c
#
echo x - Makefile
sed 's/^X//' >Makefile << 'END-of-Makefile'
XSHELL   = /bin/sh
XCC      = cc -pipe -fstrength-reduce
XCFLAGS  = -O
X
Xhuff:   huff.o
X	$(CC) $(LDFLAGS) huff.o -o huff
X
Xclean:
X	rm -f .,* *.o *.b huff core core.*
END-of-Makefile
echo x - huff.c
sed 's/^X//' >huff.c << 'END-of-huff.c'
X/*
X * Sample implementation of Huffman two-pass algorithm.
X * Original sources taken from DDJ October, 1992.
X *
X * Implemented by Sergey Vakulenko, <vak@kiae.su>.
X */
X
X#include <stdio.h>
X
X/* ---- Huffman tree structure for building ---- */
Xstruct htree {
X	long cnt;               /* character frequency */
X	short parent;           /* offset to parent node */
X	short right;            /* offset to right child node */
X	short left;             /* offset to left child node */
X};
X
X/* ---- Huffman tree structure in compressed file ---- */
Xstruct htr {
X	short right;            /* offset to right child node */
X	short left;             /* offset to left child node */
X};
X
Xstatic long bytectr;
Xstatic struct htree ht [512];
Xstatic struct htr htr [256];
Xstatic short root;
Xstatic short treect;
Xstatic FILE *fo;
Xstatic short ct;
Xstatic char out [1024];
Xstatic short in;
X
X/* ---- flush remaining bits to the compressed output file ---- */
Xstatic void outflush ()
X{
X	char *p;
X
X	if (ct == 0)
X		return;
X	while (ct < sizeof (out))
X		out [ct++] = 0;
X	p = out;
X	while (p < out+sizeof(out)) {
X		int c = *p++ << 7;
X		c |= *p++ << 6;
X		c |= *p++ << 5;
X		c |= *p++ << 4;
X		c |= *p++ << 3;
X		c |= *p++ << 2;
X		c |= *p++ << 1;
X		c |= *p++;
X		putc (c, fo);
X	}
X	ct = 0;
X}
X
X/* ---- compress a character value into a bit stream ---- */
Xstatic void compress (int h, int child)
X{
X	int hp;
X
X	if ((hp = ht[h].parent) != -1)
X		compress (hp, h);
X	if (child) {
X		if (ct >= sizeof (out))
X			outflush ();
X		out [ct++] = (child == ht[h].left);
X	}
X}
X
X/* ---- build a Huffman tree from a frequency array ---- */
Xstatic void buildtree (void)
X{
X	int i;
X
X	treect = 256;
X	/* ---- preset node pointers to -1 ---- */
X	for (i=0; i<treect; ++i) {
X		ht[i].parent = -1;
X		ht[i].right = -1;
X		ht[i].left = -1;
X	}
X	/* ---- build the Huffman tree ---- */
X	while (1) {
X		int h1= -1, h2 = -1;
X		/* ---- find the two lowest frequencies ---- */
X		for (i=0; i<treect; ++i) {
X			if (i != h1) {
X				struct htree *htt = ht+i;
X				/* ---- find a node without a parent ---- */
X				if (htt->cnt > 0 && htt->parent == -1) {
X					/* ---- h1 & h2 -> lowest nodes ---- */
X					if (h1 == -1 || htt->cnt < ht[h1].cnt) {
X						if (h2 == -1 || ht[h1].cnt < ht[h2].cnt)
X							h2 = h1;
X						h1 = i;
X					} else if (h2 == -1 || htt->cnt < ht[h2].cnt)
X						h2 = i;
X				}
X			}
X		}
X		/* ---- if only h1 -> a node, that's the root ---- */
X		if (h2 == -1) {
X			root = h1 - 256;
X			break;
X		}
X		/* ---- combine two nodes and add one ---- */
X		ht[h1].parent = treect;
X		ht[h2].parent = treect;
X		if (! ht)
X			break;
X		/* ---- the new node's frequency is the sum of the two
X			nodes with the lowest frequencies ---- */
X		ht[treect].cnt = ht[h1].cnt + ht[h2].cnt;
X		/* ---- the new node points to the two that it combines ---- */
X		ht[treect].right = h1;
X		ht[treect].left = h2;
X		/* ---- the new node has no parent (yet) ---- */
X		ht[treect].parent = -1;
X		++treect;
X	}
X	treect -= 256;
X}
X
X/* ---- compress the file from i to o ---- */
Xhuff (FILE *i, FILE *o)
X{
X	int c;
X
X	/* ---- global variable is faster than parameter passing ---- */
X	fo = o;
X
X	/* ---- read the input file and count character frequency ---- */
X	bytectr = 0;
X	while ((c = getc (i)) >= 0) {
X		++ht[c].cnt;
X		++bytectr;
X	}
X
X	/* ---- build the Huffman tree ---- */
X	buildtree ();
X	/* ---- write the byte count to the output file ---- */
X	fwrite (&bytectr, sizeof (bytectr), 1, fo);
X	/* ---- write the tree count to the output file ---- */
X	fwrite (&treect, sizeof (treect), 1, fo);
X	/* ---- write the root offset to the output file ---- */
X	fwrite (&root, sizeof (root), 1, fo);
X	/* ---- write the tree to the output file ---- */
X	for (c=0; c<treect; ++c) {
X		short lf = ht[c+256].left - 256;
X		short rt = ht[c+256].right - 256;
X		fwrite (&lf, sizeof (lf), 1, fo);
X		fwrite (&rt, sizeof (rt), 1, fo);
X	}
X
X	/* ---- compress the file ---- */
X	fseek (i, 0L, 0);
X	ct = 0;
X	while ((c = getc (i)) >= 0)
X		compress (c, 0);
X	outflush (fo);
X}
X
X/* ---- read a character from the compressed file ---- */
Xint getchuff (FILE *i)
X{
X	short h = root;
X	/* ---- walk the Huffman tree ---- */
X	do {
X		/* ---- h is a node pointer ---- */
X		if (ct == 8) {
X			/* ---- read 8 bits of compressed data ---- */
X			if ((in = getc (i)) < 0)
X				return (-1);
X			ct = 0;
X		}
X		/* ---- point to left or right node based on msb --- */
X		if (in & 0x80)
X			h = htr[h].left;
X		else
X			h = htr[h].right;
X		/* ---- shift the next bit in ---- */
X		in <<= 1;
X		++ct;
X	} while (h >= 0);
X	/* ---- h < 0 = decompressed character ---- */
X	return (h + 256);
X}
X
X/* ---- decompress the file from i to o ---- */
Xdehuff (FILE *i, FILE *o)
X{
X	int c;
X
X	/* ---- read the byte count ---- */
X	fread (&bytectr, sizeof (bytectr), 1, i);
X	/* ---- read the frequency count ---- */
X	fread (&treect, sizeof (treect), 1, i);
X	/* ---- read the root offset ---- */
X	fread (&root, sizeof (root), 1, i);
X	/* ---- read in the tree ---- */
X	for (c=0; c<treect; ++c) {
X		fread (&htr[c].left, sizeof (htr[c].left), 1, i);
X		fread (&htr[c].right, sizeof (htr[c].right), 1, i);
X	}
X	ct = 8;
X	while (--bytectr >= 0 && (c = getchuff (i)) >= 0)
X		putc (c, o);
X}
X
Xint main (int argc, char **argv)
X{
X	FILE *i, *o;
X	int c, dflag;
X
X	if (! strcmp (argv[0] + strlen (argv[0]) - 6, "dehuff"))
X		++dflag;
X	if (! strcmp (argv[1], "-d")) {
X		++argv;
X		--argc;
X		++dflag;
X	}
X	if (argc < 3) {
X		printf ("Usage: huff [-d] infile outfile\n\n");
X		printf ("Compresses (by default) or decompresses (-d) infile\n");
X		printf ("to outfile, using Huffman two-pass algorithm.\n");
X		printf ("Implemented by Sergey Vakulenko, <vak@kiae.su>.\n");
X		exit (1);
X	}
X	i = fopen (argv[1], "rb");
X	if (! i) {
X		perror (argv[1]);
X		exit (1);
X	}
X	o = fopen (argv[2], "wb");
X	if (! o) {
X		perror (argv[2]);
X		exit (1);
X	}
X	if (dflag)
X		dehuff (i, o);
X	else
X		huff (i, o);
X	fclose (i);
X	fclose (o);
X	return (0);
X}
END-of-huff.c
exit