找回密码
 立即注册
查看: 139|回复: 4

将查表法crc的查找表优化掉的方法

[复制链接]
  • 打卡等级:常住居民III
  • 打卡总天数:188
  • 最近打卡:2025-10-16 02:21:59

15

主题

92

回帖

791

积分

高级会员

积分
791
发表于 2025-9-23 01:52:40 | 显示全部楼层 |阅读模式
假设我们要计算一个crc8,多项式为0x11。我们对它使用查表法一次计算4位,那他的函数可以写成
unsigned char crc_table[16]=
{
    0x00,0x11,0x22,0x33,
    0x44,0x55,0x66,0x77,
    0x88,0x99,0xAA,0xBB,
    0xCC,0xDD,0xEE,0xFF
};

unsigned char mycrc(unsigned char *data,unsigned int length)
{
    unsigned char crc=0;
    while(length--){
        crc=crc_table[(crc>>4)^(data[0]>>4)]^crc<<4;//计算高4位
        crc=crc_table[(crc>>4)^(data[0]&0x0F)]^crc<<4;//计算低四位
    }
}

我们可以发现查找表的元素与他的索引直接相关,比如索引为0xE对于0xEE,索引为0x8对应0x88。我们可以通过位运算直接省去查找表.

unsigned char mycrc_2(unsigned char *data,unsigned int length)
{
    unsigned char crc=0,temp;
    while(length--){
        temp=(crc>>4)^(data[0]>>4);//计算高4位
        temp|=temp<<4;
        crc=temp^crc<<4;
        temp=(crc>>4)^(data[0]&0x0F);//计算低四位
        temp|=temp<<4;
        crc=temp^crc<<4;
    }
}

mycrc_2这个函数是可以通过逻辑运算化简的
可以写成
unsigned char mycrc_3(unsigned char *data,unsigned int length)
{
    unsigned char crc=0,temp;
    while(length--){
        temp=crc<<4;
        temp^=data[0]<<4;
        temp^=data[0];
        crc^=temp;
        crc=crc<<4|crc>>4;
    }
}
这样对于这种特殊多项式0x11的crc8我们就推导出一个一次可以计算8位数据,且不用查表的函数。

推广一下,一个crc的多项式可以优化并行计算多少位取决于他的多项式里最小的连续0个数,像多项式0x11他的多项式里最小的连续0个数是3,就可以无表并行计算4bit或者3bit或者2bit数据。
如果是crc16-ccitt的多项式0x1021,他的多项式里最小的连续0个数是4,那他最多可以就可以无表并行计算5bit或者4bit或者3bit或者2bit数据。

对crc16-ccitt进行优化
unsigned short crc16_ccitt_new(unsigned char *data, unsigned int length)
{
    unsigned short  crc = 0;
    while (length--)
    {
        unsigned char data_in = *data++;
        unsigned char data_out = crc >> 8;
        crc <<= 8;
        data_out ^= (data_out >> 4);

        data_out ^= (data_in >> 4);
        unsigned short xorred = data_out ^ data_in;
        crc ^= xorred;
        crc ^= xorred <<5;
        crc ^= xorred <<12;
    }
    return crc;
}
        
这个是通过两次并行4bit计算推出来的无表8bit并行计算
下面是测试程序和结果,可以看到优化后的方法时间与串行方法相差无几,结果正确,代码仿照了github上的开源项目pico-sdio-example
IMG_20250923_025110.jpg



截图202509230152298357.jpg



对于同多项式的多通道crc运算,我们可以使用将多通道crc映射为单通道crc的方式进行加速
比如SD卡在4bit传输模式下需要同时计算4个DAT通道的CRC16,多项式为0x1021.
截图202509230208095367.jpg
我们可以构造一个模型,串行计算出一个CRC64,内含4个crc16
截图202509230210057895.jpg
截图202509230211116045.jpg
将4个单通道的CRC16的问题就转化为单通道CRC64的问题,0x1021转化成的多项式0x0001 0000 0100 0001里最小的连续0个数达到23位,可以一次并行计算24位数据,再左脚踩右脚,可以推导出一次计算48位数据的函数
下面是github上的开源项目pico-sdio-example用于计算SD卡在4bit传输模式CRC的函数,一次计算32位数据
截图202509230220248485.jpg







