CRC32

Question

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

我已经使用上述多项式实现了 CRC32 值的正确 table。我生成 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

使用右移 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);
}

Answer 2

你的数组太短了一个字，因此覆盖了分配的内存。必须是：

#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 章中的描述在扩充消息上实现 table 方法（需要在代码末尾进行另外四次 CRC 迭代），那么您需要先阅读文档中的这些重要说明：

Note: The initial register value for this algorithm must be the initial value of the register for the previous algorithm fed through the table four times. Note: The table is such that if the previous algorithm used 0, the new algorithm will too.

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

    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 的回答。

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

CRC32 - wrong checksum using TABLE algorithm and 04C11DB7 polynomial

c

crc