CCS C Software and Maintenance Offers
FAQFAQ   FAQForum Help   FAQOfficial CCS Support   SearchSearch  RegisterRegister 

ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog 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
 
Post new topic   Reply to topic    CCS Forum Index -> Code Library
View previous topic :: View next topic  
Author Message
ckielstra



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

View user's profile Send private message

CRC16, very efficient
PostPosted: Sat Oct 29, 2005 6:00 pm     Reply with quote

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

View user's profile Send private message

PostPosted: Wed Nov 02, 2005 10:22 am     Reply with quote

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

View user's profile Send private message

PostPosted: Wed Sep 26, 2007 2:59 pm     Reply with quote

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

View user's profile Send private message

The last operation doesn't make sense to me
PostPosted: Tue May 27, 2008 11:04 am     Reply with quote

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

View user's profile Send private message

Have I found a bug ?
PostPosted: Sun Sep 07, 2008 1:21 am     Reply with quote

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

View user's profile Send private message

PostPosted: Mon Sep 08, 2008 12:18 am     Reply with quote

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

View user's profile Send private message Visit poster's website

PostPosted: Sun Nov 02, 2008 8:10 am     Reply with quote

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

View user's profile Send private message Visit poster's website

PostPosted: Sun Nov 02, 2008 3:32 pm     Reply with quote

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

View user's profile Send private message

Fastest CRC-CCITT for PIC 12 & 16
PostPosted: Sun Dec 13, 2009 10:16 am     Reply with quote

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

View user's profile Send private message

Fastest CRC-8 for PIC 12 & 16
PostPosted: Sun Dec 13, 2009 10:21 am     Reply with quote

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

View user's profile Send private message

Re: Fastest CRC-CCITT for PIC 12 & 16
PostPosted: Fri Jan 08, 2010 10:01 am     Reply with quote

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

View user's profile Send private message

Re: Fastest CRC-CCITT for PIC 12 & 16
PostPosted: Wed Mar 03, 2010 4:30 am     Reply with 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 Confused

Thanks in advance.
ckielstra



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

View user's profile Send private message

Re: The last operation doesn't make sense to me
PostPosted: Wed Jan 11, 2012 5:53 pm     Reply with quote

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: 1744
Location: Boston Spa UK

View user's profile Send private message

Excel
PostPosted: Fri Jan 13, 2012 4:28 am     Reply with quote

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

View user's profile Send private message

PostPosted: Fri Nov 16, 2012 5:05 am     Reply with quote

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:   
Post new topic   Reply to topic    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