23

由于 CRC 被广泛使用，我很惊讶在 C 中很难找到 CRC 实现。

是否有“每个人”都使用的 C 的“确定性”CRC 计算片段/算法？或者：是否有人可以担保并指出我的良好 CRC 实施？我正在寻找特别是 CRC8 和 CRC16 的实现。

仔细想想，我的情况可能有点不合常规。我正在为 Linux 编写 C 代码，代码最终应该移植到微控制器上。似乎某些微控制器 API 确实带有 CRC 实现；无论如何，我正在寻找一个通用的软件实现（我读到 CRC 最初是为了硬件实现）。

4

4 回答 4

32

在 C 中找到 CRC 实现应该不难。您可以在zlib中找到相对复杂的 CRC-32 实现。

下面是几个16 位和8 位 CRC的定义，它们使用了这本出色的 CRC 简介中的约定。

下面是 CRC-8 的简单实现：

// 8-bit CRC using the polynomial x^8+x^6+x^3+x^2+1, 0x14D.
// Chosen based on Koopman, et al. (0xA6 in his notation = 0x14D >> 1):
// http://www.ece.cmu.edu/~koopman/roses/dsn04/koopman04_crc_poly_embedded.pdf
//
// This implementation is reflected, processing the least-significant bit of the
// input first, has an initial CRC register value of 0xff, and exclusive-or's
// the final register value with 0xff. As a result the CRC of an empty string,
// and therefore the initial CRC value, is zero.
//
// The standard description of this CRC is:
// width=8 poly=0x4d init=0xff refin=true refout=true xorout=0xff check=0xd8
// name="CRC-8/KOOP"

static unsigned char const crc8_table[] = {
    0xea, 0xd4, 0x96, 0xa8, 0x12, 0x2c, 0x6e, 0x50, 0x7f, 0x41, 0x03, 0x3d,
    0x87, 0xb9, 0xfb, 0xc5, 0xa5, 0x9b, 0xd9, 0xe7, 0x5d, 0x63, 0x21, 0x1f,
    0x30, 0x0e, 0x4c, 0x72, 0xc8, 0xf6, 0xb4, 0x8a, 0x74, 0x4a, 0x08, 0x36,
    0x8c, 0xb2, 0xf0, 0xce, 0xe1, 0xdf, 0x9d, 0xa3, 0x19, 0x27, 0x65, 0x5b,
    0x3b, 0x05, 0x47, 0x79, 0xc3, 0xfd, 0xbf, 0x81, 0xae, 0x90, 0xd2, 0xec,
    0x56, 0x68, 0x2a, 0x14, 0xb3, 0x8d, 0xcf, 0xf1, 0x4b, 0x75, 0x37, 0x09,
    0x26, 0x18, 0x5a, 0x64, 0xde, 0xe0, 0xa2, 0x9c, 0xfc, 0xc2, 0x80, 0xbe,
    0x04, 0x3a, 0x78, 0x46, 0x69, 0x57, 0x15, 0x2b, 0x91, 0xaf, 0xed, 0xd3,
    0x2d, 0x13, 0x51, 0x6f, 0xd5, 0xeb, 0xa9, 0x97, 0xb8, 0x86, 0xc4, 0xfa,
    0x40, 0x7e, 0x3c, 0x02, 0x62, 0x5c, 0x1e, 0x20, 0x9a, 0xa4, 0xe6, 0xd8,
    0xf7, 0xc9, 0x8b, 0xb5, 0x0f, 0x31, 0x73, 0x4d, 0x58, 0x66, 0x24, 0x1a,
    0xa0, 0x9e, 0xdc, 0xe2, 0xcd, 0xf3, 0xb1, 0x8f, 0x35, 0x0b, 0x49, 0x77,
    0x17, 0x29, 0x6b, 0x55, 0xef, 0xd1, 0x93, 0xad, 0x82, 0xbc, 0xfe, 0xc0,
    0x7a, 0x44, 0x06, 0x38, 0xc6, 0xf8, 0xba, 0x84, 0x3e, 0x00, 0x42, 0x7c,
    0x53, 0x6d, 0x2f, 0x11, 0xab, 0x95, 0xd7, 0xe9, 0x89, 0xb7, 0xf5, 0xcb,
    0x71, 0x4f, 0x0d, 0x33, 0x1c, 0x22, 0x60, 0x5e, 0xe4, 0xda, 0x98, 0xa6,
    0x01, 0x3f, 0x7d, 0x43, 0xf9, 0xc7, 0x85, 0xbb, 0x94, 0xaa, 0xe8, 0xd6,
    0x6c, 0x52, 0x10, 0x2e, 0x4e, 0x70, 0x32, 0x0c, 0xb6, 0x88, 0xca, 0xf4,
    0xdb, 0xe5, 0xa7, 0x99, 0x23, 0x1d, 0x5f, 0x61, 0x9f, 0xa1, 0xe3, 0xdd,
    0x67, 0x59, 0x1b, 0x25, 0x0a, 0x34, 0x76, 0x48, 0xf2, 0xcc, 0x8e, 0xb0,
    0xd0, 0xee, 0xac, 0x92, 0x28, 0x16, 0x54, 0x6a, 0x45, 0x7b, 0x39, 0x07,
    0xbd, 0x83, 0xc1, 0xff};

