/*The LZW Lib, Included as a part of the compression tutorial
 *Written By Martin Zolnieryk 
 *
 *Thanks Goes to Mark Nelson and ever other person whos tutorials
 *aided in the writing of this.
 *
 *This code is freeware, however if you use this some credit
 *be nice.
*/
#include <stdio.h>
#include <string.h>
#include "allegro.h"
#include "lzw.h"


//Creates the table
int create_lzw_table (LZW *table, int bits)
{
table->prefix = malloc(sizeof(unsigned short int) * (1<<(bits)));
table->character = malloc(sizeof(short int) * (1<<(bits)));
table->lzw_size = (1<<(bits))-1; //One less, becuase of 0 :)
table->codes_used = 0;
table->codes_reserved = 255;
table->buffer = 0;
table->buffer_bits = 0;
table->bits = bits;
table->buffer_size = 0; //tells how big buffer chunks are
table->to_nbuffer = 0;
table->string = malloc(sizeof(unsigned char) * (1<<bits));
clear_lzw_table (table);
return 0;
}

//This is a little handy tool that returns the string
//Corrosponding to the appropriate string ID.
//Returns the size of the string
int lzw_get_string( LZW *table,int code_number)
{
int looper= 0;
 while(code_number > table->codes_reserved)
 { 
  table->string[looper] = table->character[code_number];
  code_number = table->prefix[code_number];
  looper++; 
 }
 table->string[looper] = code_number;
 looper++;
 table->string[looper] = '\0'; //End of string
 return looper;
}


//Free's the table
int delete_lzw_table (LZW *table)
{
//Error Checking
if(!table)
 return 1; //Error
//Free memory
if(table->prefix)
    free(table->prefix);
if(table->character)
    free(table->character);
if(table->string)
    free(table->string);
//Clear pointers
table->string = NULL;
table->prefix = NULL;
table->character = NULL;
//Set Defaults
table->codes_used = 0;
table->codes_reserved = 255; //255 by default
return 0;
}

//Clears the table's values
//Used mainly for gif clearing
int clear_lzw_table(LZW *table)
{
int looper;
//Some Error Checking
if(!table)
 return 1;
if(!table->prefix || !table->character)
 return 1;
//Clear Table
for(looper = 0; looper < table->lzw_size+1; looper++)
{
    table->prefix[looper] = 0; 
    table->character[looper] = -1; //Would use 0, but NULL uses it
    table->string[looper] = 0;
}
return 0;
}

//Completely Clears the table
//This is the proper use, above is used mainly for gifs, to reset the
//values at clear code
int clear_lzw_tablef(LZW *table,int bits)
{
int looper;
//Some Error Checking
if(!table)
 return 1;
if(!table->prefix || !table->character)
 return 1;
//Clear Table
for(looper = 0; looper < table->lzw_size+1; looper++)
{
    table->prefix[looper] = 0; 
    table->character[looper] = -1; //Would use 0, but NULL uses it
    table->string[looper] = 0;
}
table->codes_used = 0;
table->codes_reserved = 255;
table->buffer = 0;
table->buffer_bits = 0;
table->bits = bits;
table->buffer_size = 0; //tells how big buffer chunks are
table->to_nbuffer = 0;

return 0;
}

//This formula is really easy to understand
//Simply Does a brute-force search throught the entire table
//However, it is optimized not to look at lower code values then itself
int lzw_find_code(LZW *table, int string_buffer, int character)
{
int looper;
int counter = 0;
looper = string_buffer; //A code after string buffer cant be below
//The Search
for(looper; looper <= table->codes_used+table->codes_reserved;looper++)
 {
  //If we find a match
  if(string_buffer == table->prefix[looper] && character == table->character[looper])
    return looper;
 }
//If not we return the next available code 
return table->codes_used + 1 +table->codes_reserved;
}

