CRC位域多表查表方法
發布時間：2009-10-16 18:32
發布者：hotpower
|
本帖最后由 hotpower 于 2009-10-18 21:32 編輯 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; } 相應的移位算法程序為: 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 菜農HotPower@126.com 2009.10.16 于雁塔菜地 |
網友評論