splay.c

The two C source files in this archive are specific to the TRS-80 Model 4 with high-resolution grap

/* Splint:
 * a data compression program
 *
 * This program refers the Pascal source codes of
 * a splay-prefix encoding program in an article of
 *
 * Jones, Douglas. W,:
 * Application of Splay Trees to Data Compression,
 * Communications ACM, Vol. 31, No. 8, pp. 996 - 1007. (August 1988)
 *
 * Written by Kenji Rikitake and Naoshi Wakatabe.
 * Copyright (C)1988, 1989 by Kenji Rikitake and Naoshi Wakatabe.
 * All rights reserved.
 * Permission to copy this program without fee all or part of this
 * material is granted, provided that the copies are not made or
 * distributed for direct commercial advantage.
 *
 * If you have any questions and/or suggestions, Contact
 *
 * Kenji Rikitake
 * 4-19-11-102, Sakurajousui, Setagaya-ku,
 * Tokyo 156 Japan
 * JUNET: [e-mail]
 */

/* $Header: splay.cv  1.6  89/03/08 01:00:50  kenji  Exp $
 * $Log: RCS/splay.cv $
 * Revision 1.6  89/03/08 01:00:50  kenji
 * combined with bitio.c by Kenji
 * 
 * Revision 1.5  89/03/01 14:10:26  kenji
 * Kenji welcome Naoshi one of the authors
 * Naoshi changed the tree by using "struct".
 * This made things a bit faster
 * 
 * Revision 1.3  89/01/06 23:58:50  kenji
 * encryption algorithm improved
 * 
 * Revision 1.2  89/01/06 23:36:16  kenji
 * added block freeing routine.
 * modified for using file pointers.
 * 
 * Revision 1.1  88/12/27 16:06:14  kenji
 * Initial revision
 * 
 */

/* $Header: splay.cv  1.6  89/03/08 01:00:50  kenji  Exp $
 * $Log: RCS/splay.cv $
 * Revision 1.6  89/03/08 01:00:50  kenji
 * combined with bitio.c by Kenji
 * 
 * Revision 1.5  89/03/01 14:10:26  kenji
 * Kenji welcome Naoshi one of the authors
 * Naoshi changed the tree by using "struct".
 * This made things a bit faster
 * 
 * Revision 1.4  89/02/22 20:28:14  kenji
 * Modified for Microsoft C 5.1 Small Model by Naoshi Wakatabe
 * 
 * Revision 1.3  89/01/06 23:58:50  kenji
 * encryption algorithm improved
 * 
 * Revision 1.2  89/01/06 23:36:16  kenji
 * added block freeing routine.
 * modified for using file pointers.
 * 
 * Revision 1.1  88/12/27 16:06:14  kenji
 * Initial revision
 * 
 */

static char *identfield = "$Header: splay.cv  1.6  89/03/08 01:00:50  kenji  Exp $";

/* splaying routines */

#include "splint.h"

/* splay-prefix tree structure */

/*
int sup[MAXSTATE][TWICEMAX+1];
int sleft[MAXSTATE][MAXCHAR+1];
int sright[MAXSTATE][MAXCHAR+1];
*/

#ifndef MSDOS
#define	far
#else
#define	malloc(size)	_fmalloc(size)
#define	free(block)	_ffree(block)
#endif

struct tree {
	int	up[TWICEMAX + 1];
	int	left[MAXCHAR + 1];
	int	right[MAXCHAR + 1];
};

struct tree far *stree[MAXSTATE];
int state;

#define BIT_OVLIM 16	/* output bit overflow limit */

/* bit buffers */
static int ibuf;		/* input waiting bits */
static int ibitstogo;	/* # of bits in ibuf */
static int igarbits;	/* # of bits past eof */
static int obuf;		/* output waiting bits */
static int obitstogo;	/* # of bits in obuf */

/* initialize bit i/o buffers */
#define start_inputing_bits() {ibitstogo = 0; igarbits = 0;}
#define start_outputing_bits() {obuf = 0; obitstogo = 8;}

/* output buffer flush */
#define done_outputing_bits(outp) putc((obuf >> obitstogo), outp)

/* input a bit */

int input_bit(inp)
FILE *inp;
{
	int t;
	
	if (ibitstogo == 0) {
		ibuf = getc(inp);
		if (ibuf == EOF) {
			igarbits++;
			if (igarbits > BIT_OVLIM) {
				fprintf(stderr, "splint: input file exceeds EOF\n");
				exit(-1);
				}
			}
		ibitstogo = 8;
		}
	t = ibuf & 1;
	ibuf >>= 1;
	ibitstogo--;
	return t;
}

/* output a bit */

