v04i039: splay tree compression routines

[Bodo Rueskamp]

Posting-number: Volume 4, Issue 39
Submitted-by: "Bodo Rueskamp" <br at laura.irb.informatik.uni-dortmund.de.UUCP>
Archive-name: spl

Splay tree compression routines from the article "Application Of Splay
Trees To Data Compression", Communications of the ACM, August 1988.



#--------------------------------CUT HERE-------------------------------------
#! /bin/sh
#
# This is a shell archive.  Save this into a file, edit it
# and delete all lines above this comment.  Then give this
# file to sh by executing the command "sh file".  The files
# will be extracted into the current directory owned by
# you with default permissions.
#
# The files contained herein are:
#
# -rw-------   1 br       group         83 Aug 25 13:37 Makefile
# -rw-r--r--   1 br       group       1530 Aug 25 13:26 spl.c
# -rw-r--r--   1 br       group       1550 Aug 25 13:28 unspl.c
# -rw-------   1 br       group        251 Aug 25 13:56 RESULTS
#
echo 'x - Makefile'
if test -f Makefile; then echo 'shar: not overwriting Makefile'; else
sed 's/^X//' << '________This_Is_The_END________' > Makefile
X
Xall: spl unspl
X
Xspl: spl.o
X	cc -o spl spl.o
X
Xunspl: unspl.o
X	cc -o unspl unspl.o
X
________This_Is_The_END________
if test `wc -l < Makefile` -ne 9; then
	echo 'shar: Makefile was damaged during transit (should have been 9 bytes)'
fi
fi		; : end of overwriting check
echo 'x - spl.c'
if test -f spl.c; then echo 'shar: not overwriting spl.c'; else
sed 's/^X//' << '________This_Is_The_END________' > spl.c
X/*
X    Splay Tree Compression
X
X    from: "Application Of Splay Trees To Data Compression"
X          by Douglas W. Jones, Communications of the ACM, August 1988
X
X    implemented in C by Bodo Rueskamp, <br at unido.uucp>
X*/
X
X/*  splay tree compress  */
X
X#include <stdio.h>
X
Xint left[257], right[257], up[514];
X
Xstatic int bitnum = 0;
X
Xvoid bit_output(bit)
Xint bit;
X{
X	static int byte = 0;
X
X	byte = (byte << 1) | bit;
X	++bitnum;
X	if (bitnum == 8) {
X		putchar(byte);
X		byte = 0;
X		bitnum = 0;
X	}
X}
X
Xvoid initialize()
X{
X	int i;
X
X	for (i=0; i<514; ++i)
X		up[i] = i / 2;
X	for (i=0; i<257; ++i) {
X		left[i] = i * 2;
X		right[i] = i * 2 + 1;
X	}
X}
X
Xvoid splay(plain)
Xint plain;
X{
X	int a, b, c, d;
X
X	a = plain + 257;
X	while (a) {  /*  walk up the tree semi-rotating pairs  */
X		c = up[a];
X		if (c) {  /*  a pair remains  */
X			d = up[c];
X			/*  exchange children of pair  */
X			b = left[d];
X			if (c == b) {
X				b = right[d];
X				right[d] = a;
X			} else {
X				left[d] = a;
X			}
X			if (a == left[c]) {
X				left[c] = b;
X			} else {
X				right[c] = b;
X			}
X			up[a] = d;
X			up[b] = c;
X			a = d;
X		} else {  /*  handle odd node at end  */
X			a = c;
X		}
X	}
X}
X
Xvoid compress(plain)
Xint plain;
X{
X	int sp;
X	char stack[514];
X	int a;
X
X	a = plain + 257;
X	sp = 0;
X	while (a) {
X		stack[sp++] = a == right[up[a]];
X		a = up[a];
X	}
X	while (sp--)
X		bit_output(stack[sp]);
X	splay(plain);
X}
X
Xmain()
X{
X	int c;
X
X	putchar(0x1f);
X	putchar('S');
X	initialize();
X	while ((c = getchar()) != -1)
X		compress(c);
X	compress(256);
X	while (bitnum)
X		bit_output(0);
X	return(0);
X}
________This_Is_The_END________
if test `wc -l < spl.c` -ne 107; then
	echo 'shar: spl.c was damaged during transit (should have been 107 bytes)'
