AI 助理
备案控制台
开发者社区 物联网 文章 正文

以太网帧FCS校验：CRC32的三种实现

2024-06-11 341
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 这篇文章讨论了CRC32校验码的三种实现方法，用于检测网络通信中的数据错误。首先介绍了基础的按位计算方法，虽然直观但效率低。接着，文章提出了使用非翻转查找表和翻转查找表的快速计算方法，后者在性能上更优。文中提供了C++代码示例，展示如何生成和使用这些查找表。最后，指出在实际应用中，应根据性能需求选择合适的方法。

改文章是我在2011年写于某sdn的， 搬运过来。


在网络通信中，循环冗余校验（CRC）是一种广泛使用的检错码，用于检测数据传输过程中的错误。其中，CRC32由于其良好的检错能力和相对较低的计算复杂度，成为许多协议（包括以太网）中首选的检错机制。本文将深入探讨CRC32校验码的三种实现方法，并提供详细的代码实现。


方法一：按位计算CRC32校验码

这是最基础也是最直观的实现方式，它逐位地进行异或和移位操作，适用于理解CRC算法原理，但计算效率较低。

代码实现：

Cpp

#include <cstdint>

uint32_t crc32_bitwise(uint32_t polynomial, uint32_t initial, const void *data, size_t len) {
    uint32_t crc = initial;
    const unsigned char *ptr = (const unsigned char *)data;
    
    for (size_t i = 0; i < len; i++) {
        crc ^= ((uint32_t)(*ptr++)) << 24;
        for (int j = 0; j < 8; j++) {
            if (crc & 0x80000000)
                crc = (crc << 1) ^ polynomial;
            else
                crc <<= 1;
        }
    }
    return crc;
}

方法二：使用非翻转的查找表进行快速计算

为了提高计算速度，可以预先生成一个查找表，每次处理一个字节的数据。然而，这种实现通常包含位翻转操作，影响了计算效率。

代码实现：

Cpp

#include <cstdint>
#include <array>

constexpr uint32_t POLYNOMIAL = 0xEDB88320;
std::array<uint32_t, 256> crc_table;

void generate_crc_table() {
    for (int i = 0; i < 256; i++) {
        uint32_t crc = i;
        for (int j = 0; j < 8; j++) {
            if (crc & 1)
                crc = (crc >> 1) ^ POLYNOMIAL;
            else
                crc >>= 1;
        }
        crc_table[i] = crc;
    }
}

uint32_t crc32_lookup(uint32_t initial, const void *data, size_t len) {
    uint32_t crc = ~initial;
    const unsigned char *ptr = (const unsigned char *)data;
    
    for (size_t i = 0; i < len; i++)
        crc = (crc >> 8) ^ crc_table[(crc ^ *ptr++) & 0xFF];
    
    return ~crc;
}

方法三：使用翻转的查找表进行快速计算

这种方法通过预先翻转输入数据和查找表中的值，避免了在计算过程中的位翻转操作，从而极大地提高了计算速度。

代码实现：

Cpp

#include <cstdint>
#include <array>

constexpr uint32_t POLYNOMIAL = 0xEDB88320;
std::array<uint32_t, 256> crc_table;

void generate_crc_table_flip() {
    for (int i = 0; i < 256; i++) {
        uint32_t crc = i;
        for (int j = 0; j < 8; j++) {
            crc = (crc >> 1) ^ (-(crc & 1) & POLYNOMIAL);
        }
        crc_table[i] = crc;
    }
}

uint32_t crc32_lookup_flip(uint32_t initial, const void *data, size_t len) {
    uint32_t crc = initial;
    const unsigned char *ptr = (const unsigned char *)data;
    
    for (size_t i = 0; i < len; i++)
        crc = crc_table[(crc ^ *ptr++) & 0xFF] ^ (crc >> 8);
    
    return crc;
}

结论

