c20-3 (779625), страница 3
Текст из файла (страница 3)
If you set crc to theresult of the last call to icrc, this in effect appends the current input array to that ofthe previous call or calls. Use this feature, for example, to build up the CRC of awhole 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 tounderstand its operation: First look at the function icrc1. This incorporates oneinput character into a 16-bit CRC register. The only trick used is that character bitsare XORed into the most significant bits, eight at a time, instead of being fed intothe least significant bit, one bit at a time, at the time of the register shift.
This worksbecause XOR is associative and commutative — we can feed in character bits anytime before they will determine whether to zap with the generator polynomial. (Thedecimal constant 4129 has the generator’s bits in it.)20.3 Cyclic Redundancy and Other Checksums901if (!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 needto rewrite the routines given to work with a longer generating polynomial.
Forexample, 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 registergoes through unchanged.If you do not care about the M -consecutive bit property of the checksum, butrather only need a statistically random 32 bits, then you can use icrc as givenhere: Call it once with jrev = 1 to get 16 bits, and again with jrev = −1 to getanother 16 bits. The internal bit reversals make these two 16-bit CRCs in effecttotally independent of each other.Other Kinds of ChecksumsQuite 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 acomputer).
Check digits need to be proof against the kinds of highly structurederrors that humans tend to make, such as transposing consecutive digits. Wagner andPutter [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 thisone, uses the check equation10d1 + 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 acheck digit value of 10. Another popular scheme is the so-called “IBM check,” oftenSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).table). If jinit is negative, then crc is used on input to initialize the remainder register, ineffect (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.902Chapter 20.Less-Numerical Algorithmsused for account numbers (including, e.g., MasterCard).
Here, the check equation is2#d1 + d2 + 2#d3 + d4 + · · · = 0 (mod 10)(20.3.2)3a1 + 7a2 + a3 + 3a4 + 7a5 + a6 + 3a7 + 7a8 + a9 = 0 (mod 10) (20.3.3)The bar code put on many envelopes by the U.S. Postal Service is decoded byremoving the single tall marker bars at each end, and breaking the remaining barsinto 6 or 10 groups of five. In each group the five bars signify (from left to right)the values 7,4,2,1,0.
Exactly two of them will be tall. Their sum is the representeddigit, except that zero is represented as 7 + 4. The 5- or 9-digit Zip Code is followedby a check digit, with the check equationXdi = 0(mod 10)(20.3.4)None of these schemes is close to optimal. An elegant scheme due to Verhoeffis described in [7]. The underlying idea is to use the ten-element dihedral group D5 ,which corresponds to the symmetries of a pentagon, instead of the cyclic group ofthe integers modulo 10.
The check equation isa1 *f(a2 )*f 2 (a3 )* · · · *f n−1 (an ) = 0(20.3.5)where * is (noncommutative) multiplication in D5 , and f i denotes the ith iterationof a certain fixed permutation. Verhoeff’s method finds all single errors in a string,and all adjacent transpositions. It also finds about 95% of twin errors (aa → bb),jump transpositions (acb → bca), and jump twin errors (aca → bcb). Here is animplementation:int decchk(char string[], int n, char *ch)Decimal check digit computation or verification. Returns as ch a check digit for appendingto string[1..n], that is, for storing into string[n+1].
In this mode, ignore the returnedboolean (integer) value. If string[1..n] already ends with a check digit (string[n]), returns the function value true (1) if the check digit is valid, otherwise false (0). In this mode,ignore the returned value of ch. Note that string and ch contain ASCII characters corresponding to the digits 0-9, not byte values in that range. Other ASCII characters are allowed instring, and are ignored in calculating the check digit.{char c;int j,k=0,m=0;static int ip[10][8]={0,1,5,8,9,4,2,7,1,5, 8,9,4,2,7,0,2,7,0,1,5,8,9,4,3,6,3,6,3,6, 3,6,4,2,7,0,1,5,8,9, 5,8,9,4,2,7,0,1,6,3,6,3,6,3,6,3,7,0,1,5, 8,9,4,2,8,9,4,2,7,0, 1,5,9,4,2,7,0,1,5,8};static int ij[10][10]={0,1,2,3,4,5,6,7,8,9, 1,2,3,4,0,6,7,8,9,5,2,3,4,0,1,7,8,9,5,6, 3,4,0,1,2,8,9,5,6,7, 4,0,1,2,3,9,5,6,7,8,5,9,8,7,6,0,4,3,2,1, 6,5,9,8,7,1,0,4,3,2, 7,6,5,9,8,2,1,0,4,3,8,7,6,5,9,3,2,1,0,4, 9,8,7,6,5,4,3,2,1,0};Group multiplication and permutation tables.for (j=0;j<n;j++) {c=string[j];if (c >= 48 && c <= 57)Look at successive characters.Ignore everything except digits.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.
Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).where 2#d means, “multiply d by two and add the resulting decimal digits.” UnitedStates banks code checks with a 9-digit processing number whose check equation is20.4 Huffman Coding and Compression of Data903k=ij[k][ip[(c+2) % 10][7 & m++]];}for (j=0;j<=9;j++)Find which appended digit will check properly.if (!ij[k][ip[j][m & 7]]) break;*ch=j+48;Convert to ASCII.return k==0;}McNamara, J.E. 1982, Technical Aspects of Data Communication, 2nd ed.
(Bedford, MA: DigitalPress). [1]da Cruz, F. 1987, Kermit, A File Transfer Protocol (Bedford, MA: Digital Press). [2]Morse, G. 1986, Byte, vol. 11, pp. 115–124 (September). [3]LeVan, J. 1987, Byte, vol. 12, pp. 339–341 (November). [4]Sarwate, D.V. 1988, Communications of the ACM, vol. 31, pp. 1008–1013. [5]Griffiths, G., and Stones, G.C. 1987, Communications of the ACM, vol.
30, pp. 617–620. [6]Wagner, N.R., and Putter, P.S. 1989, Communications of the ACM, vol. 32, pp. 106–110. [7]20.4 Huffman Coding and Compression of DataA lossless data compression algorithm takes a string of symbols (typicallyASCII characters or bytes) and translates it reversibly into another string, one thatis on the average of shorter length. The words “on the average” are crucial; itis obvious that no reversible algorithm can make all strings shorter — there justaren’t enough short strings to be in one-to-one correspondence with longer strings.Compression algorithms are possible only when, on the input side, some strings, orsome input symbols, are more common than others.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
