1. 基本概念

1.1 模2運(yùn)算

??模2運(yùn)算是一種二進(jìn)制算法，CRC校驗(yàn)技術(shù)中的核心部分，因此，我們?cè)诜治鯟RC算法之前，必須掌握模2運(yùn)算的規(guī)則。與四則運(yùn)算相同，模2運(yùn)算也包括模2加、模2減、模2乘、模2除四種二進(jìn)制運(yùn)算。而且，模2運(yùn)算也使用與四則運(yùn)算相同的運(yùn)算符，即“＋”表示模2加，“－”表示模2減，“×”或“·”表示模2乘，“÷”或“/”表示模2除。但與四則運(yùn)算不同的是模2運(yùn)算不考慮進(jìn)位和借位，即模2加法是不帶進(jìn)位的二進(jìn)制加法運(yùn)算，模2減法是不帶借位的二進(jìn)制減法運(yùn)算。這樣，兩個(gè)二進(jìn)制位相運(yùn)算時(shí)，這兩個(gè)位的值就能確定運(yùn)算結(jié)果，不受前一次運(yùn)算的影響，也不對(duì)下一次造成影響。

1.1.1模2加法運(yùn)算

這是一種二進(jìn)制的運(yùn)算，等同于“異或”運(yùn)算。 通常用于計(jì)算機(jī)和電子領(lǐng)域。
規(guī)則是:

兩個(gè)序列模二相加，即兩個(gè)序列中對(duì)應(yīng)位，相加，不進(jìn)位，相同為0，不同為1。
1+1=0+0=0
1+0=0+1=1
0＋0＝0
0＋1＝1
1＋0＝1
1＋1＝0

例如0101＋0011＝0110，列豎式計(jì)算：
? 0 1 01
＋ 0 0 1 1
──────
? 0 1 1 0

1.1.2 模2減法運(yùn)算

0－0＝0
0－1＝1
1－0＝1
1－1＝0

例如0110－0011＝0101，列豎式計(jì)算：
? 01 1 0
－ 0 0 1 1
──────
? 0 1 0 1

1.1.3 模2乘法運(yùn)算：

多位二進(jìn)制模2乘法類似于普通意義上的多位二進(jìn)制乘法，不同之處在于后者累加中間結(jié)果（或稱部分積）時(shí)采用帶進(jìn)位的加法，而模2乘法對(duì)中間結(jié)果的處理方式采用的是模2加法。

0×0＝0
0×1＝0
1×0＝0
1×1＝1

例如1011×101＝100111，列豎式計(jì)算：
???1 0 1 1
×? ??1 0 1
──────────
??? 1 0 1 1
?? 0 0 0 0
＋ 1 0 1 1
──────────
? 1 0 0 1 1 1

1.1.4 模2除法運(yùn)算

多位二進(jìn)制模2除法也類似于普通意義上的多位二進(jìn)制除法，但是在如何確定商的問題上兩者采用不同的規(guī)則。后者按帶借位的二進(jìn)制減法，根據(jù)余數(shù)減除數(shù)夠減與否確定商1還是商0，若夠減則商1，否則商0。多位模2除法采用模2減法，不帶借位的二進(jìn)制減法，因此考慮余數(shù)夠減除數(shù)與否是沒有意義 的。實(shí)際上，在CRC運(yùn)算中，總能保證除數(shù)的首位為1，則模2除法運(yùn)算的商是由余數(shù)首位與除數(shù)首位的模2除法運(yùn)算結(jié)果確定。因?yàn)槌龜?shù)首位總是1，按照模2除法運(yùn)算法則，那么余數(shù)首位是1就商1，是0就商0。

0÷1＝0
1÷1＝1

例如1100100÷1011＝1110……110，列豎式計(jì)算：
? ? ? ? ? 1 1 10
? ? ? ────────
1 0 1 1 ) 1 1 0 0 1 0 0
－? ? 1 0 1 1
? ?───────
? ? ? ?1 1 1 1
－? ?? 1 0 1 1
? ? ─────────
? ? ??? 1 0 0 0
－?????1 0 1 1
??? ─────────
??????? 0 1 1 0
－?????? 0 0 0 0
??????? ──────
???????? 1 1 0

1.2 生成多項(xiàng)式

1.2.1 定義

??若一個(gè)循環(huán)碼的所有碼字多項(xiàng)式都是一個(gè)次數(shù)最低的非零首一多項(xiàng)式 g(x)的倍式，則稱g(x)生成該碼，并稱g(x)為該碼的生成元或生成多項(xiàng)式。

生成多項(xiàng)式位數(shù) (又成為位寬) = CRC校驗(yàn)碼位數(shù) +1。

注意有些生成多項(xiàng)式的簡(jiǎn)記式中將生成多項(xiàng)式的最高位1省略了。

??生成多項(xiàng)式是接受方和發(fā)送方的一個(gè)約定，也就是一個(gè)二進(jìn)制數(shù)，在整個(gè)傳輸過程中，這個(gè)數(shù)始終保持不變。在發(fā)送方，利用生成多項(xiàng)式對(duì)信息多項(xiàng)式做模2除生成校驗(yàn)碼。在接收方利用生成多項(xiàng)式對(duì)收到的編碼多項(xiàng)式做模2除檢測(cè)和確定錯(cuò)誤位置。
應(yīng)滿足以下條件：

