#include <stdio.h>

/*
#  define arch_is_big_endian 1
#if arch_is_big_endian
#  define assign_ushort(a,v) a = ((v) >> 8) + ((v) << 8)
#else
#  define assign_ushort(a,v) a = (v)
#endif
*/

#if IRIX || ULTRIX
#  define assign_ushort(a,v) a = (v)
#else
#  define assign_ushort(a,v) a = ((v) >> 8) + ((v) << 8)
#endif

#define byte unsigned char
#define ushort unsigned short
#define ulong unsigned long

putgifheader(file,xsize,ysize)
FILE *file;
int xsize;
int ysize;
{
  struct {
    byte	signature[3];	/* magic number == 'GIF' */
    byte	version[3];	/* version # '87a' or '89a' */
    ushort	width;		/* screen width */
    ushort	height;		/* screen height */
    
    /*	struct	{		/* bit structure of flags */
    /*	unsigned globalcolor:1;	/* global color table flag - MSB*/
#define globalcolor_shift 7
    /*	unsigned colorres:3;	/* bits/color */
#define colorres_shift 4
    /*	unsigned sort:1;		/* color table sorted */
#define sort_shift 3
    /*	unsigned colorsize:3;	/* 2^colorsize bytes in color table -LSB */
#define colorsize_shift 0
    /*	} flags;		*/
    
    byte 	flags;
    byte	background;	/* background color index */
    byte	aspect;		/* pixel aspect ratio */
    /* ratio = (aspect + 15) / 64 */
  } header;
  
  struct {
    byte red,green,blue;
  } palette_entry;
  
  memcpy(header.signature, "GIF", 3);
  memcpy(header.version, "87a", 3);
  assign_ushort(header.width, xsize);
  assign_ushort(header.height, ysize);
  /*	header.flags.globalcolor = TRUE;	*/
  /*	header.flags.colorres = depth-1;	*/
  /*	header.flags.sort = FALSE;		*/
  /*	header.flags.colorsize = depth-1;	*/
  header.flags = 0xf0;
  header.background = 0;
  header.aspect = 0;
  
  if ( fwrite(&header, 1, 13, file) < 13 ) {
    fprintf(stderr,"Error in GIF file\n");
    exit(1);
  };
  
  palette_entry.red=255;
  palette_entry.green=255;
  palette_entry.blue=255;
  if ( fwrite(&palette_entry, 1, 3, file) < 3 ) {
    fprintf(stderr,"Error in GIF file\n");
    exit(1);
  };
  
  palette_entry.red=0;
  palette_entry.green=0;
  palette_entry.blue=0;
  if ( fwrite(&palette_entry, 1, 3, file) < 3 ) {
    fprintf(stderr,"Error in GIF file\n");
    exit(1);
  };
  
}

putimageheader(file,xsize,ysize)
FILE *file;
int xsize;
int ysize;
{
  struct  {
    ushort	left_pos;	/* image left pos (pixels) */
    ushort	top_pos;	/* image top  pos (pixels) */
    ushort	width;		/* image width    (pixels) */
    ushort	height;		/* image height   (pixels) */
    
    /*	struct	{		*/
    /*	unsigned localcolor:1;	/* local color table flag */
    /*	unsigned interlace:1;	/* image interlaced  0=no */
    /*	unsigned sort:1;	/* color table sorted 0=no*/
    /*	unsigned resv:2;	*/
    /*	unsigned localsize:3;	/* 2^localsize+1 = color table size */
    /*	} flags;		*/

    byte	flags;
  } header_desc;
  
  header_desc.left_pos = 0;
  header_desc.top_pos = 0;
  assign_ushort(header_desc.width, xsize);
  assign_ushort(header_desc.height, ysize);
  header_desc.flags = 0;
  fputc(0x2c,file);		/* start with separator */
  if ( fwrite(&header_desc, 1, 9, file) < 9 ) {
    fprintf(stderr,"Error in GIF file\n");
    exit(1);
  };
}

