// FILE: gif.h

#ifndef _gif_
#define _gif_

//#define _gif_info_

typedef struct {
  char ID[6]                            __attribute__ ((packed));
  short Width                           __attribute__ ((packed));
  short Height                          __attribute__ ((packed));
  char Info                             __attribute__ ((packed));
  char BackGroundColor                  __attribute__ ((packed));
  char Res                              __attribute__ ((packed));
} GIF_Screen_Descriptor;

typedef struct {
  char Red                              __attribute__ ((packed));
  char Green                            __attribute__ ((packed));
  char Blue                             __attribute__ ((packed));
} GIF_Color;

typedef struct {
  short LeftOffset                      __attribute__ ((packed));
  short TopOffset                       __attribute__ ((packed));
  short Width                           __attribute__ ((packed));
  short Height                          __attribute__ ((packed));
  char Info                             __attribute__ ((packed));
} GIF_Image_Descriptor;

typedef struct {
  short prev                            __attribute__ ((packed));
  char data                             __attribute__ ((packed));
} GIF_HT_Item;

extern int GIF_error;

extern char *Load_GIF (char *name, int *l, int *h, char *pal,
                         int *color_cnt, char *bg_color);
extern int Save_GIF (char *name, char *pic, char *pal, int l, int h,
                 int color_cnt, char bg_color);

#endif

// FILE: gif.c

#include <stdlib.h>
#include <stdio.h>
#include <mem.h>
#include <string.h>
#include "gif.h"

GIF_HT_Item GIF_HashTable[4096];
int GIF_cClear, GIF_cEOI, GIF_cMax;
int GIF_cur_code_size;
int GIF_cMask[] = {0,1,3,7,0xF,0x1F,0x3F,0x7F,0xFF,0x1FF,0x3FF,0x7FF,0xFFF};
char *GIF_pic=NULL, *GIF_p;
int GIF_bytes_left;
char GIF_Pixel[4096];
char GIF_first_char;
int GIF_IsInterlaced, GIF_LineWidth, GIF_PixelsLeft, GIF_LineCnt, GIF_LineNo, GIF_IIndex;
int GIF_VOffs[] = {0,4,2,1,-1};
int GIF_VStep[] = {8,8,4,2,-1};
int GIF_error=0;

FILE *GIF_f;//, *tst;
unsigned char GIF_bstream[255];
int GIF_bstream_size;
int GIF_bstream_flag;
int GIF_bstream_index;
int GIF_bstream_shift;
int GIF_remainder;

void GIF_Init_HashTable() {
  int i;

  for (i=0;i<GIF_cClear;i++) {
    GIF_HashTable[i].prev = -1;
    GIF_HashTable[i].data = i;
  };
  GIF_HashTable[GIF_cClear].prev =
  GIF_HashTable[GIF_cEOI].prev = -2;
}

int GIF_Get_Char() {
  int res;
  if (GIF_bstream_flag==0) {
    if (fread(&GIF_bstream_size,1,1,GIF_f)!=1) return -1;
    if (GIF_bstream_size==0) return -1;
    if (fread(GIF_bstream,1,GIF_bstream_size,GIF_f)!=GIF_bstream_size) return -1;
    res = GIF_bstream[0];
    GIF_bstream_index=GIF_bstream_flag=1;
  } else
    res = GIF_bstream[GIF_bstream_index++];
  if (GIF_bstream_index == GIF_bstream_size) GIF_bstream_flag=0;
  return res;
};

int GIF_Get_Code() {
  int res, cnt;

  if (GIF_bstream_shift==0)
    if ((GIF_remainder = GIF_Get_Char()) == -1) return -1;
  res = (GIF_remainder >> GIF_bstream_shift);
  cnt = 8 - GIF_bstream_shift;
  GIF_bstream_shift += GIF_cur_code_size; GIF_bstream_shift &= 7;

  while (cnt < GIF_cur_code_size) {
    if ((GIF_remainder = GIF_Get_Char()) == -1) return -1;
    res |= (GIF_remainder << cnt);
    cnt += 8;
  };

//  fprintf (tst, "%X\n", res & GIF_cMask[GIF_cur_code_size]);
  return res & GIF_cMask[GIF_cur_code_size];
}

