// FILE: gif.h

#ifndef _GIF_H_
#define _GIF_H_

#include "ComTypes.h"

#pragma pack (push, 1)

typedef struct
{
  char          Id[6];
  uint16        Width;
  uint16        Height;
  uint8         Info;
  uint8         BackGroundColor;
  uint8         Res;
} tGifScreenDescriptor;

typedef struct
{
  uint8         Red;
  uint8         Green;
  uint8         Blue;
} tGifColor;

typedef struct
{
  uint8         Id;
  uint16        LeftOffset;
  uint16        TopOffset;
  uint16        Width;
  uint16        Height;
  uint8         Info;
} tGifImageDescriptor;

#pragma pack (pop)

typedef enum
{
  GIF_ERROR_OK,
  GIF_ERROR_BAD_ARGUMENT,
  GIF_ERROR_MALFORMED_DATA,
  GIF_ERROR_NO_MEMORY,
  GIF_ERROR_UNSUPPORTED_FORMAT
} tGifError;

#ifdef __cplusplus
extern "C" {
#endif

extern tGifError Gif_Decode (const uint8* pGif,
                             size_t GifSize,
                             tGifScreenDescriptor* pScreenDescriptor,
                             tGifImageDescriptor* pImageDescriptor,
                             tGifColor** ppGlobalColorMap,
                             tGifColor** ppLocalColorMap,
                             int TightPixelPacking,
                             uint8** ppImage);

extern tGifError Gif_Encode (const uint8* pImage,
                             int TightPixelPacking,
                             uint16 Width,
                             uint16 Height,
                             uint16 ColorCount,
                             uint8 BackGroundColor,
                             tGifScreenDescriptor* pScreenDescriptor,
                             tGifImageDescriptor* pImageDescriptor,
                             uint8** ppCompressedImage,
                             size_t* pCompressedSize);

#ifdef __cplusplus
}
#endif

#endif // _GIF_H_

// FILE: gif.c

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

/*
  GIF structure:

  (GIF signature + Screen Descriptor) (Global Color Map)?
  (
    ((Image Descriptor) (Local Color Map)? (Raster Data))
   |
    (GIF Extension Block)
  )+
  (GIF Terminator)?

  ()  - occurs once
  ()? - optional: may not occur or may occur just once
  ()+ - occurs at least once
    | - logical or
*/

#define GIF_HASH_TABLE_SHIFT            12
#define GIF_HASH_TABLE_SIZE             (1 << GIF_HASH_TABLE_SHIFT)

#define GIF_EMPTY_HASH_LIST             0xFFFFu
#define GIF_NO_HASH_TABLE_ITEM          0xFFFFu

#define GIF_MK_HASH_ITEM(_PREV_INDEX_,_CH_,_NEXT_INDEX_) \
  (((uint32)(_PREV_INDEX_) & 0xFFF) | \
   ((uint32)((_CH_) & 0xFF) << 12) | \
   ((uint32)((_NEXT_INDEX_) & 0xFFF) << 20))

#define GIF_GET_HASH_NEXT_INDEX(_ITEM_) \
  (((_ITEM_) >> 20) & 0xFFF)

#define GIF_SET_HASH_NEXT_INDEX(_ITEM_,_NEXT_INDEX_) \
  _ITEM_ = (_ITEM_ & 0x000FFFFFUL) | \
            ((uint32)((_NEXT_INDEX_) & 0xFFF) << 20);

#define GIF_GET_HASH_PREV_INDEX(_ITEM_) \
  ((_ITEM_) & 0xFFF)

#define GIF_GET_HASH_CH(_ITEM_) \
  (((_ITEM_) >> 12) & 0xFF)

#define GIF_MK_HASH(_PREV_INDEX_,_CH_) \
  (((GIF_MK_HASH_ITEM(_PREV_INDEX_,_CH_,0) * 648055UL) >> 8) & 0xFFF)

#define GIF_CMP_HASH_ITEMS(_ITEM1_,_ITEM2_) \
  (((_ITEM1_) ^ (_ITEM2_)) & 0xFFFFFUL)

/*
  Encoding hash table organization:

  ...
  aIndices[100] = GIF_EMPTY_HASH_LIST - there're no items with hash value of 100

                          +--+
                          v  |
  aIndices[101] -> aItems[0]-+ - there's only one item with hash value of 101,
                                 this item is at index 0. Because it's the last
                                 (and the only) item on the list of items with
                                 hash value of 101, it points to itself.

                                         +--+
                                         v  |
  aIndices[102] -> aItems[87] -> aItems[13]-+ - there're two items with hash
                                                value of 102. The last one
                                                points to itself.
  ...

  aItems[x] layout:
  Bits: 31  ...  20 19  ...  12 11  ...  0
        \_________/ \_________/ \________/
             |           |           |
             |           |           +- previous index (GIF-specific data)
             |           +- character (GIF-specific data)
             |      \____________________/
             |                 |
             |                 +- 20-bit key
             +- next index - link to the next item with the same hash value
*/
typedef struct
{
  uint16 aIndices[GIF_HASH_TABLE_SIZE];
  uint32 aItems[GIF_HASH_TABLE_SIZE];
  uint16 ItemCount;
} tGifEncodeHashTable;

