在嵌入式開發(fā)中，經(jīng)常使用到CRC校驗算法，用于校驗通信數(shù)據(jù)和存儲器數(shù)據(jù)。之前只是使用，對CRC原理及各種CRC算法的區(qū)別并無研究。參考網(wǎng)絡(luò)上各位大神的文章和資料，從嵌入式軟件開發(fā)的角度學(xué)習(xí)了下CRC校驗算法，作個總結(jié)記錄。
參考資料：
CRC校驗手算及直觀演示

一、簡介

循環(huán)冗余校驗(Cyclic Redundancy Check, CRC)，是數(shù)據(jù)通信中最常采用的一種數(shù)據(jù)校驗方式。與其他校驗算法（如累加和校驗）相似，CRC校驗也是根據(jù)原始數(shù)據(jù)計算出特定的校驗值作為冗余碼附加在原始數(shù)據(jù)后用于數(shù)據(jù)差錯校驗。不同的是CRC使用模2運算（所謂模2運算，就是數(shù)據(jù)除2去余數(shù)）的方法，根據(jù)校驗數(shù)據(jù)計算出校驗碼。

CRC校驗可以理解為就是一個p位二進(jìn)制數(shù)據(jù)序列后附加一個r位二進(jìn)制校驗碼，從而構(gòu)成一個總長為n = p + r位的二進(jìn)制序列。CRC校驗就是使用多項式模2運算：按異或運算，即相同為0，不同為1，可以簡單理解為不考慮進(jìn)位和借位的二進(jìn)制加減運算，校驗數(shù)據(jù)的二進(jìn)制數(shù)據(jù)流作為多項式的系數(shù)，而多項式系數(shù)作為除數(shù)，而運算后的余數(shù)作為校驗碼。

以CRC7-MMC算法(初值為0x00，多項式為X⁸ X³ + X⁰)為例，CRC校驗計算數(shù)據(jù)“0x11 0x22 0x33 0x44 0x55 0x66 0x77 0x88”過程如下所示：

// 在計算前，要在數(shù)據(jù)流前添加初值，數(shù)據(jù)流后要根據(jù)結(jié)果CRC的BIT數(shù)擴(kuò)展相應(yīng)比特個0。 000000000010001001000100011001101000100010101010110011001110111100010000000000100010010000000000010001100110100010001010101011001100111011110001000000000010001001000001011101000100010101010110011001110111100010000000000100010010011001100100010101010110011001110111100010000000000100010010100010110001010101011001100111011110001000000000010001001000000100001010101011001100111011110001000000000010001001000011000101011001100111011110001000000000010001001010011000110011001110111100010000000000100010010001000111001100111011110001000000000010001001000001110110011101111000100000000001000100101100101111011110001000000000010001001010000101101111000100000000001000100100001100101111000100000000001000100101000010110001000000000010001001000011001000100000000001000100101000001100000000001000100100001010000000000010001001001010010000001000100100101101000010001001001111010010001001

由上計算過程可知，數(shù)據(jù)“0x11 0x22 0x33 0x44 0x55 0x66 0x77 0x88”的CRC-MMC校驗的計算結(jié)果為：0x7D。

二、不同的CRC校驗算法

CRC校驗算法，根據(jù)校驗結(jié)果的位數(shù)，可以分為CRC-4，CRC-7，CRC-8，CRC-16，CRC-32，CRC-64等算法；根據(jù)CRC計算的多項式、初值、輸入是否反轉(zhuǎn)、輸出是否反轉(zhuǎn)、輸出異或值，又可以分為多種算法，如：CRC-16/CCITT，CRC-16/IBM。相同寬度的CRC算法，初值，多項式等信息不同，其校驗的碰撞幾率也不會不同（通俗的講，就是校驗結(jié)果的可靠性，CRC校驗算法，存在一定的幾率會出現(xiàn)校驗數(shù)據(jù)不同，但校驗結(jié)果相同的情況）。不同CRC校驗算法模型的碰撞幾率可以參考相關(guān)理論研究及論文。嵌入式中常用CRC校驗算法模型有：

NameWidthPolyInitRefInRefOutXorOutNote

CRC-16	16	0x8005	0x0000	True	True	0x0000
CRC-16/CCITT	16	0x1021	0x0000	True	True	0x0000
CRC-16/CCITT-FALSE	16	0x1021	0x0000	False	False	0x0000

三、CRC校驗算法代碼實現(xiàn)

在嵌入式應(yīng)用中，實現(xiàn)CRC校驗算法有多種方式。在部分硬件平臺上，存在硬件CRC模塊，因此可以使用硬件CRC算法。硬件無法提供CRC計算的平臺，也可以根據(jù)CRC原理，使用軟件實現(xiàn)CRC算法。便于理解CRC原理，可以使用直接法實現(xiàn)CRC算法。而在實際應(yīng)用，為提高CRC計算速度，通常使用查表法實現(xiàn)CRC算法。

