acms_exa.c

ACMS压缩算法

/* 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 <stdio.h>
#include <math.h>  /* 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; i<alphsize; i++) {
*      probs[i] = ((double) random())/maxran;
*      totprob += probs[i];
*    }
*/

/*  probabilities have a discretized Laplacian distribution */
/*  reduce entropy by increasing peakiness */

  for (i=0; i<alphsize; i++) {
    diff = fabs((double) (i-alphsize/2));
    probs[i] = exp(-diff*peakiness);
    totprob += probs[i];
  }
  for (i=0; i<alphsize; i++) probs[i] /= totprob;


  nlet = 10000;

  /* fill up source buffer: */
  printf("generating source...\n");
  gensource(sourcebuf,alphsize,nlet,probs);

  /* encode source, putting resulting bits in codebuf, and set nbits: */
  printf("encoding...\n");
  encode(alphsize,probs,sourcebuf,nlet,16,15,codebuf,&nbits);

  avelength = ((double) nbits)/((double) nlet);  /* ave. per-letter length */

  printf("decoding...\n");
  /* decode, putting result in destbuf: */
  decode(alphsize,probs,destbuf,nlet,16,15,codebuf,nbits);

  printf("verifying...\n");
  /* verify results: */
  if (strings_match(nlet,sourcebuf,destbuf))
    printf("No errors.\n");
  else
    printf("Errors were found.\n");

  /* report performance: */
  printf("Entropy = %lf\nActual codebits per letter = %lf\n",
	 entropy(alphsize,probs),avelength);
}

int strings_match(n,a,b)
     long n;
     int *a,*b;
{
  long i;
  for (i=0;i<n;i++) {
    if (*(a+i) != *(b+i)) return(0);
  }
  return(1);
}

#define SMALLNUM 1.0e-14
#define happylog(x) ( x>SMALLNUM ? 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<k;i++) thresh[i] = thresh[i-1] + *(p+i-1);

  while (n-- > 0) {
    ranvar = ((double) random()) * invmaxran;
    for (i=k-1;i>=0;i--) {
      if (thresh[i] < ranvar) {
	*bufcopy++ = i;
	break;
      }
    }
  }
}