IMG_20250923_025110.jpg
回复

使用道具 举报 送花

3

主题

1880

回帖

608

积分

等待验证会员

积分
608
发表于 2025-9-23 01:53:00 | 显示全部楼层
在CRC(循环冗余校验)算法中,查表法是一种常见的加速实现方式,通过预先计算并存储CRC值,可以显著减少每次计算时的运算量。然而,在某些资源受限或对代码体积敏感的应用场景中,查找表的使用可能会带来额外的存储负担。因此,优化或完全去除查找表,成为一种值得探讨的策略。

以CRC8为例,多项式为0x11(即$x^8 + x^4 + 1$),我们通常采用查表法对每个字节进行处理。而在某些实现中,为了进一步优化性能,还会采用“一次处理4位”的方式,将查找表大小从256项减少到16项,如原帖中所示的crctable[16]。然而,若我们希望进一步减少内存占用或避免使用查找表,可以采用无表计算法(Table-less CRC Calculation)。

一、无表CRC8算法原理

CRC计算本质上是一个基于多项式除法的模2运算。对于CRC8,输入数据被看作一个二进制多项式,与生成多项式进行模2除法,最终的余数即为CRC值。

对于多项式为0x11(即100010001)的CRC8,其核心计算逻辑如下:

```c
unsigned char crc8(unsigned char data, unsigned int length)
{
    unsigned char crc = 0;
    while (length--) {
        crc ^= data++;
        for (int i = 0; i < 8; i++) {
            if (crc & 0x80)
                crc = (crc

[本文内容由国芯人工智能辅助生成,仅供参考]
回复

使用道具 举报 送花

  • 打卡等级:常住居民III
  • 打卡总天数:188
  • 最近打卡:2025-10-16 02:21:59

15

主题

92

回帖

791

积分

高级会员

积分
791
发表于 2025-9-23 01:56:56 | 显示全部楼层
国芯人*** 发表于 2025-9-23 01:53
在CRC(循环冗余校验)算法中,查表法是一种常见的加速实现方式,通过预先计算并存储CRC值,可以显著减少每 ...

基本上现在所有的人工智能大模型都会在crc上吃瘪,我没见过一个ai能讲好crc校验的
回复

使用道具 举报 送花

  • 打卡等级:以坛为家II
  • 打卡总天数:539
  • 最近打卡:2025-10-15 21:55:03

33

主题

2600

回帖

5729

积分

论坛元老

积分
5729
发表于 2025-9-23 09:01:04 | 显示全部楼层
zr*** 发表于 2025-9-23 01:56
基本上现在所有的人工智能大模型都会在crc上吃瘪,我没见过一个ai能讲好crc校验的 ...

这个人工智障还不仅仅会在这里吃瘪,,别的也吃
参考例程并不是对技术参 考手册的补充,而是对技术参 考手册的解释。
技术参 考手册不应该需要参考例程作为补充,而是解释成了参考例程的样子
回复

使用道具 举报 送花

  • 打卡等级:以坛为家I
  • 打卡总天数:209
  • 最近打卡:2025-10-16 08:03:21

787

主题

1万

回帖

1万

积分

管理员

积分
19776
发表于 2025-9-23 10:15:42 | 显示全部楼层
截图202509231015385977.jpg
回复

使用道具 举报 送花

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|深圳国芯人工智能有限公司 ( 粤ICP备2022108929号-2 )

GMT+8, 2025-10-16 10:27 , Processed in 0.122975 second(s), 72 queries .

Powered by Discuz! X3.5

© 2001-2025 Discuz! Team.

快速回复 返回顶部 返回列表