在实际应用中，根据性能需求和资源限制选择合适的CRC32实现至关重要。尽管按位计算提供了最清晰的算法理解，但在性能要求较高的场景下，使用查找表的方法（特别是翻转的查找表）能提供显著的速度优势。希望本文的代码实现能帮助读者更好地理解和应用CRC32校验码。




完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <io.h>
 
 
 
 
#define alt_8    char
#define alt_u8   unsigned char
#define alt_32   int
#define alt_u32  unsigned int
#define alt_64   long long
#define alt_u64  unsigned long long
 
 
//位翻转函数
alt_u64 Reflect(alt_u64 ref,alt_u8 ch)
{   
    int i;
    alt_u64 value = 0;
    for( i = 1; i < ( ch + 1 ); i++ )
    {
        if( ref & 1 )
            value |= 1 << ( ch - i );
        ref >>= 1;
    }
    return value;
}
 
 
//标准的CRC32多项式
#define poly  0x04C11DB7
//翻转的CRC32多项式
#define upoly 0xEDB88320
 
 
 
alt_u32 crc32_bit(alt_u8 *ptr, alt_u32 len, alt_u32 gx)
{
    alt_u8 i;
    alt_u32 crc = 0xffffffff;
    while( len-- )
    {
        for( i = 1; i != 0; i <<= 1 )
        {
            if( ( crc & 0x80000000 ) != 0 )
            {
                crc <<= 1;
                crc ^= gx;
            }
            else 
                crc <<= 1;
            if( ( *ptr & i ) != 0 ) 
                crc ^= gx;
        }
        ptr++;
    }
    return ( Reflect(crc,32) ^ 0xffffffff );
}
 
 
 
 
 
 
alt_u32 Table1[256];
alt_u32 Table2[256];
 
 
 
 
 // 生成CRC32 普通表 , 第二项是04C11DB7
void gen_direct_table(alt_u32 *table)
{
    alt_u32 gx = 0x04c11db7;
    unsigned long i32, j32;
    unsigned long nData32;
    unsigned long nAccum32;
    for ( i32 = 0; i32 < 256; i32++ )
    {
        nData32 = ( unsigned long )( i32 << 24 );
        nAccum32 = 0;
        for ( j32 = 0; j32 < 8; j32++ )
        {
            if ( ( nData32 ^ nAccum32 ) & 0x80000000 )
                nAccum32 = ( nAccum32 << 1 ) ^ gx;
            else
                nAccum32 <<= 1;
            nData32 <<= 1;
        }
        table[i32] = nAccum32;
    }
}
 
 
// 生成CRC32 翻转表 第二项是77073096
void gen_normal_table(alt_u32 *table)
{
    alt_u32 gx = 0x04c11db7;
    alt_u32 temp,crc;
    for(int i = 0; i <= 0xFF; i++) 
    {
        temp=Reflect(i, 8);
        table[i]= temp<< 24;
        for (int j = 0; j < 8; j++)
        {
            unsigned long int t1,t2;
            unsigned long int flag=table[i]&0x80000000;
            t1=(table[i] << 1);
            if(flag==0)
            t2=0;
            else
            t2=gx;
            table[i] =t1^t2 ;
        }
        crc=table[i];
        table[i] = Reflect(table[i], 32);
    }
}
 
 
 
alt_u32 DIRECT_TABLE_CRC(alt_u8 *ptr,int len, alt_u32 * table) 
{
    alt_u32 crc = 0xffffffff; 
    alt_u8 *p= ptr;
    int i;
    for ( i = 0; i < len; i++ )
        crc = ( crc << 8 ) ^ table[( crc >> 24 ) ^ (alt_u8)Reflect((*(p+i)), 8)];
    return ~(alt_u32)Reflect(crc, 32) ;
}
 
 
 
 
alt_u32 Reverse_Table_CRC(alt_u8 *data, alt_32 len, alt_u32 * table)
{
    alt_u32 crc = 0xffffffff;  
    alt_u8 *p = data;
    int i;
    for(i=0; i <len; i++)
        crc =  table[( crc ^( *(p+i)) ) & 0xff] ^ (crc >> 8);
    return  ~crc ; 
}
 
 
 