1、直接計算法

實現(xiàn)算法參考網(wǎng)絡(luò)相關(guān)代碼，進(jìn)行整理并驗證，可直接使用，存在一些細(xì)節(jié)還沒想通（如CRC4、5、6、7的計算方法），有興趣的可以一起討論下。

crc.c

#include "crc.h" #include <stdio.h>typedef enum {REF_4BIT = 4,REF_5BIT = 5,REF_6BIT = 6,REF_7BIT = 7,REF_8BIT = 8,REF_16BIT = 16,REF_24BIT = 24,REF_32BIT = 32 }REFLECTED_MODE;uint32_t ReflectedData(uint32_t data, REFLECTED_MODE mode) {data = ((data & 0xffff0000) >> 16) | ((data & 0x0000ffff) << 16);data = ((data & 0xff00ff00) >> 8) | ((data & 0x00ff00ff) << 8);data = ((data & 0xf0f0f0f0) >> 4) | ((data & 0x0f0f0f0f) << 4);data = ((data & 0xcccccccc) >> 2) | ((data & 0x33333333) << 2);data = ((data & 0xaaaaaaaa) >> 1) | ((data & 0x55555555) << 1);switch (mode){case REF_32BIT:return data;case REF_24BIT:return (data >> 8) & 0xffffff;case REF_16BIT:return (data >> 16) & 0xffff;case REF_8BIT:return (data >> 24) & 0xff;case REF_7BIT:return (data >> 25) & 0x7f;case REF_6BIT:return (data >> 26) & 0x7f;case REF_5BIT:return (data >> 27) & 0x1f;case REF_4BIT:return (data >> 28) & 0x0f;}return 0; }uint8_t CheckCrc4(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,const uint8_t *buffer, uint32_t length) {uint8_t i;uint8_t crc;if (refIn == true){crc = init;poly = ReflectedData(poly, REF_4BIT);while (length--){crc ^= *buffer++;for (i = 0; i < 8; i++){if (crc & 0x01){crc >>= 1;crc ^= poly;}else{crc >>= 1;}}}return crc ^ xorOut;}else{crc = init << 4;poly <<= 4;while (length--){crc ^= *buffer++;for (i = 0; i < 8; i++){if (crc & 0x80){crc <<= 1;crc ^= poly;}else{crc <<= 1;}}}return (crc >> 4) ^ xorOut;} }uint8_t CheckCrc5(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,const uint8_t *buffer, uint32_t length) {uint8_t i;uint8_t crc;if (refIn == true){crc = init;poly = ReflectedData(poly, REF_5BIT);while (length--){crc ^= *buffer++;for (i = 0; i < 8; i++){if (crc & 0x01){crc >>= 1;crc ^= poly;}else{crc >>= 1;}}}return crc ^ xorOut;}else{crc = init << 3;poly <<= 3;while (length--){crc ^= *buffer++;for (i = 0; i < 8; i++){if (crc & 0x80){crc <<= 1;crc ^= poly;}else{crc <<= 1;}}}return (crc >> 3) ^ xorOut;} }uint8_t CheckCrc6(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,const uint8_t *buffer, uint32_t length) {uint8_t i;uint8_t crc;if (refIn == true){crc = init;poly = ReflectedData(poly, REF_6BIT);while (length--){crc ^= *buffer++;for (i = 0; i < 8; i++){if (crc & 0x01){crc >>= 1;crc ^= poly;}else{crc >>= 1;}}}return crc ^ xorOut;}else{crc = init << 2;poly <<= 2;while (length--){crc ^= *buffer++;for (i = 0; i < 8; i++){if (crc & 0x80){crc <<= 1;crc ^= poly;}else{crc <<= 1;}}}return (crc >> 2) ^ xorOut;} }uint8_t CheckCrc7(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,const uint8_t *buffer, uint32_t length) {uint8_t i;uint8_t crc;if (refIn == true){crc = init;poly = ReflectedData(poly, REF_7BIT);while (length--){crc ^= *buffer++;for (i = 0; i < 8; i++){if (crc & 0x01){crc >>= 1;crc ^= poly;}else{crc >>= 1;}}}return crc ^ xorOut;}else{crc = init << 1;poly <<= 1;while (length--){crc ^= *buffer++;for (i = 0; i < 8; i++){if (crc & 0x80){crc <<= 1;crc ^= poly;}else{crc <<= 1;}}}return (crc >> 1) ^ xorOut;} }uint8_t CheckCrc8(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,const uint8_t *buffer, uint32_t length) {uint32_t i = 0;uint8_t crc = init;while (length--){if (refIn == true){crc ^= ReflectedData(*buffer++, REF_8BIT);}else{crc ^= *buffer++;}for (i = 0; i < 8; i++){if (crc & 0x80){crc <<= 1;crc ^= poly;}else{crc <<= 1;}}}if (refOut == true){crc = ReflectedData(crc, REF_8BIT);}return crc ^ xorOut; }uint16_t CheckCrc16(uint16_t poly, uint16_t init, bool refIn, bool refOut, uint16_t xorOut,const uint8_t *buffer, uint32_t length) {uint32_t i = 0;uint16_t crc = init;while (length--){if (refIn == true){crc ^= ReflectedData(*buffer++, REF_8BIT) << 8;}else{crc ^= (*buffer++) << 8;}for (i = 0; i < 8; i++){if (crc & 0x8000){crc <<= 1;crc ^= poly;}else{crc <<= 1;}}}if (refOut == true){crc = ReflectedData(crc, REF_16BIT);}return crc ^ xorOut; }uint32_t CheckCrc24(uint32_t poly, uint32_t init, bool refIn, bool refOut, uint32_t xorOut,const uint8_t *buffer, uint32_t length) {uint32_t i = 0;uint32_t crc = init;while (length--){if (refIn == true){crc ^= ReflectedData(*buffer++, REF_8BIT) << 16;}else{crc ^= (*buffer++) << 16;}for (i = 0; i < 8; i++){if (crc & 0x800000){crc <<= 1;crc ^= poly;}else{crc <<= 1;}}}if (refOut == true){crc = ReflectedData(crc, REF_24BIT);}return (crc ^ xorOut) & 0xffffff; }uint32_t CheckCrc32(uint32_t poly, uint32_t init, bool refIn, bool refOut, uint32_t xorOut,const uint8_t *buffer, uint32_t length) {uint32_t i = 0;uint32_t crc = init;while (length--){if (refIn == true){crc ^= ReflectedData(*buffer++, REF_8BIT) << 24;}else{crc ^= (*buffer++) << 24;}for (i = 0; i < 8; i++){if (crc & 0x80000000){crc <<= 1;crc ^= poly;}else{crc <<= 1;}}}if (refOut == true){crc = ReflectedData(crc, REF_32BIT);}return crc ^ xorOut; }uint32_t CrcCheck(CRC_Type crcType, const uint8_t *buffer, uint32_t length) {switch (crcType.width){case 4:return CheckCrc4(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,crcType.xorOut, buffer, length);case 5:return CheckCrc5(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,crcType.xorOut, buffer, length);case 6:return CheckCrc6(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,crcType.xorOut, buffer, length);case 7:return CheckCrc7(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,crcType.xorOut, buffer, length);case 8:return CheckCrc8(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,crcType.xorOut, buffer, length);case 16:return CheckCrc16(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,crcType.xorOut, buffer, length);case 24:return CheckCrc24(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,crcType.xorOut, buffer, length);case 32:return CheckCrc32(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,crcType.xorOut, buffer, length);}return 0; }

