/* Copyright (c) 2010 MJ Rutter 
 * 
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License version 2
 * as published by the Free Software Foundation.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin Street,
 * Fifth Floor, Boston, MA  02110-1301, USA.
 */ 

/* de LZW encode (GIF's version) a buffer
 * MJR 4/01
 */

#include <stdio.h>
#include <stdlib.h>

#define MAXCS 12

unsigned int de_lzw(unsigned char *comp, unsigned char *out, unsigned int len,
		    int cs);
static unsigned bits(unsigned char *c,int st, int len);

unsigned int de_lzw(unsigned char *buff, unsigned char *out, unsigned int len,
		    int cs){
  unsigned char store[256], *start, *end;
  unsigned int off,tpos,eoi,clr;
  struct str {unsigned char *s; unsigned len;} table[1<<MAXCS];
  int tmax=(1<<MAXCS)-1,ccs,i,j;

  start=out;
  end=out+len;

  if (cs>MAXCS){
    fprintf(stderr,"de_lzw: initial token size of %d too large\n",cs);
    exit(1);
  }

  /* Init table */

  off=0;
  ccs=cs;
  clr=(1<<(cs-1));
  eoi=clr+1;
  tpos=clr+2;

  for(i=0;i<clr;i++){
    table[i].len=1;
    table[i].s=store+i;
    store[i]=(unsigned char)i;
  }

  i=bits(buff,0,ccs);
  if (i!=clr){
    fprintf(stderr,"de_lzw: ClearCode not first code, but %x is\n",i);
    exit(1);
  }

  while(1){
    i=bits(buff+(off>>3),off&7,ccs);
    off+=ccs;

    if(i==clr){
      ccs=cs;
      tpos=clr+2;
      continue;
    }

    if(i==eoi){
      /* fprintf(stderr,"EOI\n"); */
      return(out-start);
    }

    if(i>=tpos){
      fprintf(stderr,"de_lzw: token erroneously large.\n");
      exit(1);
    }

    if (out>end){
      fprintf(stderr,"de_lzw: output buffer full -- aborting.\n");
      exit(1);
    }

    if (tpos<=tmax){
      table[tpos].len=table[i].len+1;
      table[tpos].s=out;
      tpos++;
    }

    for(j=0;(j<table[i].len)&&(out<=end);j++) *(out++)=*(table[i].s+j);

    if ((tpos==(1<<ccs)+1)&&(ccs<MAXCS)) ccs++;
  }
  /* Never reached */
  return(out-start);
}

static unsigned bits(unsigned char *c,int st, int len){
  unsigned tmp,mask;

  tmp=((unsigned)(*(c+2))<<16)+((unsigned)(*(c+1))<<8)+*(c);
  mask=((1<<len)-1)<<st;
  tmp&=mask;
  return(tmp>>st);
}