//这是一个完整的以太网帧。最后四个字节 8b 6b f5 13是其FCS字段，用于与后面生成的CRC32对照
alt_u8  tx_data[] = {
        0xff,   0xff,   0xff,   0xff,   0xff,   0xff,   0x00,   0x1f,   //8
        0x29,   0x00,   0xb5,   0xfa,   0x08,   0x06,   0x00,   0x01,   //15
        0x08,   0x00,   0x06,   0x04,   0x00,   0x01,   0x00,   0x1f,   //24
        0x29,   0x00,   0xb5,   0xfa,   0xac,   0x15,   0x0e,   0xd9,   //32
        0x00,   0x00,   0x00,   0x00,   0x00,   0x00,   0xac,   0x15,   //40
        0x0e,   0x8e,   0x00,   0x00,   0x00,   0x00,   0x00,   0x00,   //48
        0x00,   0x00 ,  0x00,   0x00,   0x00,   0x00,   0x00,   0x00,   //56
        0x00,   0x00,   0x00,   0x00,   0x8b,   0x6b,   0xf5,   0x13    //64
};
 
 
 
 
int main()
{
    alt_u8 *data = tx_data;
    alt_u32 dataLen = sizeof(tx_data) -4;
  
    int sum = 256;
    int i = 0;
 
    //生成普通表，用于直接计算的表
    gen_direct_table(Table1);
    printf("Table1 :\n");
    for( i = 0; i < sum; i++)
    {
        if(i<16)
            printf("%08x ",Table1[i]);
    }
    printf("\n\n");
 
 
    //生成翻转表，是官方推荐的，故称其为normal_table
    gen_normal_table(Table2);
    printf("Table2 :\n");
    for( i = 0; i < sum; i++)
    {
        if(i<16)
            printf("%08x ",Table2[i]);
    }
    printf("\n\n");
 
 
 
    printf("dataLen = %d\n",dataLen);//打印数据长度，应该是60字节。
 
 
 
    //计算并打印出CRC32校验码，应该是0x13f56b8b
 
    //按照bit进行校验，最慢
    printf("Slow CRC by bit          : %08x\n",crc32_bit( data, dataLen, 0x04c11db7 ));
    //使用普通表，非官方，很慢
    printf("Direct Table  ref + xor  : %08x\n",DIRECT_TABLE_CRC (data,dataLen,Table1)); 
    //使用翻转表，官方推荐的，很快
    printf("Reverse Table  ref + xor : %08x\n",Reverse_Table_CRC(data,dataLen,Table2)); 
 
 
    system("pause");    
    return 0;
}
文章标签：
C++
算法
SDN
蓝色流星1000
目录
相关文章
sky_qiyi
|
3月前
|
算法
计算机网络——数据链路层-差错检测（奇偶校验、循环冗余校验CRC）
计算机网络——数据链路层-差错检测（奇偶校验、循环冗余校验CRC）
sky_qiyi
178 0
sky_qiyi
|
3月前
计算机网络——数据链路层-封装成帧（帧定界、透明传输-字节填充，比特填充、MTU）
计算机网络——数据链路层-封装成帧（帧定界、透明传输-字节填充，比特填充、MTU）
sky_qiyi
164 0
dulu~dulu
|
4月前
CRC与FCS的区别和联系
CRC与FCS的区别和联系
dulu~dulu
123 0
狗哥不是甜妹
|
11月前
|
自然语言处理 网络协议 算法
UDP协议和报文格式，校验和，CRC的含义
UDP协议和报文格式，校验和，CRC的含义
狗哥不是甜妹
201 0
帐篷Li
|
4月前
|
算法
Modbus-ASCII数据帧
Modbus-ASCII数据帧
帐篷Li
60 1
浩泽学编程
|
4月前
|
传感器 C++
计算机网络：数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码
计算机网络：数据链路层之差错控制、奇偶校验码、CRC循环冗余码、海明码
浩泽学编程
126 0
Paranoid
CRC校验-基于MODBUS协议实现源码
CRC校验-基于MODBUS协议实现源码
Paranoid
105 0
扯淡散人
|
4月前
|
算法
【数据链路层】循环冗余码CRC、后退N帧协议GBN、选择重传协议SR、CSMA/CA
【数据链路层】循环冗余码CRC、后退N帧协议GBN、选择重传协议SR、CSMA/CA
扯淡散人
86 0
Python-派大星
|
缓存 网络协议 网络架构
以太网数据链路层、Ethernet_II帧格式、IEEE802.3帧格式，以太网的MAC地址的组成，ARP地址解析协议的工作原理，单播帧、组播帧、广播帧的区别
数据链路层，Ethernet_II帧格式、IEEE802.3帧格式,帧格式的区分以及链路层每种帧格式有什么作用，怎么区别分辨帧格式，以太网MAC地址的组成，ARP地址解析协议原理、什么是单播帧？什么是组播数据帧？什么是广播帧？...............
Python-派大星
610 0
以太网数据链路层、Ethernet_II帧格式、IEEE802.3帧格式，以太网的MAC地址的组成，ARP地址解析协议的工作原理，单播帧、组播帧、广播帧的区别
3it3iap2n2xxu
|
传感器 人机交互
STM32:串口收发HEX数据包理论篇(内含：1.实验现象+2.文本数据包/HEX数据包+ 3.文本数据包接收/HEX数据包接收)
STM32:串口收发HEX数据包理论篇(内含：1.实验现象+2.文本数据包/HEX数据包+ 3.文本数据包接收/HEX数据包接收)
3it3iap2n2xxu
602 0
STM32:串口收发HEX数据包理论篇(内含：1.实验现象+2.文本数据包/HEX数据包+ 3.文本数据包接收/HEX数据包接收)

