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

STM32

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

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

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

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

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

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

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

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

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

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

36樓： 菜農(nóng)玩了多年的CRC，它的精華就是“初值、權(quán)和方向”~~~

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在就是輸出的異或0xffffffff~~~ 即要增加32個(gè)非門~~~ 所以，軟件的CRC32隨便怎么折騰~~~硬件就受不了了~~~ 所以，硬件廠家的各種CRC都和菜農(nóng)的算法吻合不無(wú)道理~~~ 因?yàn)榘车哪康模?a href="http://m.54549.cn/keyword/MCU" target="_blank" class="relatedlink">MCU最簡(jiǎn)潔的指令和最快的速度實(shí)現(xiàn)CRCXX的可逆運(yùn)算~~~ 俺相信大鼻子的腦漿一定和俺的顏色一樣~~~只不過(guò)是“軟硬”不同~~~ 他的是硬的，俺的是軟的~~~

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

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

//CopyRight:www.mcuisp.com //版權(quán): 單片機(jī)在線編程網(wǎng) 詳細(xì)代碼請(qǐng)到www.mcuisp.com下載

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

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

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

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

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

如果要非典（主流）就把下面的FALSE 設(shè)為TRUE 要ST的就都設(shè)為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