/*
 * LZW + ASCII85 encoding.  Original code from Tektronix Postscript utilities
 * mailer. Modified by A. Accomazzi (alberto@cfa.harvard.edu) 11/01/93 to
 * merge LZW and ASCII85 in one program.
 * 
 */

#include <stdio.h>

/* Various constants */
#define EOD	  257		/* End of Data marker */
#define CLR	  256		/* Clear Table Marker */
#define MAXSTRINGS  4096	/* using 12 bit max codes */
#define TRUE	  (1==1)
#define FALSE	  !TRUE
#define max(x,y) (((x)>(y))?(x):(y))
#define min(x,y) (((x)<(y))?(x):(y))
#define match(string, option, lmin)     ( strncmp((string), (option), max((lmin),strlen(string))) == 0 )

/* This is the structure for a single entry into the string table */
typedef struct {
    short           prefix;
    short           suffix;
    short           next;
    }               stringrec;

/* Global data */
unsigned char	*output_data;		/* output array */
long		output_bytes;		/* output bytes */
int             codeWidth;		/* Used by codeSend function */
int             nextIndex;		/* Used by newentry function */
stringrec       stringarray[4096];	/* This is the string table */
long            divarray[5] = { 1L, 85L, 7225L, 614125L, 52200625L }; 

int 		bitsInAcc = 0;
unsigned long acc = 0;	/* bits left over from a sendcode */
unsigned long base256 = 0;
int      	phase = 0;


/* function prototypes */
void            Initialize(void);
void            SendCode(short theCode);
int             FindString(short *prefix, short suffix);
void            AddString(short prefix, short suffix);
void            ASCII85Encode(int);
int		lzwa85(unsigned char*, int *, unsigned char*, int *);
#ifndef VMS
int		lzwa85_(unsigned char*, int *, unsigned char*, int *);
#endif


void 
    ASCII85Encode(int theChar)
{
    register int 	index;
#if 0
    static unsigned long base256 = 0;
    static int      	phase = 0;
#endif    
    if (theChar != EOF) {
	base256 += theChar << (8 * (3 - phase++));
	
	if (phase == 4) {
	    if (base256 == 0)
		output_data[output_bytes++] = 'z';
	    else 
		for (index = 4; index >= 0; index--) {
		    output_data[output_bytes++] = base256/divarray[index]+'!';
		    base256 = base256 % divarray[index];
		    }
	    phase = 0;
	    base256 = 0;
	    }
	
	}
    else {
	if (phase != 0) {
	    for (index = 4; index >= (4 - phase); index--) {
		output_data[output_bytes++] = base256 / divarray[index] + '!';
		base256 = base256 % divarray[index];
		}
	    }
	output_data[output_bytes++] = '~';
	output_data[output_bytes++] = '>';
	output_data[output_bytes] = '\0';
	base256 = 0;
	phase = 0;
	}
    
    return;
    }


void
    Initialize()
{
    register int 	index;
    
    for (index = 0; index < 256; index++) {
	stringarray[index].prefix = -1;
	stringarray[index].suffix = (char) index;
	stringarray[index].next = -1;
	}
    nextIndex = EOD + 1;
    codeWidth = 9;
    }


void 
SendCode(short theCode)
{
#if 0
    static int 		bitsInAcc = 0;
    static unsigned long acc = 0;	/* bits left over from a sendcode */
#endif
    acc += (long) theCode << (32 - codeWidth - bitsInAcc);
    bitsInAcc += codeWidth;

    while (bitsInAcc >= 8) {
	ASCII85Encode(acc >> 24);
	acc = acc << 8;
	bitsInAcc -= 8;
	}
    
    if (theCode == CLR) {
	Initialize();
	}

    if (theCode == EOD) {
	if (bitsInAcc != 0)
	    ASCII85Encode(acc >> 24);
	ASCII85Encode(EOF);
	bitsInAcc = 0;
	acc = 0;
	}

    return;
    }


/* fortran hooks into the program */
#ifndef VMS
int
    lzwa85_(unsigned char *indata, int *inbytes, 
	    unsigned char *outdata, int *outbytes)
{ 
    lzwa85(indata, inbytes, outdata, outbytes);
    return;
    }
#endif

int
    lzwa85(unsigned char *indata,  int *inbytes, 
       unsigned char *outdata, int *outbytes)
{
    short           lastCode;
    short           thisCode;
    register long   index = 0;
    long int 	    input_bytes = *inbytes;

    output_bytes = 0;
    output_data = outdata;
    codeWidth = 9;
    nextIndex = 0;

    SendCode(CLR);

    index = 0;
    lastCode = indata[index++];
    if (index >= input_bytes) {
	SendCode(EOD);
	*outbytes = output_bytes;
	return;
	}
    while (index < input_bytes) {
	thisCode = indata[index++];
	if (FindString(&lastCode, thisCode)) {
	    continue;
	    }
	else {
	    SendCode(lastCode);
	    AddString(lastCode, thisCode);
	    lastCode = thisCode;
	    }
	}
    
    SendCode(lastCode);
    SendCode(EOD);
    
    *outbytes = output_bytes;
    return;
    }


int
    FindString(short *prefix, short suffix)
{
    short           index = *prefix;
    
    while (index != -1) {
	if (stringarray[index].prefix == *prefix &&
	    stringarray[index].suffix == suffix) {
	    *prefix = index;
	    return (TRUE);
	    } 
	else
	    index = stringarray[index].next;
	}
    
    return (FALSE);
    }

void
    AddString(short prefix, short suffix)
{
    
    stringarray[nextIndex].prefix = prefix;
    stringarray[nextIndex].suffix = suffix;
    stringarray[nextIndex].next = stringarray[prefix].next;
    stringarray[prefix].next = nextIndex;
    
    if (++nextIndex >> codeWidth) {
	if (++codeWidth > 12) {
	    --codeWidth;
	    SendCode(CLR);
	    }
	}
    return;
    }