物联网

热门文章

最新文章

  • 1
    直播学习-AliOS Things 3.0
  • 2
    基于AliOS Things玩转智能语音
  • 3
    PostgreSQL 物联网黑科技 - 瘦身500倍的索引(范围索引)
  • 4
    PostgreSQL 数据库 物联网 应用分析
  • 5
    物联网技术在智能医疗的应用
  • 6
    【物联网】OpenWrt OpenWRT的源码下载及目录结构
  • 7
    GPRS模组通过MQTT和阿里云服务器通讯
  • 8
    AliOS Things 3.0应用笔记：支付宝小程序设备控制 - 全栈开发（附全部源码）
  • 9
    一文看懂物联网完整产业链条
  • 10
    小程序无需编程，体验IoT物联网平台-物模型开发
  • 1
    物联网：“定向卡”与“通用卡”的区别
    16
  • 2
    物联网：“物联网卡里你不知道的那些秘密与操作”
    22
  • 3
    物联网：物联网，作为新一代信息技术的重要组成部分，通过智能感知、识别技术与普适计算等通信感知技术，将各种信息传感设备与互联网结合起来而形成的一个巨大网络，实现了物物相连、人物相连，开启了万物互联的新时代。
    15
  • 4
    物联网卡
    34
  • 5
    物联网开发中C、C++和C#哪个更好用
    20
  • 6
    C 标准库
    20
  • 7
    物联卡：物联网卡和SIM卡的不同
    33
  • 8
    物联网卡：为什么物联网卡流量价格相对来说较为优惠
    47
  • 9
    物联网卡：如何选择物联网卡流量套餐
    28
  • 10
    物联网卡：物联网卡在智能家居设备中扮演的角色
    27

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    使用OSS上传下载文件