A、生成多項(xiàng)式的最高位和最低位必須為1。
B、當(dāng)被傳送信息（CRC碼）任何一位發(fā)生錯(cuò)誤時(shí)，被生成多項(xiàng)式做除后應(yīng)該使余數(shù)不為0。
C、不同位發(fā)生錯(cuò)誤時(shí)，應(yīng)該使余數(shù)不同。
D、對(duì)余數(shù)繼續(xù)做除，應(yīng)使余數(shù)循環(huán)。

1.2.2 生成原則

若設(shè)碼字長(zhǎng)度為N，信息字段為K位，校驗(yàn)字段為R位(N=K+R)，則對(duì)于CRC碼集中的任一碼字，存在且僅存在一個(gè)R次多項(xiàng)式g(x)，使得

V(x)=A(x)g(x)=xRm(x)+r(x);

其中: m(x)為K次原始的信息多項(xiàng)式， r(x)為R-1次校驗(yàn)多項(xiàng)式（即CRC校驗(yàn)和），

g(x)稱為生成多項(xiàng)式：

g(x)=g0+g1x1+ g2x2+...+g(R-1)x(R-1)+gRxR

發(fā)送方通過指定的g(x)產(chǎn)生CRC碼字，接收方則通過該g(x)來驗(yàn)證收到的CRC碼字。

結(jié)合系統(tǒng)的具體特點(diǎn)及要求，提出一種生成多項(xiàng)式的選取方法，其主要設(shè)計(jì)思想有以下兩個(gè)方面：

（1） 首先，為了確保選取的生成多項(xiàng)式校驗(yàn)性能是最優(yōu)的，考察在具體嵌入式網(wǎng)絡(luò)系統(tǒng)中傳輸數(shù)據(jù)幀最大長(zhǎng)度的情況下，碼重最大，漏檢率最低的生成多項(xiàng)式。

（2）其次，為了確保選取的生成多項(xiàng)式有較廣的使用范圍和良好的可移植性，分別考察小于和大于最大數(shù)據(jù)幀長(zhǎng)度的情況，生成多項(xiàng)式的碼重及漏檢率的情況。

在這里要注意的是嚴(yán)格按照這兩個(gè)方面的優(yōu)先次序考慮，在保證自身應(yīng)用環(huán)境中最優(yōu)檢錯(cuò)性能的前提下考察其擴(kuò)展性和可移植性。

對(duì)于最小距離相同的生成多項(xiàng)式，要首先選取可檢測(cè)數(shù)據(jù)長(zhǎng)度最大的生成多項(xiàng)式；對(duì)于較短的數(shù)據(jù)幀，如果要提高生成多項(xiàng)式的最小距離，必須以不影響該生成多項(xiàng)式對(duì)于長(zhǎng)數(shù)據(jù)幀的校驗(yàn)性能為前提；對(duì)于一些現(xiàn)行的協(xié)議，隨著網(wǎng)絡(luò)的不斷發(fā)展，也會(huì)對(duì)協(xié)議進(jìn)行修正，同時(shí)也會(huì)要求增加傳輸數(shù)據(jù)幀的長(zhǎng)度，因此在選擇生成多項(xiàng)式時(shí)要考慮將來的可擴(kuò)展性，使生成多項(xiàng)式傳輸較長(zhǎng)數(shù)據(jù)幀時(shí)也能有較好的校驗(yàn)性能。

比如說我們有兩個(gè)二進(jìn)制數(shù)，分別為：1101 和1011。

1101 與如下的多項(xiàng)式相聯(lián)系：1x3+1x2+0x1+1x0=x3+x2+x0

1011與如下的多項(xiàng)式相聯(lián)系：1x3+0x2+1x1+1x0=x3+x1+x0

兩個(gè)多項(xiàng)式的乘法：(x3+x2+x0)(x3+x1+x0)=x6+x5+x4+x3+x3+x3+x2+x1+x0

得到結(jié)果后，合并同類項(xiàng)時(shí)采用模2運(yùn)算。也就是說乘除法采用正常的多項(xiàng)式乘除法，而加減法都采用模2運(yùn)算。所謂模2運(yùn)算就是結(jié)果除以2后取余數(shù)。比如3 mod 2 = 1。因此，上面最終得到的多項(xiàng)式為：x6+x5+x4+x3+x2+x1+x0，對(duì)應(yīng)的二進(jìn)制數(shù):111111

1.2.3 最常用的幾種生成多項(xiàng)式

CRC8=X8+X5+X4+X0

CRC-CCITT=X16+X12+X5+X0

CRC16=X16+X15+X2+X0

CRC12=X12+X11+X3+X2+X0

CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+X0

