将查表法crc的查找表优化掉的方法|（速度翻倍，含测试代码）
<h1>测试代码：<a href="forum.php?mod=attachment&aid=121833" title="attachment"><img src="/source/plugin/zhanmishu_markdown/template/editor/images/upload.svg" alt="upload" /> 附件：main.c</a></h1><p>下面是运行结果，速度比查表快，占用空间比查表小，测试环境是<strong>x86_64 mingw-w64 GCC 11.4，-O1 优化</strong></p>
<p><img src="data/attachment/forum/202511/20/033433lbsbcfqbrba0wbjs.png" alt="image.png" title="image.png" /></p>
<p>原理剖析：</p>
<p>假设我们要计算一个crc8，多项式为0x11。我们对它使用查表法一次计算4位，那他的函数可以写成</p>
<pre><code class="language-C">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;
//第二次查表
crc=crc_table[(crc>>4)^(data&0x0F)]^crc<<4;
}
}
</code></pre>
<p>我们可以看到，因为并行位数选取和多项式的特殊导致我们的表的数据十分有规律，表的元素和他的索引值有关，索引是0xF，对应元素就是0xFF，索引是0x4，对应元素就是0x44。我们完全可以用索引值经过位运算得到索引对应的值，比如这个函数的并行值是4，表的索引值就等于crc的前4位异或上新的4位数据，得到索引值index后对应值就是(index<<4|index)。</p>
<p>我们就可以将函数改写为</p>
<pre><code class="language-C">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;
}
</code></pre>
<p>由于输入数据的宽度是8位，但一次计算只能计算4位，所以我们将循环展开了一次，一次迭代两次运算，但是我们还可以通过位运算直接将两次合并在一起，下面是推导示例，一个小白框就是4位数据。</p>
<p><img src="data/attachment/forum/202511/20/004804u1juq1bs1b1ynzsn.png" alt="image.png" title="image.png" /></p>
<p>现在我们只需要按照结果写出代码就好了</p>
<pre><code class="language-C">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;
}
</code></pre>
<p>我们一直都在讨论多项式为0x44，并行4位的计算方法，我们是通过“表的元素和他的索引值有关”性质推导得到计算方法。</p>
<p>我们将他一般化。这个性质是由多项式决定，并行度也是多项式决定，如果将多项式以二进制的形式展开后，只要多项式中所有两个二进制1之间都存在0就有这个性质，比如多项式crc16-ccitt的多项式是0x1021，他就有这个性质。而多项式0x04C11DB7就不行。</p>
<p>其次是一次可以并行计算多少位，这取决于多项式中两个1之间的最小间隔的0的个数（首位忽略掉的1不算），比如0x44，最小间隔3个0，可以一次并行计算3+1位。又比如0x1021，最小间隔4个0，可以一次并行计算4+1位。</p>
<p>我们以常用的crc16-ccitt为例（下面的代码是xmodem的，但是网上一堆把xmodem当ccitt的，还有把ccitt-false当ccitt的，就这样吧），他的无表并行就可以这么写。</p>
<pre><code class="language-C">unsigned short crc16_ccitt(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;
}
</code></pre>
<p>由于这个方法受限于多项式的形式，我们需要观察多项式后才能知道能不能用无表并行方法，当然这只是受限于普通的单通道CRC计算。</p>
<p>在存储器领域存在多通道CRC计算，我们以SDIO的4bit传输模式为例：</p>
<p><img src="data/attachment/forum/202511/20/015014slt3g0ke2tgg3230.png" alt="image.png" title="image.png" /></p>
<p>我们可以看到SDIO在4bit传输模式下，每条通道都有一个crc16校验码，而且这个校验码的计算方式并不是，</p>
<p>第一组n/4个数据的CRC16在第三通道，</p>
<p>第二组n/4个数据的CRC16在第二通道，</p>
<p>第三组n/4个数据的CRC16在第一通道，</p>
<p>第四组n/4个数据的CRC16在第零通道，</p>
<p>（n是SD卡传输时1个数据块（称之为扇区好理解一点）含有的字节数，通常是512及其倍数，）</p>
<p>而是通道发送的数据的crc16，比如通道3的crc是由每个字节的b7，b3组成的数据计算来的，通道1的crc是由每个字节的b5，b1组成的数据计算来的。对于这种映射关系的多通道CRC校验码计算，我们可以将多通道CRC校验码计算转化为单通道CRC校验码计算。</p>
<p>下面是推导方法</p>
<p><img src="data/attachment/forum/202511/20/015701yq91qa8j1pbqacx1.png" alt="image.png" title="image.png" /></p>
<p>我们还可以将这种映射关系的多通道CRC校验码转化为单通道CRC校验码方法一般化</p>
<p><img src="data/attachment/forum/202511/20/015809dc3gcl5cv6ecoo9r.png" alt="image.png" title="image.png" /></p>
<p>我们花费如此多的篇幅有什么意义呢，因为多通道转单通道的多项式一定会补0，所以多通道转成的单通道的多项式一定可以无表并行计算。</p>
<p>下面是github上的开源项目pico-sdio-example用于计算SD卡在4bit传输模式CRC的函数，一次计算32位数据</p>
<p><img src="https://www.stcaimcu.com/data/attachment/forum/202509/23/022024gzegezop7fs9ppzp.jpg" alt="" /></p>
<p>sdio_crc16_4bit_checksum函数原理推导</p>
<p><a href="br/%E2%80%B8!%5B%5D(https://www.stcaimcu.com/data/attachment/forum/202511/17/224822dha9k1ycsscsds1i.jpg)%3Cbr/"><img src="https://www.stcaimcu.com/data/attachment/forum/202511/17/224822dha9k1ycsscsds1i.jpg" alt="" /><br />
</a></p>
<p>再左脚踩右脚一下，推导一次计算64位的方法</p>
<p><img src="https://www.stcaimcu.com/data/attachment/forum/202511/19/230708mccga4b4qveekzi4.jpg" alt="" /></p>
<p>效果不大，只是32位展开了一次循环而已。没有从并行16位推导到并行32位的速度是3.9倍的提升大，自己展开循环，水平不到位肯定是比不上编译器的，继续推导意义不大。<br/></p>
<p><img src="data/attachment/forum/202511/20/032852nljkg4p8u9xj8ub2.png" alt="image.png" title="image.png" /></p>
<p>当然SDIO因为xmodem多项式的特殊性并行度很高，1的数量才3个,只要获得索引只需要移位运算3次，像以太网的crc32就不行了，4通道才能并行4位，递推一下才8位，由于1的数量多，获得索引后还需要进行多次移位异或，软件上实现性能不太好。</p>
在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:}
<p><img alt="lol" class="emoji" src="https://www.stcaimcu.com/static/image/smiley/default/lol.gif" title="lol" /></p>
{:4_174:}
页:
[1]