|
本帖最后由 hotpower 于 2009-10-18 21:28 編輯 菜農在《CRC位域多表查表方法》一文中，利用CRC的“性質(zhì)”:CRC[a^b]=CRC[a]^CRC, 得出了多位域多表 實(shí)現壓縮表格的方法。CRC多位域多表查表方法的優(yōu)點(diǎn)就是“直觀(guān)”，特別對位域寬度為4即表長(cháng)16時(shí)CRC明文每位 16進(jìn)制數即為表的坐標。缺點(diǎn)是每個(gè)位域都對應于一個(gè)CRC表，故表長(cháng)的壓縮不是很理想。 CRC多項式種類(lèi)及位數繁多，如CRC4,CRC8,CRC10,CRC12,CRC16,CRC24,CRC32,CRC40,CRC64等等，每種多項式 對應與一個(gè)CRC矩陣，如CRC8為16*16的CRC8矩陣，CRC16為256*256的CRC16矩陣。即(2^(N/2))*(2^(N/2))的CRCN 矩陣。 為了壓縮表格空間，可以將CRC[a^b]=CRC[a]^CRC變?yōu)镃RC[a^b]=C^CRC[A^B]的形式減少為1個(gè)統一的CRC 表，其中C和A為上次CRC查表的一部分，B為CRC明文的一部分。 選擇位域寬度為4即表長(cháng)為16來(lái)說(shuō)明CRC位域 單表查表及建表方法，傳統的查表方法實(shí)際歸為位域寬度為8即表長(cháng)為256的CRC位域單表查表方法。由于CRC算法 有左右移位之分，故其對應查表程序和建表方法也不同。而CRC位域多表查表的查表程序和建表方法都是相同的。 以CRC8舉例，CRC8位域4雙表建表方法用其行和列各16個(gè)元素分別建立2個(gè)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的移位方式來(lái)來(lái)選擇某行或某列唯一16個(gè)元素建立1個(gè)CRC表. 故CRC位域單表相對CRC位域多表占用的空間要進(jìn)一步壓縮數倍，任何CRC表都可只用16個(gè)表格。 對于左移CRC8，權值0x07表格為(左移位域4取列表16個(gè)): 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時(shí)入口需要對crcval做處理) unsigned char i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 2;i ++)//1個(gè)字節位域4需要2次完成 { crc = (crc << 4) ^ CRCL8_Col[((crc ^ crcval) >> 4) & 0x0F];//位域寬4單表16個(gè)字節 crcval <<= 4;//準備下一個(gè)位域,域寬4 } return crc; } 對于右移CRC8，權值0x8C表格為(右移位域4取行表16個(gè)): 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時(shí)入口需要對crcval做處理) unsigned char i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 2;i ++)//1個(gè)字節位域4需要2次完成 { crc = (crc >> 4) ^ CRCR8_Row[(crc ^ crcval) & 0x0F];//位域寬4單表16個(gè)字節 crcval >>= 4;//準備下一個(gè)位域,域寬4 } return crc; } CRC位域4單表查表及建表原則： 左移位域4取列表16個(gè)，大端存儲模式。右移位域4取行表16個(gè)，小端存儲模式。 對于左移CRC12，權值XX，表格為(左移位域4取列表16個(gè)): 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時(shí)入口需要對crcval做處理) unsigned int i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 6;i ++)//3個(gè)字節位域4需要6次完成 { crc = (crc << 4) ^ CRCL12_Col[((crc ^ crcval) >> 8) & 0x0F];//位域寬4單表16個(gè)字節 crcval <<= 4;//準備下一個(gè)位域,域寬4 } return crc; } 對于右移CRC12，權值XX，表格為(右移位域4取行表16個(gè)): 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時(shí)入口需要對crcval做處理) unsigned int i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 6;i ++)//3個(gè)字節位域4需要6次完成 { crc = (crc >> 4) ^ CRCR12_Row[(crc ^ crcval) & 0x0F];//位域寬4單表16個(gè)字節 crcval >>= 4;//準備下一個(gè)位域,域寬4 } return crc; } 對于左移CRC16，權值XX，表格為(左移位域4取列表16個(gè)): 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時(shí)入口需要對crcval做處理) unsigned int i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 4;i ++)//2個(gè)字節位域4需要4次完成 { crc = (crc << 4) ^ CRCL16_Col[((crc ^ crcval) >> 12) & 0x0F];//位域寬4單表16個(gè)字節 crcval <<= 4;//準備下一個(gè)位域,域寬4 } return crc; } 對于右移CRC16，權值XX，表格為(右移位域4取行表16個(gè)): 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時(shí)入口需要對crcval做處理) unsigned int i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 4;i ++)//2個(gè)字節位域4需要4次完成 { crc = (crc >> 4) ^ CRCR16_Row[(crc ^ crcval) & 0x0F];//位域寬4單表16個(gè)字節 crcval >>= 4;//準備下一個(gè)位域,域寬4 } return crc; } 對于左移CRC32，權值XX，表格為(左移位域4取列表16個(gè)): CRCL32_Col[16]={CRC[0x00000000],CRC[0x00000001],...CRC[0x0000000E],CRC[0x0000000F]}; 左移CRC32查表核心程序為(大端存儲模式): unsigned long GetCRCL32(unsigned long crcinit, unsigned long crcval) {//(可以不要初值crcinit，多字節CRC32時(shí)入口需要對crcval做處理) unsigned long i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 8;i ++)//4個(gè)字節位域4需要8次完成 { crc = (crc << 4) ^ CRCL32_Col[((crc ^ crcval) >> 28) & 0x0F];//位域寬4單表16個(gè)字節 crcval <<= 4;//準備下一個(gè)位域,域寬4 } return crc; } 對于右移CRC32，權值XX，表格為(右移位域4取行表16個(gè)): CRCR32_Row[16]={CRC[0x00000000],CRC[0x10000000],...CRC[0xE0000000],CRC[0xF0000000]}; 右移CRC32查表核心程序為(小端存儲模式): unsigned int GetCRCR32(unsigned long crcinit, unsigned long crcval) {//(可以不要初值crcinit，多字節CRC32時(shí)入口需要對crcval做處理) unsigned long i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 8;i ++)//4個(gè)字節位域4需要8次完成 { crc = (crc >> 4) ^ CRCR32_Row[(crc ^ crcval) & 0x0F];//位域寬4單表16個(gè)字節 crcval >>= 4;//準備下一個(gè)位域,域寬4 } return crc; } CRC位域8單表查表及建表原則(傳統的查表模式)： 左移位域8取列表256個(gè)，大端存儲模式。右移位域8取行表256個(gè)，小端存儲模式。 對于左移CRC16，權值XX，表格為(左移位域8取列表256個(gè)): 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時(shí)入口需要對crcval做處理) unsigned int i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 2;i ++)//2個(gè)字節位域8只需要2次完成 { crc = (crc << 8) ^ CRCL16_Col[((crc ^ crcval) >> 8) & 0xFF];//位域寬8單表256個(gè)字節 crcval <<= 8;//準備下一個(gè)位域,域寬8 } return crc; } 對于右移CRC16，權值XX，表格為(右移位域8取行表256個(gè)): 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時(shí)入口需要對crcval做處理) unsigned int i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 2;i ++)//2個(gè)字節位域8只需要2次完成 { crc = (crc >> 8) ^ CRCR16_Row[(crc ^ crcval) & 0xFF];//位域寬8單表256個(gè)字節 crcval >>= 8;//準備下一個(gè)位域,域寬8 } return crc; } 對于左移CRC32，權值XX，表格為(左移位域8取列表256個(gè)): CRCL32_Col[256]={CRC[0x00000000],CRC[0x00000001],...CRC[0x000000FE],CRC[0x000000FF]}; 左移CRC32查表核心程序為(大端存儲模式): unsigned long GetCRCL32(unsigned long crcinit, unsigned long crcval) {//(可以不要初值crcinit，多字節CRC32時(shí)入口需要對crcval做處理) unsigned long i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 4;i ++)//4個(gè)字節位域8只需要4次完成 { crc = (crc << 8) ^ CRCL32_Col[((crc ^ crcval) >> 24) & 0x0F];//位域寬8單表256個(gè)字節 crcval <<= 8;//準備下一個(gè)位域,域寬8 } return crc; } 對于右移CRC32，權值XX，表格為(右移位域8取行表256個(gè)): CRCR32_Row[256]={CRC[0x00000000],CRC[0x10000000],...CRC[0xFE000000],CRC[0xFF000000]}; 右移CRC32查表核心程序為(小端存儲模式): unsigned long GetCRCR32(unsigned long crcinit, unsigned long crcval) {//(可以不要初值crcinit，多字節CRC32時(shí)入口需要對crcval做處理) unsigned long i, crc=0; crcval = crcinit ^ crcval; for(i = 0;i < 4;i ++)//4個(gè)字節位域8只需要4次完成 { crc = (crc >> 8) ^ CRCR32_Row[(crc ^ crcval) & 0xFF];//位域寬8單表256個(gè)字節 crcval >>= 8;//準備下一個(gè)位域,域寬8 } return crc; } CRC位域8每表256個(gè)元素，適合以字節為存儲單位，故程序的入口參數用數組即表指針替代，如: 網(wǎng)上的左移CRC16查表核心程序為(crcbuff為大端存儲模式): unsigned int GetCRCL16(unsigned int crcinit, unsigned char *crcbuff) {//(可以不要初值crcinit，多字節CRC16時(shí)入口需要對crcval做處理) unsigned int i, crc=0; for(i = 0;i < 2;i ++)//2個(gè)字節位域8只需要2次完成 { crc = (crc << 8) ^ CRCL16_Col[(((crcinit ^ crc) >> 8) ^ *crcbuff++) & 0xFF];//位域寬8單表256個(gè)字節 crcinit <<= 8;//下一位域的初值 } return crc; } 網(wǎng)上的右移CRC16查表核心程序為(crcbuff為小端存儲模式): unsigned int GetCRCR16(unsigned int crcinit, unsigned char *crcbuff) {//(可以不要初值crcinit，多字節CRC16時(shí)入口需要對crcval做處理) unsigned int i, crc=0; for(i = 0;i < 2;i ++)//2個(gè)字節位域8只需要2次完成 { crc = (crc >> 8) ^ CRCR16_Col[((crcinit ^ crc) ^ *crcbuff++) & 0xFF];//位域寬8單表256個(gè)字節 crcinit >>= 8;//下一位域的初值 } return crc; } 網(wǎng)上的左移CRC32查表核心程序為(crcbuff為大端存儲模式): unsigned long GetCRCL32(unsigned long crcinit, unsigned char *crcbuff) {//(可以不要初值crcinit，多字節CRC32時(shí)入口需要對crcval做處理) unsigned long i, crc=0; for(i = 0;i < 4;i ++)//4個(gè)字節位域8只需要4次完成 { crc = (crc << 8) ^ CRCL32_Col[(((crcinit ^ crc) >> 24) ^ *crcbuff++) & 0xFF];//位域寬8單表256個(gè)字節 crcinit <<= 8;//下一位域的初值 } return crc; } 網(wǎng)上的右移CRC32查表核心程序為(crcbuff為小端存儲模式): unsigned long GetCRCR32(unsigned long crcinit, unsigned char *crcbuff) {//(可以不要初值crcinit(一般為0或0xFFFFFFFF)，多字節CRC32時(shí)入口需要對crcval做處理) unsigned long i, crc=0; for(i = 0;i < 4;i ++)//4個(gè)字節位域8只需要4次完成 { crc = (crc >> 8) ^ CRCR32_Col[((crcinit ^ crc) ^ *crcbuff++) & 0xFF];//位域寬8單表256個(gè)字節 crcinit >>= 8;//下一位域的初值 } return crc; } CRC位域單表查表方法可以應用于任何CRC查表方法，它結合了傳統的移位算法和查表方法的各自?xún)?yōu)點(diǎn)， 充分考慮了空間和速度之間的關(guān)系，對小容量及速度要求的單片機特別適用。 由于位域可等長(cháng)或不等長(cháng)，故將可派生為更多“稀有”的查表方法，對加密算法比較有用。 像CRC10,CRC12這種“非字節”存儲的CRC查表，可用位域2(CRC10)及位域3和位域4位域6等方法。 總之位域4是更為普遍的壓縮CRC表格的好方法，位域寬度大則循環(huán)次數少速度更快。 網(wǎng)上流行的一般為位域8，自然速度最快，但表格空間最大。 本文給出了如何建立數組及查表程序及相應的移位算法程序，這里不是“比拼”，而是探討更多的查表方法。 此法是菜農多年對CRC研究的結果和總結。 具體應用： CRC64ISO(d800000000000000)的16四字表長(cháng)查表程序 CRC64ECMA(42F0E1EBA9EA3693)的16四字表長(cháng)查表程序 CRC32IEEE(EDB88320)的16雙字表長(cháng)查表程序 CRC16CCITT(1021)的16字表長(cháng)查表程序 CRC-16-IBM(A001)的16字表長(cháng)查表程序 1-Wire中CRC8的16字節表長(cháng)查表程序 SMBUS中PEC(CRC)16字節表長(cháng)查表程序 本文計算工具：[url=http://[color=] 菜農HotPower@126.com 2009.10.18 于雁塔菜地 |
