lzw.cpp

采用C++编写的已经封装好的lzw压缩算法

// LZW.cpp: implementation of the CLZW class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "LZW.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

void CLZW::InitGlobalVar()
{
	num_bits = INIT_BITS;
	bytes_in = 0;
	bytes_out = 0;
	checkpoint = CHECK_TIME;
	max_code = MAXVAL(num_bits);
}

CLZW::CLZW()
{
	InitGlobalVar();
	code_value = NULL;
	prefix_code = NULL;
	append_character = NULL;
	code_value=(int *)malloc(TABLE_SIZE*sizeof(unsigned int));
	prefix_code=(unsigned int *)malloc(TABLE_SIZE*sizeof(unsigned int));
	append_character=(unsigned char *)malloc(TABLE_SIZE*sizeof(unsigned char));
}

CLZW::~CLZW()
{
	if(code_value)
		free(code_value);
	if(prefix_code)
		free(prefix_code);
	if(append_character)
		free(append_character);
}

/* UNCHANGED from original
 * This is the hashing routine.
 */
unsigned int CLZW::find_match(unsigned int hash_prefix, unsigned int hash_character)
{
	int index, offset;

	index = (hash_character << HASHING_SHIFT ) ^ hash_prefix;
	if (index == 0 )
		offset=1;
	else
		offset = TABLE_SIZE - index;
	while(1)
	{
		if(code_value[index] == -1)
			return(index);
		if(	prefix_code[index] == hash_prefix && 
			append_character[index] == hash_character)
			return(index);
		index -= offset;
		if (index < 0)
			index += TABLE_SIZE;
	}
}
/* UNCHANGED from original
 * Decode a string from the string table, storing it in a buffer.
 * The buffer can then be output in reverse order by the expansion
 * program.
 */
unsigned char *CLZW::decode_string(unsigned char *buffer, unsigned int code)
{
	int i=0;

	while(code > 255 )
	{
		*buffer++ = append_character[code];
		code=prefix_code[code];
		if (i++ >= 4000 )
		{
//			printf("Error during code expansion\n");
			exit(1);
		}
	}
	*buffer=code;
	return(buffer);
}

/* UNCHANGED from original
 * Input a variable length code.
 */
unsigned int CLZW::input_code(FILE *input)
{
	unsigned int return_value;

	while (input_bit_count <= 24 ) {
		input_bit_buffer |= (unsigned long) getc(input) << (24 - input_bit_count);
		input_bit_count += 8;
	}
	return_value=input_bit_buffer >> (32-num_bits);
	input_bit_buffer <<= num_bits;
	input_bit_count -= num_bits;
	return(return_value);
}
/* MODIFIED Output a variable length code.
 */
void CLZW::output_code(FILE *output, unsigned int code)
{

   output_bit_buffer |= (unsigned long) code << (32 - num_bits - 
                                                             output_bit_count);
   output_bit_count += num_bits;
   while (output_bit_count >= 8) {
      putc(output_bit_buffer >> 24, output);
      output_bit_buffer <<= 8;
      output_bit_count -= 8;
      bytes_out++;                    /* ADDED for compression monitoring */
   }
}

bool CLZW::compress(const char *input, const char *output)
{
	if(input && output)
	{
		FILE *input_file, *output_file;
		input_file = fopen(input, "rb");
		output_file = fopen(output, "wb");
		if(input_file == NULL || output_file == NULL)
			return false;
		InitGlobalVar();
		output_bit_count = 0;
		output_bit_buffer = 0L;

		compress(input_file, output_file);

		fclose(input_file);
		fclose(output_file);
		return true;
	}
	return false;
}

bool CLZW::expand(const char *input, const char *output)
{
	if(input && output)
	{
		FILE *input_file, *output_file;
		input_file = fopen(input, "rb");
		output_file = fopen(output, "wb");
		if(input_file == NULL || output_file == NULL)
			return false;

		InitGlobalVar();
		input_bit_count = 0;
		input_bit_buffer = 0L;

		expand(input_file, output_file);

		fclose(input_file);
		fclose(output_file);
		return true;
	}
	return false;
}

/* MODIFIED This is the new compression routine. The first two 9-bit codes 
 * have been reserved for communication between the compressor and expander.
 */