void GIF_Output_Pixels (int code) {
  int cnt=0, cnt2;

  while (code > GIF_cEOI) {
    GIF_Pixel[cnt] = GIF_HashTable[code].data;
    code = GIF_HashTable[code].prev;
    cnt++;
  };
  GIF_first_char = GIF_Pixel[cnt] = GIF_HashTable[code].data;
  cnt++;
  if (cnt > GIF_bytes_left) cnt = GIF_bytes_left;
  GIF_bytes_left -= cnt;
  if (!GIF_IsInterlaced)
    while (cnt) *GIF_p++ = GIF_Pixel[--cnt];
  else {
l:
    if (cnt < GIF_PixelsLeft) {
      GIF_PixelsLeft -= cnt;
      while (cnt) *GIF_p++ = GIF_Pixel[--cnt];
    } else {
      cnt2 = cnt;
      cnt -= GIF_PixelsLeft;
      while (GIF_PixelsLeft--) *GIF_p++ = GIF_Pixel[--cnt2];
      GIF_LineNo += GIF_VStep[GIF_IIndex];
      while (GIF_LineNo >= GIF_LineCnt) {
        GIF_IIndex++;
        GIF_LineNo = GIF_VOffs[GIF_IIndex];
      };
      GIF_p = GIF_pic + GIF_LineNo*GIF_LineWidth;
      GIF_PixelsLeft = GIF_LineWidth;
      if (cnt) goto l;
    };
  };
}