void output_bit(bit, outp)
int bit;
FILE *outp;
{
	obuf >>= 1;
	if (bit) {
		obuf |= 0x80;
		}
	obitstogo--;
	if (obitstogo == 0) {
		putc(obuf, outp);
		obitstogo = 8;
		}
}

/* malloc() with heap check */
static void far *ch_malloc(size)
size_t size;
{
	void far *blockp;

	if ((blockp = malloc(size)) == NULL) {
		fprintf(stderr, "splint: out of memory\n");
		exit(-1);
		}
	return blockp;
}

/* initializing splay tree structure */

void spl_init()
{
	int i, j, s;
	struct tree far *spp;
	void splay();

	start_inputing_bits();
	start_outputing_bits();

	for (s = 0; s < MAXSTATE; s++) {


		spp = (struct tree far *)ch_malloc(sizeof(struct tree));
		stree[s] = spp;
#ifdef DEBUG
		fprintf(stderr, "spl_init: s = %d\n", s);
		fprintf(stderr, "coreleft = %ld\n", coreleft());
#endif

		for (i = 2; i <= TWICEMAX; i++) {
			spp->up[i] = i / 2;
			}
		for (j = 1; j <= MAXCHAR; j++) {
			spp->left[j] = 2 * j;
			spp->right[j] = 2 * j + 1;
			}
		}

	/* pre-splaying for cryptography */
	j = strlen(spl_passwd) - 1;
	for (s = 0; s < MAXSTATE; s++) {
		for (i = j; i >= 0; i--) {
			state = s;
			splay(spl_passwd[i]);
			}
		}

	/* initial state */
	state = 0;

}

/* unalloc used trees */
/* free() with reverse sequence of ch_malloc() */

void free_trees()
{
	int s;

	for (s = MAXSTATE - 1; s >= 0; s--) {
		free(stree[s]);
		}

}

/* splay the tree with a symbol */

#ifndef ASM
void splay(sym)
int sym;
{
	int a, b, c, d;
	struct tree far *spp;

	a = sym + SUCCMAX;
	spp = stree[state];

	do {
		c = spp->up[a];
		if (c != ROOT) {
			d = spp->up[c];
			b = spp->left[d];
			if (c == b) {
				b = spp->right[d];
				spp->right[d] = a;
				}
			else {
				spp->left[d] = a;
				}
			if (a == spp->left[c]) {
				spp->left[c] = b;
				}
			else {
				spp->right[c] = b;
				}
			spp->up[a] = d;
			spp->up[b] = c;
			a = d;
			}
		else {
			a = c;
			}
	} while (a != ROOT);

	state = sym % MAXSTATE;
}
#endif

/* compress a symbol */

void spl_comp(sym, outp)
int sym;
FILE *outp;
{
	int sp, a;
	int stack[MAXCHAR];
	struct tree far *spp;
	
	a = sym + SUCCMAX;
	sp = 0;
	spp = stree[state];
	do {
		stack[sp] = (spp->right[spp->up[a]] == a) ? 1 : 0;
		sp++;
		a = spp->up[a];
	} while (a != ROOT);
	do {
		sp--;
		output_bit(stack[sp], outp);
	} while (sp > 0);
	splay(sym);
}

/* expand a code into its symbol */

int spl_exp(inp)
FILE *inp;
{
	int a, sym;
	struct tree far *spp;
	a = ROOT;
	
	spp = stree[state];
	do {
		if (input_bit(inp) == 0) {
			a = spp->left[a];
			}
		else {
			a = spp->right[a];
			}
	} while (a <= MAXCHAR);
	sym = a - SUCCMAX;
	splay(sym);
	return sym;
}

/* encoding from inp to outp */

void spl_encode(inp, outp)
FILE *inp, *outp;
{
	int sym;

	spl_init();

	for(;;) {
		if((sym = getc(inp)) == EOF) break;
		spl_comp(sym, outp);
		}

#ifdef DEBUG
		fprintf(stderr, "spl_encode: got out of for loop\n");
#endif
	spl_comp(EOF_CODE, outp);
#ifdef DEBUG
		fprintf(stderr, "spl_encode: spl_comp(EOF_SYM) done\n");
#endif
	done_outputing_bits(outp);
	free_trees();
}

/* decoding from inp to outp */

void spl_decode(inp, outp)
FILE *inp, *outp;
{
	int sym;

	spl_init();

	for(;;) {
		sym = spl_exp(inp);
		if(sym == EOF_CODE) break;
		putc(sym, outp);
		}
#ifdef DEBUG
		fprintf(stderr, "spl_decode: EOF_CODE received\n");
#endif
	free_trees();
}

/* end */