现在网络上广为流传的CRC32的实现代码,是基于little endian的,
幸运地是,X86CPU和Ethernet都是基于little endian的。
little endian从小头开始吃鸡蛋,将the most significant放在相对低位。
一块以little endian存放和传输方式的数据块(我当然说的是x86环境),
如何适应CRC32模型?
解决方法:
数据块的每一个字节内,相对低位是多项式码中的相对高位;
数据块的字节间,相对低位的字节是多项式码中的相对高位。
举个例子:
/* C */
char String[]={a,b,c,d,e,f};
=
; MASM
String db 'a','b','c','d','e','f'
=
; 在x86环境中的内存分布
0x61 | 0x62 | 0x63 | 0x64 | 0x65 | 0x66
0110 0001 0110 0010 0110 0011 0110 0100 0110 0101 0110 0110
=
; 表示成多项式,!!!
1000 0110 0100 0110 1100 0110 0010 0110 1010 0110 0110 0110......
; 为什么我加省略号,后面还可能接有更多的字节。
为什么选择这种方法,(1)后面可以有更多的字节,而只需要简单地往这个队列添加;(2)方便实现,还有,跟贴吧!!!
CRC的本质是多项式的模2运算,如果你关心它运算的过程,你就知道它的各种可能的变体。
模2运算
模2运算的加法和减法的结果都是相同,可以用逻辑异或来表示;
模2加减运算的特点:每一位的结果和上位或下位无关。
模2除法的余数总比除数少1位。
模2运算没有进位和退位的概念。
模2除法的上商原则是:余数最高位为1,上1,余数最高位为0,上0.
这一结论可以推至比特位:
任何数与0x0000000异或,结果不变;
任何数与0xfffffff异或,结果为反,相当于not指令。
CRC_Table表
CRC16_Table
CRC_Table是一个元素数目为256,类型为unsigned short的一维数列
CRC32_Table
CRC_Table是一个元素数目为256,类型为unsigned int的一维数列
256=2^8,多项式的最高字节一共有8位
for(i=0;i<256;i++)
{
register = i; /* the top byte of the polynominal */
for(j=0;j<8;j++)
/* the ordinal of bits in a byte: 7, 6, 5, ... */
{
if ( register & 1 ) /* dividable */
register = ( register >> 1 ) ^ 0xEDB88320;
else
register >>= 1;
}
crc_table[i]=register;
}
char CRC_TABLE={y0,y1,y2,y3,y4,...,y255};
可以看作一个一对一的映射f(index)=y;
index是被除数,y是余数,映射关系是经过8次模2除法运算。
index = ( crc ^ char [n] ) & 0x000000ff;
crc = crc_table[index] ^ crc>>8;
一次运算,指8次有8比特位参加的模2除法运算。
crc ^ char [n]
本次运算的被除数,是上次运算的余数和char[n]的逻辑加
crc_table[index] ^ crc >> 8
最后的结果等于本次运算的结果异或上次运算的余数,
(余数需经过移位)