/*
*********************************************************************************************************
*                                             uC/GUI V3.98
*                        Universal graphic software for embedded applications
*
*                       (c) Copyright 2002, Micrium Inc., Weston, FL
*                       (c) Copyright 2002, SEGGER Microcontroller Systeme GmbH
*
*              礐/GUI is protected by international copyright laws. Knowledge of the
*              source code may not be used to write a similar product. This file may
*              only be used in accordance with a license and should not be redistributed
*              in any way. We appreciate your understanding and fairness.
*
----------------------------------------------------------------------
File        : GUI_GIF.c
Purpose     : Implementation of rendering GIF images
---------------------------END-OF-HEADER------------------------------
*/

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

#include "GUI_Private.h"

/*********************************************************************
*
*       Defines
*
**********************************************************************
*/
#define GIF_INTRO_TERMINATOR ';'
#define GIF_INTRO_EXTENSION  '!'
#define GIF_INTRO_IMAGE      ','

#define GIF_COMMENT     0xFE
#define GIF_APPLICATION 0xFF
#define GIF_PLAINTEXT   0x01
#define GIF_GRAPHICCTL  0xF9

#define MAX_NUM_LWZ_BITS 12

/*********************************************************************
*
*       Types
*
**********************************************************************
*/
typedef struct {
  const U8 * pSrc; /* Pointer used for reading the data */
  int RemBytes;    /* Number of remaining bytes */
} SOURCE;

typedef struct {
  int XPos;
  int YPos;
  int XSize;
  int YSize;
  int Flags;
  int NumColors;
} IMAGE_DESCRIPTOR;

typedef struct {
  U8    aBuffer[258];                     /* Input buffer for data block */
  short aCode  [(1 << MAX_NUM_LWZ_BITS)]; /* This array stores the LZW codes for the compressed strings */
  U8    aPrefix[(1 << MAX_NUM_LWZ_BITS)]; /* Prefix character of the LZW code. */
  U8    aDecompBuffer[3000];              /* Decompression buffer. The higher the compression, the more bytes are needed in the buffer. */
  U8 *  sp;                               /* Pointer into the decompression buffer */
  int   CurBit;
  int   LastBit;
  int   GetDone;
  int   LastByte;
  int   ReturnClear;
  int   CodeSize;
  int   SetCodeSize;
  int   MaxCode;
  int   MaxCodeSize;
  int   ClearCode;
  int   EndCode;
  int   FirstCode;
  int   OldCode;
} LZW_CONTEXT;

/*********************************************************************
*
*       Static const
*
**********************************************************************
*/
static const int _aMaskTbl[16] = {
  0x0000, 0x0001, 0x0003, 0x0007,
  0x000f, 0x001f, 0x003f, 0x007f,
  0x00ff, 0x01ff, 0x03ff, 0x07ff,
  0x0fff, 0x1fff, 0x3fff, 0x7fff,
};

static const int _aInterlaceOffset[] = {  8, 8, 4, 2 };
static const int _aInterlaceYPos[]   = {  0, 4, 2, 1 };

/*********************************************************************
*
*       Static data
*
**********************************************************************
*/
LZW_CONTEXT _LZWContext;
GUI_COLOR   _aColorTable[256];
SOURCE      _Source;
static U8   _aBuffer[256];

/*********************************************************************
*
*       Static code
*
**********************************************************************
*/
/*********************************************************************
*
*       _ReadU8
*
* Purpose:
*   Reads one byte from the given pointer if possible and increments the pointer
*/
static U8 _ReadU8(void) {
  U8 Value;
  _Source.RemBytes -= 1;
  if (_Source.RemBytes < 0) {
    return 0;
  }
  Value = *(_Source.pSrc++);
  return Value;
}

/*********************************************************************
*
*       _ReadU16
*
* Purpose:
*   Reads a word from the given pointer if possible and increments the pointer
*/
static U16 _ReadU16(void) {
  U16 Value;
  U8 Byte0, Byte1;
  Byte0 = _ReadU8();
  Byte1 = _ReadU8();
  Value = (Byte1 << 8) | Byte0;
  return Value;
}

