CRC16, very efficient Goto page 1, 2  Next
Author Message
ckielstra

Joined: 18 Mar 2004
Posts: 3680
Location: The Netherlands

CRC16, very efficient Posted: Sat Oct 29, 2005 6:00 pm This is an extremely efficient implementation of the CRC16 algorithm with the CCITT polynomial. It's even faster than implementations using a lookup table.

In CCS PCH v4.137 for the PIC18F458 the results are as follows:
C version: size of 182 bytes with an average 80 instruction cycles per character.
Assembly version: size of 74 bytes with an average 25 instruction cycles per character.

 Quote: ;---------------------------------------------------------------------- ; 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 ;----------------------------------------------------------------------

The algorithm in C code:
 Code: int16 crc_1021(int16 old_crc, int8 data) {   int16 crc;   int16 x;   x = make8(old_crc,1) ^ data;  //x = ((old_crc>>8) ^ data) & 0xff;   x ^= x>>4;   crc = (old_crc << 8) ^ (x << 12) ^ (x <<5) ^ x;   // crc &= 0xffff;      // enable this line for processors with more than 16 bits   return crc; }

Same algorithm but now in assembly:
 Code: // Register defines #locate FSR0=getenv("SFR:FSR0L") #locate POSTINC0=getenv("SFR:POSTINC0") //----------------------------------------------------------------------------- // Calculate the CRC16 value of a specified buffer. // // A very fast CRC-16 routine based on the CCITT polynome 0x1021. // This implementation is very small and fast. Using some specific features of // the polynome the resulting code is even faster than table driven algorithms. // // Original Code: Ashley Roll       www.digitalnemesis.com // Optimisations: Scott Dattalo     www.dattalo.com //----------------------------------------------------------------------------- int16 Calc_Crc16(int8 *Buffer, int16 Len) // Note: save 5 instructions by {                                         // changing 'int16 Len' to 'int8 Len'.   int8 Index;   union   {     int8  uByte;     int16 uWord;   } CRC16;   CRC16.uWord = 0xFFFF;     // Initialise CRC to 0xFFFF   FSR0 = Buffer;            // Copy Buffer address to pointer register FSR0   do   {     #ASM     movf  POSTINC0,w        // load w with next databyte     xorwf CRC16.uByte,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.uByte,W     movwf CRC16.uByte #ifdef __PCH__                   // PIC18     rlncf Index,W #else             // PIC16     rlf   Index,W     rlf   Index,W #endif        xorwf CRC16.uByte,f     andlw 0xe0     xorwf CRC16.uByte,f       swapf Index,F     xorwf Index,W     movwf CRC16.uByte     #ENDASM   } while (--Len);     return CRC16.uWord; }

In order to test the above functions here is some test code.
 Code: int16 Calc_CRC_C(int8 *Buffer, int16 Len) {    int16 x;    int16 crc = 0xFFFF;        while(Len--)    {       x = make8(crc,1) ^ *Buffer++;       x ^= x>>4;             crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x;    }    return crc; }    void main() {    int16 CRC1, CRC2;    int8 Buffer;    int16 i;        for (i=0; i < sizeof(Buffer); i++)       Buffer[i] = (int8)i;    i = sizeof(Buffer);    while (i--)    {       CRC1 = Calc_CRC_C(Buffer, sizeof(Buffer));             CRC2 = Calc_Crc16(Buffer, sizeof(Buffer));             if (CRC1 != CRC2)          while(1);      // Loop here forever on error                 // Modify data for a new test case       buffer = (int8) i;    }             // If we get here the test between the two CRC methods succeeded    while(1); }

Edit 1: Changed 'len' to 'Len' so code will compile when case sensitive.
Edit Jan-2012: Commented the line '&= 0xFFFF' in the C example as it is only required on a processor with more than 16 bits.
Edit Nov-2012:
- Added test functions, including the original C-code
- Retrieve the SFR0 and POSTINC registers using the new getenv function.
Updated code with user comments from below:
- Reversed the sequence in the union so the output of the assembly version matches that of the C version.
- Replaced the two rlcf instructions by a single rlncf for the PIC18 (thanks niels_J)

Last edited by ckielstra on Fri Nov 16, 2012 4:12 pm; edited 6 times in total Dargar

Joined: 12 Dec 2003
Posts: 25 Posted: Wed Nov 02, 2005 10:22 am Thank you, we will most likely use this in our current project. Credits for the code will be left in as shown in the "Quote" field in your post. Thanks again!_________________Owner of PCWH v. 3.224 Consider myself beginer\intermediate as far as CCS and Microchip PIC's goes. Bachelor in Space Engineering and Undergraduate Masters in Space Engineering soon to be undergrad Aerospace nmeyer

Joined: 09 Jul 2004
Posts: 70 Posted: Wed Sep 26, 2007 2:59 pm I am attempting to use the CRC-CCITT in a program i am developing. Is there an example of this being used in a program? At this point, I do not follow how this is being implemented. Greg_R

Joined: 21 Feb 2006
Posts: 19
Location: San Diego

 The last operation doesn't make sense to me Posted: Tue May 27, 2008 11:04 am I've been looking at the C version. crc &= 0xffff. I don't understand the purpose of this line. Bitwise ANDing a 16bit word with 0xffff returns the word... Greg piripic

Joined: 15 Jan 2008
Posts: 25

Have I found a bug ? Posted: Sun Sep 07, 2008 1:21 am Post modified because of erroneous consideration.

Now I have understood. In the assembly crc16 function the line of code:

 Code: rlcf  Index,W           // use rlf for PIC16     rlcf  Index,W           // use rlf for PIC16

It is the same as:

 Code: BCF   carry_flag     BTFSC Index,7     BSF   carry_flag     rlcf  Index,W           // use rlf for PIC16

but the first example (the author method) it is in a very optimized form

Claudio

Last edited by piripic on Mon Sep 08, 2008 6:25 am; edited 3 times in total piripic

Joined: 15 Jan 2008
Posts: 25 Posted: Mon Sep 08, 2008 12:18 am I have inverted the CRC low byte <-> high byte order (the CRC16.uByte index). Now C function and assembly function return the same CRC16 value:

 Code: //----------------------------------------------------------------------------- // Calculate the CRC16 value of a specified buffer. // // A very fast CRC-16 routine based on the CCITT polynome 0x1021. // This implementation is very small and fast. Using some specific features of // the polynome the resulting code is even faster than table driven algorithms. // // Original Code: Ashley Roll       www.digitalnemesis.com // Optimisations: Scott Dattalo     www.dattalo.com //----------------------------------------------------------------------------- int16 Calc_Crc16(int8 *Buffer, int16 Len) // Note: save 5 instructions by {                                         // changing 'int16 Len' to 'int8 Len'.   int8 Index;   union   {     int8  uByte;     int16 uWord;   } CRC16;   CRC16.uWord = 0xFFFF;     // Initialise CRC to 0xFFFF   FSR0 = Buffer;            // Copy Buffer address to pointer register FSR0   do   {     #ASM     movf  POSTINC0,w        // load w with next databyte     xorwf CRC16.uByte,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.uByte,W     movwf CRC16.uByte       rlcf  Index,W           // use rlf for PIC16     rlcf  Index,W           // use rlf for PIC16     xorwf CRC16.uByte,f     andlw 0xe0     xorwf CRC16.uByte,f       swapf Index,F     xorwf Index,W     movwf CRC16.uByte     #ENDASM   } while (--Len);     return CRC16.uWord; }

Thanks for the fast CRC16 code.

Claudio el_tigre

Joined: 23 Dec 2007
Posts: 12
Location: Bs As : Argentina Posted: Sun Nov 02, 2008 8:10 am Thanks for the code, I did test it and it works fine, but I have a problem. I need to apply the algorithm to a buffer of 516 bytes. When I used it with 8 bytes of total data this runs OK. I think that the problem is with FSR, I'm using a PIC18F4620 and the size of memory block is 256 bytes. Can you help me ? Thanks. el_tigre

Joined: 23 Dec 2007
Posts: 12
Location: Bs As : Argentina Posted: Sun Nov 02, 2008 3:32 pm I did´t.
The code for 18F4620 and data buffer >256 bytes is:
Thanks for the code !!!
 Code: char           sector_data;    #locate        sector_data=0x0300       #define       add_low   0x00    #define       add_hi     0x03 int16 Calc_Crc16( int16 Len) // Note: the adrres of data is placed {                                         // in the code   int8 Index;   union   {                                    int8  uByte;     int16 uWord;                      } CRC16;   CRC16.uWord = 0xFFFF;     // Initialise CRC to 0xFFFF //  FSR0L = Buffer;            // Copy Buffer address to pointer register FSR0    FSR1L=add_low;       // address low byte    FSR1H=add_hi;     // address hi byte   do   {     #ASM     movf  POSTINC0,w        // load w with next databyte     xorwf CRC16.uByte,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.uByte,W     movwf CRC16.uByte       rlcf  Index,W           // use rlf for PIC16     rlcf  Index,W           // use rlf for PIC16     xorwf CRC16.uByte,f     andlw 0xe0     xorwf CRC16.uByte,f       swapf Index,F     xorwf Index,W                movwf CRC16.uByte     #ENDASM   } while (--Len);     return CRC16.uWord; } PaulHolland

Joined: 13 Dec 2009
Posts: 2

Fastest CRC-CCITT for PIC 12 & 16 Posted: Sun Dec 13, 2009 10:16 am Code: CRC_16:         movf   INDF,w      ; FSR is pointing at input byte !. CRC_16_Direct:   xorwf   CrcH,w      ;             movwf   TMP         ;             andlw   0xF0      ;             swapf   TMP,f      ;             xorwf   TMP,f      ;             movf   TMP,W      ;             andlw   0xf0      ;             xorwf   CrcL,W      ;             movwf   CrcH      ;             rlf      TMP,W      ;             rlf      TMP,W      ;             xorwf   CrcH,f      ;                andlw   0xE0      ;             xorwf   CrcH,f      ;             swapf   TMP,f      ;             xorwf   TMP,W      ;             movwf   CrcL      ;             return            ; PaulHolland

Joined: 13 Dec 2009
Posts: 2

Fastest CRC-8 for PIC 12 & 16 Posted: Sun Dec 13, 2009 10:21 am Code: crc_8:    xorwf   crc,f    clrw    btfsc   crc,0    xorlw   0x5e    btfsc   crc,1    xorlw   0xbc    btfsc   crc,2    xorlw   0x61    btfsc   crc,3    xorlw   0xc2    btfsc   crc,4    xorlw   0x9d    btfsc   crc,5    xorlw   0x23    btfsc   crc,6    xorlw   0x46    btfsc   crc,7    xorlw   0x8c    movwf   crc    return ckielstra

Joined: 18 Mar 2004
Posts: 3680
Location: The Netherlands

Re: Fastest CRC-CCITT for PIC 12 & 16 Posted: Fri Jan 08, 2010 10:01 am PaulHolland wrote:
 Code: CRC_16:         movf   INDF,w      ; FSR is pointing at input byte !. CRC_16_Direct:   xorwf   CrcH,w      ;             movwf   TMP         ;             andlw   0xF0      ;             swapf   TMP,f      ;             xorwf   TMP,f      ;             movf   TMP,W      ;             andlw   0xf0      ;             xorwf   CrcL,W      ;             movwf   CrcH      ;             rlf      TMP,W      ;             rlf      TMP,W      ;             xorwf   CrcH,f      ;                andlw   0xE0      ;             xorwf   CrcH,f      ;             swapf   TMP,f      ;             xorwf   TMP,W      ;             movwf   CrcL      ;             return            ;
Thanks for posting your code, but this is exactly the same as I posted in the first message in this thread. Only changes are that all comments and references to the original author are removed. turbok

Joined: 03 Mar 2010
Posts: 1

Re: Fastest CRC-CCITT for PIC 12 & 16 Posted: Wed Mar 03, 2010 4:30 am Can anyone give an Excel formula to calculate the CRC given by this code?
The original poster quotes the algorithm used:

 Quote: ; int x; ; ; x = ((crc>>8) ^ data) & 0xff; ; x ^= x>>4; ; ; crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x; ; ; crc &= 0xffff;

But my maths is not up to working out the formula  ckielstra

Joined: 18 Mar 2004
Posts: 3680
Location: The Netherlands

Re: The last operation doesn't make sense to me Posted: Wed Jan 11, 2012 5:53 pm Greg_R wrote: I've been looking at the C version. crc &= 0xffff. I don't understand the purpose of this line. Bitwise ANDing a 16bit word with 0xffff returns the word... Greg
Thanks for the remark. This line was a leftover from the original C-code posting where the int type was 32-bits in size. For the PIC where we have a real 16-bit data type this line can be left out. Mike Walne

Joined: 19 Feb 2004
Posts: 1767
Location: Boston Spa UK

Excel Posted: Fri Jan 13, 2012 4:28 am Turbok wrote

 Quote: Can anyone give an Excel formula to calculate the CRC given by this code? The original poster quotes the algorithm used: Quote: ; int x; ; ; x = ((crc>>8) ^ data) & 0xff; ; x ^= x>>4; ; ; crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x; ; ; crc &= 0xffff; But my maths is not up to working out the formula

The XOR function is equivalent to multiplication, I'm not in a position to translate from the CRC algoritm to a corresponding multiplication.

I don't find that Excel lends itself easily to bit wise logic.

There are many ways Excel could be used to perform the CRC conversion.

A macro using VB or entirely in VB would work.

In Excel a single formula for the CRC calculation would be unwieldy. I would do the job in stages which can be easily tested. I'm not going to do it for you, but the following should help. Using the KISS principal, (1) convert the input variables to binary, (2) perform the logic operations, then (3) convert back to decimal.

1) Convert to binary.

To convert variable a to binary one bit at a time, the Excel formula "=MOD(INT(a/2^n),2)" generates the nth bit of a. The result is either a 0 or a 1.

2) Perform bit wise logic operation again one bit at a time.

To perform a XOR b in Excel use the formula "=IF((bit n of a) = (bit n of b) , 0, 1 )". The result is 0 if both bits are the same and 1 if different.

3) The shifts and conversion to decimal are relatively trivial.

