/* File name:	LZW.C			Revision date:	1993.08.06
 *
 *
 */

#ifndef TYPEDEF
typedef long int                count_int;
typedef short int               code_int;
typedef unsigned short int      ucode_int;
typedef long int                buff_int;
typedef unsigned char           char_type;
#endif

#define CHK_POINT 1000
#define HSIZE 5003
#define LZ_MAXBITS    12
#define MAXMAXCODE (short int)(1<<LZ_MAXBITS)   /* should NEVER generate this code */
#define BLCOMP  0x80                            /* if 0 htable won't be refresed
                                         automaticaly */

typedef struct {
        code_int  n_bits;                    /* number of bits/code */
        code_int  maxcode;                   /* maximum code, given n_bits */
        count_int htab[HSIZE];
        unsigned short  codetab[HSIZE];
        code_int hsize_reg;
        code_int hshift;
        code_int free_ent ;                  /* first unused entry */

        code_int   clear_flg ;               /*flag to clear tables */
        count_int  ratio ;
        count_int  checkpoint;

        count_int    in_count ;              /* length of input record */
        count_int    bytes_out_all;          /* count all bytes in file */
        count_int    out_count;              /* # of codes output  */

        short int    new_file_flag;          /* if 0 refresh tables and turn to 1*/
                                            /* mast be set while lzopen()
*/
        code_int  offset;                       /* do not warry, it's for bits packeges */
        buff_int bytes_out;                     /* length of compressed output */
        buff_int bytes_in;

}  LZ_COMP;

/*=====================================================================================*
*Functions:                                                                            *
*  void lzopen (&hendle) - allocate memory for compress process               *
*                                                                                      *
*  void lzcomp (p_in,&bytes_in, p_out, &bytes_out, handle) -                       *
*           compress p-in which is the length of bytes_in in p_out which                     *
*           is the length of bytes_out                                                       *
*                                                                                      *
*  void lzdecomp (p_out, &bytes_out, p_in, &bites_in, handle) -                     *
*            decompress p_out which is the length of bytes_out in p_in which           *
*            is the length of bytes_in                                                 *
*                                                                                      *
*Parameters:                                                                           *
*  LZ_COMP *handle     - pointer to tables of current compression stream                        *
*                                                                                      *
*  char_type *p_in - pointer to input record to be compressed for compression          *
*  function pointer on decompressed record for decompression function                  *
*                                                                                      *
*  unsigned short bytes_in - nuber of bytes in the p_in record                         *
*                                                                                      *
*  char_type *p_out    - pointer on compressed record in compressed and                *
*  decompressed functions                                                                *
*                                                                                      *
*  unsigned short bytes_out- nuber of bytes in the p_out record                        *
*                                                                                      *
*Do not forget:                                                                        *
*                                                                                      *
*#include <stdio.h>                                                                    *
*#include <string.h>                                                                   *
*#include "lz.h"                                                                       *
*                                                                                      *
*======================================================================================*/
/*------------------------------------------------------------------*/

lzopen(handle)
LZ_COMP **handle;
 {
        *handle=(LZ_COMP *)malloc(sizeof(LZ_COMP));
        (*handle)->new_file_flag=1;
        return;
 }

/*------------------------------------------------------------------*/

lzclose(handle)
LZ_COMP *handle;
{
        free(handle);
        return;
 }

/*------------------------------------------------------------------*/
lzcomp(p_in, in_length, p_out, out_length, handle)

char_type       *p_in,     *p_out;
buff_int        *in_length, *out_length;
LZ_COMP *handle;
{

        long int        fcode;

        register code_int  disp;
        register code_int  c;
        static code_int  ent;
        register int    i ;

        handle->bytes_in = *in_length;


  if( handle->new_file_flag == 1 ){   /* if first record - refresh tables */

        handle->new_file_flag=0;

                handle->offset = 0;
                handle->n_bits = 9;
                handle->bytes_out_all = 0;
                handle->out_count = 0;
                handle->clear_flg = 0;
                handle->ratio = 0;
                handle->in_count = 1;
                handle->checkpoint =  CHK_POINT;
                handle->maxcode = ((1 << (handle->n_bits = 9)) - 1);
                handle->free_ent = ((BLCOMP) ? 257 : 256 );

                handle->hshift = 0;
                for ( fcode = (long) HSIZE; fcode < 65536L; fcode *= 2L )
                        handle->hshift++;
                handle->hshift = 8 - handle->hshift;            /* set hash code range bound */

                handle->hsize_reg = HSIZE;
                cl_hash(handle);             /* clear hash table */

        }

        ent = *p_in++;
        handle->bytes_in--;
        handle->bytes_out = 0;

        while (handle->bytes_in-- > 0) {

                c = *p_in++;
                handle->in_count++;
                fcode = (long) (((long) c << LZ_MAXBITS) + ent);
                i = ((c << handle->hshift) ^ ent);      /* xor hashing */

                if ( handle->htab[i] == fcode ) {
                        ent = handle->codetab[i];
                        continue;
                } else if ( (long)handle->htab[i] < 0 ) /* empty slot */
                        goto nomatch;
                disp = handle->hsize_reg - i;           /* secondary hash (after G. Knott) */
                if ( i == 0 )
                        disp = 1;
probe:
                if ( (i -= disp) < 0 )
                        i += handle->hsize_reg;

                if ( handle->htab[i] == fcode ) {
                        ent = handle->codetab[i];
                        continue;
                }
                if ( (long)handle->htab[i] > 0 )
                        goto probe;
nomatch:
                p_out += output (p_out, (code_int) ent , handle);
                handle->out_count++;
                ent = c;

                if ( handle->free_ent < MAXMAXCODE ) {
                        handle->codetab[i] = handle->free_ent++;        /* code -> hashtable */
                        handle->htab[i] = fcode;
                } else if ( ((count_int)handle->in_count >= handle->checkpoint) &&
                    BLCOMP )
                        p_out += cl_block (p_out, handle);
        }

        /* Put out the final code. */
        p_out += output(p_out, (code_int)ent , handle);
        handle->out_count++;
        p_out += output(p_out, (code_int) - 1 , handle);
        handle->bytes_out_all += handle->bytes_out;

        *out_length=handle->bytes_out;
        return;
}