有一點(diǎn)要特別注意，文獻(xiàn)中提到的生成多項(xiàng)式經(jīng)常會(huì)說到多項(xiàng)式的位寬（Width，簡(jiǎn)記為W），這個(gè)位寬不是多項(xiàng)式對(duì)應(yīng)的二進(jìn)制數(shù)的位數(shù)，而是位數(shù)減1。比如CRC8中用到的位寬為8的生成多項(xiàng)式，其實(shí)對(duì)應(yīng)得二進(jìn)制數(shù)有九位：100110001。另外一點(diǎn)，多項(xiàng)式表示和二進(jìn)制表示都很繁瑣，交流起來不方便，因此，文獻(xiàn)中多用16進(jìn)制簡(jiǎn)寫法來表示，因?yàn)樯啥囗?xiàng)式的最高位肯定為1，最高位的位置由位寬可知，故在簡(jiǎn)記式中，將最高的1統(tǒng)一去掉了，如CRC32的生成多項(xiàng)式簡(jiǎn)記為04C11DB7實(shí)際上表示的是104C11DB7。當(dāng)然，這樣簡(jiǎn)記除了方便外，在編程計(jì)算時(shí)也有它的用處。

對(duì)于上面的例子，位寬為4（W=4），按照CRC算法的要求，計(jì)算前要在原始數(shù)據(jù)后填上W個(gè)0，也就是4個(gè)0。

位寬W=1的生成多項(xiàng)式(CRC1)有兩種，分別是X1和X1+X0，讀者可以自己證明10 對(duì)應(yīng)的就是奇偶校驗(yàn)中的奇校驗(yàn)，而11對(duì)應(yīng)則是偶校驗(yàn)。因此，寫到這里我們知道了奇偶校驗(yàn)其實(shí)就是CRC校驗(yàn)的一種特例，這也是我要以奇偶校驗(yàn)作為開篇介紹的原因了。

2. CRC 介紹

2.1 從奇偶校驗(yàn)說起

所謂通訊過程的校驗(yàn)是指在通訊數(shù)據(jù)后加上一些附加信息，通過這些附加信息來判斷接收到的數(shù)據(jù)是否和發(fā)送出的數(shù)據(jù)相同。比如說RS232串行通訊可以設(shè)置奇偶校驗(yàn)位，所謂奇偶校驗(yàn)就是在發(fā)送的每一個(gè)字節(jié)后都加上一位，使得每個(gè)字節(jié)中1的個(gè)數(shù)為奇數(shù)個(gè)或偶數(shù)個(gè)。比如我們要發(fā)送的字節(jié)是0x1a，二進(jìn)制表示為0001 1010。

采用奇校驗(yàn)，則在數(shù)據(jù)后補(bǔ)上個(gè)0，數(shù)據(jù)變?yōu)?001 1010 0，數(shù)據(jù)中1的個(gè)數(shù)為奇數(shù)個(gè)（3個(gè)）

采用偶校驗(yàn)，則在數(shù)據(jù)后補(bǔ)上個(gè)1，數(shù)據(jù)變?yōu)?001 1010 1，數(shù)據(jù)中1的個(gè)數(shù)為偶數(shù)個(gè)（4個(gè)）

接收方通過計(jì)算數(shù)據(jù)中1個(gè)數(shù)是否滿足奇偶性來確定數(shù)據(jù)是否有錯(cuò)。

奇偶校驗(yàn)的缺點(diǎn)也很明顯，首先，它對(duì)錯(cuò)誤的檢測(cè)概率大約只有50%。也就是只有一半的錯(cuò)誤它能夠檢測(cè)出來。另外，每傳輸一個(gè)字節(jié)都要附加一位校驗(yàn)位，對(duì)傳輸效率的影響很大。因此，在高速數(shù)據(jù)通訊中很少采用奇偶校驗(yàn)。奇偶校驗(yàn)優(yōu)點(diǎn)也很明顯，它很簡(jiǎn)單，因此可以用硬件來實(shí)現(xiàn)，這樣可以減少軟件的負(fù)擔(dān)。因此，奇偶校驗(yàn)也被廣泛的應(yīng)用著。

奇偶校驗(yàn)就先介紹到這來，之所以從奇偶校驗(yàn)說起，是因?yàn)檫@種校驗(yàn)方式最簡(jiǎn)單，而且后面將會(huì)知道奇偶校驗(yàn)其實(shí)就是CRC 校驗(yàn)的一種(CRC-1)。

2.2 累加和校驗(yàn)

另一種常見的校驗(yàn)方式是累加和校驗(yàn)。所謂累加和校驗(yàn)實(shí)現(xiàn)方式有很多種，最常用的一種是在一次通訊數(shù)據(jù)包的最后加入一個(gè)字節(jié)的校驗(yàn)數(shù)據(jù)。這個(gè)字節(jié)內(nèi)容為前面數(shù)據(jù)包中全部數(shù)據(jù)的忽略進(jìn)位的按字節(jié)累加和。比如下面的例子：

我們要傳輸?shù)男畔椋?6、23、4

加上校驗(yàn)和后的數(shù)據(jù)包：6、23、4、33

這里 33 為前三個(gè)字節(jié)的校驗(yàn)和。接收方收到全部數(shù)據(jù)后對(duì)前三個(gè)數(shù)據(jù)進(jìn)行同樣的累加計(jì)算，如果累加和與最后一個(gè)字節(jié)相同的話就認(rèn)為傳輸?shù)臄?shù)據(jù)沒有錯(cuò)誤。

