CRC位域多表查表方法-电子工程世界

分享到: 微博; QQ; 微信; LinkedIn

CRC算法的实现一般可分运算和查表两种，前者靠对某CRC多项式的移位和异或得到，

占用程序空间小但速度慢。后者是将前者的运算结果值排列为一个CRC矩阵表格，占用程

序空间大但速度快。

CRC查表方法经典的有两种，由于表格空间的不同，对于CRC8采用全表查询，CRC16以上

采用小表(一般为256个元素的数组)查询。

CRC查表由于CRCN(N=4,8,12,16,20,24,32,48,64,128,...)的不同占用的表格空间差异

很大。每种CRC的多项式对应一张CRC表，例CRC4左右移位各有16个CRC4表。CRC8左右移位

各有256个CRC8表。1个CRC8表占用256个字节，可组成16*16的数组，而1个CRC16表将占用

65536个字节，组成256*256的数组。

CRC位域多表查表方法与传统的CRC查表方法最大的不同在于多表级联压缩表格空间。

此方法依据CRC的“性质”: CRC[X]=CRC[行,列]=CRC[行,0]^CRC[0,列]。

以CRC8=X8+X5+X4+1为例，它的多项式的数字表达即权值=0x8C,右移CRC8算法。

已知CRC8[0x9A]=0x6F,我们可以将0x9A用位域划分为高4位(16行)和低4位(16列)，即

CRC8[0x9A]=CRC8[0x90 ^ 0x0A]=CRC8[0x09, 0x0A]

根据：CRC[X]=CRC[行,列]=CRC[行,0]^CRC[0,列]

CRC8[0x90 ^ 0x0A]=CRC8[0x90] ^ CRC8[0x0A]=0x11 ^ 0x7E = 0x6F

或CRC8[0x90, 0x0A]=CRC8[0x90, 0] ^ CRC8[0, 0x0A]=0x11 ^ 0x7E = 0x6F

由此可见，CRC8的表格没必要组成16*16的数组，可以用2*16的行列数组替代。

CRC8_Col[16]={0x00,0x5E,0xBC,0xE2,0x61,0x3F,0xDD,0x83,0xC2,0x9C,0x7E,0x20,0xA3,0xFD,0x1F,0x41};

CRC8_Row[16]={0x00,0x9D,0x23,0xBE,0x46,0xDB,0x65,0xF8,0x8C,0x11,0xAF,0x32,0xCA,0x57,0xE9,0x74};

查表CRC8[0x9A]=CRC8_Row[0x09] ^ CRC_Col[0x0A]= 0x11 ^ 0x7E = 0x6F

此方法为CRC位域两表查询方法(占用32个字节)，位域表达为:

unsigned char Col:4;//D0~D3

unsigned char Row:4;//D4~D7

CRC位域三表查询方法(占用20个字节)，位域表达为:

unsigned char Col:3;//D0~D2

unsigned char Row:3;//D3~D5

unsigned char Block:2;//D6~D7

CRC8_Col[8]={0x00,0x5E,0xBC,0xE2,0x61,0x3F,0xDD,0x83};

CRC8_Row[8]={0x00,0xC2,0x9D,0x5F,0x23,0xE1,0xBE,0x7C}；

CRC8_Block[4]={0x00,0x46,0x8C,0xCA};

CRC8[0x9A]=CRC8_Block[0x02] ^ CRC8_Row[0x03] ^ CRC8_Col[0x02] = 0x8C ^ 0x5F ^ 0xBC = 0x6F

或CRC8[0x9A]=CRC8[0x80 ^ 0x18 ^ 0x02]=CRC8[0x80]^CRC8[0x18]^ CRC8[0x02]=0x8C^0x5F^0xBC=0x6F

CRC位域四表查询方法(占用16个字节)，位域表达为:

unsigned char Col:2;//D0~D1

unsigned char Row:2;//D2~D3

unsigned char Block:2;//D4~D5

unsigned char Segment:2;//D6~D7

CRC8_Col[4]={0x00,0x5E,0xBC,0xE2};

CRC8_Row[4]={0x00,0x61,0xC2,0xA3}；

CRC8_Block[4]={0x00,0x9D,0x23,0xBE};

CRC8_Segment[4]={0x00,0x46,0x8C,0xCA};

CRC8[0x9A]=CRC8_Segment[2]^CRC8_Block[1]^CRC8_Row[2]^CRC8_Col[2]=0x8C^0x9D^0xC2^0xBC=0x6F

此方法为多表查询，即多表结果的多次异或，当大CRC多表查询时，可能由十多个表组成，为编程方便

