使用C語言實(shí)現(xiàn)CRC校驗(yàn)的方法
CRC(Cyclic Redundancy Check)校驗(yàn)應(yīng)用較為廣泛，以前為了處理簡單，在程序中大多數(shù)采用LRC(Longitudinal Redundancy Check)校驗(yàn)，LRC校驗(yàn)很好理解，編程實(shí)現(xiàn)簡單。用了一天時(shí)間研究了CRC的C語言實(shí)現(xiàn)，理解和掌握了基本原理和C語言編程。結(jié)合自己的理解簡單寫下來。
1、CRC簡介
CRC檢驗(yàn)的基本思想是利用線性編碼理論，在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)檢驗(yàn)碼r位(就是CRC碼)，附在信息后面，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共(k+r)位，最后發(fā)送出去。接收端根據(jù)同樣的規(guī)則校驗(yàn)，以確定傳送中是否出錯(cuò)。接收端有兩種處理方式：1、計(jì)算k位序列的CRC碼，與接收到的CRC比較，一致則接收正確。2、計(jì)算整個(gè)k+r位的CRC碼，若為0，則接收正確。
CRC碼有多種檢驗(yàn)位數(shù)，8位、16位、32位等，原理相同。16位的CRC碼產(chǎn)生的規(guī)則是先將要發(fā)送的二進(jìn)制序列數(shù)左移16位（即乘以2的16次方后），除以一個(gè)多項(xiàng)式，最后所得到的余數(shù)就是CRC碼。
求CRC碼所采用的是模2運(yùn)算法則，即多項(xiàng)式除法中采用不帶借位的減法運(yùn)算，運(yùn)算等同于異或運(yùn)算。這一點(diǎn)要仔細(xì)理解，是編程的基礎(chǔ)。
CRC-16: (美國二進(jìn)制同步系統(tǒng)中采用) G(X) = X16 + X15 + X2 + 1
CRC-CCITT: (由歐洲CCITT推薦) G(X) = X16 + X12 + X5 + 1
CRC-32: G(X) = X32 + X26 + X23 + X22 + X16 +X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1
2、按位計(jì)算CRC
采用CRC-CCITT多項(xiàng)式，多項(xiàng)式為0x11021，C語言編程時(shí)，參與計(jì)算為0x1021，這個(gè)地方得深入思考才能體會(huì)其中的奧妙，分享一下我的思路：當(dāng)按位計(jì)算CRC時(shí)，例如計(jì)算二進(jìn)制序列為1001 1010 1010 1111時(shí)，將二進(jìn)制序列數(shù)左移16位，即為1001 1010 1010 1111 (0000 0000 0000 0000)，實(shí)際上該二進(jìn)制序列可拆分為1000 0000 0000 0000 (0000 0000 0000 0000) + 000 0000 0000 0000 (0000 0000 0000 0000) + 00 0000 0000 0000 (0000 0000 0000 0000) + 1 0000 0000 0000 (0000 0000 0000 0000) + ……
現(xiàn)在開始分析運(yùn)算：
<1>對第一個(gè)二進(jìn)制分序列求余數(shù)，豎式除法即為0x10000 ^ 0x11021運(yùn)算，后面的0位保留；
<2>接著對第二個(gè)二進(jìn)制分序列求余數(shù)，將第一步運(yùn)算的余數(shù)*2后再和第二個(gè)二進(jìn)制分序列一起對0x11021求余，這一步理解應(yīng)該沒什么問題。如果該分序列為0，無需計(jì)算。
<3>對其余的二進(jìn)制序列求余與上面兩步相同。
<4>計(jì)算到最后一位時(shí)即為整個(gè)二進(jìn)制序列的余數(shù)，即為CRC校驗(yàn)碼。
該計(jì)算方法相當(dāng)于對每一位計(jì)算，運(yùn)算過程很容易理解，所占內(nèi)存少，缺點(diǎn)是一位一位計(jì)算比較耗時(shí)。
下面給出C語言實(shí)現(xiàn)方法：
unsigned char test[16] = {0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
unsigned char len = 16;
void main( void )
{
unsigned long temp = 0;
unsigned int crc;
unsigned char i;
unsigned char *ptr = test;
while( len-- ) {
for(i = 0x80; i != 0; i = i >> 1) {
temp = temp * 2;
if((temp & 0x10000) != 0)
temp = temp ^ 0x11021;
if((*ptr & i) != 0)
temp = temp ^ (0x10000 ^ 0x11021);
}
ptr++;
}
crc = temp;
printf("0x%x ",crc);
}
上面的程序根據(jù)運(yùn)算分析而來，很容易理解。為了節(jié)約內(nèi)存空間，我們對程序作進(jìn)一步的簡化。分析可知，當(dāng)二進(jìn)制序列中上一位計(jì)算的余數(shù)第15bit位為1時(shí)，即( 上一位計(jì)算的余數(shù) & 0x8000) != 0，計(jì)算本位時(shí)，上一位余數(shù) * 2后可對0x11021作求余運(yùn)算,然后再加上本位計(jì)算所得余數(shù)。這個(gè)很好理解，也就是說，打個(gè)比方，把它看作簡單的除法，計(jì)算上一位時(shí)的余數(shù)乘以2后，如果比較大可以當(dāng)被除數(shù)，就再去除除數(shù)求余。有一點(diǎn)和普通除法不同的是，因?yàn)槎囗?xiàng)式除法中采用不帶借位的減法運(yùn)算，所以0x10000也可以被0x11021除，余數(shù)并非為0x10000,而是0x1021。這個(gè)自己動(dòng)手算一下就知道了。余數(shù)之和也是不帶進(jìn)位的加法運(yùn)算，即異或。最后還強(qiáng)調(diào)一點(diǎn)，因?yàn)槎M(jìn)制序列是左移16位后參與運(yùn)算的，所以，一直算到序列的最后一位也是可以被除的，這點(diǎn)大家要明白。下面給出簡化后的C語言實(shí)現(xiàn)。
unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
unsigned char len = 16;
void main( void )
{
unsigned int crc = 0;
unsigned char i;
unsigned char *ptr = test;
while( len-- ) {
for(i = 0x80; i != 0; i = i >> 1) {
if((crc & 0x8000) != 0) {
crc = crc << 1;
crc = crc ^ 0x1021;
}
else {
crc = crc << 1;
}
if((*ptr & i) != 0) {
crc = crc ^ 0x1021;
}
}
ptr++;
}
printf("0x%x ",crc);
}
上面這段程序網(wǎng)上較為常見，但冇得詳細(xì)的解釋。通過我上面的詳細(xì)分析，如果對此段程序理解還有困難，可以對比一下沒簡化之前的程序，細(xì)細(xì)品味一哈，還是比較容易理解的。要是還理解不了，還是從頭再看下，我碼這么多字容易嗎。。。。。
按位計(jì)算CRC代碼比較簡單，所占內(nèi)存少，但要一位一位去計(jì)算，下面再介紹一種按字節(jié)查表快速計(jì)算CRC的方法。
3、按字節(jié)計(jì)算CRC
有了上面按位計(jì)算的知識(shí)，理解這個(gè)就是小case了。還是舉前面的例子：當(dāng)字節(jié)計(jì)算CRC時(shí)，例如計(jì)算二進(jìn)制序列為1001 1010 1010 1111時(shí)，即0x9a9f時(shí)，將二進(jìn)制序列數(shù)左移16位，即為0x9a9f(0 0 0 0)，實(shí)際上該二進(jìn)制序列可拆分為0x9a00(0 0 0 0) + 0x009f(0 0 0 0)，分析計(jì)算時(shí)和上面的步驟一樣，唯一不同的是計(jì)算中上一步的余數(shù)CRC要乘以2的八次方參與下一步的運(yùn)算，這個(gè)應(yīng)該好理解撒。為了簡化編程，將計(jì)算中的CRC拆成高八位和低八位的形式，高八位的值直接與本位值相加求余，低八位的值乘以2的八次方后作為余數(shù)和計(jì)算得的余數(shù)相加。為了提高計(jì)算速度，我們把8位二進(jìn)制序列數(shù)的CRC全部計(jì)算出來，放在一個(gè)表中，采用查表法可大大提高計(jì)算速度。
表是怎么得到的呢？當(dāng)然是計(jì)算出來的，下面的程序給出了多項(xiàng)式是0x11021的計(jì)算程序。
void main( void )
{
unsigned int crc = 0;
unsigned char i;
unsigned int j;
for(j = 0; j < 256; j++) {
crc = 0;
for(i = 0x80; i != 0; i = i >> 1) {
if((crc & 0x8000) != 0) {
crc = crc << 1;
crc = crc ^ 0x1021;
}
else {
crc = crc << 1;
}
if((j & i) != 0) {
crc = crc ^ 0x1021;
}
}
printf("0x");
if(crc < 0x10) {
printf("000");
}
else if(crc < 0x100) {
printf("00");
}
else if(crc < 0x1000) {
printf("0");
}
printf("%x, ",crc);
}
}
如果你不是使用的0x11021多項(xiàng)式，只需把程序中0x1021換成其他的就可以了。后面的幾個(gè)printf語句為了控制使生成的表比較整齊，如果無所謂，可直接用printf("0x%x, ",crc)；代替。生成的表如下：
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef, 0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6, 0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, 0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485, 0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d, 0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, 0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, 0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, 0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, 0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, 0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0,
好了，我們來寫按字節(jié)計(jì)算的源程序：
unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
unsigned char len = 16;
unsigned int crc_table[256] ={
x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef, 0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6, 0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, 0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485, 0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d, 0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, 0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, 0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, 0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, 0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, 0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0};
void main(void)
{
unsigned int crc = 0;
unsigned char crc_H8;
unsigned char *ptr = test;
while( len-- ) {
crc_H8 = (unsigned char)(crc >> 8);
crc = crc << 8;
crc = crc ^ crc_table[ crc_H8 ^ *ptr];
ptr++;
}
printf("0x%x ",crc);
}
4、按半字節(jié)計(jì)算CRC
是不是感覺上面的表太大了，不是很爽，我們再來改進(jìn)一下，按半字節(jié)計(jì)算，原理我就不贅述了，程序如下：
unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
unsigned char len = 16;
unsigned int crc_table[16] =
{0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef
};
void main(void)
{
unsigned int crc = 0;
unsigned char crc_H4;
unsigned char *ptr = test;
while( len-- )
{
crc_H4 = (unsigned char)(crc >> 12);
crc = crc << 4;
crc = crc ^ crc_table[ crc_H4 ^ (*ptr >> 4)];
crc_H4 = (unsigned char)(crc >> 12);
crc = crc << 4;
crc = crc ^ crc_table[ crc_H4 ^ (*ptr & 0x0f)];
ptr++;
}
printf("0x%x ",crc);
}
- C語言壓縮文件和用MD5算法校驗(yàn)文件完整性的實(shí)例教程
- c語言求出給定范圍內(nèi)的所有質(zhì)數(shù)
- c語言中if 語句的作用范圍示例代碼
- C語言 數(shù)據(jù)類型詳細(xì)介紹
- 詳解C語言中的char數(shù)據(jù)類型及其與int類型的轉(zhuǎn)換
- 深入解析C語言中常數(shù)的數(shù)據(jù)類型
- 解析C語言結(jié)構(gòu)體及位段
- 深度剖析C語言結(jié)構(gòu)體
- C語言 結(jié)構(gòu)體（Struct）詳解及示例代碼
- 嵌入式項(xiàng)目使用C語言結(jié)構(gòu)體位段特性實(shí)現(xiàn)斷言宏校驗(yàn)數(shù)據(jù)范圍有效性的方法
相關(guān)文章
這篇文章主要介紹了c++ primer中的const限定符,本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-05-05
詳解C++內(nèi)存的代碼區(qū),全局區(qū),棧區(qū)和堆區(qū)
這篇文章主要為大家介紹了C++內(nèi)存的代碼區(qū),全局區(qū),棧區(qū)和堆區(qū)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-12-12
這篇文章主要介紹了C語言解決螺旋矩陣算法問題的代碼示例,螺旋矩陣中的數(shù)字由第一行開始到右邊不斷變大,向下變大,向左變大,向上變大,如此循環(huán)...需要的朋友可以參考下2016-04-04
樹形DP是什么？跟其他DP有什么區(qū)別？相信很多初學(xué)者在剛剛接觸一種新思想的時(shí)候都會(huì)有這種問題。沒錯(cuò)，樹形DP準(zhǔn)確的說是一種DP的思想，將DP建立在樹狀結(jié)構(gòu)的基礎(chǔ)上。所以我們結(jié)合具體題目進(jìn)行講解，希望大家可以在題目中領(lǐng)悟這種思想。2021-05-05
楊氏矩陣是一個(gè)數(shù)字矩陣，矩陣的每一行從左到右一次遞增，矩陣從上到下遞增，在這樣的矩陣中查找一個(gè)數(shù)字是否存在。時(shí)間復(fù)雜度小于O(N)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2023-02-02
本文主要介紹了二分查找在實(shí)際中的應(yīng)用，通過分析幾個(gè)應(yīng)用二分查找的實(shí)例，總結(jié)下能使用二分查找算法的一些共同點(diǎn)，感興趣的可以了解一下2022-03-03
這篇文章主要為大家詳細(xì)介紹了用C語言實(shí)現(xiàn)三子棋，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章將具體為大家介紹一下C語言中const和指針的使用，文中的示例代碼講解詳細(xì)，對我們學(xué)習(xí)const和指針有一定幫助，需要的可以參考一下2022-02-02
c++ TCHAR轉(zhuǎn)string導(dǎo)致中文缺失或亂碼問題及解決
這篇文章主要介紹了c++ TCHAR轉(zhuǎn)string導(dǎo)致中文缺失或亂碼問題及解決方案,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-08-08
C++實(shí)現(xiàn)學(xué)生成績管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)學(xué)生成績管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12