累加和校驗(yàn)由于實(shí)現(xiàn)起來非常簡(jiǎn)單，也被廣泛的采用。但是這種校驗(yàn)方式的檢錯(cuò)能力也比較一般，對(duì)于單字節(jié)的校驗(yàn)和大概有1/256 的概率將原本是錯(cuò)誤的通訊數(shù)據(jù)誤判為正確數(shù)據(jù)。之所以這里介紹這種校驗(yàn)，是因?yàn)镃RC校驗(yàn)在傳輸數(shù)據(jù)的形式上與累加和校驗(yàn)是相同的，都可以表示為：通訊數(shù)據(jù) 校驗(yàn)字節(jié)（也可能是多個(gè)字節(jié)）

2.3 初識(shí) CRC 算法

CRC 算法的基本思想是將傳輸?shù)臄?shù)據(jù)當(dāng)做一個(gè)位數(shù)很長(zhǎng)的數(shù)。將這個(gè)數(shù)除以另一個(gè)數(shù)。得到的余數(shù)作為校驗(yàn)數(shù)據(jù)附加到原數(shù)據(jù)后面。還以上面例子中的數(shù)據(jù)為例：

6、23、4 可以看做一個(gè)2進(jìn)制數(shù)： 0000011000010111 00000010

假如被除數(shù)選9，二進(jìn)制表示為：1001

則除法運(yùn)算可以表示為：

可以看到，最后的余數(shù)為1。如果我們將這個(gè)余數(shù)作為校驗(yàn)和的話，傳輸?shù)臄?shù)據(jù)則是：6、23、4、1

2.4 CRC算法的編程實(shí)現(xiàn)

說了這么多總算到了核心部分了。從前面的介紹我們知道CRC校驗(yàn)核心就是實(shí)現(xiàn)無借位的除法運(yùn)算。下面還是通過一個(gè)例子來說明如何實(shí)現(xiàn)CRC校驗(yàn)。

假設(shè)我們的生成多項(xiàng)式為：100110001（簡(jiǎn)記為0x31），也就是CRC-8

則計(jì)算步驟如下：

（1） 將CRC寄存器（8-bits，比生成多項(xiàng)式少1bit）賦初值0

（2） 在待傳輸信息流后面加入8個(gè)0

（3） While (數(shù)據(jù)未處理完)

（4） Begin

（5） If (CRC寄存器首位是1)

（6） reg = reg XOR 0x31

（7） CRC寄存器左移一位，讀入一個(gè)新的數(shù)據(jù)于CRC寄存器的0 bit的位置。

（8） End

（9） CRC寄存器就是我們所要求的余數(shù)。

實(shí)際上，真正的CRC 計(jì)算通常與上面描述的還有些出入。這是因?yàn)檫@種最基本的CRC除法有個(gè)很明顯的缺陷，就是數(shù)據(jù)流的開頭添加一些0并不影響最后校驗(yàn)字的結(jié)果。這個(gè)問題很讓人惱火啊，因此真正應(yīng)用的CRC 算法基本都在原始的CRC算法的基礎(chǔ)上做了些小的改動(dòng)。

所謂的改動(dòng)，也就是增加了兩個(gè)概念，第一個(gè)是“余數(shù)初始值”，第二個(gè)是“結(jié)果異或值”。

所謂的“余數(shù)初始值”就是在計(jì)算CRC值的開始，給CRC寄存器一個(gè)初始值。“結(jié)果異或值”是在其余計(jì)算完成后將CRC寄存器的值在與這個(gè)值進(jìn)行一下異或操作作為最后的校驗(yàn)值。

常見的三種CRC 標(biāo)準(zhǔn)用到個(gè)各個(gè)參數(shù)如下表。

CCITT

CRC16

CRC32

校驗(yàn)和位寬W

16

16

32

生成多項(xiàng)式

x16+x12+x5+1

x16+x15+x2+1

x32+x26+x23+x22+x16+

x12+x11+x10+x8+x7+x5+

x4+x2+x1+1

除數(shù)（多項(xiàng)式）

0x1021

0x8005

0x04C11DB7

余數(shù)初始值

0xFFFF

0x0000

0xFFFFFFFF

結(jié)果異或值

0x0000

0x0000

0xFFFFFFFF

加入這些變形后，常見的算法描述形式就成了這個(gè)樣子了：

（1） 設(shè)置CRC寄存器，并給其賦值為“余數(shù)初始值”。

（2） 將數(shù)據(jù)的第一個(gè)8-bit字符與CRC寄存器進(jìn)行異或，并把結(jié)果存入CRC寄存器。

（3） CRC寄存器向右移一位，MSB補(bǔ)零，移出并檢查L(zhǎng)SB。

（4） 如果LSB為0，重復(fù)第三步；若LSB為1，CRC寄存器與0x31相異或。

（5） 重復(fù)第3與第4步直到8次移位全部完成。此時(shí)一個(gè)8-bit數(shù)據(jù)處理完畢。

（6） 重復(fù)第2至第5步直到所有數(shù)據(jù)全部處理完成。

（7） 最終CRC寄存器的內(nèi)容與“結(jié)果異或值”進(jìn)行或非操作后即為CRC值。

