原创关于STM32内置CRC模块算法的讨论

 2009-4-16 12:10  8643 14 14 分类: MCU/ 嵌入式

有人提出STM32内置CRC模块的算法，与网上常见的CRC32计算工具得出的结果不相符，因此提出质疑：STM32的CRC模块是否非标准、是否偷工减料。

针对这样的质疑，大家进行了一些讨论和论证，最后发现网上常见的CRC32计算工具，对输入输出数据进行了倒置变换(字节的最高位至最低位对调)，属于一种特殊的算法。

下面摘录了一些主要的讨论。

香水城 发表于 2009-4-14 22:53 ST MCU ←返回版面

10楼： 6楼这位朋友：你先不要嘲笑谁

请先把你的好几个PC校验文件的计算程序亮出来看看，我的计算算法已经摆出来了，大家可以对比一下谁对谁错。

我在网上找到一些有关的资料，在此分享一下，也作为我给出的算法的佐证：

1）实用资料——CRC计算方法--春阳频道——这里描述了CRC16的计算方法，但同样适合于其它多项式算法。这里同时提出需要初始化计算余数为0xFFFF。

2）CRC计算方法与C实现——在这篇文章的第2部分(硬件电路的实现方法)，也明确提出“编码、解码前将各位初始化为1”。

3）下面这段话是我从USB 1.1协议文本的8.3.5节中抄下来的，这里也明确写明初始化为全'1'，和数据高位先参与计算的原则：
For CRC generation and checking, the shift registers in the generator and checker are seeded with an all ones
pattern. For each data bit sent or received, the high order bit of the current remainder is XORed with
the data bit and then the remainder is shifted left one bit and the low-order bit set to zero. If the result of
that XOR is one, then the remainder is XORed with the generator polynomial.

我相信你还可以从网上搜索出很多这样的说明，我无法评判网上那些程序的正确性，但我可以证明我给出的程序是正确的。

ijk 发表于 2009-4-15 10:46 ST MCU ←返回版面

20楼：关于CRC算法

  关于CRC算法，知其然，如果再知其所以然，事情就会清楚了。CRC算法，最重要的参数当然是生成多项式（CRC Polynomial），但（余数）初值和CRC数据最高位的位置也是很重要的两个参数，而这两个参数需要根据具体情况具体分析的。初值一般是全0或者全1，CRC数据最高位一般在最低字节的最低位或者最高位。

  CRC算法，作为一种检错算法，它的着眼点是出错概率高地方的错误，这在一定程度上决定了后两个参数。下面举例来说明。

1.串口通信在通信电缆的出错概率高，而串口数据是从LSb先发送，所以比较合理的做法是 CRC数据最高位是第1个被发送字节的最低位。如果发送的数据是"123"－0x31 0x32 0x33，那么输入的CRC数据是 1000 1100 0100 1100 1100 1100。另外，串口的缺省数据一般是1，那么比较合理的（余数）初值就是全1。

2.SPI（和I2C）通信在串行通信的出错概率高，而SPI数据（8位）一般是从MSb先发送，所以比较合理的做法是 CRC数据最高位是第1个被发送字节的最高位。如果发送的数据是"123"－0x31 0x32 0x33，那么输入的CRC数据是 0011 0001 0011 0010 0011 0011。另外，SPI的没有缺省数据，那么（余数）初值设置为全0或者全1都可以。

3.存储介质是FLASH（包括NAND、NOR、SPI FLASH），由于缺省数据（在擦除后）
是全1，比较合理的（余数）初值就是全1。

4.存储介质是硬盘，由于缺省数据（买来时）是全0，比较合理的（余数）初值就是全0。

问：SPI FLASH，比较合理的参数是什么？
答：如上所述，比较合理的（余数）初值是全1。
比较合理的做法是 CRC数据最高位是第1个字节的最高位；如果
SPI数据（8位）是从LSb先发送，比较合理的做法是 CRC数据最高位是第1个字节的最低位。

  对于STM32的32位CRC，如果假定它的一个主要目的是为了校验往内部FLASH
存储数据的可靠性，那么（余数）初值是全1当然是比较合理的。
由于STM32的32位CRC是纯32位，即每次必须输入32位的数，所以如果数据不到
32位，应该往低位用1来填充比较合理；另外，如果输入数据是"1234"－0x31 0x32 0x33 0x34，那么输入的CRC数据是 0011 0100 0011 0011 0011 0010 0011 0001，由于STM32的32位CRC是纯32位且STM32是按小端对齐（little endian）的，这也是合理的。

hotpower 发表于 2009-4-15 21:44 ST MCU ←返回版面

36楼：菜农玩了多年的CRC，它的精华就是“初值、权和方向”~~~

其他都不是CRC之本~~~

CRC在数学上可以论证为可逆和不可逆2种~~~

菜农做手脚后就全部可逆了~~~

由于“权”太乱，所以俺的CRC为“权开放”~~~

香水城 发表于 2009-4-15 21:58 ST MCU ←返回版面

37楼：找到一个文档似乎说明了这个Reflect()的由来

我在2楼曾经说过不太清楚这个Reflect()的作用，现在在网上找到一个资料，里面介绍了这个Reflect()的由来，不知道正确与否，拿出来给大家分享评判：

资料地址：A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS

所有CRC的计算都是按照数据的高位在先的原则进行，上述这份资料(11节)中说因为UART是先发送字节的最低位，因此设计UART的工程师按照传输线上数据位的顺序，设计了CRC的计算电路。如果这样的计算方式只是局限在芯片的硬件层次，不会产生什么问题，但后来到了与计算机通信时发生了数据位反转的问题，结果就出现了这个Reflect()函数，并被引入了CRC的软件算法中。

