/*****************************************************************************/
/*
                                 GifSpi.c

24-APR-99  MGD  maintenance
01-AUG-97  MGD  general maintenance in line with hyperspi.c,
                dispensed with write(fd,,) in favour of fwrite(,,,stdout)
20-JUN-95  MGD  initial development
*/
/*****************************************************************************/

/* standard C header files */
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <errno.h>
#include <file.h>

#define boolean int
#define true 1
#define false 0

/* externs declared in HyperSpi.c */
extern boolean  Debug;

/* externs declared in PlotSpi.c */
extern int  PlotAreaX,
            PlotAreaY;
extern char  *GraphPtr;

/*****************************************************************************/
/*
Return a bitmap image to the client as a GIF image.

The code in these functions is implemented in accordance with Compuserve's 
Graphic Interchange Format Programming Reference specification, version 89a, 
31st July 1990. 

The LZW compression employed by the GIF algorithm is implemented using code 
derived from the PBM suite.  Two functions, virtually unmodified, are 
employed, GifCompress() ... formally called 'compgif()', and GifPackBits() ... 
formally called 'pack_bits()'.  The original commentary and copyright notice 
remains as per the code author's request.
*/ 

GifImage (char *GifFileName)

{
   static int  Background = 0,
               BitsPerPixel = 1;
   /* background (index 0) is white, foreground (index 1) is black */
   static unsigned char  Red [] = { 0xff, 0x00 },
                         Green [] = { 0xff, 0x00 },
                         Blue [] = { 0xff, 0x00 };

   int  idx, Byte,
        LeftOffset,
        TopOffset,
        Resolution,
        ColorMapSize,
        InitCodeSize;

   unsigned char  *bptr;
   unsigned char Buffer [256];

   /*********/
   /* begin */
   /*********/

   if (Debug) fprintf (stdout, "GifImage()\n");

   /* intialize the following function */
   GifNextPixel (1, 0);

   ColorMapSize = 1 << BitsPerPixel;
   LeftOffset = TopOffset = 0;
   Resolution = BitsPerPixel;

   /* the initial code size */
   if (BitsPerPixel <= 1 )
      InitCodeSize = 2;
   else
      InitCodeSize = BitsPerPixel;

   /* for convenience accumulate bytes into this buffer before output */
   bptr = Buffer;

   /**************************/
   /* GIF Data Stream header */
   /**************************/

   strcpy (bptr, (unsigned char*)"GIF89a");
   bptr += 6;

   /*****************************/
   /* Logical Screen Descriptor */
   /*****************************/

   /* width and height of logical screen */
   *bptr++ = PlotAreaX & 0xff;
   *bptr++ = (PlotAreaX >> 8) & 0xff;
   *bptr++ = PlotAreaY & 0xff;
   *bptr++ = (PlotAreaY >> 8) & 0xff;

   /* indicate that there is a global colour map */
   Byte = 0x80;
   /* OR in the resolution */
   Byte |= (Resolution - 1) << 5;
   /* OR in the Bits per Pixel */
   Byte |= (BitsPerPixel - 1);
   /* write it out */
   *bptr++ = Byte;

   /* Background colour */
   *bptr++ = Background;

   /* pixel aspect ratio */
   *bptr++ = 0;

   /***********************/
   /* Global Colour Table */
   /***********************/

   for (idx = 0; idx < ColorMapSize; idx++)
   {
      *bptr++ = Red[idx];
      *bptr++ = Green[idx];
      *bptr++ = Blue[idx];
   }

   /****************************************/
   /* Graphic Control Extension descriptor */
   /****************************************/

   /* extension introducer and graphic control label */
   *bptr++ = 0x21;
   *bptr++ = 0xf9;
   /* fixed size of the following data block */
   *bptr++ = 0x04;
   /* Transparency Index is provided */
   *bptr++ = 0x01;
   /* no data in these */
   *bptr++ = 0x00;
   *bptr++ = 0x00;
   /* Transparent Color Index value, BACKGROUND SHOULD BE TRANSPARENT */
   *bptr++ = 0x00;
   /* block terminator */
   *bptr++ = 0x00;

   /********************/
   /* Image descriptor */
   /********************/

   /* write an Image separator */
   *bptr++ = 0x2c;

   /* location of image within logical screen */
   *bptr++ = LeftOffset & 0xff;
   *bptr++ = (LeftOffset >> 8) & 0xff;
   *bptr++ = TopOffset & 0xff;
   *bptr++ = (TopOffset >> 8) & 0xff;

   /* width and height of image within logical screen */
   *bptr++ = PlotAreaX & 0xff;
   *bptr++ = (PlotAreaX >> 8) & 0xff;
   *bptr++ = PlotAreaY & 0xff;
   *bptr++ = (PlotAreaY >> 8) & 0xff;

   /* no local color table, image is not interlaced, not ordered, etc. */
   *bptr++ = 0x00;

   /**************************/
   /* table-based image data */
   /**************************/

   /* write out the initial code size */
   *bptr++ = InitCodeSize;

   /* transfer what we've accumlated in the local buffer */
   fwrite (Buffer, bptr-Buffer, 1, stdout);

   /* LZW compress the data using PBM-derived algorithm and code */
   GifCompress (InitCodeSize + 1);

   /****************************************/
   /* end of image data and GIF terminator */
   /****************************************/

   /* write out a zero-length packet (to end the series), and terminator */
   fwrite ("\0;", 2, 1, stdout);
}

