Fast CRC algorithm?

Question

I want to create a 32-bit number from an ASCII string. The CRC32 algorithm is exactly what I am looking for, but I can’t use it because the required table is too large (for embedded systems where ressources are very rare).

So: any suggestions for a fast and accurate CRC algorithm? It does not matter when collisions are more likely than with the original CRC32.

Thanks!

Answer 1

CRC implementations use tables for speed. They are not required.

Below is a short CRC32 using either the Castagnoli polynomial (the same as used by Intel crc32) or the Ethernet polynomial (the same as used in zip, gzip, etc.).

#include <stddef.h> #include <stdint.h> /* CRC-32C (iSCSI) polynomial in reversed bit order. */ #define POLY 0x82f63b78 /* CRC-32 (Ethernet, ZIP, etc.) polynomial in reversed bit order. */ /* #define POLY 0xedb88320 */ uint32_t crc32c(uint32_t crc, const unsigned char *buf, size_t len) { int k; crc = ~crc; while (len--) { crc ^= *buf++; for (k = 0; k < 8; k++) crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1; } return ~crc; } 

The initial crc value must be zero. A procedure can be called sequentially chunks of data to update the CRC. You can expand the inner loop for speed, although your compiler can do this for you anyway.

Answer 2

Obviously, the largest lookup table will bring maximum performance, but you can use any (smaller) lookup table for 16.8 or 4 bits.

So, table sizes for crc32:

 16bit-lookup: 4*2^16=256k 8bit-lookup: 4*2^8=1k 4bit-lookup: 4*2^4=64byte 

A 4-bit table is four times slower than a 16-bit table.
What you should use depends on your speed requirements.

According to Luca Rane, it’s a good idea to put the table in flash memory, but on many platforms this is not enough to use the const keyword.
Most often, you need to put the table in a partition placed in flash by modifying the linker command file.