900 Chapter 20.Less-Numerical Algorithms of characters from the input array and output CRC of icrc.You should not need to do any additional bit-reversal outside of icrc. The switch jinit has one additional use:When negative it causes the input value of the array crc to be used as initialization of the register.If you set crc to the result of the last call to icrc,this in effect appends the current input array to that of the previous call or calls.Use this feature,for example,to build up the CRC of a whole file a line at a time,without keeping the whole file in memory. The routine icrc is loosely based on the function in [4].Here is how to understand its operation:First look at the function icrc1.This incorporates one input character into a 16-bit CRC register.The only trick used is that character bits 8 are XORed into the most significant bits,eight at a time,instead of being fed into the least significant bit,one bit at a time,at the time of the register shift.This works because XOR is associative and commutative-we can feed in character bits any time before they will determine whether to zap with the generator polynomial.(The decimal constant 4129 has the generator's bits in it.) unsigned short icrc1(unsigned short crc,unsigned char onech) Given a remainder up to now,return the new CRC after one character is added.This routine is functionally equivalent to icrc(,,1,-1,1),but slower.It is used by icrc to initialize its table. 5.、5y Press. int 1: unsigned short ans=(crc onech <8); for(1=0;i<8;i+)[ Here is where 8 one-bit shifts,and some XORs with the 1f(ans&0x8000) generator polynomial,are done. ans=(ans<=1)-4129; else SCIENTIFIC ans <<1; return ans; to dir COMPUTING (ISBN 19891892 Now look at icrc.There are two parts to understand,how it builds a table when it initializes,and how it uses that table later on.Go back to thinking about a character's bits being shifted into the CRC register from the least significant end.The key observation is that while 8 bits are being shifted into the register's low end,all Fuurggoglrion the generator zapping is being determined by the bits already in the high end.Since Numerical Recipes 10621 43106 XOR is commutative and associative.all we need is a table of the result of all this zapping,for each of 256 possible high-bit configurations.Then we can play catch-up (outside and XOR an input character into the result of a lookup into this table.The only other 首 Software. content to icrc is the construction at initialization time of an 8-bit bit-reverse table from the 4-bit table stored in it,and the logic associated with doing the bit reversals. References [4-6]give further details on table-driven CRC computations. typedef unsigned char uchar; #define LOBYTE(x)((uchar)((x)&0xFF)) #define HIBYTE(x)((uchar)((x)>>8)) unsigned short icrc(unsigned short crc,unsigned char *bufptr, unsigned long len,short jinit,int jrev) Computes a 16-bit Cyclic Redundancy Check for a byte array bufptr [1..len],using any of several conventions as determined by the settings of jinit and jrev (see accompanying900 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). of characters from the input array and output CRC of icrc. You should not need to do any additional bit-reversal outside of icrc. The switch jinit has one additional use: When negative it causes the input value of the array crc to be used as initialization of the register. If you set crc to the result of the last call to icrc, this in effect appends the current input array to that of the previous call or calls. Use this feature, for example, to build up the CRC of a whole file a line at a time, without keeping the whole file in memory. The routine icrc is loosely based on the function in [4]. Here is how to understand its operation: First look at the function icrc1. This incorporates one input character into a 16-bit CRC register. The only trick used is that character bits are XORed into the most significant bits, eight at a time, instead of being fed into the least significant bit, one bit at a time, at the time of the register shift. This works because XOR is associative and commutative — we can feed in character bits any time before they will determine whether to zap with the generator polynomial. (The decimal constant 4129 has the generator’s bits in it.) unsigned short icrc1(unsigned short crc, unsigned char onech) Given a remainder up to now, return the new CRC after one character is added. This routine is functionally equivalent to icrc(,,1,-1,1), but slower. It is used by icrc to initialize its table. { int i; unsigned short ans=(crc ^ onech << 8); for (i=0;i<8;i++) { Here is where 8 one-bit shifts, and some XORs with the if (ans & 0x8000) generator polynomial, are done. ans = (ans <<= 1) ^ 4129; else ans <<= 1; } return ans; } Now look at icrc. There are two parts to understand, how it builds a table when it initializes, and how it uses that table later on. Go back to thinking about a character’s bits being shifted into the CRC register from the least significant end. The key observation is that while 8 bits are being shifted into the register’s low end, all the generator zapping is being determined by the bits already in the high end. Since XOR is commutative and associative, all we need is a table of the result of all this zapping, for each of 256 possible high-bit configurations. Then we can play catch-up and XOR an input character into the result of a lookup into this table. The only other content to icrc is the construction at initialization time of an 8-bit bit-reverse table from the 4-bit table stored in it, and the logic associated with doing the bit reversals. References [4-6] give further details on table-driven CRC computations. typedef unsigned char uchar; #define LOBYTE(x) ((uchar)((x) & 0xFF)) #define HIBYTE(x) ((uchar)((x) >> 8)) unsigned short icrc(unsigned short crc, unsigned char *bufptr, unsigned long len, short jinit, int jrev) Computes a 16-bit Cyclic Redundancy Check for a byte array bufptr[1..len], using any of several conventions as determined by the settings of jinit and jrev (see accompanying