char *Load_GIF (char *name, int *l, int *h, char *pal, int *color_cnt,
                 char *bg_color) {
  GIF_Screen_Descriptor sd;
  GIF_Image_Descriptor id;
  int BitsPerPixel, MaxImgColors, MaxColors, Global, Interlaced;
  char ID[7];
  char code_size;
  int code, old_code;
  
  GIF_error=1;
  if (!(GIF_f = fopen(name, "rb"))) {
lerr:
//    fclose (tst);
    if (GIF_pic!=NULL) free (GIF_pic);
    fclose (GIF_f);
    *l=*h=*color_cnt=*bg_color=0;
//    printf ("bytes loaded: %d\n", GIF_p-GIF_pic);
    return NULL;
  };

/* Loading and displaying GIF screen descriptor */

  GIF_error=2;
  if (fread(&sd,1,sizeof(sd),GIF_f)!=sizeof(sd)) goto lerr;
  memset (&ID, 0, sizeof(ID));
  memcpy (&ID, &sd.ID, 6);
  GIF_error=3;
  if ((strcmp(ID,"GIF87a")!=0) && (strcmp(ID,"GIF89a"))!=0) goto lerr;
  BitsPerPixel = 1+(sd.Info&7);
  MaxImgColors = 1<<(((sd.Info>>4)&7)+1);
  MaxColors = 1<<BitsPerPixel;
  Global = sd.Info>>7;
  *bg_color = sd.BackGroundColor;

#ifdef _gif_info_
  printf (" -= General information =-\n");
  printf ("GIF ID:              %s\n", ID);
  printf ("Screen dimensions:   %dx%d\n", sd.Width, sd.Height);
  if (Global) printf ("Global color map:    present\n");
  else printf ("Global color map:    not present\n");
  printf ("Bits per pixel:      %d\n", BitsPerPixel);
  printf ("Max colors:          %d\n", MaxColors);
  printf ("Max colors in image: %d\n", MaxImgColors);
#endif

/* Loading GIF global color map */

  GIF_error=4;
  if (Global)
    if (fread(pal,sizeof(GIF_Color),MaxColors,GIF_f)!=
        MaxColors) goto lerr;

/* Loading and displaying GIF image descriptor */

  do {
    GIF_error=5;
    if (fread(&ID[0],1,1,GIF_f)!=1) goto lerr;
    if (ID[0] == 0x2C) break;                   // Image descriptor ID
    GIF_error=6;
    if (ID[0] != 0x21) goto lerr;               // Extension Block ID
    GIF_error=7;
    if (fread(&ID[1],1,1,GIF_f)!=1) goto lerr;  // Function code
lskip:
    GIF_error=8;
    if (fread(&ID[1],1,1,GIF_f)!=1) goto lerr;  // Function data count
    if (ID[1] == 0) continue;
    GIF_error=9;
    if (fseek (GIF_f, ID[1], SEEK_CUR)) goto lerr;
    goto lskip;
  } while (1);
  GIF_error=10;
  if (fread(&id,1,sizeof(id),GIF_f)!=sizeof(id)) goto lerr;

  GIF_error=11;
  if (!(id.Width*id.Height)) goto lerr;
  *l = id.Width; *h = id.Height;
  Global = !(id.Info>>7);
  if (!Global) BitsPerPixel = 1+(id.Info&7);
  *color_cnt = MaxColors = 1<<BitsPerPixel;
  Interlaced = (id.Info>>6)&1;

#ifdef _gif_info_
  printf (" -= Image information =-\n");
  printf ("Image dimensions:    %dx%d\n", id.Width, id.Height);
  if (Global) printf ("Color map used:      global\n");
  else printf ("Color map used:      local\n");
  if (Interlaced) printf ("Form of storage:     interlaced\n");
  else printf("Form of storage:     sequential\n");
  printf ("Bits per pixel:      %d\n", BitsPerPixel);
  printf ("Max colors:          %d\n", MaxColors);
#endif

/* Loading GIF local color map */

  GIF_error=12;
  if (!Global)
    if (fread(pal,sizeof(GIF_Color),MaxColors,GIF_f)!=
        MaxColors) goto lerr;

/* Loading raster data stream */

  GIF_error=13;
  if (fread(&code_size,1,1,GIF_f)!=1) goto lerr;
  GIF_error=14;
  if ((code_size < 2) || (code_size > 11)) goto lerr;

#ifdef _gif_info_
  printf (" -= Raster information =-\n");
  printf ("code size (bits):    %d\n", code_size);
#endif

  GIF_bytes_left=(*l)*(*h);
  GIF_error=15;
  if ((GIF_pic = malloc(GIF_bytes_left))==NULL) goto lerr;

/* Initialazing variables */

  GIF_p = GIF_pic;
  GIF_LineWidth = *l;
  GIF_LineCnt = *h;
  GIF_PixelsLeft = GIF_LineWidth;
  GIF_IIndex = GIF_LineNo = 0;
  GIF_IsInterlaced = Interlaced;
  GIF_cClear = 1<<code_size;
  GIF_cEOI = GIF_cClear+1;
  GIF_cMax = GIF_cEOI+1;
  GIF_cur_code_size = code_size+1;
  GIF_Init_HashTable();
  GIF_bstream_shift=0;                   // no shifts needed
  GIF_bstream_flag=0;                    // no bytes have yet been read

//  tst = fopen ("codes_in.txt", "wt");

  GIF_error=16;
  if (GIF_Get_Code() != GIF_cClear) goto lerr;
lclear:
  code = GIF_Get_Code();
  GIF_error=17;
  if (code<0) goto lerr;
  GIF_Output_Pixels (code);
  if (GIF_bytes_left == 0) goto lend;
  while (1) {
    old_code = code;
    code = GIF_Get_Code();
    GIF_error=18;
    if (code<0) goto lerr;
    if (code == GIF_cClear) {
      GIF_cMax = GIF_cEOI+1;
      GIF_cur_code_size = code_size+1;
      goto lclear;
    };
    if (code == GIF_cEOI) break;
    if (code < GIF_cMax) {
      GIF_Output_Pixels (code);
      if (GIF_bytes_left == 0) goto lend;
      GIF_HashTable[GIF_cMax].prev = old_code;
      GIF_HashTable[GIF_cMax].data = GIF_first_char;
      if ((++GIF_cMax == 1 << GIF_cur_code_size) && (GIF_cur_code_size<12))
        GIF_cur_code_size++;
    } else {
      GIF_HashTable[GIF_cMax].prev = old_code;
      GIF_HashTable[GIF_cMax].data = GIF_first_char;
      if ((++GIF_cMax == 1 << GIF_cur_code_size) && (GIF_cur_code_size<12))
        GIF_cur_code_size++;
      GIF_Output_Pixels (code);
      if (GIF_bytes_left == 0) goto lend;
    };
  };

//  fclose (tst);
lend:
  fclose (GIF_f);
  GIF_error = 0;
  return GIF_pic;
};

