快速CRC算法？

Question

我想用 ASCII 字符串创建一个 32 位数字。 CRC32 算法正是我要找的，但我不能使用它，因为它需要的 table 太大了（它适用于资源非常稀缺的嵌入式系统）。

那么：对快速而精简的 CRC 算法有什么建议吗？与原始 CRC32 相比，何时更可能发生冲突并不重要。

Answer 1

显然最大的查找 table 会带来最好的性能，但您可以使用任何（较小的）table 进行 16,8 或 4 位查找。

因此 table 大小适用于 crc32：

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

4位table比16位table慢四倍。
您应该使用什么取决于您的速度要求。

正如 Luka Rahne 提到的，将 table 放入闪存是个好主意，但在许多平台上使用 const 关键字是不够的。
大多数情况下，您需要通过修改链接器命令文件将 table 放入闪存中的一个部分。

Answer 2

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

这是使用 Castagnoli 多项式（与 Intel crc32 指令使用的相同）或以太网多项式（与 zip、gzip 等中使用的相同）的短 CRC32。

#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。您可以展开内部循环以提高速度，尽管您的编译器可能会为您这样做。

快速CRC算法？

Fast CRC algorithm?

c

algorithm

embedded

crc

crc32