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
评论