“手动的”CRC16CCITT(1021)的16字表长查表演算过程

2万 · 2009-10-18 22:17

本帖最后由 hotpower 于 2009-10-18 23:27 编辑

参见：CRC16CCITT(1021)的16字表长查表程序

原贴出处：https://bbs.21ic.com/icview-139615-1-1.html

hotpower发表于 2009-10-18 22:12 | 只看该作者 回复引用编辑 评分返回版面 TOP

5楼：

哈哈~~~既然大家喜欢，俺就表演个“手动的”CRC16CCITT(1021)的16字表长查表演算过程：

CRC16Table[16]={
  0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,//注意本行的0x1021
  0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
};

例如 CRC16,初值为0x0000, 求CRC16[0x1234]=0x13C6:

第1步：
CRC[0x1234>>12]=CRC[0x01]=0x1021
0x1234变为0x2340

第2步:
(0x1021<<4) ^ CRC[(0x1021>>12) ^ (0x2340>>12)]=0x0210 ^ CRC[0x01 ^ 0x02]
=0x0210 ^ CRC[0x03]=0x0210 ^ 0x3063 = 0x3273
0x2340变为0x3400

第3步:
(0x3273<<4) ^ CRC[(0x3273>>12) ^ (0x3400>>12)]=0x2730 ^ CRC[0x03 ^ 0x03]
=0x2730 ^ CRC[0x00]=0x2730 ^ 0x0000 = 0x2730
0x3400变为0x4000

第4步:
(0x2730<<4) ^ CRC[(0x2730>>12) ^ (0x4000>>12)]=0x7300 ^ CRC[0x02 ^ 0x04]
=0x7300 ^ CRC[0x06]=0x7300 ^ 0x60C6 = 0x13C6

例如 CRC16,初值为0xFFFF, 求CRC16[0x1234]=0x0EC9:

初始化: 0x1234 ^ 0xFFFF = 0xEDCB
第1步：
CRC[0xEDCB>>12]=CRC[0x0E]=0xE1CE
0xEDCB变为0xDCB0

第2步:
(0xE1CE<<4) ^ CRC[(0xE1CE>>12) ^ (0xDCB0>>12)]=0x1CE0^ CRC[0x0E ^ 0x0D]
=0x1CE0^ CRC[0x03]=0x1CE0^ 0x3063 = 0x2C83
0xDCB0变为0xCB00

第3步:
(0x2C83<<4) ^ CRC[(0x2C83>>12) ^ (0xCB00>>12)]=0xC830^ CRC[0x02 ^ 0x0C]
=0xC830 ^ CRC[0x0E]=0xC830 ^ 0xE1CE= 0x29FE
0xCB00变为0xB000

第4步:
(0x29FE<<4) ^ CRC[(0x29FE>>12) ^ (0xB000>>12)]=0x9FE0^ CRC[0x02 ^ 0x0B]
=0x9FE0^ CRC[0x09]=0x9FE0^ 0x9129= 0x0EC9

使用演算工具：http://www.hotc51.com/HotPower_HotWC3.html

或查表：
CRC16Table[16]={
  0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,//注意本行的0x1021
  0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,
};

本文可以证明菜农的脑浆是“红色的”~~~
16*2个字节“比拼”256*2个字节的结果：
循环次数是4次，而后者为2次。即速度降低1倍但空间被压缩16倍，不知菜农失败否~~~