arith-n.cpp

Arith-N 是可以在命令行指定阶数的 N 阶上下文自适应算术编码通用压缩、解压缩程序

			else
				table->links = (LINKS*)realloc((char*)table->links, new_size);
			if (table->links == NULL)
				fatal_error("Error #9: reallocating table space!");
			table->links[index].next = NULL;
		}
		new_size = sizeof(STATS);
		new_size *= table->max_index + 1;
		if (table->max_index == 0)
			table->stats = (STATS*)calloc(new_size, 1);
		else
			table->stats = (STATS*)realloc((char*)table->stats, new_size);
		if (table->stats == NULL)
			fatal_error("Error #10: reallocating table space!");
		table->stats[index].symbol = (unsigned char)symbol;
		table->stats[index].counts = 0;
	}
	// now I move the symbol to the front of its list
	i = index;
	while (i > 0 && table->stats[index].counts == table->stats[i - 1].counts)
		i--;
	if (i != index)
	{
		temp = table->stats[index].symbol;
		table->stats[index].symbol = table->stats[i].symbol;
		table->stats[i].symbol = temp;
		if (table->links != NULL)
		{
			temp_ptr = table->links[index].next;
			table->links[index].next = table->links[i].next;
			table->links[i].next = temp_ptr;
		}
		index = i;
	}
	// the switch has been performed. now I can update the counts
	table->stats[index].counts++;
	if (table->stats[index].counts == 255)
		rescale_table(table);
}

int convert_int_to_symbol(int c, SYMBOL* s)
{
	int i;
	CONTEXT* table;

	table = contexts[current_order];
	totalize_table(table);
	s->scale = totals[0];
	if (current_order == -2)
		c = -c;
	for ( i = 0; i <= table->max_index; i++ )
	{
		if (c == (int)table->stats[i].symbol)
		{
			if (table->stats[i].counts == 0)
				break;
			s->low_count = totals[i+2];
			s->high_count = totals[i+1];
			return (0);
		}
	}
	s->low_count = totals[1];
	s->high_count = totals[0];
	current_order--;
	return (1);
}

void get_symbol_scale( SYMBOL* s )
{
	CONTEXT* table;

	table = contexts[current_order];
	totalize_table(table);
	s->scale = totals[0];
}

int convert_symbol_to_int(int count, SYMBOL* s)
{
	int c;
	CONTEXT* table;
	
	table = contexts[current_order];
	for ( c = 0; count < totals[c]; c++ )
		;
	s->high_count = totals[c - 1];
	s->low_count = totals[c];
	if (c == 1)
	{
		current_order--;
		return (ESCAPE);
	}
	if (current_order < -1)
		return ((int) -table->stats[c - 2].symbol);
	else
		return (table->stats[c - 2].symbol);
}

void add_character_to_model( int c )
{
	int i;
	if (max_order < 0 || c < 0)
		return;
	contexts[max_order] = 
		shift_to_next_context(contexts[max_order], c, max_order);
	for (i = max_order - 1; i > 0; i--)
		contexts[i] = contexts[i + 1]->lesser_context;
}

CONTEXT* shift_to_next_context(CONTEXT* table, int c, int order)
{
	int i;
	CONTEXT* new_lesser;

	// first, try to find the new context by backing up the lesser
	// context and searching its link table. if I find the link, we take
	// a quick and easy exit, returning the link. note that their is a 
	// special Kludge for context order 0. we hnow for a fact that 
	// that lesser context pointer at order 0 points to the null table.
	// order -1, and we know that the -1 table only has a single link
	// pointer. which points back to the order 0 table.
	table = table->lesser_context;
	if (order == 0)
		return (table->links[0].next);
	for (i = 0; i <= table->max_index; i++)
		if ( table->stats[i].symbol == (unsigned char)c )
			if ( table->links[i].next != NULL)
				return (table->links[i].next);
			else
				break;

	// if I get here, it means the new context did not exist. I have to 
	// create the new context, add a link to it here, and add the backwards
	// link to *his* previous context. Creating the table and adding it to
	// this table is pretty easy. but adding the back pointer isn't. Since
	// creating the new back pointer isn't easy, I duck my responsibility
	// and recurse to myself in order to pick it up.
	new_lesser = shift_to_next_context(table, c, order - 1);

	// Now that I have the back pointer for this table, I can make a call
	// to a utility to allocate the new table
	table = allocate_next_order_table(table, c, new_lesser);
	return (table);
}

// rexdaling the table needs to be done for one of three reasons.
// first, if the maximum count for the table has exceeded 16383, it 
// means that arithmetic coding using 16 and 32 bit registers might
// no longer work. secondly, if an individual symbol count has
// reached 255, it will no longer fit in a byte. third, if the
// current model isn't compressing well, the compressor program may 
// want to rescale all tables in order to give more weight to newer
// statistics.
// all this routine does is divide each count by 2. if any counts
// drop to 0, the counters can be removed from the stats table, but 
// only if this is a leaf context. Otherwise, we might cut a link to 
// a higher order table.
void rescale_table(CONTEXT* table)
{
	int i;

	if ( table->max_index == -1)
		return;
	for( i = 0; i <= table->max_index; i++)
		table->stats[i].counts /= 2;
	if (table->stats[table->max_index].counts == 0 &&
			table->links == NULL)
	{
		while ( table->stats[table->max_index].counts == 0 &&
				table->max_index >= 0)
			table->max_index--;
		if (table->max_index == -1)
		{
			free( (char*) table->stats );
			table->stats = NULL;
		}
		else
		{
			table->stats = (STATS*)realloc((char*)table->stats, 
				sizeof(STATS) * (table->max_index + 1));
			if (table->stats == NULL)
				fatal_error("Error #11: reallocating stats space!");
		}
	}
}


