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 systems where ressources are VERY rare).

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

Thanks!

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.