示例性的C代碼如下所示，因?yàn)樾屎艿?，?xiàng)目中如對(duì)計(jì)算時(shí)間有要求應(yīng)該避免采用這樣的代碼。不過這個(gè)代碼已經(jīng)比網(wǎng)上常見的計(jì)算代碼要好了，因?yàn)檫@個(gè)代碼有一個(gè)crc的參數(shù)，可以將上次計(jì)算的crc結(jié)果傳入函數(shù)中作為這次計(jì)算的初始值，這對(duì)大數(shù)據(jù)塊的CRC計(jì)算是很有用的，不需要一次將所有數(shù)據(jù)讀入內(nèi)存，而是讀一部分算一次，全讀完后就計(jì)算完了。這對(duì)內(nèi)存受限系統(tǒng)還是很有用的。

#define POLY        0x1021
/**
 * Calculating CRC-16 in 'C'
 * @para addr, start of data
 * @para num, length of data
 * @para crc, incoming CRC
 */
uint16_t crc16(unsigned char *addr, int num, uint16_t crc)
{
    int i;
    for (; num > 0; num--)              /* Step through bytes in memory */
    {
        crc = crc ^ (*addr++ << 8);     /* Fetch byte from memory, XOR into CRC top byte*/
        for (i = 0; i < 8; i++)             /* Prepare to rotate 8 bits */
        {
            if (crc & 0x8000)            /* b15 is set... */
                crc = (crc << 1) ^ POLY;    /* rotate and XOR with polynomic */
            else                          /* b15 is clear... */
                crc <<= 1;                  /* just rotate */
        }                             /* Loop for 8 bits */
        crc &= 0xFFFF;                  /* Ensure CRC remains 16-bit value */
    }                               /* Loop until num=0 */
    return(crc);                    /* Return updated CRC */
}

上面的代碼是我從http://mdfs.net/Info/Comp/Comms/CRC16.htm找到的，不過原始代碼有錯(cuò)誤，我做了些小的修改。

下面對(duì)這個(gè)函數(shù)給出個(gè)例子片段代碼：

    unsigned char data1[] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
    unsigned char data2[] = {'5', '6', '7', '8', '9'};
    unsigned short c1, c2;
    c1 = crc16(data1, 9, 0xffff);
    c2 = crc16(data1, 4, 0xffff);
    c2 = crc16(data2, 5, c2);
    printf("%04x\n", c1);
    printf("%04x\n", c2);

讀者可以驗(yàn)算，c1、c2 的結(jié)果都為 29b1。上面代碼中crc 的初始值之所以為0xffff，是因?yàn)镃CITT標(biāo)準(zhǔn)要求的除數(shù)初始值就是0xffff。

上面的算法對(duì)數(shù)據(jù)流逐位進(jìn)行計(jì)算，效率很低。實(shí)際上仔細(xì)分析CRC計(jì)算的數(shù)學(xué)性質(zhì)后我們可以多位多位計(jì)算，最常用的是一種按字節(jié)查表的快速算法。該算法基于這樣一個(gè)事實(shí)：計(jì)算本字節(jié)后的CRC碼，等于上一字節(jié)余式CRC碼的低8位左移8位，加上上一字節(jié)CRC右移 8位和本字節(jié)之和后所求得的CRC碼。如果我們把8位二進(jìn)制序列數(shù)的CRC(共256個(gè))全部計(jì)算出來，放在一個(gè)表里，編碼時(shí)只要從表中查找對(duì)應(yīng)的值進(jìn)行處理即可。

按照這個(gè)方法，可以有如下的代碼（這個(gè)代碼也不是我寫的，是我在Micbael Barr的書“Programming Embedded Systems in C and C++” 中找到的，同樣，我做了點(diǎn)小小的改動(dòng)。）：

/*
crc.h
*/
 
#ifndef CRC_H_INCLUDED
#define CRC_H_INCLUDED
 
/*
* The CRC parameters. Currently configured for CCITT.
* Simply modify these to switch to another CRC Standard.
*/
/*
#define POLYNOMIAL          0x8005
#define INITIAL_REMAINDER   0x0000
#define FINAL_XOR_VALUE     0x0000
*/
#define POLYNOMIAL          0x1021
#define INITIAL_REMAINDER   0xFFFF
#define FINAL_XOR_VALUE     0x0000
 
/*
#define POLYNOMIAL          0x1021
#define POLYNOMIAL          0xA001
#define INITIAL_REMAINDER   0xFFFF
#define FINAL_XOR_VALUE     0x0000
*/
 
/*
* The width of the CRC calculation and result.
* Modify the typedef for an 8 or 32-bit CRC standard.
*/
typedef unsigned short width_t;
#define WIDTH (8 * sizeof(width_t))
#define TOPBIT (1 << (WIDTH - 1))
 
/**
 * Initialize the CRC lookup table.
 * This table is used by crcCompute() to make CRC computation faster.
 */
void crcInit(void);
 
/**
 * Compute the CRC checksum of a binary message block.
 * @para message, 用來計(jì)算的數(shù)據(jù)
 * @para nBytes, 數(shù)據(jù)的長(zhǎng)度
 * @note This function expects that crcInit() has been called
 *       first to initialize the CRC lookup table.
 */
width_t crcCompute(unsigned char * message, unsigned int nBytes);
 
#endif // CRC_H_INCLUDED
 

/*
 *crc.c
 */
 
#include "crc.h"
/*
* An array containing the pre-computed intermediate result for each
* possible byte of input. This is used to speed up the computation.
*/
static width_t crcTable[256];
 
