// ImageMagick only saves compressed GIFs if a compile option is set due to
// Unisys's patent on it. Since I have explicit permission to use it for 
// PixiePlus we include a version w/ it always enabled.

#include <stdio.h>
#include <string.h>
#include <time.h>
#include <sys/types.h>
#include <magick/api.h>
#include <assert.h>

#ifndef False
#define False 0
#endif
#ifdef True
#define True 1
#endif

#ifndef Max
#define Max(x,y)  (((x) > (y)) ? (x) : (y))
#endif
#ifndef Min
#define Min(x,y)  (((x) < (y)) ? (x) : (y))
#endif
#ifndef QuantumTick
#define QuantumTick(i,span) \
  (((~((span)-i-1) & ((span)-i-2))+1) == ((span)-i-1))
#endif

/* GraphicsMagick uses much higher "base" for version numbers: */
#if (MagickLibVersion < 0x0554) || (MagickLibVersion > 0x0100000)
#warning Using pre-ImageMagick 5.5.4 tags
#define SaveImageTag SaveImageText
#define SaveImagesTag SaveImagesText
#else
#warning Using new ImageMagick 5.5.4 tags
#endif


unsigned int EncodeCompressedGIFImage(const ImageInfo *image_info,
                                      Image *image,
                                      const unsigned int data_size)
{
#define MaxCode(number_bits)  ((1 << (number_bits))-1)
#define MaxHashTable  5003
#define MaxGIFBits  12
#define MaxGIFTable  (1 << MaxGIFBits)
#define GIFOutputCode(code) \
{ \
  /*  \
    Emit a code. \
  */ \
  if (bits > 0) \
    datum|=((long) code << bits); \
  else \
    datum=(long) code; \
  bits+=number_bits; \
  while (bits >= 8) \
  { \
    /*  \
      Add a character to current packet. \
    */ \
    packet[byte_count++]=(unsigned char) (datum & 0xff); \
    if (byte_count >= 254) \
      { \
        (void) WriteBlobByte(image,byte_count); \
        (void) WriteBlob(image,byte_count,(const unsigned char *) packet); \
        byte_count=0; \
      } \
    datum>>=8; \
    bits-=8; \
  } \
  if (free_code > max_code)  \
    { \
      number_bits++; \
      if (number_bits == MaxGIFBits) \
        max_code=MaxGIFTable; \
      else \
        max_code=MaxCode(number_bits); \
    } \
}

  int
    displacement,
    next_pixel,
    bits,
    byte_count,
    k,
    number_bits,
    offset,
    pass;

  long
    datum,
    y;

  register const PixelPacket
    *p;

  register IndexPacket
    *indexes;

  register long
    i,
    x;

  short
    clear_code,
    end_of_information_code,
    free_code,
    *hash_code,
    *hash_prefix,
    index,
    max_code,
    waiting_code;

  unsigned char
    *packet,
    *hash_suffix;

  /*
    Allocate encoder tables.
  */
  assert(image != (Image *) NULL);
  packet=(unsigned char *) AcquireMemory(256);
  hash_code=(short *) AcquireMemory(MaxHashTable*sizeof(short));
  hash_prefix=(short *) AcquireMemory(MaxHashTable*sizeof(short));
  hash_suffix=(unsigned char *) AcquireMemory(MaxHashTable);
  if ((packet == (unsigned char *) NULL) || (hash_code == (short *) NULL) ||
      (hash_prefix == (short *) NULL) ||
      (hash_suffix == (unsigned char *) NULL))
    return(false);
  /*
    Initialize GIF encoder.
  */
  number_bits=data_size;
  max_code=MaxCode(number_bits);
  clear_code=((short) 1 << (data_size-1));
  end_of_information_code=clear_code+1;
  free_code=clear_code+2;
  byte_count=0;
  datum=0;
  bits=0;
  for (i=0; i < MaxHashTable; i++)
    hash_code[i]=0;
  GIFOutputCode(clear_code);
  /*
    Encode pixels.
  */
  offset=0;
  pass=0;
  waiting_code=0;
  for (y=0; y < (long) image->rows; y++)
  {
    p=AcquireImagePixels(image,0,offset,image->columns,1,&image->exception);
    if (p == (const PixelPacket *) NULL)
      break;
    indexes=GetIndexes(image);
    if (y == 0)
      waiting_code=(*indexes);
    for (x=(y == 0) ? 1 : 0; x < (long) image->columns; x++)
    {
      /*
        Probe hash table.
      */
      index=indexes[x] & 0xff;
      p++;
      k=(int) ((int) index << (MaxGIFBits-8))+waiting_code;
      if (k >= MaxHashTable)
        k-=MaxHashTable;
      next_pixel=false;
      displacement=1;
      if ((image_info->compression != NoCompression) && (hash_code[k] > 0))
        {
          if ((hash_prefix[k] == waiting_code) && (hash_suffix[k] == index))
            {
              waiting_code=hash_code[k];
              continue;
            }
          if (k != 0)
            displacement=MaxHashTable-k;
          for ( ; ; )
          {
            k-=displacement;
            if (k < 0)
              k+=MaxHashTable;
            if (hash_code[k] == 0)
              break;
            if ((hash_prefix[k] == waiting_code) && (hash_suffix[k] == index))
              {
                waiting_code=hash_code[k];
                next_pixel=true;
                break;
              }
          }
          if (next_pixel == true)
            continue;
        }
      GIFOutputCode(waiting_code);
      if (free_code < MaxGIFTable)
        {
          hash_code[k]=free_code++;
          hash_prefix[k]=waiting_code;
          hash_suffix[k]=(unsigned char) index;
        }
      else
        {
          /*
            Fill the hash table with empty entries.
          */
          for (k=0; k < MaxHashTable; k++)
            hash_code[k]=0;
          /*
            Reset compressor and issue a clear code.
          */
          free_code=clear_code+2;
          GIFOutputCode(clear_code);
          number_bits=data_size;
          max_code=MaxCode(number_bits);
        }
      waiting_code=index;
    }
    if (image_info->interlace == NoInterlace)
      offset++;
    else
      switch (pass)
      {
        case 0:
        default:
        {
          offset+=8;
          if (offset >= (long) image->rows)
            {
              pass++;
              offset=4;
            }
          break;
        }
        case 1:
        {
          offset+=8;
          if (offset >= (long) image->rows)
            {
              pass++;
              offset=2;
            }
          break;
        }
        case 2:
        {
          offset+=4;
          if (offset >= (long) image->rows)
            {
              pass++;
              offset=1;
            }
          break;
        }
        case 3:
        {
          offset+=2;
          break;
        }
      }
    if (image->previous == (Image *) NULL)
      if (QuantumTick(y,image->rows))
        if (!MagickMonitor(SaveImageTag,y,image->rows,&image->exception))
          break;
  }
  /*
    Flush out the buffered code.
  */
  GIFOutputCode(waiting_code);
  GIFOutputCode(end_of_information_code);
  if (bits > 0)
    {
      /*
        Add a character to current packet.
      */
      packet[byte_count++]=(unsigned char) (datum & 0xff);
      if (byte_count >= 254)
        {
          (void) WriteBlobByte(image,byte_count);
          (void) WriteBlob(image,byte_count,(const unsigned char *) packet);
          byte_count=0;
        }
    }
  /*
    Flush accumulated data.
  */
  if (byte_count > 0)
    {
      (void) WriteBlobByte(image,byte_count);
      (void) WriteBlob(image,byte_count,(const unsigned char *) packet);
    }
  /*
    Free encoder memory.
  */
  LiberateMemory((void **) &hash_suffix);
  LiberateMemory((void **) &hash_prefix);
  LiberateMemory((void **) &hash_code);
  LiberateMemory((void **) &packet);
  return(true);
}