/********************************************************/
/* LZW routines are based on:				*/
/* Dr. Dobbs Journal --- Oct. 1989. 			*/
/* Article on LZW Data Compression by Mark R. Nelson 	*/
/********************************************************/

#define MAX_BITS 12		/* this is max for GIF. */

#define TABLE_SIZE 5123		/* this is max for 12-bit codes */
#define TABLE_HASH_SHIFT 2	/* size < 4095 + (4095 >> shift) */
#define uint unsigned int

/* State of LZW encoder */
typedef struct code_entry_s {
	int	code_value;
	ushort	prefix_code;
	byte	append_character;
} code_entry;
typedef struct lzw_encoder_s {
	int	bits;
	ushort	Max_Code;
	ushort	Clear_code;
	ushort	next_code;
	FILE	*file;
	code_entry	*table;
	ushort	string_code;
	/* State of output buffer */
	byte	output_bit_buffer;
	int	output_bit_count;	/* # of valid low-order bits */
					/* (between 0 and 7) in buffer */
	uint	byte_count;
	byte	gif_buffer[260];
} lzw_encoder;

/* Initialize LZW encoder */
void lzw_set_bits();
void lzw_reset();
int
lzw_init(pe, bits, file)
register lzw_encoder *pe;
int bits;
FILE *file;
{	lzw_set_bits(pe, bits);
	pe->Clear_code = (1 << bits);
	pe->file = file;
	pe->byte_count = 1;
	pe->output_bit_count = 0;
	pe->output_bit_buffer = 0;
	pe->table = (code_entry *)malloc(TABLE_SIZE*sizeof(code_entry));

	if ( pe->table == 0 )
		{fprintf(stderr,"Can't allocate buffer\n");
		 exit(1);
		 };	/* can't allocate buffers */

	lzw_reset(pe);
	pe->string_code = 0;
	return 0;
}
/* Establish the width of the code in bits */
void
lzw_set_bits(pe, bits)
register lzw_encoder *pe;
int bits;
{	pe->bits = bits;
	pe->Max_Code = (1 << (bits+1)) - 1;
}
/* Reset the encoding table */
 void
lzw_reset(pe)
register lzw_encoder *pe;
{	int index;
	for ( index = 0; index < TABLE_SIZE; index++ )
		pe->table[index].code_value = -1;
	pe->next_code = pe->Clear_code + 2;
}

/* Put out (data) of length (bits) to GIF buffer */
void
lzw_putc(pe, data)
register lzw_encoder *pe;
uint data;
{	int bits = pe->bits + 1;	/* output width */
	ulong buffer = pe->output_bit_buffer | ((ulong)data << pe->output_bit_count);
	pe->output_bit_count += bits;
	while ( pe->output_bit_count >= 8 )
	{	/* putc(output_bit_buffer >> 24, file); */
		pe->gif_buffer[pe->byte_count] = (byte)buffer;  /* low byte */
		buffer >>= 8;
		pe->output_bit_count -= 8;
		pe->byte_count++;
		if ( pe->byte_count == 256 )
		{	pe->byte_count = 1;
			pe->gif_buffer[0] = 255;  /* byte count for block */
			fwrite(pe->gif_buffer, 1, 256, pe->file);
		}
	}
	pe->output_bit_buffer = (byte)buffer;
}

/* Finish encoding, and flush the buffers. */
 void
lzw_finish(pe)
register lzw_encoder *pe;
{	lzw_putc(pe, pe->string_code);	/* output last code */
	lzw_putc(pe, pe->Clear_code+1);	/* output eof code */
	lzw_putc(pe, 0);	/* force out last code */
	if ( pe->byte_count != 1 )
	{	pe->gif_buffer[0] = pe->byte_count;
		fwrite(pe->gif_buffer, 1, pe->byte_count+1, pe->file);
	}
}