/**
 * Initialize the CRC lookup table.
 * This table is used by crcCompute() to make CRC computation faster.
 */
void crcInit(void)
{
    width_t remainder;
    width_t dividend;
    int bit;
    /* Perform binary long division, a bit at a time. */
    for(dividend = 0; dividend < 256; dividend++)
    {
        /* Initialize the remainder.  */
        remainder = dividend << (WIDTH - 8);
        /* Shift and XOR with the polynomial.   */
        for(bit = 0; bit < 8; bit++)
        {
            /* Try to divide the current data bit.  */
            if(remainder & TOPBIT)
            {
                remainder = (remainder << 1) ^ POLYNOMIAL;
            }
            else
            {
                remainder = remainder << 1;
            }
        }
        /* Save the result in the table. */
        crcTable[dividend] = remainder;
    }
} /* crcInit() */
 
/**
 * Compute the CRC checksum of a binary message block.
 * @para message, 用來計(jì)算的數(shù)據(jù)
 * @para nBytes, 數(shù)據(jù)的長(zhǎng)度
 * @note This function expects that crcInit() has been called
 *       first to initialize the CRC lookup table.
 */
width_t crcCompute(unsigned char * message, unsigned int nBytes)
{
    unsigned int offset;
    unsigned char byte;
    width_t remainder = INITIAL_REMAINDER;
    /* Divide the message by the polynomial, a byte at a time. */
    for( offset = 0; offset < nBytes; offset++)
    {
        byte = (remainder >> (WIDTH - 8)) ^ message[offset];
        remainder = crcTable[byte] ^ (remainder << 8);
    }
    /* The final remainder is the CRC result. */
    return (remainder ^ FINAL_XOR_VALUE);
} /* crcCompute() */

上面代碼中crcInit() 函數(shù)用來計(jì)算crcTable，因此在調(diào)用 crcCompute 前必須先調(diào)用 crcInit()。不過，對(duì)于嵌入式系統(tǒng)，RAM是很緊張的，最好將 crcTable 提前算好，作為常量數(shù)據(jù)存到程序存儲(chǔ)區(qū)而不占用RAM空間。CRC 計(jì)算實(shí)際上還有很多內(nèi)容可以介紹，不過對(duì)于一般的程序員來說，知道這些也就差不多了。余下的部分以后有時(shí)間了我再寫篇文章來介紹吧。

最后，給出個(gè) C++ 代碼，實(shí)現(xiàn)了 CRC8、CRC16 和 CRC32 的計(jì)算。收集了常見的各種 CRC 系數(shù)。 代碼可以從這里下載：https://code.csdn.net/liyuanbhu/crc_compute/tree/master

#ifndef CRCCOMPUTE_H
#define CRCCOMPUTE_H
 
#include <stdint.h>
 
template <typename TYPE> class CRC
{
public:
    CRC();
    CRC(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value);
    void build(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value);
    /**
     * Compute the CRC checksum of a binary message block.
     * @para message, 用來計(jì)算的數(shù)據(jù)
     * @para nBytes, 數(shù)據(jù)的長(zhǎng)度
     */
    TYPE crcCompute(char * message, unsigned int nBytes);
    TYPE crcCompute(char * message, unsigned int nBytes, bool reinit);
protected:
    TYPE m_polynomial;
    TYPE m_initial_remainder;
    TYPE m_final_xor_value;
    TYPE m_remainder;
    TYPE crcTable[256];
    int m_width;
    int m_topbit;
    /**
     * Initialize the CRC lookup table.
     * This table is used by crcCompute() to make CRC computation faster.
     */
    void crcInit(void);
};
 
template <typename TYPE>
CRC<TYPE>::CRC()
{
    m_width = 8 * sizeof(TYPE);
    m_topbit = 1 << (m_width - 1);
}
 
template <typename TYPE>
CRC<TYPE>::CRC(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value)
{
    m_width = 8 * sizeof(TYPE);
    m_topbit = 1 << (m_width - 1);
    m_polynomial = polynomial;
    m_initial_remainder = init_remainder;
    m_final_xor_value = final_xor_value;
 
    crcInit();
}
 
template <typename TYPE>
void CRC<TYPE>::build(TYPE polynomial, TYPE init_remainder, TYPE final_xor_value)
{
    m_polynomial = polynomial;
    m_initial_remainder = init_remainder;
    m_final_xor_value = final_xor_value;
 
    crcInit();
}
 
template <typename TYPE>
TYPE CRC<TYPE>::crcCompute(char * message, unsigned int nBytes)
{
    unsigned int offset;
    unsigned char byte;
    TYPE remainder = m_initial_remainder;
    /* Divide the message by the polynomial, a byte at a time. */
    for( offset = 0; offset < nBytes; offset++)
    {
        byte = (remainder >> (m_width - 8)) ^ message[offset];
        remainder = crcTable[byte] ^ (remainder << 8);
    }
    /* The final remainder is the CRC result. */
    return (remainder ^ m_final_xor_value);
}
 
