自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

嵌入式算法之CRC校驗(yàn)算法

作者： 嵌入式系統(tǒng)
開(kāi)發(fā) 前端 算法
數(shù)據(jù)傳輸過(guò)程中差錯(cuò)不可避免，接收方在收到數(shù)據(jù)后，先對(duì)數(shù)據(jù)的準(zhǔn)確性進(jìn)行校驗(yàn)，異常數(shù)據(jù)特殊處理。校驗(yàn)的方式有很多，常見(jiàn)的有CRC循環(huán)冗余校驗(yàn)。

[[350334]]

數(shù)據(jù)傳輸過(guò)程中差錯(cuò)不可避免，接收方在收到數(shù)據(jù)后，先對(duì)數(shù)據(jù)的準(zhǔn)確性進(jìn)行校驗(yàn)，異常數(shù)據(jù)特殊處理。校驗(yàn)的方式有很多，常見(jiàn)的有CRC循環(huán)冗余校驗(yàn)。CRC算法檢錯(cuò)能力強(qiáng)，效率高，是信息通信領(lǐng)域最為普遍的校驗(yàn)方式。CRC校驗(yàn)算法應(yīng)用廣，且實(shí)現(xiàn)算法簡(jiǎn)單，但其背后的涉及的糾錯(cuò)碼的代數(shù)理論，不是一般人可以理解的。所以，在不理解循環(huán)校驗(yàn)原理的基礎(chǔ)上，貿(mào)然分析算法流程是不明智的，根據(jù)源碼倒推實(shí)現(xiàn)流程，也不會(huì)明白為什么要這樣執(zhí)行?一般關(guān)注CRC以應(yīng)用為主，以及為什么都是CRC16算法，得出的結(jié)果卻不同。本文的意圖只是這個(gè)。

1、CRC定義

假設(shè)要發(fā)送996這個(gè)數(shù)字，將其除以7余數(shù)為2，發(fā)送時(shí)將996-2合并后發(fā)出，接收方按同樣運(yùn)算判斷數(shù)據(jù)包是否正確。同樣的源數(shù)據(jù)，因?yàn)槌龜?shù)不同而余數(shù)不同。CRC算法也是因?yàn)轭?lèi)似原理。

CRC算法中參數(shù)解釋如下：

1、除法定為模2除法

2、除數(shù)定為多項(xiàng)式，如x^16+x^12+x^5+1(0x1021) 2^16+2^12+2^5+2^0=65536+4096+32+1= 69665=0x11021 。依據(jù)不可描述的標(biāo)準(zhǔn)，多項(xiàng)式最高位和最低位必須為1，所以一般簡(jiǎn)化為0x1021，忽略最高位，記為Poly。

3、因?yàn)槎囗?xiàng)式長(zhǎng)度不同，一般分為CRC8、CRC16和CRC32，因?yàn)槟?除法簡(jiǎn)化為異或和移位操作，其初始值為Init。

4、還有三個(gè)參數(shù)

RefIn：待測(cè)數(shù)據(jù)的每個(gè)字節(jié)是否按位反轉(zhuǎn)，TRUE或FALSE。

RefOut：在計(jì)算后之后，異或輸出之前，整個(gè)數(shù)據(jù)是否按位反轉(zhuǎn)，TRUE或FALSE。

XorOut：計(jì)算結(jié)果與此參數(shù)異或后得到最終的CRC值。但是任何數(shù)與0異或還是它本身，所以該值為0時(shí)可以忽略。

5、因?yàn)槎囗?xiàng)式Poly，初始值等差異，CRC有不同的版本。理論上是多項(xiàng)式是可以隨意定義的，但是通用的標(biāo)準(zhǔn)多項(xiàng)式是經(jīng)過(guò)數(shù)學(xué)推導(dǎo)的，盡可能的保證不同的數(shù)據(jù)求出的CRC值不相同。

6、參考https://crccalc.com/ 的定義，不同場(chǎng)景使用不同的多項(xiàng)式。

2、CRC算法與模板

通用版的CRC算法如下：

