ron%hcr@uunet.UU.NET (05/04/90)
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 culberts@hplwbc.hpl.hp.com (Bruce Culbertson) (05/04/90)
When I implemented the monitor download command, I considered the various popular CRC codes. I chose the one I did because I thought it was compatible with both Minix and CCITT. CCITT is definitely the wave of the future -- the organizations behind it have far more clout than the people using CRC16. I am disappointed to hear that the Minix people blew it when they implemented their CRC -- that it is not really CCITT. My preference, however, is to try to convince them to fix their code and bring it into conformance. By the way, does anyone know what POSIX specifies for the "sum" command? Is there a POSIX "crc" command? I used a bit serial algorithm to save ROM space (no table required) and because download time was dominated by the serial port throughput. I like the small table size used by the posted CRC16 routine. Bruce Culbertson