冷缠带厂家
免费服务热线

Free service

hotline

010-00000000
冷缠带厂家
热门搜索:
技术资讯
当前位置:首页 > 技术资讯

CRC位域单表查表及建表方法 免费猫

发布时间:2020-02-17 14:02:18 阅读: 来源:冷缠带厂家

CRC位域单表查表及建表方法

菜农在《CRC位域多表查表方法》一文中,利用CRC的“性质”:CRC[a^b]=CRC[a]^CRC, 得出了多位域多表

实现压缩表格的方法。CRC多位域多表查表方法的优点就是“直观”,特别对位域宽度为4即表长16时CRC明文每位

16进制数即为表的坐标。缺点是每个位域都对应于一个CRC表,故表长的压缩不是很理想。

CRC多项式种类及位数繁多,如CRC4,CRC8,CRC10,CRC12,CRC16,CRC24,CRC32,CRC40,CRC64等等,每种多项式

对应与一个CRC矩阵,如CRC8为16*16的CRC8矩阵,CRC16为256*256的CRC16矩阵。即(2^(N/2))*(2^(N/2))的CRCN

矩阵。

为了压缩表格空间,可以将CRC[a^b]=CRC[a]^CRC变为CRC[a^b]=C^CRC[A^B]的形式减少为1个统一的CRC

表,其中C和A为上次CRC查表的一部分,B为CRC明文的一部分。 选择位域宽度为4即表长为16来说明CRC位域

单表查表及建表方法,传统的查表方法实际归为位域宽度为8即表长为256的CRC位域单表查表方法。由于CRC算法

有左右移位之分,故其对应查表程序和建表方法也不同。而CRC位域多表查表的查表程序和建表方法都是相同的。

以CRC8举例,CRC8位域4双表建表方法用其行和列各16个元素分别建立2个CRC表。

对于左移CRC8,权值0x07表格为:

CRCL8_Col[16]={0x00,0x07,0x0E,0x09,0x1C,0x1B,0x12,0x15,0x38,0x3F,0x36,0x31,0x24,0x23,0x2A,0x2D};

CRCL8_Row[16]={0x00,0x70,0xE0,0x90,0xC7,0xB7,0x27,0x57,0x89,0xF9,0x69,0x19,0x4E,0x3E,0xAE,0xDE};

对于右移CRC8,权值0x8C表格为:

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

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

而在CRC8位域4单表建表方法中,必须根据CRC的移位方式来来选择某行或某列唯一16个元素建立1个CRC表.

故CRC位域单表相对CRC位域多表占用的空间要进一步压缩数倍,任何CRC表都可只用16个表格。

对于左移CRC8,权值0x07表格为(左移位域4取列表16个):

CRCL8_Col[16]={CRC[0x00],CRC[0x01],CRC[0x02],...CRC[0x0D],CRC[0x0E],CRC[0x0F]};

即:CRCL8_Col[16]={0x00,0x07,0x0E,0x09,0x1C,0x1B,0x12,0x15,0x38,0x3F,0x36,0x31,0x24,0x23,0x2A,0x2D};

左移CRC8查表核心程序为(字符型不分大小端存储模式):

unsigned char GetCRCL8(unsigned char crcinit, unsigned char crcval)

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

unsigned char i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//1个字节位域4需要2次完成

{

crc = (crc 4) ^ CRCL8_Col[((crc ^ crcval) 4) 0x0F];//位域宽4单表16个字节

crcval = 4;//准备下一个位域,域宽4

}

return crc;

}

对于右移CRC8,权值0x8C表格为(右移位域4取行表16个):

CRCR8_Row[16]={CRC[0x00],CRC[0x10],CRC[0x20],...CRC[0xD0],CRC[0xE0],CRC[0xF0]};

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

右移CRC8查表核心程序为(字符型不分大小端存储模式):

unsigned char GetCRCR8(unsigned char crcinit, unsigned char crcval)

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

unsigned char i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//1个字节位域4需要2次完成

{

crc = (crc 4) ^ CRCR8_Row[(crc ^ crcval) 0x0F];//位域宽4单表16个字节

crcval = 4;//准备下一个位域,域宽4

}

return crc;

}

CRC位域4单表查表及建表原则:

左移位域4取列表16个,大端存储模式。右移位域4取行表16个,小端存储模式。

对于左移CRC12,权值XX,表格为(左移位域4取列表16个):

CRCL12_Col[16]={CRC[0x000],CRC[0x001],CRC[0x002],...CRC[0x00D],CRC[0x00E],CRC[0x00F]};

左移CRC12查表核心程序为(大端存储模式):

unsigned int GetCRCL12(unsigned int crcinit, unsigned int crcval)

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

unsigned int i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//3个字节位域4需要6次完成

