那里有很多 CRC 计算示例。通过位移位实现简单,使用预计算表更高效。但是除了影响计算的多项式之外,还有很多 CRC 参数。您可以在此处评估这些参数:http://zorc.breitbandkatze.de/crc.html
这些参数是
- CRC初值
- 输入数据的反射(reflect)
- 输出数据的反射(reflect)
- CRC 的最终 XOR 值
对于某些“标准”CRC 算法,这些参数定义明确,例如 CRC-16 (CCITT)。但是有一些实现使用不同的参数。
我的实现必须与具有 CCITT 多项式 (x16 + x12 + x5 + 1) 的 CRC16 兼容。但是必须反射(reflect)数据字节和最终的 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);
}
}
最佳答案
您无需反射(reflect)传入的数据、传入的 CRC 和传出的 CRC,而是简单地反射(reflect)多项式和运算。您只需要在编写代码时执行一次。反射多项式是 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);
}
}
对于一般情况,如果反射(reflect)了输入数据,那么您将反射(reflect)此答案中所示的多项式,在底部输入字节,检查低位以对多项式进行异或运算,然后向上移动。如果未反射(reflect)输入数据,则按照问题中的代码执行此操作,将多项式保持原样,将字节送入顶部,检查高位,然后向下移动。
几乎在所有情况下,输出的反射与输入的反射相同。对于所有这些,不需要位反向功能。如果输入和输出均未反射(reflect),或者输入和输出均已反射(reflect),则保留移位寄存器的结果。只有一个 72 CRCs catalogued at the RevEng site 中的 reflect out 不同于 reflect in (CRC-12/3GPP)。在这种情况下,您需要对输出进行位反转,因为输入没有反射(reflect)出来,但输出反射(reflect)出来了。
初始 CRC 只是移位寄存器的初始内容。您在启动 CRC 时设置一次。最后的异或运算在末尾应用于移位寄存器的内容。如果您有一个一次计算一个 CRC 的函数,您需要在输入函数时也应用最终异或,并将最终异或应用到用户看到的初始值,以便实际的初始值是最终在移位寄存器中的值。
关于c++ - 如何配置CRC表的计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28656471/