/***************************************************************************
 * GIF Encoder from arbitrary image storage format
 *
 * Credits:
 *
 *   Lempel-Ziv Compression
 *   GIF(sm)is the property of CompuServe Incorporated
 *   IEEE Computer, June 1984
 *   Spencer W. Thomas
 *   Jim McKie
 *   Steve Davies
 *   Ken Turkowski
 *   James A. Woods
 *   Joe Orost
 *   Donald Knuth, (vol 3. sec. 6.4)
 *   G. Knott
 *   David Rowley
 *   Marcel Wijkstra
 *   PBMPlus Copyright (C) 1989 by Jef Poskanzer
 *   Bitmap BMP/DIB format structures (C) Microsoft Corporation
 *   Glenn Slayden 1996
 *
 *
 **************************************************************************/

#include <malloc.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>


/***************************************************************************
 *
 * Windows BMP format definitions.  Cannot use the actual structures
 * for two reasons: first, I couldn't get the #pragma pack to work
 * in GCC, and second, the byte order is different between Intel/Sun.
 *
 **************************************************************************/

/* BITMAPFILEHEADER offsets */
#define w_bfType          0x00
#define d_bfSize          0x02
#define w_bfReserved1     0x06
#define w_bfReserved2     0x08
#define d_bfOffBits       0x0A

/* BITMAPINFOHEADER offsets */
#define d_biSize          0x0E
#define l_biWidth         0x12
#define l_biHeight        0x16
#define w_biPlanes        0x1A
#define w_biBitCount      0x1C
#define d_biCOmpression   0x1E
#define d_biSizeImage     0x22
#define l_biXPelsPerMeter 0x26
#define l_biYPelsPerMeter 0x2A
#define d_biClrUsed       0x2E
#define d_biClrImportant  0x32
#define offs_start_rgb    0x36
#define sizeof_rgb        4

#define _swapword(x)   (x[0] + (x[1]<<8))
#define GetIntelWord(a) ((unsigned short)_swapword(((unsigned char *)(a))))
#define GetIntelDWord(a)  ((unsigned long)GetIntelWord(a) + \
                           (unsigned long)(GetIntelWord(a+2)<<16))

/***************************************************************************
 *
 * PIMG can be a pointer to any user-defined image type.  You must
 * pass it into GIFEncode() in the main() function, and add your
 * code to handle it in the GetPixel() function
 *
 **************************************************************************/

typedef char *PIMG;
void GIFEncode(FILE *fp,int GWidth, int GHeight, int GInterlace, int Background, int Transparent, int BitsPerPixel, int *Red, int *Green, int *Blue, PIMG pi);

/***************************************************************************
 *
 * A code_int must be able to hold 1<<GIFBITS values of type int, and also -1
 *
 **************************************************************************/

typedef int             code_int;
typedef long int        count_int;

#define GIFBITS    12

#define HSIZE  5003            /* 80% occupancy */

static int n_bits;                        /* number of bits/code */
static int maxbits = GIFBITS;                /* user settable max # bits/code */
static code_int maxcode;                  /* maximum code, given n_bits */
static code_int maxmaxcode = (code_int)1 << GIFBITS; /* should NEVER generate this code */

#define MAXCODE(n_bits)        (((code_int) 1 << (n_bits)) - 1)


static count_int htab[HSIZE];
static unsigned short ctab[HSIZE];

static code_int hsize = HSIZE;                 /* for dynamic table sizing */
static code_int free_ent = 0;                  /* first unused entry */

/*
 * block compression parameters -- after all codes are used up,
 * and compression rate changes, start over.
 */
static int clear_flg = 0;

static int g_init_bits;
static FILE* g_outfile;

static int ClearCode;
static int EOFCode;


static int Width, Height;
static int curx, cury;
static long CountDown;
static int Pass = 0;
static int Interlace;


#define CGI


/***************************************************************************
 *
 * GetPixel
 *
 * User-supplied routine to fetch a pixel value from the source image
 *
 **************************************************************************/

