//LZW constant size dictionary
// based on M. Nelson, The Data Compression Book, M&T Books, 1991
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "bitio.h"


#define BITS 		12
#define MAX_CODE	((1<<BITS)-1)
#define TABLE_SIZE	5021
#define END_OF_STREAM	256
#define FIRST_CODE	257
#define UNUSED	-1

unsigned int find_child_node(int parent_code,int child_character);
unsigned int decode_string(unsigned int offset,unsigned int code);

char *CompressionName = "LZW 12 Bit Encoder";
char *Usage	      = "in_file out_file\n\n";

struct dictionary {
 int code_value;
 int parent_code;
 char character;
 } dict[TABLE_SIZE];

char decode_stack[TABLE_SIZE];

void CompressFile(FILE *input,BIT_FILE *output,int argc,char *argv[])
{
 int next_code,character,string_code;
 unsigned int index,i;

 next_code = FIRST_CODE;
 for(i=0;i<TABLE_SIZE;i++)
  dict[i].code_value=UNUSED;
 if((string_code=getc(input))==EOF)
  string_code=END_OF_STREAM;
 while((character=getc(input))!=EOF) {
  index=find_child_node(string_code,character);
  if(dict[index].code_value != -1)
   string_code=dict[index].code_value;
  else {
    if(next_code <= MAX_CODE) {
     dict[index].code_value = next_code++;
     dict[index].parent_code = string_code;
     dict[index].character = (char)character;
    }
    OutputBits(output,(unsigned long)string_code,BITS);
    string_code = character;
   }
  }
 OutputBits(output,(unsigned long)string_code,BITS);
 OutputBits(output,(unsigned long)END_OF_STREAM,BITS);
 while(argc-- > 0)
  printf("Unknown argument: %s\n",*argv++);
}

void ExpandFile(BIT_FILE *input,FILE *output,int argc,char *argv[])
{
 unsigned int next_code,new_code,old_code;
 int character;
 unsigned int count ;

 next_code = FIRST_CODE;
 old_code=(unsigned int)InputBits(input,BITS);
 if(old_code==END_OF_STREAM)
  return;
 character=old_code;
 putc(old_code,output);
 while((new_code=(unsigned int)InputBits(input,BITS))!=END_OF_STREAM) {
  if(new_code >= next_code) {
   decode_stack[0]=(char)character;
   count=decode_string(1,old_code);
  } else
   count=decode_string(0,new_code);
  character=decode_stack[count-1];
  while(count>0)
   putc(decode_stack[--count],output);
  if(next_code <= MAX_CODE) {
   dict[next_code].parent_code = old_code;
   dict[next_code].character=(char)character;
   next_code++;
  }
  old_code=new_code;
 }
 while(argc-->0)
  printf("Unknown argument: %s\n",*argv++);
}

unsigned int find_child_node(int parent_code,int child_character)
{
 int index;
 int offset;

 index=(child_character << (BITS - 8)) ^ parent_code;
 if(index==0)
  offset=1;
 else
  offset=TABLE_SIZE-index;
 for(;;) {
  if(dict[index].code_value==UNUSED)
   return(index);
  if((dict[index].parent_code==parent_code) && (dict[index].character==(char)child_character))
   return(index);
  index-=offset;
  if(index<0)
   index+=TABLE_SIZE;
 }
}

unsigned int decode_string(unsigned int count,unsigned int code)
{
 while(code>255) {
  decode_stack[count++]=dict[code].character;
  code=dict[code].parent_code;
  }
 decode_stack[count++]=(char)code;
 return(count);
}