int GIF_Put_Char (unsigned char c) {
  GIF_bstream[GIF_bstream_size++] = c;
  if (GIF_bstream_size == 255) {
    if (fwrite(&GIF_bstream_size,1,1,GIF_f)!=1) return -1;
    if (fwrite(&GIF_bstream,1,GIF_bstream_size,GIF_f)!=GIF_bstream_size) return -1;
    GIF_bstream_size = 0;
  };
  return 0;
};

int GIF_Flush_Stream() {
  if (GIF_bstream_shift) {
    if (GIF_Put_Char((unsigned char)GIF_remainder)<0) return -1;
    GIF_bstream_shift = 0;
  };
  if (GIF_bstream_size) {
    if (fwrite(&GIF_bstream_size,1,1,GIF_f)!=1) return -1;
    if (fwrite(&GIF_bstream,1,GIF_bstream_size,GIF_f)!=GIF_bstream_size) return -1;
    GIF_bstream_size = 0;
  };
  return 0;
};

int GIF_Put_Code (int code) {
  int cnt;

//  fprintf (tst, "%X\n", code);
  if (!GIF_bstream_shift) GIF_remainder = 0;
  GIF_remainder |= code << GIF_bstream_shift;
  cnt = 8 - GIF_bstream_shift;
  if (cnt < GIF_cur_code_size) {
    code >>= cnt; 
    do {
      if (GIF_Put_Char ((unsigned char)GIF_remainder) < 0) return -1;
      GIF_remainder = code;
      code >>= 8;
      cnt += 8;
    } while (cnt < GIF_cur_code_size);
  };
  GIF_bstream_shift += GIF_cur_code_size; GIF_bstream_shift &= 7;
  if (!GIF_bstream_shift)
    if (GIF_Put_Char ((unsigned char)GIF_remainder) < 0) return -1;

  return 0;
}

