lzw.cpp

经过DCT变换用 LZW进行数据压缩 再还原回来

#include "head.h"
int *code_value;                      /* This is the code value array */
unsigned int *prefix_code;            /* This array holds the prefix codes */
unsigned char *append_character;      /* This array holds the appended chars */
unsigned char decode_stack[4000];     /* This array holds the decoded string */

int num_bits=INIT_BITS;               /* Starting with 9 bit codes */
unsigned long bytes_in=0,bytes_out=0; /* Used to monitor compression ratio */
int max_code;                         /* old MAX_CODE */
unsigned long checkpoint=CHECK_TIME;  /* For compression ratio monitoring */
/////this routine is for lzw encoding
compress(FILE *input, FILE *output)
{
	unsigned int next_code=FIRST_CODE;
	unsigned int character;
	unsigned int string_code;
	unsigned int index;
	int i,            
		ratio_new,         
		ratio_old=100;     
	
	for (i=0;i<TABLE_SIZE;i++)  
		code_value[i]=-1;
	printf("Compressing\n");
	string_code=getc(input);    
	
								 
	while((character=getc(input)) != (unsigned)EOF) {
		if (!(++bytes_in % 1000)) {     
			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);  
			string_code=character;
			if (next_code > max_code) {     
				if ( num_bits < MAX_BITS) {    
					putchar('+');
					max_code = MAXVAL(++num_bits); 
				}
				else if (bytes_in > checkpoint) {         
					if (num_bits == MAX_BITS ) {
						ratio_new = bytes_out*100/bytes_in; 
						if (ratio_new > ratio_old) {        
							output_code(output,CLEAR_TABLE); 
							putchar('C');
							num_bits=INIT_BITS;
							next_code=FIRST_CODE;        
							max_code = MAXVAL(num_bits); 
							bytes_in = bytes_out = 0;
							ratio_old=100;               
							for (i=0;i<TABLE_SIZE;i++)  
								code_value[i]=-1;
						}
						else                               
							ratio_old = ratio_new;           
					}
					checkpoint = bytes_in + CHECK_TIME;   
				}
			}
		}
	}
	output_code(output,string_code);   
	if (next_code == max_code) {       
		++num_bits;                     
		putchar('+');
	}
	output_code(output,TERMINATOR);    
	output_code(output,0);             
	output_code(output,0);
	output_code(output,0);
	putchar('\n');
}

output_code(FILE *output, unsigned int code)
{
	static int output_bit_count=0;
	static unsigned long output_bit_buffer=0L;
	
	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++;                    
	}
}
find_match(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;
	}
}
//////////////This routine for lzw decoding//////////////////
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;          
	unsigned char *string;
	unsigned char *decode_string(unsigned char *buffer, unsigned int code);

	printf("Expanding\n");

	while((new_code=input_code(input)) != TERMINATOR) {
		if (clear_flag) {       
			clear_flag=0;
			old_code=new_code;   
			character=old_code;  
			putc(old_code,output);
			continue;
		}
		if (new_code == CLEAR_TABLE) {    
			clear_flag=1;
			num_bits=INIT_BITS;
			next_code=FIRST_CODE;
			putchar('C');
			max_code = MAXVAL(num_bits);
			continue;
		}
		if (++counter == 1000) {         
			counter=0;
			putchar('.');
		}
		if (new_code >= next_code) {       
			*decode_stack=character;
			string=(unsigned char *)decode_string(decode_stack+1,old_code);
		}
		else
			string=(unsigned char *)decode_string(decode_stack,new_code);

		character = *string;              
		while (string >= decode_stack)
			putc(*string--,output);

		if (next_code <= max_code) {      
			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');
}

unsigned input_code(FILE *input)
{
	unsigned int return_value;
	static int input_bit_count=0;
	static unsigned long input_bit_buffer=0L;

	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);
}

unsigned char *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);
}