/*********************************************************************
*
*       _ReadBytes
*
* Purpose:
*   Reads a string from the given pointer if possible and increments the pointer
*/
static void _ReadBytes(U8 * pBuffer, int Len) {
  if (_Source.RemBytes < 0) {
    return;
  }
  if (_Source.RemBytes < Len) {
    Len = _Source.RemBytes;
    return;
  }
  _Source.RemBytes -= Len;
  memcpy(pBuffer, _Source.pSrc, Len);
  _Source.pSrc += Len;
}

/*********************************************************************
*
*       _SkipBytes
*
* Purpose:
*   Skips the number of given bytes and increments the pointer
*/
static void _SkipBytes(int Len) {
  if (_Source.RemBytes < 0) {
    return;
  }
  if (_Source.RemBytes < Len) {
    Len = _Source.RemBytes;
    return;
  }
  _Source.RemBytes -= Len;
  _Source.pSrc += Len;
}

/*********************************************************************
*
*       _InitLWZ
*
* Purpose:
*   Initializes the given LZW with the input code size
*/
static void _InitLZW(int InputCodeSize) {
  GUI__memset((U8 *)&_LZWContext, 0, sizeof(LZW_CONTEXT));
  _LZWContext.SetCodeSize  = InputCodeSize;
  _LZWContext.CodeSize     = InputCodeSize + 1;
  _LZWContext.ClearCode    = (1 << InputCodeSize);
  _LZWContext.EndCode      = (1 << InputCodeSize) + 1;
  _LZWContext.MaxCode      = (1 << InputCodeSize) + 2;
  _LZWContext.MaxCodeSize  = (1 << InputCodeSize) << 1;
  _LZWContext.ReturnClear  = 1;
  _LZWContext.LastByte     = 2;
  _LZWContext.sp           = _LZWContext.aDecompBuffer;
}

/*********************************************************************
*
*       _GetDataBlock
*
* Purpose:
*   Reads a LZW data block. The first byte contains the length of the block,
*   so the maximum length is 256 byte
*
* Return value:
*   Length of the data block
*/
static int _GetDataBlock(U8 * pBuffer) {
  U8 Count;
  Count = _ReadU8(); /* Read the length of the data block */
  if (Count) {
    if (pBuffer) {
      _ReadBytes(pBuffer, Count);
    } else {
      _Source.pSrc += Count;
    }
  }
  return((int)Count);
}

/*********************************************************************
*
*       _GetNextCode
*
* Purpose:
*   Returns the next LZW code from the LZW stack. One LZW code contains up to 12 bits.
*
* Return value:
*   >= 0 if succeed
*   <  0 if not succeed
*/
static int _GetNextCode(void) {
  int i, j, End;
  long Result;
  if (_LZWContext.ReturnClear) {
    /* The first code should be a clear code. */
    _LZWContext.ReturnClear = 0;
    return _LZWContext.ClearCode;
  }
  End = _LZWContext.CurBit + _LZWContext.CodeSize;
  if (End >= _LZWContext.LastBit) {
    int Count;
    if (_LZWContext.GetDone) {
      return -1; /* Error */
    }
    _LZWContext.aBuffer[0] = _LZWContext.aBuffer[_LZWContext.LastByte - 2];
    _LZWContext.aBuffer[1] = _LZWContext.aBuffer[_LZWContext.LastByte - 1];
    if ((Count = _GetDataBlock(&_LZWContext.aBuffer[2])) == 0) {
      _LZWContext.GetDone = 1;
    }
    if (Count < 0) {
      return -1; /* Error */
    }
    _LZWContext.LastByte = 2 + Count;
    _LZWContext.CurBit   = (_LZWContext.CurBit - _LZWContext.LastBit) + 16;
    _LZWContext.LastBit  = (2 + Count) * 8 ;
    End                  = _LZWContext.CurBit + _LZWContext.CodeSize;
  }
  j = End >> 3;
  i = _LZWContext.CurBit >> 3;
  if (i == j) {
    Result = (long)_LZWContext.aBuffer[i];
  } else if (i + 1 == j) {
    Result = (long)_LZWContext.aBuffer[i] | ((long)_LZWContext.aBuffer[i + 1] << 8);
  }  else {
    Result = (long)_LZWContext.aBuffer[i] | ((long)_LZWContext.aBuffer[i + 1] << 8) | ((long)_LZWContext.aBuffer[i + 2] << 16);
  }
  Result = (Result >> (_LZWContext.CurBit & 0x7)) & _aMaskTbl[_LZWContext.CodeSize];
  _LZWContext.CurBit += _LZWContext.CodeSize;
  return (int)Result;
}