int GetPixel(
  PIMG pi,
  int x,
  int y)
{
   static char mpm[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
   static unsigned char *pBits = 0;
   static int m_widthbytes;
   static int m_height;
   char b;
   int width,bpp;

   if (!pBits)
   {
      pBits    = pi + GetIntelDWord(pi + d_bfOffBits);
      width    =      GetIntelDWord(pi + l_biWidth);
      m_height =      GetIntelDWord(pi + l_biHeight);
      bpp      =      GetIntelWord (pi + w_biBitCount);

      m_widthbytes = width / (8/bpp);
      m_widthbytes = (m_widthbytes + 3) & 0xFC;

#ifndef CGI
      printf("\n----in GetPixel---\n");
      printf("m_widthbytes: %d\n",m_widthbytes);
#endif

   }

   if (bpp==1)
   {
      b = pBits[(((m_height - 1) - y) * m_widthbytes) + (x / 8)];

      if (b & mpm[x % 8])
         return 1;
      else
         return 0;
   }
   else if (bpp==8)
      return pBits[((m_height - 1) - y) * m_widthbytes + x];
   else
      return 0;

}


/***************************************************************************
 *
 * main() is the entry point for CGI scripts.  Most of the information
 * passed from the server is found in certain environment strings.
 *
 **************************************************************************/

main()
{
   PIMG pImg;
   FILE *fpOut;
   FILE *fp;
   int Red[256];
   int Green[256];
   int Blue[256];
   int i;
   char *pBmp;
   unsigned char *pRgb;
   int width,height,bpp;
   int cColors;
   char preread[6];
   int cbFile;
   char *pq;

#ifdef CGI
   fpOut = stdout;

   pq = getenv("QUERY_STRING");

   if (pq && *pq != '\0')
   {

      /* process query string here.  In this case this CGI script should
       * be called like this:
       * http://www.foo.com/.../gifencode.cgi?win3bmp.bmp
       */

      fp = fopen(pq,"r");

   }
   else
   {
      fprintf(fpOut,"Content-Type: text/html\n\n");
      fprintf(fpOut,"<HEAD><TITLE>Usage</TITLE></HEAD>\n");
      fprintf(fpOut,"<BODY>");
      fprintf(fpOut,"Usage: gifencode.cgi?win3bmp.bmp\n");
      fprintf(fpOut,"</BODY>");
      exit(0);
   }

#else
   fpOut = fopen("mygif.gif","w");
   fp = fopen("image/blobule.bmp","r");
#endif

   if (!fp)
      exit(0);

   /* preread 6 bytes from the file to get its size */

   fread(preread,1,6,fp);

   /* Check for proper signature */

   if (GetIntelWord(preread + w_bfType) != 0x4D42)
      exit(0);

   cbFile = GetIntelDWord(preread + d_bfSize);

   /* Read the rest of the file into pBmp */

   pBmp = malloc(cbFile);
   fread(&pBmp[6],1,cbFile-6,fp);

   /* Make sure it's not an old-style OS/2 bitmap */

   if (GetIntelDWord(pBmp+d_biSize) != 0x28)
      exit(0);

#ifndef CGI
   printf("bfType: %x\n",    GetIntelWord(preread+w_bfType));
   printf("cbFile: %lx\n",   cbFile);
   printf("bfSize: %lx\n",   GetIntelDWord(preread+d_bfSize));
   printf("bfOffBits: %lx\n",GetIntelDWord(pBmp+d_bfOffBits));

   printf("biSize: %lx\n",   GetIntelDWord(pBmp+d_biSize));
   printf("biWidth: %ld\n",  GetIntelDWord(pBmp+l_biWidth));
   printf("biHeight: %ld\n", GetIntelDWord(pBmp+l_biHeight));
   printf("biPlanes: %x\n",  GetIntelWord(pBmp+w_biPlanes));
   printf("biBitCount: %x\n",GetIntelWord(pBmp+w_biBitCount));
#endif

   bpp      = GetIntelWord(pBmp + w_biBitCount);
   width    = GetIntelDWord(pBmp + l_biWidth);
   height   = GetIntelDWord(pBmp + l_biHeight);

   cColors = (1 << bpp);

   pRgb = pBmp + offs_start_rgb;

   for (i=0; i<cColors; i++)
   {
      Blue[i]  = pRgb[0];
      Green[i] = pRgb[1];
      Red[i]   = pRgb[2];
      pRgb += sizeof_rgb;
   }

#ifdef CGI
   fprintf(fpOut,"Content-Type: image/gif\n");
   fprintf(fpOut,"Content-transfer-encoding: binary\n\n");
#endif

   GIFEncode(fpOut,
             width,     /* target x */
             height,    /* target y */
             0,         /* interlace */
             0,         /* background */
             -1,        /* transparent color index, -1 for GIF87a */
             bpp,       /* bits per pixel */
             Red,       /* red */
             Green,     /* green */
             Blue,      /* blue */
             pBmp);     /* pointer to source image */

   free(pBmp);

   fclose(fp);
#ifndef CGI
   fclose(fpOut);
#endif
}


/***************************************************************************
 *
 * Bump the 'curx' and 'cury' to point to the next pixel
 *
 **************************************************************************/

void BumpPixel(void)
{
   ++curx;

   /*
    * If we are at the end of a scan line, set curx back to the beginning
    * If we are interlaced, bump the cury to the appropriate spot,
    * otherwise, just increment it.
    */

   if (curx == Width)
   {
      curx = 0;

      if (!Interlace)
         ++cury;
      else
      {
         switch (Pass)
         {
            case 0:
               cury += 8;
               if (cury >= Height)
               {
                  ++Pass;
                  cury = 4;
               }
               break;

            case 1:
               cury += 8;
               if (cury >= Height)
               {
                  ++Pass;
                  cury = 2;
               }
               break;

            case 2:
               cury += 4;
               if (cury >= Height)
               {
                  ++Pass;
                  cury = 1;
               }
               break;

            case 3:
               cury += 2;
               break;
          }
      }
   }
}


/***************************************************************************
 *
 * Return the next pixel from the image
 *
 **************************************************************************/

int GIFNextPixel(PIMG pi)
{
   int r;

   if (CountDown == 0)
      return EOF;

   --CountDown;

   r = GetPixel(pi, curx, cury);

   BumpPixel();

   return r;
}


/***************************************************************************
 *
 * GIF block size related globals
 *
 **************************************************************************/

static char accum[256];   /* packet accumulator */
static int a_count = 0;   /* Number of character in the accumulator */


/***************************************************************************
 *
 * Flush a 254 byte packet to disk and reset the accumulator
 *
 **************************************************************************/

void flush_char(void)
{
   if (a_count > 0)
   {
      fputc( a_count, g_outfile );
      fwrite( accum, 1, a_count, g_outfile );
      a_count = 0;
   }
}


/***************************************************************************
 *
 * Add a character to the end of the current packet, and if it is 254
 * characters, flush the packet to disk.
 *
 **************************************************************************/

void char_out(int c)
{
   accum[a_count++] = c;
   if (a_count >= 254)
      flush_char();
}


/***************************************************************************
 *
 * Output the given code
 *
 **************************************************************************/

void output(code_int code)
{

   /* Statics */

   static unsigned long cur_accum = 0;
   static int cur_bits = 0;
   static unsigned long masks[] = {
          0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F,
          0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF,
          0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };

   /* Code */

   cur_accum &= masks[cur_bits];

   if (cur_bits > 0)
      cur_accum |= ((long)code << cur_bits);
   else
      cur_accum = code;

   cur_bits += n_bits;

   while (cur_bits >= 8)
   {
      char_out((unsigned int)(cur_accum & 0xff));
      cur_accum >>= 8;
      cur_bits -= 8;
   }

   /*
    * If the next entry is going to be too big for the code size,
    * then increase it, if possible.
    */

   if (free_ent > maxcode || clear_flg)
   {
      if (clear_flg)
      {
         maxcode = MAXCODE(n_bits = g_init_bits);
         clear_flg = 0;
      }
      else
      {
         ++n_bits;
         if (n_bits == maxbits)
            maxcode = maxmaxcode;
         else
            maxcode = MAXCODE(n_bits);
      }
   }

   if( code == EOFCode )
   {
      /* At EOF, write the rest of the buffer. */

      while (cur_bits > 0)
      {
         char_out((unsigned int)(cur_accum & 0xff));
         cur_accum >>= 8;
         cur_bits -= 8;
      }

      flush_char();

      fflush(g_outfile);

      if (ferror(g_outfile))
         return;
   }
}


/***************************************************************************
 *
 * Clear the hash table
 *
 **************************************************************************/

void cl_hash(register count_int hsize)
{

   register count_int *htab_p = htab+hsize;

   register long i;
   register long m1 = -1;

   i = hsize - 16;
   do
   {
      *(htab_p-16) = m1;
      *(htab_p-15) = m1;
      *(htab_p-14) = m1;
      *(htab_p-13) = m1;
      *(htab_p-12) = m1;
      *(htab_p-11) = m1;
      *(htab_p-10) = m1;
      *(htab_p-9) = m1;
      *(htab_p-8) = m1;
      *(htab_p-7) = m1;
      *(htab_p-6) = m1;
      *(htab_p-5) = m1;
      *(htab_p-4) = m1;
      *(htab_p-3) = m1;
      *(htab_p-2) = m1;
      *(htab_p-1) = m1;
      htab_p -= 16;

   } while ((i -= 16) >= 0);

   for (i+=16; i > 0; --i)
      *--htab_p = m1;
}


/***************************************************************************
 *
 * Clear out the codes table
 *
 **************************************************************************/

void cl_block(void)
{
   cl_hash((count_int)hsize);
   free_ent = ClearCode + 2;
   clear_flg = 1;

   output((code_int)ClearCode);
}


/***************************************************************************
 *
 * compress - according to original documentation, "use open addressing
 * double hashing (no chaining) on the prefix code / next character
 * combination.  Do a variant of Knuth's algorithm D (vol 3. sec. 6.4)
 * along with G. Knott's relatively-prime secondary probe.  Here, the
 * modular division first probe gives way to a faster exclusive-or
 * manipulation.  Also do block compression with an adaptive reset,
 * whereby the code table is cleared when the compression ratio decreases,
 * but after the table fills.  The variable-length output codes are re-
 * sized at this point, and a special CLEAR code is generated for the
 * decompressor.
 *
 **************************************************************************/

void compress(
  int init_bits,
  FILE *outfile,
  PIMG pi)
{
   register long fcode;
   register code_int i /* = 0 */;
   register int c;
   register code_int ent;
   register code_int disp;
   register code_int hsize_reg;
   register int hshift;

   g_init_bits = init_bits;
   g_outfile = outfile;

   clear_flg = 0;
   maxcode = MAXCODE(n_bits = g_init_bits);

   ClearCode = (1 << (init_bits - 1));
   EOFCode = ClearCode + 1;
   free_ent = ClearCode + 2;

   ent = GIFNextPixel(pi);

   hshift = 0;
   for (fcode = (long)hsize;  fcode < 65536L; fcode *= 2L)
      ++hshift;

   /* set hash code range bound */

   hshift = 8 - hshift;

   hsize_reg = hsize;

   /* clear hash table */

   cl_hash((count_int) hsize_reg);

   output((code_int)ClearCode);

   while ((c = GIFNextPixel(pi)) != EOF)
   {
      fcode = (long) (((long) c << maxbits) + ent);

      i = (((code_int)c << hshift) ^ ent);    /* xor hashing */

      if (htab[i] == fcode)
      {
         ent = ctab[i];
         continue;
      }
      else if ((long)htab[i] < 0)      /* empty slot */
         goto nomatch;

      disp = hsize_reg - i;           /* secondary hash (after G. Knott) */

      if (i == 0)
         disp = 1;
probe:
      if ((i -= disp) < 0)
         i += hsize_reg;

      if (htab[i] == fcode)
      {
         ent = ctab[i];
         continue;
      }

      if ((long)htab[i] > 0)
         goto probe;
nomatch:
      output((code_int)ent);
      ent = c;

      if (free_ent < maxmaxcode)
      {
         ctab[i] = free_ent++;     /* code -> hashtable */
         htab[i] = fcode;
      }
      else
         cl_block();
   }

   /* Put out the final code */

   output((code_int)ent);
   output((code_int)EOFCode);
}


/***************************************************************************
 *
 * Write out a word to the GIF file
 *
 **************************************************************************/

void Putword(
  int w,
  FILE *fp)
{
   fputc(w & 0xff, fp);
   fputc((w / 256) & 0xff, fp);
}


/***************************************************************************
 *
 * Write out a GIF file
 *
 **************************************************************************/

void GIFEncode(
  FILE *fp,             /* Writeable file handle for output */
  int GWidth,           /* Pixel width of the source image */
  int GHeight,          /* Pixel height of the source image */
  int GInterlace,       /* Interlace flag */
  int Background,       /* Background color index */
  int Transparent,      /* -1 or Transparent color index (causes GIF89a) */
  int BitsPerPixel,     /* Bits per pixel of source and output */
  int *Red,             /* 2^bpp entries of red component */
  int *Green,
  int *Blue,
  PIMG pi)              /* pointer to source image */
{
   int B;
   int RWidth, RHeight;
   int LeftOfs, TopOfs;
   int Resolution;
   int ColorMapSize;
   int InitCodeSize;
   int i;

   Interlace = GInterlace;

   ColorMapSize = 1 << BitsPerPixel;

   RWidth = Width = GWidth;
   RHeight = Height = GHeight;
   LeftOfs = TopOfs = 0;

   Resolution = BitsPerPixel;

   /* Calculate number of bits we are expecting */

   CountDown = (long)Width * (long)Height;

   /* Indicate which pass we are on (if interlace) */

   Pass = 0;

   /* The initial code size */

   if (BitsPerPixel <= 1)
      InitCodeSize = 2;
   else
      InitCodeSize = BitsPerPixel;

   /* Set up the current x and y position */

   curx = cury = 0;

   /* Write the GIF header */

   fwrite( Transparent < 0 ? "GIF87a" : "GIF89a", 1, 6, fp );

   /* Write out the screen width and height */

   Putword( RWidth, fp );
   Putword( RHeight, fp );

   /* Indicate that there is a global colour map */

   B = 0x80;

   /* OR in the resolution */

   B |= (Resolution - 1) << 5;

   /* OR in the Bits per Pixel */

   B |= (BitsPerPixel - 1);

   /* Write it out */

   fputc( B, fp );

   /* Write out the Background colour */

   fputc( Background, fp );

   /* Byte of 0's (future expansion) */

   fputc( 0, fp );

   /* Write out the Global Color Map */

   for (i=0; i<ColorMapSize; ++i)
   {
      fputc( Red[i], fp );
      fputc( Green[i], fp );
      fputc( Blue[i], fp );
   }

   /* Write out extension for transparent colour index, if necessary. */

   if (Transparent >= 0)
   {
      fputc( '!', fp );
      fputc( 0xf9, fp );
      fputc( 4, fp );
      fputc( 1, fp );
      fputc( 0, fp );
      fputc( 0, fp );
      fputc( (unsigned char) Transparent, fp );
      fputc( 0, fp );
   }

   /* Write an Image separator */

   fputc( ',', fp );

   /* Write the Image header */

   Putword( LeftOfs, fp );
   Putword( TopOfs, fp );
   Putword( Width, fp );
   Putword( Height, fp );

   /* Write out whether or not the image is interlaced */

   if (Interlace)
      fputc( 0x40, fp );
   else
      fputc( 0x00, fp );

   /* Write out the initial code size */

   fputc( InitCodeSize, fp );

   /* Write out the compressed image */

   compress( InitCodeSize+1, fp, pi );

   /* Write out a Zero-length packet (to end the series) */

   fputc( 0, fp );

   /* Write the GIF file terminator */

   fputc( ';', fp );
}