Fast CRC algorithm?

Question

I want to create a 32-bit number out of an ASCII-string. CRC32 algorithm is exactly what I'm looking for, but I can't use it because the table it requires is way too huge (it is for an embedded system where resources are VERY rare).

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

Answer 1

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

Here is a short CRC32 using either the Castagnoli polynomial (same one as used by the Intel crc32 instruction), or the Ethernet polynomial (same one 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 should be zero. The routine can be called successively with chunks of the data to update the CRC. You can unroll the inner loop for speed, though your compiler might do that for you anyway.

Answer 2

Obviously the biggest lookup table will bring the best performance, but you can use any (smaller) table for 16,8 or 4bit lookups.

So the table sizes are for crc32:

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

The 4bit table is four times slower than the 16bit table.
What you should use depends on your speed requirements.

As Luka Rahne mentions it's a good idea to put a table to the flash memory, but on many platforms it's not enough to use the const keyword.
Most often you need to place the table into a section placed in flash, by modifying your linker command file.