精通算法的坛友请进：这CRC16算法不比查表慢是如何做到的？

smallwood · 发表于 2022-5-5 11:08:59

网上有牛人做的一个CRC16 CCITT算法，不比查表慢，主要的速度贡献是用数学方法省去了每byte的8次循环，已经测试过不比查表慢，能省去512 byte的表。

精妙所在应该是这两句替代了每byte的8次循环：
   x ^= x>>4;
   crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x;

我数学差，搞不懂原因，望博士级的坛友能指教一下！CRC8, CRC32 又如何？

来源：
------------------------------------------------
https://www.ccsinfo.com/forum/viewtopic.php?t=24977

代码:
------------------------------------------------
int16 Calc_CRC_C(int8 *Buffer, int16 Len)
{
int16 x;
int16 crc = 0xFFFF;

while(Len--)
{
   x = make8(crc,1) ^ *Buffer++;
   x ^= x>>4;

   crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x;
}
return crc;
}

void main()
{
int16 CRC1, CRC2;
int8 Buffer[500];
int16 i;

for (i=0; i < sizeof(Buffer); i++)
   Buffer = (int8)i;

i = sizeof(Buffer);
while (i--)
{
   CRC1 = Calc_CRC_C(Buffer, sizeof(Buffer));

   CRC2 = Calc_Crc16(Buffer, sizeof(Buffer));

   if (CRC1 != CRC2)
      while(1);    // Loop here forever on error

   // Modify data for a new test case
   buffer[200] = (int8) i;
}

// If we get here the test between the two CRC methods succeeded
while(1);
}

bwang1 · 发表于 2022-5-5 11:16:59

make8是完成什么功能呢?

smallwood · 发表于 2022-5-5 11:27:35

bwang1 发表于 2022-5-5 11:16
make8是完成什么功能呢?
(引用自2楼)

网上有说明：x = make8(old_crc,1) ^ data;  //x = ((old_crc>>8) ^ data) & 0xff;

我改一下代码：
int16 Calc_CRC_C(int8 *Buffer, int16 Len)
{
int16 x;
int16 crc = 0xFFFF;

while(Len--)
{
   x = ((crc>>8) ^ *Buffer++) & 0xff;
   x ^= x>>4;

   crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x;
   crc &= 0xffff;  //enable this line for processors with more than 16 bits
}
return crc;
}

void main()
{
int16 CRC1, CRC2;
int8 Buffer[500];
int16 i;

for (i=0; i < sizeof(Buffer); i++)
   Buffer = (int8)i;

i = sizeof(Buffer);
while (i--)
{
   CRC1 = Calc_CRC_C(Buffer, sizeof(Buffer));

   CRC2 = Calc_Crc16(Buffer, sizeof(Buffer));

   if (CRC1 != CRC2)
      while(1);    // Loop here forever on error

   // Modify data for a new test case
   buffer[200] = (int8) i;
}

// If we get here the test between the two CRC methods succeeded
while(1);
}

myiccdream · 发表于 2022-5-5 11:44:32

你觉得一个单片机定义 int8 Buffer[500]; 可以吗？

1a2b3c · 发表于 2022-5-5 12:41:07

myiccdream 发表于 2022-5-5 11:44
你觉得一个单片机定义 int8 Buffer[500]; 可以吗？
(引用自4楼)

我不是博士，但是看了这个回复非常赞同，应该是要根据实际环境来了，普通单片机动不动就开个128字节以上的临时变量，要么就编译不通，要么就运行出错，比如传统的51，能有500字节以上的ram还是比较难的，不晓得是不是必须的，而且就这一个功能就搞掉这么大ram，遇到中断或者其它还同时需要ram的地方咋办啊，
小芯片给不了这么多资源，大芯片（高级芯片）又不缺这点处理时间或者空间，所以还是根据实际情况最合适吧，

jyrpxj · 发表于 2022-5-5 12:52:29

查表快，不接受反驳。
楼主要给出具体对比测试的平台环境和具体的测试结果。
光速和万分之一光速，其实也差不多快，反正都是眨眼功夫就能从A城到B城，手动狗头。

pcwinner · 发表于 2022-5-5 13:22:47

