model.h

推荐一个快速压缩算法

#pragma once

/*
This is based on the adaptive arithmetic coding software by R. M. Neal that 
is contained in the following reference:

  Witten, I. H., Neal, R. M., and Cleary, J. G. (1987) 
    "Arithmetic coding for data compression", Communications 
    of the ACM, vol. 30, no. 6 (June).
*/

/* INTERFACE TO THE MODEL. */

/* DECLARATIONS USED FOR ARITHMETIC ENCODING AND DECODING */

/* SIZE OF ARITHMETIC CODE VALUES. */

#define Code_value_bits 16		/* Number of bits in a code value   */
typedef long code_value;		/* Type of an arithmetic code value */

#define Top_value (((long)1<<Code_value_bits)-1)      /* Largest code value */


/* HALF AND QUARTER POINTS IN THE CODE VALUE RANGE. */

#define First_qtr (Top_value/4+1)	/* Point after first quarter        */
#define Half	  (2*First_qtr)		/* Point after first half           */
#define Third_qtr (3*First_qtr)		/* Point after third quarter        */

/* THE SET OF SYMBOLS THAT MAY BE ENCODED. */

#define No_of_chars 256			/* Number of character symbols      */
#define EOF_symbol (No_of_chars+1)	/* Index of EOF symbol              */

#define No_of_symbols (No_of_chars+1)	/* Total number of symbols          */


/* TRANSLATION TABLES BETWEEN CHARACTERS AND SYMBOL INDEXES. */

/* CUMULATIVE FREQUENCY TABLE. */

#define Max_frequency 16383		/* Maximum allowed frequency count  */

//warning C4127: conditional expression is constant
//warning C4710: function '...' not inlined
#pragma warning(disable:4710 4127)

template<typename T>
class CArithmeticModel
{
public:
	void start_model()
	{
		int i;
		for (i = 0; i<No_of_chars; i++) {		/* Set up tables that       */
			char_to_index[i] = i+1;			/* translate between symbol */
			index_to_char[i+1] = (unsigned char) i;			/* indexes and characters.  */
		}
		for (i = 0; i<=No_of_symbols; i++) {	/* Set up initial frequency */
			freq[i] = 1;				/* counts to be one for all */
			cum_freq[i] = No_of_symbols-i;		/* symbols.                 */
		}
		freq[0] = 0;				/* Freq[0] must not be the  */
	}
	void update_model(int symbol)
	{   
		int i;			/* New index for symbol                     */
		if (cum_freq[0]==Max_frequency) {		/* See if frequency counts  */
			int cum = 0;				/* are at their maximum.    */
			for (i = No_of_symbols; i>=0; i--) {	/* If so, halve all the     */
				freq[i] = (freq[i]+1)/2;		/* counts (keeping them     */
				cum_freq[i] = cum; 			/* non-zero).               */
				cum += freq[i];
			}
		}
		for (i = symbol; freq[i]==freq[i-1]; i--) ;	/* Find symbol's new index. */
		if (i<symbol) 
		{
			unsigned char ch_i = index_to_char[i];		/* Update the translation   */
			unsigned char ch_symbol = index_to_char[symbol];	/* tables if the symbol has */
			index_to_char[i] = ch_symbol;           /* moved.                   */
			index_to_char[symbol] = ch_i;
			char_to_index[ch_i] = symbol;
			char_to_index[ch_symbol] = i;
		}
		freq[i]++;				/* Increment the frequency  */

		for (int* pFreq = cum_freq + i; --pFreq >= cum_freq; )
			++(*pFreq);
	}