/*****************************************************************/

output(p_out, code, handle)
char_type  *p_out;
code_int   code;
LZ_COMP *handle;
{

static char_type        buf[12];

static char_type lmask[9] = {
        0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00            };

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


        register code_int       r_off = handle->offset;
        code_int bits = handle->n_bits;
        register char_type      *bp = p_out;

        register buff_int       nw = 0;

        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  */
                if ( bits >= 8 ) {
                        *bp++ = code;
                        code >>= 8;
                        bits -= 8;
                }
                /* Last bits. */
                if (bits)
                        *bp = code;
                handle->offset += handle->n_bits;
                if ( handle->offset == (handle->n_bits << 3) ) {
                        bp = buf;
                        bits = handle->n_bits;
                        handle->bytes_out += bits;
                        nw = bits;
                        handle->offset = 0;
                }

                /*
 * If the next entry is going to be too big for the code size,
 * then increase it, if possible.
 */
                if ( handle->free_ent > handle->maxcode || (handle->clear_flg > 0)) {
                        /*
 * Write the whole buffer, because the input side won't
 * discover the size increase until after it has read it.
 */
                        if ( handle->offset > 0 ) {
                                nw = handle->n_bits;
                                handle->bytes_out += handle->n_bits;
                        }
                        handle->offset = 0;

                        if ( handle->clear_flg ) {
                                handle->maxcode = ((1 << (handle->n_bits = 9)) - 1);
                                handle->clear_flg = 0;
                        } else {
                                handle->n_bits++;
                                if ( handle->n_bits == LZ_MAXBITS )
                                        handle->maxcode = MAXMAXCODE;
                                else
                                        handle->maxcode = ((1 << (handle->n_bits)) - 1);
                        }

                }
        } else {
                /*
 * Write the rest of the buffer.
 */
                if ( handle->offset > 0 ) {
                        handle->bytes_out += (handle->offset + 7) / 8;
                        nw = (handle->offset + 7) / 8;
                }
                handle->offset = 0;

        }
        return(nw);
}


/*----------------------------------------------------------------*/

lzdecomp(p_in, in_length, p_out, out_length, handle)
char_type       *p_in, *p_out;
buff_int        *in_length,*out_length;

LZ_COMP *handle;

