Source Code 1992 March/Source_Code_CD-ROM_Walnut_Creek_March_1992.iso/usenet/compsrcs/misc/volume04/spl

Text File | 1991-08-27 | 6.2 KB | 304 lines

Path: uunet!lll-winken!lll-tis!ames!mailrus!tut.cis.ohio-state.edu!cwjcc!hal!ncoast!allbery
From: [e-mail] (Bodo Rueskamp)
Newsgroups: comp.sources.misc
Subject: v04i039: splay tree compression routines
Message-ID: <[e-mail]>
Date: 25 Aug 88 23:46:57 GMT
Sender: [e-mail]
Reply-To: [e-mail] (Bodo Rueskamp)
Lines: 291
Approved: [e-mail]

Posting-number: Volume 4, Issue 39
Submitted-by: "Bodo Rueskamp" <[e-mail]>
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, <[e-mail]>
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, <[e-mail]>
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