fi
fi		; : end of overwriting check
echo 'x - unspl.c'
if test -f unspl.c; then echo 'shar: not overwriting unspl.c'; else
sed 's/^X//' << '________This_Is_The_END________' > unspl.c
X/*
X    Splay Tree Compression
X
X    from: "Application Of Splay Trees To Data Compression"
X          by Douglas W. Jones, Communications of the ACM, August 1988
X
X    implemented in C by Bodo Rueskamp, <br at unido.uucp>
X*/
X
X/*  splay tree uncompress  */
X
X#include <stdio.h>
X
Xint left[257], right[257], up[514];
X
Xint bit_input()
X{
X	static int bitnum = 0;
X	static int byte;
X
X	if (bitnum == 0) {
X		if ((byte = getchar()) == -1) {
X			fprintf(stderr, "unexpected end of input\n");
X			exit(1);
X		}
X		bitnum = 8;
X	}
X	byte <<= 1;
X	--bitnum;
X	return((byte >> 8) & 1);
X}
X
Xvoid initialize()
X{
X	int i;
X
X	for (i=0; i<514; ++i)
X		up[i] = i / 2;
X	for (i=0; i<257; ++i) {
X		left[i] = i * 2;
X		right[i] = i * 2 + 1;
X	}
X}
X
Xvoid splay(plain)
Xint plain;
X{
X	int a, b, c, d;
X
X	a = plain + 257;
X	while (a) {  /*  walk up the tree semi-rotating pairs  */
X		c = up[a];
X		if (c) {  /*  a pair remains  */
X			d = up[c];
X			/*  exchange children of pair  */
X			b = left[d];
X			if (c == b) {
X				b = right[d];
X				right[d] = a;
X			} else {
X				left[d] = a;
X			}
X			if (a == left[c]) {
X				left[c] = b;
X			} else {
X				right[c] = b;
X			}
X			up[a] = d;
X			up[b] = c;
X			a = d;
X		} else {  /*  handle odd node at end  */
X			a = c;
X		}
X	}
X}
X
Xint uncompress()
X{
X	int a;
X
X	a = 0;
X	while (a < 257)
X		a = bit_input() ? right[a] : left[a];
X	a -= 257;
X	splay(a);
X	return(a);
X}
X
Xmain()
X{
X	int c;
X
X	if ((getchar() != 0x1f) || (getchar() != 'S')) {
X		fprintf(stderr, "stdin not in compressed format\n");
X		exit(1);
X	}
X	initialize();
X	while ((c = uncompress()) != 256)
X		putchar(c);
X	return(0);
X}
________This_Is_The_END________
if test `wc -l < unspl.c` -ne 101; then
	echo 'shar: unspl.c was damaged during transit (should have been 101 bytes)'
fi
fi		; : end of overwriting check
echo 'x - RESULTS'
if test -f RESULTS; then echo 'shar: not overwriting RESULTS'; else
sed 's/^X//' << '________This_Is_The_END________' > RESULTS
X
Xsome results of LZW and splay tree compression:
X
Xfilename       length  factor
X
XMakefile	  83	 0%
XMakefile.S	  62	25%
XMakefile.Z	  59	29%
X
Xspl.c		1530	 0%
Xspl.c.S		1128	26%
Xspl.c.Z	 	 958	37%
X
Xunspl.c		1550	 0%
Xunspl.c.S	1152	26%
Xunspl.c.Z	1007	35%
X
________This_Is_The_END________
if test `wc -l < RESULTS` -ne 17; then
	echo 'shar: RESULTS was damaged during transit (should have been 17 bytes)'
fi
fi		; : end of overwriting check
exit 0