Fast CRC library (uses the built-in crc-module in Teensy3)

Status
Not open for further replies.

Frank B

Senior Member
EDIT: Now AVR-compatible.
EDIT: Added very fast table crc-algorithms in pure c++ for all supported CRCs. The lib is now compatible to all MCUs. For Teensy 3.0 or 3.1, the fast on-chip-hardware is used (because it's still faster!).

For 32BIT, there are two variants with different table-sizes.
The default uses really big tables with a size of 4KB, but it can be switched to smaller tables with 1KB (but a bit slower)
Code:
// Set this to 0 for smaller 32BIT-CRC-Tables:
#define CRC_BIGTABLES 1

Link:http://https://github.com/FrankBoesing/FastCRC

Currently supported CRCs:
8 BIT: SMBUS MAXIM (Table size 256 Bytes)
16 BIT: KERMIT (Alias CRC-16/CCITT, CRC-16/CCITT-TRUE, CRC-CCITT) CCITT-FALSE MCRF4XX MODBUS XMODEM (Alias ZMODEM, CRC-16/ACORN) X25 (Alias CRC-16/IBM-SDLC, CRC-16/ISO-HDLC, CRC-B) and all from _avr_libc (Table size 2KB)
32 BIT: CRC32, CRC-32/ADCCP, PKZIP, ETHERNET, 802.3 CKSUM, CRC-32/POSIX (Table size 4KB or 1KB)

Edit: There was a bug in "SMBUS", the nibbles where reversed. I fixed that.

Old Post:

Hi,

i'm developing a FastCRC Library for Cortex M4 (Teensy3).
(see link above)

Since i've never done that before for Arduino, and the Arduino-world is still new for me, iwould like to ask if somebody could have a look at it
and tell me, if the naming of functions and so on (is there a "style guide" ?) is ok.

Tests, tips and comments are welcome.

Thank you,
Frank.
 
Last edited:
Thanks for the work!
Code looks great to me.
recommendations:
Add comments just above each class method in the cpp file, saying what the purpose is, input, output, parameters, and anything non-obvious like an initialization then multiple calls.
And somewhere, maybe explain how this is using K20 hardware acceleration and the gist of that, and a pointer into a K20 document for more detail.

Serial.flush() - not normally used. Are you doing it to assure the output is finished before starting the timed code loops?

Optional: I tend to use Serial.printf() to simplify, control, and reduce typing!

No style guide. The best work I've seen on docs that are Teensy relevant are at
http://www.airspayce.com/mikem/arduino/RadioHead/

where he spent the time to get doxygen coded. Maybe an overkill for your simpler case.
 
Thanks for making this nice library. Lots of projects need CRC checks.

If you have time for a few quick edits, here are a couple ideas...

I'd recommend using a consistent name, including capitalization, like "FastCRC.cpp" and "FastCRC" for the repository name, and "FastCRC" for the class name. As much as I like seeing Teensy3 promoted, it's probably best to mention Teensy's special CRC hardware in the readme file and any web page that gets created. Long-term, a short and descriptive name for your library will help people find and understand it, especially when looking at a long list of libraries.

The Arduino IDE uses a case sensitive match between the .h file and library's directory name to resolve ambiguous includes, which can happen if another library happens to have any file named FastCRC.h. As a library grows in popularity, that situation can occur if someone tries to copy the files into another directory for a variety of reasons (usually confusion about which copy Arduino is really using).

You'll almost certainly get requests for compatibility with non-Teensy boards. You might use a #else in the main file to compile the non-Teensy code. Many more people are likely to use your library in publicly shared projects if it always works on every board, even if it's only highly optimized on some. It's possible to use a much faster algorithm with lookup tables for the software-only version.

Most libraries have a keywords.txt file to cause Arduino to highlight their keywords. It's simple to just copy another library's file and edit the words. Beware of converting the tab character to multiple spaces, which look the same in most text editors, but Arduino doesn't recognize multiple spaces in keywords.txt.
 
Hi,
thank you both very much !

Today i changed some things, and did the first and (hopefully) last API-Change.

It was very tricky because there is a minor bug in the Kinetis-silicon (Errata ID 2776) which makes it not easier to make a fast API. Finally i found a way, and surprisingly, this gave an additional huge speedup.
Now, all CRC (including 8-bit) are calculated as 32 bit. This means 3/4 less writes to the dataregister.
It is split into 3 classes for 8, 16, and 32 bit.
The link in the first post is changed because a change of the name.

In the next days, i'll do some more documentation (+keywords) and eventually add more CRC Routines.

It would be great if somebody could test it with other ARMs with built-in CRC - if you want to, comment out the defines for teensy at the beginning of the files.
I believe, the crc device is the same on all M4.

Currently, there are 2 8-bit, 5 16-bit and one 32-bit (Ethernet) algos.

For 32 bit, I want to read the manual again to find a way to feed the CRC with DMA.


Thank you,
Frank.
 
Current List of supported CRC calculations:

8 BIT

SMBUS
MAXIM

16 BIT


CCITT-FALSE
KERMIT (Alias CRC-16/CCITT, CRC-16/CCITT-TRUE, CRC-CCITT)
MCRF4XX
MODBUS
XMODEM (Alias ZMODEM, CRC-16/ACORN)
X25 (Alias CRC-16/IBM-SDLC, CRC-16/ISO-HDLC, CRC-B)

32 BIT


CRC32 (Alias CRC-32/ADCCP, PKZIP, ETHERNET, 802.3)
CKSUM (Alias CRC-32/POSIX)

Up to 30 times faster than equivalent functions from Arduino/avr_libc.
All tested with "check"-values from RevEng and should work "out of the box".
If you miss a special CRC, feel free to ask...
 
Last edited:
A very nice library Frank, thanks.
One suggestion though. Can you organize your git repo directory structure in the same way as I have made in this zip file (below) so that it unpacks in such a way that the examples will compile "out of the box"? Then they will also show up in the IDE examples menu.
http://members.shaw.ca/el_supremo/FastCRC.zip

Pete
 
Could the defines of CRC_FLAG_NOREFLECT etc. be placed in FastCRC.h so that a user can call generic() properly?

Pete
 
Hi,


I changed the structure, added some more documentation, and moved the #defines.

Thank you,
Frank.
 
Last edited:
I too have been looking for something like this for my IP stack on the teensy 3.x. This looks like it is something I can totally use. thank you very much.
 
Added very fast table crc-algorithms in pure c++ for all supported CRCs. The lib should now be compatible to all Arduino-MCUs. For Teensy 3.0 or 3.1, the fast on-chip-hardware is used (automatically).
Link in the first post.
 
polynomial/coefficients definitions I found used in Arduino was vague and ambiguous as to which if any standard it complied with.
Risky if you put their CRC code in flash and ship thousands and they change the definition.
So for my work, I put the CRC generator/checker in the project source and don't use Arduino's as it might change.
 
polynomial/coefficients definitions I found used in Arduino was ambiguous as to which if any standard it complied with.
Risky if you put their CRC-16 code in flash and ship thousands and they change the definition.
So for my work, I put the CRC generator/checker in the project source and don't use Arduino's as it might change.
 
Very nice work Frank!

One issue that's probably going to come up when people try to use this on AVR is the size of the tables in RAM. After using ARM so much, I know the AVR PROGMEM and pgm_read_byte are so very painful.... but eventually it's going to come up. Might be worth putting those in?
 
Hi,
It would be great if somebody could test it with other ARMs with built-in CRC - if you want to, comment out the defines for teensy at the beginning of the files.
I believe, the crc device is the same on all M4.

Not sure why you believe that, the CRC block might be the same within the Freescale range, other manufacturers are quite different.

By coincidence I was implementing hardware CRC at work last week for a Freescale DSP, it uses exactly the same CRC block as the Kinetis chips. Your mention of errata had me quickly checking the datasheet!

Nice job with the library. In the perhaps unlikely event a user calls a CRC function from an interrupt, it's worth noting that the hardware CRC is inherently not thread safe.
 
Since i'm using the "official" polynoms and params, they will not change, never.
They are identical to the ones from "Catalogue of parametrised CRC algorithms, CRC RevEng" (http://reveng.sourceforge.net/crc-catalogue/)
This lib is not using anything from arduino, it's "standalone".

The best solution is to comply with ISO - and state exactly what constants in ISO are being used:
Initial value
coefficients
polynomial


It is a large concern when one replicates that Arduino library code in volumes of devices in the field then some Arduino-ite changes it, e.g., to correct the ambiguity.
 
Last edited:
The proper solution is to comply with ISO.

These are fixed algorithms, a fixed input gives the same (correct!) output every time.
There's no guessing or interpretation involved. The parameters are clearly defined. If one gives the wrong results, please tell me - that would be a bug.

If there's an important ISO-algorithm missing, please tell me its polynom & parameters and I'm happy to implement it.


EDIT: in fact, some of them are ISO :)
 
Last edited:
You added:
The best solution is to comply with ISO - and state exactly what constants in ISO are being used:
Initial value
coefficients
polynomial

pls look at the sourcecode.

Example:
Code:
/** CRC32
 * Alias CRC-32/ADCCP, PKZIP, Ethernet, 802.3
 * @param data Pointer to Data
 * @param datalen Length of Data
 * @return CRC value
 */
uint32_t FastCRC32::crc32(const uint8_t *data, const uint16_t datalen)
{
  // [B][I]poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xcbf43926[/I][/B] <- params
  return generic(0x04C11DB7L, 0XFFFFFFFFL, CRC_FLAG_REFLECT | CRC_FLAG_XOR, data, datalen);
}
 
Last edited:
But in the code - there's no reference to the ISO standard for CRC16 where the constants are defined. That's my point. It should cite ISO and that the code complies. So that any OTHER CRC16 per the same ISO standard should interoperate.
 
Added:

https://github.com/FrankBoesing/FastCRC/blob/master/README.md
Code:
8 BIT:

SMBUS
 (poly=0x07 init=0x00 refin=false refout=false xorout=0x00 check=0xf4)
 
MAXIM
 (poly=0x31 init=0x00 refin=true refout=true xorout=0x00  check=0xa1)
 
 
16 BIT:

KERMIT (Alias CRC-16/CCITT, CRC-16/CCITT-TRUE, CRC-CCITT)
 (poly=0x1021 init=0x0000 refin=true refout=true xorout=0x0000 check=0x2189
  Attention: sometimes you'll find byteswapped presentation of result in other implementations)
 
CCITT-FALSE
 (poly=0x1021 init=0xffff refin=false refout=false xorout=0x0000 check=0x29b1)
 
MCRF4XX
 (poly=0x1021 init=0xffff refin=true refout=true xorout=0x0000 check=0x6f91)
 
MODBUS
 (poly=0x8005 init=0xffff refin=true refout=true xorout=0x0000 check=0x4b37)
 
XMODEM (Alias ZMODEM, CRC-16/ACORN)
 (poly=0x1021 init=0x0000 refin=false refout=false xorout=0x0000 check=0x31c3)
 
X25 (Alias CRC-16/IBM-SDLC, CRC-16/ISO-HDLC, CRC-B)
 (poly=0x1021 init=0xffff refin=true refout=true xorout=0xffff check=0x906e)

 
32 BIT:

CRC32, CRC-32/ADCCP, PKZIP, ETHERNET, 802.3
  (poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xcbf43926)
  
CKSUM, CRC-32/POSIX
  (poly=0x04c11db7 init=0x00000000 refin=false refout=false xorout=0xffffffff check=0x765e7680)
 
@Paul,
what do you think, can i use the "new" __flash attribute instead of PROGMEM ?
What's the current AVR GCC version of arduino ?

argh..i really dislike PROGMEM from the bottom of my heart.. :mad:
 
Last edited:
Status
Not open for further replies.
Back
Top