矛与盾的较量之CRC原理篇

核心提示：如果我们想计算一个位串的CRC码，我们想确定每一个位都被处理过，矛与盾的较量之CRC原理篇(2)，因此，我们要在目标位串后面加上W个0位，这个算法的C语言描述如下：temp = (oldcrc ^ abyte) & 0x000000FF;crc= (( oldcrc >> 8) & 0x00FFFFFF)

如果我们想计算一个位串的CRC码，我们想确定每一个位都被处理过，因此，我们要在目标位串后面加上W个0位。现在让我们根据CRC的规范来改写一下上面的例子：

Poly　　　　　　　　　　=　　1001，宽度W = 3
位串Bitstring　　　　　 =　　11110
Bitstring + W zeroes　　=　　11110 + 000 = 11110000
11110000
1001||||　　-
-------------
1100|||
1001|||　　-
------------
　　　　 1010||
　　　　 1001||　　-
　　　　 -----------
　　　　 0110|
　　　　 0000|　　-
　　　　 ----------
　　　　 1100
　　　　 1001　　-
　　　　 ---------
　　　　 101　　　　--> 3，余数 --> the CRC!

还有两点重要声明如下：

1、只有当Bitstring的最高位为1，我们才将它与poly进行XOR运算，否则我们只是将Bitstring左移一位。

2、XOR运算的结果就是被操作位串Bitstring与poly的低W位进行XOR运算，因为最高位总为0。

呵呵，是不是有点头晕脑胀的感觉了？看不懂的话，再从头看一遍，其实是很好理解的。（就是一个XOR运算嘛！）

好啦，原理介绍到这里，下面我讲讲具体怎么编程。

由于速度的关系，CRC的实现主要是通过查表法，对于CRC-16和CRC-32，各自有一个现成的表，大家可以直接引入到程序中使用。（由于这两个表太长，在这里不列出来了，请读者自行在网络上查找，很容易找到的。）
　　 如果我们没有这个表怎么办呢？或者你跟我一样，懒得自己输入？不用急，我们可以“自己动手，丰衣足食”。

你可能会说，自己编程来生成这个表，会不会太慢了？其实大可不必担心，因为我们是在汇编代码的级别进行运算的，而这个表只有区区256个双字，根本影响不了速度。

这个表的C语言描述如下：

for (i = 0; i < 256; i++)
{
　　　　 crc = i;
　　　　 for (j = 0; j < 8; j++)
　　　　 {
　　　　 if (crc & 1)
　　　　 crc = (crc >> 1) ^ 0xEDB88320;
　　　　 else
　　　　 crc >>= 1;
　　　　 }
　　　　 crc32tbl[i] = crc;
}

生成表之后，就可以进行运算了。

我们的算法如下：

1、将寄存器向右边移动一个字节。

2、将刚移出的那个字节与我们的字符串中的新字节进行XOR运算，得出一个指向值表table[0..255]的索引。

3、将索引所指的表值与寄存器做XOR运算。

4、如果数据没有全部处理完，则跳到步骤1。

这个算法的C语言描述如下：

temp = (oldcrc ^ abyte) & 0x000000FF;

crc　= (( oldcrc >> 8) & 0x00FFFFFF) ^ crc32tbl[temp];

return crc;

好啦，所有的东东都说完啦，最后献上一个完整的Win32Asm例子，请读者仔细研究吧！