typedef struct
{
  uint8 Stream[256];
  uint8 Shift;
  uint8 Remainder;
} tGifBitstream;

typedef struct
{
  uint16 CodeClear;
  uint16 CodeEOI;
  uint16 CodeCnt;
  uint16 CurCodeSize;
} tGifCodesInfo;

typedef struct
{
  uint8* pImage;
  size_t Size;
  size_t Allocated;
} tGifCompressed;

typedef struct
{
  tGifBitstream         Bitstream;
  tGifCodesInfo         CodesInfo;
  tGifCompressed        Compressed;
} tGifEncodeContext;

typedef struct
{
  const uint8*          pGif;
  size_t                GifSize;
  size_t                Ofs;
  const uint8*          pBytestream;
  uint8                 BytestreamIndex;
  uint8                 BytestreamShift;
  uint8                 BytestreamRemainder;
  tGifCodesInfo         CodesInfo;
} tGifDecodeContext;

static const char Gif87aId[] = "GIF87a";
static const char Gif89aId[] = "GIF89a";

static
void HashTable_Insert (tGifEncodeHashTable* pHashTable,
                       uint16 PrevIndex,
                       uint8 Ch);

static
void HashTable_Init (tGifEncodeHashTable* pHashTable,
                     uint16 CodeClear)
{
  uint i;

  // Generic hash table code:

  // Set the number of items in the hash table to 0:
  pHashTable->ItemCount = 0;

  // Empty the hash-to-list map too:
  for (i = 0; i < GIF_HASH_TABLE_SIZE; i++)
  {
    pHashTable->aIndices[i] = GIF_EMPTY_HASH_LIST;
  }

  // GIF-specific hash table code:

  // Allocate and initialize the first items that
  // describe the color codes:
  for (i = 0; i < CodeClear; i++)
  {
    HashTable_Insert (pHashTable, GIF_NO_HASH_TABLE_ITEM, (uint8)i);
  }

  // Reserve 2 more items in the hash table for 2 codes:
  // CodeClear and CodeEOI. The items for these codes
  // can't be allocated for data when encoding because of
  // the special meaning of the codes associated with them,
  // hence skipping them:
  pHashTable->ItemCount += 2;
}

static
void HashTable_Insert (tGifEncodeHashTable* pHashTable,
                       uint16 PrevIndex,
                       uint8 Ch)
{
  uint16 Hash = GIF_MK_HASH (PrevIndex, Ch);
  uint16 NextIndex;

  // The last item in the list of items sharing the same hash value
  // will point to itself:
  if (pHashTable->aIndices[Hash] != GIF_EMPTY_HASH_LIST)
    NextIndex = pHashTable->aIndices[Hash];
  else
    NextIndex = pHashTable->ItemCount;

  // Allocate and push the new item onto the list:
  pHashTable->aIndices[Hash] = pHashTable->ItemCount;
  pHashTable->aItems[pHashTable->ItemCount] =
    GIF_MK_HASH_ITEM (PrevIndex, Ch, NextIndex);

  pHashTable->ItemCount++;
}

static
uint16 HashTable_Search (tGifEncodeHashTable* pHashTable,
                         uint16 PrevIndex,
                         uint8 Ch)
{
  uint16 Hash = GIF_MK_HASH (PrevIndex, Ch);

  if (pHashTable->aIndices[Hash] != GIF_EMPTY_HASH_LIST)
  {
    uint32 Item = GIF_MK_HASH_ITEM (PrevIndex, Ch, 0);
    uint16 i, j = pHashTable->aIndices[Hash];
    do
    {
      i = j;
      if (!GIF_CMP_HASH_ITEMS (pHashTable->aItems[i], Item))
        return i;
      // No match, try the next item on the list:
      j = GIF_GET_HASH_NEXT_INDEX (pHashTable->aItems[i]);
      // If the index of the next item is the same as
      // of the current item, the last item has been
      // processed and we're finished w/o a match:
    } while (j != i);
  }

  return GIF_NO_HASH_TABLE_ITEM;
}

