[代码][C库]针对32Bit ARM优化的CRC库，静态配置支持大部分CRC。
本帖最后由 dr2001 于 2013-1-6 09:46 编辑简要说明：
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，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编译:0c: f810 4b01 ldrb.wr4, , #1
10: 4063 eors r3, r4
12: f003 040f and.w r4, r3, #15
16: f852 4024 ldr.w r4,
1a: 4288 cmp r0, r1
1c: ea84 1313 eor.w r3, r4, r3, lsr #4
20: f003 040f and.w r4, r3, #15
24: f852 4024 ldr.w r4,
28: ea84 1313 eor.w r3, r4, r3, lsr #4
2c: d1ee bne.n c <crc+0xc>这是MSB模式循环的汇编，CortexM3，GCC O2编译:0c: f810 4b01 ldrb.wr4, , #1
10: ea83 6304 eor.w r3, r3, r4, lsl #24
14: 0f1c lsrs r4, r3, #28
16: f852 4024 ldr.w r4,
1a: ea84 1303 eor.w r3, r4, r3, lsl #4
1e: 0f1c lsrs r4, r3, #28
20: f852 4024 ldr.w r4,
24: 4288 cmp r0, r1
26: ea84 1303 eor.w r3, r4, r3, lsl #4
2a: d1ef bne.n c <crc+0xc>MDK的结果基本一样，区别在循环终点的判定上，MDK的是用的计数器，GCC是判终止地址。
6 如果有兴趣进一步优化，可以进行循环展开。
如果一次Load 4字节，应该还能获得20%-25%的性能提升，如果数据长度在8字节以上的话（粗略估计）。能节约Load数据，循环比较和跳转的周期数。
另外，Cortex-M3的RevByte之类的指令也很有用，在MSB模式，循环展开的情况下。
7 预处理阶段，基于配置常数进行宏展开，生成复杂的常数表达式。值得注意的是，看来复杂的宏，展开量和展开后的计算量不一定是大的。这和C的算法有区别。
编译阶段常数表达式被编译器计算得到表格的常数。
变量类型和算法根据具体的处理器架构和指令集进行适当变形。
不是太烂的编译器就会输出想要的代码。
本帖最后由 dr2001 于 2013-1-10 22:15 编辑
最终版本；更新了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模式；内存布局是小端。 PUSH {r4-r6,lr}
LDR r2, = CRC_INITR
LDR r3, = crcLUT ; CRC_LUT_Table
; If(len <= 4) Jump to Final.
CMP r1,#0x04
BCC Final
; Load First Word.
AND r4,r0,#0x03
SUBS r0,r0,r4
LSLS r6,r4,#3
LDM r0!,{r5}
LSRS r5,r5,r6
REV r5,r5
EORS r2,r2,r5
ADDS r5,r1,r4
AND r1,r5,#0x03
SUBS r5,r5,r1
; Swtich/Case Jump.
CMP r4,#0x01
BEQ Case1
CMP r4,#0x02
BEQ Case2
CMP r4,#0x03
BNE Case0
B Case3
; Main Loop.
CRC_UnRoll: LDM r0!,{r4}
REV r4,r4
EORS r2,r2,r4
Case0: LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
Case1: LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
Case2: LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
Case3: LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
SUBS r5,r5,#4
BNE CRC_UnRoll
B Final
; Final Bytes.
CRC_Final:LDRB r4,,#0x01
EOR r2,r2,r4,LSL #24
LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
LSRS r4,r2,#28
LDR r4,
EOR r2,r4,r2,LSL #4
Final: SUBS r1,r1,#1
BCS CRC_Final
; Result XOR
LDR r0, = CRC_RSXOR
EORS r0,r0,r2, LSR (32 - (CRC_WIDTH))
POP {r4-r6,pc}不知道现在IAR的编译器结果如何，如果有人能贴一个就更好了。
GCC产生的汇编代码质量略差，数据预处理看起来不是太精简；核心循环里多了一条跳转，主要是对switch/case的结构实现有一个小瑕疵，导致多消耗一个周期。
文件如下：
简单看了下,写的很不错, 只两点
# define ,个人看不惯把#和define分开....很多编辑器的自动着色也会有问题
另外,看代码,LZ应该会用#error,不知道为啥弄个下面 这种方式让编译器静态检测错误
switch(0) { case 0: case 0: }
snoopyzz 发表于 2013-1-6 10:04 static/image/common/back.gif
简单看了下,写的很不错, 只两点
# define ,个人看不惯把#和define分开....很多编辑器的自动着色也会有问 ...
个人爱好#放在第一列，然后预处理命令放在对齐的地方。这样找预处理命令好找。
可能有的编辑器着色因为不支持正则表达会有问题……不过这种编辑器对复杂代码着色估计也不会太好。。。
#error是预处理期的错误，swtich是编译期的错误。两个不是一码事。
反正都符合标准，属于个人习惯而已了。
这个真心不错。 crc 一直没搞懂学习，谢谢！！！{:smile:} MARK.
.
这个要顶一下 本帖最后由 dr2001 于 2013-1-9 14:24 编辑
更新后的库，新加入了循环展开。
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上编译用于确认算法正确性。
这个可以有！ dr2001 发表于 2013-1-9 14:17
更新后的库，新加入了循环展开。
1、原有基于字节Load数据的半字节查表法代码不变。字节的处理顺序为地址 ...
请教大神 代码可以对8位字符数组进行crc16校验并返回16位的结果吗 define处应该怎么选择
这个可以有，收下了 顶一下 今天用到dr2001的CRC万能库，modbus里面需要如下配置
/*-- CRC Algorithm Information --*/
/*CRC Width. <Integer, > */
#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 后排膜拜VIP+++大神的神作! 楼主你好, 使用你的库有个疑问, 如果分段计算传入初值会有点麻烦,
另外switch里面嵌套一个while,确实第一次见,长见识了
switch(tmp) {
while(1) {
default:
case 0: dat = crcLUT;
crc = dat ^ (crc >>4);
dat = crcLUT;
crc = dat ^ (crc >>4);
case 1: dat = crcLUT;
crc = dat ^ (crc >>4);
dat = crcLUT;
crc = dat ^ (crc >>4);
case 2: dat = crcLUT;
crc = dat ^ (crc >>4);
dat = crcLUT;
crc = dat ^ (crc >>4);
case 3: dat = crcLUT;
crc = dat ^ (crc >>4);
dat = crcLUT;
crc = dat ^ (crc >>4);
cur ++;
if(len < 4) {
break;
}
len -=4;
dat = *cur;
# if(CRC_MEMORY_MODE == MSB)
CRC_INTRIN_REV(dat);
# endif
crc = crc ^ dat;
}
} icoyool 发表于 2021-8-12 09:58
楼主你好, 使用你的库有个疑问, 如果分段计算传入初值会有点麻烦,
另外switch里面嵌套一个while,确实第一 ...
switch在这里用的出神入化，怎么会有这样的奇思妙想呢？ zcllom 发表于 2021-8-12 10:07
switch在这里用的出神入化，怎么会有这样的奇思妙想呢？
类似的用法还有：实现一个字符串的拷贝
voidcopy( char *dst,char *src,intlen)
{
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++;
}
}
}
页:
[1]