/*
 * Convert data format of figure
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "bookfile_figure.h"	/* verify prototypes */
#include "bookreader_recdef.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 width, int height );

/*  hdr[2] = section #, hdr[3] = x, hdr[4] = y, hdr[5] = w hdr[6] = h
 *  hdr[7] = picbytes, hdr[8]<0..7> = primitive
 *  data[4..5] col, data[6..7] = rows
 */
int LIB$INIT_TIMER(), LIB$SHOW_TIMER();
int bkg_convert_figure_to_gif ( 
	long hdr[10], 			/* Section header figure subrec */
	unsigned char *data, int datalen,   /* data read from section */
	int (*output)(void*, int, char *), /* User-supplied output function */
	void *outarg )			/* user-arg for output function */
{
    FILE* out;
    int i, j, k, width, height, value, mask, status;
    float aspect;
    short *cols, *rows;
    char trailer[2] = { 0, ';' };
    unsigned char *cur_row, *cur_col;
    unsigned char *pixel_row, *pixel_image;
    int size, count;
#ifdef __DECC
#pragma nomember_alignment
#endif
    struct gif_header {
	char signature[6];		/* GIF87a */
	short width, height;		/* little-endian */
	unsigned char 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 */
	short aspect;			/* aspect ratio */
	unsigned char color_table[6];	/* 2-entry color table */
			/* Image header follows */
	char separator;			/* ',' */
	short left,top;			/* origin */
	short iwidth, iheight;		/* Image size */
	unsigned char iflags;		/* <0..2> pixel depth */
					/* <3..5> mbz */
					/* <6>  Interlace flag */
					/* <7> local color table */
	unsigned char code_size;	/* first byte of image data */
    } header;
#ifdef __DECC
#pragma member_alignment
#endif
    struct bitstream bs;
    /*
     * Get dimensions of image and move data point to start of image bits.
     */
    data += 4;
    cols = (short  *)&data[0]; rows = (short *) &data[2];
    datalen = datalen - 8;
    data += 4;		 /* skip origin and size info */
    width = *cols;
    height = *rows;
    /*
     * Build gif header in structure and output.
     */
    strcpy ( header.signature, "GIF87a" );
    header.width = *cols;
    header.height = *rows;
    header.flags = 0;			/* ASSUME 2^(0+1) = 2 BITS */
    header.flags = header.flags | 0x00080;	/* include GCT */
    header.aspect = 0;
    header.color_table[0] = header.color_table[1] = header.color_table[2] = 0;
    header.color_table[3] = header.color_table[4] = header.color_table[5] = 255;
    header.separator = ',';
    header.left = header.top = 0;
    header.iwidth = width;
    header.iheight = height;
    header.iflags = 0;
    header.code_size = 2;		/* first byte of raster data */

    status = output( outarg, sizeof(header), (char *) &header );
    if ( (status&1) == 0 ) return status;
    /*
     * Initialize data stream structure and do LZ compression on bits.
     * add bits automatically calls output routine when buffer fills.
     */
LIB$INIT_TIMER();
    bs.words_filled = 0;
    bs.bit_off = 8;			/* leave room for count byte. */
    bs.flush = output;
    bs.flush_arg = outarg;
    bs.buffer[0] = 0;

    status = compress_data ( &bs, 2, data, width, height );
    if ( (status&1) == 0 ) return status;
    /*
     * Flush remaining bits in buffer and add final trailer bytes.
     */
    count = bs.words_filled*4 + (bs.bit_off+7)/8;	/* include whole byte */
    if ( count > 1 ) {
	bs.buffer[0] |= (count-1);
        status = output ( outarg, count, (char *) bs.buffer );
	if ( (status&1) == 0 ) return status;
    }

    status = output ( outarg, 2, trailer );
    if ( (status&1) == 0 ) return status;
LIB$SHOW_TIMER();
    return status;
}
/*
 * GIF encoder.  
 *
 *     The Graphics Interchange Format(c) is the Copyright property of
 *     CompuServe Incorporated. GIF(sm) is a Service Mark property of 
 *     CompuServe Incorporated."
 *
 */


/*****************************************************************************/
static unsigned bmask[33] = { 
	0, 1, 3, 7, 15, 31, 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;
#ifdef DEBUG
printf("<%d,%d=%d>", off, size, value );
#endif
    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;
	if ( ov_bits > 0 ) {
	    low = (value & bmask[size-ov_bits]);
	    bs->buffer[cur++] |= (low<<off);
	}
#ifdef DEBUG
printf("buf[%d]=%x\n", cur-1, bs->buffer[cur-1] );
#endif
	if ( cur > 62 ) {
	    long bcount;
	    bcount = cur*4;
	    bs->buffer[0] |= (bcount-1);	/* load first (low) byte */
	    
	    status = bs->flush ( bs->flush_arg, cur*4, (char *)bs->buffer );
	    if ( (status&1) == 0 ) return cur;
	    value = (value & (~bmask[size-ov_bits]));	/* zero field */
	    value = value << 8;   /* make room for count */
	    ov_bits += 8;
	    size += 8;
	    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 13
#define HASH_TABLE_SIZE 8192
    int hash_shift;			/* shift for charval in hash func */
    struct code_t_entry table[4096];	/* code table */
    short hash_table[HASH_TABLE_SIZE];
};
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]; * /
    max_hash = bmask[HASH_BITS];	/* optimize for 1 bit data */
    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;
    }
    for ( ; i < 4096; i++ ) table[i].prefix = table[i].code = 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 width, int height )
{
    int code, prefix, current, new, out_size, i, j, hashval;
    int code_limit, value, mask;
    unsigned char *dptr, *data_end;
    struct code_t_entry *table;
    short *hash_table;
    struct lz_state lz;

    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 );
    value = *dptr++;
    prefix = (value&1) ? 0 : 1;		/* first bit */
    mask = 2;
    for ( i = 0; i < height; i++ ) {
    for ( j = (i==0) ? 1 : 0; j < width; j++ ) {
	/*
	 * Extract next bit from input bits.
	 */
	current = ((value&mask) != 0) ? 0 : 1;
	mask *= 2;
	if ( mask > 128 ) { mask = 1; value = *dptr++; }
	/* 
	 * Find prefix//current table entry 
	 */
	/* hashval = (lz.max_hash&((current<<lz.hash_shift) ^ prefix)); */
	hashval = (current << 12) |  prefix;   /* optimized */
	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 = lz.clear;
		initialize_lz_state ( &lz, code_size );
#ifdef DEBUG
printf("Reset code table, out_size %d, clear=%d\n", lz.out_size,  lz.clear );
#endif
		out_size = lz.out_size;
		code_limit = bmask[out_size];

		prefix = ((value&mask) != 0) ? 0 : 1;
		mask *= 2;
		if ( mask > 128 ) { mask = 1; value = *dptr++; }
		j++; if ( j >= width ) break;
	    } 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;
	    }
	    
	}
    }
    if ( mask != 1 ) {	/* wrap to next byte at eol */
	mask = 1; value = *dptr++;;
    }
    }
    /*
     * Flush remaining to output.
     */
    add_bits ( bs, prefix, out_size );
    if ( i >= height ) { add_bits ( bs, lz.eoi, out_size ); return 1; }

    return 1;
}