www.pudn.com > arithmetic_demo.zip > 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<
class CArithmeticModel
{
public:
void start_model()
{
int i;
for (i = 0; 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= 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)
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> 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)
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>= 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(this)->GetByte();
}
void PutByte_(int byte)
{
static_cast(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 */
};