/* File: minunsplay.c
   Author: Douglas Jones, Dept. of Comp. Sci., U. of Iowa, Iowa City, IA 52242.
   Date: Nov. 5, 1990.
         (derived from the Feb. 14 1990 version by stripping out irrelevancies)
         (minor revision of Feb. 20, 1989 to add exit(0) at end of program).
         (minor revision of Nov. 14, 1988 to detect corrupt input better).
         (minor revision of Aug. 8, 1988 to eliminate unused vars, fix -c).
   Copyright:  This material is derived from code Copyrighted 1988 by
         Jeffrey Chilton and Douglas Jones.  That code contained a copyright
         notice allowing copying for personal or research purposes, so long
         as copies of the code were not sold for direct commercial advantage.
         This version of the code has been stripped of most of the material
         added by Jeff Chilton, and this release of the code may be used or
         copied for any purpose, public or private.
   Patents:  The algorithm central to this code is entirely the invention of
         Douglas Jones, and it has not been patented.  Any patents claiming
         to cover this material are invalid.
   Exportability:  Splay-tree based compression algorithms may be used for
         cryptography, and when used as such, they may not be exported from
         the United States without appropriate approval.  All cryptographic
         features of the original version of this code have been removed.
   Language: C
   Purpose: Data uncompression program, a companion to minsplay.c
   Algorithm: Uses a splay-tree based prefix code.  For a full understanding
          of the operation of this data compression scheme, refer to the paper
          "Applications of Splay Trees to Data Compression" by Douglas W. Jones
          in Communications of the ACM, Aug. 1988, pages 996-1007.
*/

#include<stdio.h>

/* The magic numbers are a two byte prefix on the stream of compressed
   data.  This prefix is applied by the main program, and it serves to
   distinguish files compressed this way from files produced by other
   software.  The particular prefix used here is compatible with the
   splay-compress UNIX data compression utility.  In other contexts, there
   is no reason to use this particular prefix or any prefix at all.
 */
#define MAGIC1 0x93     /* ^S with the high bit set */
#define MAGIC2 0x10     /* ^P */

/* The following constants depend on the size of the alphabet being
   compressed, and are used to dimension the arrays that hold the tree used
   for compression and to mark key elements in these trees.

   Throughout, it is assumed that the alphabet of source characters is
   contiguous and runs from zero to some maximum.
 */
#define MAXCHAR 256     /* maximum source character code */
#define SUCCMAX 257     /* MAXCHAR + 1 */
#define TWICEMAX 513    /* 2 * MAXCHAR + 1 */
#define SUCCTWICE 514   /* TWICEMAX + 1 */

#define ROOT    1       /* index of root node in the arrays left,right,up */


/* data structures used to unpack successive bits from bytes.
 */
#define TOPBITINBUFFER 128 /* mask for the most sig bit of 8 bit byte */
#define MAXBITCOUNTER 8    /* size of a byte */
short int bitbuffer;       /* buffer to hold a byte for unpacking bits */
short int bitcounter = 0;  /* count of remaining bits in buffer */

short int plain;           /* most recent character uncompressed */

/* global variables that hold the tree used for uncompression.

   Node i of the tree is stored in left[i], right[i] and up[i].  Nodes from
   the root (node 1) to node MAXCHAR are internal nodes of the tree, and
   nodes SUCCMAX to SUCCTWICE are leaves.  For an alphabet of MAXCHAR
   characters, this allows one extra character to be used as an end-of-file
   mark.
 */
short int left[SUCCMAX];
short int right[SUCCMAX];
short int up[SUCCTWICE];


/* begin error messages */
bad_magic()
{
        fprintf(stderr, "Error: input not in splayed format\n");
        exit(-1);
}

bad_data()
{
        fprintf(stderr, "Error: corrupt input\n");
        exit(-1);
}
/* end error messages */


/* begin build initial splay tree */
initsplay()
{
        short int i, j;
        for (i = 2; i <= TWICEMAX; ++i) {
                up[i] = i/2;
        }
        for (j = 1; j <= MAXCHAR; ++j)  {
                left[j] = 2 * j;
                right[j] = 2 * j + 1;
        }
}
/* end build initial splay tree */


/* begin uncompress function */
uncompress()
{
        register short int a, b, c, d;                                  \
        a = ROOT;

        do {  /* once for each bit on path */
                if(bitcounter == 0) {
                        bitbuffer = getchar();
                        if ((bitbuffer == EOF) && feof(stdin)) {
                                bad_data();
                        }
                        bitcounter = MAXBITCOUNTER;
                }
                --bitcounter;
                if ((bitbuffer & TOPBITINBUFFER) != 0) {
                        a = right[a];
                } else {
                        a = left[a];
                }
                bitbuffer = bitbuffer << 1;
        } while (a <= MAXCHAR);
        plain = a - SUCCMAX;

        /* now splay tree about leaf a */
        do {    /* walk up the tree semi-rotating pairs of nodes */
                if ((c = up[a]) != ROOT) {      /* a pair remains */
                        d = up[c];
                        b = left[d];
                        if (c == b) {
                                b = right[d];
                                right[d] = a;
                        } else {
                                left[d] = a;
                        }
                        if (left[c] == a) {
                                left[c] = b;
                        } else { 
                                right[c] = b;
                        }
                        up[a] = d;
                        up[b] = c;
                        a = d;
                } else { 
                        a = c;
                }
        } while (a != ROOT);
}
/* end uncompress function */


/* THE MAIN PROGRAM */
main(argc, argv)
int argc;
char *argv[];
{
        initsplay();

        /* check the magic number as produced by the UNIX splay utility */
        if (getchar() != MAGIC1) bad_magic();
        if (getchar() != MAGIC2) bad_magic();
        if (getchar() != 1) bad_magic();

        /* begin uncompress input */
        for (;;) {
                uncompress();
                if (plain != MAXCHAR) {
                        putchar(plain);
                } else {
                        break;
                }
        }
        /* end uncompress input */

        /* see if file really ended */
        if ((getchar() != EOF) || !feof(stdin)) {
                bad_data();
        }
}