{
        static char_type *stackp;
        code_int finchar, oldcode;
        code_int code;
        code_int incode;
        int     stack_size = 0;
        int     i;

        handle->bytes_out = 0;

 if(handle->new_file_flag== 1){

       handle->new_file_flag=0;
       handle->offset = 0;

                /*
 * As above, initialize the first 256 entries in the table.
 */
                handle->maxcode = ((1 << (handle->n_bits = 9)) - 1);
                for ( code = 256; code > 0; code--) {

                        handle->codetab[code-1] = 0;
                        ((char_type * )(handle->htab))[code-1] = (char_type)(code - 1);
                }
                handle->free_ent = ((BLCOMP) ? 257 : 256 );


        }

        handle->bytes_in = *in_length;

        code = getcode(handle,&p_in);
        incode = code;
        stackp = p_out;

        while ( code >= 256 ) {
                *stackp++ = ((char_type * )(handle->htab))[code];
                stack_size++;
                code = handle->codetab[code];
        }
        *stackp++ = finchar = ((char_type * )(handle->htab))[code];
        stack_size++;

        for (i = 0; i < (stack_size + 1) / 2; i++) {
                char_type ch;

                ch = *(p_out + i);
                *(p_out + i) = *(stackp - i - 1);
                *(stackp - i - 1) = ch;
        }
        handle->bytes_out += stack_size;
        stack_size = 0;
        p_out = stackp;

        oldcode = incode;

        while ( (code = getcode(handle,&p_in)) > -1 ) {


                if ( (code == 256) && BLCOMP ) {
                        for ( code = 255; code >= 0; code--)
                                handle->codetab[code] = 0;
                        handle->clear_flg = 1;
                        handle->free_ent = 256;

                        if ( (code = getcode (handle,&p_in)) <= -1 )
                                /* O, untimely death! */
                                break;
                }
                incode = code;
                /*
 * Special case for KwKwK string.
 */
                if ( code >= handle->free_ent ) {
                        *stackp++ = finchar;
                        stack_size++;
                        code = oldcode;
                }

                /*
 * Generate output characters in reverse order
 */

                while ( code >= 256 ) {
                        *stackp++ = ((char_type * )(handle->htab))[code];
                        stack_size++;
                        code = handle->codetab[code];
                }
                *stackp++ = finchar = ((char_type * )(handle->htab))[code];
                stack_size++;

                /*
 * And put them out in forward order
 */

                for (i = 0; i < (stack_size + 1) / 2; i++) {
                        char_type ch;

                        ch = *(p_out + i);
                        *(p_out + i) = *(stackp - i - 1);
                        *(stackp - i - 1) = ch;
                }
                handle->bytes_out += stack_size;
                stack_size = 0;
                p_out = stackp;

                /*
 * Generate the new entry.
 */

                if ( (code = handle->free_ent) < MAXMAXCODE ) {

                        handle->codetab[code] = (unsigned short)oldcode;

                        ((char_type * )(handle->htab))[code] = finchar;

                        handle->free_ent = code + 1;
                }
                /*
 * Remember previous code.
 */
                oldcode = incode;
        }

        *out_length=handle->bytes_out;
        return;

}


/******************************************************************/
getcode(handle,pp_in)
LZ_COMP *handle;
char_type **pp_in;

{
static char_type        buf[12];
static char_type rmask[9] = {
        0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff            };

        register code_int code;
        register char_type *bp = buf;

        static code_int  size = 0;
        static code_int r_off, bits;

        if ( handle->clear_flg > 0 || handle->offset >= size || handle->free_ent >
            handle->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 ( handle->free_ent > handle->maxcode ) {
                        handle->n_bits++;
                        if ( handle->n_bits == LZ_MAXBITS )
                                handle->maxcode = MAXMAXCODE;
                                /* won't get any bigger now */
                        else
                                handle->maxcode = ((1 << (handle->n_bits)) - 1);
                }
                if ( handle->clear_flg > 0) {
                        handle->maxcode = ((1 << (handle->n_bits = 9)) - 1);
                        handle->clear_flg = 0;

                }


                if ( handle->bytes_in == 0)
                        return - 1;

                if ( handle->n_bits <= handle->bytes_in ) {

                        bp = buf;

                        (void) memcpy(bp,*pp_in, handle->n_bits);
                        size= handle->n_bits;
                        *pp_in+=size;
                        handle->bytes_in-=handle->n_bits;


                }  else {

                        bp = buf;
                        (void) memcpy(bp,*pp_in, handle->bytes_in);
                        size= handle->bytes_in;
                        *pp_in+=size;
                        handle->bytes_in=0;

                }

                handle->offset = 0;
                /* Round size down to integral number of codes */
                size = (size << 3) - (handle->n_bits - 1);
        }
        r_off = handle->offset;
        bits = handle->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;
        handle->offset += handle->n_bits;

        return code;
}


/*------------------------------------------------------------------*/

cl_block (p_out, handle)         /* table clear for block compress */
char_type  *p_out;
LZ_COMP *handle;
{
        register long int       rat;

        buff_int nw = 0;

        handle->checkpoint = handle->in_count + CHK_POINT;


        if (handle->in_count > 0x007fffff) {    /* shift will overflow */
                rat = (handle->bytes_out_all + handle->bytes_out) >> 8;
                if (rat == 0) {         /* Don't divide by zero */
                        rat = 0x7fffffff;
                } else {
                        rat = handle->in_count / rat;
                }
        } else {
                rat = (handle->in_count << 8) / (handle->bytes_out_all + handle->bytes_out);
                /* 8 fractional bits */
        }


        if ( rat > handle->ratio ) {
                handle->ratio = rat;
                nw = 0;

        } else {
                handle->ratio = 0;

                cl_hash ( handle );
                handle->free_ent = 257;
                handle->clear_flg = 1;
                putchar('/');
                nw = output ( p_out, (code_int) 256, handle );

        }
        return nw;
}


/*------------------------------------------------------------------*/
cl_hash(handle)           /* reset code table */
LZ_COMP *handle;
{


        register count_int *htab_p = handle->htab;
        register long   i;
        register long   m1 = -1;


        for (i = 0; i < HSIZE; i++)
                *htab_p++ = m1;

}

/*	End of file:	LZW.C		*/
