/*
** general purpose file unpacker, Copyright (C) Randy Nevin 1989, 1990.
**
** you may give this software to anyone, make as many copies as you like, and
** post it on public computer bulletin boards and file servers. you may not
** sell it or charge any fee for distribution (except for media and postage),
** remove this comment or the copyright notice from the code, or claim that
** you wrote this code or anything derived from it. you may modify the code as
** much as you want (please document clearly with comments, and maintain the
** coding style), but programs which are derived from this one are subject to
** the conditions stated here. i am providing this code so that people can
** learn from it, so if you distribute it, please include source code, not
** just executables. contact me to report bugs or suggest enhancements; i do
** not guarantee support, but i will make an effort to help you, and i want to
** act as a central clearing house for future versions. you should contact me
** before undertaking a significant development effort, to avoid reinventing
** the wheel. if you come up with an enhancement you consider particularly
** useful, i would appreciate being informed so that it can be incorporated in
** future versions. my address is: Randy Nevin, 1731 211th PL NE, Redmond,
** WA 98053, USA. this code is available directly from the author; just send a
** 360k floppy and a self-addressed floppy mailer with sufficient postage.
**
** HISTORY
** (name		date		description)
** ----------------------------------------------------
** randy nevin		7/17/89		initial version
** randy nevin		8/6/89		changed to handle run-length encoding
**					in addition to huffman encoding
** randy nevin		8/15/89		released version 1.00
*/

/* BUGBUG: doesn't handle files with only one byte value */

/*
** unpack a file that has been packed with huffman or run-length encoding. the
** file contains a packing identification byte (1=huffman, 2=run-length). for
** huffman encoding, it also contains the number of bytes, a skeletal tree
** structure, the corresponding byte values, and the encoded bits. for
** run-length encoding, it contains the encoding byte, then the encoded file,
** with the encoding byte indicating the next two bytes are the number of
** occurrences, and the encoded byte. an exception (for run-length encoding)
** is if the number of occurrences is 0, in which case this represents just
** one (literal) encoded byte; there is no following 'encoded byte'.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 32	/* use a maximum of 32 bits per byte */

struct node { /* tree node for huffman encoding */
	int byteval;
	char buf[MAX+1];
	char pad;
	struct node *left, *right;
	} *head = NULL;

void main( int, char *[] );
void walk0( struct node *, FILE * );
void walk1( struct node *, char [], int );
void walk2( struct node *, FILE * );
void initbit( void );
int inbit( FILE * );

