如何配置CRC表的计算

Question

有很多CRC计算的例子。具有比特移位的简单实现，并且具有预先计算的表的效率更高。但是，除了多项式之外，CRC的许多参数也会影响计算。您可以在此处评估这些参数：http://zorc.breitbandkatze.de/crc.html

这些参数是

• CRC的初始值
• 输入数据的反映
• 输出数据的反映
• CRC的最终XOR值

对于某些"标准"CRC算法，这些参数定义良好，如CRC-16（CCITT）。但也有一些实现使用不同的参数。

我的实现必须与具有CCITT多项式的CRC16兼容（x¹⁶+x²²+x⁵+1）。但是必须反映数据字节和最终CRC。我已经在计算方法中实现了这些反射。但这很耗时。为了获得最佳性能，必须将其从计算中删除。

在初始化方法中，如何计算CRC的反射参数？

编辑：我应该如何单独控制每个参数？我想了解Init函数实际上是如何工作的，以及所有参数是如何实现的。

typedef unsigned char uint8_t;
typedef unsigned short crc;
crc  crcTable[256];
#define WIDTH  (8 * sizeof(crc))
#define TOPBIT (1 << (WIDTH - 1))
#define POLYNOMIAL 0x1021
template<typename t>
t reflect(t v)
{
    t r = 0;
    for (int i = 0; i < (8 * sizeof v); ++i)
    {
        r <<= 1;
        r |= v&1;
        v >>= 1;
    }
    return r;
}
void Init()
{
    crc  remainder;
    for (int dividend = 0; dividend < 256; ++dividend)
    {
        remainder = dividend << (WIDTH - 8);
        for (uint8_t bit = 8; bit > 0; --bit)
        {
            if (remainder & TOPBIT)
                remainder = (remainder << 1) ^ POLYNOMIAL;
            else
                remainder = (remainder << 1);
        }
        crcTable[dividend] = remainder;
    }
}
crc Calculate(const uint8_t *message, int nBytes, crc wOldCRC)
{
    uint8_t data;
    crc remainder = wOldCRC;
    for (int byte = 0; byte < nBytes; ++byte)
    {
        data = reflect(message[byte]) ^ (remainder >> (WIDTH - 8));
        remainder = crcTable[data] ^ (remainder << 8);
    }
    return reflect(remainder);
}
int main()
{
    crc expected = 0x6f91;
    uint8_t pattern[] = "123456789";
    Init();
    crc result = Calculate(pattern, 9, 0xFFFF);
    if (result != expected)
    {
        // this output is not relevant to the question, despite C++ tag
        printf("CRC 0x%04x wrong, expected 0x%04xn", result, expected);
    }
}

Answer 1

您只需反映多项式和运算，而不是反映输入的数据、输入的CRC和输出的CRC。您只需要在编写代码时这样做一次。所反映的多项式是CCD_ 2。

typedef unsigned char uint8_t;
typedef unsigned short crc;
crc  crcTable[256];
#define POLYNOMIAL 0x8408
void Init()
{
    crc  remainder;
    for (int dividend = 0; dividend < 256; ++dividend)
    {
        remainder = dividend;
        for (uint8_t bit = 8; bit > 0; --bit)
        {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ POLYNOMIAL;
            else
                remainder = (remainder >> 1);
        }
        crcTable[dividend] = remainder;
    }
}
crc Calculate(const uint8_t *message, int nBytes, crc wOldCRC)
{
    uint8_t data;
    crc remainder = wOldCRC;
    for (int byte = 0; byte < nBytes; ++byte)
    {
        data = message[byte] ^ remainder;
        remainder = crcTable[data] ^ (remainder >> 8);
    }
    return remainder;
}
int main()
{
    crc expected = 0x6f91;
    uint8_t pattern[] = "123456789";
    Init();
    crc result = Calculate(pattern, 9, 0xFFFF);
    if (result != expected)
    {
        // this output is not relevant to the question, despite C++ tag
        printf("CRC 0x%04x wrong, expected 0x%04xn", result, expected);
    }
}

对于一般情况，如果反映了输入数据，则反映如本答案所示的多项式，输入底部的字节，检查低位是否独占多项式，然后向上移位。如果输入数据没有反映出来，那么你就按照问题中的代码来做，保持多项式不变，输入顶部的字节，检查高位，然后向下移位。

在几乎所有情况下，输出的反射与输入的反射相同。对于所有这些，不需要位反向函数。如果输入和输出都未反映，或者输入和输出均反映，则可以保持移位寄存器的结果不变。在RevEng网站编目的72个CRC中，只有一个是反射出不同于反射入（CRC-12/3GPP）。在这种情况下，您需要对输出进行位反转，因为输入没有被反映，但输出是。

初始CRC只是移位寄存器的初始内容。您可以在启动CRC时设置一次。最后的异或应用于最后的移位寄存器内容。如果你有一个函数一次计算一个CRC，你需要在输入函数时应用最终的互斥或，还需要将最终的互斥应用于用户看到的初始值，这样实际的初始值就是最终在移位寄存器中的值。