/*
 * GIF encoder.  
 *
 *     The Graphics Interchange Format(c) is the Copyright property of
 *     CompuServe Incorporated. GIF(sm) is a Service Mark property of 
 *     CompuServe Incorporated."
 *
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct bitstream {
    int words_filled;		/* Completed words */
    int bit_off;		/* bits written to current word */
    int (*flush)(void *,int,char *);
    void *flush_arg;
    unsigned long buffer[65];
};
static int add_bits ( struct bitstream *bs, int value, int size );
static int compress_data ( struct bitstream *bs, 
	int code_size, unsigned char *data, int length );

/*****************************************************************************/
/*
 */
int write_gif_header ( 
	int width, int height, 		/* Size of screen */
	int gct_size,                   /* Number of entries in color table */
	unsigned char *gct, 		/* Color table 3 bytes/entry  (r,g,b)*/
	int background,			/* Background color pixel index*/
	int (*output)(void*, int, char *), /* output function */
	void *outarg )			/* user-arg for output routine*/
{
    int size, count;
#ifdef __ALPHA
#pragma nomember_alignment
#endif
    struct gif_header {
	char signature[6];		/* GIF87a */
	short width, height;		/* little-endian */
	int flags;			/* <0..2> gct_size (2**(val+1)). */
					/* <3> color table sorted */
					/* <4..6> out device clr res (7)*/
					/* <7> Global color table if set */
    } header;
#ifdef __ALPHA
#pragma member_alignment
#endif

    /*
     * Build gif header in structure.
     */
    strcpy ( header.signature, "GIF87a" );
    header.width = width;
    header.height = height;
    header.flags = 0;			/* ASSUME 2^(0+1) = 2 BITS */
    header.flags = header.flags | (background*256) | 0x00080;
    for ( size = 2; size < gct_size; size = size * 2 ) header.flags++;
    /*
     * Send header and color table using caller-supplied output function.
     */
    count = output( outarg, 13, (char *) &header );
    count = output( outarg, gct_size*3, (char *) gct );
    return count;
}
/*****************************************************************************/
/*
 */
int write_gif_image ( 
	int width, int height, 		/* Size of image */
	int max_pixel,			/* Highest pixel value in image */
 	unsigned char *image, 		/* Image data, 1 byte/pixel */
	int interlace,			/* Only set if you've interlaced image*/
	int (*output)(void*, int, char *), /* User-supplied output function */
	void *outarg )			/* user-arg for output function */
{
    int size, status, count, bits;
#ifdef __ALPHA
#pragma nomember_alignment
#endif
    struct {
	char align_fill;
	char separator;
	short left, top;		/* x, y offset of origin */
	short width, height;		/* size of image */
	int flags;			/* <0..2> pixel depth */
					/* <3..5> mbz */
					/* <6>  Interlace flag */
					/* <7> local color table */
    } header;
#ifdef __ALPHA
#pragma member_alignment
#endif
    int prefix, clear, eoi;
    struct bitstream bs;
    char trailer[2] = { '\0', ';' };
    /*
     * Construct image header and write it, assume no local color table.
     */
    header.separator = ',';
    header.left = header.top = 0;
    header.width = width;
    header.height = height;

    header.flags = 0;		/* depth of 2 */
    if ( interlace ) header.flags |= 64;

     count = output (outarg,10, (char *) &header.separator );
    /*
     * Determine number of bits needed to hold max_pixel, minimum 2, and output.
     */
    for ( bits = 2, size = 4; size < max_pixel; size = size * 2 ) bits++;
    status = output ( outarg, 1, (char *) &bits );
     /*
      * Initilize structure used for packing variable sized bits fields.
      * Include poitner to output function so add_bits can flush accumulated
      * data as needed.
      */
    bs.words_filled = 0;
    bs.bit_off = 0;
    bs.flush = output;
    bs.flush_arg = outarg;
    bs.buffer[0] = 0;
    /*
     * Compress the data, when done flush any remaining data in bs buffer.
     */
    status = compress_data ( &bs, bits, image, width * height );

    count = bs.words_filled*4 + (bs.bit_off+7)/8;	/* include whole byte */
    if ( count > 0 ) {
        status = output ( outarg, 1, (char *) &count );
        status = output ( outarg, count, (char *) bs.buffer );
    }
    /*
     * Send final 0 byte to end image data and ';' to end gif.
     */
    status = output ( outarg, 2, trailer );
    return status;
}

static unsigned bmask[32] = { 
	0, 1, 3, 7, 15, 63, 127, 255, 
	511, 1023, 2047, 4095, 8191, 0x03fff, 0x07fff, 0x0ffff, 
	0x01ffff, 0x03ffff, 0x07ffff, 0x0fffff, 
	0x01fffff, 0x03ffff, 0x07ffff, 0x0ffffff,
	0x01ffffff, 0x03fffff, 0x07fffff, 0x0ffffff,
	0x1fffffff, 0x3ffffff, 0x7ffffff, 0xffffffff };