写个程序测一下运行时间就知道啦

smallwood · 发表于 2022-5-5 13:26:37

myiccdream 发表于 2022-5-5 11:44
你觉得一个单片机定义 int8 Buffer[500]; 可以吗？
(引用自4楼)

作为一只合格的程序猿，你这问题问的也太含糊了吧？

你是想问为什么用一个没定义的data type：int8，还是宣告一个500byte的array有问题呢？
这些代码都是该网页拷贝出来的说明用的（pseudo code)， 500byte的array是验证该CRC16 算法的，不是算法本身。

smallwood · 发表于 2022-5-5 13:42:26

jyrpxj 发表于 2022-5-5 12:52
查表快，不接受反驳。
楼主要给出具体对比测试的平台环境和具体的测试结果。
光速和万分之一光速，其实也差 ...
(引用自6楼)

其实，这个帖子主要目的不是想说哪个速度快，而是希望解开该算法的奥秘：两句描述替代了一个8次循环

至于CRC16 implement的选择：
- MCU有硬件CRC的，一律用硬件CRC
- MCU没有硬件CRC：
  1.没有速度要求，没有flash size限制的，用CRC16查表
  2.没有速度要求，有flash size限制的，不要用查表，用任何CRC16算法
  3.有速度要求，有flash size限制的，用帖子的CRC16算法

工程师030 · 发表于 2022-5-5 14:04:06

还能有硬件的快吗？

chendaon · 发表于 2022-5-5 16:45:20

CRC一直拿现成的代码用，没有深究过，为楼主的研究精神点赞哦

yyts · 发表于 2022-5-5 16:50:43

smallwood 发表于 2022-5-5 13:42
其实，这个帖子主要目的不是想说哪个速度快，而是希望解开该算法的奥秘：两句描述替代了一个8次循环

(引用自9楼)

还有第4种情况：

4.有速度要求，没有flash size限制的，

用哪个？

smallwood · 发表于 2022-5-5 19:28:49

yyts 发表于 2022-5-5 16:50
还有第4种情况：

4.有速度要求，没有flash size限制的，

(引用自12楼)

查表或本帖 CRC16算法（可省512 byte flash表）皆可

1a2b3c · 发表于 2022-5-5 19:41:23

基本思想都是时间换空间，空间换时间吧，应该是没有鱼和熊掌兼得的，个人愚见，

wshtyr · 发表于 2022-5-6 00:04:52

本帖最后由 wshtyr 于 2022-5-6 00:05 编辑

提取最核心的四句代码：

x = ((crc>>8) ^ *Buffer++) & 0xff;
x ^= x>>4;
crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x;
crc &= 0xffff; //enable this line for processors with more than 16 bits

复制代码

算法进一步拆分：

y = ((crc>>8) ^ *Buffer++) & 0xff;
crc = crc << 8;
x = y ^ (y>>4);
crc = crc ^ (x << 12) ^ (x <<5) ^ x;
crc &= 0xffff; //enable this line for processors with more than 16 bits

复制代码

对于一般的CRC计算过程，在当前CRC值的基础上计算新增8位码字后的CRC值，需要将新增码字与CRC高8位异或后低位补8个0作为计算的起点。
上述算法中，新增码字(*Buffer++)与CRC高8位(crc >> 8)异或的结果赋给y，补0则通过左移实现(crc << 8)。

将y记作[y7 y6 y5 y4 y3 y2 y1 y0]，将crc记作[r7 r6 r5 r4 r3 r2 r1 r0 0 0 0 0 0 0 0 0]，进行如下图所示计算：

计算原则为：对于每一行，将生成多项式[1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1]乘以适当的系数，使最高位与被减数相同；余式作为下一步的被减数。
经过8次计算后，左侧全部归0，右侧按位依次相加所有竖排非0项即可得到余式。（这里说的加减是等效的，都是异或）
对余式进一步分析，可找到合适的中间变量(y ^ (y >> 4))，使最终结果可用 crc ^ (x << 12) ^ (x <<5) ^ x表示

当然，生成多项式不同，核心代码的计算过程也是不一样的，并且可以得到直观的结论：
1. 生成多项式的"1"数量越少，分散得越开，计算过程越容易简单描述
2. CRC位数越少，计算过程越简单