CRC8

  1. //以CRC-8/ITU為參考 
  2. unsigned char CRC8(unsigned char *data, unsigned int len) 
  3. { 
  4.     unsigned char i; 
  5.     unsigned char poly = 0x07;//與表中的Poly列對(duì)應(yīng) 
  6.     unsigned char init = 0x00;//與表中的Init列對(duì)應(yīng) 
  7.  
  8.     unsigned char wChar = 0; 
  9.  
  10.     while (len--) 
  11.     { 
  12.         wChar = *(data++); 
  13.  
  14.         //RefIn為TRUE時(shí)執(zhí)行，FALSE時(shí)刪除 
  15.         //InvertUint8(&wChar,&wChar); 
  16.  
  17.         init ^= wChar; 
  18.         for( i = 0;i < 8;i++) 
  19.         { 
  20.             if(init & 0x80) 
  21.             { 
  22.                 init = (init << 1) ^ poly; 
  23.             } 
  24.             else 
  25.             { 
  26.                 init = init << 1; 
  27.             } 
  28.         } 
  29.     } 
  30.  
  31.     //RefOut為TRUE時(shí)執(zhí)行，FALSE時(shí)刪除 
  32.     //InvertUint8(&init,&init); 
  33.  
  34.     //與XorOut進(jìn)行異或，若為0時(shí)執(zhí)行或不執(zhí)行沒(méi)有區(qū)別 
  35.     init=init^0x55; 
  36.  
  37.     return (init); 
  38.  
  39. } 

CRC16

  1. //以CRC-16/X-25為參考 
  2. unsigned short CRC16(unsigned char *data, unsigned int len) 
  3. { 
  4.     unsigned char i; 
  5.     unsigned short poly = 0x1021;//與表中的Poly列對(duì)應(yīng) 
  6.     unsigned short init = 0xFFFF;//與表中的Init列對(duì)應(yīng) 
  7.     unsigned char wChar = 0; 
  8.  
  9.     while (len--) 
  10.     { 
  11.         wChar = *(data++); 
  12.  
  13.         //RefIn為TRUE時(shí)執(zhí)行，FALSE時(shí)刪除 
  14.         InvertUint8(&wChar,&wChar); 
  15.  
  16.         init ^= (wChar << 8); 
  17.         for( i = 0;i < 8;i++) 
  18.         { 
  19.             if(init & 0x8000) 
  20.             { 
  21.                 init = (init << 1) ^ poly; 
  22.             } 
  23.             else 
  24.             { 
  25.                 init = init << 1; 
  26.             } 
  27.         } 
  28.     } 
  29.  
  30.     //RefOut為TRUE時(shí)執(zhí)行，FALSE時(shí)刪除 
  31.     InvertUint16(&init,&init); 
  32.  
  33.     //與XorOut進(jìn)行異或，若為0時(shí)執(zhí)行或不執(zhí)行沒(méi)有區(qū)別 
  34.     init=init^0xFFFF; 
  35.  
  36.     return (init); 
  37. } 

CRC8和CRC16，根據(jù)不同版本的參數(shù)差異，查表，將模板里的參數(shù)改為對(duì)應(yīng)值，即可得出對(duì)應(yīng)版本的CRC值。其中涉及到數(shù)據(jù)反轉(zhuǎn)的代碼如下：

  1. void InvertUint8(unsigned char *DesBuf, unsigned char *SrcBuf) 
  2. { 
  3.     int i; 
  4.     unsigned char temp = 0; 
  5.  
  6.     for(i = 0; i < 8; i++) 
  7.     { 
  8.         if(SrcBuf[0] & (1 << i)) 
  9.         { 
  10.             temp |= 1 << (7 - i); 
  11.         } 
  12.     } 
  13.     *DesBuf = temp; 
  14. } 
  15.  
  16. void InvertUint16(unsigned short *DesBuf, unsigned short *SrcBuf) 
  17. { 
  18.     int i; 
  19.     unsigned short temp = 0; 
  20.  
  21.     for(i = 0; i < 16; i++) 
  22.     { 
  23.         if(SrcBuf[0] & (1 << i)) 
  24.         { 
  25.             temp |= 1 << (15 - i); 
  26.         } 
  27.     } 
  28.     *DesBuf = temp; 
  29. } 

