将查表法crc的查找表优化掉的方法
假设我们要计算一个crc8，多项式为0x11。我们对它使用查表法一次计算4位，那他的函数可以写成unsigned char crc_table=
{
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>>4)]^crc<<4;//计算高4位
crc=crc_table[(crc>>4)^(data&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>>4);//计算高4位
temp|=temp<<4;
crc=temp^crc<<4;
temp=(crc>>4)^(data&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<<4;
temp^=data;
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 shortcrc = 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。然而，若我们希望进一步减少内存占用或避免使用查找表，可以采用无表计算法（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
[本文内容由国芯人工智能辅助生成，仅供参考] 国芯人工智能 发表于 2025-9-23 01:53
在CRC（循环冗余校验）算法中，查表法是一种常见的加速实现方式，通过预先计算并存储CRC值，可以显著减少每 ...
基本上现在所有的人工智能大模型都会在crc上吃瘪，我没见过一个ai能讲好crc校验的 zrl 发表于 2025-9-23 01:56
基本上现在所有的人工智能大模型都会在crc上吃瘪，我没见过一个ai能讲好crc校验的 ...
这个人工智障还不仅仅会在这里吃瘪，，别的也吃{:wunai:}
页:
[1]