/* changed charset to unsigned: need to check rest of
   code to see what impact this has!  (it does have
   impact) */

/************************************************
* Code by Suan Hsi Yong - use at your own risk! *
************************************************/

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

#define BLKSIZE 255

struct gifinfo{
   int wid;     /* image width (pixels) */
   int hgt;     /* image height (pixels) */
   int numiter; /* number of iterations for animated */
   int delay;   /* centiseconds delay for animated */
   char usemap; /* 0x00 or 0x80 - indicates if colormap included */
   unsigned char * charset; /* character set to be encoded
		               must be 2^nbits unique characters*/
   int nbits;      /* code size : between 2 (4 colors) and 8 (256 colors)*/
   int ncols;      /* number of RGB triplets in colors[] */
   unsigned char * colors; /* global color map must be (ncols*3) characters,
			      colors listed in rgb triplets */
   char bgindex;  /* index to background color/transparency color */
   char istrans;  /* 1 or 0: turns on or off transparency */
   char sortfl;   /* 0x00 or 0x08 */
};

void gifhead(FILE * ofstr, struct gifinfo a)
{
   int lzwencode(char *, char *, int, char *, int);
   int i, j;

   /* gif signature */
   fprintf(ofstr,"GIF89a");
   /* logical screen width/height */
   fprintf(ofstr,"%c%c%c%c",a.wid,a.wid>>8,a.hgt,a.hgt>>8);
   /* M/cr/S/P */
   fputc(a.usemap|((a.nbits-1)<<4)|a.sortfl|(a.nbits-1),ofstr);
   /* bg & pixel aspect ratio */
   fprintf(ofstr,"%c%c",a.bgindex,0);
   /* global color map */
   if(a.usemap){
      j = a.ncols*3;
      for(i = 0; i < j; i+=3) /* fill in colors given */
	 fprintf(ofstr,"%c%c%c",a.colors[i],a.colors[i+1],a.colors[i+2]);
      j = (1<<a.nbits)*3;
      for(; i < j; i+=3) /* zero pad the rest */
	 fprintf(ofstr,"%c%c%c",0,0,0);
   }
   /* netscape 2.0 loop */
   if(a.numiter)
      fprintf(ofstr,"!%c%cNETSCAPE2.0%c%c%c%c%c",
	   0xff,11,3,1,a.numiter,a.numiter>>8,0);

}

void gifout(FILE * ofstr, char * src, int len, struct gifinfo a)
{
   int lzwencode(char *, char *, int, char *, int);
   char * tgt;/* assume no compression as max    */
   /* What we *really* need here is tgt=(char*)malloc(len) */
   int i, j, lim;

   tgt = (char *) malloc(a.wid * a.hgt * sizeof(char));
   /* transparency extension block */
   fprintf(ofstr,"!%c%c%c%c%c%c%c",
	    0xf9,4,a.istrans,a.delay,a.delay>>8,a.bgindex,0);
   /* image coords and dimension */
   fprintf(ofstr,",%c%c%c%c%c%c%c%c",
	   0,0,0,0,a.wid,a.wid>>8,a.hgt,a.hgt>>8);
   /* M/I/S/0/0/P  <== should P = 0??? */
   fputc(a.sortfl<<2|(a.nbits-1),ofstr);
   for(i = a.wid*a.hgt - 1; i >= 0; --i) tgt[i] = 0;
   len = lzwencode(src, tgt, len, a.charset, a.nbits+1);
   /* minimum code */
   fputc(a.nbits,ofstr);
   /* divide into subblocks */
   for(i = 0; i < len; i+= BLKSIZE){
      lim = len-i;
      if(lim > BLKSIZE) lim = BLKSIZE;
      /* subblock size */
      fputc(lim, ofstr);
      for(j = 0; j < lim; ++j)
	 fputc(tgt[i+j],ofstr);
   }
   /* terminate with zero subblock */
   fputc(0, ofstr);
}

