Home

Awesome

AceCRC

AUnit Tests

This library contains a number of CRC algorithms that were generated from pycrc (https://pycrc.org) and programmatically converted to Arduino format to use C++ namespaces to avoid name collisions and PROGMEM flash memory for lookup tables to save static RAM. From the list of pycrc supported algorithms, this library supports:

For each algorithm, 4 different implementations were generated:

The pycrc program generates *.h and *.c files containing C99 code with the following definitions:

This library converts the C99 code in the following way:

TL;DR: Use crc32_nibble in most cases, except on ESP8266 where you should use crc32_nibblem.

Version: 1.1.1 (2023-07-12)

Changelog: CHANGELOG.md

Table of Contents

<a name="HelloCRC"></a>

HelloCRC

Here is the sample program from examples/HelloCRC that uses the CRC-16-CCITT algorithm using a 4-bit lookup table (16 elements):

#include <Arduino.h>
#include <AceCRC.h>

using namespace ace_crc::crc16ccitt_nibble;

static const char CHECK_STRING[] = "123456789";
static const size_t LENGTH = sizeof(CHECK_STRING) - 1;

void setup() {
  Serial.begin(115200);
  while (!Serial); // Wait - Leonardo/Micro

  crc_t crc = crc_init();
  crc = crc_update(crc, CHECK_STRING, LENGTH);
  crc = crc_finalize(crc);
  Serial.print("0x");
  Serial.println((unsigned long) crc, 16);

  crc = crc_calculate(CHECK_STRING, LENGTH);
  Serial.print("0x");
  Serial.println((unsigned long) crc, 16);
}

void loop() {
}

This prints the hexadecimal numbers

0xE5CC
0xE5CC

as expected.

<a name="Installation"></a>

Installation

The latest stable release is available in the Arduino IDE Library Manager. Search for "AceCRC" and click install.

The development version can be installed by cloning the git repo:

You can copy over the contents to the ./libraries directory used by the Arduino IDE. (The result is a directory named ./libraries/AceCRC). Or you can create symlinks from ./libraries to these directories.

The develop branch contains the latest development. The master branch contains the stable releases.

<a name="Dependencies"></a>

Dependencies

This library has no external dependencies for client use. But the following dependencies are required for development and testing purposes:

<a name="Documentation"></a>

Documentation

<a name="Usage"></a>

Usage

<a name="Headers"></a>

Headers and Namespaces

Only a single header file AceCRC.h is required to use this library.

#include <AceCRC.h>

Then select the namespace of the algorithm that you want to use. For example, to use the version of crc32 which uses a 4-bit table (16 entries), which are stored in static memory instead of flash memory, use the following:

using namespace ace_crc::crc32_nibblem;

To use the 8-bit table, which are stored in flash memory, use:

using namespace ace_crc::crc32_byte;

<a name="CoreFunctions"></a>

Core CRC Functions

All algorithms and their variants are placed in separate C++ namespaces so they do not collide, and you can use multiple CRC algorithms in a single program without worrying about name collision.

The function names and their signatures from the underlying generated code from pycrc remain unchanged. For reference, the principle functions are:

See the examples/HelloCRC example code to see how these functions are used. The crc_update() function can be called multiple times with additional data, before calling crc_finalize().

This library adds the following convenience function to each header file in each namespace:

This function replaces the three separate calls to crc_init(), crc_update(), crc_finalize() with a single call.

<a name="IntegerSizes"></a>

Integer Sizes

By default, the pycrc program generates C99 code which contains one of the following definitions of the crc_t type:

typedef uint_fast8_t crc_t;
typedef uint_fast16_t crc_t;
typedef uint_fast32_t crc_t;

These are converted by this library to these instead:

typedef uint8_t crc_t;
typedef uint16_t crc_t;
typedef uint32_t crc_t;

On 8-bit processors, uint_fast8_t is identical to uint8_t, uint_fast16_t is identical to uint16_t, and uint_fast32_t is identical to uint32_t.

On 32-bit processors (e.g. SAMD, ESP8266, ESP32), uint_fast8_t and uint_fast16_t are both defined to be uint32_t, presumably because the 32-bit integer type is faster for most operations (but not always). The main effect of these definitions is to increase the size of the crc_table for the CRC-8 and CRC-16-CCITT algorithms by a factor of 4x or 2x, compared to what they could be.

After collecting the CPU and memory consumption results of various algorithms on different microcontrollers in examples/benchmarks, I found that using the smaller uint8_t or uint16_t did not affect the speed of the algorithms very much (2-14%). Some were got slightly slower, but some actually got slightly faster using the exact uint8_t and uint16_t types, which are supposed to be slower.

The bigger difference is the sizes of the internal crc_table which become a lot smaller when the crc_t becomes smaller. It also seemed potentially confusing for the end user if sizeof(crc_t) returned 4 instead of 1 or 2 when using the CRC-8 or CRC-16-CCITT algorithms.

I concluded that it was better in the Arduino microcontroller environments to make the crc_t type correspond to the exact sized integer types (uint8_t, uint16_t, uint32_t).

The size_t is used as the type of the data_len parameter of the crc_update() or the crc_calculate() function. On 8-bit processors size_t is 2 bytes, and on 32-bit processors size_t is 4 bytes. To calculate the CRC of an array that's longer than 64 kiB long on 8-bit processors, it must be broken down into chunks smaller than 64 kiB and processed through the crc_update() function multiple times. I suspect that this situation will happen only rarely on 8-bit processors which tend to deal with fairly small amounts of data.

<a name="ResourceConsumption"></a>

Resource Consumption

<a name="MemoryBenchmarks"></a>

Memory Benchmarks

I wrote a bunch of scripts in examples/benchmarks/MemoryBenchmark to automatically gather the flash and static RAM consumption of various CRC algorithms on various microcontrollers. The results are summarized in the README.md in that directory. All algorithms (except for xxx_nibblem variants) consume no static RAM, because their lookup tables are located in flash using PROGMEM.

Here are rough flash memory consumption for each algorithm:

<a name="CpuBenchmarks"></a>

CPU Benchmarks

The CPU performance of each CRC algorithm and variant is given in examples/benchmarks/CpuBenchmark as units of microseconds per kiB (1024 bytes).

For 8-bit processors (e.g. Nano, Micro), the numbers are roughly:

For 32-bit processors (e.g. SAMD, ESP8266, ESP32), the numbers are in the range of:

<a name="Recommendations"></a>

Recommendations

TL;DR: Use crc32_nibble in most cases, except on ESP8266 where you should use crc32_nibblem.

The benchmark numbers from CpuBenchmark and MemoryBenchmark are combined into a single place in examples/benchmarks for convenience. Here are 2 samples:

Arduino Nano

+--------------------------------------------------------------+
| CRC algorithm                   |  flash/  ram |  micros/kiB |
|---------------------------------+--------------+-------------|
| crc8_bit                        |     64/    0 |        7808 |
| crc8_nibble                     |    130/    0 |        7356 |
| crc8_nibblem                    |    134/   16 |        7224 |
| crc8_byte                       |    292/    0 |         916 |
|---------------------------------+--------------+-------------|
| crc16ccitt_bit                  |     84/    0 |       11888 |
| crc16ccitt_nibble               |    134/    0 |        5296 |
| crc16ccitt_nibblem              |    138/   32 |        5040 |
| crc16ccitt_byte                 |    562/    0 |        1496 |
|---------------------------------+--------------+-------------|
| crc16modbus_bit                 |    120/    0 |       11692 |
| crc16modbus_nibble              |    132/    0 |        5232 |
| crc16modbus_nibblem             |    134/   32 |        4912 |
| crc16modbus_byte                |    562/    0 |        1496 |
|---------------------------------+--------------+-------------|
| crc32_bit                       |    188/    0 |       18248 |
| crc32_nibble                    |    204/    0 |        7616 |
| crc32_nibblem                   |    208/   64 |        7104 |
| crc32_byte                      |   1106/    0 |        2272 |
|---------------------------------+--------------+-------------|
| CRC32                           |    208/    0 |        7688 |
| Arduino_CRC32                   |   1112/ 1024 |        2144 |
| FastCRC                         |   4262/    0 |        2160 |
+--------------------------------------------------------------+

ESP8266

+--------------------------------------------------------------+
| CRC algorithm                   |  flash/  ram |  micros/kiB |
|---------------------------------+--------------+-------------|
| crc8_bit                        |    128/    0 |        1513 |
| crc8_nibble                     |    144/    0 |         488 |
| crc8_nibblem                    |    112/   16 |         270 |
| crc8_byte                       |    336/    0 |         246 |
|---------------------------------+--------------+-------------|
| crc16ccitt_bit                  |    128/    0 |        1820 |
| crc16ccitt_nibble               |    160/    0 |         669 |
| crc16ccitt_nibblem              |    144/   32 |         283 |
| crc16ccitt_byte                 |    608/    0 |         375 |
|---------------------------------+--------------+-------------|
| crc16modbus_bit                 |    160/    0 |        1937 |
| crc16modbus_nibble              |    160/    0 |         642 |
| crc16modbus_nibblem             |    128/   32 |         244 |
| crc16modbus_byte                |    608/    0 |         375 |
|---------------------------------+--------------+-------------|
| crc32_bit                       |    144/    0 |        1567 |
| crc32_nibble                    |    176/    0 |         591 |
| crc32_nibblem                   |    160/   64 |         244 |
| crc32_byte                      |   1104/    0 |         340 |
|---------------------------------+--------------+-------------|
| CRC32                           |    224/    0 |         834 |
| Arduino_CRC32                   |   1120/ 1024 |         155 |
| FastCRC                         |   4656/    0 |         458 |
+--------------------------------------------------------------+

Comparing the different variants ("bit", "nibble" and "byte"), it seems that the "nibble" variants (4-bit lookup table) offer a good tradeoff between flash memory consumption and CPU speed in the following ways:

The CRC-8 algorithm has the unfortunate property that arrays of zeros of different lengths (e.g. 1 zero or 2 zeros) have the exact same CRC (0). The other two (CRC-16-CCITT and CRC32) are able to distinguish strings of zeroes of different lengths. In terms of flash size and performance, the CRC-8 algorithm is not all that much faster than the CRC-16-CCITT, even on 8-bit processors. For these reasons, the CRC-8 algorithm is not recommended, unless you are really strapped for flash bytes.

The CRC-16-CCITT was selected for this library over the CRC-16 algorithm because CRC-16 suffers the same problem as CRC-8 with regards to arrays of zeros of different lengths. The CRC-16-CCITT uses a non-zero XOR-input which allows it to distinguish different lengths of zeros.

Between the CRC-16-CCITT and CRC-32 algorithms, if we look at the _nibble variants, there is very little difference in flash size and CPU speed, even on 8-bit processors. On 32-bit processors, the CRC-32 is actually faster. The advantage of CRC-32 over CRC-16-CCITT is that 32 bits will be able to detect longer sequences of errors than 16 bits.

The nibblem variant is the same as the nibble variant on all processors except for AVR (small speed improvement) and ESP8266 (1.9X-2.7X speed improvement). The cost is that the 16-64 bytes of static memory is consumed to store the lookup table, instead of keeping them in flash memory.

Putting all these together, here are my recommended algorithms in decreasing order of preference:

  1. crc32_nibble in most situtations for a balance of flash size (~200 bytes) and speed
    • Except on ESP8266, where crc32_nibblem should be used to gain a factor of 2.7X in performance, at a cost of only 64 byes of static RAM (out of a maximum size of 80kB).
  2. crc16ccitt_nibble to save 60 bytes of flash on 8-bit AVR processors, with a reasonable amount of error detection
    • Use crc16ccitt_nibblem if you want a 5% performance increase on an AVR, at a cost of 32 bytes of static memory. In most cases, this is probably not worth it.
  3. crc32_byte if you need the fastest algorithm and you have 1100 bytes of flash to spare
    • Except on ESP8266, where crc32_nibblem is even faster than crc32_byte, while consuming 1 kB of less flash memory, and costing only 64 bytes of extra static memory.
  4. crc16ccitt_bit if you need to implement a very tiny CRC algorithm (90 bytes on an 8-bit AVR processor), and you are not worried about speed
  5. crc8_bit if you need to implement the absolute smallest CRC algorithm (80 bytes on an 8-bit AVR processor), and you are not worried about speed, and you can tolerate high chances of corruption

On the ESP8266, the crc32_nibblem is the hands-down winner. It is faster than all other algorithms, while consuming only 160 bytes of flash and 64 bytes of static ram.

You can consult the results in examples/benchmarks to determine exactly how you want to make the space versus time tradeoff for your specific application.

<a name="Motivation"></a>

Background and Motiviation

Before writing this library, I did not understand how CRC algorithms worked and how they were implemented. I just knew that they calculated a checksum. I had been using the crc32() algorithm from the FastCRC library (https://github.com/FrankBoesing/FastCRC) but when I dug in a little deeper, I discovered that it was configured to use "large tables" by default, which is why it is "fast". But that meant that the crc32() algorithm was pulling in a table of 1024 elements of 4 bytes each, for a total of 4kB.

The crc32() function was being called from my CrcEeprom class (https://github.com/bxparks/AceUtils), which I had included in various applications running on an Arduino Nano or Sparkfun Pro Micro with only 32kB of flash. Due to my ignorance, I was using at least 1/8 of my flash memory budget just to calculate the CRC32!

I decided to figure out how to write my own CRC routines. The best reference I found was A Painless Guide to CRC Error Detection Algorithms by Ross Williams written in 1993. Once I read that, I could understand how a code generator such as pycrc (https://pycrc.org/) worked. For each algorithm type (with a given polynomial generator), the pycrc code can generate multiple implementations. The 3 that seemed most useful in the context of small memory Arduino microcontrollers were:

I calculated the flash and static memory consumption of each algorithm using examples/benchmarks/MemoryBenchmark. From those benchmarks, I can see that I am able to reduce the flash memory usage of the CrcEeprom class by a least 4kB by using a CRC algorithm that consumes only about 150-250 bytes (either the CRC16CCITT or CRC32 algorithm using a 4-bit lookup table).

<a name="OtherLibraries"></a>

Other CRC Libraries

I did a quick survey of existing CRC libraries for Arduino, before deciding to write my own. Part of the motiation was that I wanted to learn this stuff. The other part was that the existing libraries did not offer me enough control over space and time tradeoffs.

Some platforms include an implementation of a CRC algorithm in a core header or an example file:

<a name="Bugs"></a>

Bugs and Limitations

None that I know of right now.

<a name="SystemRequirements"></a>

System Requirements

<a name="Hardware"></a>

Hardware

Tier 1: Fully supported

These boards are tested on each release:

Tier 2: Should work

These boards should work but I don't test them as often:

Tier 3: May work, but not supported

<a name="ToolChain"></a>

Tool Chain

It should work with PlatformIO but I have not tested it.

The library works on Linux or MacOS (using both g++ and clang++ compilers) using the EpoxyDuino emulation layer.

<a name="OperatingSystem"></a>

Operating System

I use Ubuntu 22.04 for the vast majority of my development. I expect that the library will work fine under MacOS and Windows, but I have not tested them.

The generator script in ./tools/generate.sh has only been tested under Ubuntu 20.04 and 22.04.

<a name="License"></a>

License

MIT License

<a name="FeedbackAndSupport"></a>

Feedback and Support

If you have any questions, comments, or feature requests for this library, please use the GitHub Discussions for this project. If you have a bug report, please file a ticket in GitHub Issues. Feature requests should go into Discussions first because they often have alternative solutions which are useful to remain visible, instead of disappearing from the default view of the Issue tracker after the ticket is closed.

Please refrain from emailing me directly unless the content is sensitive. The problem with email is that I cannot reference the email conversation when other people ask similar questions later.

<a name="Authors"></a>

Authors

Created by Brian T. Park (brian@xparks.net).