// this routine has the job of creating a cumulative totals table for
// a given context. the cumulative low and high for symbol c are going to 
// be shored in totals[c + 2] and totals[c + 1]. Locations 0 and 1 are 
// reserved for the special ESCAPE symbol.
void totalize_table(CONTEXT* table)
{
	int i;
	unsigned char max;

	for(;;)
	{
		max = 0;
		i = table->max_index + 2;
		totals[i] = 0;
		for (; i > 1; i--)
		{
			totals[i - 1] = totals[i];
			if (table->stats[i - 2].counts)
				if ((current_order == -2) || 
						scoreboard[table->stats[i - 2].symbol] == 0)
					totals[i - 1] += table->stats[i - 2].counts;
			if (table->stats[i - 2].counts > max)
				max = table->stats[i - 2].counts;
		}

		// here is where the escape calulation needs to take place.
		if  (max == 0)
			totals[0] = 1;
		else
		{
			totals[0] = (short int)(256 - table->max_index);
			totals[0] *= table->max_index;
			totals[0] /= 256;
			totals[0] /= max;
			totals[0]++;
			totals[0] += totals[1];
		}
		if (totals[0] < MAXIMUM_SCALE)
			break;
		rescale_table(table);
	}
	for(i = 0; i < table->max_index; i++)
		if (table->stats[i].counts != 0)
			scoreboard[table->stats[i].symbol] = 1;
}

void recursive_flush( CONTEXT* table )
{
	int i;
	if (table->links != NULL)
		for ( i = 0; i <= table->max_index; i++)
			if (table->links[i].next != NULL)
				recursive_flush(table->links[i].next);
	rescale_table(table);
}

void flush_model()
{
	putc('F', stdout);
	recursive_flush(contexts[0]);
}


//---------------------------------------------------------------
// everything from here down define the arithmetic coder section
// of the program

static unsigned short int code;		// the present input code value
static unsigned short int low;		// start of the current code range
static unsigned short int high;		// end of the current code range
long underflow_bits;				// number of underflow bits pending

void initialize_arithmetic_encoder()
{
	low = 0;
	high = 0xffff;
	underflow_bits = 0;
}

void flush_arithmetic_encoder( BIT_FILE* stream )
{
	OutputBit( stream, low & 0x4000 );
	underflow_bits++;
	while( underflow_bits-- > 0 )
		OutputBit( stream, ~low & 0x4000 );
	OutputBits( stream, 0L, 16 );
}

void encode_symbol( BIT_FILE* stream, SYMBOL* s )
{
	long range; 

	// these three lines rescale high and low for the new symbol.
	range = (long)(high - low) + 1;
	high = low + (unsigned short int)
			((range * s->high_count) / s->scale - 1);
	low = low + (unsigned short int)
			((range * s->low_count) / s->scale);

	// this loop turns out new bits until high and low are far enough
	// apart to have stabilized.
	for (;;)
	{
		// if this test passer, it means that the MSDigits match, and can
		// be sent to the output stream.
		if ((high & 0x8000) == (low & 0x8000))
		{
			OutputBit( stream, high & 0x8000 );
			while ( underflow_bits > 0 )
			{
				OutputBit( stream, ~high & 0x8000);
				underflow_bits--;
			}
		}
		// if this test passes, the numbers are in danger of underflow, because
		// the MSDigits don't match, and the 2nd digits are just one apart.
		else if ((low & 0x4000) && !(high & 0x4000))
		{
			underflow_bits += 1;
			low &= 0x3fff;
			high |= 0x4000;
		}
		else
			return;
		low <<= 1;
		high <<= 1;
		high |= 1;
	}
}

short int get_current_count( SYMBOL* s )
{
	long range;
	short int count;

	range = (long)(high - low) + 1;
	count = (short int)
			((((long) ( code - low ) + 1) * s->scale - 1) / range);
	return (count);
}

void initialize_arithmetic_decoder( BIT_FILE* stream )
{
	int i;
	code = 0;
	for (i = 0; i < 16; i++)
	{
		code <<= 1;
		code += InputBit(stream);
	}
	low = 0;
	high = 0xffff;
}

void remove_symbol_from_stream( BIT_FILE* stream, SYMBOL* s )
{
	long range;

	// first, the range is expanded to account for the symbol removal
	range = (long)(high - low) + 1;
	high = low + (unsigned short int)
			((range * s->high_count) / s->scale - 1);
	low = low + (unsigned short int)
			((range * s->low_count) / s->scale);
	// next, any possible bits are shipped out
	for (;;)
	{
		// if the MSDigits match, the ibts will be shifted out.
		if ((high & 0x8000) == (low & 0x8000))
		{
		}
		// else, if underflow is threatening, shift out the 2nd MSDigit.
		else if ((low & 0x4000) == 0x4000 && (high & 0x4000) == 0)
		{
			code ^= 0x4000;
			low &= 0x3fff;
			high |= 0x4000;
		}
		// otherwise, nothing can be shifted out, so I return.
		else
			return;
		low <<= 1;
		high <<= 1;
		high |= 1;
		code <<= 1;		
		code += InputBit(stream);
	}
}