/*****************************************************************************/
/*
Get a series of pixels from the bitmap.  This function is called by 
GifCompress() to scan the image.  Bit 0 through to bit 7 of the current byte 
are returned as 1 or 0 before the next byte is pointed to.  When the total 
number of bytes have been transmitted return EOF.  This function is 
initialized by a first call, setting the values of the byte pointer and number 
of bytes in the image.
*/ 

GifNextPixel
(
unsigned char *Address,
int Count
)
{
   static int  LongWord,
               Pixels,
               NumberOfBits;
   static unsigned int  Bit;

   /*********/
   /* begin */
   /*********/

   if (Address)
   {
      /* initial call, initialize byte pointer and counter */
      NumberOfBits = PlotAreaX * PlotAreaY;
      LongWord = 0;
      Bit = 1;
      Pixels = ((unsigned long*)GraphPtr)[LongWord++];
      return;
   }

   if (!NumberOfBits--) return (EOF);

   if (!Bit)
   {
      /* bits 0 through to 31 have been returned, move to next long word */
      Pixels = ((unsigned long*)GraphPtr)[LongWord++];
      Bit = 1;
   }

/*
   printf("%d %d %08.08X %08.08X\n",NumberOfBits,LongWord,Bit,Pixels);
*/

   if (Pixels & Bit)
   {
      /* next call will return the next most significant bit */
      Bit = (Bit << 1);
      /* the tested bit position contained a 1 (foreground) */
      return (1);
   }
   else
   {
      /* next call will return the next most significant bit */
      Bit = (Bit << 1);
      /* the tested bit position contained a 0 (background) */
      return (0);
   }
}

/****************************************************************************/
/*
 * This software is copyrighted as noted below.  It may be freely copied,
 * modified, and redistributed, provided that the copyright notice is 
 * preserved on all copies.
 * 
 * There is no warranty or other guarantee of fitness for this software,
 * it is provided solely "as is".  Bug reports or fixes may be sent
 * to the author, who may or may not act on them as he desires.
 *
 * You may not include this software in a program or other software product
 * without supplying the source, or without informing the end-user that the 
 * source is available for no extra charge.
 *
 * If you modify this software, you should include a notice giving the
 * name of the person performing the modification, the date of modification,
 * and the reason for such modification.
 */

/*  compgif.c */
/*
 *
 * GIF Image compression - LZW algorithm implemented with Trie type
 *                         structure.
 *                         Written by Bailey Brown, Jr.
 *                         last change May 24, 1990
 *                         file: compgif.c
 *
 *  You may use or modify this code as you wish, as long as you mention
 *  my name in your documentation.
 *
 *                  - Bailey Brown, Jr.
 *
 */

#define MAXIMUMCODE 4095   /* 2**maximum_code_size */
#define BLOCKSIZE 256   /* max block byte count + 1 */
#define NULLPREFIX -1

typedef struct str_table_entry {
        int code;
        int prefix;
        int suffix;
}  strTableEntry;

typedef struct str_table_node {
        strTableEntry entry;
    struct str_table_node *left;
    struct str_table_node *right;
struct str_table_node *children;
} strTableNode, *strTableNodePtr, **strTable;

/*
 ********************************************************************
 * compgif() recieves pointers to an input function and an output    *
 * stream, and the code size as parameters and outputs successive   *
 * blocks of LZW compressed gif data.  The calling routine should   *
 * have aready written the GIF file header out to the output file.  *
 * It assumes that there will be no more than 8 bits/pixel and that *
 * each data item comes from successive bytes returned by infun.    *
 ********************************************************************
 */

int GifCompress (int code_size)

