// CompressArithmetic.cpp: implementation of the CCompressArithmetic class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Compress.h"
#include "CompressArithmetic.h"

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

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

CCompressArithmetic::CCompressArithmetic()
{
	code_value=NULL;			/* This is the code value array */
	prefix_code=NULL;			/* This array holds the prefix codes */
	append_character=NULL;		/* This array holds the appended chars */
	decode_stack=NULL;			/* This array holds the decoded string */
	num_bits=INIT_BITS;			/* Starting with 9 bit codes */
	bytes_in=0,bytes_out=0;		/* Used to monitor compression ratio */
	input_bit_count=0;
	input_bit_buffer=0L;
	output_bit_count=0;
	output_bit_buffer=0L;
	checkpoint=CHECK_TIME;		/* For compression ratio monitoring */
	incounts=0;					/* Input Bytes */
	outcounts=0;				/* Output Bytes */
	counts=0;					/* Statistic */
	bFlagAlloc=false;
}

CCompressArithmetic::~CCompressArithmetic()
{
	/*掃尾*/
	if(code_value)
		code_value=(int*)GlobalFree(code_value);
	if(prefix_code)
		prefix_code=(unsigned int*)GlobalFree(prefix_code);
	if(append_character)
		append_character=(unsigned char*)GlobalFree(append_character);
	if(decode_stack)
		decode_stack=(unsigned char*)GlobalFree(decode_stack);
	bFlagAlloc=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 CCompressArithmetic::compress()
{
	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% */

	num_bits=INIT_BITS;				/* Re-initialize for expansion */
	max_code = MAXVAL(num_bits);

	for (i=0;i<TABLE_SIZE;i++){		/* Initialize the string table first */
		code_value[i]=-1;
	}
	string_code=*input++;			/* Get the first code */
	incounts++;					
 /* 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(incounts<counts ) {
		character=*input++;
		incounts++;
		++bytes_in;
		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(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? */
					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(CLEAR_TABLE);			/* YES,flush string table */
							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(string_code);			/* Output the last code */
	if (next_code == max_code) {		/* Handles special case for bit */
		++num_bits;						/* increment on EOF */
	}
	output_code(TERMINATOR);			/* Output the end of buffer code */
	output_code(0);						/* Flush the output buffer */
	output_code(0);
	output_code(0);
}
/* 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 CCompressArithmetic::uncompress()
{
	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;
	num_bits=INIT_BITS;                  /* Re-initialize for expansion */
	max_code = MAXVAL(num_bits);
	while((new_code=input_code()) != 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 */
		  *output++=(unsigned char)old_code;
		  outcounts++;
		  continue;
	  }
	  if (new_code == CLEAR_TABLE) {     /* Clear string table */
		  clear_flag=1;
		  num_bits=INIT_BITS;
		  next_code=FIRST_CODE;
		  max_code = MAXVAL(num_bits);
		  continue;
	  }
	  if (++counter == 1000) {           /* Pacifier */
		  counter=0;
	  }
	  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){
		  *output++=*string--;
		  outcounts++;
	  }

	  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) {
			  max_code = MAXVAL(++num_bits);
		  }
	  }
	  old_code=new_code;
	}
}

/* UNCHANGED from original
 * This is the hashing routine.
 */
int CCompressArithmetic::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 *CCompressArithmetic::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 ) {
			/*一般不會錯*/
		   ;
	   }
   }
   *buffer=code;
   return(buffer);
}

/* UNCHANGED from original
 * Input a variable length code.
 */
unsigned CCompressArithmetic::input_code()
{
	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) (*input++) << (24 - input_bit_count);
		incounts++;
		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 CCompressArithmetic::output_code(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) {
		*output++=(unsigned char)(output_bit_buffer >> 24);
		output_bit_buffer <<= 8;
		output_bit_count -= 8;
		bytes_out++;                    /* ADDED for compression monitoring */
		outcounts++;
	}
}

bool CCompressArithmetic::AllocTables()
{
	bool flag=true;
	__try{
	code_value=(int*)GlobalAlloc(GPTR,TABLE_SIZE*sizeof(unsigned int));
	prefix_code=(unsigned int *)GlobalAlloc(GPTR,TABLE_SIZE*sizeof(unsigned int));
	append_character=(unsigned char*)GlobalAlloc(GPTR,TABLE_SIZE*sizeof(unsigned char));
	decode_stack=(unsigned char*)GlobalAlloc(GPTR,4000);
	bFlagAlloc=true;
	}
	__except(1){
		if(code_value)
			code_value=(int*)GlobalFree(code_value);
		if(prefix_code)
			prefix_code=(unsigned int*)GlobalFree(prefix_code);
		if(append_character)
			append_character=(unsigned char*)GlobalFree(append_character);
		if(decode_stack)
			decode_stack=(unsigned char*)GlobalFree(decode_stack);
			flag=false;
			bFlagAlloc=false;
		}
	return flag;
}

void CCompressArithmetic::FreeTables()
{
	if(code_value)
		code_value=(int*)GlobalFree(code_value);
	if(prefix_code)
		prefix_code=(unsigned int*)GlobalFree(prefix_code);
	if(append_character)
		append_character=(unsigned char*)GlobalFree(append_character);
	if(decode_stack)
		decode_stack=(unsigned char*)GlobalFree(decode_stack);
	bFlagAlloc=false;
}

bool CCompressArithmetic::init(unsigned char *inputs,unsigned long lens,unsigned char *outputs)
{
	if(!bFlagAlloc)
		return false;
	input=inputs;
	output=outputs;
	counts=lens;
	num_bits=INIT_BITS;               /* Starting with 9 bit codes */
	max_code = MAXVAL(num_bits);
	bytes_in=0,bytes_out=0; /* Used to monitor compression ratio */
	input_bit_count=0;
	input_bit_buffer=0L;
	output_bit_count=0;
	output_bit_buffer=0L;
	checkpoint=CHECK_TIME;  /* For compression ratio monitoring */
	incounts=0;
	outcounts=0;
	return true;
	
}

unsigned long CCompressArithmetic::GetOutBytes()
{
	return outcounts;
}

unsigned long CCompressArithmetic::GetInBytes()
{
	return incounts;
}