908 Chapter 20.Less-Numerical Algorithms repeatedly to encode consecutive characters in a message,but must be preceded by a single initializing call to hufmak,which constructs hcode. void nrerror(char error_text)； int l,n; unsigned long k,nc; static unsigned long setbit [32]={0x1L,Ox2L,Ox4L,Ox8L,0x10L,0x20L, 0x40L,0x80L,0x100L,0x200L,0x400L,0x800L,0x1000L,0x2000L 0x4000L,0x8000L,0x10000L,0x20000L,0x40000L,0x80000L,0x100000L, 0x200000L,0x400000L,0x800000L,0x1000000L,0x2000000L,0x4000000L, 0x8000000L,0x10000000L,0x20000000L,0x40000000L,0x80000000L]; 5常 k=ich+1; Convert character range 0..nch-1 to array index range 1..nch. if (k hcode->nch II k 1)nrerror("ich out of range in hufenc.") for (n=hcode->ncod[k]-1;n>=0;n--,++(*nb)){ Loop over the bits in the stored 18881892 nc=(*nb>>3); Huffman code for ich. if (++nc >*lcode){ fprintf(stderr,"Reached the end of the 'code'array.\n"); fprintf(stderr,"Attempting to expand its size.\n"); *1code*=1.5; if ((*codep=(unsigned char *)realloc(*codep, RECIPES (unsigned)(*lcode*sizeof(unsigned char))))==NULL){ nrerror("Size expansion failed."); 1=(*nb)&7; Press. if (!1)(*codep)[nc]=0; Set appropriate bits in code. ART if (hcode->icod[k]setbit [n])(*codep)[nc]I=setbit[l]; 2 Programs 豆 Decoding a Huffman-encoded message is slightly more complicated.The IENTIFIC coding tree must be traversed from the top down,using up a variable number of bits: typedef struct MPUTING unsigned long *icod,*ncod,*left,*right,nch,nodemax; huffcode; 1992 (ISBN void hufdec(unsigned long *ich,unsigned char *code,unsigned long lcode, unsigned long *nb,huffcode *hcode) Starting at bit number nb in the character array code [1..lcode],use the Huffman code stored Numerical in the structure hcode to decode a single character (returned as ich in the range 0..nch-1) and increment nb appropriately.Repeated calls,starting with nb=0 will return successive ucti Recipes 431086 characters in a compressed message.The returned value ich=nch indicates end-of-message The structure hcode must already have been defined and allocated in your main program,and also filled by a call to hufmak. (outside f Software. long nc,node; North static unsigned char setbit [8]={Ox1,0x2,0x4,0x8,0x10,0x20,0x40,0x80}; node=hcode->nodemax; for(;;){ Set node to the top of the decoding tree,and loop nc=(*nb>>3); until a valid character is obtained. if (++nc lcode){ Ran out of input;with ich=nch indicating end of *ich=hcode->nch: message. return; node=(code [nc]&setbit[7 (*nb)++]? hcode->right [node]:hcode->left [node]); Branch left or right in tree,depending on its value. if (node <hcode->nch){If we reach a terminal node,we have a complete character and can return.908 Chapter 20. Less-Numerical Algorithms 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). repeatedly to encode consecutive characters in a message, but must be preceded by a single initializing call to hufmak, which constructs hcode. { void nrerror(char error_text[]); int l,n; unsigned long k,nc; static unsigned long setbit[32]={0x1L,0x2L,0x4L,0x8L,0x10L,0x20L, 0x40L,0x80L,0x100L,0x200L,0x400L,0x800L,0x1000L,0x2000L, 0x4000L,0x8000L,0x10000L,0x20000L,0x40000L,0x80000L,0x100000L, 0x200000L,0x400000L,0x800000L,0x1000000L,0x2000000L,0x4000000L, 0x8000000L,0x10000000L,0x20000000L,0x40000000L,0x80000000L}; k=ich+1; Convert character range 0..nch-1 to array index range 1..nch. if (k > hcode->nch || k < 1) nrerror("ich out of range in hufenc."); for (n=hcode->ncod[k]-1;n>=0;n--,++(*nb)) { Loop over the bits in the stored nc=(*nb >> 3); Huffman code for ich. if (++nc >= *lcode) { fprintf(stderr,"Reached the end of the ’code’ array.\n"); fprintf(stderr,"Attempting to expand its size.\n"); *lcode *= 1.5; if ((*codep=(unsigned char *)realloc(*codep, (unsigned)(*lcode*sizeof(unsigned char)))) == NULL) { nrerror("Size expansion failed."); } } l=(*nb) & 7; if (!l) (*codep)[nc]=0; Set appropriate bits in code. if (hcode->icod[k] & setbit[n]) (*codep)[nc] |= setbit[l]; } } Decoding a Huffman-encoded message is slightly more complicated. The coding tree must be traversed from the top down, using up a variable number of bits: typedef struct { unsigned long *icod,*ncod,*left,*right,nch,nodemax; } huffcode; void hufdec(unsigned long *ich, unsigned char *code, unsigned long lcode, unsigned long *nb, huffcode *hcode) Starting at bit number nb in the character array code[1..lcode], use the Huffman code stored in the structure hcode to decode a single character (returned as ich in the range 0..nch-1) and increment nb appropriately. Repeated calls, starting with nb = 0 will return successive characters in a compressed message. The returned value ich=nch indicates end-of-message. The structure hcode must already have been defined and allocated in your main program, and also filled by a call to hufmak. { long nc,node; static unsigned char setbit[8]={0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80}; node=hcode->nodemax; for (;;) { Set node to the top of the decoding tree, and loop nc=(*nb >> 3); until a valid character is obtained. if (++nc > lcode) { Ran out of input; with ich=nch indicating end of *ich=hcode->nch; message. return; } node=(code[nc] & setbit[7 & (*nb)++] ? hcode->right[node] : hcode->left[node]); Branch left or right in tree, depending on its value. if (node <= hcode->nch) { If we reach a terminal node, we have a complete character and can return