;---------------------------------------------------------------------- ; PIC CRC16 Implementation with Restricted Table Size ; ; Digital Nemesis Pty Ltd ; www.digitalnemesis.com ; ash@digitalnemesis.com ; ; Original Code: Ashley Roll ; Optimisations: Scott Dattalo ; Reflected version: Dave Dribin ;---------------------------------------------------------------------- list p=12c508 ; list directive to define processor #include ; processor specific variable definitions __CONFIG _CP_OFF & _WDT_OFF & _MCLRE_OFF & _IntRC_OSC ;---------------------------------------------------------------------- ; Program Variables ; Note that we start at RAM location 0x07 ;---------------------------------------------------------------------- CBLOCK 0x07 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. ; ; This is a table for the CRC-16 with a polynomial of 8005 and the ; inputs and outputs reflected. ; CRC16_Lookup: ANDLW 0xF ADDWF PCL, F ; RETLW 0x00 ; LOW Byte DATA ; RETLW 0x01 ; RETLW 0x01 ; RETLW 0x00 ; RETLW 0x01 ; RETLW 0x00 ; RETLW 0x00 ; RETLW 0x01 ; RETLW 0x01 ; RETLW 0x00 ; RETLW 0x00 ; RETLW 0x01 ; RETLW 0x00 ; RETLW 0x01 ; RETLW 0x01 ; RETLW 0x00 RETLW 0x00 ; HIGH Byte Data RETLW 0xCD RETLW 0xD9 RETLW 0x14 RETLW 0xF1 RETLW 0x3C RETLW 0x28 RETLW 0xE5 RETLW 0xA1 RETLW 0x6C RETLW 0x78 RETLW 0xB5 RETLW 0x50 RETLW 0x9D RETLW 0x89 RETLW 0x44 ;---------------------------------------------------------------------- ; CRC_Init Subroutine CRC_Init: MOVLW 0x00 MOVWF CRC16_High MOVWF CRC16_Low RETLW 0 ;---------------------------------------------------------------------- ; CRC_Update Subroutine ; ; Optimized 16-bit CRC routine for the polynomial 0x8005 - reversed ; Inspired by Dave Dribin. ; ; The algorithm for computing a 16-bit CRC using nibble tables ; can be generically described. Suppose the 16-bit is described ; by: ; ; CRC = STUV ; ; Where S, T, U, and V are the 4 nibbles of the CRC. ; ; And suppose the next byte in the message stream is ; ; Message byte = PQ ; ; Where P and Q are the nibbles. ; ; In this algorithm there are two tables (or arrays); one for the high ; byte and one for the low byte of the CRC. Each table is 16 bytes long ; and indexed by the lowest nibble of the current CRC value like so: ; ; Index = V ^ Q ; ; The CRC is shifted right 4 bit positions and the elements from the high ; and low byte tables are exclusive ored to create the new CRC: ; ; Shift right 4 ( CRC = CRC >> 4 ) ; CRC = 0STU ; ; YZ = TU ^ CRC_TableLow[Index]; ; WX = 0S ^ CRC_TableHigh[Index]; ; ; Where WXYZ is the new CRC value. ; ; This step needs to be repeated once more for the second nibble ; of the message byte: ; ; Index = Z ^ P ; This time the high nibble of the message is used ; ; CRC = 0WXY ; Shift the CRC right 4 positions ; ; New Low byte = XY ^ CRC_TableLow[Index]; ; New High byte = 0W ^ CRC_TableHigh[Index]; ; ; and we're done! ; ; Now, it's possible to collapse many of these XOR operations into ; just a few steps. Before doing that, let's make a few observations. ; ; The computed Index is used to access a byte from the low and high ; tables at each step. Combine these bytes and into a 16-bit word ; and express them in terms of nibbles: ; ; A1 B1 C1 D1 => A1,B1 are the nibbles of the high byte ; and C1,D1 are the nibbles of the low byte ; ; the '1' refers to the first access of the table. ; ; The second access is: ; ; A2 B2 C2 D2 ; ; Now we can re-express the algorithm as: ; ; Index = V ^ Q ; low nibble of crc and message byte ; A1 B1 C1 D1 = CRC_table[Index]; ; WXYZ = 0STU ^ A1 B1 C1 D1; ; ; Index = Z ^ P ; low nibble of crc and high nibble of message ; A2 B2 C2 D2 = CRC_table[Index]; ; STUV = 0WXY ^ A2 B2 C2 D2 ; ; Ignoring the index computation for a moment, we can collapse ; the two 16-bit exclusive or operations: ; ; STUV = 00ST ^ (0 A1 B1 C1) ^ (A2 B2 C2 D2) ; ; Or in terms of nibbles: ; ; V = T ^ C1 ^ D2 ; U = S ^ B1 ^ C2 ; T = A1 ^ B2 ; S = A2 ; ; Now we need to calculate the Nibbles for Ai - Di. This is where it ; becomes necessary to analyze the CRC Polynomial. Dave Dribin has ; shown that the nibble indexed tables for the low and high bytes ; are: ; ; CRC16_LookupLow[16] = { 0x00,0x01,0x01,0x00,0x01,0x00,0x00,0x01, ; 0x01,0x00,0x00,0x01,0x00,0x01,0x01,0x00}; ; CRC16_LookupHigh[16] = { 0x00,0xCD,0xD9,0x14,0xF1,0x3C,0x28,0xE5, ; 0xA1,0x6C,0x78,0xB5,0x50,0x9D,0x89,0x44}; ; ;Observation 1 ; C, the high nibble of the low byte, is always 0. ;Observation 2 ; D, the low nibble of the low byte, is either 0 or 1. Also, the ; lsb of D is equal to the MSB of A. ; ; If we express the nibble that indexes into the table as: ; ; Index = abcd, abcd are the individual bits of the Index nibble, ; then with a little effort you can see that the bits of A, the ; high nibble of the high byte, can be expressed as: ; ; bit3 = a^b^c^d ; bit2 = b^c^d ; bit1 = a^b ; bit0 = b^c ; ; Similarly, B, the low nibble of the high byte can be expressed as: ; ; bit3 = c^d ; bit2 = d ; bit1 = 0 ; bit0 = 0 ; ; ; Okay, that should be enough background to enable writing the code CRC_Update: XORWF CRC16_Low,w ;UV^PQ - The next message byte and the MOVWF Temp ;current crc xor'd for the indexes into ;the tables MOVF CRC16_High,W ;Shift the CRC right 8 bits, i.e. MOVWF CRC16_Low ;UV = ST ; CLRW ;Build CRC_TableHigh from Index1 BTFSC Temp,0 ;From the description above, we're MOVLW 0xcc ;forming the A1 B1 byte. However, BTFSC Temp,1 ;as a little twist, we actually XORLW 0x8d ;form B1 A1 since we need to shift BTFSC Temp,2 ;this right 4 bits before xor'ing XORLW 0x0f ; BTFSC Temp,3 ; XORLW 0x0a ; ; MOVWF CRC16_High ;Set the high byte to B1 A1 ANDLW 0xf0 ;grab B1 XORWF CRC16_High,f ;Remove it from the high byte (now 0 A1) XORWF CRC16_Low,f ;and put it in the low byte ; CLRW ;We need to grab the LSB of D1 (same as msb BTFSC CRC16_High,3 ;of A1) and xor it with the LSB of Index2. MOVLW 0xcc ; BTFSC Temp,4 ;Now we build CRC_TableHigh from Index2 XORLW 0xcc ;We basically do the same thing as BTFSC Temp,5 ;above, but this time we build the XORLW 0xd8 ;nibbles in order: A2 B2 BTFSC Temp,6 ; XORLW 0xf0 ; BTFSC Temp,7 ; XORLW 0xa0 ; ; XORWF CRC16_High,f ;Now combine it with the high byte MOVLW 0x01 ;The lsb of D2 (same as msb of A2) BTFSC CRC16_High,7 ;needs to be combined with the low XORWF CRC16_Low,f ;byte RETURN ; 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 low 4 bits from the message byte and XOR it with the ; low 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_Low, W XORWF CRC16_MessageByte, W ANDLW 0x0F MOVWF Index ; Index = (CRC16_Low ^ CRC16_MessageByte) ;; CRC16 is composed of the following nybbles: S T U V ;; where CRC16_High = S T and CRC16_Low = U V ;; Shift the CRC Register right 4 bits MOVLW 0xf0 ; W = F 0 ANDWF CRC16_Low, F ; CRC16_Low = U 0 SWAPF CRC16_Low, F ; CRC16_Low = 0 U SWAPF CRC16_High, F ; CRC16_High = T S ANDWF CRC16_High, W ; W = T 0 IORWF CRC16_Low, F ; CRC16_Low = T U XORWF CRC16_High, F ; CRC16_High = 0 S, thus CRC16 = 0 S T U ; Do the table lookups and XOR into the CRC Registers MOVF Index, W CALL CRC16_Lookup ANDLW 0x01 XORWF CRC16_Low, F ; CRC16_Low = CRC16_Low ^ CRC16_LookupLow[t] MOVF Index, W ;IORLW 0x10 ; Access High Table CALL CRC16_Lookup ;BTFSC Count,0 ANDLW 0xfe XORWF CRC16_High, F ; CRC16_High = CRC16_High ^ CRC16_LookupHigh[t] ; 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 ;---------------------------------------------------------------------- ; Beginnig of Main Program ;---------------------------------------------------------------------- BeginProgram: call CRC_Init movlw 0x80 CALL CRC_Update ;a001 call CRC_Init movlw 0x40 CALL CRC_Update ;f001 call CRC_Init movlw 0x20 CALL CRC_Update ;0xd801 call CRC_Init movlw 0x10 CALL CRC_Update ;cc01 call CRC_Init movlw 0x08 CALL CRC_Update ;c601 call CRC_Init movlw 0x04 CALL CRC_Update ;c301 call CRC_Init movlw 0x02 CALL CRC_Update ;c181 call CRC_Init movlw 0x01 CALL CRC_Update ;c0c1 ; Initialise the CRC registers CALL CRC_Init MOVLW 0x80 ; crc = 00 00 CALL CRC_Update MOVLW 0x75 ; crc = a0 01 CALL CRC_Update MOVLW 0x8a ; crc = 27 a0 CALL CRC_Update MOVLW 0x0b ; crc = df a6 CALL CRC_Update MOVLW 0x75 ; crc = bd 1e CALL CRC_Update MOVLW 0xc7 ; crc = ef fc CALL CRC_Update MOVLW 0xaa ; crc = d3 ae CALL CRC_Update MOVLW 0x75 ; crc = c3 d2 CALL CRC_Update MOVLW 0xc7 ; crc = ba 82 CALL CRC_Update MOVLW 0x55 ; crc = f3 7b CALL CRC_Update MOVLW 0x43 ; crc = 1c 73 CALL CRC_Update MOVLW 0x1c ; crc = 14 1c CALL CRC_Update MOVLW 0x14 ; crc = 00 14 CALL CRC_Update NOP ; crc = 00 00 Forever: GOTO Forever END