static
tGifError BitStream_StoreBytes (tGifEncodeContext* pContext,
                                const uint8* pBytes,
                                size_t ByteCount)
{
  tGifError err = GIF_ERROR_OK;

  while (ByteCount)
  {
    size_t CanCopy;

    CanCopy = pContext->Compressed.Allocated - pContext->Compressed.Size;

    if (CanCopy)
    {
      memcpy (pContext->Compressed.pImage + pContext->Compressed.Size,
              pBytes,
              CanCopy);

      pContext->Compressed.Size += CanCopy;
      pBytes += CanCopy;
      ByteCount -= CanCopy;
    }

    if (ByteCount)
    {
      void* pNewLocation;

      pNewLocation = realloc (pContext->Compressed.pImage,
                              pContext->Compressed.Allocated + ByteCount);

      if (pNewLocation == NULL)
      {
        err = GIF_ERROR_NO_MEMORY;
        break;
      }

      pContext->Compressed.pImage = pNewLocation;
      pContext->Compressed.Allocated += ByteCount;
    }
  }

  return err;
}

static
tGifError BitStream_Store (tGifEncodeContext* pContext)
{
  tGifError err = GIF_ERROR_OK;

  if (pContext->Bitstream.Stream[0])
  {
    err = BitStream_StoreBytes (pContext,
                                pContext->Bitstream.Stream,
                                pContext->Bitstream.Stream[0] + 1);

    pContext->Bitstream.Stream[0] = 0;
  }

  return err;
}

static
tGifError BitStream_PutByte (tGifEncodeContext* pContext,
                             uint8 Data)
{
  tGifError err = GIF_ERROR_OK;

  pContext->Bitstream.Stream[++pContext->Bitstream.Stream[0]] = Data;

  if (pContext->Bitstream.Stream[0] >= 255)
    err = BitStream_Store (pContext);

  return err;
}

static
tGifError BitStream_Flush (tGifEncodeContext* pContext)
{
  tGifError err;

  if (pContext->Bitstream.Shift)
  {
    err = BitStream_PutByte (pContext, pContext->Bitstream.Remainder);
    if (err != GIF_ERROR_OK)
      return err;

    pContext->Bitstream.Shift = 0;
  }

  err = BitStream_Store (pContext);

  return err;
}

static
tGifError BitStream_PutCode (tGifEncodeContext* pContext,
                             uint16 Code)
{
  tGifError err = GIF_ERROR_OK;
  uint Cnt;

  if (!pContext->Bitstream.Shift)
    pContext->Bitstream.Remainder = 0;

  pContext->Bitstream.Remainder |=
    (Code << pContext->Bitstream.Shift) & 0xFF;

  Cnt = 8 - pContext->Bitstream.Shift;

  Code >>= Cnt; 

  while (Cnt < pContext->CodesInfo.CurCodeSize)
  {
    err = BitStream_PutByte (pContext, pContext->Bitstream.Remainder);
    if (err != GIF_ERROR_OK)
      return err;
    pContext->Bitstream.Remainder = Code & 0xFF;
    Code >>= 8;
    Cnt += 8;
  }

  pContext->Bitstream.Shift += pContext->CodesInfo.CurCodeSize;
  pContext->Bitstream.Shift &= 7;

  if (!pContext->Bitstream.Shift)
    err = BitStream_PutByte (pContext, pContext->Bitstream.Remainder);

  return err;
}