void main ( argc, argv )
	int argc;
	char *argv[];
	{
	char *self, *t;
	int c, enc, i;
	FILE *fin, *fout;
	register struct node *p;
	char buf[MAX+1];
	long total;
	int b1, b2, b3, b4;

	printf( "Copyright (C) Randy Nevin, 1989, 1990. Version 1.00\n" );
	printf( "See source code for rights granted.\n\n" );
	self = argv[0];
	/* get rid of initial part of path */
	if ((t = strrchr( self, '\\' )) || (t = strrchr( self, ':' )))
		self = ++t;
	/* get rid of extension */
	if ((t = strrchr( self, '.' )) && !stricmp( t, ".EXE" ))
		*t = 0;
	if (argc != 3) { /* need infile and outfile */
		fprintf( stderr, "usage: %s infile outfile\n", self );
		exit( -1 );
		}
	if (!(fin = fopen( argv[1], "rb" ))) {
		fprintf( stderr, "can't open %s\n", argv[1] );
		exit( -1 );
		}
	if (!(fout = fopen( argv[2], "wb" ))) {
		fprintf( stderr, "can't open %s\n", argv[2] );
		exit( -1 );
		}
	if ((c = getc( fin )) == 1) { /* huffman encoding */
		b1 = getc( fin );
		b2 = getc( fin );
		b3 = getc( fin );
		b4 = getc( fin );
		total = (long)b1 | ((long)b2<<8) | ((long)b3<<16)
			| ((long)b4 << 24);
		/* build the encoding tree */
		if (!(head = (struct node *)malloc( sizeof(struct node) ))) {
			fprintf( stderr, "out of memory\n" );
			exit( -1 );
			}
		head->left = head->right = NULL;
		initbit();
		walk0( head, fin ); /* construct encoded tree */
		buf[0] = 0;
		walk1( head, buf, 0 ); /* assign encoded bit strings */
		walk2( head, fin ); /* read in byte values */
		initbit();
		while (total--) { /* read in each "byte" */
			p = head;
			while (p->left && p->right)
				p = (inbit( fin )) ? p->right : p->left;
			putc( (char)(p->byteval), fout );
			}
		}
	else if (c == 2) { /* run-length encoding */
		if ((enc = getc( fin )) == EOF) {
			fprintf( stderr, "premature eof\n" );
			exit( -1 );
			}
		while ((c = getc( fin )) != EOF) {
			if (c == enc) {
				if ((i = getc( fin )) == EOF) {
					fprintf( stderr, "premature eof\n" );
					exit( -1 );
					}
				if (!i)
					putc( (char)enc, fout );
				else {
					if ((c = getc( fin )) == EOF) {
						fprintf( stderr,
							"premature eof\n" );
						exit( -1 );
						}
					while (i--)
						putc( (char)c, fout );
					}
				}
			else
				putc( (char)c, fout );
			}
		}
	else if (c == EOF) {
		fprintf( stderr, "premature eof\n" );
		exit( -1 );
		}
	else {
		fprintf( stderr, "unrecognized encoding type\n" );
		exit( -1 );
		}
	if (ferror( fout ))
		fprintf( stderr, "output error; disk might be full\n" );
	fclose( fout );
	exit( 0 );
	}

void walk0 ( p, fin ) /* input skeletal tree structure */
	struct node *p;
	FILE *fin;
	{
	/* a 1 bit indicates a node has children; 0 means no children */
	if (inbit( fin )) {
		if (!(p->left = (struct node *)malloc(
				sizeof(struct node) ))
			|| !(p->right = (struct node *)malloc(
				sizeof(struct node) ))) {
			fprintf( stderr, "out of memory\n" );
			exit( -1 );
			}
		p->left->left =
		  p->left->right =
		    p->right->left =
		      p->right->right = NULL;
		walk0( p->left, fin );
		walk0( p->right, fin );
		}
	}

void walk1 ( p, buf, level ) /* assign encoded bit strings */
	struct node *p;
	char buf[];
	int level;
	{
	if (!(p->left) && !(p->right)) {
		strcpy( p->buf, buf );
		/* printf( "str[0x%02X] = %s\n", p->byteval, buf ); */
		}
	else if (level < MAX) {
		buf[level] = '0';
		buf[level+1] = 0;
		walk1( p->left, buf, level+1 );
		buf[level] = '1';
		buf[level+1] = 0;
		walk1( p->right, buf, level+1 );
		buf[level] = 0;
		}
	else {
		fprintf( stderr, "error: skewed tree\n" );
		exit( -1 );
		}
	}

void walk2 ( p, fin ) /* read in byte values for the tree */
	struct node *p;
	FILE *fin;
	{
	if (p->left) {
		walk2( p->left, fin );
		walk2( p->right, fin );
		}
	else
		p->byteval = getc( fin );
	}

static int nbit; /* how many bits remaining in buffer */
static char byte; /* the byte buffer */

void initbit () { /* initialize bit output buffer */
	nbit = 0;
	byte = 0;
	}

int inbit( fp ) /* input a bit using byte buffering */
	FILE *fp;
	{
	int bit, newbyte;

	if (!nbit) {
		if ((newbyte = getc( fp )) == EOF) {
			fprintf( stderr, "unexpected EOF\n" );
			newbyte = 0; /* force zeros */
			}
		byte = (char)newbyte;
		nbit = 8;
		}

	bit = byte & 1;
	byte >>= 1;
	nbit--;
	return( bit );
	}