Products > Programming

Faster alternatives to CRC?

(1/9) > >>

Infraviolet:
I'm trying to implement a CRC checksumming check on an AVR microcontroller.

I'm making a 16 bit checksum from up to 35 bytes of data.

I use a 16 item table of uint16_t values to a table driven CRC algorithm.

The algorithm calls:

uint16_t crc_of_byte(uint16_t crc, uint8_t data_byte){
  uint8_t i;
  i = (crc >> 12) ^ (data_byte >> 4);
  crc = pgm_read_dword_near(table + (i & 0x0f)) ^ (crc <<4);
  i = (crc >> 12) ^ (data_byte >> 0);
  crc = pgm_read_dword_near(table + (i & 0x0f)) ^ (crc <<4);
  return crc;
}

for each byte of the up to 35, with the result of the function being fed back in as crc when it run for the next byte of the array it is calculating the CRC of.

But it seems rather slow, quite a lot of clock cycles per byte to the extent that with a 16MHz clock rate my AVR chips are taking about 6.5us per byte to calculate checksums.

I cannot switch to a 256 element table as that would take too much PROGMEM space.

I'm aware of something called a sliced CRC table, which is apparently faster than normal CRC tables, mentioned at https://pycrc.org/pycrc.html . But I tried generating a CRC table by that method using the very useful python script provided, and it wouldn't do it unless I used a 256 element table anyway.

I am not tied to using a particular CRC polynomial, nor even to using a CRC at all, I could try anything which can detect errors and produce a 2 byte "checksum" for an array up to 35 bytes.

What else could I try for error detection? I'd like methods which would do a good job of catching burst errors, and "sliding" errors*, as well as having the largest easily feasible hamming distance (max number of bit flip errors somewhere throughout a message before you can potentially get a bit flip which makes a corrupted message which still passes the check as if it were valid).

Thank You

*By sliding, I mean, imagine the effect on data if a single bit is missed, and everything following shifts earlier by one bit, or if a phantom bit is added and everything afterwards shifts later by one bit.
121,82,96,3
(
01111001,
01010010,
01100000,
00000011
)
could "slide" to, if an error happened that missed the last bit of 121:
120,164,192,6
(
01111000,
10100100,
11000000,
00000110
)

ataradov:
https://en.wikipedia.org/wiki/Fletcher%27s_checksum is pretty good for detecting bit errors in short messages. It has a few weaknesses, but those are usually not an issues for real applications.

brucehoult:

--- Quote from: Infraviolet on January 05, 2024, 09:37:44 pm ---I cannot switch to a 256 element table as that would take too much PROGMEM space.

--- End quote ---

That seems rather strange as that's only 512 bytes and even the ATTiny25/45/85 series is available with 8K of program space. It will be much faster!

You could switch to a simple xor checksum (multiple CRC-1 streams in parallel), but that won't meet your burst etc requirements.

I don't think you're going to find any algorithm with as good or better protection properties than CRC with lower memory or clock cycles requirements. There's a reason the CRC algorithm is still used after sixty years, though better polynomials are known today than were initially used (e.g. CRC-32C (Castagnoli)).

And of course a 32 bit CRC will give much better protection than a 16 bit CRC.

Berni:
I also like using the fletcher checksum.

It is very fast on MCUs because it is just 2 sum operations. Sure CRC is more efficient in hardware, but that doesn't help unless the MCU has such hardware built in.

brucehoult:

--- Quote from: ataradov on January 05, 2024, 09:58:51 pm ---https://en.wikipedia.org/wiki/Fletcher%27s_checksum is pretty good for detecting bit errors in short messages. It has a few weaknesses, but those are usually not an issues for real applications.

--- End quote ---

Fletcher and Adler are certainly a lot cheaper to compute than CRC, for slightly worse but maybe adequate protection.

You could also look into the much more recent murmurhash, cityhash, farmhash series developed primarily for very fast hashing of relatively short keys for hash tables. There's no reason they can't also be used for data transmission. I guess one thing to watch out for is that they pretty much assume shifts by arbitrary amounts are fast, which is not the case on AVR, unlike on typical ARM/RISC-V implementations.

Navigation

[0] Message Index

[#] Next page