acmod.c

This code implements the arithmetic coding algorithm used for text compression. At present it takes

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<stdlib.h>

#define COUNT 3

char* pad(char*,int);
int bin_to_dec(char*);


void main()
{
	int symbol[COUNT];
	int cum_count[COUNT];
	int i,total,wordlength,l,u,lprev,uprev,temp,j,scale3;
	char *str="";
	char *tag="";
	char *l_bincode="";
	char *u_bincode="";
	clrscr();

	symbol[0]=40;
	symbol[1]=1;
	symbol[2]=9;

	for(i=0;i<COUNT;i++)
	{
		if(i==0)
		{
			cum_count[i]=symbol[i];
			continue;
		}
		cum_count[i]=cum_count[i-1]+symbol[i];
	}

	printf("Enter string to encode:");
	scanf("%s",str);

	total=cum_count[2];
	lprev=0;
	temp=total*4;

	for(i=0;;i++)
	{
		if(pow(2,i) >= temp)
			break;
	}
	wordlength=i;
	uprev=pow(2,i)-1;

	l_bincode=(char*)malloc(wordlength*sizeof(char));
	u_bincode=(char*)malloc(wordlength*sizeof(char));

	for(i=0;i<strlen(str);i++)
	{
		if((i-1)<0)
			l=lprev;
		else
			l=lprev+floor((uprev-lprev+1)*cum_count[i-1]/total);
		u=lprev+floor((uprev-lprev+1)*cum_count[i]/total)-1;

		itoa(l,l_bincode,2);
		//l_bincode=pad(l_bincode,wordlength);
		l_bincode=dec_to_bin(l,wordlength);
		itoa(u,u_bincode,2);
		//u_bincode=pad(u_bincode,wordlength);
		u_bincode=dec_to_bin(u,wordlength);

		while(1)
		{
			if(l_bincode[0]==u_bincode[0])
			{
				if(l_bincode[0]==0)
				{
					//E1 mapping
					for(j=1;j<wordlength;j++)
					{
						l_bincode[j-1]=l_bincode[j];
					}
					l_bincode[j]='0';
					strcat(tag,"0");
					if(scale3!=0)
					{
						for(j=0;j<scale3;j++)
						{
							strcat(tag,"1");
							scale3--;
						}
					}
				}
				else
				{
					//E2 mapping
					for(j=1;j<wordlength;j++)
					{
						u_bincode[j-1]=u_bincode[j];
					}
					u_bincode[j]='1';
					strcat(tag,"1");
					if(scale3!=0)
					{
						for(j=0;j<scale3;j++)
						{
							strcat(tag,"0");
							scale3--;
						}
					}
				}
			}
			else if(l_bincode[0]==0 && u_bincode[0]==1 && l_bincode[1]==1 && u_bincode[1]==0)
			{
				//E3 mapping
				scale3++;
			}
			else
				break;
		}
		l_bincode[strlen(l_bincode)]=NULL;
		lprev=bin_to_dec(l_bincode);
		uprev=bin_to_dec(u_bincode);
	}

	strcat(tag,l_bincode);
	strcat(tag,"\0");

	printf("\n\nTag value is: %s",tag);
	getch();
}

/*
char* pad(char* str,int l)
{
	char *temp="";
	int i,padlen;
	temp=(char*)malloc(l*sizeof(char));

	if(strlen(str)==l)
		return str;
	else
	{
		padlen=l-strlen(str);
		strcpy(temp,"0");
		for(i=1;i<padlen;i++)
			strcat(temp,"0");
		strcat(temp,str);
		str[strlen(str)]=NULL;
		return temp;
	}
}
*/

char* dec_to_bin(int num,int l)
{
	char *str=(char*)malloc(l*sizeof(char));
	int temp=num
	i=l-1;
	while(temp)
	{
		str[i]=temp%2;
		temp=temp/2;
	}
	return str;
}

int bin_to_dec(char* str)
{
	int i,d;
	int num=0;
	int l=strlen(str);
	for(i=l-1;i>=0;i--)
	{
		d=str[i]-48;
		num=num+pow(2,i)*d;
	}
	return num;
}