void CLZW::compress(FILE *input, FILE *output)
{
   unsigned int next_code=FIRST_CODE;
   unsigned int character;
   unsigned int string_code;
   unsigned int index;
   int i,             /* All purpose integer */
   ratio_new,         /* New compression ratio as a percentage */
   ratio_old=100;     /* Original ratio at 100% */

   for (i=0;i<TABLE_SIZE;i++)   /* Initialize the string table first */
      code_value[i]=-1;
   printf("Compressing\n");
   string_code=getc(input);     /* Get the first code */

 /* This is the main compression loop. Notice when the table is full we try
  * to increment the code size. Only when num_bits == MAX_BITS and the code
  * value table is full do we start to monitor the compression ratio.
  */
   while((character=getc(input)) != (unsigned)EOF) {
      if (!(++bytes_in % 1000)) {     /* Count input bytes and pacifier */
         putchar('.');
      }
      index=find_match(string_code,character);
      if (code_value[index] != -1)
         string_code=code_value[index];
      else {
         if (next_code <= max_code ) {
            code_value[index]=next_code++;
            prefix_code[index]=string_code;
            append_character[index]=character;
         }
         output_code(output,string_code);   /* Send out current code */
         string_code=character;
         if (next_code > max_code) {      /* Is table Full? */
            if ( num_bits < MAX_BITS) {     /* Any more bits? */
               putchar('+');
               max_code = MAXVAL(++num_bits);  /* Increment code size then */
            }
            else if (bytes_in > checkpoint) {         /* At checkpoint? */
               if (num_bits == MAX_BITS ) {
                ratio_new = bytes_out*100/bytes_in; /* New compression ratio */
                if (ratio_new > ratio_old) {        /* Has ratio degraded? */
                  output_code(output,CLEAR_TABLE); /* YES,flush string table */
                  putchar('C');
                  num_bits=INIT_BITS;
                  next_code=FIRST_CODE;        /* Reset to FIRST_CODE */
                  max_code = MAXVAL(num_bits); /* Re-Initialize this stuff */
                  bytes_in = bytes_out = 0;
                  ratio_old=100;               /* Reset compression ratio */
                  for (i=0;i<TABLE_SIZE;i++)   /* Reset code value array */
                        code_value[i]=-1;
               }
               else                                /* NO, then save new */
               ratio_old = ratio_new;            /* compression ratio */
            }
            checkpoint = bytes_in + CHECK_TIME;    /* Set new checkpoint */
            }
         }
      }
   }
   output_code(output,string_code);   /* Output the last code */
   if (next_code == max_code) {       /* Handles special case for bit */
      ++num_bits;                     /* increment on EOF */
      putchar('+');
   }
   output_code(output,TERMINATOR);    /* Output the end of buffer code */
   output_code(output,0);             /* Flush the output buffer */
   output_code(output,0);
   output_code(output,0);
   putchar('\n');
}
/* MODIFIED This is the modified expansion routine. It must now check for the
 * CLEAR_TABLE code and know when to increment the code size.
 */
void CLZW::expand(FILE *input, FILE *output)
{
   unsigned int next_code=FIRST_CODE;
   unsigned int new_code;
   unsigned int old_code;
   int character,
   counter=0,
   clear_flag=1;          /* Need to clear the code value array */
   unsigned char *string;

   printf("Expanding\n");

   while((new_code=input_code(input)) != TERMINATOR) {
      if (clear_flag) {       /* Initialize or Re-Initialize */
         clear_flag=0;
         old_code=new_code;   /* The next three lines have been moved */
         character=old_code;  /* from the original */
         putc(old_code,output);
         continue;
      }
      if (new_code == CLEAR_TABLE) {     /* Clear string table */
         clear_flag=1;
         num_bits=INIT_BITS;
         next_code=FIRST_CODE;
         putchar('C');
         max_code = MAXVAL(num_bits);
         continue;
      }
      if (++counter == 1000) {           /* Pacifier */
         counter=0;
         putchar('.');
      }
      if (new_code >= next_code) {       /* Check for string+char+string */
         *decode_stack=character;
         string=decode_string(decode_stack+1,old_code);
      }
      else
         string=decode_string(decode_stack,new_code);

      character = *string;              /* Output decoded string in reverse */
      while (string >= decode_stack)
         putc(*string--,output);

      if (next_code <= max_code) {      /* Add to string table if not full */
         prefix_code[next_code]=old_code;
         append_character[next_code++]=character;
         if (next_code == max_code && num_bits < MAX_BITS) {
			putchar('+');
            max_code = MAXVAL(++num_bits);
         }
      }
      old_code=new_code;
   }
	putchar('\n');
}