Xref: utzoo comp.sys.nsc.32k:826 alt.sys.pc532:87
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!elroy.jpl.nasa.gov!jarthur!bridge2!mips!daver!bungi.com!news
From: ron%hcr@uunet.UU.NET
Newsgroups: comp.sys.nsc.32k,alt.sys.pc532
Subject: A better CRC routine
Message-ID: <9005032242.AA12298@capri.COM>
Date: 3 May 90 22:42:30 GMT
Sender: news@daver.bungi.com
Distribution: comp
Lines: 189
Approved: news@daver.bungi.com

The following is a crc16 routine for the 32000 family,  note that
it is faster than the single bit loop version and the table used
fits into cache. The C code has been tested on a 386 and
a VAX. The results have also been compared to the vax CRC instruction
results. Give it a try.

CAUTION -
This is a true crc16 routine, it has been used for many years
on various communication protocols - it works.  The CCITT routine
posted is NOT a valid CCITT crc (it does not use an initial value
of 0xfff ...).  The interesting property of the crc16 routine is that
a buffer of zeros has a crc value of 0, this is NOT true for the
CCITT crc.

;
; crc16.s
;
; Declare all routines as exports
;
;
; ***	unsigned short crc16(out,buffer,size)
;	char *out;
;	char *buffer;
;	unsigned short size;
;		This routine returns the crc16 for 'buffer' of 'size'. 
;		If 'out' is non-zero, result is also stored there.
;	Registers:	r0 = result
;			r7 = buffer pointer
;			r6 = size remaining
;			r5,r4 intermediate results
;
crc16:
	enter	[r4,r5,r6,r7],0x00	; Enter frame
	movd	12(fp),r7		; Point to buffer
	movzwd	16(fp),r6		; Buffer size
	movd	0,r0			; start result
;
; buffer loop
;
crc_1:	movzbd	0(r7),r5		; Get next character
	xorb	r0,r5			; Xor low byte with previous
	movd	r5,r4			; Copy
	andb	0x0f,r5			; Extract low nibble
	movw	crc16l[r5:w],r5		; Table entry for low nibble
	andb	0xf0,r4			; Extract hi nibble
	lshb	-3,r4			; Index [w] to table
	xorw	crc16h[r4:b],r5		; Xor table entry for hi nibble
	lshw	-8,r0			; Old hi byte to low byte
	xorw	r5,r0			; Xor table entries
	addd	1,r7			; Update pointer
	acbw	-1,r6,crc_1		; Dec size and repeat
;
	cmpd	0,8(fp)			; Output pointer specified?
	beq	crc_2			; No
	movw	r0,0(8(fp))		; Yes -	save result there
crc_2:	exit	[r4,r5,r6,r7]		; Restore
	ret	0			; and return

;
; crc16 table: low and hi halves, each 16 words
;
	.align	4			; word align for speed
crc16l:	.word	0x0000,0xc0c1,0xc181,0x0140
	.word	0xc301,0x03c0,0x0280,0xc241
	.word	0xc601,0x06c0,0x0780,0xc741
	.word	0x0500,0xc5c1,0xc481,0x0440
crc16h:	.word	0x0000,0xcc01,0xd801,0x1400
	.word	0xf001,0x3c00,0x2800,0xe401
	.word	0xa001,0x6c00,0x7800,0xb401
	.word	0x5000,0x9c01,0x8801,0x4400


------------------------------

/* C version */
static int      crc();
int	crc_table();

/* crc16 - DDCMP and Bisync (16 bit)
 *	x^16 + x^15 + x^2 + 1
 */

#define TEST	1		/* set to 1 for testing */
#define SINGLE	0		/* single bit version */


/*	crc16 - crc16 routine
 *
 *	R.K. Irvine
 *
 *	This routine returns the crc16 for the buffer pointed
 *	to by "in" of size "size".
 *	crc16 is given by:  x^16 + x^15 + x^2 + 1
 */

unsigned short crc16_l[] = {
	0x0000,0xc0c1,0xc181,0x0140,
	0xc301,0x03c0,0x0280,0xc241,
	0xc601,0x06c0,0x0780,0xc741,
	0x0500,0xc5c1,0xc481,0x0440,
};

unsigned short crc16_h[] = {
	0x0000,0xcc01,0xd801,0x1400,
	0xf001,0x3c00,0x2800,0xe401,
	0xa001,0x6c00,0x7800,0xb401,
	0x5000,0x9c01,0x8801,0x4400,
};

unsigned short
crc16(in, size)
	unsigned char *in;
	int size;
{
	unsigned short	c, n, crc;

	crc = 0;
	while (size--) {	
		n = *in++ ^ crc;
		crc = crc16_l[n&0x0f] ^ crc16_h[(n>>4)&0x0f] ^ (crc>>8);
	}
	return(crc);
}

#if TEST
/* test routine */
main() {

	printf("CRC16 test routine\n");

	test("Hello world.", 0x33f9);
	test("12345678901234567890", 0x9b37);
	test("if else while case", 0xdb7f);

	printf("done\n");
}

test(s, n)
	unsigned char *s;
	int n;
{
	static t=0;
	int	r;

#if SINGLE	/* test with single bit version */
	r = crc_ok(s);
#else	/* test nibble version */
	r = crc16(s, strlen(s));
#endif

	printf("test %d: '%s' = %x; ", t++, s, r);
	if (r != n) {
		printf("BAD, should be %x\n", n);
	}
	else {
		printf("OK\n");
	}
}

/* single bit version of crc16 */

unsigned crc_byte(crc, new_ch)
register unsigned short crc;
int new_ch;
{
	register unsigned short bit;
	register int i;

	for (i=1; i <= 0x80; i<<=1) {

		bit = ((new_ch&i)?0x8000:0);
		if (crc & 1) bit ^= 0x8000;
		crc >>= 1;
		if (bit) crc ^= (int)(0x2001);
		crc |= bit;
  	}
	return crc;
}

crc_ok(p)
	char *p;
{
	unsigned crc = 0;
	while (*p) {
		crc = crc_byte(crc, *p++);
	}
	return(crc);
}
#endif