/* a GIF LZW Decoder */

/*
 * Copyright (C) 1995 by Sam Rushing <rushing@nightmare.com>
 * 
 * The Graphics Interchange Format(c) is the Copyright property of
 * CompuServe Incorporated.  GIF(sm) is a Service Mark property of
 * CompuServe Incorporated.
 *
 * Although I stared at several other gif decoders,
 * most seemed to have compress.c as an ancestor - which
 * used a lot of static variables, so you couldn't do
 * concurrent decompressions.
 * 
 * I've learned in the course of writing this that there
 * _is no_ elegant implementation.  The simple beauty of
 * the LZW algorithm evaporated into a cloud of special
 * cases, and in the end my code looked just like everyone
 * else's.
 *
 * Thanks to Dave Koblas (xpaint) and Patrick J. Naughton
 * (giftopnm) for making their code available for
 * instrumentation.
 *
 * This should probably be made into a separate C library
 * so that we python weenies don't hog it up.
 *
 * TODO: generalize the input and output so you don't have
 * to use huge strings if you don't want to.
 *
 * ********************
 * Note: Unisys owns a patent <ick> on the LZW algorithm used
 * by GIF.  Check it out before you do Something Important with
 * this.
 * ********************
 *
 */

#include "allobjects.h"

#define SAFE_FREE(thing) do { if ((thing)) {free ((thing));}} while (0)

#ifdef DEBUG_GIFLZW
#define DEBUG_FPRINTF(args) do { fprintf args; } while (0)
#else
#define DEBUG_FPRINTF(args)
#endif

static object *ErrorObject;

static unsigned int bit_slice_table[8][9];

static void
fill_bit_slice_table (void)
{
  int i;
  int j;

  for (i=0; i < 8; i++) {
    for(j=0; j < 9; j++) {
      if (j < (9 - i)) {
	bit_slice_table[i][j] = (((1 << j) - 1) << i);
      } else {
	bit_slice_table[i][j] = 0;
      }
    }
  }
}

typedef struct {
  unsigned char *	data_table;
  unsigned int *	prefix_table;
  unsigned char *	data_stack;
  size_t		stack_index;
  unsigned char *	input;
  size_t		input_length;
  unsigned char		bit_pos;
  unsigned int		byte_pos;
  unsigned char		first_of_last;
  unsigned int		initial_code_size;
} gif_lzw_decoder;

typedef struct {
  PyObject *		string_object;
  unsigned char *	data;
  unsigned char *	row;
  int			pass;
  int			xpos;
  int			ypos;
  int			width;
  int			height;
  int			interlaced;
  size_t		count;
} gif_output;


static
gif_output *
new_output (int width, int height, int interlaced)
{
  gif_output * go;

  go = (gif_output *) malloc (sizeof(gif_output));
  go->width = width;
  go->height = height;
  go->interlaced = interlaced;
  go->xpos = go->ypos = go->count = go->pass = 0;

  go->string_object = PyString_FromStringAndSize (NULL, width * height);
  if (!(go->string_object)) {
    free (go);
    return NULL;
  }
  go->data = (unsigned char *) PyString_AsString (go->string_object);
  go->row = go->data;
  return (go);
}

static
void
free_output (gif_output * go)
{
  Py_DECREF (go->string_object);
  free (go);
}

/*
 * return the bitfield of length <code_size> at position <bit_pos>
 * in byte <byte_pos>, using bit_slice_table.  Modifies <byte_pos>
 * and <bit_pos> to point to the next bitfield.
 */

static int
get_code (gif_lzw_decoder * gld,
	  int code_size)
{
  int result=0;
  int left=code_size;
  int slice_len;
  int slice;

  while (left > 0) {
    slice_len = (left < (8 - gld->bit_pos) ? left : (8 - gld->bit_pos));
    slice = ((((unsigned char)(gld->input[gld->byte_pos]))
	      & bit_slice_table[gld->bit_pos][slice_len])
	     >> gld->bit_pos) << (code_size - left);
    result = result | slice;
    left = left - slice_len;
    gld->bit_pos = (gld->bit_pos + slice_len) % 8;
    if (gld->bit_pos == 0) {
      (gld->byte_pos)++;
    }
  }
  return result;
}

