程序文件请在这里下载https://bbs.21ic.com/upfiles/img/20076/2007619133825985.rar
CRC(查表)-表的由来
by lenglx (lenglx@qq.com,lianxi.leng@changhong.com)
2006/07/25
1)硬件电路组成
a) x^16 + x^12 + x^5 + 1
┌───────────┬─────────────────┬─────────────┐
↑ ┌─┬─┬─┬─┐ ↓ ┌─┬─┬─┬─┬─┬─┬─┐ ↓ ┌─┬─┬─┬─┬─┐ │
◎←│15│14│13│12│←◎←│11│10│09│08│07│06│05│←◎←│04│03│02│01│00│←┘
↑ └─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┘
in
b) x^8 + x^2 + x + 1
┌───────────────┬─────┬─────┐
↑ ┌─┬─┬─┬─┬─┬─┐ ↓ ┌─┐ ↓ ┌─┐ │
◎←│07│06│05│04│03│02│←◎←│01│←◎←│00│←┘
↑ └─┴─┴─┴─┴─┴─┘ └─┘ └─┘
in
2) 简单算法模型(按bit计算)
照以上的硬件电路来看,其工作原理就是:
如果原来CRC的最高位异或输入是1的话,那么絇OSThttps://bbs.21ic.com/club/bbs/SaveOwnerEd?并且异或生成多项式(图a为0x1021,图b为0x7).
如果原来CRC的最高位异或输入是高位异或输入是0的话,那么结果就是CRC左移一位.
那么可以得到以下的程序(以图a例)
U16 crc_cal(bit * in, U32 cnt)
{
U16 crc = 0;
while(cnt--)
{
bool tmp = (crc >> 15) ^ *in;
crc <<= 1;
if(tmp)
crc ^= 0x1021;
in ++;
}
return crc;
}
3) 查表(按字节计算)
很显然,按比特计算的方法,其效率是低下的.
下面介绍查表方法(按字节计算).
要知道为什么可以用查表的方法,需要一些预备知识.
以图b为例,假设当前的CRC值是1011 1001,现在要输入4比特数据1101,其生成多项式是:0000 0111
CRC = 1011 1001, in=1101 , G(X)= 0000 0111
<计算方法1> <计算方法2>
step: 1011 1001 0110 1001
1: 011 1001 0 110 1001 0
2: 11 1001 00 10 1001 00
^ 00 0001 11 ^00 0001 11 <1>
-------------- --------------
11 1000 11 10 1000 11
3: 1 1000 110 0 1000 110
^ 0 0000 111 ^0 0000 111 <2>
---------------- -------------
1 1000 001 0 1000 001
4: 1000 0010 1000 0010
<计算方法1>是硬件电路的完全模拟算法
step 1: 将crc左移一位,因为crc的最高位是1,输入也是1,所以不做处理.
step 2: 将crc左移一位,因为crc的最高位是0,输入是1,所以还需要异或G(X).
....
step 4: 将crc左移一位,因为crc的最高位是0,输入也是0,所以不做处理.
得到最终的结果 crc = 1000 0010
实际上,在crc左移以后,是否还要异或生成多项式的条件是: crc的最高位和输入位异或后的值.
那么是否可以预先将CRC(h)的值与要输入的4比特数据异或,作为是否判断条件呢.
答案是肯定的. CRC = 1011 1001, in=1101, CRC(h)^in = 0110
其计算过程见<计算方法2>
step 1: 将CRC左移一位,因为CRC的最高位是0,所以不做处理.
step 2: 将CRC左移一位,因为CRC的最高位是1,所以还需要异或G(X).
....
step 4: 将CRC左移一位,因为CRC的最高位是0,所以不做处理.
得到最终的结果 CRC = 1000 0010
虽然,上面的结果是一样的,可有证据证明无论什么情况下,结果都是对的?
静下来想想,你就是知道这2个方法确实能得出相同的结果.
当4比特的输入完成之后,整个CRC值左移了4位,原来的CRC(h)只是作为判断异或生成多项式的条件存在过.
最终的CRC值完全是G(X)和CRC(l)不停地(异或/移位)的结果.
虽然,在CRC计算的过程中,CRC不停的在变化着,但:
1. 如果在<方法1>中,由于CRC的最高位和输入异或后的结果等于0,那么CRC只是左移一位.
显然2个方法是一样的.
2. 如果在<方法1>中,由于CRC的最高位和输入异或后的结果等于1,那么CRC左移一位后,还需要异或G(X).
异或G(X)的过程中,可能使CRC的后续某位产生变化(也可能不变化,视生成多项式的值而定).
a.如果没发生变化,那当这位最后移到最高位,作为判断条件的时候,仍然是以前的这个值和输入位的异或.
显然2个计算方法是一样的.
b.如果变化过, 那当这位最后移到最高位,作为判断条件的时候,是变化过后的值和输入位的异或.
但如果<方法1>能引起后续某位的变化,<方法2>同样也会引起同一位的变化.
这样当这位最后移到最高位,作为判断条件的时候,2种方法的判断条件仍然是一致的.
* 关于这部分,我描述得不怎么清楚,那是因为我小时候地语文基础没打好,:).
如果你有更好地描述,请告诉我.
好了,预备知识完毕,现在开始探讨那个查找表是怎么来的.
请看<方法2>,最终的CRC的结果是: (CRC(l) << 4) ^ <1> ^ <2>
<计算方法2>
CRC = 1011 1001, in=1101 , G(X)= 0000 0111
|-----------------------> CRC(h)^in = 1011 ^ 1101 = 0110
|
| |------------------> CRC(l)
---- ----
0110 1001
110 1001 0
10 1001 00
^00 0001 11 <1>
--------------
10 1000 11
0 1000 110
^0 0000 111 <2>
-------------
0 1000 001
1000 0010
由于异或的可结合律,其结果等同于: (CRC(l) << 4) ^ ( <1> ^ <2> )
这说明, ( <1) ^ <2> )可以预先制作成表格,采用查表的方法计算CRC, 表的索引是 CRC(h) ^ in .
其结果是: ( CRC(l) << 4) ^ table[ CRC(h) ^ in ].
因为是4比特,表的大小是16.
表的内容可以根据G(X),预先计算.
这里举例用的4比特,基于字节的方法可以用同样的方法.
那么现在开始编程了.
U16 crc_tab[256]= {...};
U16 crc_cal(U8 * ptr, U32 cnt)
{
U16 crc = 0;
U8 da;
while (cnt--)
{
da = crc >> 8; // CRC(h)
crc <<= 8;
crc ^= crc_tab[da ^ *ptr++];
}
return crc;
}
既然你已经知道了查表的原理,那么编一个计算表值的程序不成问题了.
#define GX 0x1021
void CCrcDlg::OnButton1()
{
WORD table[256];
for(int i =0; i<256; i++)
{
WORD crc = i << 8;
for(int n=0; n<8; n++)
{
bool tmp = crc & (1<<15) ? true : false;
crc <<= 1;
if(tmp)
crc ^= GX;
}
table = crc;
}
}
那么你得到了这么个表:
U16 table[256]=
{
0X0000, 0X1021, 0X2042, 0X3063, 0X4084, 0X50A5, 0X60C6, 0X70E7,
0X8108, 0X9129, 0XA14A, 0XB16B, 0XC18C, 0XD1AD, 0XE1CE, 0XF1EF,
0X1231, 0X0210, 0X3273, 0X2252, 0X52B5, 0X4294, 0X72F7, 0X62D6,
0X9339, 0X8318, 0XB37B, 0XA35A, 0XD3BD, 0XC39C, 0XF3FF, 0XE3DE,
0X2462, 0X3443, 0X0420, 0X1401, 0X64E6, 0X74C7, 0X44A4, 0X5485,
0XA56A, 0XB54B, 0X8528, 0X9509, 0XE5EE, 0XF5CF, 0XC5AC, 0XD58D,
0X3653, 0X2672, 0X1611, 0X0630, 0X76D7, 0X66F6, 0X5695, 0X46B4,
0XB75B, 0XA77A, 0X9719, 0X8738, 0XF7DF, 0XE7FE, 0XD79D, 0XC7BC,
0X48C4, 0X58E5, 0X6886, 0X78A7, 0X0840, 0X1861, 0X2802, 0X3823,
0XC9CC, 0XD9ED, 0XE98E, 0XF9AF, 0X8948, 0X9969, 0XA90A, 0XB92B,
0X5AF5, 0X4AD4, 0X7AB7, 0X6A96, 0X1A71, 0X0A50, 0X3A33, 0X2A12,
0XDBFD, 0XCBDC, 0XFBBF, 0XEB9E, 0X9B79, 0X8B58, 0XBB3B, 0XAB1A,
0X6CA6, 0X7C87, 0X4CE4, 0X5CC5, 0X2C22, 0X3C03, 0X0C60, 0X1C41,
0XEDAE, 0XFD8F, 0XCDEC, 0XDDCD, 0XAD2A, 0XBD0B, 0X8D68, 0X9D49,
0X7E97, 0X6EB6, 0X5ED5, 0X4EF4, 0X3E13, 0X2E32, 0X1E51, 0X0E70,
0XFF9F, 0XEFBE, 0XDFDD, 0XCFFC, 0XBF1B, 0XAF3A, 0X9F59, 0X8F78,
0X9188, 0X81A9, 0XB1CA, 0XA1EB, 0XD10C, 0XC12D, 0XF14E, 0XE16F,
0X1080, 0X00A1, 0X30C2, 0X20E3, 0X5004, 0X4025, 0X7046, 0X6067,
0X83B9, 0X9398, 0XA3FB, 0XB3DA, 0XC33D, 0XD31C, 0XE37F, 0XF35E,
0X02B1, 0X1290, 0X22F3, 0X32D2, 0X4235, 0X5214, 0X6277, 0X7256,
0XB5EA, 0XA5CB, 0X95A8, 0X8589, 0XF56E, 0XE54F, 0XD52C, 0XC50D,
0X34E2, 0X24C3, 0X14A0, 0X0481, 0X7466, 0X6447, 0X5424, 0X4405,
0XA7DB, 0XB7FA, 0X8799, 0X97B8, 0XE75F, 0XF77E, 0XC71D, 0XD73C,
0X26D3, 0X36F2, 0X0691, 0X16B0, 0X6657, 0X7676, 0X4615, 0X5634,
0XD94C, 0XC96D, 0XF90E, 0XE92F, 0X99C8, 0X89E9, 0XB98A, 0XA9AB,
0X5844, 0X4865, 0X7806, 0X6827, 0X18C0, 0X08E1, 0X3882, 0X28A3,
0XCB7D, 0XDB5C, 0XEB3F, 0XFB1E, 0X8BF9, 0X9BD8, 0XABBB, 0XBB9A,
0X4A75, 0X5A54, 0X6A37, 0X7A16, 0X0AF1, 0X1AD0, 0X2AB3, 0X3A92,
0XFD2E, 0XED0F, 0XDD6C, 0XCD4D, 0XBDAA, 0XAD8B, 0X9DE8, 0X8DC9,
0X7C26, 0X6C07, 0X5C64, 0X4C45, 0X3CA2, 0X2C83, 0X1CE0, 0X0CC1,
0XEF1F, 0XFF3E, 0XCF5D, 0XDF7C, 0XAF9B, 0XBFBA, 0X8FD9, 0X9FF8,
0X6E17, 0X7E36, 0X4E55, 0X5E74, 0X2E93, 0X3EB2, 0X0ED1, 0X1EF0
};
---------------------------------- END ------------------------------------ |
楼主
标题置顶
标题高亮
