[導讀]關注星標公眾號，不錯過精彩內(nèi)容來源?|一口LinuxCRC校驗應用比較廣泛，通常在通信領域用的比較多，即便是自定義通信協(xié)議，也可以添加CRC校驗碼，使其通信更加可靠。今天就來進一步描述CRC校驗碼。一、CRC概念1.什么是CRC？CRC（CyclicRedundancyCheck...
關注 星標公眾號，不錯過精彩內(nèi)容來源?| 一口Linux
CRC校驗應用比較廣泛，通常在通信領域用的比較多，即便是自定義通信協(xié)議，也可以添加CRC校驗碼，使其通信更加可靠。今天就來進一步描述CRC校驗碼。
CRC校驗應用比較廣泛，通常在通信領域用的比較多，即便是自定義通信協(xié)議，也可以添加CRC校驗碼，使其通信更加可靠。今天就來進一步描述CRC校驗碼。
一、CRC概念
1. 什么是CRC？
CRC（Cyclic Redundancy Checksum）是一種糾錯技術，代表循環(huán)冗余校驗和。數(shù)據(jù)通信領域中最常用的一種差錯校驗碼，其信息字段和校驗字段長度可以任意指定，但要求通信雙方定義的CRC標準一致。主要用來檢測或校驗數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯誤。它的使用方式可以說明如下圖所示：在數(shù)據(jù)傳輸過程中，無論傳輸系統(tǒng)的設計再怎么完美，差錯總會存在，這種差錯可能會導致在鏈路上傳輸?shù)囊粋€或者多個幀被破壞(出現(xiàn)比特差錯，0變?yōu)?，或者1變?yōu)?)，從而接受方接收到錯誤的數(shù)據(jù)。為盡量提高接受方收到數(shù)據(jù)的正確率，在接收方接收數(shù)據(jù)之前需要對數(shù)據(jù)進行差錯檢測，當且僅當檢測的結果為正確時接收方才真正收下數(shù)據(jù)。檢測的方式有多種，常見的有奇偶校驗、因特網(wǎng)校驗和循環(huán)冗余校驗等。2. 使用方法概述
循環(huán)冗余校驗是一種用于校驗通信鏈路上數(shù)字傳輸準確性的計算方法（通過某種數(shù)學運算來建立數(shù)據(jù)位和校驗位的約定關系的 ）。發(fā)送方計算機使用某公式計算出被傳送數(shù)據(jù)所含信息的一個值，并將此值 附在被傳送數(shù)據(jù)后，接收方計算機則對同一數(shù)據(jù)進行 相同的計算，應該得到相同的結果。如果這兩個 CRC結果不一致，則說明發(fā)送中出現(xiàn)了差錯，接收方計算機可要求發(fā)送方計算機重新發(fā)送該數(shù)據(jù)。3. 應用廣泛
在諸多檢錯手段中，CRC是最著名的一種。CRC的全稱是循環(huán)冗余校驗，其特點是:檢錯能力強，開銷小，易于用編碼器及檢測電路實現(xiàn)。從其檢錯能力來看，它所不能發(fā)現(xiàn)的錯誤的幾率僅為0.0047%以下。從性能上和開銷上考慮，均遠遠優(yōu)于奇偶校驗及算術和校驗等方式。因而，在數(shù)據(jù)存儲和數(shù)據(jù)通訊領域，CRC無處不在：著名的通訊協(xié)議X.25的FCS(幀檢錯序列)采用的是CRC-CCITT，WinRAR、NERO、ARJ、LHA等壓縮工具軟件采用的是CRC32，磁盤驅(qū)動器的讀寫采用了CRC16，通用的圖像存儲格式GIF、TIFF等也都用CRC作為檢錯手段。二、CRC名稱的定義
這里需要知道幾個組成部分或者說計算概念：多項式公式、多項式簡記式、數(shù)據(jù)寬度、初始值、結果異或值、輸入值反轉、輸出值反轉、參數(shù)模型。1、多項式公式
對于CRC標準除數(shù)，一般使用多項式（或二項式）公式表示，如下圖中除數(shù)11011（poly值為0x1b）的二項式為G(X)=X4 X3 X 1，X的指數(shù)就代表了該bit位上的數(shù)據(jù)為1,（最低位為0）。這里特別注意一下位數(shù)問題，除數(shù)的位數(shù)為二項式最高次冪 1（4 1=5），這個很重要。2、多項式簡記式
通過對CRC的基本了解我們知道，多項式的首尾必定為1，而這個1的位置在下一步計算一定為0，所以就把前面這個1給省略掉了，出現(xiàn)了一個叫簡記式的東西，如上例中除數(shù)11011的簡記式為1011，很多看過CRC高級語言源碼的人會知道，對于CRC_16標準下G(X)=X16 X15 X2 1（16#18005）的poly值實際上是8005，這里使用的就是簡記式。后面會對這個用法做一個說明。3、數(shù)據(jù)寬度
數(shù)據(jù)寬度指的就是CRC校驗碼的長度（二進制位數(shù)），知道了CRC的運算概念和多項式，就可以理解這個概念了，CRC長度始終要比除數(shù)位數(shù)少1，與簡記式長度是一致的。以上三個數(shù)據(jù)就是我們經(jīng)常能夠用到的基本數(shù)據(jù)4、初始值與結果異或值
在一些標準中，規(guī)定了初始值，則數(shù)據(jù)在進行上述二項式運算之前，需要先將要計算的數(shù)據(jù)與初始值的最低字節(jié)進行異或，然后再與多項式進行計算。而在結果異或值不為零的情況下，則需要將計算得到的CRC結果值再與結果異或值進行一次異或計算，得到的最終值才是我們需要的CRC校驗碼。這里可以看出，初始值與結果值的位數(shù)要求與數(shù)據(jù)寬度一致。5、輸入值反轉與輸出值反轉
輸入值反轉的意思是在計算之前先將二項式反轉，然后再用得到的新值和數(shù)據(jù)進行計算。如對于G(X)=X16 X15 X2 1（16#18005），其正向值為1 1000 0000 0000 0101，反轉值則為1010 0000 0000 0001 1輸出值反轉則是將最終得到的CRC結果反轉。通常，輸入值反轉后的結果值也會是反轉的，所以這兩個選項一般是同向的，我們只有在在線CRC計算器中會看到自由選擇正反轉的情況存在。三、常見的CRC算法
雖然CRC可以任意定義二項式、數(shù)據(jù)長度等，但沒有一個統(tǒng)一的標準的話，就會讓整個計算變得非常的麻煩。但實際上，不同的廠家經(jīng)常采用不同的標準算法，這里列出了一些國際常用的模型表：| 名稱 | 多項式 | 表示法 | 應用舉例 |
|---|---|---|---|
| CRC-8 | X8 X2 X 1 | 0X107 | |
| CRC-12 | X12 X11 X3 X2 X 1 | 0X180F | telecom systems |
| CRC-16 | X16 X15 X2 1 | 0X18005 | Bisync, Modbus, USB, ANSI X3.28, SIA DC-07, many others; also known as CRC-16 and CRC-16-ANSI |
| CRC-CCITT | X16 X12 X5 1 | 0X11021 | ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS |
| CRC-32 | X32 X26 X23 X22 X16 X12 X11 X10 X8 X7 X5 X4 X2 X 1 | 0x104C11DB7 | ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS |
| CRC-32C | X32 X28 X27 X26 X25 X23 X22 X20 X19 X18 X14 X13 X11 X10 X9 X8 X6 1 | 0x11EDC6F41 | iSCSI, SCTP, G.hn payload, SSE4.2, Btrfs, ext4, Ceph |
四、CRC校驗算法前置知識
在學習CRC校驗算法之前，先復習一下CRC會涉及的主要幾個主要的算法。1. 異或
異或，就是不同為1，相同為0，運算符號是^。0^0?=?0
0^1?=?1
1^1?=?0
1^0?=?1
異或運算存在如下幾個規(guī)律，需要了解。0^x?=?x?即0?異或任何數(shù)等于任何數(shù)
1^x?=?~x?即1異或任何數(shù)等于任何數(shù)取反
x^x?=?0?即任何數(shù)與自己異或，結果為0
a?^?b?=?b?^?a?交換律
a?^?(b?^?c)?=?(a?^?b)?^c?結合律
2. 模2加法
模2加法相對于普通的算術加法，主要的區(qū)別在模2加法，不做進位處理。具體結果如下。0 0 = 0 0 1 = 1 1 1 = 0 1 0 = 1 我們發(fā)現(xiàn)模2加法的計算結果，同異或運算結果一模一樣。進一步推演，我們會發(fā)現(xiàn)，異或運算的5個規(guī)律，同樣適合于模2加法。這里，就不在一一列舉了。3. 模2減法
模2減法相對于普通的算術減法，主要的區(qū)別在模2減法，不做借位處理。具體結果如下。0-0 = 0 0-1 = 1 1-1 = 0 1-0 = 1 我們發(fā)現(xiàn)模2減法的計算結果，同模2加法，以及異或的運算結果一模一樣。進一步推演，我們會發(fā)現(xiàn)，異或運算的5個規(guī)律，同樣適合于模2減法。這里，就不在一一列舉了。4. 模2除法
模2除法相對于普通的算術除法，主要的區(qū)別在模2除法，它既不向上位借位，也不比較除數(shù)和被除數(shù)的相同位數(shù)值的大小，只要以相同位數(shù)進行相除即可。五、CRC原理
CRC原理：在K位信息碼（目標發(fā)送數(shù)據(jù)）后再拼接R位校驗碼，使整個編碼長度為N位，因此這種編碼也叫（N,K）碼。通俗的說，就是在需要發(fā)送的信息后面附加一個數(shù)（即校驗碼），生成一個新的發(fā)送數(shù)據(jù)發(fā)送給接收端。這個數(shù)據(jù)要求能夠使生成的新數(shù)據(jù)被一個特定的數(shù)整除。這里的整除需要引入模 2除法的概念。那么，CRC校驗的具體做法就是（1）選定一個標準除數(shù)（K位二進制數(shù)據(jù)串）（2）在要發(fā)送的數(shù)據(jù)（m位）后面加上K-1位0，然后將這個新數(shù)（M K-1位）以模2除法的方式除以上面這個標準除數(shù)，所得到的余數(shù)也就是該數(shù)據(jù)的CRC校驗碼（注：余數(shù)必須比除數(shù)少且只少一位，不夠就補0）（3）將這個校驗碼附在原m位數(shù)據(jù)后面，構成新的M K-1位數(shù)據(jù)，發(fā)送給接收端。（4）接收端將接收到的數(shù)據(jù)除以標準除數(shù)，如果余數(shù)為0則認為數(shù)據(jù)正確。注意：CRC校驗中有兩個關鍵點：一是要預先確定一個發(fā)送端和接收端都用來作為除數(shù)的二進制比特串（或多項式）；二是把原始幀與上面選定的除進行二進制除法運算，計算出FCS。前者可以隨機選擇，也可按國際上通行的標準選擇，但最高位和最低位必須均為“1”六、循環(huán)冗余的計算
實例：
由于CRC-32、CRC-16、CCITT和CRC-4的編碼過程基本一致，只有位數(shù)和生成多項式不一樣，下面就舉例，來說明CRC校驗碼生成過程。對于數(shù)據(jù)1110 0101（16#E5），以指定除數(shù)11011求它的CRC校驗碼，其過程如下：使用上面計算的校驗和和消息數(shù)據(jù)，可以創(chuàng)建要傳輸?shù)拇a字。七、代碼實現(xiàn)
實現(xiàn)算法參考網(wǎng)絡相關代碼，進行整理并驗證，可直接使用。crc.c/*??
?*一口Linux
?*2021.6.21
?*version:?1.0.0
*/
#include?"crc.h"
#include?
typedef?enum?{
?REF_4BIT?=?4,
?REF_5BIT?=?5,
?REF_6BIT?=?6,
?REF_7BIT?=?7,
?REF_8BIT?=?8,
?REF_16BIT?=?16,
?REF_32BIT?=?32
}REFLECTED_MODE;
uint32_t?ReflectedData(uint32_t?data,?REFLECTED_MODE?mode)
{
?data?=?((data? 
下載文檔
