/*#include <stdio.h>
#include <stdlib.h>*/

#define BITS 12                      /* Setting the number of bits to 12, 13 */
#define HASHING_SHIFT BITS-8         /* or 14 affects several constants.     */
#define MAX_VALUE (1 << BITS) - 1    /* Note that MS-DOS machines need to    */
#define MAX_CODE MAX_VALUE - 1       /* compile their code in large model if */
                                     /* 14 bits are selected.                */
#define TABLE_SIZE 5021

int code_value[TABLE_SIZE * sizeof(int)];                     /* This is the code value array         */
unsigned int prefix_code[TABLE_SIZE * sizeof(int)];           /* This array holds the prefix codes    */
unsigned char append_character [TABLE_SIZE];     /* This array holds the appended chars  */
unsigned char decode_stack[4000];    /* This array holds the decoded string  */

char *outptr;
char *inptr;

char *decode_string(unsigned char *buffer,unsigned int code);

/*
** The following two routines are used to output variable length
** codes.  They are written strictly for clarity, and are not
** particularly efficient.
*/
    volatile static int input_bit_count=0;
    static unsigned long input_bit_buffer=0L;

input_code(void) {
    unsigned int return_value;
    unsigned char a;
    unsigned long x;

    while (input_bit_count <= 24) {
	a = *(unsigned char*)inptr++;
	x = a << ( 24 - input_bit_count );
       input_bit_buffer |= x;
       input_bit_count += 8;
    }
    return_value=input_bit_buffer >> (32-BITS);
    input_bit_buffer <<= BITS;
    input_bit_count -= BITS;

 
    return(return_value);
}
/*
** This routine simply decodes a string from the string table, storing
** it in a buffer.  The buffer can then be output in reverse order by
** the expansion program.
*/
char *decode_string(unsigned char *buffer, unsigned int code) {
int i;

    i=0;
    while (code > 255) {
        *buffer++ = append_character[code];
        code=prefix_code[code];
        if (i++>=4094)
        {
            printf("Fatal error during code expansion.\n");
            exit(1);
        }
    }
    *buffer=code;
    return(buffer);
}

/*
**  This is the expansion routine.  It takes an LZW format file, and expands
**  it to an output file.  The code here should be a fairly close match to
**  the algorithm in the accompanying article.
*/
int expand(char *in, char *out){
    unsigned int next_code;
    unsigned int new_code;
    unsigned int old_code;
    int character;
    int counter;
    unsigned char *string;
    int outsize = 0;

    outptr = out;
    inptr  = in;

    input_bit_count=0;
    input_bit_buffer=0L;

    //printf("expand %X %X\n", in, out);


    next_code=256;          /* This is the next available code to define */

    old_code=input_code();  /* Read in the first code, initialize the */
    character=old_code;          /* character variable, and send the first */
   // printf("%d", (long)character);

    //putc(old_code,output);       /* code to the output file                */
    *outptr++ = old_code;

/*
**  This is the main expansion loop.  It reads in characters from the LZW file
**  until it sees the special code used to inidicate the end of the data.
*/
    while ((new_code=input_code()) != (MAX_VALUE)) {

/*
** This code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
** case which generates an undefined code.  It handles it by decoding
** the last code, adding a single character to the end of the decode string.
*/
        if (new_code>=next_code) {
            *decode_stack=character;
            string=decode_string(decode_stack+1,old_code);
        }
/*
** Otherwise we do a straight decode of the new code.
*/
        else
            string=decode_string(decode_stack,new_code);
/*
** Now we output the decoded string in reverse order.
*/
        character=*string;
        while (string >= decode_stack)
	  *outptr++ = *string--;
      //      putc(*string--,output);
/*
** Finally, if possible, add a new code to the string table.
*/
        if (next_code <= MAX_CODE) {
            prefix_code[next_code]=old_code;
            append_character[next_code]=character;
            next_code++;
        }
        old_code=new_code;
    }
    return (outptr - out);
}
#if 0
void main(int argc, char *argv[]){
    FILE *in,*out;
    char *inbuf, *outbuf;
    int sizeinbuf, sizeoutbuf;

    if (argc < 3) {
	printf("compress input output\n");
	exit(1);
    }

    in = fopen(argv[1], "rb");
    if (in == NULL){
	printf("error on input file\n");
	exit(1);
    }
    out = fopen(argv[2], "wb");
    if (out == NULL){
	printf("error on output file\n");
	exit(1);
    }

    printf("in: %s, out: %s\n",argv[1], argv[2]);

    code_value=malloc(TABLE_SIZE*sizeof(unsigned int));
    prefix_code=malloc(TABLE_SIZE*sizeof(unsigned int));
    append_character=malloc(TABLE_SIZE*sizeof(unsigned char));
    if (code_value==NULL || prefix_code==NULL || append_character==NULL) {
        printf("Fatal error allocating table space!\n");
        exit(1);
    }

    inbuf = malloc (1024*1024*1);
    outbuf = malloc (1024*1024*1);

    sizeinbuf = fread (inbuf, 1, 1024*1024, in);
    printf("input file size = %d\n", sizeinbuf);
    fclose(in);

    sizeoutbuf = expand(inbuf, outbuf, sizeinbuf);
    fwrite (outbuf, 1, sizeoutbuf, out);

    fclose(out);

    free(prefix_code);
    free(append_character);

}
#endif