#include "globals.h"
#include "../fileio/fileglob.h"

/* Written to allow for bits to be upto 16, although currently smaller values
   are used in Macintosh archives. */
#define BITS 16
#if BITS == 16
# define HSIZE	69001		/* 95% occupancy */
#endif
#if BITS == 15
# define HSIZE	35023		/* 94% occupancy */
#endif
#if BITS == 14
# define HSIZE	18013		/* 91% occupancy */
#endif
#if BITS == 13
# define HSIZE	9001		/* 91% occupancy */
#endif
#if BITS <= 12
# define HSIZE	5003		/* 80% occupancy */
#endif

#define INIT_BITS 9			/* initial number of bits/code */

static int n_bits;				/* number of bits/code */
static int maxbits;			/* user settable max # bits/code */
static long maxcode;			/* maximum code, given n_bits */
static long maxmaxcode;			/* should NEVER generate this code */
# define MAXCODE(n_bits)	((1 << (n_bits)) - 1)

static long htab [HSIZE];
static unsigned short codetab [HSIZE];

#define tab_prefixof(i) codetab[i]
#define tab_suffixof(i)	((unsigned char *)(htab))[i]
#define de_stack	((unsigned char *)&tab_suffixof(1<<BITS))

static long free_ent = 0;			/* first unused entry */

static long getcode();

static int clear_flg = 0;

/*
 * the next two codes should not be changed lightly, as they must not
 * lie within the contiguous general code space.
 */
#define FIRST	257	/* first free entry */
#define	CLEAR	256	/* table clear output code */

static int toread;

void decompress(ibytes, mb)
unsigned long ibytes;
int mb;
{
    register unsigned char *stackp;
    register int finchar;
    register long code, oldcode, incode;

    toread = ibytes;
    maxbits = mb;
    maxmaxcode = 1 << maxbits;
    maxcode = MAXCODE(n_bits = INIT_BITS);
    for(code = 255; code >= 0; code--) {
	tab_prefixof(code) = 0;
	tab_suffixof(code) = (unsigned char)code;
    }
    free_ent = FIRST;
    finchar = oldcode = getcode();
    if(oldcode == -1) {	/* EOF already? */
	return;			/* Get out of here */
    }
    /* first code must be 8 bits = char */
    *out_ptr++ = (char)finchar;
    stackp = de_stack;
    while((code = getcode()) > -1) {
	if(code == CLEAR) {
	    for(code = 255; code >= 0; code--) {
		tab_prefixof(code) = 0;
	    }
	    clear_flg = 1;
	    free_ent = FIRST - 1;
	    if((code = getcode()) == -1) {	/* O, untimely death! */
		break;
	    }
	}
	incode = code;
	/*
	 * Special case for KwKwK string.
	 */
	if(code >= free_ent) {
	    *stackp++ = finchar;
	    code = oldcode;
	}
	/*
	 * Generate output characters in reverse order
	 */
	while(code >= 256) {
	    *stackp++ = tab_suffixof(code);
	    code = tab_prefixof(code);
	}
	*stackp++ = finchar = tab_suffixof(code);
	/*
	 * And put them out in forward order
	 */
	do {
	    *out_ptr++ = (char)*--stackp;
	} while(stackp > de_stack);
	/*
	 * Generate the new entry.
	 */
	if((code=free_ent) < maxmaxcode) {
	    tab_prefixof(code) = (unsigned short)oldcode;
	    tab_suffixof(code) = finchar;
	    free_ent = code+1;
	}
	/*
	 * Remember previous code.
	 */
	oldcode = incode;
    }
    return;
}

unsigned char rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};

static long getcode()
{
    register long code;
    static int offset = 0, size = 0;
    static unsigned char buf[BITS];
    register int r_off, bits;
    register unsigned char *bp = buf;

    if(clear_flg > 0 || offset >= size || free_ent > maxcode) {
	/*
	 * If the next entry will be too big for the current code
	 * size, then we must increase the size.  This implies reading
	 * a new buffer full, too.
	 */
	if(free_ent > maxcode) {
	    n_bits++;
	    if(n_bits == maxbits) {
		maxcode = maxmaxcode;	/* won't get any bigger now */
	    } else {
		maxcode = MAXCODE(n_bits);
	    }
	}
	if(clear_flg > 0) {
	    maxcode = MAXCODE (n_bits = INIT_BITS);
	    clear_flg = 0;
	}
	if(toread == 0) {
	    return -1;
	}
	size = fread((char *)buf, 1, (n_bits < toread ? n_bits : toread), infp);
	toread -= size;
	if(size <= 0) {
	    fprintf(stderr, "Premature EOF\n");
	    exit(1);
	}
	offset = 0;
	/* Round size down to integral number of codes */
	size = (size << 3) - (n_bits - 1);
    }
    r_off = offset;
    bits = n_bits;
    /*
     * Get to the first byte.
     */
    bp += (r_off >> 3);
    r_off &= 7;
    /* Get first part (low order bits) */
    code = (*bp++ >> r_off);
    bits -= (8 - r_off);
    r_off = 8 - r_off;		/* now, offset into code word */
    /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
    if(bits >= 8) {
	code |= *bp++ << r_off;
	r_off += 8;
	bits -= 8;
    }
    /* high order bits. */
    code |= (*bp & rmask[bits]) << r_off;
    offset += n_bits;
    return code;
}