static int add_bits ( struct bitstream *bs, int value, int size )
{
    int cur, pos, off, ov_bits, status;
    unsigned low;

    cur = bs->words_filled;
    off = bs->bit_off;

    if ( off + size <= 32 ) {
	/*
	 * All fits in current longword of buffer.
	 */
	low = (value &bmask[size]);
	bs->buffer[cur] |= (low << off);
	bs->bit_off = off + size;
    } else {
	/*
	 * value straddles two longwords.
	 */
	ov_bits = size + off - 32;
	low = (value & bmask[size-ov_bits]);
	bs->buffer[cur++] |= (low<<off);
	if ( cur > 62 ) {
	    unsigned char bcount;
	    bcount = cur*4;
	    status = bs->flush ( bs->flush_arg, 1, (char *)&bcount );
	    status = bs->flush ( bs->flush_arg, cur*4, (char *)bs->buffer );
	    cur = 0;
	}

	low = value;
	low = (low>>(size-ov_bits));
	bs->buffer[cur] = (low & bmask[ov_bits]);
	bs->bit_off = ov_bits;
    }
    bs->words_filled = cur;
    return cur;
}

struct code_t_entry {
    short prefix, code, next_hash;
};

struct lz_state {
    int code_size;			/* Number of bits of input size */
    int clear;				/* value of clear code (2^code_size) */
    int eoi;				/* End-of-info code (clear+1); */
    int out_size;
    int max_code;			/* hight entry in code_table */
    int max_hash;
#define HASH_BITS 18
#define HASH_TABLE_SIZE 262144
    int hash_shift;			/* shift for charval in hash func */
    struct code_t_entry table[4096];	/* code table */
    short hash_table[262144];
};
typedef struct lz_state *lzptr;

static int initialize_lz_state ( lzptr lz, int code_size )
{
    int i, max_code, max_hash;
    struct code_t_entry *table;
    short *hash;

    lz->code_size = code_size;
    lz->clear = 1;
    for ( i = 0; i < code_size; i++ ) lz->clear *= 2;
    lz->eoi = lz->clear+1;
    lz->out_size = code_size + 1;
    lz->max_code = max_code = lz->eoi;

    max_hash = HASH_TABLE_SIZE;
    lz->hash_shift = 12;
    while ( (code_size+lz->hash_shift) > HASH_BITS) {
	lz->hash_shift = lz->hash_shift - 1;
    }
    max_hash = bmask[code_size+lz->hash_shift];
    lz->max_hash = max_hash;
    /*
     * Initialize the tables.
     */
    table = lz->table;
    for ( i = 0; i <= max_code; i++ ) { 
	table[i].prefix = -1; table[i].code = i; table[i].next_hash = 0;
    }

    hash = lz->hash_table;
    for ( i = 0; i < max_hash; i++ ) hash[i] = 0;

    return 1;
}


static int compress_data ( struct bitstream *bs, 
	int code_size, unsigned char *data, int length )
{
    int stack[4100], *stackptr;
    int code, prefix, current, new, prev_code, out_size, i, hashval;
    int code_limit;
    unsigned char *dptr, *data_end;
    struct code_t_entry *table;
    short *hash_table;
    struct lz_state lz;

    data_end = &data[length];
    dptr = data;

    initialize_lz_state ( &lz, code_size );
    table = lz.table;
    hash_table = lz.hash_table;
    out_size = lz.out_size;
    code_limit = bmask[out_size];

    add_bits ( bs, lz.clear, out_size );
    prefix = *dptr++;
    while ( dptr < data_end ) {
	current = *dptr++;
	/* Find prefix//current table entry */
	hashval = (lz.max_hash&((current<<lz.hash_shift) ^ prefix));
	code = hash_table[hashval];
	while ( code  ) {
	    if ( (table[code].prefix == prefix) && 
		 (table[code].code == current) ) break;

	    code = table[code].next_hash;
	}
	/*
	 * If code is non-zero, current prefix//code found in table and i is
	 * the code.  Make it the prefix and continue loop;
	 */
	if ( code ) {
	    prefix = code;
	} else {
	    /*
	     * Entry not found, output current prefix.
	     */
	    add_bits ( bs, prefix, out_size );
	    /* prefix = current; */
	    /*
	     * Add new entry to table and update output size.
	     */
	    new = ++lz.max_code;
	    if ( new > code_limit ) {
	        out_size++;
	        code_limit = code_limit*2 + 1;
	    }
	    if ( new > 4092 ) {
		/* Reset so we don't overflow */
		add_bits ( bs, current, out_size );
		add_bits ( bs, lz.clear, out_size );
		current = prefix = lz.clear;
		initialize_lz_state ( &lz, code_size );
printf("Reset code table, out_size %d\n", lz.out_size);
		out_size = lz.out_size;
		code_limit = bmask[out_size];
	    } else {
	        lz.table[new].prefix = prefix;
	        lz.table[new].code = current;
	        lz.table[new].next_hash = hash_table[hashval];
	        lz.hash_table[hashval] = new;


	        /* prefix for next value */
	    
	    }
	        prefix = current;
	}
    }
    /*
     * Flush remaining to output.
     */
    add_bits ( bs, prefix, out_size );
    if ( dptr >= data_end ) { add_bits ( bs, lz.eoi, out_size ); return 1; }

    return 1;
}