Follow our illustrated blog on Embedded Software Architecture

How to build a hybrid solar/wind energy harvester?

Painless CRC for your embedded device

VN:F [1.9.22_1171]
Rating: 0.0/10 (0 votes cast)

We cannot take credit for any of the code – which is public domain – but we found it to be so valuable that we dedicate this blog post to it.

A CRC or cyclic redundancy check algorithm is used to detect errors or changes in raw data.

  • It is good at detecting unintentional changes (bit errors) in a data stream.
  • It provides little protection against intentional data changes.
  • An applied n-bit CRC will detect any single error burst not longer than n bits.
  • An applied n-bit CRC will detect a fraction (with value 1 − 2 to the power -n) of all longer error bursts.

A naive but good and common implementation can be found at the website of the barrgroup.

crcmodel

But the one that we prefer and is public domain can be found at http://www.ross.net/crc/download/crc_v3.txt
The original article is from 1993.

It is endian-agnostic, which means it is very helpful if you ever tried to verify a CRC, which was calculated on a system with another endianess byte order.
It can be accelerated by using the table-driven variant, but usually the slow reference implementation is sufficient.

One can download crcmodel.h and crcmodel.c

How to use this?
Clues can be found at http://www.ross.net/crc/download/crc_v3.txt


/*********************************************************/
/*                                                       */
/* How to Use This Package                               */
/* -----------------------                               */
/* Step 1: Declare a variable of type cm_t.              */
/*         Declare another variable                      */
/*         (p_cm say) of type p_cm_t                     */
/*         and initialize it to point to the first       */
/*         variable (e.g. p_cm_t p_cm = &cm_t).          */
/*                                                       */
/* Step 2: Assign values to the parameter fields of      */
/*         the structure.                                */
/*         If you don't know what to assign, see the     */
/*         document cited earlier.                       */
/*         For example:                                  */
/*            p_cm->cm_width = 16;                       */
/*            p_cm->cm_poly  = 0x8005L;                  */
/*            p_cm->cm_init  = 0L;                       */
/*            p_cm->cm_refin = TRUE;                     */
/*            p_cm->cm_refot = TRUE;                     */
/*            p_cm->cm_xorot = 0L;                       */
/*         Note: Poly is specified without its top bit   */
/*               (18005 becomes 8005).                   */
/*         Note: Width is one bit less than the raw      */
/*               poly width.                             */
/*                                                       */
/* Step 3: Initialize the instance with a call           */
/*         cm_ini(p_cm);                                 */
/*                                                       */
/* Step 4: Process zero or more message bytes by placing */
/*         zero or more successive calls to cm_nxt.      */
/*         Example: cm_nxt(p_cm,ch);                     */
/*                                                       */
/* Step 5: Extract the CRC value at any time by calling  */
/*         crc = cm_crc(p_cm);                           */
/*         If the CRC is a 16-bit value,                 */
/*         it will be in the bottom 16 bits.             */
/*                                                       */
/*********************************************************/

Example

Our example attempt:


//////////////////////////////////////////////////////////
// CRC-16/CITT // 0x1021
uint16_t CRC16_CITT(const uint8_t* message, uint32_t nBytes)
{
  cm_t crcmodel = {
    .cm_width = 16,
    .cm_poly = 0x1021,
    .cm_init = 0xFFFF,
    .cm_refin = FALSE,
    .cm_refot = FALSE,
    .cm_xorot = 0,
  };
  cm_ini(&crcmodel);
  while (nBytes) {
    cm_nxt(&crcmodel, *message);
    --nBytes;
    ++message;
  }
  return cm_crc(&crcmodel);
}
VN:F [1.9.22_1171]
Rating: 0.0/10 (0 votes cast)
Share
About rtos.be

rtos.be is a joined initiative from Gert Boddaert and Pieter Beyens.
More info: about us, our mission, contact us.

Comments

  1. Matthias Dörfel says:

    There are some more public domain implementations. Back in 1995 we used a table-based implementation which is published in the Appendix of RFC 1549 – even including the source code to generate a new table for a different CRC polynom.
    The tables could save some cycles if you can afford the space in the .text section.

Speak Your Mind

*