#define GIF_MAXBITS 12

static void
reset_decoder (gif_lzw_decoder * gld)
{
  int i;
  for (i=0; i < (1<<GIF_MAXBITS); i++) {
    /* fill the data table */
    if (i < (1<<(gld->initial_code_size))) {
      gld->data_table[i] = (unsigned char)i;
    } else {
      gld->data_table[i] = 0;
    }
    /* fill the prefix table */
    gld->prefix_table[i] = 0;
  }
}    

static int
initialize_decoder (gif_lzw_decoder * gld,
		    unsigned int code_size)
{
  gld->bit_pos = 0;
  gld->byte_pos = 0;
  gld->stack_index = 0;
  gld->data_table = (unsigned char *) malloc (sizeof(unsigned char) * (1<<GIF_MAXBITS));
  if (!(gld->data_table)) {
    return 0;
  } else {
    gld->prefix_table = (unsigned int *) malloc (sizeof(unsigned int) * (1<<GIF_MAXBITS));
    if (!(gld->prefix_table)) {
      free (gld->data_table);
      return 0;
    } else {
      gld->data_stack = (unsigned char *) malloc (sizeof(unsigned char) * (1<<GIF_MAXBITS));
      reset_decoder (gld);
      return 1;
    }
  }
}

static void
free_decoder (gif_lzw_decoder * gld)
{
  SAFE_FREE (gld->data_table);
  SAFE_FREE (gld->prefix_table);
  SAFE_FREE (gld->data_stack);
  free (gld);
}

/* maybe: reverse stack and write codes out atomically */

static void
output_code (gif_lzw_decoder * gld,
	     gif_output * go,
	     unsigned int code)
{
  /*
   * code strings are built in reverse, so as we
   * travel the prefix table, we push each byte onto
   * a stack
   */
   
  while (1) {
    gld->data_stack[(gld->stack_index)++] = gld->data_table[code];
    if (gld->prefix_table[code] != 0) {
      code = gld->prefix_table[code] - 1;
    } else {
      gld->first_of_last = code;
      break;
    }
  }
    
  /*
   * now we reconstruct the string by popping it all
   * off the stack
   */
  
  while (gld->stack_index) {
    gld->stack_index--;
    go->row[go->xpos] = gld->data_stack[gld->stack_index];
    (go->count)++;
    DEBUG_FPRINTF ((stderr, "%d ", (int) go->row[go->xpos]));
    (go->xpos)++;
    if ((go->xpos) == (go->width)) {
      (go->xpos) = 0;
      /* handle interlaced data */
      if (go->interlaced) {
	do  {
	  switch ((go->pass)) {
	  case 0:
	  case 1:
	    (go->ypos) += 8;
	    if (go->ypos >= go->height) { (go->pass)++; go->ypos = 4; }
	    break;
	  case 2:
	    (go->ypos) += 4;
	    if (go->ypos >= go->height) { (go->pass)++; go->ypos = 2; }
	    break;
	  case 3:
	    (go->ypos) += 2;
	    if (go->ypos >= go->height) { (go->pass)++; go->ypos = 1; }
	    break;	    
	  }
	  /* this extra check is necessary for images of only a few lines */
	} while (((go->ypos) >= go->height) && (go->pass < 5));
      } else {
	(go->ypos)++;
      }
      (go->row) = go->data + (go->ypos * go->width);      
    }
  }
}

