;---------------------------------------------------------------------- ; PIC CRC16 (CRC-CCITT-16 0x1021) ; ; ; ; ; Background: ; ; Ashley Roll posted some code on the piclist (http://www.piclist.com) ; that implemented "CRC16" - or the CRC-CCITT-16 algorithm for the polynomial ; 0x1021. Tony K�bek and I took a few rounds optimizing the code and ; we ended up with a PIC implementation that was only 17 instructions ; (and 17 cycles, i.e. unlooped)! ; ; After further investigations, I found that the algorithm can be ; expressed: ; ; ; int x; ; ; x = ((crc>>8) ^ data) & 0xff; ; x ^= x>>4; ; ; crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x; ; ; crc &= 0xffff; ; ; No claim is made here that this is the first time that this algorithm ; has been expressed this way. But, it's the first time I've seen like ; this. Using this as a guide, I wrote another routine in PIC assembly. ; Unfortunately, this one takes 17 cycles too. ; ; Digital Nemesis Pty Ltd ; www.digitalnemesis.com ; ash@digitalnemesis.com ; ; Original Code: Ashley Roll ; Optimisations: Scott Dattalo ;---------------------------------------------------------------------- list p=p16f84 ; list directive to define processor #include p16f84.inc ; processor specific variable definitions ; __CONFIG _CP_OFF & _WDT_OFF & _MCLRE_OFF & _IntRC_OSC ;---------------------------------------------------------------------- ; Program Variables ; Note that we start at RAM location 0x07 ;---------------------------------------------------------------------- CBLOCK 0x0c CRC16_High ; The CRC Register CRC16_Low Index ; Temp registers used during CRC update, can Temp ; be reused when not calling CRC_Update Count CRC16_MessageByte ENDC ;---------------------------------------------------------------------- ; Startup Code ORG 0x0000 ; coding begins here ; MOVWF OSCCAL ; update register with factory cal value ; Skip to the main code GOTO BeginProgram ;---------------------------------------------------------------------- ; CRC16 Lookup Table. This is actually the Low and High lookup tables ; conconated together to save a few words of ROM space. ; ; To access the Low table, Enter with 0 <= W <= 15 ; To access the High table, Enter with 16 <= W <= 31 ; ; This can easily be achieved by setting or clearing bit 4. CRC16_Lookup: ANDLW 0x1F ADDWF PCL, F RETLW 0x00 ; LOW Byte Data RETLW 0x21 RETLW 0x42 RETLW 0x63 RETLW 0x84 RETLW 0xA5 RETLW 0xC6 RETLW 0xE7 RETLW 0x08 RETLW 0x29 RETLW 0x4A RETLW 0x6B RETLW 0x8C RETLW 0xAD RETLW 0xCE RETLW 0xEF RETLW 0x00 ; HIGH Byte DATA RETLW 0x10 RETLW 0x20 RETLW 0x30 RETLW 0x40 RETLW 0x50 RETLW 0x60 RETLW 0x70 RETLW 0x81 RETLW 0x91 RETLW 0xA1 RETLW 0xB1 RETLW 0xC1 RETLW 0xD1 RETLW 0xE1 RETLW 0xF1 ;---------------------------------------------------------------------- ; CRC_Init Subroutine CRC_Init: MOVLW 0xFF MOVWF CRC16_High MOVWF CRC16_Low RETLW 0 ;---------------------------------------------------------------------- ; Looped version: ; ; CRC_Update Subroutine _CRC_Update: ; Save the Message Byte in the W register MOVWF CRC16_MessageByte ; We need to perform two iterations each processing 4 bits from the ; CRC16_MessageByte register. MSB first. MOVLW 2 MOVWF Count CRC16_UpdateLoop: ; Get the top 4 bits from the message byte and XOR it with the ; top 4 bits extracted from the CRC register to generate the lookup index. ; Note that on the second iteration the nibbles in the message byte ; will have been swaped again so we are actually getting the low ; nibble of the message byte MOVF CRC16_High, W XORWF CRC16_MessageByte, W ANDLW 0xF0 MOVWF Index ; Index = (CRC16_High ^ CRC16_MessageByte) & 0xF0 ; Shift the CRC Register left 4 bits MOVLW 0x0f ANDWF CRC16_High, F SWAPF CRC16_High, F SWAPF CRC16_Low, F ANDWF CRC16_Low, W IORWF CRC16_High, F ; CRC16_High = (CRC16_High << 4) | (CRC16_Low >> 4) XORWF CRC16_Low, F ; CRC16_Low = CRC16_Low << 4 ; Do the table lookups and XOR into the CRC Registers movf Index,w btfsc Index,7 iorlw 1 xorwf CRC16_High,f swapf Index,w addwf Index,w addwf Index,w xorwf CRC16_Low,f ; Swap the nibbles in the message byte so that next iteration we do the ; low nibble SWAPF CRC16_MessageByte, F ; Check if we need to iterate again DECFSZ Count, F GOTO CRC16_UpdateLoop RETLW 0 ; return Finished ;============================================================== ; ; Unrolled version ; ; W = CRC Message byte ; CRC16 - current 16-bit CRC check sum ; ; let CRC16 = abcd ; Message Byte = xy ; ; where abcd, xy are nibble variables ; ; Upon exit, ; ; a = c ^ (i1>>3) ^ i2 ; b = d ^ ((i1<<1)&0xf) ^ (i2>>3) ; c = i1 ^ ((i2<<1)&0xf) ; d = i2 ; ; First compute the nibble array indices: ; i1 = a ^ x ; i2 = i1 ^ b ^ y ; ; ; Notation (I) : (J) is a byte with I= high nibble, J= low nibble ; CRC_Update2: xorwf CRC16_High,w ; (a^x):(b^y) movwf Index ; andlw 0xf0 ; W = (a^x):0 swapf Index,f ; Index = (b^y):(a^x) xorwf Index,f ; Index = (a^b^x^y):(a^x) = i2:i1 ; High byte rlf Index,W ; rlf Index,W ; andlw 0x1f ; W = (i1>>3) : (((i1<<1)&0xf) | (i2>>3)) xorwf CRC16_Low,w ; W = (i1>>3)^c : ((((i1<<1)&0xf) | (i2>>3)) ^ d) movwf CRC16_High ; low nibble of high byte is done movf Index,w andlw 0xf0 ; W = i2 : 0 xorwf CRC16_High,f ; High nibble is of high byte is done ; now low byte movwf CRC16_Low ; Low = i2 : 0 addwf CRC16_Low,f ; Low = (i2<<1) : 0 swapf Index,W ; W = i1 : i2 xorwf CRC16_Low,f ; Low = i1 ^ (i2<<1) : i2 retlw 0 ;============================================================== ;int crc_1021(int data) ;{ ; ; int x; ; ; x = ((crc>>8) ^ data) & 0xff; ; x ^= x>>4; ; ; crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x; ; ; crc &= 0xffff; ; ; return crc; ; ;} CRC_Update xorwf CRC16_High,w ; (a^x):(b^y) movwf Index ; andlw 0xf0 ; W = (a^x):0 swapf Index,f ; Index = (b^y):(a^x) xorwf Index,f ; Index = (a^b^x^y):(a^x) = i2:i1 ; High byte movf Index,W andlw 0xf0 xorwf CRC16_Low,W movwf CRC16_High rlf Index,W ; rlf Index,W ; xorwf CRC16_High,f andlw 0xe0 xorwf CRC16_High,f swapf Index,F xorwf Index,W movwf CRC16_Low retlw 0 ;---------------------------------------------------------------------- ; Beginnig of Main Program ;---------------------------------------------------------------------- BeginProgram: ; Initialise the CRC registers CALL CRC_Init ; Test Vector: "123456789" ; Result: 0x29B1 MOVLW '1' CALL CRC_Update ;c782 MOVLW '2' CALL CRC_Update ;3dba MOVLW '3' CALL CRC_Update ;5bce MOVLW '4' CALL CRC_Update ;5349 MOVLW '5' CALL CRC_Update ;4560 MOVLW '6' CALL CRC_Update ;2ef4 MOVLW '7' CALL CRC_Update ;7718 MOVLW '8' CALL CRC_Update ;a12b MOVLW '9' CALL CRC_Update ;29b1 Forever: GOTO Forever END