三、常見的CRC算法

雖然CRC可以任意定義二項(xiàng)式、數(shù)據(jù)長(zhǎng)度等,但沒有一個(gè)統(tǒng)一的標(biāo)準(zhǔn)的話,就會(huì)讓整個(gè)計(jì)算變得非常的麻煩。但實(shí)際上,不同的廠家經(jīng)常采用不同的標(biāo)準(zhǔn)算法,這里列出了一些國(guó)際常用的模型表:

名稱多項(xiàng)式表示法應(yīng)用舉例CRC-8X8+X2+X+10X107
CRC-12X12+X11+X3+X2+X+10X180Ftelecom systemsCRC-16X16+X15+X2+10X18005Bisync, Modbus, USB, ANSI X3．28, SIA DC-07, many others; also known as CRC-16 and CRC-16-ANSICRC-CCITTX16+X12+X5+10X11021ISO HDLC, ITU X．25, V．34/V．41/V．42, PPP-FCSCRC-32X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+10x104C11DB7ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCSCRC-32CX32+X28+X27+X26+X25+X23+X22+X20+X19+X18+X14+X13+X11+X10+X9+X8+X6+10x11EDC6F41iSCSI, SCTP, G．hn payload, SSE4．2, Btrfs, ext4, Ceph

四、CRC校驗(yàn)算法前置知識(shí)

在學(xué)習(xí)CRC校驗(yàn)算法之前,先復(fù)習(xí)一下CRC會(huì)涉及的主要幾個(gè)主要的算法。

1． 異或

異或,就是不同為1,相同為0,運(yùn)算符號(hào)是^。

0^0 = 0
0^1 = 1
1^1 = 0
1^0 = 1

異或運(yùn)算存在如下幾個(gè)規(guī)律,需要了解。

0^x = x 即0 異或任何數(shù)等于任何數(shù)
1^x = ～x 即1異或任何數(shù)等于任何數(shù)取反
x^x = 0 即任何數(shù)與自己異或,結(jié)果為0
a ^ b = b ^ a 交換律
a ^ (b ^ c) = (a ^ b) ^c 結(jié)合律
2． 模2加法

模2加法相對(duì)于普通的算術(shù)加法,主要的區(qū)別在模2加法,不做進(jìn)位處理。具體結(jié)果如下。0+0 = 00+1 = 11+1 = 01+0 = 1我們發(fā)現(xiàn)模2加法的計(jì)算結(jié)果,同異或運(yùn)算結(jié)果一模一樣。進(jìn)一步推演,我們會(huì)發(fā)現(xiàn),異或運(yùn)算的5個(gè)規(guī)律,同樣適合于模2加法。這里,就不在一一列舉了。

3． 模2減法

模2減法相對(duì)于普通的算術(shù)減法,主要的區(qū)別在模2減法,不做借位處理。具體結(jié)果如下。0-0 = 00-1 = 11-1 = 01-0 = 1我們發(fā)現(xiàn)模2減法的計(jì)算結(jié)果,同模2加法,以及異或的運(yùn)算結(jié)果一模一樣。進(jìn)一步推演,我們會(huì)發(fā)現(xiàn),異或運(yùn)算的5個(gè)規(guī)律,同樣適合于模2減法。這里,就不在一一列舉了。

4． 模2除法

模2除法相對(duì)于普通的算術(shù)除法,主要的區(qū)別在模2除法,它既不向上位借位,也不比較除數(shù)和被除數(shù)的相同位數(shù)值的大小,只要以相同位數(shù)進(jìn)行相除即可。

五、CRC原理

CRC原理:在K位信息碼(目標(biāo)發(fā)送數(shù)據(jù))后再拼接R位校驗(yàn)碼,使整個(gè)編碼長(zhǎng)度為N位,因此這種編碼也叫(N,K)碼。

通俗的說,就是在需要發(fā)送的信息后面附加一個(gè)數(shù)(即校驗(yàn)碼),生成一個(gè)新的發(fā)送數(shù)據(jù)發(fā)送給接收端。這個(gè)數(shù)據(jù)要求能夠使生成的新數(shù)據(jù)被一個(gè)特定的數(shù)整除。這里的整除需要引入模 2除法的概念。

那么,CRC校驗(yàn)的具體做法就是

(1)選定一個(gè)標(biāo)準(zhǔn)除數(shù)(K位二進(jìn)制數(shù)據(jù)串)

(2)在要發(fā)送的數(shù)據(jù)(m位)后面加上K-1位0,然后將這個(gè)新數(shù)(M+K-1位)以模2除法的方式除以上面這個(gè)標(biāo)準(zhǔn)除數(shù),所得到的余數(shù)也就是該數(shù)據(jù)的CRC校驗(yàn)碼(注:余數(shù)必須比除數(shù)少且只少一位,不夠就補(bǔ)0)

(3)將這個(gè)校驗(yàn)碼附在原m位數(shù)據(jù)后面,構(gòu)成新的M+K-1位數(shù)據(jù),發(fā)送給接收端。

(4)接收端將接收到的數(shù)據(jù)除以標(biāo)準(zhǔn)除數(shù),如果余數(shù)為0則認(rèn)為數(shù)據(jù)正確。

注意:CRC校驗(yàn)中有兩個(gè)關(guān)鍵點(diǎn):

一是要預(yù)先確定一個(gè)發(fā)送端和接收端都用來作為除數(shù)的二進(jìn)制比特串(或多項(xiàng)式);

二是把原始幀與上面選定的除進(jìn)行二進(jìn)制除法運(yùn)算,計(jì)算出FCS。

前者可以隨機(jī)選擇,也可按國(guó)際上通行的標(biāo)準(zhǔn)選擇,但最高位和最低位必須均為“1”

六、循環(huán)冗余的計(jì)算 

實(shí)例:

由于CRC-32、CRC-16、CCITT和CRC-4的編碼過程基本一致,只有位數(shù)和生成多項(xiàng)式不一樣,下面就舉例,來說明CRC校驗(yàn)碼生成過程。

對(duì)于數(shù)據(jù)1110 0101(16#E5),以指定除數(shù)11011求它的CRC校驗(yàn)碼,其過程如下:

使用上面計(jì)算的校驗(yàn)和和消息數(shù)據(jù),可以創(chuàng)建要傳輸?shù)拇a字。

有時(shí)候,我們需要填充checksum到制定的位置,這就涉及到字節(jié)序問題,建議用memcpy()進(jìn)行拷貝。

七、代碼實(shí)現(xiàn)

實(shí)現(xiàn)算法參考網(wǎng)絡(luò)相關(guān)代碼,進(jìn)行整理并驗(yàn)證,可直接使用。crc．c

 
*一口Linux
*2021．6．21
*version: 1．0．0
#include "crc．h"
#include

crc．h

 
*一口Linux
*2021．6．21
*version: 1．0．0
#ifndef __CRC_H__
#define __CRC_H__
#include

main．c

 
*一口Linux
*2021．6．21
*version: 1．0．0
#include

注意

不同的CRC算法,對(duì)00H或FFH數(shù)據(jù)流的計(jì)算結(jié)果不一樣,部分算法存在校驗(yàn)結(jié)果也為00H或FFH的情況(也就意味著存儲(chǔ)空間處于初始化狀態(tài)時(shí):全0或全1,CRC校驗(yàn)反而是正確的),在應(yīng)用中需要注意避免。