gus@plains.UUCP (jim gustafson) (07/17/90)
In article <144@qmsseq.imagen.com> pipkins@imagen.com (Jeff Pipkins) writes: >In article <1990Jul13.013921.1320@cec1.wustl.edu> jma7759@cec1.wustl.edu (James Michael Anderson) writes: >>In article <269bd6d3-120comp.sys.ibm.pc.programmer@vpnet.chi.il.us> cgordon@vpnet.chi.il.us (Gordon Hlavenka) writes: >>> >>>I need to generate the CCITT CRC16 for an array of bytes. I know there's a >>>sexy little algorithm which does it in a dozen lines or so, without lookup >>>tables. It uses SHL's and XOR's... >> >> Hey! I'm looking for the same; however, I have a need for the FASTEST >>version possible (lookup tables are OK). Anybody got any suggestions >>for this one? I belive that there exists (once again) an algorithm that >>uses a table of "pre-shifted" values... > >There is a book called "C Programmer's Guide to NetBIOS" by >David Schwaderer (sp?). It has the best treatment of CRC's for >software types that I have seen anywhere. It explains several >different kinds of CRC's, including CRC-16, CRC-32, and others. >It has both bit-at-a-time algorithms (less space, more time), and >table lookup algorithms (more space, less time). Even if you >couldn't care less about NetBIOS, if you are at all interested >in CRC's, this book is a must. > >--Jeff Pipkins >pipkins@imagen.com >Disclaimer: "I've already told you more than I know!" Ok, here is an implementation based on... Communications of the Association for Computing Machinery. Enjoy! file: crc16.c /* * crc16.c -- Dr. R. Gammill (gammill@plains.nodak.edu) * CRC routine from CACM August 1988, p. 1008 */ #include <stdio.h> char *t = { "THE, QUICK, BROWN, FOX, 0123456789abcdefghijklmopqrsty" }; int cnst[2] = { 0x1021, 0x8005 }; /* CCITT16 and CRC16 */ main() { int i, j, k, m, n; k = strlen(t); for(n=0; n<2; n++) { setab(cnst[n]); i = tabcrc(t,k,0); /* reverse bytes of CRC for PC*/ m = ((i&0xff)<<8) | ((i>>8)&0xff); j = tabcrc(&m,2,i); printf("CRC = %04x CRC including check bytes = %04x\n",i,j); } } unsigned short int table[256]; tabcrc(ptr, count, oldcrc) unsigned char *ptr; /* bytewise CACM table version */ { /*register*/ union { /* TC barfs on register union, MSC ok */ unsigned short i; struct { unsigned char lo, hi; } byte; } wrk, crc; for(crc.i = oldcrc; count--; ) { wrk.byte.lo = 0; wrk.byte.hi = crc.byte.lo; crc.i = wrk.i ^ table[crc.byte.hi ^ *ptr++]; } return(crc.i); } setab(ctrl) /* initialize the table */ { register unsigned int crc, i, j; for(j = 0; j<256; j++) { crc = (j << 8); for(i=0; i<8; i++) if(crc & 0x8000) crc = (crc << 1) ^ ctrl; else crc <<= 1; table[j] = crc; } } -- Jim. -- Jim Gustafson gus@plains.nodak.edu uunet!plains!gus (UUCP) gus@plains (Bitnet)