 |
 |
| View previous topic :: View next topic |
| 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.
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: 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 
Thanks in advance. |
|
|
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: 1785
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: 2
|
|
| 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
|
|
|
|
|
|
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
|
FAQ 
Search
Register
Profile 
Log in to check your private messages 
Log in
