C语言 C 的最终 CRC
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15169387/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
definitive CRC for C
提问by oyvind
Since CRC is so widely used, I'm surprised by having a hard time finding CRC implementations in C.
由于 CRC 使用如此广泛，我很惊讶在 C 中很难找到 CRC 实现。
Is there a "definitive" CRC calculation snippet/algorithm for C, that "everyone" uses? Or: is there a good CRC implementation somebody can vouch for, and point me towards? I'm looking for CRC8 and CRC16 implementations in particular.
是否有“每个人”都使用的 C 的“确定性”CRC 计算片段/算法？或者：是否有一个好的 CRC 实施，有人可以担保，并指出我的方向？我特别在寻找 CRC8 和 CRC16 实现。
Come to think of it, my situation may be a little unconventional. I'm writing C code for Linux, and the code should eventually be ported to a microcontroller. It seems some microcontroller APIs do come with CRC implementations; in any case, I'm looking for a generic software implementation (I read that CRC is originally meant to be hardware implemented).
想想看，我的情况可能有点不合常规。我正在为 Linux 编写 C 代码，代码最终应该移植到微控制器。似乎有些微控制器 API 确实带有 CRC 实现；无论如何，我正在寻找一个通用的软件实现（我读到 CRC 最初是由硬件实现的）。
采纳答案by oyvind
No. There is no "definitive CRC" as CRC represents a set of algorithms based upon polynomials. Various [ambiguous] common names are usually given based on size (e.g. CRC-8, CRC-32). Unfortunately, there are several different versions for most sizes.
不。没有“确定性 CRC”，因为 CRC 表示一组基于多项式的算法。各种[歧义] 通用名称通常根据大小给出（例如 CRC-8、CRC-32）。不幸的是，大多数尺寸都有几个不同的版本。
Wikipedia's Cyclic Redundancy Checkentry lists some common variants, but the correct checksumfor the given domainmust be used or else there will be incompatibilities. (See my comment to Mike's answer for just how confusing this can be!)
维基百科的循环冗余校验条目列出了一些常见的变体，但必须使用给定域的正确校验和，否则会出现不兼容。（请参阅我对迈克回答的评论，了解这有多令人困惑！）
Anyway, pick a suitable implementation and use it - there is no shortage of examples that can be found online. If there happens to be a library that provides a suitable implementation then, by all means, use that. However, there is no "standard" C library for this.
无论如何，选择一个合适的实现并使用它 - 网上不乏可以找到的示例。如果碰巧有一个库提供了合适的实现，那么一定要使用它。但是，没有用于此的“标准”C 库。
Here are a few resources:
以下是一些资源：
- A "CRC16" (CRC-16-CCITT)implementation on AutomationWiki.
- Implementing The CCITT Cyclical Redundancy Checkon Dr Dobbs.
- The IEEE 802.3 Cyclic Redundancy Checkarticle by Chris Borrelli discusses an obsolete Xilinx tool to generate Verilog (i.e. "to hardware") implementations.
- See associated question CRC32 C or C++ implementation- note that some answers relate to "CRC32" (IEEE 802.3) and others to Adler-32.
- The librocklibrary, boost, source for cksumfrom GNU core utils ..
- 一个“CRC16”（CRC16-CCITT）上AutomationWiki实施。
- 对 Dobbs 博士实施 CCITT 循环冗余检查。
- Chris Borrelli 撰写的IEEE 802.3 循环冗余检查文章讨论了一种过时的 Xilinx 工具来生成 Verilog（即“到硬件”）实现。
- 请参阅相关问题CRC32 C or C++ implementation- 请注意，一些答案与“CRC32”（IEEE 802.3）有关，而其他答案与Adler-32 相关。
- 该librock库，提高，源校验和从GNU核心utils的..
回答by Mark Adler
It should not be hard to find CRC implementations in C. You can find a relatively sophisticated implementation of CRC-32 in zlib.
在 C 中找到 CRC 实现应该不难。您可以在zlib 中找到一个相对复杂的 CRC-32 实现。
Here are definitions for several 16-bitand 8-bit CRCs, which use the conventions in this excellent introduction to CRCs.
以下是几个16 位和8 位 CRC 的定义，它们使用了这篇出色的 CRC 介绍中的约定。
Here is a simple implementation of a CRC-8:
这是 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
回答by mpontillo
Not sure about CRC-8 or CRC-16, but there is example CRC-32 code in RFC 1952. This RFC also references the V.42standard, which describes a CRC-16 in section 8.1.1.6.
不确定 CRC-8 或 CRC-16，但RFC 1952 中有示例 CRC-32 代码。此 RFC 还引用了V.42标准，该标准在第 8.1.1.6 节中描述了 CRC-16。
RFC 1952 also states:
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.]
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.]
So there's your CRC-16 and CRC-32, potentially. (just take the two least significant bytes of the CRC-32, that is.)
所以可能有你的 CRC-16 和 CRC-32。（只需取 CRC-32 的两个最低有效字节，即。）
回答by Flip
There are number of different algorithms used to implement CRCs. There is the naive one that does the polynomial division.
有许多不同的算法用于实现 CRC。有一个简单的进行多项式除法。
Hereis a link for various algorithms, in C, for generic 32 bit CRC computations. The author also gives some speed comparisons.
这是各种算法的链接，在 C 中，用于通用 32 位 CRC 计算。作者还给出了一些速度对比。
Koopmanhas a website giving the performances of various CRCs, as well as a guide to the best CRCs for a given packet length.
Koopman有一个网站，提供各种 CRC 的性能，以及给定数据包长度的最佳 CRC 的指南。