template <typename TYPE>
TYPE CRC<TYPE>::crcCompute(char * message, unsigned int nBytes, bool reinit)
{
    unsigned int offset;
    unsigned char byte;
    if(reinit)
    {
        m_remainder = m_initial_remainder;
    }
    /* Divide the message by the polynomial, a byte at a time. */
    for( offset = 0; offset < nBytes; offset++)
    {
        byte = (m_remainder >> (m_width - 8)) ^ message[offset];
        m_remainder = crcTable[byte] ^ (m_remainder << 8);
    }
    /* The final remainder is the CRC result. */
    return (m_remainder ^ m_final_xor_value);
}
 
class CRC8 : public CRC<uint8_t>
{
public:
    enum CRC8_TYPE {eCRC8, eAUTOSAR, eCDMA2000, eDARC, eDVB_S2, eEBU, eAES, eGSM_A, eGSM_B, eI_CODE,
                    eITU, eLTE, eMAXIM, eOPENSAFETY, eROHC, eSAE_J1850, eWCDMA};
    CRC8(CRC8_TYPE type);
    CRC8(uint8_t polynomial, uint8_t init_remainder, uint8_t final_xor_value)
        :CRC<uint8_t>(polynomial, init_remainder, final_xor_value){}
};
 
class CRC16 : public CRC<uint16_t>
{
public:
    enum CRC16_TYPE {eCCITT, eKERMIT, eCCITT_FALSE, eIBM, eARC, eLHA, eSPI_FUJITSU,
                     eBUYPASS, eVERIFONE, eUMTS, eCDMA2000, eCMS, eDDS_110, eDECT_R,
                     eDECT_X, eDNP, eEN_13757, eGENIBUS, eEPC, eDARC, eI_CODE, eGSM,
                     eLJ1200, eMAXIM, eMCRF4XX, eOPENSAFETY_A, eOPENSAFETY_B, ePROFIBUS,
                     eIEC_61158_2, eRIELLO, eT10_DIF, eTELEDISK, eTMS37157, eUSB,
                     eCRC_A, eMODBUS, eX_25, eCRC_B, eISO_HDLC, eIBM_SDLC, eXMODEM,
                     eZMODEM, eACORN, eLTE};
    CRC16(CRC16_TYPE type);
    CRC16(uint16_t polynomial, uint16_t init_remainder, uint16_t final_xor_value)
        :CRC<uint16_t>(polynomial, init_remainder, final_xor_value){}
};
 
class CRC32 : public CRC<uint32_t>
{
public:
    enum CRC32_TYPE {eADCCP, ePKZIP, eCRC32, eAAL5, eDECT_B, eB_CRC32, eBZIP2, eAUTOSAR,
                     eCRC32C, eCRC32D, eMPEG2, ePOSIX, eCKSUM, eCRC32Q, eJAMCRC, eXFER};
    CRC32(CRC32_TYPE type);
};
 
 
#endif // CRCCOMPUTE_H

#include "crcCompute.h"
 
template <typename TYPE>
void CRC<TYPE>::crcInit(void)
{
    TYPE remainder;
    TYPE dividend;
    int bit;
    /* Perform binary long division, a bit at a time. */
    for(dividend = 0; dividend < 256; dividend++)
    {
        /* Initialize the remainder.  */
        remainder = dividend << (m_width - 8);
        /* Shift and XOR with the polynomial.   */
        for(bit = 0; bit < 8; bit++)
        {
            /* Try to divide the current data bit.  */
            if(remainder & m_topbit)
            {
                remainder = (remainder << 1) ^ m_polynomial;
            }
            else
            {
                remainder = remainder << 1;
            }
        }
        /* Save the result in the table. */
        crcTable[dividend] = remainder;
    }
}
 
CRC8::CRC8(CRC8_TYPE type)
{
    switch (type)
    {
    case eCRC8:
        m_polynomial = 0x07; //http://reveng.sourceforge.net/crc-catalogue/all.htm
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eAUTOSAR:
        m_polynomial = 0x2f;
        m_initial_remainder = 0xff;
        m_final_xor_value = 0xff;
        break;
    case eCDMA2000:
        m_polynomial = 0x9b;
        m_initial_remainder = 0xFF;
        m_final_xor_value = 0x00;
        break;
    case eDARC:
        m_polynomial = 0x39;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eDVB_S2:
        m_polynomial = 0xd5;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eEBU:
    case eAES:
        m_polynomial = 0x1d;
        m_initial_remainder = 0xFF;
        m_final_xor_value = 0x00;
        break;
    case eGSM_A:
        m_polynomial = 0x1d;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eGSM_B:
        m_polynomial = 0x49;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0xFF;
        break;
    case eI_CODE:
        m_polynomial = 0x1d;
        m_initial_remainder = 0xFD;
        m_final_xor_value = 0x00;
        break;
    case eITU:
        m_polynomial = 0x07;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x55;
        break;
    case eLTE:
        m_polynomial = 0x9b;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eMAXIM:
        m_polynomial = 0x31;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eOPENSAFETY:
        m_polynomial = 0x2f;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    case eROHC:
        m_polynomial = 0x07;
        m_initial_remainder = 0xff;
        m_final_xor_value = 0x00;
        break;
    case eSAE_J1850:
        m_polynomial = 0x1d;
        m_initial_remainder = 0xff;
        m_final_xor_value = 0xff;
        break;
    case eWCDMA:
        m_polynomial = 0x9b;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    default:
        m_polynomial = 0x07;
        m_initial_remainder = 0x00;
        m_final_xor_value = 0x00;
        break;
    }
    crcInit();
 
}
 