/*
  tbd:
  - option to find out compressed size
  - option to choose whether to save thru callback or keep in memory
  - option to specify custom malloc/free/realloc
*/
tGifError Gif_Encode (const uint8* pImage,
                      int TightPixelPacking,
                      uint16 Width,
                      uint16 Height,
                      uint16 ColorCount,
                      uint8 BackGroundColor,
                      tGifScreenDescriptor* pScreenDescriptor,
                      tGifImageDescriptor* pImageDescriptor,
                      uint8** ppCompressedImage,
                      size_t* pCompressedSize)
{
  tGifError err = GIF_ERROR_BAD_ARGUMENT;
  uint32 Area;
  uint BitsPerPixel;
  uint8 CodeSize;
  tGifEncodeHashTable* pHashTable = NULL;
  tGifEncodeContext Context;
  uint16 PrevIndex;
  uint8 Shift;

  memset (&Context, 0, sizeof(Context));
  Context.Compressed.pImage = NULL;

  if ((pImage == NULL) ||
      (!Width) || (!Height) ||
      (ColorCount < 2) || (ColorCount > 256) ||
      (ColorCount & (ColorCount - 1)) ||
//      (BackGroundColor >= ColorCount) ||
      (pScreenDescriptor == NULL) ||
      (pImageDescriptor == NULL) ||
      (ppCompressedImage == NULL) ||
      (pCompressedSize == NULL))
  {
    goto lerr;
  }

  if (ColorCount == 256)
    TightPixelPacking = 0;

  Area = (uint32)Width * Height;

  if ((!Area) || (Area / Width != Height))
  {
    goto lerr;
  }

  pHashTable = malloc (sizeof (*pHashTable));

  if (pHashTable == NULL)
  {
    err = GIF_ERROR_NO_MEMORY;
    goto lerr;
  }

  BitsPerPixel = 0;
  while ((1 << BitsPerPixel) < ColorCount)
    BitsPerPixel++;

  // GIF screen descriptor:

  memcpy (pScreenDescriptor->Id, Gif87aId, sizeof(pScreenDescriptor->Id));
  pScreenDescriptor->Width = Width;
  pScreenDescriptor->Height = Height;
  pScreenDescriptor->BackGroundColor = BackGroundColor;
  pScreenDescriptor->Res = 0;
  pScreenDescriptor->Info =
    0x80 |                      // Global color map is present
    ((BitsPerPixel-1)<<4) |     // Color resolution
    (BitsPerPixel-1);           // Bits per pixel

  // GIF global color map isn't used or stored here

  // GIF image descriptor:

  pImageDescriptor->Id = 0x2C;
  pImageDescriptor->LeftOffset =
    pImageDescriptor->TopOffset = 0;
  pImageDescriptor->Width = Width;
  pImageDescriptor->Height = Height;
  pImageDescriptor->Info = 0;   // Global color map & sequential order

  // GIF raster data stream initial code size:
  CodeSize = BitsPerPixel + (BitsPerPixel == 1); // extra 1 is neded :(

  err = BitStream_StoreBytes (&Context, &CodeSize, 1);
  if (err != GIF_ERROR_OK)
    goto lerr;

  // Setting up the needed work variables:

  Context.CodesInfo.CodeClear = 1 << CodeSize;
  Context.CodesInfo.CodeEOI = Context.CodesInfo.CodeClear + 1;
  Context.CodesInfo.CodeCnt = Context.CodesInfo.CodeClear + 2;
  Context.CodesInfo.CurCodeSize = CodeSize + 1;

  HashTable_Init (pHashTable, Context.CodesInfo.CodeClear);

  // Let's start encoding, first code must be CodeClear:

  err = BitStream_PutCode (&Context, Context.CodesInfo.CodeClear);
  if (err != GIF_ERROR_OK)
    goto lerr;

  // Begin with an empty sequence of pixels:
  PrevIndex = GIF_NO_HASH_TABLE_ITEM;

  Shift = 0;

  // Process all pixels of the image:
  do
  {
    uint16 i;
    uint8 Data, Pixel;

    // Get the next pixel and append to the current sequence of pixels:
    if (!TightPixelPacking)
    {
      Pixel = (*pImage++) & (ColorCount - 1);
    }
    else
    {
      if (!Shift)
      {
        Data = *pImage++ & 0xFF;
        Shift = 8;
      }

      if (Shift >= BitsPerPixel)
      {
        Pixel = Data & (ColorCount - 1);
        Data >>= BitsPerPixel;
        Shift -= BitsPerPixel;
      }
      else
      {
        Pixel = Data;
        Data = *pImage++ & 0xFF;
        Pixel |= (Data << Shift) & (ColorCount - 1);
        Data >>= BitsPerPixel - Shift;
        Shift = 8 - (BitsPerPixel - Shift);
      }
    }

    Area--;

    // Find a sequence of pixels like the current one in the hash table:
    i = HashTable_Search (pHashTable, PrevIndex, Pixel);

    if (i != GIF_NO_HASH_TABLE_ITEM)
    {
      // Found, keep growing the current sequence of pixels until it's unique:
      PrevIndex = i;
    }
    else // elseof if (i != GIF_NO_HASH_TABLE_ITEM)
    {
      // The last pixel made the current pixel sequence unique, so
      // we must store the code representing the entire subsequence before
      // the last pixel and possibly store the sequence in the hash table:
      err = BitStream_PutCode (&Context, PrevIndex);
      if (err != GIF_ERROR_OK)
        goto lerr;

      // Grow the bit size of the code if needed:
      if ((Context.CodesInfo.CodeCnt == (1 << Context.CodesInfo.CurCodeSize)) &&
          (Context.CodesInfo.CurCodeSize < GIF_HASH_TABLE_SHIFT))
        Context.CodesInfo.CurCodeSize++;

#if 0
      if (Context.CodesInfo.CodeCnt >= GIF_HASH_TABLE_SIZE - 1)
      {
        // If the hash table is full, reinitialize it and start over:
        err = BitStream_PutCode (&Context, Context.CodesInfo.CodeClear);
        if (err != GIF_ERROR_OK)
          goto lerr;

        HashTable_Init (pHashTable, Context.CodesInfo.CodeClear);

        Context.CodesInfo.CodeCnt = Context.CodesInfo.CodeClear + 2;
        Context.CodesInfo.CurCodeSize = CodeSize + 1;
      }
      else // elseof if (Context.CodesInfo.CodeCnt >= GIF_HASH_TABLE_SIZE - 1)
      {
        // If there's enough space for another item in the hash table,
        // store the current pixel sequence there:
        HashTable_Insert (pHashTable, PrevIndex, Pixel);
        Context.CodesInfo.CodeCnt++;
      }
#else
      // If there's enough space for another item in the hash table,
      // store the current pixel sequence there:
      if (Context.CodesInfo.CodeCnt < GIF_HASH_TABLE_SIZE)
        HashTable_Insert (pHashTable, PrevIndex, Pixel);
// worse compression may be because of the table reinit
// that doesn't give us a chance to use the last table element
// or store extra code(s) $$$:
      if (++Context.CodesInfo.CodeCnt >= GIF_HASH_TABLE_SIZE)
      {
        // If the hash table is full, reinitialize it and start over:
        err = BitStream_PutCode (&Context, Context.CodesInfo.CodeClear);
        if (err != GIF_ERROR_OK)
          goto lerr;

        HashTable_Init (pHashTable, Context.CodesInfo.CodeClear);

        Context.CodesInfo.CodeCnt = Context.CodesInfo.CodeClear + 2;
        Context.CodesInfo.CurCodeSize = CodeSize + 1;
      }
#endif

      // Shrink the current pixel sequence down to the last pixel:
      PrevIndex = Pixel;
    } // if (i != GIF_NO_HASH_TABLE_ITEM)
  } while (Area);

  // Store the remaining data of the current pixel sequence:
  err = BitStream_PutCode (&Context, PrevIndex);
  if (err != GIF_ERROR_OK)
    goto lerr;

  // Store the End Of Image code:
  err = BitStream_PutCode (&Context, Context.CodesInfo.CodeEOI);
  if (err != GIF_ERROR_OK)
    goto lerr;

  // Flush/store all buffered bitsream data bits:
  err = BitStream_Flush (&Context);
  if (err != GIF_ERROR_OK)
    goto lerr;

  // Raster data end ID:
  CodeSize = 0;
  err = BitStream_StoreBytes (&Context, &CodeSize, 1);
  if (err != GIF_ERROR_OK)
    goto lerr;

  // GIF terminator:
  CodeSize = 0x3B;
  err = BitStream_StoreBytes (&Context, &CodeSize, 1);
  if (err != GIF_ERROR_OK)
    goto lerr;

  *ppCompressedImage = Context.Compressed.pImage;
  *pCompressedSize = Context.Compressed.Size;

  err = GIF_ERROR_OK;

lerr:

  if (err != GIF_ERROR_OK)
  {
    if ((ppCompressedImage != NULL) && (*ppCompressedImage != NULL))
    {
      free (*ppCompressedImage);
      *ppCompressedImage = NULL;
    }

    if (pCompressedSize != NULL)
    {
      *pCompressedSize = 0;
    }
  }

  if (pHashTable != NULL)
    free (pHashTable);

  return err;
}

