/* ACMS_EXAMPLE.C */
/* Example main program to demonstrate arithmetic coding and decoding */
/* Ashok Popat 6/90 --- modified version of prog. given in thesis */
/*
* Copyright 1990 Massachusetts Institute of Technology
* All rights reserved.
*
* Permission to use, copy, or modify this software and its documentation
* for educational and research purposes only and without fee is hereby
* granted, provided that this copyright notice appear on all copies and
* supporting documentation. For any other uses of this software, in
* original or modified form, including but not limited to distribution
* in whole or in part, specific prior permission must be obtained from
* M.I.T. and the author. These programs shall not be used, rewritten,
* or adapted as the basis of a commercial software or hardware product
* without first obtaining appropriate licenses from M.I.T. M.I.T. makes
* no representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
#include
#include /* for log and pow */
#define MAXK 512 /* max allowable size of source alphabet */
#define MAXN 10000 /* max allowable length of source string */
#define MAXM 90000 /* max allowable length of codestring (be conservative) */
extern void encode(),decode(); /* routines we're trying to demonstrate */
long random();
double maxran;
double peakiness;
void main(argc,argv)
int argc;
char *argv[];
{
void gensource(); /* generates random source sequence according to probs*/
double entropy(); /* computes source entropy */
int strings_match(); /* to check for correct decoding */
double avelength; /* average number of bits per letter */
long nlet,nbits; /* length of source string and code string */
int alphsize; /* number of letters in source alphabet */
double diff;
static double probs[MAXK];
int sourcebuf[MAXN],codebuf[MAXM],destbuf[MAXN];
double totprob = 0.0;
int i;
if (argc != 3) {
fprintf(stderr,"usage: %s alphsize peakiness\n", argv[0]);
fprintf(stderr,"\twhere 2 <= alphsize < %d\n",MAXK);
fprintf(stderr,"\tand peakiness > 0\n",MAXK);
exit(-1);
}
sscanf(argv[1],"%d",&alphsize);
sscanf(argv[2],"%lf",&peakiness);
maxran = pow(2.0,31.0) - 1.0; /* max poss. val. of random() */
/* probabilties are random in this version --- change as desired */
/*
* for (i=0; iSMALLNUM ? log(x) : log(SMALLNUM))
double entropy(k,p)
int k;
double *p;
{
double sum = 0.0;
while (k-- > 0) sum -= *(p+k) * happylog(*(p+k));
return(sum/log(2.0));
}
#undef SMALLNUM
void gensource(buf,k,n,p)
double *p;
int *buf,k;
long n;
{
double ranvar,thresh[MAXK], invmaxran;
int *bufcopy;
int i;
/* divide unit interval into k segments, each corresponding to a
** different source letter, and each having a width equal to the
** probability of the corresponding source letter. Select a letter
** by generating a uniformly-distributed random number between
** 0 and 1, then finding the letter that corresponds to the segment
** that contains the random number. */
invmaxran = 1.0/maxran;
bufcopy = buf;
/* set up thresholds to be cum. prob of letters: */
thresh[0] = 0;
for (i=1;i 0) {
ranvar = ((double) random()) * invmaxran;
for (i=k-1;i>=0;i--) {
if (thresh[i] < ranvar) {
*bufcopy++ = i;
break;
}
}
}
}