	void start_encoding()
	{   
		//low = 0;					/* Full code range.         */
		//high = Top_value;
		low_high = 0;
		bits_to_follow = 0;				/* No bits to follow next.  */
	}
	void encode_symbol(int symbol, int cum_freq[])	/* Symbol to encode                         */
	{   
		long low = low_high & 0xFFFF;
		long high = (~low_high) >> 16; // Note that low_high is unsigned

		long range = (long)(high-low)+1;	/* Size of the current code region          */
		high = low +				/* Narrow the code region   */
			(range*cum_freq[symbol-1])/cum_freq[0]-1;	/* to that allotted to this */
		low = low + 				/* symbol.                  */
			(range*cum_freq[symbol])/cum_freq[0];

		low_high = low + ((~high) << 16);

		do
		{
			if ((long)low_high < 0)
			{
				bit_plus_follow_0();			/* Output 0 if in low half. */
			} 
			//else if (low>=Half) 
			else if ((short)low_high < 0)
			{			/* Output 1 if in high half.*/
				bit_plus_follow_1();

				//low -= Half;
				//high -= Half;			/* Subtract offset to top.  */
				low_high += unsigned long(Half << 16) - Half;
			}
			else 
				break;
		
			for (;;) 
			{					/* Loop to output bits.     */
				//low = 2*low;
				//high = 2*high+1;			/* Scale up code range.     */
				low_high <<= 1;

				//if (high<Half) 
				if ((long)low_high < 0)
				{
					//bit_plus_follow_0();			/* Output 0 if in low half. */
					output_bit_0();				/* Output the bit.          */
				} 
				//else if (low>=Half) 
				else if ((short)low_high < 0)
				{			/* Output 1 if in high half.*/
					//bit_plus_follow_1();
					output_bit_1();				/* Output the bit.          */

					//low -= Half;
					//high -= Half;			/* Subtract offset to top.  */
					low_high += unsigned long(Half << 16) - Half;
				}
				else 
					break;
			}
		}
		while (false);

		//while (low>=First_qtr && high<Third_qtr)
		unsigned long buf = ~low_high;
		if (!(buf & 0x40004000))
		{
			do
			{
				bits_to_follow++;
				//low = 2 * (low - First_qtr);			// Subtract offset to middle
				//high = 2 * (high - First_qtr) + 1;
				buf = (buf << 1) + 1 + (First_qtr << 1) - (First_qtr << 17);
			} 
			while (!(buf & 0x40004000));
			low_high = ~buf;
		}

	}
	void done_encoding()
	{   
		bits_to_follow += 1;			/* Output two bits that     */
		//if (low<First_qtr) 
		if ((low_high & 0x0000FFFF) < First_qtr) 
			bit_plus_follow_0();	/* select the quarter that  */
		else 
			bit_plus_follow_1();			/* the current code range   */
	}

	void start_decoding()
	{   
		int i;
		value = 0;					/* Input bits to fill the   */
		for (i = 1; i<=Code_value_bits; i++) {	/* code value.              */
			value = 2*value+input_bit();
		}
		//low = 0;					/* Full code range.         */
		//high = Top_value;
		low_high = 0;
	}
	int decode_symbol(int cum_freq[])
	{   
		//long range;			/* Size of current code region              */
		//int cum;			/* Cumulative frequency calculated          */
		int symbol;			/* Symbol decoded                           */

		long low = low_high & 0xFFFF;
		long high = (~low_high) >> 16; // Note that low_high is unsigned

		long range = (long)(high-low)+1;
		int cum = 					/* Find cum freq for value. */
			(((long)(value-low)+1)*cum_freq[0]-1)/range;
		for (symbol = 1; cum_freq[symbol]>cum; symbol++) ; /* Then find symbol. */
		high = low +				/* Narrow the code region   */
			(range*cum_freq[symbol-1])/cum_freq[0]-1;	/* to that allotted to this */
		low = low + 				/* symbol.                  */
			(range*cum_freq[symbol])/cum_freq[0];

		low_high = low + ((~high) << 16);

		for (;;) 
		{					/* Loop to get rid of bits. */
			//if (high<Half) 
			if ((long)low_high < 0)
			{
				/* nothing */			/* Expand low half.         */
			} 
			//else if (low>=Half) 
			else if ((short)low_high < 0)
			{			/* Expand high half.        */
				value -= Half;
				//low -= Half;			/* Subtract offset to top.  */
				//high -= Half;
				low_high += unsigned long(Half << 16) - Half;
			}
			//else if (low>=First_qtr			/* Expand middle half.      */
			//	  && high<Third_qtr) 
			else if (!((low_high | ~0x40004000) + 1))
			{
				value -= First_qtr;
				//low -= First_qtr;			/* Subtract offset to middle*/
				//high -= First_qtr;
				low_high += (First_qtr << 16) - First_qtr;
			}
			else break;				/* Otherwise exit loop.     */
			//low = 2*low;
			//high = 2*high+1;			/* Scale up code range.     */
			low_high <<= 1;

			value = 2*value+input_bit();		/* Move in next input bit.  */
		}
		return symbol;
	}