//Compress a file with LZW encoding,
//This is a nice little example of how it can be used
int lzw_compress_file(LZW *table,const char *in, const char *out)
{
FILE *file_in, *file_out;
char written = 0;
short int next_char;      //Check psuedo code, grabs next char
short int string_buffer;  //Check the psuedo code, hold string info
short int code_number;    //Holds code value for STRING_BUFFER

file_in = fopen(in,"rb"); //We open files and make sure they opened correctly
if(file_in == NULL)
 return -1;
file_out = fopen(out,"wb");
if(file_out ==NULL)
 return -1;

clear_lzw_tablef(table,table->bits);
string_buffer=fgetc(file_in);  //Get the first code
while(!feof(file_in)) //End when the file is finished
  {
    next_char = fgetc(file_in); //get next code
    code_number = lzw_find_code(table,string_buffer,next_char); //look for entry
    if (table->character[code_number] != -1)  //If its in the table
	{
        string_buffer= code_number;     
		written = 0;
	}
    else   //If its not in the table
    {                                      
        //We can only add new entries if the table is not full  
        if (table->codes_used+ table->codes_reserved < table->lzw_size-1)
        {
          table->prefix[code_number]= string_buffer;
          table->character[code_number]=next_char;
          table->codes_used++;
        }

        //We write the code
        written = 1;
		lzw_write_code(table,file_out,string_buffer);
        //Start again
        string_buffer=next_char;     
    }                                
  }                                  
//This is our little way of saying the file is finished, this code number
//is not used
if(!written)
lzw_write_code(table,file_out,string_buffer); //In case last byte was not written
lzw_write_code(table,file_out,table->lzw_size); //ENDOFFILE
//Will flush the buffer if any codes need to be flushed
lzw_flush_write_code(table, file_out);
fclose(file_in);
fclose(file_out);
return 0;
}


//Does the oposite of the routine above
int lzw_decompress_file(LZW *table,const char *in, const char *out)
{
FILE *file_in, *file_out;
short int looper;
short int first_code = -1;      //Check psuedo code, is the previous code
unsigned short int next_code;  //Name is self explanatory   
unsigned char first_char;      //Is used if the code is not in the table

file_in = fopen(in,"rb"); //We open files and make sure they opened correctly
if(file_in == NULL)
 return -1;
file_out = fopen(out,"wb");
if(file_out ==NULL)
 return -1;
clear_lzw_tablef(table,table->bits);
//Do the initialization
first_code = lzw_get_code(table,file_in);
first_char = first_code;         
fputc(first_code,file_out);  


//We start the main loop
while((next_code = lzw_get_code(table,file_in))!= table->lzw_size)
  {

   //This is some error checking, basically
   //If a the buffer is empty, and the file is finshed, exit!
   if(feof(file_in))
   {
     if(!table->buffer_bits)
      break;
   }  

    //If not in table
    if (next_code > table->codes_used + table->codes_reserved)          
    {
      table->codes_used++;
      table->prefix[next_code]= first_code;
      table->character[next_code]=first_char;
      looper = lzw_get_string(table,next_code);
    }
    //If the code was already in the table
    //See if we can add a new code to the table
    //Make sure we have not gone over the table size
    else if(table->codes_used + table->codes_reserved < table->lzw_size )                                   
    {                                       
        looper = lzw_get_string(table,next_code);
        table->codes_used++;
        table->prefix[table->codes_used +table->codes_reserved]= first_code;
        table->character[table->codes_used +table->codes_reserved]=table->string[looper-1];
    }
    else //Normal 0-255 ascii char
      looper = lzw_get_string(table,next_code);


    //We write out the decompressed code to the file
    first_char = table->string[looper-1];    
    first_code = next_code;
    while(looper > 0)
     {
 
      fputc(table->string[looper-1],file_out);
      looper--;
     }
 
  } 
fclose(file_in);
fclose(file_out);
 return 0;
}

//This writes a code to a file, really cool stuff.
//We support a max of 16 bit compression
int lzw_write_code(LZW *table,FILE *fp, unsigned int code)
{
//Some bit manipulation
table->buffer |= code << (sizeof(int)*8 - table->bits - table->buffer_bits);
table->buffer_bits+=table->bits;
while(table->buffer_bits >=8)//Never go less than 8 or we loose data
 {
  fputc((table->buffer >> ((sizeof(int) - sizeof(char))*8)),fp);
  table->buffer <<=8; //Remove the char from the buffer
  table->buffer_bits-= 8; //Buffer now stores one less char.
 }
return 0;
}

//Flushes if anything left
int lzw_flush_write_code(LZW *table,FILE *fp)
{
if(table->buffer_bits > 0)
 lzw_write_code(table,fp, 0);
return 0;
}
//This gets a gif code from the file
//this time, we work backwards
int lzw_get_code(LZW*table,FILE *fp)
{
int temp;
while(table->buffer_bits <=((sizeof(int)-sizeof(char))*8))//Never go over than size - or we loose data
 {
//No point reading anymore, files done :p
if(feof(fp))
      break;
   table->buffer |= (unsigned char)getc(fp) <<((sizeof(int)-sizeof(char))*8 - table->buffer_bits);
   table->buffer_bits+= 8; //Buffer now stores one less char.
 }
temp = table->buffer >>(sizeof(int)*8 -table->bits);
table->buffer <<= table->bits;
table->buffer_bits -= table->bits;
return temp;
}