CRC位域多表查表方法
加入技術(shù)交流群
相應的移位算法程序為:
unsigned int GetCRCL16_1021(unsigned int crcinit, unsigned int crcval)//CRC16=X16+X12+X5+1
{//(可以不要初值crcinit，多字節(jié)CRC16時入口需要對crcval做處理)
unsigned int i, crc;
crc = crcinit ^ crcval;//初值^明文,將CRC編碼矩陣轉(zhuǎn)化為CRC編碼表
for(i = 0;i < 16;i ++)//雙字節(jié)16位
{
if (crc & 0x8000)//左移記憶最高位
{
crc <<= 1;
crc ^= 0x1021;//權(quán)值
}
else
{
crc <<= 1;
}
}
return crc;
}
對比傳統(tǒng)的CRC16_1021(左移、大端數(shù)據(jù)存儲方式)查表方法：
CRC16_1021_Array[256]={//位域?qū)?每表256個字節(jié)
CRC16[0x0000], CRC16[0x0001], CRC16[0x0002],...CRC16[0x00FD], CRC16[0x00FE], CRC16[0x00FF]
};
即：
CRC16_1021_Array[256]={//位域?qū)?每表256個字節(jié)
0x0000, 0x1021, 0x2042, 0x3063, 0x4084,...0x2e93, 0x3eb2, 0x0ed1, 0x1ef0
};
查表核心程序為:
unsigned int GetCRC16(unsigned int crcinit, unsigned int crcval)
{//(可以不要初值crcinit，多字節(jié)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];//位域?qū)?每表256個字節(jié)
crcval <<= 8;//準備下一個位域,域?qū)?,每表256字節(jié)
}
return crc;
}
此法實際為(大端數(shù)據(jù)存儲方式):
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 權(quán)值0x04C11DB7
unsigned long CRCL32_04C11DB7_Array[8, 16]={//數(shù)組元素未列完，有空搞個自動生成序列
{//位域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個字節(jié)表, 傳統(tǒng)查表為256*4=1024個字節(jié), 位域法壓縮1倍):
unsigned long GetCRCL32_04C11DB7(unsigned long crcinit, unsigned long crcval)
{//(可以不要初值crcinit，多字節(jié)CRC32時入口需要對crcval做處理)
unsigned int i;
unsigned long crc=0;
crcval = crcinit ^ crcval;//初值(一般為0xFFFFFFFF)^明文,將CRC編碼矩陣轉(zhuǎn)化為CRC編碼表
for(i = 0;i < 8;i ++)//8表級聯(lián)查表8次(傳統(tǒng)查表方法只需4次即4字節(jié))
{
crc ^= CRCL32_04C11DB7_Array[i, crcval & 0x0F];//位域?qū)?每表16個字節(jié)
crcval >>= 4;//準備下一個位域,域?qū)?,每表16字節(jié)
}
return crc;
}
相應的移位算法程序為:
unsigned long GetCRCL32_04C11DB7(unsigned long crcinit, unsigned long crcval)
{//(可以不要初值crcinit，多字節(jié)CRC32時入口需要對crcval做處理)
unsigned int i, crc;
crc = crcinit ^ crcval;//初值(一般為0xFFFFFFFF)^明文,將CRC編碼矩陣轉(zhuǎn)化為CRC編碼表
for(i = 0;i < 32;i ++)//雙字32位
{
if (crc & 0x80000000)//左移記憶最高位
{
crc <<= 1;
crc ^= 0x04C11DB7;//權(quán)值
}
else
{
crc <<= 1;
}
}
return crc;
}
CRC位域多表查表方法可以應用于任何CRC查表方法，它結(jié)合了傳統(tǒng)的移位算法和查表方法的各自優(yōu)點，
充分考慮了空間和速度之間的關系，對小容量及速度要求的單片機特別適用。
由于位域可等長或不等長，故將可派生為更多“稀有”的查表方法，對加密算法比較有用。
本文給出了如何建立數(shù)組及查表程序及相應的移位算法程序，這里不是“比拼”，而是探討更多的查表方法。
此法是菜農(nóng)多年對CRC研究的結(jié)果，若網(wǎng)友發(fā)現(xiàn)早有此法，請告知，謝謝?。?！
本文計算工具：http://www.hotc51.com/HotPower_HotWC3.html
此方法參考“性質(zhì)”見：
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
評論