lzw15.c

站长96年写的一个Internet上用的股票行情、分析、交易、资讯程序源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

#include "lzw.h"

#define         BITS            15
#define         MAX_CODE        ((1L<<BITS) -1 )        //32767
#define         TABLE_SIZE      35023L                  //137*256=35072
#define         TABLE_BANKS     ((TABLE_SIZE >> 8) +1)  //137
#define         END_OF_STREAM   256
#define         BUMP_CODE       257
#define         FLUSH_CODE      258
#define         FIRST_CODE      259
#define         UNUSED          -1

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

void  InitializeStorage(void);
void  InitializeDictionary(void);
void  ExitLzw(void);

//char *CompressionName ="lzw 15 bit Encode";
//char *Usage         ="in-file out-file\n\n";
//this package inlude file:bitio.c/lzw15.c/lzw.h

typedef struct tag_dictionary
{
	int code_value;
	int parent_code;
	char character;
}dictionary;

dictionary *dict[TABLE_BANKS];

#define DICT(i) dict[i >> 8][i&0xff]
//char decode_stack[TABLE_SIZE];
char *decode_stack=NULL;

unsigned int next_code;
int current_code_bits;
unsigned int next_bump_code;

void ExitLzw()
{
	int i;
	for(i=0;i<TABLE_BANKS;i++)
		_ffree(dict[i]);
}

void InitializeDictionary()
{
	unsigned int i;

	for(i=0;i<TABLE_SIZE;i++)
		DICT(i).code_value = UNUSED;
	next_code =FIRST_CODE;
	//putc('F',stdout);
	current_code_bits =9;
	next_bump_code =511;
}

void InitializeStorage()
{
	int i;

	for(i=0;i<TABLE_BANKS;i++)
	{
		//dict[i] =(struct dictionary *)
		//      calloc(256,sizeof(struct dictionary));
		dict[i] =(dictionary *)
			_fmalloc(256*sizeof(dictionary));

		if(dict[i] == NULL)
			fatal_error("Error allocating dictionary space");
	}
}

void CompressFile(char * infile,char *outfile)
{
	int character;
	int string_code;
	unsigned int index;
     
    BIT_FILE * output;
    FILE * input;
    
	input = fopen(infile,"rb");
    if(input==NULL)
    {
		fatal_error("Can not open input file");
		return;
    }
	output =OpenOutputBitFile(outfile);
    if(output ==NULL)
    {
		fatal_error("Can not open output file");
		fclose(input);
		return;    
    }
	InitializeStorage();
	InitializeDictionary();

	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
		{
			DICT(index).code_value =next_code++;
			DICT(index).parent_code=string_code;
			DICT(index).character=(char)character;

			OutputBits(output,(unsigned long)string_code,current_code_bits);
			string_code =character;
			if(next_code>MAX_CODE)
			{
				OutputBits(output,(unsigned long)FLUSH_CODE,current_code_bits);
				InitializeDictionary();
			}
			else if(next_code>next_bump_code)
			{
				OutputBits(output,(unsigned long)BUMP_CODE,current_code_bits);
				current_code_bits++;
				next_bump_code<<=1;
				next_bump_code|=1;
				//putc('B',stdout);
			}
		}
	}
	OutputBits(output,(unsigned int)string_code,current_code_bits);
	OutputBits(output,(unsigned int)END_OF_STREAM,current_code_bits);
	ExitLzw();
	CloseOutputBitFile(output);
	fclose(input);  
}

void CompressMemFile(char *ptr,long len,char *outfile)
{
	int character;
	int string_code;
	unsigned int index;
	BIT_FILE *output;
	
	output =OpenOutputBitFile(outfile);
    if(output ==NULL)
    {
		fatal_error("Can not open output file");
		return;    
    }

	InitializeStorage();
	InitializeDictionary();

	if(len==0)
		string_code =EOF;
	else
	{
		string_code =*ptr++;
		len--;
	}
	if(string_code == EOF)
		string_code = END_OF_STREAM;

	for(;;)
	{
		if(len==0L)
		{
			character =EOF;
			break;
		}
		else
		{
			character =*ptr++;
			len--;
		}

		index =find_child_node(string_code,character);
		if(DICT(index).code_value !=-1)
			string_code =DICT(index).code_value;
		else
		{
			DICT(index).code_value =next_code++;
			DICT(index).parent_code=string_code;
			DICT(index).character=(char)character;

			OutputBits(output,(unsigned long)string_code,current_code_bits);
			string_code =character;
			if(next_code>MAX_CODE)
			{
				OutputBits(output,(unsigned long)FLUSH_CODE,current_code_bits);
				InitializeDictionary();
			}
			else if(next_code>next_bump_code)
			{
				OutputBits(output,(unsigned long)BUMP_CODE,current_code_bits);
				current_code_bits++;
				next_bump_code<<=1;
				next_bump_code|=1;
				//putc('B',stdout);
			}
		}
	}
	OutputBits(output,(unsigned int)string_code,current_code_bits);
	OutputBits(output,(unsigned int)END_OF_STREAM,current_code_bits);
	ExitLzw();
	CloseOutputBitFile(output);	
}

void ExpandFile(char *infile,char *outfile)
{
	unsigned int new_code;
	unsigned int old_code;
	int character;
	unsigned int count;

    FILE * output;
    BIT_FILE * input;
    
    decode_stack =(char *)_fmalloc((size_t)TABLE_SIZE);
    if(decode_stack ==NULL)
    	fatal_error("can not get decode_stack space");
    	
	output = fopen(outfile,"wb");
    if(output==NULL)
    {
		fatal_error("Can not open output file");
		return;
    }
	input =OpenInputBitFile(infile);
    if(input ==NULL)
    {
		fatal_error("Can not open input file");
		fclose(output);
		_ffree(decode_stack);
		return;    
    }

	InitializeStorage();
	for(;;)
	{
		InitializeDictionary();
		old_code =(unsigned int)InputBits(input,current_code_bits);

		if(old_code == END_OF_STREAM)
		{
			CloseInputBitFile(input);
			fclose(output); 
			ExitLzw();              
			_ffree(decode_stack);
			return;
		}       
		character =old_code;
		putc(old_code,output);

		for(;;)
		{
			new_code =(unsigned int) InputBits(input,current_code_bits);
			if(new_code == END_OF_STREAM)
			{
				CloseInputBitFile(input);
				fclose(output);                 
				ExitLzw();                      
				_ffree(decode_stack);						
				return;
			}       
			if(new_code == FLUSH_CODE)
				break;
			if(new_code == BUMP_CODE)
			{
				current_code_bits++;
				//putc('B',stdout);
				continue;
			}
			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);
			DICT(next_code).parent_code =old_code;
			DICT(next_code).character =(char)character;
			next_code++;
			old_code = new_code;
		}
	}
}

unsigned int find_child_node(int parent_code ,int child_character)
{
	unsigned int index;
	unsigned int offset;
    
	index =(child_character <<(BITS-8)) ^parent_code;
	if(index ==0)
		offset =1;
	else
		offset =(unsigned int)(TABLE_SIZE -(long)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);
		if((long)index >=(long)offset)
			index =(unsigned int)((long)index -(long)offset);
		else
			index=index +(unsigned int)(TABLE_SIZE-(long)offset);
	}
}

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