至于此法是否比查表快？
理论上，在Cortex-M3平台，如果是512字节的表，单次计算，查表法需要2次load和2次异或，此法需要1次load和5次异或（Cortex-M3的异或指令可带移位，故移位不计算在内）
那么哪种算法快，就取决于1次load和3次异或哪个快了，对于STM32，还真不一定哪个快

redroof · 发表于 2022-5-6 12:04:44

wshtyr 发表于 2022-5-6 00:04
提取最核心的四句代码：

(引用自15楼)

其实越高级的cpu，越应该用逻辑计算代替查表。因为越高级的cpu，内存比cpu本身慢的越多。

mPiDDR · 发表于 2022-5-6 12:39:22

redroof 发表于 2022-5-6 12:04
其实越高级的cpu，越应该用逻辑计算代替查表。因为越高级的cpu，内存比cpu本身慢的越多。 ...
(引用自16楼)

越高级的CPU，那是不是应该带cache? 把表连接到cache 是不是比你的内存还有快？

redroof · 发表于 2022-5-6 15:48:33

mPiDDR 发表于 2022-5-6 12:39
越高级的CPU，那是不是应该带cache? 把表连接到cache 是不是比你的内存还有快？
...
(引用自17楼)

cache比内存快，但是仍然比直接执行指令慢多了。而且首次使用的时候数据肯定不在cache
现代处理器基本上都是64字节的cache行，查表又是随机的，所以很容易就相当于要把整个512字节的表格全部读到cache里面～
给一个数据包做crc，又不会有多少数据量，基本上没法分摊首次把这个表格装入cache的开销。

modbus · 发表于 2022-5-6 17:28:33

wshtyr 发表于 2022-5-6 00:04
提取最核心的四句代码：

(引用自15楼)

M3内核1个load需要2个时钟（根据指令排列也可能只需1个时钟），而3个异或指令需要3个时钟

mPiDDR · 发表于 2022-5-6 17:41:18

redroof 发表于 2022-5-6 15:48
cache比内存快，但是仍然比直接执行指令慢多了。而且首次使用的时候数据肯定不在cache
现代处理器基本上 ...
(引用自18楼)

直接执行指令就不需要取指令，译码，执行指令了吗？
这个指令在哪里？不管是内存还是flash，或者是icache 调到CPU执行也是要时间的吧。
不管如何，除非是硬件的CRC，否则，在同等条件下，查表总是比直接算要省时间。
因查表，间接寻址，就完成了，
x ^= x>>4;
crc = (crc << 8) ^ (x << 12) ^ (x <<5) ^ x;
同样条件，以上语句需要多少个指令？

redroof · 发表于 2022-5-6 18:06:16

本帖最后由 redroof 于 2022-5-6 18:19 编辑

mPiDDR 发表于 2022-5-6 17:41
直接执行指令就不需要取指令，译码，执行指令了吗？
这个指令在哪里？不管是内存还是flash，或者是icache ...
(引用自20楼)

我只说高性能CPU，没说单片机。
这俩是完全不同的东西。
低性能单片机当然应该查表，查表肯定快于计算。

对高性能CPU来说，要执行任何指令，指令本身必须已经在指令Cache里面，对这两种做法都一样。而且指令是连续的，很好批量读取到cache。
区别是数据。
零零散散的数据对现代CPU并不友好，一次cache miss的代价就是CPU的上百个周期，够CPU执行几百条指令了。
对于计算不复杂的情况，查表远远不如直接算。

我刚才用AIDA64实测了一下我自己的电脑，数据如下：
主频4.2G，内存频率1.2G，时序参数 14-17-17-39，
测得内存延迟71.5ns，等于内存频率的86个周期，相当于CPU的300个周期
L1 Cache延迟1.2ns，L2是3.4ns，18.9ns
分别相当于CPU的 5个周期，14个周期，79个周期。

这下明白为什么对于电脑CPU来说，直接算会比查表要快了吧

对电脑CPU的优化很多时候是跟单片机完全反过来的，而且可能是反直觉的