3、查表

針對(duì)上面的代碼，求解CRC移位異或運(yùn)算的循環(huán)體，對(duì)時(shí)間要求較高的場(chǎng)景，可以提前計(jì)算生成數(shù)值表，以空間換時(shí)間。

  1. //以CRC-8/ITU為例，生成數(shù)組查表 
  2. void creatTable(void) 
  3. { 
  4.     unsigned char i,init; 
  5.     unsigned short j; 
  6.     for(j=0;j<=255;j++) 
  7.     { 
  8.         if(j%16==0) 
  9.         { 
  10.             printf("\r\n"); 
  11.         } 
  12.  
  13.         init=j; 
  14.         for( i = 0;i < 8;i++) 
  15.         { 
  16.             if(init & 0x80) 
  17.             { 
  18.                 init = (init << 1) ^ 0x07;//以實(shí)際poly為準(zhǔn); 
  19.             } 
  20.             else 
  21.             { 
  22.                 init = init << 1; 
  23.             } 
  24.         } 
  25.         printf("0x%02X,", init); 
  26.     } 
  27. } 

確定poly后，假設(shè)init為0-255，求出256個(gè)參數(shù)，轉(zhuǎn)為一維數(shù)組。如上，以CRC-8/ITU為例，生成數(shù)組如下：

  1. unsigned char crcTable[]={  
  2. 0x00,0x07,0x0E,0x09,0x1C,0x1B,0x12,0x15,0x38,0x3F,0x36,0x31,0x24,0x23,0x2A,0x2D,  
  3. 0x70,0x77,0x7E,0x79,0x6C,0x6B,0x62,0x65,0x48,0x4F,0x46,0x41,0x54,0x53,0x5A,0x5D,  
  4. 0xE0,0xE7,0xEE,0xE9,0xFC,0xFB,0xF2,0xF5,0xD8,0xDF,0xD6,0xD1,0xC4,0xC3,0xCA,0xCD,  
  5. 0x90,0x97,0x9E,0x99,0x8C,0x8B,0x82,0x85,0xA8,0xAF,0xA6,0xA1,0xB4,0xB3,0xBA,0xBD,  
  6. 0xC7,0xC0,0xC9,0xCE,0xDB,0xDC,0xD5,0xD2,0xFF,0xF8,0xF1,0xF6,0xE3,0xE4,0xED,0xEA,  
  7. 0xB7,0xB0,0xB9,0xBE,0xAB,0xAC,0xA5,0xA2,0x8F,0x88,0x81,0x86,0x93,0x94,0x9D,0x9A,  
  8. 0x27,0x20,0x29,0x2E,0x3B,0x3C,0x35,0x32,0x1F,0x18,0x11,0x16,0x03,0x04,0x0D,0x0A,  
  9. 0x57,0x50,0x59,0x5E,0x4B,0x4C,0x45,0x42,0x6F,0x68,0x61,0x66,0x73,0x74,0x7D,0x7A,  
  10. 0x89,0x8E,0x87,0x80,0x95,0x92,0x9B,0x9C,0xB1,0xB6,0xBF,0xB8,0xAD,0xAA,0xA3,0xA4,  
  11. 0xF9,0xFE,0xF7,0xF0,0xE5,0xE2,0xEB,0xEC,0xC1,0xC6,0xCF,0xC8,0xDD,0xDA,0xD3,0xD4,  
  12. 0x69,0x6E,0x67,0x60,0x75,0x72,0x7B,0x7C,0x51,0x56,0x5F,0x58,0x4D,0x4A,0x43,0x44,  
  13. 0x19,0x1E,0x17,0x10,0x05,0x02,0x0B,0x0C,0x21,0x26,0x2F,0x28,0x3D,0x3A,0x33,0x34,  
  14. 0x4E,0x49,0x40,0x47,0x52,0x55,0x5C,0x5B,0x76,0x71,0x78,0x7F,0x6A,0x6D,0x64,0x63,  
  15. 0x3E,0x39,0x30,0x37,0x22,0x25,0x2C,0x2B,0x06,0x01,0x08,0x0F,0x1A,0x1D,0x14,0x13,  
  16. 0xAE,0xA9,0xA0,0xA7,0xB2,0xB5,0xBC,0xBB,0x96,0x91,0x98,0x9F,0x8A,0x8D,0x84,0x83,  
  17. 0xDE,0xD9,0xD0,0xD7,0xC2,0xC5,0xCC,0xCB,0xE6,0xE1,0xE8,0xEF,0xFA,0xFD,0xF4,0xF3, }; 

