[代码][C库]针对32Bit ARM优化的CRC库，静态配置支持大部分CRC。

dr2001

简要说明：
1 参考文献："A Painless Guide To CRC Error Detection Algorithms"。Google即可。

2 算法信息：
2-1 支持大部分CRC：CRC3到CRC32，输入和输出同序。即宽于CRC32的不支持；同序指输入和输出要么都反射，要么都不反射。否则结果需要自行反射处理一下。
2-2 CRC半字节查表法。表大小固定为64Bytes，无论是计算哪种CRC。（CRC3 .. CRC32）
2-3 算法C代码针对ARM 32Bit架构（ARM/Thumb2）优化。在ARM926EJ-S和Cortex-M3上进行过反汇编验证。可以用于别的体系结构，但效率会低。
2-4 计算结果和第三方软件计算结果以及CRC算法标准CheckNumber校对过。主要测试过CRC[3/4/5/7/8/11/12/15/16/24/31/32]，MSB/LSB都有。

3 使用说明：
  库仅包含一个C文件，每个C文件通过宏进行静态配置；每个C文件支持一种CRC。
3-1 复制C文件为特定的文件名。
3-2 修改CRC_FUNC_NAME, CRC_WIDTH, CRC_DIRCT, CRC_POLY, CRC_INIT, CRC_XORV这几个宏定义。
    其中FUNC Name是函数名，其它的是CRC配置信息。
3-3 如果使用的不是C99编译器，需要自行声明对应长度的变量类型。
3-4 编译该C文件，自行在h文件中声明对应的函数名，即可。

4 配置说明：
  对于常见的CRC完整参数：宽度，多项式，初值，结果异或这四个值照填。
  如果Input和Output都需要Reflect，那么选择CRC_DIRCT的LSB模式；
  如果两个都不需要Reflect，那么选择MSB模式即可。
  只有一个需要Reflect的话，那么结果会错误。（主要是数据序不对，需要再处理一下，不过这种CRC极少。）

5 优化结果：
5-1 Keil MDK和GCC无警告编译通过；GCC C90严格模式编译无警告。
5-2 O2等级优化，ARM926EJ-S Core，ARM指令集，每个字节处理需要10条指令，无论CRC模式。
    O2等级优化，Cortex-M3 Core，Thumb2指令集，每个字节处理需要10条指令，无论CRC模式。每个字节处理约需要15个周期。

这是LSB模式循环的汇编，CortexM3，GCC O2编译:

1. 0c:   f810 4b01       ldrb.w  r4, [r0], #1
   
2. 10:   4063            eors    r3, r4
   
3. 12:   f003 040f       and.w   r4, r3, #15
   