crc.h

#ifndef __CRC_H__ #define __CRC_H__#include <stdint.h> #include <stdbool.h>typedef struct {uint8_t width;uint32_t poly;uint32_t init;bool refIn;bool refOut;uint32_t xorOut; }CRC_Type;uint32_t CrcCheck(CRC_Type crcType, const uint8_t *buffer, uint32_t length);#endif

main.c

#include <stdio.h> #include <stdint.h> #include <stdbool.h> #include "crc.h"#define LENGTH 8 const uint8_t data[3][LENGTH] = {{ 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },{ 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 },{ 0xfe, 0xfd, 0xfb, 0xf7, 0xef, 0xdf, 0xbf, 0x7f } };typedef struct {CRC_Type crcType;uint32_t result[3]; }CRC_Test;CRC_Test crc4_ITU = { { 4, 0x03, 0x00, true, true, 0x00 }, { 0x0f, 0x0a, 0x0e } }; CRC_Test crc5_EPC = { { 5, 0x09, 0x09, false, false, 0x00 }, { 0x00, 0x0c, 0x17 } }; CRC_Test crc5_ITU = { { 5, 0x15, 0x00, true, true, 0x00 }, { 0x16, 0x0a, 0x17 } }; CRC_Test crc5_USB = { { 5, 0x05, 0x1f, true, true, 0x1f }, { 0x10, 0x09, 0x17 } }; CRC_Test crc6_ITU = { { 6, 0x03, 0x00, true, true, 0x00 }, { 0x1d, 0x30, 0x00 } }; CRC_Test crc7_MMC = { { 7, 0x09, 0x00, false, false, 0x00 }, { 0x57, 0x30, 0x5b } }; CRC_Test crc8 = { { 8, 0x07, 0x00, false, false, 0x00 }, { 0x3e, 0xe1, 0x36 } }; CRC_Test crc8_ITU = { { 8, 0x07, 0x00, false, false, 0x55 }, { 0x6b, 0xb4, 0x63 } }; CRC_Test crc8_ROHC = { { 8, 0x07, 0xff, true, true, 0x00 }, { 0x6b, 0x78, 0x93 } }; CRC_Test crc8_MAXIM = { { 8, 0x31, 0x00, true, true, 0x00 }, { 0x83, 0x60, 0xa9 } }; CRC_Test crc16_IBM = { { 16, 0x8005, 0x0000, true, true, 0x0000 }, { 0xc4f0, 0x2337, 0xa776 } }; CRC_Test crc16_MAXIM = { { 16, 0x8005, 0x0000, true, true, 0xffff }, { 0x3b0f, 0xdcc8, 0x5889 } }; CRC_Test crc16_USB = { { 16, 0x8005, 0xffff, true, true, 0xffff }, { 0x304f, 0xd788, 0x53c9 } }; CRC_Test crc16_MODBUS = { { 16, 0x8005, 0xffff, true, true, 0x0000 }, { 0xcfb0, 0x2877, 0xac36 } }; CRC_Test crc16_CCITT = { { 16, 0x1021, 0x0000, true, true, 0x0000 }, { 0xeea7, 0xfe7c, 0x7919 } }; CRC_Test crc16_CCITT_FALSE = { { 16, 0x1021, 0xffff, false, false, 0x0000 }, { 0x4792, 0x13a7, 0xb546 } }; CRC_Test crc16_X25 = { { 16, 0x1021, 0xffff, true, true, 0xffff }, { 0x6dd5, 0x7d0f, 0xfa6a } }; CRC_Test crc16_XMODEM = { { 16, 0x1021, 0x0000, false, false, 0x0000 }, { 0x76ac, 0x2299, 0x8478 } }; CRC_Test crc16_DNP = { { 16, 0x3D65, 0x0000, true, true, 0xffff }, { 0x7bda, 0x0535, 0x08c4 } }; CRC_Test crc24 = { { 24, 0x864cfb, 0x000000, false, false, 0x000000 }, { 0x4c9612, 0x352d9f, 0x1c3c32 } }; CRC_Test crc32 = { { 32, 0x04c11db7, 0xffffffff, true, true, 0xffffffff }, { 0x3fca88c5, 0xe0631a53, 0xa4051a26 } }; CRC_Test crc32_MPEG2 = { { 32, 0x4c11db7, 0xffffffff, false, false, 0x00000000 }, { 0x14dbbdd8, 0x6509b4b6, 0xcb09d294 } };void CrcTest(CRC_Test crcTest) {uint32_t i;for (i = 0; i < 3; i++){printf("%08x\t%08x\r\n", CrcCheck(crcTest.crcType, data[i], LENGTH), crcTest.result[i]);}printf("\r\n"); }int main(void) {CrcTest(crc4_ITU);CrcTest(crc5_EPC);CrcTest(crc5_ITU);CrcTest(crc5_USB);CrcTest(crc6_ITU);CrcTest(crc7_MMC);CrcTest(crc8);CrcTest(crc8_ITU);CrcTest(crc8_ROHC);CrcTest(crc8_MAXIM);CrcTest(crc16_IBM);CrcTest(crc16_MAXIM);CrcTest(crc16_USB);CrcTest(crc16_MODBUS);CrcTest(crc16_CCITT);CrcTest(crc16_CCITT_FALSE);CrcTest(crc16_X25);CrcTest(crc16_XMODEM);CrcTest(crc16_DNP);CrcTest(crc24);CrcTest(crc32);CrcTest(crc32_MPEG2);return 0; }

四、注意

• 不同的CRC算法，對00H或FFH數(shù)據(jù)流的計算結(jié)果不一樣，部分算法存在校驗結(jié)果也為00H或FFH的情況（也就意味著存儲空間處于初始化狀態(tài)時：全0或全1，CRC校驗反而是正確的），在應(yīng)用中需要注意避免。
• 對數(shù)據(jù)流的CRC校驗進(jìn)行檢查時，可以將原數(shù)據(jù)流和CRC校驗結(jié)果一起再做CRC校驗，若CRC校驗正確則計算結(jié)果為0。利用這個特性可簡化CRC驗證的軟件實現(xiàn)（對CRC校驗結(jié)果又進(jìn)行異或非0的CRC算法不適用）。

總結(jié)

以上是生活随笔為你收集整理的CRC校验算法及实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。