關(guān)于STM32內置CRC模塊算法的討論

STM32

有人提出STM32內置CRC模塊的算法，與網(wǎng)上常見(jiàn)的CRC32計算工具得出的結果不相符，因此提出質(zhì)疑：STM32的CRC模塊是否非標準、是否偷工減料。

針對這樣的質(zhì)疑，大家進(jìn)行了一些討論和論證，最后發(fā)現網(wǎng)上常見(jiàn)的CRC32計算工具，對輸入輸出數據進(jìn)行了倒置變換(字節的最高位至最低位對調)，屬于一種特殊的算法。

下面摘錄了一些主要的討論。

香水城 發(fā)表于 2009-4-14 22:53

10樓： 6樓這位朋友：你先不要嘲笑誰(shuí)

請先把你的好幾個(gè)PC校驗文件的計算程序亮出來(lái)看看，我的計算算法已經(jīng)擺出來(lái)了，大家可以對比一下誰(shuí)對誰(shuí)錯。 我在網(wǎng)上找到一些有關(guān)的資料，在此分享一下，也作為我給出的算法的佐證： 1）實(shí)用資料——CRC計算方法--春陽(yáng)頻道——這里描述了CRC16的計算方法，但同樣適合于其它多項式算法。這里同時(shí)提出需要初始化計算余數為0xFFFF。 2）CRC計算方法與C實(shí)現——在這篇文章的第2部分(硬件電路的實(shí)現方法)，也明確提出“編碼、解碼前將各位初始化為1”。 3）下面這段話(huà)是我從USB 1.1協(xié)議文本的8.3.5節中抄下來(lái)的，這里也明確寫(xiě)明初始化為全'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. 我相信你還可以從網(wǎng)上搜索出很多這樣的說(shuō)明，我無(wú)法評判網(wǎng)上那些程序的正確性，但我可以證明我給出的程序是正確的。

ijk 發(fā)表于 2009-4-15 10:46

20樓： 關(guān)于CRC算法

關(guān)于CRC算法，知其然，如果再知其所以然，事情就會(huì )清楚了。CRC算法，最重要的參數當然是生成多項式（CRCPolynomial），但（余數）初值和CRC數據最高位的位置也是很重要的兩個(gè)參數，而這兩個(gè)參數需要根據具體情況具體分析的。初值一般是全0或者全1，CRC數據最高位一般在最低字節的最低位或者最高位。   CRC算法，作為一種檢錯算法，它的著(zhù)眼點(diǎn)是出錯概率高地方的錯誤，這在一定程度上決定了后兩個(gè)參數。下面舉例來(lái)說(shuō)明。 1.串口通信在通信電纜的出錯概率高，而串口數據是從LSb先發(fā)送，所以比較合理的做法是CRC數據最高位是第1個(gè)被發(fā)送字節的最低位。如果發(fā)送的數據是"123"－0x31 0x32 0x33，那么輸入的CRC數據是 10001100 0100 1100 1100 1100。另外，串口的缺省數據一般是1，那么比較合理的（余數）初值就是全1。 2.SPI（和I2C）通信在串行通信的出錯概率高，而SPI數據（8位）一般是從MSb先發(fā)送，所以比較合理的做法是CRC數據最高位是第1個(gè)被發(fā)送字節的最高位。如果發(fā)送的數據是"123"－0x31 0x32 0x33，那么輸入的CRC數據是 00110001 0011 0010 0011 0011。另外，SPI的沒(méi)有缺省數據，那么（余數）初值設置為全0或者全1都可以。 3.存儲介質(zhì)是FLASH（包括NAND、NOR、SPI FLASH），由于缺省數據（在擦除后） 是全1，比較合理的（余數）初值就是全1。 4.存儲介質(zhì)是硬盤(pán)，由于缺省數據（買(mǎi)來(lái)時(shí)）是全0，比較合理的（余數）初值就是全0。 問(wèn)：SPI FLASH，比較合理的參數是什么？ 答：如上所述，比較合理的（余數）初值是全1。 比較合理的做法是 CRC數據最高位是第1個(gè)字節的最高位；如果 SPI數據（8位）是從LSb先發(fā)送，比較合理的做法是 CRC數據最高位是第1個(gè)字節的最低位。   對于STM32的32位CRC，如果假定它的一個(gè)主要目的是為了校驗往內部FLASH 存儲數據的可靠性，那么（余數）初值是全1當然是比較合理的。 由于STM32的32位CRC是純32位，即每次必須輸入32位的數，所以如果數據不到 32位，應該往低位用1來(lái)填充比較合理；另外，如果輸入數據是"1234"－0x31 0x32 0x33 0x34，那么輸入的CRC數據是 00110100 0011 0011 0011 0010 00110001，由于STM32的32位CRC是純32位且STM32是按小端對齊（little endian）的，這也是合理的。

hotpower 發(fā)表于 2009-4-15 21:44

36樓： 菜農玩了多年的CRC，它的精華就是“初值、權和方向”~~~

其他都不是CRC之本~~~ CRC在數學(xué)上可以論證為可逆和不可逆2種~~~ 菜農做手腳后就全部可逆了~~~ 由于“權”太亂，所以俺的CRC為“權開(kāi)放”~~~

香水城 發(fā)表于 2009-4-15 21:58

