djones@megatest.UUCP (Dave Jones) (10/31/90)
Here's the shar-file for the previous posting about CRC-16.
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
#
# Contents: readme crc-orig.c crc-test.c string_crc16.c example_output
#
# Wrapped by djones@goofy on Tue Oct 30 17:02:07 1990
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f readme -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"readme\"
else
echo shar: Extracting \"readme\" \(2507 characters\)
sed "s/^X//" >readme <<'END_OF_readme'
X
XRecently, in connection with the topic of hashing, Ron Irvine
Xposted a C algorithm for calculating the CRC-16 number for
Xa null-terminated string. I decided to grab it and put it
Xin my utilities library. His routine was based on two sixteen-entry
Xtables, because, he said, they would fit in cache. Well one
Xmachine I use has a much larger cache than that, and the other
Xhas none, so I decided just for the fun of it to convert the algorithm
Xto one based on one 256-entry table. I did that, and testing
Xhas verified that it produces the same results.
X
XNow then, for purposes of documentation, and to verify the original
Xalgorithm, (and for my own education I guess), I decided to figure
Xout what the thing actually does. I borrowed a book, _Computer Networks,
XSecond Edition_, by Andrew S. Tanenbaum, (Simon & Schuster) and dug
Xin. I coded up the algorithm they gave, using the example on page
X210, fig. 4-7.(*) My code printed out intermediate results exactly
Xmatching those in the example. So far so good. Now I changed the
Xtwo constants that in theory should change the example check-sum into the
XCRC-16 checksum. The result was that I got different numbers from
Xmy algorithm than from the posted one. Could this be because of some
XBig-endian/Little-Endian kind of disagreement? Does the posted algorithm
Xin effect shift the bits out least-significant bit first, for example?
XAlso the book specifies that the input is first tagged at the end with
X16 zero-bits before doing the calculation. Does the algorithm published
Xon the net effectively do that? It does not appear to, but I confess I
Xhave not yet figured out why the posted algorithm does anything similar
Xto what the book describes.
X
XI guess what I am asking for is the "official" definition of
Xa CRC-16 checksum as it applies to byte-streams rather than bit-streams,
Xand why I don't get the same numbers that the posted algorithm gets.
X
XIn another posting, you'll find a shar of the files under discussion
Xhere, including the "bit-shifting" toy algorithm based on what I
Xread in the book.
X
X
X(*) Actually I had to change it a little, because the algorithm described
X was obviously wrong. It says, "A divisor is said to 'go into'
X a dividend if the dividend has as many bits as the divisor."
X I interpreted that to mean instead, "if the dividend and divisor have
X the same base-two log," which is consistent with the example,
X and with the statement that the algorithm can be implemented with
X "a simple shift register circuit".
X
END_OF_readme
if test 2507 -ne `wc -c <readme`; then
echo shar: \"readme\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f crc-orig.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"crc-orig.c\"
else
echo shar: Extracting \"crc-orig.c\" \(2098 characters\)
sed "s/^X//" >crc-orig.c <<'END_OF_crc-orig.c'
X#ifdef COMMENTED_OUT
X
XPath: megatest!decwrl!uunet!attcan!ncrcan!scocan!ron
XFrom: ron@sco.COM (Ron Irvine)
XNewsgroups: comp.lang.c
XSubject: hash function for text in C
XMessage-ID: <1990Oct19.165408.27856@sco.COM>
XDate: 19 Oct 90 20:54:08 GMT
XReply-To: ron@sco.COM (Ron Irvine)
XOrganization: SCO Canada, Inc. (formerly HCR Corporation)
XLines: 49
X
XI have used many hash functions. Each one has advantages
Xand disadvantages. Here is a powerful but simple one.
XIt simply does a crc16 on the character string. The crc16 is
Xa great hash function since it is designed to produce a
Xunique code for different character strings. So for "reasonable"
Xtext it gives a good distribution of hash numbers (a big problem
Xto solve in general). The crc16 function I list below uses nibbles
Xto build the crc from each byte, this is faster than a bit by bit and
Xless room than a 256 entry table needed for a byte by byte (fits
Xin cache). So, it is fast (no multiply, just shifts and masks),
Xwell behaved and simple. If you have a VAX you could even use the
X"crc" instruction instead of the crc16 function - what a CISC.
XTo use, do a crc16 on the string and the truncate the 16 bit
Xresult to the size you need (this should be a power of 2).
X
X#endif COMMENTED_OUT
X
X/* crc16 - crc16 routine
X *
X * R.K. Irvine
X *
X * This routine returns the crc16 for the string pointed
X * to by "in".
X * crc16 is given by: x^16 + x^15 + x^2 + 1
X */
Xunsigned short
Xcrc16(in)
X register char *in;
X {
X register unsigned int n, crc;
X
X static unsigned short crc16l[] = {
X 0x0000,0xc0c1,0xc181,0x0140,
X 0xc301,0x03c0,0x0280,0xc241,
X 0xc601,0x06c0,0x0780,0xc741,
X 0x0500,0xc5c1,0xc481,0x0440,
X };
X
X static unsigned short crc16h[] = {
X 0x0000,0xcc01,0xd801,0x1400,
X 0xf001,0x3c00,0x2800,0xe401,
X 0xa001,0x6c00,0x7800,0xb401,
X 0x5000,0x9c01,0x8801,0x4400,
X };
X
X crc = 0;
X while (n = (unsigned char)(*in++)) {
X n ^= crc;
X crc = crc16l[n&0x0f] ^ crc16h[(n>>4)&0x0f] ^ (crc>>8);
X }
X return(crc);
X}
X
X
Xmain()
X{
X char ch[2];
X int i;
X ch[1] = 0;
X for(i = 0; i < 16; i++) {
X ch[0] = i;
X printf("0x%4.4x\n", crc16(ch));
X }
X}
END_OF_crc-orig.c
if test 2098 -ne `wc -c <crc-orig.c`; then
echo shar: \"crc-orig.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f crc-test.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"crc-test.c\"
else
echo shar: Extracting \"crc-test.c\" \(1901 characters\)
sed "s/^X//" >crc-test.c <<'END_OF_crc-test.c'
X/*
X * This file implements the algorithm described in _Computer Networks,
X * second edition_, Andrew S. Tannenbaum, Simon & Schuster, pp 208-212.
X * If #define example, you get the check sum of fig. 4-7, p. 210.
X * If not, you get (what should be) the CRC-16 checksum. The algorithm
X * works on a single 32-bit integer. (If your machine does not have
X * 32-bit longs, forget all of this.)
X */
X
X#if !defined(example)
X
X /*
X * crc-16 polynomial = x**16 + x**15 + x**2 + 1
X */
X
X# define generator ((1<<16)|(1<<15)|(1<<2)|(1<<0))
X# define degree 16
X
X#else
X
X /* Example from "Computer Networks" -- Andrew S. Tannenbaum. p 210 , fig 4-7 */
X# define generator ((1<<4)|(1<<1)|(1<<0))
X# define degree 4
X
X bits(i) /* for printing the intermediate results of the example */
X long i;
X {
X int j = 32;
X while(j--) {
X putchar(i < 0 ? '1' : '0');
X i = i << 1;
X }
X }
X
X#endif
X
X
X/*
X * calc crc-16 of a (32-bit) integer
X */
Xcrc_16(frame)
X long frame;
X{
X int times = 32; /* bits per int */
X long remainder = 0;
X long dividend = frame << degree;
X
X while(times--) {
X
X /* "Bring down" next bit into the remainder...
X * That is, shift top bit of dividend onto the bottom
X * of the remainder
X */
X
X remainder = (remainder << 1) ^ (0!=(dividend & (1<<31)));
X dividend = dividend << 1;
X
X /* If the generator "goes into" the remainder, "subtract" it. */
X if(remainder & (1<<degree))
X remainder ^= generator; /* "subtract" generator from remainder. */
X
X#ifdef example
X bits(dividend); putchar(' '); bits(remainder); putchar('\n');
X#else
X printf("%x\n", remainder);
X#endif
X
X }
X
X return remainder;
X}
X
Xmain(argc, argv)
X char **argv;
X{
X int i;
X
X#ifdef example
X bits(crc_16(0x35b)); /* 1101011011 as per example */
X putchar('\n');
X#else
X printf("%x\n", crc_16(1)); /* does it match crc_tbl[1] in string_crc16.c ? No. */
X#endif
X
X}
END_OF_crc-test.c
if test 1901 -ne `wc -c <crc-test.c`; then
echo shar: \"crc-test.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f string_crc16.c -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"string_crc16.c\"
else
echo shar: Extracting \"string_crc16.c\" \(2838 characters\)
sed "s/^X//" >string_crc16.c <<'END_OF_string_crc16.c'
X/*
X * unsigned short string_crc16(str)
X * unsigned char *str;
X *
X * Return the 16 bit crc number for a null-terminated string of chars.
X * Uses a table of 256 entries.
X */
X
X
Xunsigned short
Xstring_crc16(in)
X register char *in;
X{
X static unsigned short crc_tbl [256] = {
X 0x0000, 0xc0c1, 0xc181, 0x0140, 0xc301, 0x03c0, 0x0280, 0xc241,
X 0xc601, 0x06c0, 0x0780, 0xc741, 0x0500, 0xc5c1, 0xc481, 0x0440,
X 0xcc01, 0x0cc0, 0x0d80, 0xcd41, 0x0f00, 0xcfc1, 0xce81, 0x0e40,
X 0x0a00, 0xcac1, 0xcb81, 0x0b40, 0xc901, 0x09c0, 0x0880, 0xc841,
X 0xd801, 0x18c0, 0x1980, 0xd941, 0x1b00, 0xdbc1, 0xda81, 0x1a40,
X 0x1e00, 0xdec1, 0xdf81, 0x1f40, 0xdd01, 0x1dc0, 0x1c80, 0xdc41,
X 0x1400, 0xd4c1, 0xd581, 0x1540, 0xd701, 0x17c0, 0x1680, 0xd641,
X 0xd201, 0x12c0, 0x1380, 0xd341, 0x1100, 0xd1c1, 0xd081, 0x1040,
X 0xf001, 0x30c0, 0x3180, 0xf141, 0x3300, 0xf3c1, 0xf281, 0x3240,
X 0x3600, 0xf6c1, 0xf781, 0x3740, 0xf501, 0x35c0, 0x3480, 0xf441,
X 0x3c00, 0xfcc1, 0xfd81, 0x3d40, 0xff01, 0x3fc0, 0x3e80, 0xfe41,
X 0xfa01, 0x3ac0, 0x3b80, 0xfb41, 0x3900, 0xf9c1, 0xf881, 0x3840,
X 0x2800, 0xe8c1, 0xe981, 0x2940, 0xeb01, 0x2bc0, 0x2a80, 0xea41,
X 0xee01, 0x2ec0, 0x2f80, 0xef41, 0x2d00, 0xedc1, 0xec81, 0x2c40,
X 0xe401, 0x24c0, 0x2580, 0xe541, 0x2700, 0xe7c1, 0xe681, 0x2640,
X 0x2200, 0xe2c1, 0xe381, 0x2340, 0xe101, 0x21c0, 0x2080, 0xe041,
X 0xa001, 0x60c0, 0x6180, 0xa141, 0x6300, 0xa3c1, 0xa281, 0x6240,
X 0x6600, 0xa6c1, 0xa781, 0x6740, 0xa501, 0x65c0, 0x6480, 0xa441,
X 0x6c00, 0xacc1, 0xad81, 0x6d40, 0xaf01, 0x6fc0, 0x6e80, 0xae41,
X 0xaa01, 0x6ac0, 0x6b80, 0xab41, 0x6900, 0xa9c1, 0xa881, 0x6840,
X 0x7800, 0xb8c1, 0xb981, 0x7940, 0xbb01, 0x7bc0, 0x7a80, 0xba41,
X 0xbe01, 0x7ec0, 0x7f80, 0xbf41, 0x7d00, 0xbdc1, 0xbc81, 0x7c40,
X 0xb401, 0x74c0, 0x7580, 0xb541, 0x7700, 0xb7c1, 0xb681, 0x7640,
X 0x7200, 0xb2c1, 0xb381, 0x7340, 0xb101, 0x71c0, 0x7080, 0xb041,
X 0x5000, 0x90c1, 0x9181, 0x5140, 0x9301, 0x53c0, 0x5280, 0x9241,
X 0x9601, 0x56c0, 0x5780, 0x9741, 0x5500, 0x95c1, 0x9481, 0x5440,
X 0x9c01, 0x5cc0, 0x5d80, 0x9d41, 0x5f00, 0x9fc1, 0x9e81, 0x5e40,
X 0x5a00, 0x9ac1, 0x9b81, 0x5b40, 0x9901, 0x59c0, 0x5880, 0x9841,
X 0x8801, 0x48c0, 0x4980, 0x8941, 0x4b00, 0x8bc1, 0x8a81, 0x4a40,
X 0x4e00, 0x8ec1, 0x8f81, 0x4f40, 0x8d01, 0x4dc0, 0x4c80, 0x8c41,
X 0x4400, 0x84c1, 0x8581, 0x4540, 0x8701, 0x47c0, 0x4680, 0x8641,
X 0x8201, 0x42c0, 0x4380, 0x8341, 0x4100, 0x81c1, 0x8081, 0x4040
X };
X
X register int n, crc;
X
X crc = 0;
X while (n = (unsigned char)(*in++)) {
X n ^= crc;
X crc = crc_tbl[n & 0xff] ^ (crc>>8);
X }
X return(crc);
X}
END_OF_string_crc16.c
if test 2838 -ne `wc -c <string_crc16.c`; then
echo shar: \"string_crc16.c\" unpacked with wrong size!
fi
# end of overwriting check
fi
if test -f example_output -a "${1}" != "-c" ; then
echo shar: Will not over-write existing file \"example_output\"
else
echo shar: Extracting \"example_output\" \(2145 characters\)
sed "s/^X//" >example_output <<'END_OF_example_output'
X00000000000000000110101101100000 00000000000000000000000000000000
X00000000000000001101011011000000 00000000000000000000000000000000
X00000000000000011010110110000000 00000000000000000000000000000000
X00000000000000110101101100000000 00000000000000000000000000000000
X00000000000001101011011000000000 00000000000000000000000000000000
X00000000000011010110110000000000 00000000000000000000000000000000
X00000000000110101101100000000000 00000000000000000000000000000000
X00000000001101011011000000000000 00000000000000000000000000000000
X00000000011010110110000000000000 00000000000000000000000000000000
X00000000110101101100000000000000 00000000000000000000000000000000
X00000001101011011000000000000000 00000000000000000000000000000000
X00000011010110110000000000000000 00000000000000000000000000000000
X00000110101101100000000000000000 00000000000000000000000000000000
X00001101011011000000000000000000 00000000000000000000000000000000
X00011010110110000000000000000000 00000000000000000000000000000000
X00110101101100000000000000000000 00000000000000000000000000000000
X01101011011000000000000000000000 00000000000000000000000000000000
X11010110110000000000000000000000 00000000000000000000000000000000
X10101101100000000000000000000000 00000000000000000000000000000001
X01011011000000000000000000000000 00000000000000000000000000000011
X10110110000000000000000000000000 00000000000000000000000000000110
X01101100000000000000000000000000 00000000000000000000000000001101
X11011000000000000000000000000000 00000000000000000000000000001001
X10110000000000000000000000000000 00000000000000000000000000000000
X01100000000000000000000000000000 00000000000000000000000000000001
X11000000000000000000000000000000 00000000000000000000000000000010
X10000000000000000000000000000000 00000000000000000000000000000101
X00000000000000000000000000000000 00000000000000000000000000001011
X00000000000000000000000000000000 00000000000000000000000000000101
X00000000000000000000000000000000 00000000000000000000000000001010
X00000000000000000000000000000000 00000000000000000000000000000111
X00000000000000000000000000000000 00000000000000000000000000001110
X00000000000000000000000000001110
END_OF_example_output
if test 2145 -ne `wc -c <example_output`; then
echo shar: \"example_output\" unpacked with wrong size!
fi
# end of overwriting check
fi
echo shar: End of shell archive.
exit 0