{

crc = (crc 4) ^ CRCL12_Col[((crc ^ crcval) 8) 0x0F];//位域宽4单表16个字节

crcval = 4;//准备下一个位域,域宽4

}

return crc;

}

对于右移CRC12,权值XX,表格为(右移位域4取行表16个):

CRCR12_Row[16]={CRC[0x0000],CRC[0x100],CRC[0x200],...CRC[0xD00],CRC[0xE00],CRC[0xF00]};

右移CRC12查表核心程序为(小端存储模式):

unsigned int GetCRCR12(unsigned int crcinit, unsigned int crcval)

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

unsigned int i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//3个字节位域4需要6次完成

{

crc = (crc 4) ^ CRCR12_Row[(crc ^ crcval) 0x0F];//位域宽4单表16个字节

crcval = 4;//准备下一个位域,域宽4

}

return crc;

}

对于左移CRC16,权值XX,表格为(左移位域4取列表16个):

CRCL16_Col[16]={CRC[0x0000],CRC[0x0001],CRC[0x0002],...CRC[0x000D],CRC[0x000E],CRC[0x000F]};

左移CRC16查表核心程序为(大端存储模式):

unsigned int GetCRCL16(unsigned int crcinit, unsigned int crcval)

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

unsigned int i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//2个字节位域4需要4次完成

{

crc = (crc 4) ^ CRCL16_Col[((crc ^ crcval) 12) 0x0F];//位域宽4单表16个字节

crcval = 4;//准备下一个位域,域宽4

}

return crc;

}

对于右移CRC16,权值XX,表格为(右移位域4取行表16个):

CRCR16_Row[16]={CRC[0x0000],CRC[0x1000],CRC[0x2000],...CRC[0xD000],CRC[0xE000],CRC[0xF000]};

右移CRC16查表核心程序为(小端存储模式):

unsigned int GetCRCR16(unsigned int crcinit, unsigned int crcval)

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

unsigned int i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//2个字节位域4需要4次完成

{

crc = (crc 4) ^ CRCR16_Row[(crc ^ crcval) 0x0F];//位域宽4单表16个字节

crcval = 4;//准备下一个位域,域宽4

}

return crc;

}

对于左移CRC32,权值XX,表格为(左移位域4取列表16个):

CRCL32_Col[16]={CRC[0x00000000],CRC[0x00000001],...CRC[0x0000000E],CRC[0x0000000F]};

左移CRC32查表核心程序为(大端存储模式):

unsigned long GetCRCL32(unsigned long crcinit, unsigned long crcval)

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

unsigned long i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//4个字节位域4需要8次完成

{

crc = (crc 4) ^ CRCL32_Col[((crc ^ crcval) 28) 0x0F];//位域宽4单表16个字节

crcval = 4;//准备下一个位域,域宽4

}

return crc;

}

对于右移CRC32,权值XX,表格为(右移位域4取行表16个):

CRCR32_Row[16]={CRC[0x00000000],CRC[0x10000000],...CRC[0xE0000000],CRC[0xF0000000]};

右移CRC32查表核心程序为(小端存储模式):

unsigned int GetCRCR32(unsigned long crcinit, unsigned long crcval)

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

unsigned long i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//4个字节位域4需要8次完成

{

crc = (crc 4) ^ CRCR32_Row[(crc ^ crcval) 0x0F];//位域宽4单表16个字节

crcval = 4;//准备下一个位域,域宽4

}

return crc;

}

CRC位域8单表查表及建表原则(传统的查表模式):

左移位域8取列表256个,大端存储模式。右移位域8取行表256个,小端存储模式。

对于左移CRC16,权值XX,表格为(左移位域8取列表256个):

CRCL16_Col[256]={CRC[0x0000],CRC[0x0001],CRC[0x0002],...CRC[0x00FD],CRC[0x00FE],CRC[0x00FF]};

左移CRC16查表核心程序为(大端存储模式):

unsigned int GetCRCL16(unsigned int crcinit, unsigned int crcval)

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

unsigned int i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//2个字节位域8只需要2次完成

{

crc = (crc 8) ^ CRCL16_Col[((crc ^ crcval) 8) 0xFF];//位域宽8单表256个字节

crcval = 8;//准备下一个位域,域宽8

}

return crc;

}

对于右移CRC16,权值XX,表格为(右移位域8取行表256个):

CRCR16_Row[256]={CRC[0x0000],CRC[0x1000],CRC[0x2000],...CRC[0xFD00],CRC[0xFE00],CRC[0xFF00]};

右移CRC16查表核心程序为(小端存储模式):

unsigned int GetCRCR16(unsigned int crcinit, unsigned int crcval)

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

unsigned int i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//2个字节位域8只需要2次完成

{

crc = (crc 8) ^ CRCR16_Row[(crc ^ crcval) 0xFF];//位域宽8单表256个字节

crcval = 8;//准备下一个位域,域宽8

}