原來(lái)的直接計(jì)算改為查表，如下：

  1. //以CRC-8/ITU為參考 
  2. unsigned char CRC8(unsigned char *data, unsigned int len) 
  3. { 
  4.     unsigned char i; 
  5.     unsigned char poly = 0x07;//與表中的Poly列對(duì)應(yīng) 
  6.     unsigned char init = 0x00;//與表中的Init列對(duì)應(yīng) 
  7.  
  8.     unsigned char wChar = 0; 
  9.  
  10.     while (len--) 
  11.     { 
  12.         wChar = *(data++); 
  13.  
  14.         //RefIn為TRUE時(shí)執(zhí)行，FALSE時(shí)刪除 
  15.         //InvertUint8(&wChar,&wChar); 
  16.  
  17.         init ^= wChar; 
  18.  
  19. /************************************************************/ 
  20. #if 1 
  21.  
  22.         init=crcTable[init];//查表，空間換時(shí)間 
  23. #else 
  24.         for( i = 0;i < 8;i++) 
  25.         { 
  26.             if(init & 0x80) 
  27.             { 
  28.                 init = (init << 1) ^ poly; 
  29.             } 
  30.             else 
  31.             { 
  32.                 init = init << 1; 
  33.             } 
  34.         } 
  35. #endif 
  36. /************************************************************/ 
  37.     } 
  38.  
  39.     //RefOut為TRUE時(shí)執(zhí)行，FALSE時(shí)刪除 
  40.     //InvertUint8(&init,&init); 
  41.  
  42.     //與XorOut進(jìn)行異或，若為0時(shí)執(zhí)行或不執(zhí)行沒(méi)有區(qū)別 
  43.     init=init^0x55; 
  44.  
  45.     return (init); 
  46. } 

對(duì)于CRC16也可以使用查表法。

本文轉(zhuǎn)載自微信公眾號(hào)「嵌入式系統(tǒng)」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系嵌入式系統(tǒng)公眾號(hào)。

 

責(zé)任編輯：武曉燕 來(lái)源： 嵌入式系統(tǒng)
嵌入式算法CRC
相關(guān)推薦

2021-11-05 22:47:44

冒泡排序選擇插入

2022-03-10 08:59:59

傅里葉變換算法系統(tǒng)

2023-03-26 12:41:46

2020-11-03 09:55:33

嵌入式算法夾角

2021-11-29 07:43:08

大數(shù)據(jù)存儲(chǔ)算法

2013-07-25 09:32:26

OpenGL ESAndroid4.3

2022-11-24 11:15:49

IoTLinux設(shè)備樹(shù)機(jī)制

2011-01-14 13:13:23

嵌入式Linux開(kāi)發(fā)

2009-12-09 10:12:28

嵌入式Linux

2009-07-17 16:06:59

ARM嵌入式開(kāi)發(fā)

2011-04-18 11:34:34

嵌入式軟件測(cè)試

2009-12-17 10:33:05

嵌入式Linux

2009-12-16 15:41:40

嵌入式Linux入門(mén)

2011-06-17 08:59:27

QT Embedded Arm

2023-01-15 17:57:01

2009-11-30 16:54:28

微軟

2023-04-27 07:06:18

2020-04-22 11:51:41

物聯(lián)網(wǎng)嵌入式編程IOT

2009-04-23 10:38:27

InnoDB存儲(chǔ)引擎嵌入式

2010-03-26 11:23:59

無(wú)線嵌入式控制技術(shù)
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)