从所有对CRC计算的文字描述来看，显然都没有这个Reflect()的操作，因此上述的说法是有一定的可信度的。我从网上也下载了一个号称是WinZIP使用的CRC算法，在里面我也看到了这个Reflect()的操作；这再次让我相信WinZIP的实现只是CRC实现的一个个案，而不具有普遍的代表性。

前述资料的作者来自于澳大利亚阿德莱德大学，他也认为这种REFLECTED算法引起了不少的混乱，我相信这种混乱也包括我们这里的讨论。

McuIsp 发表于 2009-4-15 22:09 ST MCU ←返回版面

38楼：各位可以用stm32计算下0x81818181的crc。

结果再与0xffffffff异或。此时stm32应该是跟主流一致的。

感觉stm32与主流实例差别有2点：
1、每个字节的位序相反。stm32f是按32位，高位在先。而主流实例每字节里面是从低位起的。
2、结果出来后，主流实例与0xffffffff异或了。而stm32f没有。

所以stm32f的crc完全可以主流化。只要数据输入后位序处理下，结果出来后异或下。

香水城 发表于 2009-4-15 22:10 ST MCU ←返回版面

39楼：看看大叔34楼贴出的图片，算一个CRC居然也要这么多选项

reverse!
convert!
nondirect <--> direct
"reverse data bytes"
"reverse CRC result before final XOR"

这么多选项足以把所有人搞晕，哪个才是合适的？哪个又是标准？

我至今没有找到所谓权威的标准文件，可以相信大叔的话它的精华就是“初值、权和方向”，其它的东西只能说只要不违反这个原则，存在就是合理的，没有什么标准不标准的问题。

hotpower 发表于 2009-4-15 22:12 ST MCU ←返回版面

40楼：关于CRC初值的选择问题

在任何“左移CRC”中，当选初值为0时，

若输入为0时，CRC结果为0.
若输入为1时，CRC结果为权.

这样“阶级敌人”很好破译“权”~~~

所以，CRC32选择了初值非0~~~

香水城 发表于 2009-4-15 22:14 ST MCU ←返回版面

41楼：如果按照38楼的说法，那个关于Reflect()的由来就得到了印证

而最后这个与0xffffffff异或操作，用软件实现比用硬件实现方便得多，便宜得多。

hotpower 发表于 2009-4-15 22:22 ST MCU ←返回版面

42楼： 30楼的问题就是“方向”~~~左移“硬件成本低廉”~~~

在就是输出的异或0xffffffff~~~
即要增加32个非门~~~

所以，软件的CRC32随便怎么折腾~~~硬件就受不了了~~~

所以，硬件厂家的各种CRC都和菜农的算法吻合不无道理~~~

因为俺的目的：MCU最简洁的指令和最快的速度实现CRCXX的可逆运算~~~

俺相信大鼻子的脑浆一定和俺的颜色一样~~~只不过是“软硬”不同~~~

他的是硬的，俺的是软的~~~

McuIsp 发表于 2009-4-15 23:21 ST MCU ←返回版面

48楼：夜深了，出个解决方案，让stm32f的CRC32主流化：

//CopyRight:www.mcuisp.com
//版权: 单片机在线编程网
详细代码请到www.mcuisp.com下载

香水城 发表于 2009-4-16 08:38 ST MCU ←返回版面

50楼：谢谢48楼：原来那个主流是个非典应用

我已经在37楼给出了说明，现在48楼MCUISP又给出了直接证据，谢谢！

哈哈，可以结帖了。

Netjob 发表于 2009-4-16 09:34 ST MCU ←返回版面

51楼：那就将非典进行到底！

如果要非典（主流）就把下面的FALSE 设为TRUE
要ST的就都设为FALSE
ST的CRC 最后还要异或FINAL_XOR_VALUE
我这样改改：

typedef unsigned long  crc_16_32;

#define CRC_NAME        "CRC-32"
#define POLYNOMIAL        0x04C11DB7L
#define INITIAL_REMAINDER    0xFFFFFFFF
#define FINAL_XOR_VALUE    0xFFFFFFFF
#define REFLECT_DATA    FALSE
#define REFLECT_REMAINDER    FALSE

#if (REFLECT_DATA == TRUE)
#undef  REFLECT_DATA
#define reflect_data(X)    ((crc_16_32) revbit(X))
#else
#undef  REFLECT_DATA
#define reflect_data(X)            (X)
#endif

#if (REFLECT_REMAINDER == TRUE)
#undef  REFLECT_REMAINDER
#define reflect_rmder(X)    ((crc_16_32) revbit(X)^FINAL_XOR_VALUE)
#else
#undef  REFLECT_REMAINDER
#define reflect_rmder(X)    (X)
#endif

crc_16_32 revbit(crc_16_32 data)
{
  asm("rbit r0,r0");
  return data;
};

crc_16_32 cal_crc(crc_16_32 *ptr, int len)
{
    crc_16_32    xbit;
    crc_16_32    data;
    crc_16_32    CRC = 0xFFFFFFFF;    // init
    while (len--) {
        xbit = (crc_16_32)1 << 31;
        data=reflect_data(*ptr++);
        for (int bits = 0; bits < 32; bits++)
        {
            if (CRC & 0x80000000)
            {
                CRC <<= 1;
                CRC ^= POLYNOMIAL;
            }
            else

                CRC <<= 1;
                if (data & xbit)
                {
                  CRC ^= POLYNOMIAL;
                }

            xbit >>= 1;
        }
    }
    return (reflect_rmder(CRC));

}//END SUB

写原创有奖励！2024面包板原创奖励正在进行中