如何配置CRC表的计算 [英] How to confgure calculation of CRC table
问题描述
有很多CRC计算示例。使用预计算表，位移和更高效的简单实现。但是，除了影响计算的多项式之外，还有很多CRC的参数。您可以在此处评估这些参数： http://zorc.breitbandkatze.de/crc.html
这些参数是
- CRC的初始值
- 输入数据的反射
- 输出数据的反映
- CRC的最终异或值
对于某些标准CRC算法，这些参数被很好地定义，如CRC-16（CCITT）。但是有一些实现使用不同的参数。
我的实现必须与具有CCITT多项式的CRC16兼容（x 16 + x 12 + x 5 + 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 <
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 = < 1）^ POLYNOMIAL;
else
remainder =（remainder<< 1）;
}
crcTable [dividend] = remainder;
}
}
crc计算（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]）^（remaining> 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）
{
//此输出与问题无关，尽管使用C ++标记
printf（CRC 0x％04x wrong ，expected 0x％04x\\\
，result，expected）;
}
}
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 = 1）^ POLYNOMIAL;
else
remainder =（remainder>> 1）;
}
crcTable [dividend] = remainder;
}
}
crc计算（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 = crcTable [data] ^（remainder>> 8）;
}
return remaining;
}
int main（）
{
crc expected = 0x6f91;
uint8_t pattern [] =123456789;
Init（）;
crc result = Calculate（pattern，9，0xFFFF）;
if（result！= expected）
{
//此输出与问题无关，尽管使用C ++标记
printf（CRC 0x％04x wrong ，expected 0x％04x\\\
，result，expected）;
}
}
对于一般情况，如果反映输入数据，那么您反映如此答案所示的多项式，将底部的字节馈入，检查低位用于排除多项式，并向上移位。如果没有反映输入数据，那么就像你的问题中的代码一样，按照原样保留多项式，在顶部输入字节，检查高位并向下移动。
在几乎所有情况下，输出的反射与输入的反射相同。对于所有这些，不需要位反向功能。如果输入和输出都未反映，或者如果输入和输出都反映，则将移位寄存器的结果保留。只有在RevEng网站编目的72个CRC的其中一个是反映出不同的从反射（CRC-12 / 3GPP）。在这种情况下，您需要将输出位反转，因为输入未反映，但输出为。
初始CRC仅仅是移位的初始内容寄存器。在启动CRC时设置一次。最终的异或被应用于结束处的移位寄存器内容。如果你有一个函数一次计算一个CRC，你需要应用最终的异或，或者当输入函数时，也应用最终的异或或用户看到的初始值，因此实际的初始值是移位寄存器中的结果。
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
These parameters are
- initial value of CRC
- reflection of input data
- reflection of output data
- final XOR value for CRC
For some "standard" CRC algorithm these parameters are well defined, like CRC-16 (CCITT). But there are some implementations that use different parameters.
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.
How can the reflection parameters of the CRC be calculated in the initialization method?
Edit: 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);
}
}
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.
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.
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屋！
