list p=p18f452 #include p18f452.inc cblock 0 crc32:4 temp endc crc_hi EQU crc32+0 crc_mh EQU crc32+1 crc_ml EQU crc32+2 crc_lo EQU crc32+3 org 0 bra start ;============================================================= ; ; CRC-32 for 18fxxx PIC's ; ; 25JUL03 T. Scott Dattalo ; ; References ; 1) http://www.repairfaq.org/filipg/LINK/F_crc_v3.html ; 2) http://rcswww.urz.tu-dresden.de/~sr21/crc.html ; ; crc-32 ; ; This is an implementation of the 32-bit CRC algorithm based ; on the polynomial 04c11db7. According to reference (1), this ; CRC is used in Ethernet and PKZIP. Reference (2) implements ; this algorithm several different ways in C - crctester.c. The ; algorithm(s) in this PIC implementation extend those in reference (2). ; ; The first extension involves two lookup tables each 16 words long. ; It starts by examining the 256-element table created by the function ; generate_crc_table. If you write the 256-element as a 16 by 16 ; table, then the first row and column are: ; ; row 0 col 0 ; 00000000 00000000 ; 77073096 1db71064 ; ee0e612c 3b6e20c8 ; 990951ba 26d930ac ; 076dc419 76dc4190 ; 706af48f 6b6b51f4 ; e963a535 4db26158 ; 9e6495a3 5005713c ; 0edb8832 edb88320 ; 79dcb8a4 f00f9344 ; e0d5e91e d6d6a3e8 ; 97d2d988 cb61b38c ; 09b64c2b 9b64c2b0 ; 7eb17cbd 86d3d2d4 ; e7b82d07 a00ae278 ; 90bf1d91 bdbdf21c ; ; Here's C-function that implements the CRC-32 algorithm with these ; two arrays: ; ; unsigned long crcSmalltablefast (unsigned char* p, unsigned long len) ; { ; ; // fast lookup table algorithm without augmented zero bytes, e.g. used in pkzip. ; // only usable with polynom orders of 8, 16, 24 or 32. ; ; unsigned long crc = crcinit_direct; ; unsigned long i; ; ; if (refin) ; crc = reflect(crc, order); ; ; if (!refin) ; while (len--) { ; i = ((crc >> (order-8)) & 0xff) ^ *p++; ; crc = (crc << 8) ^ crcrow0[i&0x0f] ^ crccol0[i>>4]; ; } ; else ; while (len--) { ; i = (crc & 0xff) ^ *p++; ; crc = (crc >> 8) ^ crcrow0[i&0x0f] ^ crccol0[i>>4]; ; } ; ; if (refout^refin) ; crc = reflect(crc, order); ; ; crc^= crcxor; ; crc&= crcmask; ; ; return(crc); ; } ; ; ; The next optimization is obtain by examining the patterns that ; exist in the 16-element arrays. Notice for example, that: ; crccol0[3] = crccol0[2] ^ crccol0[1]. ; In general, if the index into the array is written as a bit ; pattern: i = (abcd) then: ; crccol0[i] = crccol0[abcd] ; = crccol0[a000] ^ crccol0[0b00] ^ crccol0[00c0] ^ crccol0[000d] ; ; The same is true for crcrow0. Since it's possible to build the 16 elements ; from just 4 elements, then the two arrays can be reduced from 32 elemetns ; to just 8. Re-write this as a single array: ; ; 77073096 ; ee0e612c ; 076dc419 ; 0edb8832 ; 1db71064 ; 3b6e20c8 ; 76dc4190 ; edb88320 ; ; And then the CRC-32 can be computed like so: ; ; ; unsigned long crcbitbybit_2(unsigned char* p, unsigned long len) ; { ; ; unsigned long i; ; unsigned long crc = crcinit_direct; ; unsigned long u,v; ; ; if (refin) ; crc = reflect(crc, order); ; ; ; if(!refin) { ; ; ; } else ; while (len--) { ; i = (crc & 0xff) ^ *p++; ; crc >>= 8; ; ; if(i & 0x01) ; crc ^= 0x77073096; ; ; if(i & 0x02) ; crc ^= 0xee0e612c; ; ; if(i & 0x04) ; crc ^= 0x076dc419; ; ; if(i & 0x08) ; crc ^= 0x0edb8832; ; ; if(i & 0x10) ; crc ^= 0x1db71064; ; ; if(i & 0x20) ; crc ^= 0x3b6e20c8; ; ; if(i & 0x40) ; crc ^= 0x76dc4190; ; ; if(i & 0x80) ; crc ^= 0xedb88320; ; ; } ; ; crc^= crcxor; ; crc&= crcmask; ; ; return(crc); ; } ; ; ; This algorithm can easily be implemented in assembly PIC assembly. ; (another implementation is below). ; ; enter with W=new data byte and current crc in crc:0-3 ; exit with new crc ; ; 94 instructions ; 35 - 85 cycles crc32_ver1: xorwf crc_lo,w movwf temp btfsc temp,0 bra v1_bit0 movf crc_ml,w movwf crc_lo movf crc_mh,w movwf crc_ml movf crc_hi,w movwf crc_mh clrf crc_hi bra v1_bit1 v1_bit0: movf crc_ml,w xorlw 0x96 movwf crc_lo movf crc_mh,w xorlw 0x30 movwf crc_ml movf crc_hi,w xorlw 0x07 movwf crc_mh movlw 0x77 movwf crc_hi v1_bit1: btfss temp,1 bra v1_bit2 movlw 0x2c xorwf crc_lo,f movlw 0x61 xorwf crc_ml,f movlw 0x0e xorwf crc_mh,f movlw 0xee xorwf crc_hi,f v1_bit2: btfss temp,2 bra v1_bit3 movlw 0x19 xorwf crc_lo,f movlw 0xc4 xorwf crc_ml,f movlw 0x6d xorwf crc_mh,f movlw 0x07 xorwf crc_hi,f v1_bit3: btfss temp,3 bra v1_bit4 movlw 0x32 xorwf crc_lo,f movlw 0x88 xorwf crc_ml,f movlw 0xdb xorwf crc_mh,f movlw 0x0e xorwf crc_hi,f v1_bit4: btfss temp,4 bra v1_bit5 movlw 0x64 xorwf crc_lo,f movlw 0x10 xorwf crc_ml,f movlw 0xb7 xorwf crc_mh,f movlw 0x1d xorwf crc_hi,f v1_bit5: btfss temp,5 bra v1_bit6 movlw 0xc8 xorwf crc_lo,f movlw 0x20 xorwf crc_ml,f movlw 0x6e xorwf crc_mh,f movlw 0x3b xorwf crc_hi,f v1_bit6: btfss temp,6 bra v1_bit7 movlw 0x90 xorwf crc_lo,f movlw 0x41 xorwf crc_ml,f movlw 0xdc xorwf crc_mh,f movlw 0x76 xorwf crc_hi,f v1_bit7: btfss temp,7 return movlw 0x20 xorwf crc_lo,f movlw 0x83 xorwf crc_ml,f movlw 0xb8 xorwf crc_mh,f movlw 0xed xorwf crc_hi,f return ; A second implementation ; ; enter with W=new data byte and current crc in crc:0-3 ; exit with new crc ; ; 76 instructions, 76 cycles. crc32_ver2: xorwf crc_lo,w movwf temp ; low byte movf crc_ml,W btfsc temp,0 xorlw 0x96 btfsc temp,1 xorlw 0x2c btfsc temp,2 xorlw 0x19 btfsc temp,3 xorlw 0x32 btfsc temp,4 xorlw 0x64 btfsc temp,5 xorlw 0xcb btfsc temp,6 xorlw 0x90 btfsc temp,7 xorlw 0x20 movwf crc_lo ; mid-low byte movf crc_mh,W btfsc temp,0 xorlw 0x30 btfsc temp,1 xorlw 0x61 btfsc temp,2 xorlw 0xc4 btfsc temp,3 xorlw 0x88 btfsc temp,4 xorlw 0x10 btfsc temp,5 xorlw 0x20 btfsc temp,6 xorlw 0x41 btfsc temp,7 xorlw 0x83 movwf crc_ml ; mid-high byte movf crc_hi,W btfsc temp,0 xorlw 0x07 btfsc temp,1 xorlw 0x0e btfsc temp,2 xorlw 0x6d btfsc temp,3 xorlw 0xdb btfsc temp,4 xorlw 0xb7 btfsc temp,5 xorlw 0x6e btfsc temp,6 xorlw 0xdc btfsc temp,7 xorlw 0xb8 movwf crc_mh ; hi byte clrw btfsc temp,0 xorlw 0x77 btfsc temp,1 xorlw 0xee btfsc temp,2 xorlw 0x07 btfsc temp,3 xorlw 0x0e btfsc temp,4 xorlw 0x1d btfsc temp,5 xorlw 0x3b btfsc temp,6 xorlw 0x76 btfsc temp,7 xorlw 0xed movwf crc_hi return crc_init movlw 0xff movwf crc_lo movwf crc_ml movwf crc_mh movwf crc_hi return crc_invert comf crc_lo,f comf crc_ml,f comf crc_mh,f comf crc_hi,f return start: rcall crc_init movlw '1' rcall crc32_ver1 ; crc = 0x7c231048 movlw '2' rcall crc32_ver1 ; crc = 0xb0acbb32 movlw '3' rcall crc32_ver1 ; crc = 0x77b79c2d movlw '4' rcall crc32_ver1 ; crc = 0x641c1f5c movlw '5' rcall crc32_ver1 ; crc = 0x340ac5e3 movlw '6' rcall crc32_ver1 ; crc = 0xf68d2c9e movlw '7' rcall crc32_ver1 ; crc = 0xaffc9660 movlw '8' rcall crc32_ver1 ; crc = 0x651f2550 movlw '9' rcall crc32_ver1 ; crc = 0x340bc6d9 rcall crc_invert ; crc = 0xcbf43926 bra start end