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

zr***

假设我们要计算一个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






对于同多项式的多通道crc运算，我们可以使用将多通道crc映射为单通道crc的方式进行加速
比如SD卡在4bit传输模式下需要同时计算4个DAT通道的CRC16，多项式为0x1021.

我们可以构造一个模型，串行计算出一个CRC64，内含4个crc16


将4个单通道的CRC16的问题就转化为单通道CRC64的问题，0x1021转化成的多项式0x0001 0000 0100 0001里最小的连续0个数达到23位，可以一次并行计算24位数据，再左脚踩右脚，可以推导出一次计算48位数据的函数
下面是github上的开源项目pico-sdio-example用于计算SD卡在4bit传输模式CRC的函数，一次计算32位数据

国芯人***

在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

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

zr***

国芯人*** 发表于 2025-9-23 01:53
在CRC（循环冗余校验）算法中，查表法是一种常见的加速实现方式，通过预先计算并存储CRC值，可以显著减少每 ...

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

_奶***

zr*** 发表于 2025-9-23 01:56
基本上现在所有的人工智能大模型都会在crc上吃瘪，我没见过一个ai能讲好crc校验的 ...

这个人工智障还不仅仅会在这里吃瘪，，别的也吃

神***