return crc;

}

对于左移CRC32,权值XX,表格为(左移位域8取列表256个):

CRCL32_Col[256]={CRC[0x00000000],CRC[0x00000001],...CRC[0x000000FE],CRC[0x000000FF]};

左移CRC32查表核心程序为(大端存储模式):

unsigned long GetCRCL32(unsigned long crcinit, unsigned long crcval)

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

unsigned long i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//4个字节位域8只需要4次完成

{

crc = (crc 8) ^ CRCL32_Col[((crc ^ crcval) 24) 0x0F];//位域宽8单表256个字节

crcval = 8;//准备下一个位域,域宽8

}

return crc;

}

对于右移CRC32,权值XX,表格为(右移位域8取行表256个):

CRCR32_Row[256]={CRC[0x00000000],CRC[0x10000000],...CRC[0xFE000000],CRC[0xFF000000]};

右移CRC32查表核心程序为(小端存储模式):

unsigned long GetCRCR32(unsigned long crcinit, unsigned long crcval)

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

unsigned long i, crc=0;

crcval = crcinit ^ crcval;

for(i = 0;i i ++)//4个字节位域8只需要4次完成

{

crc = (crc 8) ^ CRCR32_Row[(crc ^ crcval) 0xFF];//位域宽8单表256个字节

crcval = 8;//准备下一个位域,域宽8

}

return crc;

}

CRC位域8每表256个元素,适合以字节为存储单位,故程序的入口参数用数组即表指针替代,如:

网上的左移CRC16查表核心程序为(crcbuff为大端存储模式):

unsigned int GetCRCL16(unsigned int crcinit, unsigned char *crcbuff)

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

unsigned int i, crc=0;

for(i = 0;i i ++)//2个字节位域8只需要2次完成

{

crc = (crc 8) ^ CRCL16_Col[(((crcinit ^ crc) 8) ^ *crcbuff++) 0xFF];//位域宽8单表256个字节

crcinit = 8;//下一位域的初值

}

return crc;

}

网上的右移CRC16查表核心程序为(crcbuff为小端存储模式):

unsigned int GetCRCR16(unsigned int crcinit, unsigned char *crcbuff)

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

unsigned int i, crc=0;

for(i = 0;i i ++)//2个字节位域8只需要2次完成

{

crc = (crc 8) ^ CRCR16_Col[((crcinit ^ crc) ^ *crcbuff++) 0xFF];//位域宽8单表256个字节

crcinit = 8;//下一位域的初值

}

return crc;

}

网上的左移CRC32查表核心程序为(crcbuff为大端存储模式):

unsigned long GetCRCL32(unsigned long crcinit, unsigned char *crcbuff)

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

unsigned long i, crc=0;

for(i = 0;i i ++)//4个字节位域8只需要4次完成

{

crc = (crc 8) ^ CRCL32_Col[(((crcinit ^ crc) 24) ^ *crcbuff++) 0xFF];//位域宽8单表256个字节

crcinit = 8;//下一位域的初值

}

return crc;

}

网上的右移CRC32查表核心程序为(crcbuff为小端存储模式):

unsigned long GetCRCR32(unsigned long crcinit, unsigned char *crcbuff)

{//(可以不要初值crcinit(一般为0或0xFFFFFFFF),多字节CRC32时入口需要对crcval做处理)

unsigned long i, crc=0;

for(i = 0;i i ++)//4个字节位域8只需要4次完成

{

crc = (crc 8) ^ CRCR32_Col[((crcinit ^ crc) ^ *crcbuff++) 0xFF];//位域宽8单表256个字节

crcinit = 8;//下一位域的初值

}

return crc;

}

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

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

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

像CRC10,CRC12这种“非字节”存储的CRC查表,可用位域2(CRC10)及位域3和位域4位域6等方法。

总之位域4是更为普遍的压缩CRC表格的好方法,位域宽度大则循环次数少速度更快。

网上流行的一般为位域8,自然速度最快,但表格空间最大。

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

此法是菜农多年对CRC研究的结果和总结。

具体应用:

CRC64ISO(d800000000000000)的16四字表长查表程序

CRC64ECMA(42F0E1EBA9EA3693)的16四字表长查表程序

CRC32IEEE(EDB88320)的16双字表长查表程序

CRC16CCITT(1021)的16字表长查表程序

CRC-16-IBM(A001)的16字表长查表程序

1-Wire中CRC8的16字节表长查表程序

SMBUS中PEC(CRC)16字节表长查表程序

本文计算工具:[url=http://[color=] FONT]http://www.hotc51.com/HotPower_HotWC3.html[/url]

菜农HotPower@126.com 2009.10.18 于雁塔菜地

宝蓝旗袍

书屋小说全集免费阅读

君子兰种植