/* 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.
 */ 

/* LZW encode (Adobe's version) a buffer
 * MJR 5/01
 *
 * Re-written 7/12 to use a form of tree. Time to compress certain test
 * image on certain machine drops from 13s to 0.5s.
 *
 * 8/12 added buffer length parameter
 *
 * returns length of compressed data, or zero if compression failed
 * (i.e. supplied buffer too small)
 *
 * N.B. the sbits function is also used by the CCITT code
 */

#include <stdio.h>

#ifdef USE_LZW
#define MAXCS 12

void sbits(unsigned char *c,int st, int len, int data);

unsigned int to_lzw(unsigned char *buff, unsigned char *out,
		    unsigned int buff_len, int len){
  short tp;
  short child[1<<MAXCS],sibling[1<<MAXCS];
  unsigned char ch[1<<MAXCS];
  int i,j,tpos,bpos,off,ccs,tmax=(1<<MAXCS)-1,clr,eoi,parent,sib,end;
  unsigned char data;

  /* Init tables */

  for(i=0;i<1<<MAXCS;i++) child[i]=sibling[i]=0;

  clr=256;
  eoi=257;
  tpos=258;

  bpos=0;
  ccs=9;
  end=buff_len*8-24; /* End of buffer in bits, with a space for two codes */

  sbits(out,0,ccs,clr);
  off=ccs;
  data=buff[bpos++];

  while((bpos<=len)&&(off<end)){
    tp=data;
    parent=tp;
    sib=0;
    data=buff[bpos++];

    j=child[tp];
    while((j)&&(bpos<=len)){
      if (ch[j]==data){
	data=buff[bpos++];
        parent=j;
        sib=0;
        tp=j;
	j=child[j];
      }
      else {sib=j;j=sibling[j];}
    }

    ch[tpos]=data;
    if (sib) sibling[sib]=tpos;
    else child[parent]=tpos;
    tpos++;

    /*    printf("LZW code: %d at %d\n",tp,off); */

    sbits(out+(off>>3),off&7,ccs,tp);
    off+=ccs;

    if(tpos==(1<<ccs)) ccs++;

    if (tpos==tmax){
      sbits(out+(off>>3),off&7,ccs,clr);
      off+=ccs;
      ccs=9;
      tpos=258;
      for(i=0;i<1<<MAXCS;i++) child[i]=sibling[i]=0;
    }
  }

  if (off>=end) return 0;

  sbits(out+(off>>3),off&7,ccs,eoi);
  off+=ccs;
  return((off+7)>>3);
}
#endif

/* Sets the next bits of buffer to the data given
 * *c  -  start of buffer
 * st  -  offset in bits from *c at which to start (<8)
 * len -  number of bits to write (<=sizeof(int))
 * data - the bits to write
 */ 
void sbits(unsigned char *c,int st, int len, int data){
  unsigned char tmp;

  if (st==0) tmp=0;
  else tmp=*c;

  if ((len+st-8)>0)
    tmp|=(data>>(len+st-8));
  else
    tmp|=(data<<(8-st-len));
  *c=tmp;
  len=len-8+st;
  while (len>0){
    data&=((1<<len)-1);
    c++;
    len-=8;
    if (len>0)
      *c=(data>>len);
    else
      *c=(data<<(-len));
  }
}