{
    strTable heap; /* our very own memory manager */
    int heap_index;
    int clear_code, end_code, cur_code;
    int i, found, num_colors, prefix, compress_size;
    int cur_char, end_of_data, bits_per_pix;
    strTableNodePtr cur_node;
    strTable root;  /* root of string table for LZW compression is */
                    /* an array of 2**bits_per_pix pointers to atomic nodes */
    heap_index = 0;
    heap = (strTable)malloc(sizeof(strTableNodePtr)*MAXIMUMCODE);
    if (heap == NULL) printf("can't allocate heap");
    for (i=0; i < MAXIMUMCODE; i++) {
        heap[i] = (strTableNodePtr)malloc(sizeof(strTableNode));
        if (heap[i] == NULL)
        {
           printf("can't allocate heap");
           exit (1);
        }
    }
    bits_per_pix = code_size - 1;
    compress_size = code_size;
    num_colors = 1<<(bits_per_pix);
    clear_code = num_colors;
    end_code = clear_code + 1;
    cur_code = end_code + 1;
    prefix = NULLPREFIX;
    root = (strTable)malloc(sizeof(strTableNodePtr)*num_colors);
    if (!root)
    {
       printf("memory allocation failure (root)");
       exit (1);
    }
    for(i=0; i<num_colors; i++) {
        root[i] = heap[heap_index++];
        root[i]->entry.code = i;
        root[i]->entry.prefix = NULLPREFIX;
        root[i]->entry.suffix = i;
        root[i]->left = NULL;
        root[i]->right = NULL;
        root[i]->children = NULL;
    }
    /* initialize  output block */
    GifPackBits(compress_size, -1);
    GifPackBits(compress_size, clear_code);
    end_of_data = 0;
    if ((cur_char = GifNextPixel(NULL, 0)) == EOF)
       printf("premature end of data");
    while (!end_of_data) {
        prefix = cur_char;
        cur_node = root[prefix];
        found = 1;
        if((cur_char = GifNextPixel(NULL, 0)) == EOF) {
            end_of_data = 1; break;
        }
        while(cur_node->children && found) {
            cur_node = cur_node->children;
            while(cur_node->entry.suffix != cur_char) {
                if (cur_char < cur_node->entry.suffix) {
                    if (cur_node->left) cur_node = cur_node->left;
                    else {
                        cur_node->left = heap[heap_index++];
                        cur_node = cur_node->left;
                        found = 0; break;
                    }
                }
                else {
                    if (cur_node->right) cur_node = cur_node->right;
                    else {
                        cur_node->right = heap[heap_index++];
                        cur_node = cur_node->right;
                        found = 0; break;
                    }
                }
            }
            if (found) {
                prefix = cur_node->entry.code;
                if((cur_char = GifNextPixel(NULL, 0)) == EOF) {
                    end_of_data = 1; break;
                }
            }
        }
        if (end_of_data) break;
        if (found) {
            cur_node->children = heap[heap_index++];
            cur_node = cur_node->children;
        }
        cur_node->children = NULL;
        cur_node->left = NULL;
        cur_node->right = NULL;
        cur_node->entry.code = cur_code;
        cur_node->entry.prefix = prefix;
        cur_node->entry.suffix = cur_char;
        GifPackBits(compress_size, prefix);
        if (cur_code > ((1<<(compress_size))-1))
            compress_size++;
        if (cur_code < MAXIMUMCODE) {
            cur_code++;
        }
        else {
            heap_index = num_colors;  /* reinitialize string table */
            for (i=0; i < num_colors; i++ ) root[i]->children = NULL;
            GifPackBits(compress_size, clear_code);
            compress_size = bits_per_pix + 1;
            cur_code = end_code + 1;
        }
    }
    GifPackBits(compress_size, prefix);
    GifPackBits(compress_size, end_code);
    GifPackBits(compress_size, -1);
    for (i=0; i < MAXIMUMCODE; i++) free(heap[i]);
    free(heap);
    free(root);
    return (1);
}

/*
 ************************************************************************
 * GifPackBits() packs the bits of the codes generated by gifenc() into   *
 * a 1..256 byte output block.  The first byte of the block is the      *
 * number 0..255 of data bytes in the block.  To flush or initialize    *
 * the block, pass a negative argument.                                 *
 ************************************************************************
 */

int GifPackBits (int compress_size, int prefix)

{
    static int cur_bit = 8;
    static unsigned char block[BLOCKSIZE] = { 0 };
    int i, left_over_bits;

    /* if we are about to excede the bounds of block or if the flush
       code (code_bis < 0) we output the block */
    if((cur_bit + compress_size > (BLOCKSIZE-1)*8) || (prefix < 0)) {
        /* handle case of data overlapping blocks */
        if ((left_over_bits = (((cur_bit>>3) +
                ((cur_bit & 7) != 0))<<3) - cur_bit) != 0) {
            for (i=0; i < left_over_bits; i++) {
                if (prefix & (1<<i))
                   block[cur_bit>>3] |= (char)(1<<(cur_bit & 7));
                /* note n>>3 == n/8 and n & 7 == n % 8 */
                cur_bit++;
            }
        }
        compress_size -= left_over_bits;
        prefix = prefix>>left_over_bits;
        block[0] =  (unsigned char)((cur_bit>>3) - 1);

        if (block[0]) fwrite (block, block[0]+1, 1, stdout);

        for(i=0; i < BLOCKSIZE; i++) block[i] = 0;
        cur_bit = 8;
    }
    if (prefix >= 0) {
        for (i=0; i < compress_size; i++) {
           if (prefix & (1<<i))
           block[cur_bit>>3] |= (unsigned char)(1<<(cur_bit & 7));
           /* note n>>3 == n/8 and n & 7 == n % 8 */
           cur_bit++;
        }
    }
    return (1);
}

/*****************************************************************************/