Mike Walne niels_J

Joined: 16 Nov 2012
Posts: 1 Posted: Fri Nov 16, 2012 5:05 am Thanks a lot for this ingenious code. It made my bootloader fit in the boot page. It is also very much faster than the equivalent C-code, which I tried first. I have implemented it in an .asm file and can confirm that it verifies OK against the C-code and a very different code on a PC, which was checked against http://www.lammertbies.nl/comm/info/crc-calculation.html CRC-CCITT (0xFFFF).
While trying to understand the code I found I could replace the two rlcf with one rlncf on a PIC18. I have also added my own comments to the code. Hope this can help someone.
 Code: #include ; C18 uses FRS1 and FSR2 for stack pointers. FSR0 for indexing and other . ; It should be safe to use FSR0 here    LIST R=DEC   ; Default radix is hex    ; Make sure these are located in access RAM. Declared near in Main.c    EXTERN PgmData    ; (struct Adr; Byte)    EXTERN CRC16H, CRC16L        UDATA_ACS COUNTER   res 1 X   res 1       CODE CalcCRC16a:       GLOBAL CalcCRC16a ; Exported. C-prototype: extern void Crc16a(void) in Main.h    ; W=0, F=1. Last parameter is:  ACCESS = 0, BANKED = 1    ; Set CRC to 0xFFFF:    SETF     CRC16L,0   ; CL = FF    SETF     CRC16H,0   ; CH = FF    MOVLW     66      ; Number of bytes to process    MOVWF     COUNTER    ; Set FSR0 to point to PgmData in access RAM:    LFSR   FSR0, PgmData UpdateCRC:       ; x = ((crc>>8) ^ Data & 0xff;       ; x ^= x>>4;       ; crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x;              ;x = ((crc>>8) ^ Data & 0xff:   [(crc>>8): CL = CH, CH = 00]       movf  POSTINC0,0,0      ; load w with next databyte W = (dh:dl)       xorwf CRC16H,0,0        ; W = (CHh^dh : CHl^dl)       movwf X,0              ; X = W = (CHh^dh : CHl^dl)       andlw 0xf0              ; W = (CHh^dh : 0)       ;x ^= x>>4:       swapf X,1,0            ; X = (CHl^dl : CHh^dh)       xorwf X,1,0            ; X = (CHh^dh^CHl^dl : CHh^dh)  Now X is nibble swapped x:                         ; X = x3,x2,x1,x0 : x7,x6,x5,x4       ;(crc << 8) ^ (x << 12):  [(crc << 8): CH = CL, CL = 00]       movf  X,0,0            ; W = X              andlw 0xf0             ; W = Xh : 0       xorwf CRC16L,0,0       ; W = CLh^Xh : CLl       movwf CRC16H,0          ; CH = W       ; ^ (x <<5):       rlncf  X,0,0          ; W = (x2,x1,x0,x7 : x6,x5,x4,x3)  replaces next 2 lines       ;rlcf  X,0,0          ; W = (x2,x1,x0,x7 : x6,x5,x4,?)   old          ;rlcf  X,0,0             ; W = x2,x1,x0,x7 : x6,x5,x4,x3    old       xorwf CRC16H,1,0       ; CH = CH ^ (x2,x1,x0,x7 : x6,x5,x4,x3)       andlw 0xe0             ; W = x2,x1,x0,0 : 0,0,0,0       xorwf CRC16H,1,0       ; CH = CH ^ (0,0,0,x7 : x6,x5,x4,x3) ( dubbel xor = ingen ändring)       ; ^ x  (and part of ^ (x <<5))       swapf X,1,0          ; X = x7,x6,x5,x4 : x3,x2,x1,x0       xorwf X,0,0            ; W = (x2,x1,x0,0 : 0,0,0,0) ^ (x7,x6,x5,x4 : x3,x2,x1,x0)       movwf CRC16L,0          ; CL = W (CL was 00)        DECF COUNTER,1,0           BNZ UpdateCRC    return END Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 All times are GMT - 6 HoursGoto page 1, 2  Next Page 1 of 2

 Jump to: Select a forum Software----------------General CCS C DiscussionCode LibraryEZ App Lynx Hardware----------------CCS ICD / Mach X / Load-n-Go
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum