快速CRC算法？

Question

我想用ASCII字符串创建一个32位数字.CRC32算法正是我正在寻找的,但我不能使用它,因为它需要的表太大了(它适用于资源很少的嵌入式系统).

那么:对快速而纤薄的CRC算法的任何建议？与原始CRC32相比,何时碰撞更可能无关紧要.

谢谢!

Answer 1

CRC实现使用表来提高速度.它们不是必需的.

这是一个简短的CRC32,使用Castagnoli多项式(与Intel crc32指令使用的相同)或以太网多项式(与zip,gzip等中使用的相同).

#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;
}

初始crc值应为零.可以使用数据块连续调用该例程以更新CRC.您可以展开内部循环以获得速度,尽管您的编译器可能会为您执行此操作.