20.5 Arithmetic Coding 913 Individual characters in a message are coded or decoded by the routine arcode, which in turn uses the utility arcsum #include <stdio.h> #include <stdlib.h> #define NWK 20 #define JTRY(j,k,m)((long)((((double)(k))*((double)(j)))/((double)(m)))) This macro is used to calculate (k*j)/m without overflow.Program efficiency can be improved by substituting an assembly language routine that does integer multiply to a double register. typedef struct unsigned long *ilob,*iupb,*ncumfq,jdif,nc,minint,nch,ncum,nrad; arithcode; 83g void arcode(unsigned long *ich,unsigned char **codep,unsigned long *lcode, granted for (including unsigned long *lcd,int isign,arithcode *acode) Compress (isign=1)or decompress (isign =-1)the single character ich into or out of 11.800 the character array *codep[1..lcode],starting with byte *codep [lcd]and(if necessary) incrementing lcd so that,on return,lcd points to the first unused byte in *codep.Note that the structure acode contains both information on the code,and also state information on from NUMERICAL RECIPES I 18881892 the particular output being written into the array *codep.An initializing call with isign=0 is required before beginning any *codep array,whether for encoding or decoding.This is in addition to the initializing call to arcmak that is required to initialize the code itself.A call with ich=nch (as set in arcmak)has the reserved meaning "end of message." 9 void arcsum(unsigned long iin[],unsigned long iout ]unsigned long ja, int nwk,unsigned long nrad,unsigned long nc); ART void nrerror(char error_text[]); int j,ki Program unsigned long ihi,ja,jh,jl,m; if (!isign){ Initialize enough digits of the upper and lower bounds. acode->idifsacode->nrad-1; for (j=NWK;j>=1;j--){ acode->iupb[j]=acode->nrad-1; acode->ilob[j]=0; acode->nc=j; 188 if (acode->jdif acode->minint)return; Initialization complete OF SCIENTIFIC COMPUTING(ISBN acode->jdif=(acode->jdif+1)*acode->nrad-1; 1920 nrerror("NWK too small in arcode."); else 0621 1f(1s1gm>0){ If encoding,check for valid input character. if (*ich acode->nch)nrerror("bad ich in arcode."); Numerical Recipes -43108 else If decoding.locate the character ich by bisection. ja=(+codep)[*lcd]-acode->ilob[acode->nc]; for (j=acode->nc+1;j<=NWK;j++) (outside ja +acode->nrad; Software. ja +=((*codep)[*lcd+j-acode->nc]-acode->ilob[j]); ihi=acode->nch+1; Amer *ich=0; while (ihi-(*ich)>1){ m=(*ich+ih1)>>1; if (ja >JTRY(acode->jdif,acode->ncumfq[m+1],acode->ncum)) *ich=m: else ihi=m; if (*ich =acode->nch)return Detected end of message Following code is common for encoding and decoding.Convert character ich to a new subrange [ilob,iupb)20.5 Arithmetic Coding 913 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). Individual characters in a message are coded or decoded by the routine arcode, which in turn uses the utility arcsum. #include <stdio.h> #include <stdlib.h> #define NWK 20 #define JTRY(j,k,m) ((long)((((double)(k))*((double)(j)))/((double)(m)))) This macro is used to calculate (k*j)/m without overflow. Program efficiency can be improved by substituting an assembly language routine that does integer multiply to a double register. typedef struct { unsigned long *ilob,*iupb,*ncumfq,jdif,nc,minint,nch,ncum,nrad; } arithcode; void arcode(unsigned long *ich, unsigned char **codep, unsigned long *lcode, unsigned long *lcd, int isign, arithcode *acode) Compress (isign = 1) or decompress (isign = −1) the single character ich into or out of the character array *codep[1..lcode], starting with byte *codep[lcd] and (if necessary) incrementing lcd so that, on return, lcd points to the first unused byte in *codep. Note that the structure acode contains both information on the code, and also state information on the particular output being written into the array *codep. An initializing call with isign=0 is required before beginning any *codep array, whether for encoding or decoding. This is in addition to the initializing call to arcmak that is required to initialize the code itself. A call with ich=nch (as set in arcmak) has the reserved meaning “end of message.” { void arcsum(unsigned long iin[], unsigned long iout[], unsigned long ja, int nwk, unsigned long nrad, unsigned long nc); void nrerror(char error_text[]); int j,k; unsigned long ihi,ja,jh,jl,m; if (!isign) { Initialize enough digits of the upper and lower bounds. acode->jdif=acode->nrad-1; for (j=NWK;j>=1;j--) { acode->iupb[j]=acode->nrad-1; acode->ilob[j]=0; acode->nc=j; if (acode->jdif > acode->minint) return; Initialization complete. acode->jdif=(acode->jdif+1)*acode->nrad-1; } nrerror("NWK too small in arcode."); } else { if (isign > 0) { If encoding, check for valid input character. if (*ich > acode->nch) nrerror("bad ich in arcode."); } else { If decoding, locate the character ich by bisection. ja=(*codep)[*lcd]-acode->ilob[acode->nc]; for (j=acode->nc+1;j<=NWK;j++) { ja *= acode->nrad; ja += ((*codep)[*lcd+j-acode->nc]-acode->ilob[j]); } ihi=acode->nch+1; *ich=0; while (ihi-(*ich) > 1) { m=(*ich+ihi)>>1; if (ja >= JTRY(acode->jdif,acode->ncumfq[m+1],acode->ncum)) *ich=m; else ihi=m; } if (*ich == acode->nch) return; Detected end of message. } Following code is common for encoding and decoding. Convert character ich to a new subrange [ilob,iupb)