#ifndef	lint
static char sccsid[] = "@(#)compress.c 1.3 88/12/21";
#endif

#include "cbratp.h"
#include <stdio.h>

#define	HSIZE		5003			/* Constants for NUT */
#define	HSHIFT		4
#define INIT_BITS 	9                     /* initial number of bits/code */
#define	BITS		12
#define CHECK_GAP 	10000 /* ratio check interval */
#define FIRST   	257     /* first free entry */
#define CLEAR   	256     /* table clear output code */
#define MAXCODE(n_bits) ((1 << (n_bits)) - 1)
#define htabof(i)       htab[i]
#define codetabof(i)    codetab[i]

extern char *memset();
#define cl_hash() (void) memset((char *) htab, 0xff, HSIZE * sizeof(long))

static int n_bits = INIT_BITS;          /* number of bits/code */
static int maxbits = BITS;		/* user settable max # bits/code */
static int maxcode = MAXCODE(INIT_BITS);/* maximum code, given n_bits */
static int maxmaxcode = 1 << BITS;      /* should NEVER generate this code */
static int free_ent = FIRST;		/* first unused entry */
static int clear_flg;
static long ratio;
static long checkpoint = CHECK_GAP;

static long htab[HSIZE];
static u_short codetab[HSIZE];
static once = 1;
 
/*
 * Algorithm from "A Technique for High Performance Data Compression",
 * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
 *
 * Modified Lempel-Ziv method (LZW).  Basically finds common
 * substrings and replaces them with a variable size code.  This is
 * deterministic, and can be done on the fly.  Thus, the decompression
 * procedure needs no input table, but tracks the way the table was built.
 */

static int	offset;
static int	ent;
static u_char	outbuf[MAXPKTSIZE];
static u_char	*outbufptr;
static long	in_count;
static long	out_count;

/* compresses onto inbuf so inbuf needs to be large enough to
 * contain the worse case compression. 1.5 * inbufsize
 */
compress(inbuf, inbufsize)
    u_char	 *inbuf;	/* uncompressed input (NULL if continued) */
    register int inbufsize;	/* uncompressed size / # input bytes read */
{
    register u_char	*inbufptr;
    register u_char	*inbufmax;
    register long	fcode;
    register int	i = 0;
    register int	c;
    register int	disp;
    extern char *memset();

#define	getinputchar() (inbufptr < inbufmax ? *inbufptr++ : EOF)

    outbufptr = outbuf;

    inbufptr = inbuf;
    inbufmax = inbufptr + inbufsize;

    offset = 0;
    clear_flg = 0;

    if (once)
    {
	cl_hash();
	once = 0;
    }

    ent = getinputchar();
    in_count++;

    while ((c = getinputchar()) != EOF)
    {
	in_count++;
	fcode = (long) (((long) c << maxbits) + ent);
 	i = ((c << HSHIFT) ^ ent);	/* xor hashing */

	if (htabof(i) == fcode) 
	{
	    ent = codetabof(i);
	    continue;
	} 
	else if ((long) htabof(i) < 0)	/* empty slot */
	    goto nomatch;
 	disp = HSIZE - i;		/* secondary hash (after G. Knott) */
	if (i == 0)
	    disp = 1;
probe:
	if ((i -= disp) < 0)
	    i += HSIZE;

	if (htabof(i) == fcode) 
	{
	    ent = codetabof(i);
	    continue;
	}
	if ((long) htabof(i) > 0) 
	    goto probe;

nomatch:
	output(ent);
	ent = c;
	if (free_ent < maxmaxcode) 
	{
 	    codetabof(i) = free_ent++;	/* code -> hashtable */
	    htabof(i) = fcode;
	}
	else if (in_count >= checkpoint) 
	{
	    /*
	     * table clear for block compress
	     * [cl_block() in-line]
	     */
	    long rat;
	    int	bytes_out = out_count + outbufptr - outbuf;

	    checkpoint = in_count + CHECK_GAP;

	    if (in_count > 0x007fffff) 
	    {		/* shift will overflow */
		rat = bytes_out >> 8;
		if (rat == 0) 
		    rat = 0x7fffffff;
		else
		    rat = in_count / rat;
	    }
	    else 
		rat = (in_count << 8) / bytes_out;	/* 8 fractional bits */

	    if (rat > ratio)
		ratio = rat;
	    else
	    {
		ratio = 0;
		cl_hash();				/* clear hash table */
		free_ent = FIRST;
		clear_flg = 1;
		output(CLEAR);
	    }
	}
    }

    if (c == EOF) 
    {
	output(ent);
	output(-1);
    }
    out_count += outbufptr - outbuf;
    bcopy((char *) outbuf, (char *) inbuf, outbufptr - outbuf);
    return outbufptr - outbuf;
}

static char buf[BITS];
 
static u_char lmask[9] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
static u_char rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
         
/*       
 * Output the given code.
 * Inputs:
 *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
 *              that n_bits =< (long)wordsize - 1.
 * Outputs:
 *      Outputs code to the file.
 * Assumptions:
 *      Chars are 8 bits long.
 * Algorithm:
 *      Maintain a BITS character long buffer (so that 8 codes will
 *      fit in it exactly).  When the buffer fills up empty it and start over.
 */      
output(code)
int  code;
{
    register int	r_off = offset;
    register int	bits = n_bits;
    register char	*bp = buf;
 
    if (code >= 0) 
    {
        /*
         * Get to the first byte.
         */
        bp += (r_off >> 3);
        r_off &= 7;
        /*
         * Since code is always >= 8 bits, only need to mask the first
         * hunk on the left.
         */
        *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
        bp++;
        bits -= (8 - r_off);
        code >>= 8 - r_off;
        /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
        if (bits >= 8) 
	{
            *bp++ = code;
            code >>= 8;
            bits -= 8;
        }
        /* Last bits. */
        if (bits)
            *bp = code;
        offset += n_bits;
        if (offset == (n_bits << 3)) 
	{
	    bcopy(buf, (char *) outbufptr, n_bits);
	    outbufptr += n_bits;
            offset = 0;
        }
         
        /*
         * If the next entry is going to be too big for the code size,
         * then increase it, if possible.
         */
        if (free_ent > maxcode || (clear_flg > 0)) 
	{
            /*
             * Write the whole buffer, because the input side won't
             * discover the size increase until after it has read it.
             */
            if (offset > 0) 
	    {
		bcopy(buf, (char *) outbufptr, n_bits);
		outbufptr += n_bits;
            }
            offset = 0;
         
            if (clear_flg) 
	    {
                maxcode = MAXCODE(n_bits = INIT_BITS);
                clear_flg = 0;
            }
            else 
	    {
                n_bits++;
                if (n_bits == maxbits)
                    maxcode = maxmaxcode;
                else
                    maxcode = MAXCODE(n_bits);
            }
        }       
    }    
    else 
    {
        /*
         * At EOF, write the rest of the buffer.
         */
	if (offset > 0) 
	{
	    bcopy(buf, (char *) outbufptr, (offset + 7) / 8);
	    outbufptr += (offset + 7) / 8;
	}
    }   
}