====== CRC (assembly and C) ======

===== Background =====

[[.:crc-16:crc_16_1021.asm]]

PIC CRC16 (CRC-CCITT-16 **0x1021**)

Representations: normal / reversed / reverse of reciprocal: 0x1021 / 0x8408 / 0x8810

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. 

[[http://www.digitalnemesis.com|Digital Nemesis Pty Ltd]] (ash at digitalnemesis.com)

Original Code: Ashley Roll

Optimisations: Scott Dattalo

===== C code =====


<code C>
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; 

  return crc; 
}
</code>

===== Assembly code =====

Same algorithm but now in assembly: 
<code C>
// Register defines for the PIC18F458 
unsigned int16 FSR0; 
#locate FSR0=0x0FE9 

//----------------------------------------------------------------------------- 
// 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[0],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[1],W 
    movwf CRC16.uByte[0] 
  
    rlcf  Index,W           // use rlf for PIC16 
    rlcf  Index,W           // use rlf for PIC16 
    xorwf CRC16.uByte[0],f 
    andlw 0xe0 
    xorwf CRC16.uByte[0],f 
  
    swapf Index,F 
    xorwf Index,W 
    movwf CRC16.uByte[1] 
    #ENDASM  
  } while (--Len); 
  
  return CRC16.uWord; 
}
</code>