關于STM32內置CRC模塊算法的討論

STM32

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

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

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

香水城 發表于 2009-4-14 22:53

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

20樓： 關于CRC算法

關于CRC算法，知其然，如果再知其所以然，事情就會清楚了。CRC算法，最重要的參數當然是生成多項式（CRCPolynomial），但（余數）初值和CRC數據最高位的位置也是很重要的兩個參數，而這兩個參數需要根據具體情況具體分析的。初值一般是全0或者全1，CRC數據最高位一般在最低字節的最低位或者最高位。   CRC算法，作為一種檢錯算法，它的著眼點是出錯概率高地方的錯誤，這在一定程度上決定了后兩個參數。下面舉例來說明。 1.串口通信在通信電纜的出錯概率高，而串口數據是從LSb先發送，所以比較合理的做法是CRC數據最高位是第1個被發送字節的最低位。如果發送的數據是"123"－0x31 0x32 0x33，那么輸入的CRC數據是 10001100 0100 1100 1100 1100。另外，串口的缺省數據一般是1，那么比較合理的（余數）初值就是全1。 2.SPI（和I2C）通信在串行通信的出錯概率高，而SPI數據（8位）一般是從MSb先發送，所以比較合理的做法是CRC數據最高位是第1個被發送字節的最高位。如果發送的數據是"123"－0x31 0x32 0x33，那么輸入的CRC數據是 00110001 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數據是 00110100 0011 0011 0011 0010 00110001，由于STM32的32位CRC是純32位且STM32是按小端對齊（little endian）的，這也是合理的。

hotpower 發表于 2009-4-15 21:44

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

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

香水城 發表于 2009-4-15 21:58

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

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

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

香水城 發表于 2009-4-15 22:10

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

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

hotpower 發表于 2009-4-15 22:12

40樓： 關于CRC初值的選擇問題

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

香水城 發表于 2009-4-15 22:14

41樓： 如果按照38樓的說法，那個關于Reflect()的由來就得到了印證

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

hotpower 發表于 2009-4-15 22:22

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

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

McuIsp 發表于 2009-4-15 23:21

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

//CopyRight:www.mcuisp.com //版權: 單片機在線編程網 詳細代碼請到www.mcuisp.com下載

香水城 發表于 2009-4-16 08:38

50樓： 謝謝48樓：原來那個主流是個非典應用

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

Netjob 發表于 2009-4-16 09:34

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