unsigned int WriteCompressedGIFImage(const ImageInfo *image_info,Image *image)
{
  Image
    *next_image;

  int
    y;

  long
    opacity;

  QuantizeInfo
    quantize_info;

  RectangleInfo
    page;

  register IndexPacket
    *indexes;

  register const PixelPacket
    *p;

  register long
    x;

  register long
    i;

  register unsigned char
    *q;

  size_t
    j;

  unsigned char
    bits_per_pixel,
    c,
    *colormap,
    *global_colormap;

  unsigned int
    interlace,
    status;

  unsigned long
    scene;

  /*
    Open output image file.
  */
  assert(image_info != (const ImageInfo *) NULL);
  assert(image_info->signature == MagickSignature);
  assert(image != (Image *) NULL);
  assert(image->signature == MagickSignature);
  status=OpenBlob(image_info,image,WriteBinaryBlobMode,&image->exception);
  if (status == false)
#if (MagickLibVersion > 0x0100000) /* GraphicsMagick - must pass image */
    ThrowWriterException(FileOpenError,"Unable to open file", image);
#else
    ThrowWriterException(FileOpenError,"Unable to open file");
#endif
  /*
    Determine image bounding box.
  */
  page.width=image->columns;
  page.height=image->rows;
  page.x=0;
  page.y=0;
  for (next_image=image; next_image != (Image *) NULL; )
  {
    page.x=next_image->page.x;
    page.y=next_image->page.y;
    if ((next_image->columns+page.x) > page.width)
      page.width=next_image->columns+page.x;
    if ((next_image->rows+page.y) > page.height)
      page.height=next_image->rows+page.y;
    next_image=next_image->next;
  }
  /*
    Allocate colormap.
  */
  global_colormap=(unsigned char *) AcquireMemory(768);
  colormap=(unsigned char *) AcquireMemory(768);
  if ((global_colormap == (unsigned char *) NULL) ||
      (colormap == (unsigned char *) NULL))
#if (MagickLibVersion > 0x0100000) /* GraphicsMagick - must pass image */
    ThrowWriterException(ResourceLimitError,"Memory allocation failed", image);
#else
    ThrowWriterException(ResourceLimitError,"Memory allocation failed");
#endif
  for (i=0; i < 768; i++)
    colormap[i]=0;
  /*
    Write GIF header.
  */
  if ((GetImageAttribute(image,"comment") == (ImageAttribute *) NULL) &&
      !image_info->adjoin && !image->matte)
    (void) WriteBlob(image,6,(const unsigned char*)"GIF87a");
  else
    if (LocaleCompare(image_info->magick,"GIF87") == 0)
      (void) WriteBlob(image,6,(const unsigned char*)"GIF87a");
    else
      (void) WriteBlob(image,6,(const unsigned char*)"GIF89a");
  page.x=image->page.x;
  page.y=image->page.y;
  if ((image->page.width != 0) && (image->page.height != 0))
    page=image->page;
  (void) WriteBlobLSBShort(image,page.width);
  (void) WriteBlobLSBShort(image,page.height);
  /*
    Write images to file.
  */
  interlace=image_info->interlace;
  if (image_info->adjoin && (image->next != (Image *) NULL))
    interlace=NoInterlace;
  opacity=(-1);
  scene=0;
  do
  {
    (void) TransformRGBImage(image,RGBColorspace);
    if ((image->storage_class == DirectClass) || (image->colors > 256))
      {
        /*
          GIF requires that the image is colormapped.
        */
        GetQuantizeInfo(&quantize_info);
        quantize_info.dither=image_info->dither;
        quantize_info.number_colors=image->matte ? 255 : 256;
        (void) QuantizeImage(&quantize_info,image);
        if (image->matte)
          {
            /*
              Set transparent pixel.
            */
            opacity=(long) image->colors++;
            ReacquireMemory((void **) &image->colormap,
              image->colors*sizeof(PixelPacket));
            if (image->colormap == (PixelPacket *) NULL)
              {
                LiberateMemory((void **) &global_colormap);
                LiberateMemory((void **) &colormap);
#if (MagickLibVersion > 0x0100000) /* GraphicsMagick - must pass image */
                ThrowWriterException(ResourceLimitError,
                  "Memory allocation failed", image);
#else
                ThrowWriterException(ResourceLimitError,
                  "Memory allocation failed")
#endif
              }
            image->colormap[opacity]=image->background_color;
            for (y=0; y < (long) image->rows; y++)
            {
              p=AcquireImagePixels(image,0,y,image->columns,1,
                &image->exception);
              if (p == (const PixelPacket *) NULL)
                break;
              indexes=GetIndexes(image);
              for (x=0; x < (long) image->columns; x++)
              {
                if (p->opacity == TransparentOpacity)
                  indexes[x]=(IndexPacket) opacity;
                p++;
              }
              if (!SyncImagePixels(image))
                break;
            }
          }
      }
    else
      if (image->matte)
        {
          /*
            Identify transparent pixel index.
          */
          for (y=0; y < (long) image->rows; y++)
          {
            p=AcquireImagePixels(image,0,y,image->columns,1,&image->exception);
            if (p == (const PixelPacket *) NULL)
              break;
            indexes=GetIndexes(image);
            for (x=0; x < (long) image->columns; x++)
            {
              if (p->opacity == TransparentOpacity)
                {
                  opacity=(long) indexes[x];
                  break;
                }
              p++;
            }
            if (x < (long) image->columns)
              break;
          }
        }
    if (image->colormap == (PixelPacket *) NULL)
      break;
    for (bits_per_pixel=1; bits_per_pixel < 8; bits_per_pixel++)
      if ((1UL << bits_per_pixel) >= image->colors)
        break;
    q=colormap;
    for (i=0; i < (long) image->colors; i++)
    {
      *q++=ScaleQuantumToChar(image->colormap[i].red);
      *q++=ScaleQuantumToChar(image->colormap[i].green);
      *q++=ScaleQuantumToChar(image->colormap[i].blue);
    }
    for ( ; i < (1L << bits_per_pixel); i++)
    {
      *q++=(Quantum) 0x0;
      *q++=(Quantum) 0x0;
      *q++=(Quantum) 0x0;
    }
    if ((image->previous == (Image *) NULL) || !image_info->adjoin)
      {
        /*
          Write global colormap.
        */
        c=0x80;
        c|=(8-1) << 4;  /* color resolution */
        c|=(bits_per_pixel-1);   /* size of global colormap */
        (void) WriteBlobByte(image,c);
        for (j=0; j < Max(image->colors-1,1); j++)
          if (FuzzyColorMatch(&image->background_color,image->colormap+j,0))
            break;
        (void) WriteBlobByte(image,(long) j);  /* background color */
        (void) WriteBlobByte(image,0x0);  /* reserved */
        (void) WriteBlob(image,3*(1 << bits_per_pixel),(const unsigned char*)colormap);
        for (j=0; j < 768; j++)
          global_colormap[j]=colormap[j];
      }
    if (LocaleCompare(image_info->magick,"GIF87") != 0)
      {
        /*
          Write Graphics Control extension.
        */
        (void) WriteBlobByte(image,0x21);
        (void) WriteBlobByte(image,0xf9);
        (void) WriteBlobByte(image,0x04);
        c=(unsigned char) ((int) image->dispose << 2);
        if (opacity >= 0)
          c|=0x01;
        (void) WriteBlobByte(image,c);
        (void) WriteBlobLSBShort(image,image->delay);
        (void) WriteBlobByte(image,opacity >= 0 ? opacity : 0);
        (void) WriteBlobByte(image,0x00);
        if (GetImageAttribute(image,"comment") != (ImageAttribute *) NULL)
          {
            const ImageAttribute
              *attribute;

            register char
              *p;

            size_t
              count;

            /*
              Write Comment extension.
            */
            (void) WriteBlobByte(image,0x21);
            (void) WriteBlobByte(image,0xfe);
            attribute=GetImageAttribute(image,"comment");
            p=attribute->value;
            while (strlen(p) != 0)
            {
              count=Min(strlen(p),255);
              (void) WriteBlobByte(image,(long) count);
              for (i=0; i < (long) count; i++)
                (void) WriteBlobByte(image,*p++);
            }
            (void) WriteBlobByte(image,0x0);
          }
        if ((image->previous == (Image *) NULL) &&
            (image->next != (Image *) NULL) && (image->iterations != 1))
          {
            /*
              Write Netscape Loop extension.
            */
            (void) WriteBlobByte(image,0x21);
            (void) WriteBlobByte(image,0xff);
            (void) WriteBlobByte(image,0x0b);
            (void) WriteBlob(image,11,(const unsigned char*)"NETSCAPE2.0");
            (void) WriteBlobByte(image,0x03);
            (void) WriteBlobByte(image,0x01);
            (void) WriteBlobLSBShort(image,image->iterations);
            (void) WriteBlobByte(image,0x00);
          }
      }
    (void) WriteBlobByte(image,',');  /* image separator */
    /*
      Write the image header.
    */
    page.x=image->page.x;
    page.y=image->page.y;
    if ((image->page.width != 0) && (image->page.height != 0))
      page=image->page;
    (void) WriteBlobLSBShort(image,page.x);
    (void) WriteBlobLSBShort(image,page.y);
    (void) WriteBlobLSBShort(image,image->columns);
    (void) WriteBlobLSBShort(image,image->rows);
    c=0x00;
    if (interlace != NoInterlace)
      c|=0x40;  /* pixel data is interlaced */
    for (j=0; j < (3*image->colors); j++)
      if (colormap[j] != global_colormap[j])
        break;
    if (j == (3*image->colors))
      (void) WriteBlobByte(image,c);
    else
      {
        c|=0x80;
        c|=(bits_per_pixel-1);   /* size of local colormap */
        (void) WriteBlobByte(image,c);
        (void) WriteBlob(image,3*(1 << bits_per_pixel),(const unsigned char*) colormap);
      }
    /*
      Write the image data.
    */
    c=Max(bits_per_pixel,2);
    (void) WriteBlobByte(image,c);
    status=EncodeCompressedGIFImage(image_info,image,Max(bits_per_pixel,2)+1);
    if (status == false)
      {
        LiberateMemory((void **) &global_colormap);
        LiberateMemory((void **) &colormap);
#if (MagickLibVersion > 0x0100000) /* GraphicsMagick - must pass image */
        ThrowWriterException(ResourceLimitError,"Memory allocation failed", image);
#else
        ThrowWriterException(ResourceLimitError,"Memory allocation failed")
#endif
      }
    (void) WriteBlobByte(image,0x0);
    if (image->next == (Image *) NULL)
      break;
    image=GetNextImage(image);
    if (!MagickMonitor(SaveImagesTag,scene++,GetImageListSize(image),&image->exception))
      break;
  } while (image_info->adjoin);
  (void) WriteBlobByte(image,';'); /* terminator */
  LiberateMemory((void **) &global_colormap);
  LiberateMemory((void **) &colormap);
  if (image_info->adjoin)
    while (image->previous != (Image *) NULL)
      image=image->previous;
  CloseBlob(image);
  return(true);
}