如何配置 CRC table 的计算

Question

那里有很多 CRC 计算示例。移位的简单实现和预先计算的 table 更有效。但是除了影响计算的多项式之外，还有很多 CRC 参数。您可以在此处评估这些参数：http://zorc.breitbandkatze.de/crc.html

这些参数是

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

对于某些 "standard" 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%04x\n", result, expected);
    }
}

Answer 1

您无需反映传入的数据、传入的 CRC 和传出的 CRC，而是简单地反映多项式和运算。您只需要在编写代码时执行一次。反射多项式为 0x8408.

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%04x\n", result, expected);
    }
}

对于一般情况，如果输入数据被反映，那么你反映这个答案中所示的多项式，在底部输入字节，检查低位是否对多项式进行异或运算，然后向上移动。如果未反映输入数据，则按照问题中的代码进行操作，保留多项式不变，在顶部输入字节，检查高位，然后向下移动。

在几乎所有情况下，输出的反射与输入的反射相同。对于所有这些，不需要位反向功能。如果输入和输出均未反映，或者输入和输出均已反映，则保留移位寄存器的结果。在 72 CRCs catalogued at the RevEng site 中只有一个是反映出不同于反映在 (CRC-12/3GPP) 中。在那种情况下，您需要反转输出，因为输入没有反映出来，但输出是。

初始CRC只是移位寄存器的初始内容。您在启动 CRC 时设置一次。最后的异或运算在末尾应用于移位寄存器的内容。如果您有一个一次计算一个 CRC 的函数，您需要在输入函数时也应用最终异或，并将最终异或应用到用户看到的初始值，以便实际的初始值是最终在移位寄存器中的值。

如何配置 CRC table 的计算

How to configure calculation of CRC table

c++

crc

crc16