/* Terminate LZW encoder. */
 void
lzw_exit(pe)
register lzw_encoder *pe;
{	free((char *)pe->table);
}

/* Get the next (depth) bits from the pixel buffer. */
/* Note that 8 % depth == 0. */
/* Free variables: bits_left, bit_buffer, next, depth, depth_mask. */
#define lzw_getc()\
 (bits_left =\
  (bits_left == 0 ?\
   (bit_buffer = *(next++), 8 - (depth)) :\
   bits_left - (depth)),\
  (bit_buffer >> bits_left) & (depth_mask))

/* Output 1 row of data in GIF (LZW) format. */
void
lzw(from, end, pe, depth)
byte *from;
byte *end;
register lzw_encoder *pe;
int depth;
{	int bits_left = 0;
	uint bit_buffer;
	byte *next = from;
	uint depth_mask = (1 << depth) - 1;

	if ( pe->next_code == (pe->Clear_code + 2))	/* first time through */
	{	pe->string_code = lzw_getc();
	}

	while ( next < end || bits_left >= depth )
	{	uint	data = lzw_getc();  /* actually only a byte */

		/* Hash to find a match for the prefix+char */
		/* string in the string table */

		ushort	hash_prefix = pe->string_code;
		int	index = (data << 4) ^ hash_prefix;
		int	hash_offset;
		register code_entry *pce;

		index += index >> TABLE_HASH_SHIFT;
		if ( index == 0 )
			hash_offset = 1;
		else
			hash_offset = TABLE_SIZE - index;

		while ( 1 )
		{	pce = &pe->table[index];
			if ( pce->code_value == -1 )
				break;
			if ( pce->prefix_code == hash_prefix && 
			     pce->append_character == data )
				break;
			index -= hash_offset;
			if ( index < 0 )
				index += TABLE_SIZE;
		}
		if ( pce->code_value != -1 )
			pe->string_code = pce->code_value;
		else
		{	/* Make a new entry */
			pce->code_value = pe->next_code++;
			pce->prefix_code = pe->string_code;
			pce->append_character = data;

			lzw_putc(pe, pe->string_code);

			if ( pe->next_code > (pe->Max_Code + 1) )
			{	/* Increment the width of the code */
				if ( pe->bits+1 >= MAX_BITS )
				{	/* output clear code first*/
					lzw_putc(pe, pe->Clear_code);
					pe->bits = (depth == 1 ? 2 : depth);
					lzw_reset(pe);
				}
				else
					pe->bits++;
				lzw_set_bits(pe, pe->bits);
			}
			pe->string_code = data;
		}
	}
}


int putbitmap(file,bitmap,xsize,ysize)
     FILE *file;
     unsigned char bitmap[];
     int xsize;
     int ysize;
{
  int depth=1;
  int raster=xsize/8;
  ushort height=ysize;
  ushort gif_width = raster * (8 / depth); /* decoders want the width */
  /* on a byte boundary */
  byte *row = (byte *)malloc(raster * 2);
  byte *end = row + raster;
  lzw_encoder encoder;
  int y;
  
  if(lzw_init(&encoder,2,file)<0)exit(1);
  putgifheader(file,xsize,ysize);
  putimageheader(file,xsize,ysize);
  
  fputc(encoder.bits, file);		/* start with code size */
  
  lzw_putc(&encoder, encoder.Clear_code);	/* output clear code first*/
  
  /* Dump the contents of the image. */
  for ( y = 0; y < height; y++ ) 
    {	memcpy(row, bitmap+raster*y, raster);
	lzw(row, end, &encoder, depth);
      }
  
  lzw_finish(&encoder);
/* odd fix
  fputc(0, file);
*/  
  lzw_exit(&encoder);
  free((char *)row, raster * 2);
  fputc(0,file);
  fputc(0x3b, file);  /* EOF */
}