快速CRC算法？ [英] Fast CRC algorithm?

问题描述

我想创建一个32位的数字了一个ASCII字符串。 CRC32算法正是我要找的，但是因为它需要的表是太巨大（这是一个嵌入式系统中ressources是非常罕见的）。

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).

所以：一个快速和超薄CRC算法有什么建议？当collissions比与原CRC32更可能一点也没关系。

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.

谢谢！

推荐答案

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

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

下面是一个使用任一Castagnoli酒店多项式（13759英特尔CRC32指令相同），或以太网多项式（同一个作为拉链使用的gzip等）短CRC32。

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

最初的 CRC 值应为零。该例程可以依次与数据更新的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.

这篇关于快速CRC算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！