static
tGifError BitStream_GetByte (tGifDecodeContext* pContext,
                             uint8* pData)
{
  tGifError err = GIF_ERROR_OK;

  if (pContext->pBytestream == NULL)
  {
    pContext->pBytestream = pContext->pGif + pContext->Ofs;
    pContext->BytestreamIndex = 1;
  }

  if ((pContext->BytestreamIndex >=
       pContext->pGif + pContext->GifSize - pContext->pBytestream) ||
      !pContext->pBytestream[0])
  {
    return GIF_ERROR_MALFORMED_DATA;
  }

  *pData = pContext->pBytestream[pContext->BytestreamIndex];

  if (pContext->BytestreamIndex < pContext->pBytestream[0])
  {
    pContext->BytestreamIndex++;
  }
  else
  {
    pContext->pBytestream += 1 + pContext->pBytestream[0];
    pContext->BytestreamIndex = 1;
  }

  return err;
}

static
tGifError BitStream_GetCode (tGifDecodeContext* pContext,
                             uint16* pCode)
{
  tGifError err = GIF_ERROR_OK;
  uint Cnt = 0;
  uint16 Code = 0;

  if (!pContext->BytestreamShift)
  {
    err = BitStream_GetByte (pContext, &pContext->BytestreamRemainder);
    if (err != GIF_ERROR_OK)
      return err;
  }

  Code = (pContext->BytestreamRemainder & 0xFF) >> pContext->BytestreamShift;

  Cnt = 8 - pContext->BytestreamShift;

  pContext->BytestreamShift += pContext->CodesInfo.CurCodeSize;
  pContext->BytestreamShift &= 7;

  while (Cnt < pContext->CodesInfo.CurCodeSize)
  {
    err = BitStream_GetByte (pContext, &pContext->BytestreamRemainder);
    if (err != GIF_ERROR_OK)
      return err;
    Code |= (uint16)(pContext->BytestreamRemainder & 0xFF) << Cnt;
    Cnt += 8;
  }

  Code &= (1 << pContext->CodesInfo.CurCodeSize) - 1;

  *pCode = Code;

  return err;
}

