CRC校验算法及实现

2023-08-11 11:19| 来源: 网络整理| 查看: 265

在嵌入式开发中，经常使用到CRC校验算法，用于校验通信数据和存储器数据。之前只是使用，对CRC原理及各种CRC算法的区别并无研究。参考网络上各位大神的文章和资料，从嵌入式软件开发的角度学习了下CRC校验算法，作个总结记录。参考资料： CRC校验手算及直观演示

一、简介

循环冗余校验(Cyclic Redundancy Check, CRC)，是数据通信中最常采用的一种数据校验方式。与其他校验算法（如累加和校验）相似，CRC校验也是根据原始数据计算出特定的校验值作为冗余码附加在原始数据后用于数据差错校验。不同的是CRC使用模2运算（所谓模2运算，就是数据除2去余数）的方法，根据校验数据计算出校验码。

CRC校验可以理解为就是一个p位二进制数据序列后附加一个r位二进制校验码，从而构成一个总长为n = p + r位的二进制序列。CRC校验就是使用多项式模2运算：按异或运算，即相同为0，不同为1，可以简单理解为不考虑进位和借位的二进制加减运算，校验数据的二进制数据流作为多项式的系数，而多项式系数作为除数，而运算后的余数作为校验码。

以CRC7-MMC算法(初值为0x00，多项式为X8 X3 + X0)为例，CRC校验计算数据“0x11 0x22 0x33 0x44 0x55 0x66 0x77 0x88”过程如下所示：

// 在计算前，要在数据流前添加初值，数据流后要根据结果CRC的BIT数扩展相应比特个0。 000000000010001001000100011001101000100010101010110011001110111100010000000000 10001001 00000000000100011001101000100010101010110011001110111100010000000000 10001001 000001011101000100010101010110011001110111100010000000000 10001001 0011001100100010101010110011001110111100010000000000 10001001 01000101100010101010110011001110111100010000000000 10001001 0000001000010101010110011001110111100010000000000 10001001 0000110001010110011001110111100010000000000 10001001 010011000110011001110111100010000000000 10001001 00010001110011001110111100010000000000 10001001 00000111011001110111100010000000000 10001001 011001011110111100010000000000 10001001 01000010110111100010000000000 10001001 0000110010111100010000000000 10001001 010000101100010000000000 10001001 00001100100010000000000 10001001 0100000110000000000 10001001 000010100000000000 10001001 00101001000000 10001001 001011010000 10001001 0011110100 10001001

由上计算过程可知，数据“0x11 0x22 0x33 0x44 0x55 0x66 0x77 0x88”的CRC-MMC校验的计算结果为：0x7D。

二、不同的CRC校验算法

CRC校验算法，根据校验结果的位数，可以分为CRC-4，CRC-7，CRC-8，CRC-16，CRC-32，CRC-64等算法；根据CRC计算的多项式、初值、输入是否反转、输出是否反转、输出异或值，又可以分为多种算法，如：CRC-16/CCITT，CRC-16/IBM。相同宽度的CRC算法，初值，多项式等信息不同，其校验的碰撞几率也不会不同（通俗的讲，就是校验结果的可靠性，CRC校验算法，存在一定的几率会出现校验数据不同，但校验结果相同的情况）。不同CRC校验算法模型的碰撞几率可以参考相关理论研究及论文。嵌入式中常用CRC校验算法模型有：

NameWidthPolyInitRefInRefOutXorOutNoteCRC-16160x80050x0000TrueTrue0x0000CRC-16/CCITT160x10210x0000TrueTrue0x0000CRC-16/CCITT-FALSE160x10210x0000FalseFalse0x0000 三、CRC校验算法代码实现

在嵌入式应用中，实现CRC校验算法有多种方式。在部分硬件平台上，存在硬件CRC模块，因此可以使用硬件CRC算法。硬件无法提供CRC计算的平台，也可以根据CRC原理，使用软件实现CRC算法。便于理解CRC原理，可以使用直接法实现CRC算法。而在实际应用，为提高CRC计算速度，通常使用查表法实现CRC算法。

1、直接计算法

实现算法参考网络相关代码，进行整理并验证，可直接使用，存在一些细节还没想通（如CRC4、5、6、7的计算方法），有兴趣的可以一起讨论下。

crc.c

#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_24BIT = 24, REF_32BIT = 32 }REFLECTED_MODE; uint32_t ReflectedData(uint32_t data, REFLECTED_MODE mode) { data = ((data & 0xffff0000) >> 16) | ((data & 0x0000ffff) 8) | ((data & 0x00ff00ff) 4) | ((data & 0x0f0f0f0f) 2) | ((data & 0x33333333) 1) | ((data & 0x55555555) uint8_t i; uint8_t crc; if (refIn == true) { crc = init; poly = ReflectedData(poly, REF_4BIT); while (length--) { crc ^= *buffer++; for (i = 0; i crc >>= 1; crc ^= poly; } else { crc >>= 1; } } } return crc ^ xorOut; } else { crc = init if (crc & 0x80) { crc uint8_t i; uint8_t crc; if (refIn == true) { crc = init; poly = ReflectedData(poly, REF_5BIT); while (length--) { crc ^= *buffer++; for (i = 0; i crc >>= 1; crc ^= poly; } else { crc >>= 1; } } } return crc ^ xorOut; } else { crc = init if (crc & 0x80) { crc uint8_t i; uint8_t crc; if (refIn == true) { crc = init; poly = ReflectedData(poly, REF_6BIT); while (length--) { crc ^= *buffer++; for (i = 0; i crc >>= 1; crc ^= poly; } else { crc >>= 1; } } } return crc ^ xorOut; } else { crc = init if (crc & 0x80) { crc uint8_t i; uint8_t crc; if (refIn == true) { crc = init; poly = ReflectedData(poly, REF_7BIT); while (length--) { crc ^= *buffer++; for (i = 0; i crc >>= 1; crc ^= poly; } else { crc >>= 1; } } } return crc ^ xorOut; } else { crc = init if (crc & 0x80) { crc 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 crc 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) if (crc & 0x8000) { crc 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) if (crc & 0x800000) { crc 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) if (crc & 0x80000000) { crc 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 #include 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 #include #include #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 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数据流的计算结果不一样，部分算法存在校验结果也为00H或FFH的情况（也就意味着存储空间处于初始化状态时：全0或全1，CRC校验反而是正确的），在应用中需要注意避免。对数据流的CRC校验进行检查时，可以将原数据流和CRC校验结果一起再做CRC校验，若CRC校验正确则计算结果为0。利用这个特性可简化CRC验证的软件实现（对CRC校验结果又进行异或非0的CRC算法不适用）。

【本文地址】

公司简介

联系我们