4. 16:   f852 4024       ldr.w   r4, [r2, r4, lsl #2]
   
5. 1a:   4288            cmp     r0, r1
   
6. 1c:   ea84 1313       eor.w   r3, r4, r3, lsr #4
   
7. 20:   f003 040f       and.w   r4, r3, #15
   
8. 24:   f852 4024       ldr.w   r4, [r2, r4, lsl #2]
   
9. 28:   ea84 1313       eor.w   r3, r4, r3, lsr #4
   
10. 2c:   d1ee            bne.n   c <crc+0xc>

复制代码

这是MSB模式循环的汇编，CortexM3，GCC O2编译:

1. 0c:   f810 4b01       ldrb.w  r4, [r0], #1
   
2. 10:   ea83 6304       eor.w   r3, r3, r4, lsl #24
   
3. 14:   0f1c            lsrs    r4, r3, #28
   
4. 16:   f852 4024       ldr.w   r4, [r2, r4, lsl #2]
   
5. 1a:   ea84 1303       eor.w   r3, r4, r3, lsl #4
   
6. 1e:   0f1c            lsrs    r4, r3, #28
   
7. 20:   f852 4024       ldr.w   r4, [r2, r4, lsl #2]
   
8. 24:   4288            cmp     r0, r1
   
9. 26:   ea84 1303       eor.w   r3, r4, r3, lsl #4
   
10. 2a:   d1ef            bne.n   c <crc+0xc>

复制代码

MDK的结果基本一样，区别在循环终点的判定上，MDK的是用的计数器，GCC是判终止地址。

6 如果有兴趣进一步优化，可以进行循环展开。
  如果一次Load 4字节，应该还能获得20%-25%的性能提升，如果数据长度在8字节以上的话（粗略估计）。能节约Load数据，循环比较和跳转的周期数。
  另外，Cortex-M3的RevByte之类的指令也很有用，在MSB模式，循环展开的情况下。

7 预处理阶段，基于配置常数进行宏展开，生成复杂的常数表达式。值得注意的是，看来复杂的宏，展开量和展开后的计算量不一定是大的。这和C的算法有区别。
  编译阶段常数表达式被编译器计算得到表格的常数。
  变量类型和算法根据具体的处理器架构和指令集进行适当变形。
  不是太烂的编译器就会输出想要的代码。

dr2001

最终版本；更新了C代码，以获得最佳优化结果。
该文件展示了这样的内容：配合针对目标体系结构的，优质的编译器，纯C语言生成的代码几乎等价于手工汇编的结果。

在Keil MDK上，O2优化，Cortex-M3，编译得到的结果中，除了Switch/Case没有进行查找表优化外，其他的汇编代码就是我想要的汇编代码。

使用Keil MDK软件仿真功能计算指令执行周期数进行性能分析。（和CortexM3手册对过，结果应该没问题。）
Cortex-M3：
1、不进行循环展开的代码，进行N字节的CRC，需要约：22 + 15 * N周期。
2、进行循环展开，CRC的移位方向和内存的大小端模式都是低位在前或者高位在前，计算CRC的循环开销为：9.75周期/字节。
3、如果CRC和内存大小端是反的，那么CRC循环的开销是：10周期/字节。
A、循环展开受到起始地址是否32Bit对齐；剩余0-3个逐字节访问等影响，额外的开销不定。
B、计算8字节以上CRC，使用循环展开模式就能快了。
C、代码大小：循环展开后256字节左右（含查找表）。

ARM926EJ-S：
循环展开后的核心循环周期数为：12-13周期/字节。和上边的2/3点一致。


以下是CortexM3 MDK编译结果，加了简要注释，CRC是MSB模式；内存布局是小端。

1.             PUSH     {r4-r6,lr}
   
2.             LDR      r2, = CRC_INITR
   
3.             LDR      r3, = crcLUT ; CRC_LUT_Table
   
4. ;   If(len <= 4) Jump to Final.
   
5.             CMP      r1,#0x04
   
6.             BCC      Final
   
7. 
   
8. ;   Load First Word.
   
9.             AND      r4,r0,#0x03
   
10.             SUBS     r0,r0,r4
    
11.             LSLS     r6,r4,#3
    
12.             LDM      r0!,{r5}
    
13.             LSRS     r5,r5,r6
    
14.             REV      r5,r5
    
15.             EORS     r2,r2,r5
    
16.             ADDS     r5,r1,r4
    
17.             AND      r1,r5,#0x03
    
18.             SUBS     r5,r5,r1
    
19. 
    
20. ;   Swtich/Case Jump.
    
21.             CMP      r4,#0x01
    
22.             BEQ      Case1
    
23.             CMP      r4,#0x02
    
24.             BEQ      Case2
    
25.             CMP      r4,#0x03
    
26.             BNE      Case0
    
27.             B        Case3
    
28. 
    
29. ;   Main Loop.
    
30. CRC_UnRoll: LDM      r0!,{r4}
    
31.             REV      r4,r4
    
32.             EORS     r2,r2,r4
    
33. Case0:      LSRS     r4,r2,#28
    
34.             LDR      r4,[r3,r4,LSL #2]
    
35.             EOR      r2,r4,r2,LSL #4
    
36.             LSRS     r4,r2,#28
    
37.             LDR      r4,[r3,r4,LSL #2]
    
38.             EOR      r2,r4,r2,LSL #4
    
39. Case1:      LSRS     r4,r2,#28
    
40.             LDR      r4,[r3,r4,LSL #2]
    
41.             EOR      r2,r4,r2,LSL #4
    
42.             LSRS     r4,r2,#28
    
43.             LDR      r4,[r3,r4,LSL #2]
    
44.             EOR      r2,r4,r2,LSL #4
    
45. Case2:      LSRS     r4,r2,#28
    
46.             LDR      r4,[r3,r4,LSL #2]
    
47.             EOR      r2,r4,r2,LSL #4
    
48.             LSRS     r4,r2,#28
    
49.             LDR      r4,[r3,r4,LSL #2]
    
50.             EOR      r2,r4,r2,LSL #4
    
51. Case3:      LSRS     r4,r2,#28
    
52.             LDR      r4,[r3,r4,LSL #2]
    
53.             EOR      r2,r4,r2,LSL #4
    
54.             LSRS     r4,r2,#28
    
55.             LDR      r4,[r3,r4,LSL #2]
    
56.             EOR      r2,r4,r2,LSL #4
    
57.             SUBS     r5,r5,#4
    
58.             BNE      CRC_UnRoll
    
59.             B        Final
    
60. 
    
61. ;   Final Bytes.
    
62. CRC_Final:  LDRB     r4,[r0],#0x01
    
63.             EOR      r2,r2,r4,LSL #24
    
64.             LSRS     r4,r2,#28
    
65.             LDR      r4,[r3,r4,LSL #2]
    
66.             EOR      r2,r4,r2,LSL #4
    
67.             LSRS     r4,r2,#28
    
68.             LDR      r4,[r3,r4,LSL #2]
    
69.             EOR      r2,r4,r2,LSL #4
    
70. Final:      SUBS     r1,r1,#1
    
71.             BCS      CRC_Final
    
72. 
    
73. ;   Result XOR
    
74.             LDR      r0, = CRC_RSXOR
    
75.             EORS     r0,r0,r2, LSR (32 - (CRC_WIDTH))
    
76.             POP      {r4-r6,pc}

复制代码

不知道现在IAR的编译器结果如何，如果有人能贴一个就更好了。

GCC产生的汇编代码质量略差，数据预处理看起来不是太精简；核心循环里多了一条跳转，主要是对switch/case的结构实现有一个小瑕疵，导致多消耗一个周期。

文件如下：

snoopyzz

简单看了下,写的很不错, 只两点
#   define ,个人看不惯把#和define分开....很多编辑器的自动着色也会有问题

另外,看代码,LZ应该会用#error,  不知道为啥弄个下面 这种方式让编译器静态检测错误
switch(0) { case 0: case 0: }

dr2001

snoopyzz 发表于 2013-1-6 10:04
简单看了下,写的很不错, 只两点
#   define ,个人看不惯把#和define分开....很多编辑器的自动着色也会有问 ...

个人爱好#放在第一列，然后预处理命令放在对齐的地方。这样找预处理命令好找。
可能有的编辑器着色因为不支持正则表达会有问题……不过这种编辑器对复杂代码着色估计也不会太好。。。

#error是预处理期的错误，swtich是编译期的错误。两个不是一码事。

反正都符合标准，属于个人习惯而已了。

farmerzhangdl

这个真心不错。

dory_m

crc 一直没搞懂学习，谢谢！！！

Excellence

MARK.
.

Gorgon_Meducer

这个要顶一下

dr2001

更新后的库，新加入了循环展开。

1、原有基于字节Load数据的半字节查表法代码不变。字节的处理顺序为地址增序不变。
2、增加了循环展开的代码，展开次数为4；Load数据基于32Bit进行。
2-1、展开后的代码类似于Cache Line Size = 4Bytes的Cache的行为。即起始地址为3的话，也会读0，1，2的数据；但是尾巴的非对齐部分是逐字节处理的。在内存边界不会有问题。
2-2、由于Load 32Bit数据存在大小端问题，程序进行了相应处理。反序使用了编译器原语或编译器内置函数。
3、尽管代码针对ARM 32Bit架构编写，但是可以运行于其它平台上，就是效率可能会低。无论循环展开与否，代码都可以在ARM/X86/X64上运行，别的平台没测试。
4、由于C无法控制编译器底层行为，循环展开代码只是描述理想情况下的行为；具体优化效果依赖于编译器的行为。MDK可以获得很好的优化效果；GCC-ARM则较差，有冗余代码。
4-1、如果想要最高效的代码，还是用汇编，基本上对着把C翻译成汇编就行了。

大致性能：
1、非展开代码，无论CRC的MSB，LSB模式，MDK开优化的编译结果约为15周期/字节。
2、循环展开，CRC MSB模式在内存小端模式下，MDK输出代码的平均性能为10.8周期/字节。（主要是多了rev指令）
3、循环展开，CRC LSB模式在内存小端模式下，MDK输出代码的平均性能为10.5周期/字节。
-、即CRC模式和内存模式同为MSB/LSB的话，大约是10.5；不同的话，就是10.8，就差一个REV指令的开销。
-、考虑初始地址的全部情况，循环展开后的代码从10字节左右的数据开始速度就会比不展开的代码快；如果编译器不是太差意思，用展开的就行了。

代码体积展开后大约增加一倍多，Thumb2下从112字节总消耗增加为约256字节。（含64B查找表的大小）

代码可以在PC上编译用于确认算法正确性。

haigerl

这个可以有！

sept

dr2001 发表于 2013-1-9 14:17
更新后的库，新加入了循环展开。

1、原有基于字节Load数据的半字节查表法代码不变。字节的处理顺序为地址 ...

请教大神 代码可以对8位字符数组进行crc16校验并返回16位的结果吗 define处应该怎么选择

yanyi103

这个可以有，收下了

huangxiaowei

   顶一下

RAMILE

今天用到dr2001的CRC万能库，modbus里面需要如下配置
/*--         CRC Algorithm Information        --*/
/*  CRC Width.          <Integer, [1..32]>      */
#define CRC_WIDTH               16

/*  CRC Shift Direction. <LSB | MSB>            */
#define CRC_DIRCT               LSB

/*  CRC polynomial.     <Integer, end with ul>  */
#define CRC_POLY                 0x8005ul  // 0xa001

/*  CRC Reg Init Value. <Integer, end with ul>  */
#define CRC_INIT                0xFFFFul

/*  CRC XOR Ret Value.  <Integer, end with ul>  */
#define CRC_XORV                0x0000ul

/*--    UnRoll CRC Calculation Loop Options   --*/
/*  If Unroll Loop is Enabled. (Suggested ON.)  *\
\*                      <optEnable | optDisable>*/
#define CRC_UNROLL_LOOP         optEnable

/*  Memory Mode, used by UnRoll.                *\
\*  <LSB | MSB> First / At Lower Address.       */
#define CRC_MEMORY_MODE         LSB

icoyool

后排膜拜VIP+++大神的神作!

icoyool

楼主你好, 使用你的库有个疑问, 如果分段计算传入初值会有点麻烦,
另外switch里面嵌套一个while,确实第一次见,长见识了

1. 
   
2.         switch(tmp) {
   
3.             while(1) {
   
4.                 default:
   
5.                 case 0: dat =   crcLUT[crc & 0xF];
   
6.                 crc =   dat ^ (crc >>  4);
   
7.                 dat =   crcLUT[crc & 0xF];
   
8.                 crc =   dat ^ (crc >>  4);
   
9.                 case 1: dat =   crcLUT[crc & 0xF];
   
10.                 crc =   dat ^ (crc >>  4);
    
11.                 dat =   crcLUT[crc & 0xF];
    
12.                 crc =   dat ^ (crc >>  4);
    
13.                 case 2: dat =   crcLUT[crc & 0xF];
    
14.                 crc =   dat ^ (crc >>  4);
    
15.                 dat =   crcLUT[crc & 0xF];
    
16.                 crc =   dat ^ (crc >>  4);
    
17.                 case 3: dat =   crcLUT[crc & 0xF];
    
18.                 crc =   dat ^ (crc >>  4);
    
19.                 dat =   crcLUT[crc & 0xF];
    
20.                 crc =   dat ^ (crc >>  4);
    
21.                
    
22.                 cur ++;
    
23.                
    
24.                 if(len < 4) {
    
25.                     break;
    
26.                 }
    
27.                
    
28.                 len -=  4;
    
29.                 dat =   *cur;
    
30. #               if  (CRC_MEMORY_MODE == MSB)
    
31.                 CRC_INTRIN_REV(dat);
    
32. #               endif
    
33.                 crc =   crc ^ dat;
    
34.             }
    
35.         }

复制代码

zcllom

icoyool 发表于 2021-8-12 09:58
楼主你好, 使用你的库有个疑问, 如果分段计算传入初值会有点麻烦,
另外switch里面嵌套一个while,确实第一 ...

switch在这里用的出神入化，怎么会有这样的奇思妙想呢？

zcllom

zcllom 发表于 2021-8-12 10:07
switch在这里用的出神入化，怎么会有这样的奇思妙想呢？

类似的用法还有：实现一个字符串的拷贝

void  copy( char *  dst,  char *  src,  int  len)
{
    switch(len & 7)
    {
        default:
        while (len > 7)
        {
            len -= 8;
            *dst++ = *src++;
   
            case 7:  *dst++ = *src++;
   
            case 6:  *dst++ = *src++;
   
            case 5:  *dst++ = *src++;
   
            case 4:  *dst++ = *src++;
   
            case 3:  *dst++ = *src++;
   
            case 2:  *dst++ = *src++;
   
            case 1:  *dst++ = *src++;
        
        }
   
    }

}