CRC16::CRC16(CRC16_TYPE type)
{
    switch (type)
    {
    case eCCITT_FALSE:
    case eMCRF4XX:
        m_polynomial = 0x1021;
        m_initial_remainder = 0xFFFF;
        m_final_xor_value = 0x0000;
        break;
    case eIBM:
    case eARC:
    case eLHA:
    case eBUYPASS:
    case eVERIFONE:
    case eUMTS:
        m_polynomial = 0x8005;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eSPI_FUJITSU:
        m_polynomial = 0x1021;
        m_initial_remainder = 0x1d0f;
        m_final_xor_value = 0x0000;
        break;
    case eCCITT:
    case eKERMIT:
    case eXMODEM:
    case eZMODEM:
    case eACORN:
    case eLTE:
        m_polynomial = 0x1021;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eCDMA2000:
        m_polynomial = 0xc867;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0x0000;
        break;
    case eCMS:
    case eMODBUS:
        m_polynomial = 0x8005;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0x0000;
        break;
    case eDDS_110:
        m_polynomial = 0x8005;
        m_initial_remainder = 0x800d;
        m_final_xor_value = 0x0000;
        break;
    case eDECT_R:
        m_polynomial = 0x0589;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0001;
        break;
    case eDECT_X:
        m_polynomial = 0x0589;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eDNP:
    case eEN_13757:
        m_polynomial = 0x3d65;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0xffff;
        break;
    case eGENIBUS:
    case eEPC:
    case eDARC:
    case eI_CODE:
    case eX_25:
    case eCRC_B:
    case eISO_HDLC:
    case eIBM_SDLC:
        m_polynomial = 0x1021;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0xffff;
        break;
    case eGSM:
        m_polynomial = 0x1021;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0xffff;
        break;
    case eLJ1200:
        m_polynomial = 0x6f63;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eMAXIM:
        m_polynomial = 0x8005;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0xffff;
        break;
    case eOPENSAFETY_A:
        m_polynomial = 0x5935;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eOPENSAFETY_B:
        m_polynomial = 0x755b;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case ePROFIBUS:
    case eIEC_61158_2:
        m_polynomial = 0x1dcf;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0xffff;
        break;
    case eRIELLO:
        m_polynomial = 0x1021;
        m_initial_remainder = 0xb2aa;
        m_final_xor_value = 0x0000;
        break;
    case eT10_DIF:
        m_polynomial = 0x8bb7;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eTELEDISK:
        m_polynomial = 0xa097;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    case eTMS37157:
        m_polynomial = 0x1021;
        m_initial_remainder = 0x89ec;
        m_final_xor_value = 0x0000;
        break;
    case eUSB:
        m_polynomial = 0x8005;
        m_initial_remainder = 0xffff;
        m_final_xor_value = 0xffff;
        break;
    case eCRC_A:
        m_polynomial = 0x1021;
        m_initial_remainder = 0xc6c6;
        m_final_xor_value = 0x0000;
        break;
    default:
        m_polynomial = 0x8005;
        m_initial_remainder = 0x0000;
        m_final_xor_value = 0x0000;
        break;
    }
    crcInit();
}
 
 
CRC32::CRC32(CRC32_TYPE type)
{
    switch (type)
    {
    case eADCCP:
    case ePKZIP:
    case eCRC32:
    case eBZIP2:
    case eAAL5:
    case eDECT_B:
    case eB_CRC32:
        m_polynomial = 0x04c11db7;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eAUTOSAR:
        m_polynomial = 0xf4acfb13;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eCRC32C:
        m_polynomial = 0x1edc6f41;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eCRC32D:
        m_polynomial = 0xa833982b;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eMPEG2:
    case eJAMCRC:
        m_polynomial = 0x04c11db7;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0x00000000;
        break;
    case ePOSIX:
    case eCKSUM:
        m_polynomial = 0x04c11db7;
        m_initial_remainder = 0x00000000;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    case eCRC32Q:
        m_polynomial = 0x814141ab;
        m_initial_remainder = 0x00000000;
        m_final_xor_value = 0x00000000;
        break;
    case eXFER:
        m_polynomial = 0x000000af;
        m_initial_remainder = 0x00000000;
        m_final_xor_value = 0x00000000;
        break;
    default:
        m_polynomial = 0x04C11DB7;
        m_initial_remainder = 0xFFFFFFFF;
        m_final_xor_value = 0xFFFFFFFF;
        break;
    }
    crcInit();
}

#include <iostream>
#include <stdio.h>
#include "crcCompute.h"
 
using namespace std;
 
int main(int argc, char *argv[])
{
 
    CRC16 crc16(CRC16::eCCITT_FALSE);
    char data1[] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};
    char data2[] = {'5', '6', '7', '8', '9'};
    unsigned short c1, c2;
    c1 = crc16.crcCompute(data1, 9);
    c2 = crc16.crcCompute(data1, 4, true);
    c2 = crc16.crcCompute(data2, 5, false);
 
 
    printf("%04x\n", c1);
    printf("%04x\n", c2);
 
    return 0;
}