CRC位域多表查表方法

作者：時(shí)間：2016-12-02 來源：網(wǎng)絡(luò)

加入技術(shù)交流群
- 掃碼加入
  和技術(shù)大咖面對(duì)面交流
  海量資料庫查詢

CRC算法的實(shí)現(xiàn)一般可分運(yùn)算和查表兩種，前者靠對(duì)某CRC多項(xiàng)式的移位和異或得到，

占用程序空間小但速度慢。后者是將前者的運(yùn)算結(jié)果值排列為一個(gè)CRC矩陣表格，占用程

序空間大但速度快。

CRC查表方法經(jīng)典的有兩種，由于表格空間的不同，對(duì)于CRC8采用全表查詢，CRC16以上

采用小表(一般為256個(gè)元素的數(shù)組)查詢。

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

很大。每種CRC的多項(xiàng)式對(duì)應(yīng)一張CRC表，例CRC4左右移位各有16個(gè)CRC4表。CRC8左右移位

各有256個(gè)CRC8表。1個(gè)CRC8表占用256個(gè)字節(jié)，可組成16*16的數(shù)組，而1個(gè)CRC16表將占用

65536個(gè)字節(jié)，組成256*256的數(shù)組。

CRC位域多表查表方法與傳統(tǒng)的CRC查表方法最大的不同在于多表級(jí)聯(lián)壓縮表格空間。

此方法依據(jù)CRC的“性質(zhì)”: CRC[X]=CRC[行,列]=CRC[行,0]^CRC[0,列]。

以CRC8=X8+X5+X4+1為例，它的多項(xiàng)式的數(shù)字表達(dá)即權(quán)值=0x8C,右移CRC8算法。

已知CRC8[0x9A]=0x6F,我們可以將0x9A用位域劃分為高4位(16行)和低4位(16列)，即

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

根據(jù)：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的數(shù)組，可以用2*16的行列數(shù)組替代。

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個(gè)字節(jié))，位域表達(dá)為:

unsigned char Col:4;//D0~D3

unsigned char Row:4;//D4~D7

CRC位域三表查詢方法(占用20個(gè)字節(jié))，位域表達(dá)為:

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個(gè)字節(jié))，位域表達(dá)為:

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

此方法為多表查詢，即多表結(jié)果的多次異或，當(dāng)大CRC多表查詢時(shí)，可能由十多個(gè)表組成，為編程方便

一般將表壓縮成等長位域的單表或多維數(shù)組，以簡化程序。故CRC位域四表可組成矩陣：

unsigned char CRCR8_8C_Array[16]=

{

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

};

查表程序?yàn)?

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

{//(可以不要初值crcinit，多字節(jié)CRC8時(shí)入口需要對(duì)crcval做處理)

unsigned char i, crc=0;

crcval = crcinit ^ crcval;//初值^明文,將CRC編碼矩陣轉(zhuǎn)化為CRC編碼表

for(i = 0;i < 4;i ++)//4表級(jí)聯(lián)查表4次

{

crc ^= CRCR8_8C_Array[(i << 2) | (crcval & 0x03)];//位域?qū)?每表4個(gè)字節(jié)

crcval >>= 2;//準(zhǔn)備下一個(gè)位域,域?qū)?,每表4字節(jié)

}

return crc;

}

相應(yīng)的移位算法程序?yàn)?

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

{//(可以不要初值crcinit，多字節(jié)CRC8時(shí)入口需要對(duì)crcval做處理)

unsigned char i, crc;

crc = crcinit ^ crcval;//初值^明文,將CRC編碼矩陣轉(zhuǎn)化為CRC編碼表

for(i = 0;i < 8;i ++)//每字節(jié)8位

{

if (crc & 0x01)//右移記憶最低位

{

crc >>= 1;

crc ^= 0x8C;//權(quán)值

}

else

{

crc >>= 1;

}

return crc;

}

下面以CRC16的位域多表查表方法來說明大CRC位域多表查表方法。為統(tǒng)一方法采用等位域4即每表16個(gè)元素舉例.

左移CRC16=X16+X12+X5+1，多項(xiàng)式即權(quán)值=0x1021

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

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

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

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

我們可以構(gòu)成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

}

};

查表程序?yàn)?需要4*16*2=128個(gè)字節(jié)表, 傳統(tǒng)查表為256*2=512個(gè)字節(jié), 位域法壓縮4倍):

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

{//(可以不要初值crcinit，多字節(jié)CRC16時(shí)入口需要對(duì)crcval做處理)

unsigned int i, crc=0;

crcval = crcinit ^ crcval;//初值^明文,將CRC編碼矩陣轉(zhuǎn)化為CRC編碼表

for(i = 0;i < 4;i ++)//4表級(jí)聯(lián)查表4次(傳統(tǒng)查表方法只需2次即2字節(jié))

{

crc ^= CRCL16_1021_Array[i, crcval & 0x0F];//位域?qū)?每表16個(gè)字節(jié)

crcval >>= 4;//準(zhǔn)備下一個(gè)位域,域?qū)?,每表16字節(jié)

}

return crc;

}

新聞中心

CRC位域多表查表方法

評(píng)論

相關(guān)推薦

技術(shù)專區(qū)