static PyObject *
py_giflzw_decode (PyObject * self, PyObject * args)
{
  gif_lzw_decoder	* gld;
  gif_output	* go;
  int		code_size;
  unsigned int	clear_code, orig_code, code, last_code, next_code, max_code;
  unsigned int	width, height, interlaced;
  PyObject *	result;

  /* try to allocate a new decoder */
  gld = (gif_lzw_decoder *) malloc (sizeof(gif_lzw_decoder));
  
  if (!gld) {
    PyErr_SetString (PyExc_MemoryError, "couldn't allocate decoder");
    return NULL;
  }

  /* parse the args */
  if (!PyArg_ParseTuple (args, "s#iiii",
			 &(gld->input),
			 &(gld->input_length),
			 &(gld->initial_code_size),
			 &width,
			 &height,
			 &interlaced)) {
    return NULL;
  }
  
  /* try to allocate the output string */
  go = new_output (width, height, interlaced);

  if (!go) {
    free_decoder (gld);
    PyErr_SetString (PyExc_MemoryError, "couldn't allocate output string");
    return NULL;
  }

  /* try to initialize the decoder */
  if (!initialize_decoder (gld, gld->initial_code_size)) {
    free_decoder (gld);
    free_output (go);
    PyErr_SetString (PyExc_MemoryError, "couldn't allocate decoder tables");
    return NULL;
  }

  code_size = gld->initial_code_size;
  clear_code = 1<<code_size;
  next_code = clear_code + 2;
  max_code = (1<<(code_size+1)) - 1;
  
#define BARF_RETURN(message)				\
  do { free_decoder (gld);				\
       free_output (go);				\
       PyErr_SetString (PyExc_ValueError, (message));	\
       return NULL;					\
     }							\
    while (0)

  /* read the clear code */
  code = get_code (gld, code_size+1);
  
  DEBUG_FPRINTF ((stderr, "clear code %d\n", code));
  if (code != clear_code) {
    BARF_RETURN ("invalid GIF LZW data stream (didn't start with clear code)");
  }
  
  /* read the first code */
  last_code = get_code (gld, code_size+1);
  /* output the code */
  output_code (gld, go, last_code);

  while (1) {

    if (gld->byte_pos >= gld->input_length) {
      BARF_RETURN ("read past data with seeing end code");
    }

    code = orig_code = get_code (gld, code_size+1);

    DEBUG_FPRINTF ((stderr, "\ncode: %d\n", code));

    if (code == clear_code) {
      DEBUG_FPRINTF ((stderr, "***** clear code found *****\n"));
      code_size = gld->initial_code_size;
      clear_code = 1 << code_size;
      next_code = clear_code + 2;
      max_code = (1<<(code_size+1)) -1;
      reset_decoder (gld);
      code = last_code = get_code (gld, code_size+1);
      output_code (gld, go, code);
      continue;
    } else if (code == clear_code + 1) {
      DEBUG_FPRINTF ((stderr, "***** end code found *****\n"));
      DEBUG_FPRINTF ((stderr, "%ld bytes written\n", (long) gld->byte_pos));
      break;
    } else if (code == next_code) {
      /* special case for KwKwK */
      output_code (gld, go, gld->first_of_last);
      code = last_code;
    }
      
    output_code (gld, go, code);

    if (next_code != (1<<GIF_MAXBITS) - 1) {
      /* add a new code to the chain */

      gld->prefix_table[next_code] = last_code + 1;
      gld->data_table[next_code] = gld->first_of_last;
      next_code = next_code + 1;

      if (next_code > max_code) {
	code_size = code_size + 1;
	max_code = (1<<(code_size+1)) - 1;
      }
    }
    last_code = orig_code;
  }

  if (go->count != width*height) {
    BARF_RETURN ("not enough decoder output, premature end code found");
  } else {
    free_decoder (gld);
    result = go->string_object;
    Py_INCREF (result);
    free_output (go);
  }
  return (result);
}
  
/* List of functions exported by this module */
static struct PyMethodDef giflzw_functions[] = {
  {"decode",	py_giflzw_decode,	1},
  {NULL, NULL}			/* Sentinel */
};

/* Initialization function for the module (*must* be called initgiflzw) */

void
initgiflzw()
{
  PyObject *m, *d;

  /* Create the module and add the functions */
  m = Py_InitModule("giflzw", giflzw_functions);

  /* Add some symbolic constants to the module */
  d = PyModule_GetDict(m);
  ErrorObject = PyString_FromString("giflzw error");
  PyDict_SetItemString(d, "error", ErrorObject);

  fill_bit_slice_table();

  /* Check for errors */
  if (PyErr_Occurred())
    Py_FatalError("can't initialize module giflzw");
}