[技術棧]CRC校驗原理及C#代碼實現CRC16、CRC32計算FCS校驗碼
- 2019 年 10 月 3 日
- 筆記
1.CRC、FCS是什麼
CRC，全稱Cyclic Redundancy Check，中文名稱為循環冗餘校驗，是一種根據網絡數據包或計算機文件等數據產生簡短固定位數校驗碼的一種信道編碼技術，主要用來檢測或校驗數據傳輸或者保存後可能出現的錯誤。它是利用除法及餘數的原理來作錯誤偵測的。
FCS，全稱Frame Check Sequence，中文名稱為幀校驗序列，俗稱幀尾，即計算機網絡數據鏈路層的協議數據單元（幀）的尾部字段，是一段4個位元組的循環冗餘校驗碼。
註：CRC循環冗餘校驗和FCS幀校驗序列是單獨的概念，CRC是一種錯誤校驗方法，FCS是幀尾校驗碼，FCS可以採用CRC校驗方法，也可以採用其他校驗方法。
2.CRC算法原理
我們可以把任意的一串二進制數據表示為一個與之對應的多項式。比如：
二進制數據：1100101
多項式：(x^6 + x^5 + x^2+1)
多項式： (x^6 + x^4+x^3 + x^2+1)
二進制數據：1011101
有了這樣的對應關係，對二進制數據的CRC校驗就可以利用多項式運算規則進行校驗計算。
CRC校驗算法正是採用了模2除法，在數據處理里的具體表現為異或運算。
CRC的具體運算規則為：假設要傳輸的二進制數據為：10010110,對應的m階多項式為：(M =x^7+x^4+x^2+x^1)，除數為h階的多項式為：(H=x^4+x)，對應的二進制碼為：10010,先將M乘以(x^h)，即將M對應的二進制數據後面加h個0，然後除以h階的多項式H，得到的h-1階的餘數項R對應的二進制數據即為數據10010110的CRC校驗碼。
3.計算CRC校驗
3.1.手工計算CRC校驗碼
M和H的多項式除法運算，可以用模2除法運算計算。下面為以生成多項式為H求10010110的CRC校驗碼運算過程：
對應到異或運算：
通過示例即其他自定義的一些數據運算後，根據運算現象總結可以得到一些規律：
1.每次異或運算，當從左到右首位為1的時候，就與生成多項式H異或運算，然後再左移1位；當首位為0的時候只將數據左移1位。
2.每次異或運算後的數據，首位必定為0，因為首位為1的時候進行異或運算，而生成多項式的首位也必定為1。所以當需要進行異或運算時，可以捨棄H的首位，捨棄後為H’，直接將數據左移一位後再與H’異或。
3.每次運算，參與運算的是數據的前h位，可以用一個存儲h位二進制數據的寄存器S，將數據的前h位存儲到這個寄存器中。每次運算先將寄存器的首位移除，然後將二進制數據後一位移入，然後再參與運算，最後寄存器中的值即為CRC校驗碼。
3.2.C#代碼計算CRC校驗碼
//代碼驗證如下： static void Main(string[] args) { int data = 0b10010110; int ploy = 0b0010; ploy <<= 4; Console.WriteLine($"第0次運算結果："+Convert.ToString(data, 2)); for (int i = 0; i < 8; i++) { if ((data & 0b10000000) == 0b10000000) { data = (data << 1) ^ ploy; } else { data <<= 1; } Console.WriteLine($"第{i+1}次運算結果："+Convert.ToString(data, 2)); } Console.WriteLine($" 最終運算結果："+Convert.ToString(data, 2)); Console.ReadKey(); } 
這裡用int的第5位到第8位作為一個四位寄存器，可以看到與手算一致，最後算得校驗位1100。
4.查表法
可以看到，參與運算的始終只有4位，所以在移位D1數據時，參與運算的數據只有D1和D2，經過四次移位運算，D1被移除寄存器，這個時候受到影響的只有D2。而將D2的初值經過四次異或運算後的值就可以獲得四次移位後的新數據(D2'=D2bigoplus H1 bigoplus H2bigoplus H3bigoplus H4 = D2 bigoplus sum{h})。
每一次D2是異或0還是異或生成多項式H’，與D2本身的值無關，僅與D1中被移除的數據有關(首位為0還是1)，所以這裡引入了一個查表法，即先將所有可能的D1組合都計算出對應的(sum{h}),一次性移除四位，然後以(D2bigoplus{sum{h}})即可以獲得D2′。
生成多項式為H，則一共有(2^h)種可能，代碼如下：
class CalcByCrcTable { private byte[] CrcTable; private void CteateTable() { int ploy = 0b0010; CrcTable = new byte[(int)Math.Pow(2,4)]; ploy <<= 4; for (int i = 0; i < CrcTable.Length ; i++) { int data = i<<4; for (int j = 0; j < 4; j++) { if ((data & 0b10000000) == 0b10000000) { data = (data << 1) ^ ploy; } else { data <<= 1; } } CrcTable[i] = Convert.ToByte((data & 0xf0)>>4); } } public byte CalcCrc() { CteateTable(); int data = 0b10010110; byte crchigh4 = CrcTable[(data>>4)&0x0f];//用查表法先查到data的高四位1001的crc值； byte value = Convert.ToByte((data & 0x0f) ^ crchigh4);//將高四位的CRC與低四位異或，得到移位四次後的數據值； byte crc = CrcTable[value]; //在用移位後的數據值查出數據的CRC校驗碼； return crc; } } static void Main(string[] args) { CalcByCrcTable calcByCrcTable = new CalcByCrcTable(); byte crc = calcByCrcTable.CalcCrc(); Console.WriteLine($" CRC校驗碼為：" + Convert.ToString(crc, 2)); Console.ReadKey(); }//打印結果如下
CRC校驗碼為：1100
可以看到與前面的計算法結果一致。
5.反向校驗
上面所訴的均為正向檢驗(Normal)，當然也有反向校驗(Reversed)，反向校驗是將數據和生成多項式均進行了一個鏡像，當然算法也需要鏡像，即鏡像後從右往左運算。
5.1手工計算CRC反向校驗碼
原二進制數據：10010110
原生成多項式：0010
正向CRC校驗碼：1100
鏡像二進制數據：01101001
鏡像生成多項式：0100
鏡像算法：
反向CRC校驗碼：0011
5.2.C#代碼計算CRC反向校驗碼
class CalcByCrcTable { private byte[] CrcTable; private void CteateReversedTable() { int ploy = 0b0100; CrcTable = new byte[(int)Math.Pow(2, 4)]; for (int i = 0; i < CrcTable.Length; i++) { int data = i; for (int j = 0; j < 4; j++) { if ((data & 1) == 1) { data = (data >> 1) ^ ploy; } else { data >>= 1; } } CrcTable[i] = Convert.ToByte((data & 0x0f)); } } public byte CalcReversedCrc() { CteateReversedTable(); int data = 0b01101001; byte crclow4 = CrcTable[data & 0x0f];//用用查表法先查到data的低四位1001的crc值； byte value = Convert.ToByte(((data>>4) & 0x0f) ^ crclow4);//將第四位的CRC與低四位異或，得到移位四次後的數據值； byte crc = CrcTable[value]; //在用移位後的數據值查出數據的CRC校驗碼； return crc; } } static void Main(string[] args) { CalcByCrcTable calcByCrcTable = new CalcByCrcTable(); byte crc = calcByCrcTable.CalcReversedCrc(); Console.WriteLine($" CRC反向校驗碼為：" + Convert.ToString(crc, 2)); Console.ReadKey(); }//打印結果如下
CRC反向校驗碼為：11
6.C#查表法計算CRC16校驗碼
//多線程使用時請注意干擾 class CalcOnCrc16 { private ushort[] Crc16NormalTable; private ushort[] Crc16ReversedTable; private void CreateNormalCrc16Table(ushort ploy) { ushort data; Crc16NormalTable = new ushort[256]; int i, j; for (i = 0; i < 256; i++) { data = (ushort)(i << 8); for (j = 0; j < 8; j++) { if ((data & 0x8000) == 0x8000) data = Convert.ToUInt16((ushort)(data << 1) ^ ploy); else data <<= 1; } Crc16NormalTable[i] = data; } } private void CreateReversedCrc16Table(ushort ploy) { ushort data; Crc16ReversedTable = new ushort[256]; int i, j; for (i = 0; i < 256; i++) { data = (ushort)i; for (j = 0; j < 8; j++) { if ((data & 1) == 1) data = Convert.ToUInt16((ushort)(data >>1) ^ ploy); else data >>= 1; } Crc16ReversedTable[i] = data; } } /// <summary> /// 正向計算CRC16校驗碼 /// </summary> /// <param name="bytes">校驗數據</param> /// <param name="poly">生成多項式</param> /// <param name="crcInit">校驗碼初始值</param> /// <returns></returns> public ushort CalcNoemalCrc16(byte[] bytes,ushort poly,ushort crcInit) { CreateNormalCrc16Table(poly); ushort crc = crcInit; for (int i = 0; i < bytes.Length; i++) { crc = Convert.ToUInt16((ushort)(crc << 8) ^ Crc16NormalTable[((crc >> 8) & 0xff) ^ bytes[i]]); } return crc; } /// <summary> /// 反向計算CRC16校驗碼 /// </summary> /// <param name="bytes">校驗數據</param> /// <param name="poly">反向生成多項式</param> /// <param name="crcInit">校驗碼初始值</param> /// <returns></returns> public ushort CalcReversedCrc16(byte[] bytes, ushort poly, ushort crcInit) { CreateReversedCrc16Table(poly); ushort crc = crcInit; for (int i = 0; i < bytes.Length; i++) { crc = Convert.ToUInt16((ushort)(crc >> 8) ^ Crc16ReversedTable[(crc & 0xff) ^ bytes[i]]); } return crc; } }7.C#查表法計算CRC32校驗碼
class CalcOnCrc32 { private uint[] Crc32NormalTable; private uint[] Crc32ReversedTable; private void CreateNormalCrc32Table(uint ploy) { uint data; Crc32NormalTable = new uint[256]; int i, j; for (i = 0; i < 256; i++) { data = (uint)(i << 24); for (j = 0; j < 8; j++) { if ((data & 0x80000000) == 0x80000000) data = Convert.ToUInt32((uint)(data << 1) ^ ploy); else data <<= 1; } Crc32NormalTable[i] = data; } } private void CreateReversedCrc32Table(uint ploy) { uint data; Crc32ReversedTable = new uint[256]; int i, j; for (i = 0; i < 256; i++) { data = (uint)i; for (j = 0; j < 8; j++) { if ((data & 1) == 1) data = Convert.ToUInt32((uint)(data >> 1) ^ ploy); else data >>= 1; } Crc32ReversedTable[i] = data; } } /// <summary> /// 正向計算CRC32校驗碼 /// </summary> /// <param name="bytes">校驗數據</param> /// <param name="poly">生成多項式</param> /// <param name="crcInit">校驗碼初始值</param> /// <returns></returns> public uint CalcNoemalCrc32(byte[] bytes, uint poly, uint crcInit) { CreateNormalCrc32Table(poly); uint crc = crcInit; for (int i = 0; i < bytes.Length; i++) { crc = Convert.ToUInt32((uint)(crc << 8) ^ Crc32NormalTable[((crc >> 24) & 0xff) ^ bytes[i]]); } return crc; } /// <summary> /// 反向計算CRC32校驗碼 /// </summary> /// <param name="bytes">校驗數據</param> /// <param name="poly">反向生成多項式</param> /// <param name="crcInit">校驗碼初始值</param> /// <returns></returns> public uint CalcReversedCrc32(byte[] bytes, uint poly, uint crcInit) { CreateReversedCrc32Table(poly); uint crc = crcInit; for (int i = 0; i < bytes.Length; i++) { crc = Convert.ToUInt32((uint)(crc >> 8) ^ Crc32ReversedTable[(crc & 0xff) ^ bytes[i]]); } return crc; } }