	void start_inputing_bits()
	{   
		bits_to_go = 0;				/* Buffer starts out with   */
	}						/* no bits in it.           */
	int input_bit()
	{   
		int t;
		bits_to_go -= 1;
		if (bits_to_go<0) {				/* Read the next byte if no */
			buffer = GetByte_();			/* bits are left in the     */
			bits_to_go = 7;				/* buffer. Return anything  */
		}			   			/* after end-of-file.       */
		t = buffer&1;
		buffer >>= 1;				/* Return the next bit from */
		return t;					/* the bottom of the byte.  */
	}

	void start_outputing_bits()
	{   
		buffer = 0;					/* Buffer is empty to start */
		bits_to_go= 8;				/* with.                    */
	}
	void done_outputing_bits()
	{   
		PutByte_(buffer>>bits_to_go);
	}

	int GetByte_()
	{
		return static_cast<T*>(this)->GetByte();
	}
	void PutByte_(int byte)
	{
		static_cast<T*>(this)->PutByte(byte);
	}

	int char_to_index[No_of_chars];		/* To index from character          */
	unsigned char index_to_char[No_of_symbols+1]; /* To character from index    */
	int cum_freq[No_of_symbols+1];		/* Cumulative symbol frequencies    */

protected:
	void bit_plus_follow_0()
	{   
		output_bit_0();				/* Output the bit.          */
		while (bits_to_follow>0) {
//			output_bit_1();			/* Output bits_to_follow    */
			buffer >>= 1; buffer |= 0x80;	/* Put bit in top of buffer.*/
			if (--bits_to_go==0) {			/* Output buffer if it is   */
				flush_bits_to_follow(255);
				return;
			}
			bits_to_follow--;			/* opposite bits. Set       */
		}						/* bits_to_follow to zero.  */
	}
	void bit_plus_follow_1()
	{   
		output_bit_1();				/* Output the bit.          */
		while (bits_to_follow>0) {
//			output_bit_0();			/* Output bits_to_follow    */
			buffer >>= 1; //if (bit) buffer |= 0x80;	/* Put bit in top of buffer.*/
			if (--bits_to_go==0) {			/* Output buffer if it is   */
				flush_bits_to_follow(0);
				return;
			}
			bits_to_follow--;			/* opposite bits. Set       */
		}						/* bits_to_follow to zero.  */
	}

	void output_bit_0()
	{   
		buffer >>= 1; //if (bit) buffer |= 0x80;	/* Put bit in top of buffer.*/
		if (--bits_to_go==0) {			/* Output buffer if it is   */
			PutByte_(buffer);			/* now full.                */
			bits_to_go = 8;
		}
	}
	void output_bit_1()
	{   
		buffer >>= 1; buffer |= 0x80;	/* Put bit in top of buffer.*/
		if (--bits_to_go==0) {			/* Output buffer if it is   */
			PutByte_(buffer);			/* now full.                */
			bits_to_go = 8;
		}
	}

private:
	void flush_bits_to_follow(int buffer_)
	{
		for (;;)
		{
			PutByte_(buffer);			/* now full.                */
			buffer = buffer_;
			if (bits_to_follow <= 8)
				break;
			bits_to_follow -= 8;
		}
		bits_to_go = 9 - bits_to_follow;
		bits_to_follow = 0;
	}

	int freq[No_of_symbols+1];	/* Symbol frequencies                       */

	//code_value low, high;	/* Ends of the current code region          */
	unsigned long low_high;
	long bits_to_follow;	/* Number of opposite bits to output after  */
					/* the next bit.                            */
	code_value value;	/* Currently-seen code value                */

	int buffer;		/* Bits waiting to be input                 */
	int bits_to_go;		/* Number of bits still in buffer           */
};