将查表法crc的查找表优化掉的方法|（速度翻倍，含测试代码）

zr***

测试代码： 附件：main.c

下面是运行结果，速度比查表快，占用空间比查表小，测试环境是x86_64 mingw-w64 GCC 11.4，-O1 优化

原理剖析：

假设我们要计算一个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;
                //第二次查表
		crc=crc_table[(crc>>4)^(data[0]&0x0F)]^crc<<4;
	}
}

我们可以看到，因为并行位数选取和多项式的特殊导致我们的表的数据十分有规律，表的元素和他的索引值有关，索引是0xF，对应元素就是0xFF，索引是0x4，对应元素就是0x44。我们完全可以用索引值经过位运算得到索引对应的值，比如这个函数的并行值是4，表的索引值就等于crc的前4位异或上新的4位数据，得到索引值index后对应值就是(index<<4|index)。

我们就可以将函数改写为

unsigned char mycrc_new(unsigned char *data,unsigned int length)
{
	unsigned char crc=0;
	unsigned char temp;
	while(length--){
		temp=(crc>>4^(*data>>4));
		temp=temp<<4|temp;
		crc=(crc<<4)^temp;
		temp=(crc>>4^(*data&0x0F));
		temp=temp<<4|temp;
		crc=(crc<<4)^temp;
		data++;
	}
	return crc;
}

由于输入数据的宽度是8位，但一次计算只能计算4位，所以我们将循环展开了一次，一次迭代两次运算，但是我们还可以通过位运算直接将两次合并在一起，下面是推导示例，一个小白框就是4位数据。

现在我们只需要按照结果写出代码就好了

unsigned char mycrc_new1(unsigned char *data,unsigned int length)
{
	unsigned char crc=0;
	while(length--){
		crc^=crc>>4;
		crc^=(*data)>>4;
		crc^=(*data);
		crc^=crc<<4;
		data++;
	}
	return crc;
}

我们一直都在讨论多项式为0x44，并行4位的计算方法，我们是通过“表的元素和他的索引值有关”性质推导得到计算方法。

我们将他一般化。这个性质是由多项式决定，并行度也是多项式决定，如果将多项式以二进制的形式展开后，只要多项式中所有两个二进制1之间都存在0就有这个性质，比如多项式crc16-ccitt的多项式是0x1021，他就有这个性质。而多项式0x04C11DB7就不行。

其次是一次可以并行计算多少位，这取决于多项式中两个1之间的最小间隔的0的个数（首位忽略掉的1不算），比如0x44，最小间隔3个0，可以一次并行计算3+1位。又比如0x1021，最小间隔4个0，可以一次并行计算4+1位。

我们以常用的crc16-ccitt为例（下面的代码是xmodem的，但是网上一堆把xmodem当ccitt的，还有把ccitt-false当ccitt的，就这样吧），他的无表并行就可以这么写。

unsigned short crc16_ccitt(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;
}

由于这个方法受限于多项式的形式，我们需要观察多项式后才能知道能不能用无表并行方法，当然这只是受限于普通的单通道CRC计算。

在存储器领域存在多通道CRC计算，我们以SDIO的4bit传输模式为例：

我们可以看到SDIO在4bit传输模式下，每条通道都有一个crc16校验码，而且这个校验码的计算方式并不是，

第一组n/4个数据的CRC16在第三通道，

第二组n/4个数据的CRC16在第二通道，

第三组n/4个数据的CRC16在第一通道，

第四组n/4个数据的CRC16在第零通道，

（n是SD卡传输时1个数据块（称之为扇区好理解一点）含有的字节数，通常是512及其倍数，）

而是通道发送的数据的crc16，比如通道3的crc是由每个字节的b7，b3组成的数据计算来的，通道1的crc是由每个字节的b5，b1组成的数据计算来的。对于这种映射关系的多通道CRC校验码计算，我们可以将多通道CRC校验码计算转化为单通道CRC校验码计算。

下面是推导方法

我们还可以将这种映射关系的多通道CRC校验码转化为单通道CRC校验码方法一般化

我们花费如此多的篇幅有什么意义呢，因为多通道转单通道的多项式一定会补0，所以多通道转成的单通道的多项式一定可以无表并行计算。

下面是github上的开源项目pico-sdio-example用于计算SD卡在4bit传输模式CRC的函数，一次计算32位数据

sdio_crc16_4bit_checksum函数原理推导

再左脚踩右脚一下，推导一次计算64位的方法

效果不大，只是32位展开了一次循环而已。没有从并行16位推导到并行32位的速度是3.9倍的提升大，自己展开循环，水平不到位肯定是比不上编译器的，继续推导意义不大。

当然SDIO因为xmodem多项式的特殊性并行度很高，1的数量才3个,只要获得索引只需要移位运算3次，像以太网的crc32就不行了，4通道才能并行4位，递推一下才8位，由于1的数量多，获得索引后还需要进行多次移位异或，软件上实现性能不太好。

国芯人***

在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校验的 ...

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

神***

zr***

zr***