FAQ Forum Help Official CCS Support Search Register Profile Log in to check your private messages Log in | CCS does not monitor this forum on a regular basis. Please do not post bug Reports on this forum. Send them to support@ccsinfo.com
CRC16, very efficient Goto page 1, 2 Next
| CCS Forum Index -> Code Library
View previous topic :: View next topic
Author | Message
--- | ---
ckielstra Joined: 18 Mar 2004 Posts: 3674 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. Code downloaded from http://www.dattalo.com/technical/software/pic/crc_1021.asm and adapted for the CCS compiler. 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[2]; 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[1],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[0],W movwf CRC16.uByte[1] #ifdef __PCH__ // PIC18 rlncf Index,W #else // PIC16 rlf Index,W rlf Index,W #endif xorwf CRC16.uByte[1],f andlw 0xe0 xorwf CRC16.uByte[1],f swapf Index,F xorwf Index,W movwf CRC16.uByte[0] #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[500]; 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[200] = (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 2: Added link to Scott Dattalo's website 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[2]; 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[1],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[0],W movwf CRC16.uByte[1] rlcf Index,W // use rlf for PIC16 rlcf Index,W // use rlf for PIC16 xorwf CRC16.uByte[1],f andlw 0xe0 xorwf CRC16.uByte[1],f swapf Index,F xorwf Index,W movwf CRC16.uByte[0] #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[516]; #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[2]; 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[1],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[0],W movwf CRC16.uByte[1] rlcf Index,W // use rlf for PIC16 rlcf Index,W // use rlf for PIC16 xorwf CRC16.uByte[1],f andlw 0xe0 xorwf CRC16.uByte[1],f swapf Index,F xorwf Index,W movwf CRC16.uByte[0] #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: 3674 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 Thanks in advance.
ckielstra Joined: 18 Mar 2004 Posts: 3674 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: 1641 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 <p18F2520.inc> ; 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[2]; Byte[64]) 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:
| CCS Forum Index -> Code Library | All times are GMT - 6 Hours Goto page 1, 2 Next
Page 1 of 2
Jump to:
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
Powered by phpBB © 2001, 2005 phpBB Group