/*********************************************************************
*
*       _GetNextByte
*
* Purpose:
*   Reads the next LZW code from the LZW stack and returns the first byte from the LZW code.
*
* Return value:
*   >= 0 if succeed
*   -1   if not succeed
*   -2   if end code has been read
*/
static int _GetNextByte(void) {
  int i, Code, Incode;
  while ((Code = _GetNextCode()) >= 0) {
    if (Code == _LZWContext.ClearCode) {
      /* Corrupt GIFs can make this happen */
      if (_LZWContext.ClearCode >= (1 << MAX_NUM_LWZ_BITS)) {
        return -1; /* Error */
      }
      /* Clear the tables */
      GUI__memset((U8 *)_LZWContext.aCode, 0, sizeof(_LZWContext.aCode));
      for (i = 0; i < _LZWContext.ClearCode; ++i) {
        _LZWContext.aPrefix[i] = i;
      }
      /* Calculate the 'special codes' in dependence of the initial code size
         and initialize the stack pointer */
      _LZWContext.CodeSize    = _LZWContext.SetCodeSize + 1;
      _LZWContext.MaxCodeSize = _LZWContext.ClearCode << 1;
      _LZWContext.MaxCode     = _LZWContext.ClearCode + 2;
      _LZWContext.sp          = _LZWContext.aDecompBuffer;
      /* Read the first code from the stack after clearing and initializing */
      do {
        _LZWContext.FirstCode = _GetNextCode();
      } while (_LZWContext.FirstCode == _LZWContext.ClearCode);
      _LZWContext.OldCode = _LZWContext.FirstCode;
      return _LZWContext.FirstCode;
    }
    if (Code == _LZWContext.EndCode) {
      return -2; /* End code */
    }
    Incode = Code;
    if (Code >= _LZWContext.MaxCode) {
      *(_LZWContext.sp)++ = _LZWContext.FirstCode;
      Code = _LZWContext.OldCode;
    }
    while (Code >= _LZWContext.ClearCode) {
      *(_LZWContext.sp)++ = _LZWContext.aPrefix[Code];
      if (Code == _LZWContext.aCode[Code]) {
        return Code;
      }
      if ((_LZWContext.sp - _LZWContext.aDecompBuffer) >= sizeof(_LZWContext.aDecompBuffer)) {
        return Code;
      }
      Code = _LZWContext.aCode[Code];
    }
    *(_LZWContext.sp)++ = _LZWContext.FirstCode = _LZWContext.aPrefix[Code];
    if ((Code = _LZWContext.MaxCode) < (1 << MAX_NUM_LWZ_BITS)) {
      _LZWContext.aCode  [Code] = _LZWContext.OldCode;
      _LZWContext.aPrefix[Code] = _LZWContext.FirstCode;
      ++_LZWContext.MaxCode;
      if ((_LZWContext.MaxCode >= _LZWContext.MaxCodeSize) && (_LZWContext.MaxCodeSize < (1 << MAX_NUM_LWZ_BITS))) {
        _LZWContext.MaxCodeSize <<= 1;
        ++_LZWContext.CodeSize;
      }
    }
    _LZWContext.OldCode = Incode;
    if (_LZWContext.sp > _LZWContext.aDecompBuffer) {
      return *--(_LZWContext.sp);