CRC routines

swToday we publish a general 8-bit CRC routine and an optimized CRC 16-bit routine with x16+x15+x2+1CRC16 IBM polynomial.

Sometimes it is necessary to add extra data protection using CRC. Presented 8-bit general optimized routine can handle any 8-bit polynomial specified in the reverse polynomial representation. Unlike 16-bit routine is hand optimized for polynomial x16+x15+x2+1only. If general 16-bit polynomial is required there are a few options how to implement it. There is usually time-memory tradeoff (lookup tables vs. recalculation). Good compromise is to use two nibble lookup tables (total size 32 bytes) instead of full tables (512 bytes). We might describe this technique in some future post.

Please note that version 3.5B of the CC5X compiler is required, as the previous versions do not compile the code at all or correctly.

uns8 UpdateCrc8( uns8 value @ W )
{
#define Poly 0x8c// 0x8C (OneWire x^8 + x^5 + x^4 + 1) is reverse polynomial representation (normal is 0x31, reciprocal is 0x98)
// #define Poly 0xB2 // x^8+x^6+x^3+x^2+1 (normal is 0x4D, reciprocal is 0xA6)
 
// Based on http://www.dattalo.com/technical/software/pic/crc_8bit.c
// 19 instructions, 20 machine cycles per byte. [Hynek]
 
/*
  *  How to compute next value to xor with
  *  Xn = (Xn-1 >> 1 ) ^ ( Xn-1.0 ? ReversePoly : 0x00 )
  *   e.g. 0x8C (OneWire x^8 + x^5 + x^4 + 1) is reverse polynomial representation (normal is 0x31)
  *   0x8c, 0x46, 0x23, 0x9d, 0xc2, 0x61, 0xbc, 0x5e
  */
#define NextP(CurPoly,Poly) ((uns8)( ((CurPoly) >>1) ^ ( ( (((CurPoly) &1) ^ 1 ) - 1 ) & (Poly) )))
 
  Crc8 ^= value;
#pragma update_RP 0/* OFF */    
  value = 0;
if ( Crc8.7 )
    value ^= Poly;    // Reverse polynomial representation
if ( Crc8.6 )
    value ^= NextP( Poly, Poly );
if ( Crc8.5 )
    value ^= NextP( NextP( Poly, Poly ), Poly );
if ( Crc8.4 )
    value ^= NextP( NextP( NextP( Poly, Poly ), Poly ), Poly );
if ( Crc8.3 )
    value ^= NextP( NextP( NextP( NextP( Poly, Poly ), Poly ), Poly ), Poly );
if ( Crc8.2 )
    value ^= NextP( NextP( NextP( NextP( NextP( Poly, Poly ), Poly ), Poly ), Poly ), Poly );
if ( Crc8.1 )
    value ^= NextP( NextP( NextP( NextP( NextP( NextP( Poly, Poly ), Poly ), Poly ), Poly ), Poly ), Poly );
if ( Crc8.0 )
    value ^= NextP( NextP( NextP( NextP( NextP( NextP( NextP( Poly, Poly ), Poly ), Poly ), Poly ), Poly ), Poly ), Poly );
 
return value;
}
uns16 Crc16IBM;
 
void UpdateCrc16IBM( uns8 value @ W )
{
// Based on http://www.piclist.com/techref/microchip/crc16ca.htm
// CRC-16 (CRC-16-IBM)  x^16 + x^15 + x^2 + 1  ( 0xa001 )
// Used at Bisync, Modbus, USB, ANSI X3.28, SIA DC - 07, many others; also known as CRC-16 and CRC-16-ANSI
//
// 27 instructions, 28 machine cycles per byte. [Hynek]
// No tables, No loops, No temporary registers used.
//
// Copyright( C ) February 8, 2000. All Right Reserved.
// Charles Ader, PO Box 940 Pleasanton, California, USA.
//
// This code started out as an example program found in
// Dallas Semiconductor Application Note 27: Understanding and Using Cyclic Redundancy Checks with Dallas Semiconductor iButton( TM ) Products.
// 
// Modified and optimized by Hynek
// - complimenting Carry by INCF STATUS,F does not work at 16F1938 family PIC! 
 
  value ^= Crc16IBM.low8;    // value = input XOR old crc_lo
#pragma update_RP 0/* OFF */    
  value ^= Crc16IBM.high8; // Swap old crc_hi with value
  Crc16IBM.high8 ^= value;
  value ^= Crc16IBM.high8; // new crc_hi = input XOR old crc_lo
  Crc16IBM.low8 = value;    // new crc_lo = old crc_hi
 
// Calculate parity of crc_hi ( input XOR old crc_lo )
  value = swap( Crc16IBM.high8 ); // Save crc_hi in value
  value ^= Crc16IBM.high8; // XOR high half byte with low
// Compute parity of bits 0-3 at bit 0
if ( value.1 )
    value ^= 1;
if ( value.2 )
    value ^= 1;
if ( value.3 )
    value ^= 1;
  value &= 1; // value = parity
 
// Use the parity of crc_hi, ( input XOR crc_lo ) to complete the CRC calculation.
  Crc16IBM.low8 ^= value;    // flip bit 0 of crc_lo by parity
  value = rr( value ); // Carry = parity 
  Crc16IBM.high8 = rr( Crc16IBM.high8 ); // shift parity into crc_hi
  value = 0x40;
if ( Carry ) // if shift out is one 
    Crc16IBM.low8 ^= value;    // flip bit 6 of crc_lo
 
  value = rl( Crc16IBM.high8 ); // unshift crc_hi into value
  Crc16IBM.high8 ^= value; // combine them
  Crc16IBM.high8 = rr( Crc16IBM.high8 ); // shift parity back into crc_hi
 
  value = 0x80;
if ( Carry ) // if shift out is one
    Crc16IBM.low8 ^= value;    // flip bit 7 of crc_lo
 
#pragma update_RP 1/* ON */    
}

 Enjoy.

Post sent by Hynek Syrovátka.

Leave a Reply

Your email address will not be published. Required fields are marked *