Category : C Source Code
Archive   : SPLINT.ZIP
Filename : SPLAY.C

/* 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: rikitake%[email protected]
*/

/* $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 */