int Save_GIF (char *name, char *pic, char *pal, int l, int h,
                 int color_cnt, char bg_color) {
  GIF_Screen_Descriptor sd;
  GIF_Image_Descriptor id;
  int BitsPerPixel, MaxColors;
  char ID[7]="GIF87a";
  char code_size, idID=0x2C;
  GIF_HT_Item X;
  int size, i, exists, search, ht_look=0;

  GIF_error=1;
  if ((l <= 0) || (h <= 0)) goto lerr;
  size = l*h;
  GIF_error=2;
  if ((color_cnt < 2) || (color_cnt > 256)) goto lerr;
  BitsPerPixel = 0;
  while (1<<BitsPerPixel < color_cnt) BitsPerPixel++;
  MaxColors = 1<<BitsPerPixel;
  
  GIF_error=3;
  if (!(GIF_f = fopen(name, "wb"))) {
lerr:
//    fclose (tst);
    fclose (GIF_f);
    return 0;
  };

/* Saving GIF screen descriptor */

  memcpy (sd.ID, ID, 6);
  sd.Width = l;
  sd.Height = h;
  sd.BackGroundColor = bg_color;
  sd.Res = 0;
  sd.Info = 0x80 |                      // Global color map is present
            ((BitsPerPixel-1)<<4) |     // Color resolution
            (BitsPerPixel-1);           // Bits per pixel
  GIF_error=4;
  if (fwrite(&sd,1,sizeof(sd),GIF_f)!=sizeof(sd)) goto lerr;

/* Saving GIF global color map */

  GIF_error=5;
  if (fwrite(pal,sizeof(GIF_Color),MaxColors,GIF_f)!=MaxColors) goto lerr;

/* Saving GIF image descriptor */

  id.LeftOffset = id.TopOffset = 0;
  id.Width = l;
  id.Height = h;
  id.Info = 0;                  // Global color map & sequential order
  GIF_error=6;
  if (fwrite(&idID,1,1,GIF_f)!=1) goto lerr;            // Img descr ID
  GIF_error=7;
  if (fwrite(&id,1,sizeof(id),GIF_f)!=sizeof(id)) goto lerr;// Img descriptor

/* Saving GIF raster data stream */

  if ((code_size = BitsPerPixel) == 1) code_size++;     // it's neded :(
  GIF_error=8;
  if (fwrite(&code_size,1,1,GIF_f)!=1) goto lerr;

/* Setting up needed variables */

  GIF_cClear = 1<<code_size;
  GIF_cEOI = GIF_cClear+1;
  GIF_cMax = GIF_cEOI+1;
  GIF_cur_code_size = code_size+1;
  GIF_Init_HashTable();
  GIF_bstream_shift=0;                   // no shifts needed
  GIF_bstream_size=0;                    // buffer is empty

//  tst = fopen ("codes_ou.txt", "wt");

/* Let's start encoding */

  GIF_error=9;
  if (GIF_Put_Code(GIF_cClear) < 0) goto lerr;// First code is always cClear

  search = X.prev = -1;

  do {
    X.data = *pic++; size--;
    if (X.prev == -1) {
      i = X.data;
      exists = 1;
    } else {
      exists = 0;
      for (i=1+search;i<GIF_cMax;i++) {
        ht_look++;
        if ((GIF_HashTable[i].prev==X.prev) && (GIF_HashTable[i].data==X.data)) {
          exists = 1;
          break;
        };
      };
    };
    if (exists) {
        search = X.prev = i;
    } else {
      GIF_error=10;
      if (GIF_Put_Code(X.prev) < 0) goto lerr;
      if ((GIF_cMax == 1 << GIF_cur_code_size) && (GIF_cur_code_size<12))
        GIF_cur_code_size++;
      if (GIF_cMax == 4096) {
        GIF_error=11;
        if (GIF_Put_Code(GIF_cClear) < 0) goto lerr;
        GIF_cMax = GIF_cEOI+1;
        GIF_cur_code_size = code_size+1;
        search=-1;
      } else {
        GIF_HashTable[GIF_cMax++] = X;
        search=GIF_cEOI;
      };
      X.prev = X.data;
    };
  } while (size);

  GIF_error=12;
  if (GIF_Put_Code(X.prev) < 0) goto lerr;
  GIF_error=13;
  if (GIF_Put_Code(GIF_cEOI) < 0) goto lerr;

/* Wow! We're near the end */

  GIF_error=14;
  if (GIF_Flush_Stream() < 0) goto lerr;        // Flush out the buffer
  idID = 0;
  GIF_error=15;
  if (fwrite(&idID,1,1,GIF_f)!=1) goto lerr;    // Raster data end ID

/* Saving GIF terminator */

  idID = 0x3B;
  GIF_error=16;
  if (fwrite(&idID,1,1,GIF_f)!=1) goto lerr;    // GIF end ID
  
//  fclose (tst);
  fclose (GIF_f);
  printf ("ht_look/size= %d\n", ht_look/(l*h-1));
  GIF_error = 0;
  return 1;
}