37樓： 找到一個(gè)文檔似乎說(shuō)明了這個(gè)Reflect()的由來(lái)

我在2樓曾經(jīng)說(shuō)過(guò)不太清楚這個(gè)Reflect()的作用，現在在網(wǎng)上找到一個(gè)資料，里面介紹了這個(gè)Reflect()的由來(lái)，不知道正確與否，拿出來(lái)給大家分享評判： 資料地址：A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS 所有CRC的計算都是按照數據的高位在先的原則進(jìn)行，上述這份資料(11節)中說(shuō)因為UART是先發(fā)送字節的最低位，因此設計UART的工程師按照傳輸線(xiàn)上數據位的順序，設計了CRC的計算電路。如果這樣的計算方式只是局限在芯片的硬件層次，不會(huì )產(chǎn)生什么問(wèn)題，但后來(lái)到了與計算機通信時(shí)發(fā)生了數據位反轉的問(wèn)題，結果就出現了這個(gè)Reflect()函數，并被引入了CRC的軟件算法中。 從所有對CRC計算的文字描述來(lái)看，顯然都沒(méi)有這個(gè)Reflect()的操作，因此上述的說(shuō)法是有一定的可信度的。我從網(wǎng)上也下載了一個(gè)號稱(chēng)是WinZIP使用的CRC算法，在里面我也看到了這個(gè)Reflect()的操作；這再次讓我相信WinZIP的實(shí)現只是CRC實(shí)現的一個(gè)個(gè)案，而不具有普遍的代表性。 前述資料的作者來(lái)自于澳大利亞阿德萊德大學(xué)，他也認為這種REFLECTED算法引起了不少的混亂，我相信這種混亂也包括我們這里的討論。

McuIsp 發(fā)表于 2009-4-15 22:09

38樓： 各位可以用stm32計算下0x81818181的crc。

結果再與0xffffffff異或。此時(shí)stm32應該是跟主流一致的。 感覺(jué)stm32與主流實(shí)例差別有2點(diǎn)： 1、每個(gè)字節的位序相反。stm32f是按32位，高位在先。而主流實(shí)例每字節里面是從低位起的。 2、結果出來(lái)后，主流實(shí)例與0xffffffff異或了。而stm32f沒(méi)有。 所以stm32f的crc完全可以主流化。只要數據輸入后位序處理下，結果出來(lái)后異或下。

香水城 發(fā)表于 2009-4-15 22:10

39樓： 看看大叔34樓貼出的圖片，算一個(gè)CRC居然也要這么多選項

reverse! convert! nondirect <--> direct "reverse data bytes" "reverse CRC result before final XOR" 這么多選項足以把所有人搞暈，哪個(gè)才是合適的？哪個(gè)又是標準？ 我至今沒(méi)有找到所謂權威的標準文件，可以相信大叔的話(huà)它的精華就是“初值、權和方向”，其它的東西只能說(shuō)只要不違反這個(gè)原則，存在就是合理的，沒(méi)有什么標準不標準的問(wèn)題。

hotpower 發(fā)表于 2009-4-15 22:12

40樓： 關(guān)于CRC初值的選擇問(wèn)題

在任何“左移CRC”中，當選初值為0時(shí)， 若輸入為0時(shí)，CRC結果為0. 若輸入為1時(shí)，CRC結果為權. 這樣“階級敵人”很好破譯“權”~~~ 所以，CRC32選擇了初值非0~~~

香水城 發(fā)表于 2009-4-15 22:14

41樓： 如果按照38樓的說(shuō)法，那個(gè)關(guān)于Reflect()的由來(lái)就得到了印證

而最后這個(gè)與0xffffffff異或操作，用軟件實(shí)現比用硬件實(shí)現方便得多，便宜得多。

hotpower 發(fā)表于 2009-4-15 22:22

42樓： 30樓的問(wèn)題就是“方向”~~~左移“硬件成本低廉”~~~

在就是輸出的異或0xffffffff~~~ 即要增加32個(gè)非門(mén)~~~ 所以，軟件的CRC32隨便怎么折騰~~~硬件就受不了了~~~ 所以，硬件廠(chǎng)家的各種CRC都和菜農的算法吻合不無(wú)道理~~~ 因為俺的目的：MCU最簡(jiǎn)潔的指令和最快的速度實(shí)現CRCXX的可逆運算~~~ 俺相信大鼻子的腦漿一定和俺的顏色一樣~~~只不過(guò)是“軟硬”不同~~~ 他的是硬的，俺的是軟的~~~

McuIsp 發(fā)表于 2009-4-15 23:21

48樓： 夜深了，出個(gè)解決方案，讓stm32f的CRC32主流化：

//CopyRight:www.mcuisp.com //版權: 單片機在線(xiàn)編程網(wǎng) 詳細代碼請到www.mcuisp.com下載

香水城 發(fā)表于 2009-4-16 08:38

50樓： 謝謝48樓：原來(lái)那個(gè)主流是個(gè)非典應用

我已經(jīng)在37樓給出了說(shuō)明，現在48樓MCUISP又給出了直接證據，謝謝！ 哈哈，可以結帖了。

Netjob 發(fā)表于 2009-4-16 09:34

51樓： 那就將非典 進(jìn)行到底！

如果要非典（主流）就把下面的FALSE 設為T(mén)RUE 要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