tGifError Gif_Decode (const uint8* pGif,
                      size_t GifSize,
                      tGifScreenDescriptor* pScreenDescriptor,
                      tGifImageDescriptor* pImageDescriptor,
                      tGifColor** ppGlobalColorMap,
                      tGifColor** ppLocalColorMap,
                      int TightPixelPacking,
                      uint8** ppImage)
{
  tGifError err = GIF_ERROR_BAD_ARGUMENT;
  uint BitsPerPixel;
  uint ColorCount;
  size_t Ofs = 0;
  uint32 Area;
  uint32 DecompressedImageSize;
  tGifDecodeContext Context;
  uint8 CodeSize;
  uint32* pHashTable = NULL;
  uint16 PrevCode, Code;
  int IsFirstCode = 1;
  uint8 FirstChar;
  uint8* pImage;
  uint8 Shift = 0;
  uint8 Remainder;

  memset (&Context, 0, sizeof(Context));
  Context.pGif = pGif;
  Context.GifSize = GifSize;

  if (ppGlobalColorMap != NULL)
    *ppGlobalColorMap = NULL;
  if (ppLocalColorMap != NULL)
    *ppLocalColorMap = NULL;
  if (ppImage != NULL)
    *ppImage = NULL;

  if ((pGif == NULL) ||
      (GifSize < sizeof(tGifScreenDescriptor)) ||
      (pScreenDescriptor == NULL) ||
      (pImageDescriptor == NULL) ||
      (ppGlobalColorMap == NULL) ||
      (ppLocalColorMap == NULL) ||
      (ppImage == NULL))
  {
    goto lerr;
  }

  // Validate Screen Descriptor:

  *pScreenDescriptor = *(tGifScreenDescriptor*)pGif;

  err = GIF_ERROR_MALFORMED_DATA;

  BitsPerPixel = 1 + (pScreenDescriptor->Info & 7);
  ColorCount = 1 << BitsPerPixel;

  if (!memcmp (pScreenDescriptor->Id, Gif87aId, sizeof(pScreenDescriptor->Id)))
  {
    // This bit is 0 only in GIF87a's, but may be 1 in GIF89a's:
    if (pScreenDescriptor->Info & 8)
      goto lerr;
  }
  else if (memcmp (pScreenDescriptor->Id, Gif89aId, sizeof(pScreenDescriptor->Id)))
  {
    goto lerr;
  }

  if ((!pScreenDescriptor->Width) ||
      (!pScreenDescriptor->Height) ||
//      (pScreenDescriptor->BackGroundColor >= ColorCount) ||
      (pScreenDescriptor->Res))
  {
    goto lerr;
  }

  Ofs += sizeof (tGifScreenDescriptor);

  // Global Color Map:

  if (pScreenDescriptor->Info & 0x80)
  {
    if (GifSize - Ofs < ColorCount * sizeof (tGifColor))
      goto lerr;

    *ppGlobalColorMap = malloc (ColorCount * sizeof (tGifColor));

    if (*ppGlobalColorMap == NULL)
    {
      err = GIF_ERROR_NO_MEMORY;
      goto lerr;
    }

    memcpy (*ppGlobalColorMap,
            pGif + Ofs,
            ColorCount * sizeof (tGifColor));

    Ofs += ColorCount * sizeof (tGifColor);
  }

  // Locate Image Descriptor:
  for (;;)
  {
    if (GifSize - Ofs < sizeof (tGifImageDescriptor))
      goto lerr;

    switch (pGif[Ofs])
    {
      case 0x2C: // Image Descriptor
        break;

      case 0x21: // Extension Block
        Ofs += 2;
        for (;;)
        {
          if ((GifSize - Ofs < 1) || (GifSize - Ofs < 1 + pGif[Ofs]))
            goto lerr;
          else if (!pGif[Ofs])
            break;
          else
            Ofs += 1 + pGif[Ofs];
        }
        Ofs++;
        continue;

      default:
        goto lerr;
    }

    break;
  }

  // Validate Image Descriptor:

  *pImageDescriptor = *(tGifImageDescriptor*)(pGif + Ofs);

  if ((pImageDescriptor->Id != 0x2C) ||
      (!pImageDescriptor->Width) ||
      (!pImageDescriptor->Height) ||
      ((uint32)pImageDescriptor->LeftOffset + pImageDescriptor->Width >
       pScreenDescriptor->Width) ||
      ((uint32)pImageDescriptor->TopOffset + pImageDescriptor->Height >
       pScreenDescriptor->Height) ||
      (pImageDescriptor->Info & 0x38))
  {
    goto lerr;
  }

  Ofs += sizeof (tGifImageDescriptor);

  // Local Color Map:

  if (pImageDescriptor->Info & 0x80)
  {
    BitsPerPixel = 1 + (pImageDescriptor->Info & 7);
    ColorCount = 1 << BitsPerPixel;

    if (GifSize - Ofs < ColorCount * sizeof (tGifColor))
      goto lerr;

    *ppLocalColorMap = malloc (ColorCount * sizeof (tGifColor));

    if (*ppLocalColorMap == NULL)
    {
      err = GIF_ERROR_NO_MEMORY;
      goto lerr;
    }

    memcpy (*ppLocalColorMap,
            pGif + Ofs,
            ColorCount * sizeof (tGifColor));

    Ofs += ColorCount * sizeof (tGifColor);
  }

  if (!((pImageDescriptor->Info | pScreenDescriptor->Info) & 0x80))
    goto lerr;

  Area = (uint32)pImageDescriptor->Width * pImageDescriptor->Height;

  if (TightPixelPacking)
    DecompressedImageSize = (Area * BitsPerPixel + 7) / 8;
  else
    DecompressedImageSize = Area;

  if (DecompressedImageSize != (size_t)DecompressedImageSize)
  {
    err = GIF_ERROR_NO_MEMORY;
    goto lerr;
  }

  // Allocate memory for the image:
  *ppImage = malloc ((size_t)DecompressedImageSize);

  if (*ppImage == NULL)
  {
    err = GIF_ERROR_NO_MEMORY;
    goto lerr;
  }

  pImage = *ppImage;

  // Allocate memory for the table:
  pHashTable = malloc (sizeof(uint32) * GIF_HASH_TABLE_SIZE);

  if (pHashTable == NULL)
  {
    err = GIF_ERROR_NO_MEMORY;
    goto lerr;
  }

  if (pImageDescriptor->Info & 0x40)
  {
    // No interlaced image support yet:
    err = GIF_ERROR_UNSUPPORTED_FORMAT;
    goto lerr;
  }

  // GIF raster data stream initial code size:

  if (Ofs >= GifSize)
    goto lerr;

  CodeSize = pGif[Ofs++] & 0xFF;

#if 0
  // Unfortunately, this condition doesn't hold for all images:
  if (CodeSize != BitsPerPixel + (BitsPerPixel == 1))
#else
  // This condition is less restrictive:
  if ((CodeSize < 2) || (CodeSize > 8))
#endif
    goto lerr;

  // Setting up the needed work variables:

  Context.CodesInfo.CodeClear = 1 << CodeSize;
  Context.CodesInfo.CodeEOI = Context.CodesInfo.CodeClear + 1;
  Context.CodesInfo.CodeCnt = Context.CodesInfo.CodeClear + 2;
  Context.CodesInfo.CurCodeSize = CodeSize + 1;
  Context.Ofs = Ofs;

  // Initialize the table:
  for (Code = 0; Code < Context.CodesInfo.CodeClear; Code++)
    pHashTable[Code] = GIF_MK_HASH_ITEM (GIF_NO_HASH_TABLE_ITEM, Code, 0);

  // Let's start decoding, first code must be CodeClear:

  err = BitStream_GetCode (&Context, &Code);
  if ((err != GIF_ERROR_OK) || (Code != Context.CodesInfo.CodeClear))
    goto lerr;

  for (;;)
  {
    PrevCode = Code;

    err = BitStream_GetCode (&Context, &Code);
    if (err != GIF_ERROR_OK)
      goto lerr;

    if (Code == Context.CodesInfo.CodeClear)
    {
      // Reinitialize the table:
      Context.CodesInfo.CodeCnt = Context.CodesInfo.CodeClear + 2;
      Context.CodesInfo.CurCodeSize = CodeSize + 1;
      IsFirstCode = 1;
      continue;
    }
    else if (Code == Context.CodesInfo.CodeEOI)
    {
#if 0
      // This will never break if size yet to be decoded is analyzed elsewhere
      if (!Area)
        break;
#endif
      err = GIF_ERROR_MALFORMED_DATA;
      goto lerr;
    }
    else if (Code <= Context.CodesInfo.CodeCnt)
    {
      int i = 2, OperationOrder;

      if ((OperationOrder = (Code == Context.CodesInfo.CodeCnt)) && IsFirstCode)
      {
        // The first code must exist in the table when the table has just
        // been (re)initialized:
        err = GIF_ERROR_MALFORMED_DATA;
        goto lerr;
      }

      while (i--)
      {
        if (OperationOrder)
        {
          if (Context.CodesInfo.CodeCnt >= GIF_HASH_TABLE_SIZE)
          {
            // Table overflow:
            err = GIF_ERROR_MALFORMED_DATA;
            goto lerr;
          }

          pHashTable[Context.CodesInfo.CodeCnt] =
            GIF_MK_HASH_ITEM (PrevCode, FirstChar, 0);

          if (++Context.CodesInfo.CodeCnt == (1 << Context.CodesInfo.CurCodeSize) &&
              (Context.CodesInfo.CurCodeSize < GIF_HASH_TABLE_SHIFT))
             Context.CodesInfo.CurCodeSize++;
        }
        else // elseof if (OperationOrder)
        {
          uint Cnt = 0, SkipCnt = 0;
          uint16 Code2 = Code;

          // Decode the sequence of pixels (in the reverse order) for the
          // code into the free space of the table:
          while (Code2 > Context.CodesInfo.CodeEOI)
          {
            GIF_SET_HASH_NEXT_INDEX (pHashTable[Cnt],
                                     GIF_GET_HASH_CH (pHashTable[Code2]) &
                                     (ColorCount - 1));
            Code2 = GIF_GET_HASH_PREV_INDEX (pHashTable[Code2]);
            Cnt++;
          }

          FirstChar = GIF_GET_HASH_CH (pHashTable[Code2]) & (ColorCount - 1);
          GIF_SET_HASH_NEXT_INDEX (pHashTable[Cnt], FirstChar);
          Cnt++;

          if (Cnt > Area)
          {
#if 0
            err = GIF_ERROR_MALFORMED_DATA;
            goto lerr;
#else
            // Some encoders encode more data than necessary (off-by-X bug? :),
            // don't fail, just ignore what doesn't fit:
            SkipCnt = Cnt - Area;
            Cnt = Area;
#endif
          }

          Area -= Cnt;

          // Now, store the pixels:
          if (!TightPixelPacking)
          {
            while (Cnt--)
            {
              *pImage++ = GIF_GET_HASH_NEXT_INDEX (pHashTable[Cnt + SkipCnt]);
            }
          }
          else
          {
            while (Cnt--)
            {
              uint8 Cnt2;
              uint8 Pixel = GIF_GET_HASH_NEXT_INDEX (pHashTable[Cnt + SkipCnt]);

              if (!Shift)
                Remainder = 0;

              Remainder |= (Pixel << Shift) & 0xFF;

              Cnt2 = 8 - Shift;

              Pixel >>= Cnt2; 

              if (Cnt2 < BitsPerPixel)
              {
                *pImage++ = Remainder;
                Remainder = Pixel;
              }

              Shift += BitsPerPixel;
              Shift &= 7;

              if (!Shift)
                *pImage++ = Remainder;
            }

            // Store the remaining last bits if it was tight packing
            // and we're done:
            if (Shift && !Area)
              *pImage++ = Remainder;
          }

          // If all has been decoded, don't check for CodeEOI,
          // just finish. Btw, not all encoders produce CodeEOI,
          // raster data end ID and GIF terminator:
          if (!Area)
            goto lok;

          if (IsFirstCode)
          {
            // The first code after CodeClear is only used for decoding,
            // no table insertion is made for it, breaking out of the loop:
            IsFirstCode = 0;
            break; // while (i--)
          }
        } // endof if (OperationOrder)

        OperationOrder ^= 1;
      } // endof while (i--)
    }
    else // elseof else if (Code <= Context.CodesInfo.CodeCnt)
    {
      // The code must either exist in the table or be numerically the next
      // to be added to the table. If it's too big numerically, fail:
      err = GIF_ERROR_MALFORMED_DATA;
      goto lerr;
    }
  } // endof for (;;)

lok:

  err = GIF_ERROR_OK;

lerr:

  if (err != GIF_ERROR_OK)
  {
    if ((ppGlobalColorMap != NULL) && (*ppGlobalColorMap != NULL))
    {
      free (*ppGlobalColorMap);
      *ppGlobalColorMap = NULL;
    }
    if ((ppLocalColorMap != NULL) && (*ppLocalColorMap != NULL))
    {
      free (*ppLocalColorMap);
      *ppLocalColorMap = NULL;
    }
    if ((ppImage != NULL) && (*ppImage != NULL))
    {
      free (*ppImage);
      *ppImage = NULL;
    }
  }

  if (pHashTable != NULL)
    free (pHashTable);

  return err;
}

// FILE: ComTypes.h

#ifndef _COMTYPES_H_
#define _COMTYPES_H_

#include <stddef.h>

typedef unsigned char uchar;
typedef signed char schar;
typedef unsigned int uint;
typedef unsigned short int ushort;
typedef unsigned long int ulong;

typedef signed char int8;
typedef unsigned char uint8;

typedef signed short int int16;
typedef unsigned short int uint16;

typedef signed long int int32;
typedef unsigned long int uint32;

#if defined(__DJGPP__) || defined(__GNUC__)
typedef signed long long int int64;
typedef unsigned long long int uint64;
#endif
#if defined(_MSC_VER) || defined(__WATCOMC__)
typedef __int64 int64;
typedef unsigned __int64 uint64;
#endif

#ifdef __TURBOC__
 #ifdef inline
  #undef inline
 #endif
 #define inline
#endif

#if defined (__GNUC__) || defined(__386__)
 #ifdef far
  #undef far
 #endif
 #define far
#endif

#endif // _COMTYPES_H_