20.3 Cyclic Redundancy and Other Checksums 901 table).If jinit is negative,then crc is used on input to initialize the remainder register,in effect (for crc set to the last returned value)concatenating bufptr to the previous call. unsigned short icrc1(unsigned short crc,unsigned char onech); static unsigned short icrctb[256],init-0; static uchar rchr[256]; unsigned short j,cword=crc; stat1 c uchar1t[16]=0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]; Table of 4-bit bit-reverses. if (!init){ Do we need to initialize tables? 1n1t=1· for(j=0;j<=255;j+)[ The two tables are:CRCs of all characters,and bit-reverses of all characters. icrctb[j]=icrc1(j <8,(uchar)0); rchr[j]=(uchar)(it[i&OxF]<4 I it[i >4]); NUMERI if (jinit >=0)cword=((uchar)jinit)I (((uchar)jinit)<<8); ICAL Initialize the remainder register. else if (jrev 0)cword=rchr[HIBYTE(cword)]I rchr[LOBYTE(cword)]<8; If not initializing,do we reverse the register? for (j=1;j<=len;i++) Main loop over the characters in the array. cword=icrctb[(jrev 0 rchr[bufptr[j]] 令 bufptr[j])HIBYTE(cword)]LOBYTE(cword)<<8; return (jrev >=0 cword rchr [HIBYTE(cword)]I rchr[LOBYTE(cword)]<8); Do we need to reverse the output? 今 What if you need a 32-bit checksum?For a true 32-bit CRC,you will need R国是。A to rewrite the routines given to work with a longer generating polynomial.For example,32+5++++1is primitive modulo 2,and has nonleading, nonzero bits only in its least significant byte (which makes for some simplification). The idea of table lookup on only the most significant byte of the CRC register goes through unchanged. If you do not care about the M-consecutive bit property of the checksum,but rather only need a statistically random 32 bits,then you can use icrc as given here:Call it once with jrev =1 to get 16 bits,and again with jrev =-1 to get another 16 bits.The internal bit reversals make these two 16-bit CRCs in effect totally independent of each other 指、 Numerica 10621 43106 Other Kinds of Checksums Quite different from CRCs are the various techniques used to append a decimal "check digit"to numbers that are handled by human beings (e.g.,typed into a North computer).Check digits need to be proof against the kinds of highly structured errors that humans tend to make,such as transposing consecutive digits.Wagner and Putter [7]give an interesting introduction to this subject,including specific algorithms. Checksums now in widespread use vary from fair to poor.The 10-digit ISBN (International Standard Book Number)that you find on most books,including this one,uses the check equation 10d1+9d2+8d3+.·+2dg+d10=0(mod11) (20.3.1) where dio is the right-hand check digit.The character"X"is used to represent a check digit value of 10.Another popular scheme is the so-called"IBM check,"often20.3 Cyclic Redundancy and Other Checksums 901 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). table). If jinit is negative, then crc is used on input to initialize the remainder register, in effect (for crc set to the last returned value) concatenating bufptr to the previous call. { unsigned short icrc1(unsigned short crc, unsigned char onech); static unsigned short icrctb[256],init=0; static uchar rchr[256]; unsigned short j,cword=crc; static uchar it[16]={0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15}; Table of 4-bit bit-reverses. if (!init) { Do we need to initialize tables? init=1; for (j=0;j<=255;j++) { The two tables are: CRCs of all characters, and bit-reverses of all characters. icrctb[j]=icrc1(j << 8,(uchar)0); rchr[j]=(uchar)(it[j & 0xF] << 4 | it[j >> 4]); } } if (jinit >= 0) cword=((uchar) jinit) | (((uchar) jinit) << 8); Initialize the remainder register. else if (jrev < 0) cword=rchr[HIBYTE(cword)] | rchr[LOBYTE(cword)] << 8; If not initializing, do we reverse the register? for (j=1;j<=len;j++) Main loop over the characters in the array. cword=icrctb[(jrev < 0 ? rchr[bufptr[j]] : bufptr[j]) ^ HIBYTE(cword)] ^ LOBYTE(cword) << 8; return (jrev >= 0 ? cword : rchr[HIBYTE(cword)] | rchr[LOBYTE(cword)] << 8); Do we need to reverse the output? } What if you need a 32-bit checksum? For a true 32-bit CRC, you will need to rewrite the routines given to work with a longer generating polynomial. For example, x32 +x7 +x5 +x3 +x2 +x+ 1 is primitive modulo 2, and has nonleading, nonzero bits only in its least significant byte (which makes for some simplification). The idea of table lookup on only the most significant byte of the CRC register goes through unchanged. If you do not care about the M-consecutive bit property of the checksum, but rather only need a statistically random 32 bits, then you can use icrc as given here: Call it once with jrev = 1 to get 16 bits, and again with jrev = −1 to get another 16 bits. The internal bit reversals make these two 16-bit CRCs in effect totally independent of each other. Other Kinds of Checksums Quite different from CRCs are the various techniques used to append a decimal “check digit” to numbers that are handled by human beings (e.g., typed into a computer). Check digits need to be proof against the kinds of highly structured errors that humans tend to make, such as transposing consecutive digits. Wagner and Putter [7] give an interesting introduction to this subject,including specific algorithms. Checksums now in widespread use vary from fair to poor. The 10-digit ISBN (International Standard Book Number) that you find on most books, including this one, uses the check equation 10d1 + 9d2 + 8d3 + ··· + 2d9 + d10 = 0 (mod 11) (20.3.1) where d10 is the right-hand check digit. The character “X” is used to represent a check digit value of 10. Another popular scheme is the so-called “IBM check,” often