以太网CRC32计算-软件与算法结果比较

Question

我正在尝试逐字节计算以太网数据包的帧检验序列（FCS）。使用的多项式是 0x104C11DB7。我参考了这里的异或移位算法 http://en.wikipedia.org/wiki/Cyclic_redundancy_check 或者这里 http://www.woodmann.com/fravia/crctut1.htm

假设要计算CRC的信息只有一个字节。我们假设这个字节是 0x03。

1. 第一步：在右边补充32位的零

   0x0300000000

2. 将多项式和数据的第一个非零位对齐到左边，然后进行异或运算

   0x300000000 xor 0x209823B6E = 0x109823b6e

3. 取余数，再次对齐并进行异或运算

   0x109823b6e xor 0x104C11DB7 = 0x0d4326d9

由于没有剩余的位，0x03 的 CRC32 应该是 0x0d4326d9

不幸的是，所有的软件实现都告诉我我错了，那我到底哪里出错了，或者他们有什么不同的做法呢？

Python 告诉我：

 "0x%08x" % binascii.crc32(chr(0x03))
 0x4b0bbe37

这里的在线工具 http://www.lammertbies.nl/comm/info/crc-calculation.html#intr 得到了相同的结果。我的手动计算和这些软件使用的算法有什么区别呢？

更新：

结果发现 Stack Overflow 上已经有类似的问题：

你可以在这里找到答案 Python CRC-32 woes

虽然这并不是很直观。如果你想要更正式的描述以太网帧是如何处理的，可以查看 以太网标准文档 802.3 第3部分 - 第3.2.9节 帧检验序列字段

让我们继续上面的例子：

1. 反转消息的位顺序。这代表它们是如何逐位进入接收器的。

   0x03 因此变成 0xC0

2. 对消息的前32位进行补码。注意我们再次用32位补充这个单字节。

   0xC000000000 xor 0xFFFFFFFF = 0x3FFFFFFF00

3. 再次完成上面的异或和移位方法。经过大约6步，你会得到：

   0x13822f2d

4. 上面的位序列再进行补码。

   0x13822f2d xor 0xFFFFFFFF = 0xec7dd0d2

5. 记住我们在第一步反转了位顺序以获得以太网线上的表示。现在我们需要反转这一步，最终完成我们的任务。

   0x4b0bbe37

谁想出这种做法的真是...

很多时候，你实际上想知道你收到的消息是否正确。为了实现这一点，你需要将收到的消息（包括FCS）进行同样的步骤1到5。结果应该是他们所称的余数。对于给定的多项式，这是一个常量。在这种情况下是 0xC704DD7B。

正如 mcdowella 提到的，你需要不断调整你的位，直到得到正确的结果，这取决于你使用的应用程序。

Answer 1

在网上有很多地方提到，在计算FCS之前，位的顺序必须反转，但802.3的规范并没有这样要求。引用2008年版本的规范：

3.2.9 Frame Check Sequence (FCS) field

A cyclic redundancy check (CRC) is used by the transmit and receive algorithms to
generate a CRC value for the FCS field. The FCS field contains a 4-octet (32-bit)
CRC value. This value is computed as a function of the contents of the protected
fields of the MAC frame: the Destination Address, Source Address, Length/ Type 
field, MAC Client Data, and Pad (that is, all fields except FCS). The encoding is
defined by the following generating polynomial.

  G(x) = x32 + x26 + x23 + x22 + x16 + x12 + x11 
             + x10 + x8 + x7 + x5 + x4 + x2 + x + 1

Mathematically, the CRC value corresponding to a given MAC frame is defined by 
the following procedure:

a) The first 32 bits of the frame are complemented.
b) The n bits of the protected fields are then considered to be the coefficients
   of a polynomial M(x) of degree n – 1. (The first bit of the Destination Address
   field corresponds to the x(n–1) term and the last bit of the MAC Client Data 
   field (or Pad field if present) corresponds to the x0 term.)
c) M(x) is multiplied by x32 and divided by G(x), producing a remainder R(x) of
   degree ≤ 31.
d) The coefficients of R(x) are considered to be a 32-bit sequence.
e) The bit sequence is complemented and the result is the CRC.

The 32 bits of the CRC value are placed in the FCS field so that the x31 term is
the left-most bit of the first octet, and the x0 term is the right most bit of the
last octet. (The bits of the CRC are thus transmitted in the order x31, x30,..., 
x1, x0.) See Hammond, et al. [B37].

当然，帧中的其他位是以反向顺序传输的，但这不包括FCS。再次引用规范：

3.3 Order of bit transmission

Each octet of the MAC frame, with the exception of the FCS, is transmitted least
significant bit first.

Answer 2

在计算CRC（循环冗余校验）时，通常需要一些反复尝试才能让计算结果一致，因为你总是无法准确找到需要做什么。有时候你需要反转输入的字节或者多项式，有时候你需要从一个非零的值开始，等等。

一种避免这些麻烦的方法是查看一个已经正确实现CRC计算的程序的源代码，比如http://sourceforge.net/projects/crcmod/files/（至少它声称是正确的，并且附带了单元测试来验证这一点）。

另一种方法是自己动手尝试实现。比如，如果我使用http://www.lammertbies.nl/comm/info/crc-calculation.html#intr上的计算器，我可以看到输入00000000会得到CRC值0x2144DF1C，而输入FFFFFFFF则得到FFFFFFFF——所以这并不是你描述的多项式除法，因为在那种情况下，0的校验和应该是0。

从快速浏览源代码和这些结果来看，我认为你需要从CRC值0xFFFFFFFF开始——但我可能错了，你可能需要在调试你的代码时，和这个实现并行对比，使用相应的打印语句找出第一个不同的地方，然后逐个修正这些差异。

Answer 3

这个代码片段可以生成以太网的正确CRC值。

Python 3

# write payload
for byte in data:
    f.write(f'{byte:02X}\n')
# write FCS
crc = zlib.crc32(data)
for i in range(4):
    byte = (crc >> (8*i)) & 0xFF
    f.write(f'{byte:02X}\n')

Python 2

# write payload
for byte in data:
    f.write('%02X\n' % ord(byte))
# write FCS
crc = zlib.crc32(data) & 0xFFFFFFFF
for i in range(4):
    byte = (crc >> (8*i)) & 0xFF
    f.write('%02X\n' % byte)

如果我早一点在这里找到这个，肯定能省不少时间。