/* source contains data byte by byte - all bytes must exist in charset
   target must be preallocated and zero-initialized
   charset must be char[2^numbits][2] where not used = NULL
 */
int lzwencode(char * source, char * target, int len,
	      char * charset, int nbits)
{
   int find(char *, char *, short int *, char *, int, int);
   short int c, cc;
   char * out, * pref, * k;
   short int ptab[4096];
   char ctab[4096];
   int coff, h, i, j, numbits, siz;
   numbits = nbits;
   siz = 1 << numbits;
   cc = siz/2;
   for(i = 0; i < cc; ++i){ /* initialize string table */
      ptab[i] = cc+1; /* initial prefixes are eoi */
      ctab[i] = charset[i];
   }
   ptab[i] = cc+1; /* CC slot */
   ctab[i++] = 0;
   ptab[i] = cc+1; /* EOI slot */
   ctab[i++] = 0;
   pref = source; /* initialize pointers and all */
   k = source;
   out = target;
   * out = cc; /* 1st thing - output CC */
   coff = numbits;        /* coff = current offset for output */
   if(coff >= 8){
      coff -= 8;
      out++;
      c = cc >> (numbits - coff);
      * out = c & ~(0xFF << coff);
   }
   for(h = 0; h < len; ++h){
      j = find(pref, k, ptab, ctab, i, cc+1);
      if(j == -1) /* found */
	 k++;
      else{ /* not found */
	 ptab[i] = j; /* add entry to strtab */
	 ctab[i] = *k;
	 /* output code j */
	 * out |= j << coff;
	 coff += numbits;
	 if(coff >= 8){
	    coff -= 8;
	    out++;
	    c = j >> (numbits - coff);
	    if(coff >= 8){ /* if numbits > 8 we may span 3 bytes */
	       * (out++) = (char) c;
	       coff -= 8;
	       c = j >> (numbits - coff);
	    }
	    * out = c & ~(0xFF << coff); /* just in case stray 1's */
	 }                               /* happen to shift in     */
	 /* increment index, and codesize if need be */
	 if(i++ == siz)
	    numbits++;
	 if(i >= 4095){ /* My belief that >= is safer than == */
	    /* output clear code */
	    * out |= cc << coff;
	    coff += numbits;
	    if(coff >= 8){
	       coff -= 8;
	       out++;
	       c = cc >> (numbits - coff);
	       if(coff >= 8){
		  * (out++) = (char) c;
		  coff -= 8;
		  c = j >> (numbits - coff);
	       }
	       * out = c & ~(0xFF << coff);
	    }
	    numbits = nbits; /* reset numbits */
	    i = cc + 2;      /* and i */
	 }
	 siz = 1 << numbits;
	 /* reset prefix and increment k */
	 pref = k++;
      }
   }
   /* output last prefix code */
   j = find(pref, k, ptab, ctab, i, cc+1);
   * out |= j << coff;
   coff += numbits;
   if(coff >= 8){
      coff -= 8;
      out++;
      c = j >> (numbits - coff);
      * out = c & ~(0xFF << coff);
   }
   /* finally, output EOI */
   * out |= (cc+1) << coff;
   coff += numbits;
   if(coff >= 8){
      coff -= 8;
      out++;
      c = (cc+1) >> (numbits - coff);
      * out = c & ~(0xFF << coff);
   }
   return (int)(out - target);
}

int find(char * start, char * end, short int * ptab, char * ctab,
	 int num, int eoi)
{ /* returns -1 if found, else returns prefix index */
   int i, p;
   p = eoi; /* set to return eoi if invalid data byte */
   for(i = 0; i < num; ++i){
      if(p == ptab[i]){ /* if prefix is same */
	 if(*start == ctab[i]){ /* if char ('K') is same */
	    if(start == end) /* if that's all, then found */
	       return -1;
	    p = i;
	    start++;
	 }
      }
   }
   return p;
}