🚀 go-pugleaf

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)