---- --------
1011 01001101 高四位和当前记存器值
1010 11100 + (*1) Poly 放在顶部最高位进行XOR运算 (因为那里是1) -------------
0001 10101101 运算结果 现在我们仍有一位1在高4位: 0001 10101101 上一步结果
1 01011100+ (*2) Poly 放在顶部的最低位进行XOR运算 (因为那里是1) -------------
0000 11110001 第二步运算结果 ^^^^
现在顶部所有位均为0,所以我们不需要在与poly进行XOR运算
你可以得到相同的结果如果你先将(*1)与(*2)做XOR然后将结果与记存器值做XOR. 这就是标准XOR运算的特性:
(a XOR b) XOR c = a XOR (b XOR c) 由此,推出如下的运算顺序也是正确的. 1010 11100 poly (*1) 放在顶部最高位 1 01011100+ polys (*2) 放在顶部最低位 -------------
1011 10111100 (*3) XOR运算结果
The result (*3) 将(*3)与记存器的值做XOR运算 1011 10111100
1011 01001101+ 如右:
------------- 0000 11110001
你看到了吗?得到一样的结果!现在(*3)变的重要了,因为顶部为1010则(3)的值总是等于
10111100(当然是在一定的条件之下)这意味着你可以预先计算出任意顶部位结合的XOR值.
注意,顶部结果总是0,这就是组合XOR操作导致的结果.(翻译不准确,保留原文) 现在我们回到figure 1,对每一个顶部字节的值都做移出操作,我们可以预先计算出一个值.
此例中,它将是一个包含256个double word(32 bit)双字的表.(附录中CRC-32的表).
(翻译不准确,保留原文) 用伪语言表示我们的算法如下: While (byte string is not exhausted) Begin
Top = top_byte of register ;
Register = Register shifted 8 bits left ORred with a new byte from string ;
Register = Register XORred by value from precomputedTable at position Top ; End
direct table算法:
上面提到的算法可以被优化.字节串中的字节在被用到之前没有必要经过整个记村器.用
这个新的算法,我们可以直接用一个字节去XOR一个字节串通过将此字节移出记存器.结果
指向预先计算的表中的一个值,这个值是用来被记存器的值做XOR运算的. 我不十分确切的知道为什么这会得到同样的结果(这需要了解XOR运算的特性),但是这又
极为便利,因为你无须在你的字节串后填充0字节/位.(如果你知道原理,请告诉我:) 让我们来实现这个算法:
+----< byte string (or file) 字节串,(或是文件) |
v 3 2 1 0 byte 字节 | +---+---+---+---+
XOR---<| | | | | Register 记存器 | +---+---+---+---+ | | | XOR | ^
v +---+---|---+---+
| | | | | | Precomputed table 值表(用来进行操作) | +---+---+---+---+ +--->-: : : : : +---+---+---+---+
| | | | | +---+---+---+---+ (figure 2)
'reflected' direct Table 算法:
由于这里有这样一个与之相对应的'反射'算法,事情显得复杂了.一个反射的值/记存器
就是将它的每一位以此串的中心位为标准对调形成的.例如:0111011001就是1001101110 的反射串.
他们提出'反射'是因为UART(一种操作IO的芯片)发送每一个字节时是先发最没用的0位,
最后再发最有意义的第七位.这与正常的位置是相逆的.
除了信息串不做反射以外,在进行下一步操作前,要将其于的数据都做反射处理.所以在
计算值表时,位向右移,且poly也是作过反射处理的.当然,在计算CRC时,记存器也要向右
移,而且值表也必须是反射过的. byte string (or file) -->---+
| 1. 表中每一个入口都是反射的. byte 3 2 1 0 V 2. 初始化记存器也是反射的.
+---+---+---+---+ | 3. 但是byte string中的数据不是反射的, | | | | |>---XOR 因为其他的都做过反射处理了. +---+---+---+---+ |
| | XOR V ^ | +---+---|---+---+ | | | | | | | 值表 +---+---+---+---+ | : : : : : <---+ +---+---+---+---+ | | | | | +---+---+---+---+ (figure 3) 我们的算法如下:
1. 将记存器向右移动一个字节.
2. 将刚移出的哪个字节与byte string中的新字节做XOR运算, 得出一个指向值表table[0..255]的索引 3. 将索引所指的表值与记存器做XOR运算. 4. 如数据没有全部处理完,则跳到步骤1.
下面是这个算法的简单的可执行汇编源码:
完整的CRC-32标准所包含的内容: Name : \Width : 32 Poly : 04C11DB7