//*********************************************************************************************
//Simple arithmetic coding program for the example of Witten and Neal's paper---
// ---arithmetic coding for data compression(Communications of ACM,June 1987 Volume 30 Number 6)
//
//                                    integer mul&div
//******************************************************************************************
#include "stdio.h"
typedef long code_value;

#define Top_value 65535
#define First_qtr 16384
#define Half 32768
#define Third_qtr 49152


static code_value low, high;
static long bits_to_follow;

void bit_plus_follow(int);
void start_encoding();
void encode_symbol(int,long *);

int main(int argc, char* argv[])
{
	long c_freq[7]={16383,14745,13106,9830,8192,3278,0}; //AC Models
	int sym[5]={5,6,4,4,1};
	int i;
	
	start_encoding();
	for(i=0;i<5;i++)
		encode_symbol(sym[i],c_freq);

	return 0;
		
}

void encode_symbol(int symbol,long *cum_freq)
{
	long range;
	range=(long)(high-low)+1;
	high=low+(range*cum_freq[symbol-1])/cum_freq[0]-1;
	low=low+(range*cum_freq[symbol])/cum_freq[0];
	for(;;)
	{

		if(high<Half)
		{
			bit_plus_follow(0);
		}
		else if(low>=Half)
		{
			bit_plus_follow(1);
			low-=Half;
			high-=Half;
		}
		else if(low>=First_qtr&&high<Third_qtr)
		{
			bits_to_follow+=1;
			low-=First_qtr;
			high-=First_qtr;
		}
		else break;
		low=2*low;
		high=2*high+1;

	}
}

void start_encoding()
{
	low=0;
	high=Top_value;
	bits_to_follow=0;
		
}

void bit_plus_follow(int bit)
{
	printf("%d",bit);
	while(bits_to_follow>0)
	{
		printf("%d",!bit);
		bits_to_follow--;
	}
}