C++ 快速CRC算法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/27939882/
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
Fast CRC algorithm?
提问by Elmi
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).
我想从 ASCII 字符串中创建一个 32 位数字。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 算法有什么建议吗？与原始 CRC32 相比，何时更可能发生冲突并不重要。
Thanks!
谢谢！
回答by Mark Adler
CRC implementations use tables for speed. They are not required.
CRC 实现使用表来提高速度。它们不是必需的。
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.).
这是使用 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;
}
The initial crcvalue 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值应为零。可以使用数据块连续调用该例程以更新 CRC。您可以展开内部循环以提高速度，尽管您的编译器可能会为您执行此操作。
回答by jeb
Obviously the biggest lookup table will bring the best performance, but you can use any (smaller) table for 16,8 or 4bit lookups.
显然最大的查找表会带来最好的性能，但是您可以使用任何（较小的）表进行 16,8 或 4 位查找。
So the table sizes are for crc32:
所以表格大小适用于 crc32：
16bit-lookup: 4*2^16=256k
8bit-lookup: 4*2^8=1k
4bit-lookup: 4*2^4=64byte
The 4bit table is four times slower than the 16bit table.
What you should use depends on your speed requirements.
4 位表比 16 位表慢四倍。
您应该使用什么取决于您的速度要求。
As Luka Rahne mentions it's a good idea to put a table to the flash memory, but on many platforms it's not enough to use the constkeyword.
Most often you need to place the table into a section placed in flash, by modifying your linker command file.
正如 Luka Rahne 提到的，将表放入闪存是个好主意，但在许多平台上，仅使用const关键字是不够的。
大多数情况下，您需要通过修改链接器命令文件将表放入闪存中的节中。