一般将表压缩成等长位域的单表或多维数组，以简化程序。故CRC位域四表可组成矩阵：

unsigned char CRCR8_8C_Array[16]=

{

0x00,0x5E,0xBC,0xE2,0x00,0x61,0xC2,0xA3,0x00,0x9D,0x23,0xBE,0x00,0x46,0x8C,0xCA

};

查表程序为:

unsigned char GetCRCR8_8C(unsigned char crcinit, unsigned char crcval)//CRC8右移权值0x8C(X8+X5+X4+1)

{//(可以不要初值crcinit，多字节CRC8时入口需要对crcval做处理)

unsigned char i, crc=0;

crcval = crcinit ^ crcval;//初值^明文,将CRC编码矩阵转化为CRC编码表

for(i = 0;i < 4;i ++)//4表级联查表4次

{

crc ^= CRCR8_8C_Array[(i << 2) | (crcval & 0x03)];//位域宽2每表4个字节

crcval >>= 2;//准备下一个位域,域宽2,每表4字节

}

return crc;

}

相应的移位算法程序为:

unsigned char GetCRCR8_8C(unsigned char crcinit, unsigned char crcval)//CRC8右移权值0x8C(X8+X5+X4+1)

{//(可以不要初值crcinit，多字节CRC8时入口需要对crcval做处理)

unsigned char i, crc;

crc = crcinit ^ crcval;//初值^明文,将CRC编码矩阵转化为CRC编码表

for(i = 0;i < 8;i ++)//每字节8位

{

if (crc & 0x01)//右移记忆最低位

{

crc >>= 1;

crc ^= 0x8C;//权值

}

else

{

crc >>= 1;

}

return crc;

}

下面以CRC16的位域多表查表方法来说明大CRC位域多表查表方法。为统一方法采用等位域4即每表16个元素举例.

左移CRC16=X16+X12+X5+1，多项式即权值=0x1021

CRC16[0x1234]=0x13C6,可分解为

CRC16[0x1234]=CRC16[0x1000 ^ 0x0200 ^ 0x0030 ^ 0x0004]

=CRC16[0x1000] ^ CRC16[0x0200] ^ CRC16[0x0030] ^ CRC16[0x0004]

=0x0373 ^ 0x6662 ^ 0x3653 ^ 0x4084 = 0x13C6

我们可以构成CRC16表：

CRC16_Array[4, 16]={

{CRC16[0x0000], CRC16[0x0001], CRC16[0x0002],...CRC16[0x000D], CRC16[0x000E], CRC16[0x000F]},

{CRC16[0x0000], CRC16[0x0010], CRC16[0x0020],...CRC16[0x00D0], CRC16[0x00E0], CRC16[0x00F0]},

{CRC16[0x0000], CRC16[0x0100], CRC16[0x0200],...CRC16[0x0D00], CRC16[0x0E00], CRC16[0x0F00]},

{CRC16[0x0000], CRC16[0x1000], CRC16[0x2000],...CRC16[0xD000], CRC16[0xE000], CRC16[0xF000]}

};

即

unsigned int CRCL16_1021_Array[4, 16]={

{//位域D0~D3

0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,

0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF

{//位域D4~D7

0x0000, 0x1231, 0x2462, 0x3653, 0x48C4, 0x5AF5, 0x6CA6, 0x7E97,

0x9188, 0x83B9, 0xB5EA, 0xA7DB, 0xD94C, 0xCB7D, 0xFD2E, 0xEF1F

{//位域D8~D11

0x0000, 0x3331, 0x6662, 0x5553, 0xCCC4, 0xFFF5, 0xAAA6, 0x9997,

0x89A9, 0xBA98, 0xEFCB, 0xDCFA, 0x456D, 0x765C, 0x230F, 0x103E

{//位域D11~D15

0x0000, 0x0373, 0x06E6, 0x0595, 0x0DCC, 0x0EBF, 0x0B2A, 0x0859,

0x1B98, 0x18EB, 0x1D7E, 0x1E0D, 0x1654, 0x1527, 0x10B2, 0x13C1

}

};

查表程序为(需要4*16*2=128个字节表, 传统查表为256*2=512个字节, 位域法压缩4倍):

unsigned int GetCRCL16_1021(unsigned int crcinit, unsigned int crcval)//CRC16=X16+X12+X5+1

{//(可以不要初值crcinit，多字节CRC16时入口需要对crcval做处理)

unsigned int i, crc=0;

crcval = crcinit ^ crcval;//初值^明文,将CRC编码矩阵转化为CRC编码表

for(i = 0;i < 4;i ++)//4表级联查表4次(传统查表方法只需2次即2字节)

{

crc ^= CRCL16_1021_Array[i, crcval & 0x0F];//位域宽4每表16个字节

crcval >>= 4;//准备下一个位域,域宽4,每表16字节

}

return crc;

}

[page]

相应的移位算法程序为:

unsigned int GetCRCL16_1021(unsigned int crcinit, unsigned int crcval)//CRC16=X16+X12+X5+1

{//(可以不要初值crcinit，多字节CRC16时入口需要对crcval做处理)

unsigned int i, crc;

crc = crcinit ^ crcval;//初值^明文,将CRC编码矩阵转化为CRC编码表

for(i = 0;i < 16;i ++)//双字节16位

{

if (crc & 0x8000)//左移记忆最高位

{

crc <<= 1;

crc ^= 0x1021;//权值

}

else

{

crc <<= 1;

}

return crc;

}

对比传统的CRC16_1021(左移、大端数据存储方式)查表方法：

CRC16_1021_Array[256]={//位域宽8每表256个字节

CRC16[0x0000], CRC16[0x0001], CRC16[0x0002],...CRC16[0x00FD], CRC16[0x00FE], CRC16[0x00FF]

};

即：

CRC16_1021_Array[256]={//位域宽8每表256个字节

0x0000, 0x1021, 0x2042, 0x3063, 0x4084,...0x2e93, 0x3eb2, 0x0ed1, 0x1ef0

};

查表核心程序为:

unsigned int GetCRC16(unsigned int crcinit, unsigned int crcval)

{//(可以不要初值crcinit，多字节CRC16时入口需要对crcval做处理)

unsigned int i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i < 2;i ++)

{

crc = (crc << 8) ^ CRC16_1021_Array[((crc >> 8) ^ (crcval >> 8)) & 0xFF];//位域宽8每表256个字节

crcval <<= 8;//准备下一个位域,域宽8,每表256字节

}

return crc;

}

此法实际为(大端数据存储方式):

CRC16[0x1234] = (CRC16[0x0012] << 8) ^ CRC16[((CRC16[0x0012] >> 8) ^ 0x0034) & 0xFF]

= (0x3273 << 8) ^ CRC16[(0x0032 ^ 0x0034) & 0xFF]

= 0x7300 ^ CRC16[0x0006]

= 0x7300 ^ 0x60C6

= 0x13C6

同理左移CRC32=X32+X26+..+1 权值0x04C11DB7

unsigned long CRCL32_04C11DB7_Array[8, 16]={//数组元素未列完，有空搞个自动生成序列

{//位域D0~D3

0x00000000, 0x04C11DB7, 0x09823B6E,... 0x3C8EA00A, 0x384FBDBD

{//位域D4~D7

0x00000000, 0x4C11DB70, 0x9823B6E0,... 0xC5A92679, 0x89B8FD09

{//位域D8~D11

0x00000000, 0xD219C1DC, 0xA0F29E0F,... 0x6F9EFCF4, 0xBD873D28

{//位域D11~D15

0x00000000, 0x10519B13, 0x20A33626,... 0xE36982F2, 0xF33819E1

{//位域D16~D19

0x00000000, 0x01D8AC87, 0x03B1590E,... 0x0A168F2A, 0x0BCE23AD

{//位域D20~D23

0x00000000, 0x1D8AC870, 0x3B1590E0,... 0xA168F2A0, 0xBCE23AD0

{//位域D24~D27

0x00000000, 0xDC6D9AB7, 0xBC1A28D9,... 0x3905FCD6, 0xE5686661

{//位域D28~D31

0x00000000, 0xF7142DA3, 0xEAE946F1,... 0x9D1CEBB9, 0x6A08C61A

}

};

查表程序为(需要8*16*4=512个字节表, 传统查表为256*4=1024个字节, 位域法压缩1倍):

unsigned long GetCRCL32_04C11DB7(unsigned long crcinit, unsigned long crcval)

{//(可以不要初值crcinit，多字节CRC32时入口需要对crcval做处理)

unsigned int i;

unsigned long crc=0;

crcval = crcinit ^ crcval;//初值(一般为0xFFFFFFFF)^明文,将CRC编码矩阵转化为CRC编码表

for(i = 0;i < 8;i ++)//8表级联查表8次(传统查表方法只需4次即4字节)

{

crc ^= CRCL32_04C11DB7_Array[i, crcval & 0x0F];//位域宽4每表16个字节

crcval >>= 4;//准备下一个位域,域宽4,每表16字节

}

return crc;

}

相应的移位算法程序为:

unsigned long GetCRCL32_04C11DB7(unsigned long crcinit, unsigned long crcval)

{//(可以不要初值crcinit，多字节CRC32时入口需要对crcval做处理)

unsigned int i, crc;

crc = crcinit ^ crcval;//初值(一般为0xFFFFFFFF)^明文,将CRC编码矩阵转化为CRC编码表

for(i = 0;i < 32;i ++)//双字32位

{

if (crc & 0x80000000)//左移记忆最高位

{

crc <<= 1;

crc ^= 0x04C11DB7;//权值

}

else

{

crc <<= 1;

}

return crc;

}

CRC位域多表查表方法可以应用于任何CRC查表方法，它结合了传统的移位算法和查表方法的各自优点，

充分考虑了空间和速度之间的关系，对小容量及速度要求的单片机特别适用。

由于位域可等长或不等长，故将可派生为更多“稀有”的查表方法，对加密算法比较有用。

本文给出了如何建立数组及查表程序及相应的移位算法程序，这里不是“比拼”，而是探讨更多的查表方法。

此法是菜农多年对CRC研究的结果，若网友发现早有此法，请告知，谢谢！！！

本文计算工具：http://www.hotc51.com/HotPower_HotWC3.html

此方法参考“性质”见：

http://blog.ednchina.com/hotpower/12817/category.aspx

http://blog.ednchina.com/hotpower/31641/category.aspx

http://bbs.pediy.com/showthread.php?t=93968&highlight

http://bbs.pediy.com/showthread.php?t=94251&highlight

http://bbs.pediy.com/showthread.php?t=93218&highlight

http://bbs.pediy.com/showthread.php?t=94191&highlight

http://bbs.pediy.com/showthread.php?t=92571&highlight

http://bbs.pediy.com/showthread.php?t=93248&highlight

关键字：CRC 位域多表查表方法引用地址：CRC位域多表查表方法

上一篇：CRC位域单表查表及建表方法
下一篇：C的库函数真的很好用！

推荐阅读最新更新时间：2024-03-16 13:58

STM32 硬件CRC和软件CRC速度比较

一、测试条件硬件： STM32L432KC 主频： 80MHz 编译器： IAR 8.20.1 编译选项： High Speed no size constraints CRC 生成多项式： 0x782f 二、测试方法软件提前生成CRC表，用于查询。分别使用软件CRC算法和硬件CRC外设对一个缓存进行计算，目的是从该缓存中找到同步头。同步头共11字节，前两个字节为后九个字节的CRC校验值。通过迭代算法依次对11字节进行计算和比较，当找到同步头后返回同步头偏移量。通过时间比较两者之间的速度。三、测试结果迭代24464次后，从缓存中找到同步头。不开启编译时间优化时，软件算法用时238ms，硬件CRC用时220ms。

[单片机]

STM32的硬件CRC32使用

最近用到STM32的CRC32模块,看一下官网的Lib,感觉用起来十分简单.但是,你会发现直接使用起来会出现,与很多在线CRC32的网站或者PC端的CRC32校验工具计算结果不一致！简直就是无语...... 搜索了一下,在21IC的论坛上面有关使用STM32的CRC32的大讨论,不过是09年的帖子.主要定论是STM32的CRC32与目前大多数的PC端软件使用的一些数据顺序及方法不一致.这里主要推荐看一下这个链接: STM32内置CRC模块的使用讨论的很火. 如果真如,那帖子说的那样.那么作为MCU这端,是有必要进行转换,要适应潮流.当然这里不是说ST不好. 按照帖子的结论： 1、每个字节的位序相反。stm32f是按32位，高位

[单片机]

STM32的硬件<font color='red'>CRC</font>32使用

STM32F10x 学习笔记3之CRC计算单元

STM32F 系列的单片机内部带了CRC32 计算单元。这个内置CRC模块的方法使用非常简单。其操作如下图所示。图 1 CRC计算单元框图归纳起来有如下几步操作： 1. 开启CRC单元的时钟。RCC_AHBPeriphClockCmd(RCC_AHBPeriph_CRC, ENABLE) 2. 复位CRC模块(设置CRC_CR=0x01)，这个操作把CRC余数初始化为0xFFFFFFFF 3. 把要计算的数据按逐个地写入CRC_DR寄存器 4. 写完所有的数据字后，从CRC_DR寄存器读出计算的结果 STM32F10x StdPeriph Driver 中提供了几个函数。 CRC_ResetDR(void)

[单片机]