br@laura.irb.informatik.uni-dortmund.de.UUCP (Bodo Rueskamp) (08/26/88)
Posting-number: Volume 4, Issue 39
Submitted-by: "Bodo Rueskamp" <br@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@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@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