#include <stddef.h>

// Return the CRC-8 of data[0..len-1] applied to the seed crc. This permits the
// calculation of a CRC a chunk at a time, using the previously returned value
// for the next seed. If data is NULL, then return the initial seed. See the
// test code for an example of the proper usage.
unsigned crc8(unsigned crc, unsigned char const *data, size_t len)
{
    if (data == NULL)
        return 0;
    crc &= 0xff;
    unsigned char const *end = data + len;
    while (data < end)
        crc = crc8_table[crc ^ *data++];
    return crc;
}

// crc8_slow() is an equivalent bit-wise implementation of crc8() that does not
// need a table, and which can be used to generate crc8_table[]. Entry k in the
// table is the CRC-8 of the single byte k, with an initial crc value of zero.
// 0xb2 is the bit reflection of 0x4d, the polynomial coefficients below x^8.
unsigned crc8_slow(unsigned crc, unsigned char const *data, size_t len)
{
    if (data == NULL)
        return 0;
    crc = ~crc & 0xff;
    while (len--) {
        crc ^= *data++;
        for (unsigned k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ 0xb2 : crc >> 1;
    }
    return crc ^ 0xff;
}

#ifdef TEST
#include <stdio.h>
#define CHUNK 16384

int main(void) {
    unsigned char buf[CHUNK];
    unsigned crc = crc8(0, NULL, 0);
    size_t len;
    do {
        len = fread(buf, 1, CHUNK, stdin);
        crc = crc8(crc, buf, len);
    } while (len == CHUNK);
    printf("%#02x\n", crc);
    return 0;
}
#endif
于 2013-03-02T07:20:06.150 回答
15

不，没有“确定的 CRC”，因为 CRC 代表一组基于多项式的算法。通常根据大小给出各种[模棱两可的]通用名称（例如CRC-8、CRC-32）。不幸的是，大多数尺寸都有几个不同的版本。

Wikipedia 的Cyclic Redundancy Check条目列出了一些常见的变体，但必须使用给定域的正确校验和，否则会出现不兼容性。（请参阅我对迈克的回答的评论，了解这有多么令人困惑！）

无论如何，选择一个合适的实现并使用它——网上不乏可以找到的示例。如果碰巧有一个库提供了合适的实现，那么一定要使用它。但是，没有为此的“标准”C 库。

这里有一些资源：

于 2013-03-02T00:57:27.460 回答
2

不确定 CRC-8 或 CRC-16，但RFC 1952中有示例 CRC-32 代码。该 RFC 还引用了V.42标准，该标准在第 8.1.1.6 节中描述了 CRC-16。

RFC 1952 还指出：

        If FHCRC is set, a CRC16 for the gzip header is present,
        immediately before the compressed data. The CRC16 consists
        of the two least significant bytes of the CRC32 for all
        bytes of the gzip header up to and not including the CRC16.
        [The FHCRC bit was never set by versions of gzip up to
        1.2.4, even though it was documented with a different
        meaning in gzip 1.2.4.]

所以可能有你的 CRC-16 和 CRC-32。（即只取 CRC-32 的两个最低有效字节。）

于 2013-03-02T01:03:07.040 回答
1

有许多不同的算法用于实现 CRC。有一个简单的进行多项式除法。

这是 C 语言中用于通用 32 位 CRC 计算的各种算法的链接。作者还给出了一些速度对比。

Koopman有一个网站，提供各种 CRC 的性能，以及给定数据包长度的最佳 CRC​​ 指南。

于 2016-10-26T06:46:21.823 回答