如何配置CRC表计算 [英] How to configure calculation of CRC table
问题描述
那里有很多CRC计算示例。带有位移的简单实现，使用预先计算的表更有效。但是多项式旁边还有很多CRC参数会影响计算。您可以在此处评估这些参数： http://zorc.breitbandkatze.de/crc.html
There are a lot of CRC calculation examples out there. Simple implementations with bit shifting and more efficient with a pre-calculated table. But there are also a lot of Parameters of a CRC beside the polynomial that affect the calculation. You can evaluate these parameters here: http://zorc.breitbandkatze.de/crc.html
这些参数是
- CRC的初始值
- 输入数据的反射
- 输出数据的反射
- CRC的最终XOR值
- initial value of CRC
- reflection of input data
- reflection of output data
- final XOR value for CRC
对于某些标准 CRC算法，这些参数已经很好定义，例如CRC-16（CCITT）。但是有些实现使用不同的参数。
For some "standard" CRC algorithm these parameters are well defined, like CRC-16 (CCITT). But there are some implementations that use different parameters.
我的实现必须与具有CCITT多项式的CRC16兼容（x 16 + x 12 + x 5 +1）。但是必须反映数据字节和最终的CRC。我已经在计算方法中实现了这些反射。但这很耗时。为了获得最佳性能，必须将其从计算中删除。
My implementation has to be compatible with a CRC16 with a CCITT polynomial (x16 + x12 + x5 + 1). But the data bytes and the final CRC must be reflected. I have implemented these reflection in the calculation method. But that is time consuming. For best performance it must be removed from the calculation.
如何在初始化方法中计算CRC的反射参数？
How can the reflection parameters of the CRC be calculated in the initialization method?
编辑：我应该如何单独控制每个参数？我想了解 Init 函数的实际工作方式以及所有参数的实现方式。
How should I do to control each of the parameters individually? I would like to understand how the Init function actually works and how all the parameters are implemented.
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);
}
}
推荐答案
反映传入的数据，传入的CRC和传出的CRC，您只需反映多项式和运算即可。编写代码时，只需执行一次。反射的多项式为 0x8408 。
Instead of reflecting the data coming in, and the CRC coming in, and the CRC going out, you simply reflect the polynomial and the operations. You only need to do that once, when you're writing the code. The reflected polynomial is 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);
}
}
对于一般情况，如果反映了输入数据，然后您可以如本答案所示反映多项式，在底部提供字节，检查低位以对多项式进行异或，然后上移。如果未反映输入数据，则可以按照问题代码中的方法进行操作，将多项式保持不变，将字节送入顶部，检查高位，然后向下移位。
For the general case, if the input data is reflected, then you reflect the polynomial as shown in this answer, feed the byte at the bottom, check the low bit for exclusive-oring the polynomial, and shift up. If the input data is not reflected, then you do it as in the code in your question, leaving the polynomial as is, feeding the byte at the top, check the high bit, and shift down.
几乎在所有情况下，输出的反射与输入的反射相同。对于所有这些，都不需要位反转功能。如果输入和输出均未反映，或者输入和输出均已反映，则将移位寄存器的结果保持不变。在RevEng网站上分类的 72个CRC 中，只有一个反映出不同从（CRC-12 / 3GPP）中反映出来。在那种情况下，您需要对输出进行位反转，因为输入没有被反映，但是输出却是。
In nearly all cases, the reflection of the output is the same as the reflection of the input. For all of those, there is no need for a bit reverse function. You leave the result from the shift register as is if both input and output are not reflected, or if both input and output are reflected. In only one of the 72 CRCs catalogued at the RevEng site is the reflect out different from the reflect in (CRC-12/3GPP). In that one case, you need to bit reverse the output since the input is not reflected, but the output is.
初始CRC只是移位的初始内容。寄存器。启动CRC时只需设置一次。最后，最后的异或将应用于移位寄存器的内容。如果您有一次可一次计算CRC的函数，则还需要在输入该函数时应用最终异或，并将该最终异或应用于用户看到的初始值，以便实际的初始值就是移位寄存器中的值。
The initial CRC is simply the initial contents of the shift register. You set that once when starting the CRC. The final exclusive-or is applied to the shift register contents at the end. If you have a function that computes a CRC a piece at a time, you need to apply the final exclusive-or when entering the function as well, and also apply that final exclusive-or to the initial value that the user sees, so that the actual initial value is what ends up in the shift register.
这篇关于如何配置CRC表计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
