CRC (assembly and C)

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.

Digital Nemesis Pty Ltd (ash at digitalnemesis.com)

Original Code: Ashley Roll

Optimisations: Scott Dattalo

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; 
}

Same algorithm but now in assembly:

// 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; 
}