wshtyr · 发表于 2022-5-6 18:45:20

redroof 发表于 2022-5-6 18:06
我只说高性能CPU，没说单片机。
这俩是完全不同的东西。
低性能单片机当然应该查表，查表肯定快于计算。
(引用自21楼)

确实

我试着在96MHz的Cortex-M4平台上试了下：

const uint16_t crc_ccitt_tab[256] =
{
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,
0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,
0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de,
0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,
0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,
0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,
0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,
0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823,
0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,
0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,
0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,
0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,
0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,
0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,
0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,
0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,
0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,
0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,
0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,
0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,
0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c,
0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,
0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,
0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,
0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,
0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92,
0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,
0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,
0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,
0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
};
__asm uint16_t crc16_calc_table(uint8_t * dat, int len)
{
push {r4-r7, lr}
ldr r3, =0xFFFF
ldr r2, =__cpp(crc_ccitt_tab)
crc16_calc_table_loop
ldrb r4, [r0], #1
eor r5, r4, r3, lsr #8
ldrh r5, [r2, r5, lsl #1]
eor r3, r5, r3, lsl #8
uxth r3, r3
subs r1, #1
bhi crc16_calc_table_loop
movs r0, r3
pop {r4-r7, pc}
}
__asm uint16_t crc16_calc_shift(uint8_t * dat, int len)
{
push {r4-r7, lr}
ldr r3, =0xFFFF
crc16_calc_shift_loop
ldrb r4, [r0], #1
eor r5, r4, r3, lsr #8
eor r5, r5, lsr #4
eor r3, r5, r3, lsl #8
eor r3, r3, r5, lsl #12
eor r3, r3, r5, lsl #5
uxth r3, r3
subs r1, #1
bhi crc16_calc_shift_loop
movs r0, r3
pop {r4-r7, pc}
}
static void app_misc_sen_poll(void)
{
int i;
uint32_t tick_t;
rt_kprintf("[CRC-TABLE] Start\n");
tick_t = rt_tick_get();
for(i = 0; i < 1000; i++)
{
crc16_calc_table((uint8_t *)0x08000000, 65536);
}
tick_t = rt_tick_get() - tick_t;
rt_kprintf("[CRC-TABLE] %d us\n", tick_t);
rt_kprintf("[CRC-SHIFT] Start\n");
tick_t = rt_tick_get();
for(i = 0; i < 1000; i++)
{
crc16_calc_shift((uint8_t *)0x08000000, 65536);
}
tick_t = rt_tick_get() - tick_t;
rt_kprintf("[CRC-SHIFT] %d us\n", tick_t);
}

复制代码

运行结果是：
[CRC-TABLE] Start
[CRC-TABLE] 9294 us
[CRC-SHIFT] Start
[CRC-SHIFT] 9026 us

也就是说，计算65536字节的CRC-CCITT，LZ位的算法比查表法少200多us。

modbus · 发表于 2022-5-6 19:00:57

wshtyr 发表于 2022-5-6 18:45
确实

我试着在96MHz的Cortex-M4平台上试了下：
(引用自22楼)

你这个把表格放在内存中试试

wshtyr · 发表于 2022-5-6 21:52:01

本帖最后由 wshtyr 于 2022-5-6 21:53 编辑

modbus 发表于 2022-5-6 19:00
你这个把表格放在内存中试试
(引用自23楼)

做了更详细的测试：

计算长度均为64K，测试方法是连续计算1000次，比较计算前后的系统节拍差

图中黄色背景的为有实用价值的组合。

结论是，这两种方法不相上下。
把CRC表放在RAM中可有效减少load时间，此时查表法快；
若以节约RAM为目的把CRC表放在ROM中，则移位法反而更快。这时的移位法确实做到了鱼和熊掌兼得。

jyrpxj · 发表于 2022-5-6 23:49:09

51单片机或者8位单片机，还是用查表快。只是多用了512 byte 的ROM。如果对于ROM紧张的，还是用移位法，时间换空间。

精通算法的坛友请进：这CRC16算法不比查表慢是如何做到的？

阿莫论坛20周年了！感谢大家的支持与爱护！！

本帖子中包含更多资源

本帖子中包含更多资源