c-CRC32-使用TABLE算法和04C11DB7多项式的校验和错误

Question

我正在遵循一个关于代码校正算法的无痛指南。(https://zlib.net/crc_v3.txt)我已经设法编写了一个TABLE算法，为增强部分使用了额外的循环(我希望如此(。我正在尝试编写一个使用最广泛的CRC32版本(使用0x04C11DB7多项式(，但我无法获得正确的CRC值。

我已经用提到的多项式获得了CRC32值的正确表格。我生成CRC32的代码(第9章和第10章(：

#include <stdlib.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#define CRC32_BYTE_POSSIBLE_VALUES 255
#define CRC32_LAST_BIT_MASK 0x80000000
#define CRC32_POLYNOMIAL 0x04C11DB7
uint32_t __crc32_table[CRC32_BYTE_POSSIBLE_VALUES] = { 0 };
void __crc32_fill_crc_table() {
uint32_t reg;
uint8_t byte = 0;
for (;;) {
reg = (byte << 24);
for (uint8_t byte_size = 0; byte_size < 8; byte_size++) {
if (reg & CRC32_LAST_BIT_MASK) {
reg <<= 1;
reg ^= CRC32_POLYNOMIAL;
} else {
reg <<= 1;
}
}
__crc32_table[byte] = reg;
if (byte == 255)
break;
else
byte++;
}
}
void __crc32_print_table(uint32_t *arr) {
printf(" 0x%08X ", arr[0]);
for (uint32_t i = 1; i < 256; i++) {
if (!(i % 8))
printf("n");
printf(" 0x%08X ", arr[i]);
}
printf("n");
}
uint8_t inverse_byte(uint8_t byte) {
uint8_t reflected_byte = 0;
for (uint8_t i = 0; i < 8; i++) {
if (byte & (1 << i))
reflected_byte |= (1 << (7 - i));
}
return reflected_byte;
}
uint32_t inverse(uint32_t src) {
uint32_t toret;
for (uint8_t i = 0; i < 32; i++) {
if (src & (1 << i))
toret |= (1 << (31 - i));
}
return toret;
}

uint32_t __crc32_table_approach( unsigned char *data, size_t size) {
uint32_t reg = -1;
uint8_t top_byte;
for (size_t i = 0; i < size; i++) {
top_byte = (uint8_t)(reg >> 24);
reg = (reg << 8) | inverse_byte(data[i]);
reg ^= __crc32_table[top_byte];
}
for (size_t i = 0; i < 4; i++) {
top_byte = (uint8_t) (reg >> 24);
reg = (reg << 8) ;
reg ^= __crc32_table[top_byte];
}
return inverse(reg) ^ -1;
}
uint32_t calc_crc32(unsigned char *data, size_t size) {
if (!__crc32_table[1])
__crc32_fill_crc_table();
__crc32_print_table(__crc32_table);
return __crc32_table_approach(data, size);
}

int main( int argc, char** argv )
{

unsigned char* test = "123456789";
size_t test_len = strlen(test);
uint32_t crc = calc_crc32(test, test_len);
printf("CRC32: 0x%08X", crc);
return 0;
}

逆函数反转UINT32值的位，而函数inverse_byte反转UINT8值的位。

但是对于"123456789"字符串，我得到了错误的校验和。有人能帮我吗？或者提供一些建议？

---

输入字符串：'123456789'

输出CRC:CRC32:0x22016B0A

所需CRC:CRC32:0xCBF43926

Answer 1

您将数组缩短了一个字，因此覆盖了分配的内存。它需要：

#define CRC32_BYTE_POSSIBLE_VALUES 256

尽管这部分可能仍然有效，因为C.

您需要初始化要反转到的变量：

uint32_t toret = 0;

这些线路：

top_byte = (uint8_t)(reg >> 24);
reg = (reg << 8) | inverse_byte(data[i]);

需要：

top_byte = (uint8_t)(reg >> 24) ^ inverse_byte(data[i]);
reg <<= 8;

并且您需要删除以下行：

for (size_t i = 0; i < 4; i++) {
top_byte = (uint8_t) (reg >> 24);
reg = (reg << 8) ;
reg ^= __crc32_table[top_byte];
}

那么你就得到了正确的答案。

如果你想在第9章中描述的增强消息上实现表方法(需要在代码的末尾再重复四次CRC(，那么你需要首先阅读文档中的这些重要注释：

注意：此算法的初始寄存器值必须是上一个算法的寄存器的初始值桌子翻了四次。注：该表是这样的，如果算法使用了0，新算法也会。

要在非增强消息版本中获得与0xffffffff的初始值相同的效果(特别是而不是零(，这就是标准CRC的定义方式，那么您需要找到一个初始值，以便使用CRC对其应用32个零位，从而获得0xffffffff。该值为0x46af6449，通过反转CRC逐位算法获得：

uint32_t x = -1;
for (unsigned i = 0; i < 32; i++)
x = x & 1 ? ((x ^ 0x4c11db7) >> 1) | 0x80000000 : x >> 1;

如果您修复了数组大小和toret初始化错误，并简单地替换：，那么您的代码就会工作

uint32_t reg = -1;

带有：

uint32_t reg = 0x46af6449;

无论是否增强，在执行操作时反转每个输入字节都是浪费时间。相反，你可以也应该只是颠倒计算和多项式。请参阅rcgldr的答案。

Answer 2

使用右移CRC的示例代码(0xedb88320是0x04C11DB7的反映版本(：

#include <iostream>
#include <iomanip>
typedef unsigned char uint8_t;
typedef unsigned int uint32_t;
uint32_t crctbl[256];
void gentbl(void)
{
uint32_t crc;
uint32_t c;
uint32_t i;
for(c = 0; c < 0x100; c++){
crc = c;
for(i = 0; i < 8; i++){
crc = (crc & 1) ? (crc >> 1) ^ 0xedb88320 : (crc >> 1);
}
crctbl[c] = crc;
}
}
uint32_t crc32(uint8_t * bfr, size_t size)
{
uint32_t crc = 0xfffffffful;
while(size--)
crc = (crc >> 8) ^ crctbl[(crc & 0xff) ^ *bfr++];
return(crc ^ 0xfffffffful);
}
int main(int argc, char**argv)
{
uint32_t crc;
uint8_t msg[10] = "123456789";
gentbl();
crc = crc32(msg, 9);
std::cout << "crc " << std::hex << std::setw(8) << std::setfill('0') << crc << std::endl;
return(0);
}