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

Question

我想逐字节计算以太网数据包的帧校验序列（FCS）。多项式是0x104C11DB7 。

我尝试了在这里http://en.wikipedia.org/wiki/Cyclic_redundancy_check或者在这里http://www.woodmann.com/fravia/crctut1.htm看到的XOR-SHIFT算法。

假设需要进行CRC校验的信息仅为一个字节。让我们假设它是0x03。

1. 步骤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与我手算得到的结果相同。提到的软件算法与我的手算有何区别？

更新: 原来在stackoverflow上已经有了类似的问题： 你可以在此处找到答案 Python CRC-32 woes 虽然这并不是非常直观。如果您想要一个更正式的描述，关于以太网帧的方法是如何完成的，请参考 Ethernet Standard document 802.3 Part 3 - Chapter 3.2.9 Frame Check Sequence Field

继续以上面的例子为例:

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 所提到的，您必须根据您使用的应用程序来调整比特，直到您正确地得到结果。

- sebs

---

0x209823B6E 是从哪里来的？ - grieve

你是否将初始余数设置为0xFFFFFFFF？ - grieve

0x209823B6E 是多项式的移位版本，以便与数据对齐。 - sebs

@sebs，移位是如何实现的？ - cp.engr

@cp.engr 左移一位。 (0x104C11DB7 << 1) - sebs

Answer 1

这段代码用于计算以太网的正确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)

如果我能在这里找到这个内容，那就可以节省我的时间了。

- maxy

---

这节省了我数小时的痛苦。谢谢，谢谢。 - dinkelk

谢谢这段代码，帮了我很多忙。为什么要将zlib.crc(data)与f进行and操作呢？crc已经是一个32位的整数，因此与32位的“1”进行and操作将返回相同的结果，无论zlib.crc32(data)返回1还是2^32-1。虽然这不是什么大问题，但它让我有点困惑。谢谢。 - Michael Grover

在Python3中不需要，谢谢你指出来。(我已经编辑了答案。) 在Python2中结果可能为负数：https://docs.python.org/3/library/zlib.html#zlib.crc32 - maxy

Answer 2

通常需要一些试错才能使CRC计算匹配，因为你永远不会完全读懂要做什么。有时候你需要反转输入字节或多项式，有时候你需要从非零值开始等等。

绕过这个问题的方法之一是查看一个正确计算CRC的程序的源代码，例如http://sourceforge.net/projects/crcmod/files/（至少它声称匹配，并带有此项的单元测试）。

另一种方法是玩弄实现。例如，如果我使用http://www.lammertbies.nl/comm/info/crc-calculation.html#intr上的计算器，我可以看到给它00000000会产生0x2144DF1C的CRC，但给它FFFFFFFF会产生FFFFFFFF - 所以它不完全是你描述的多项式除法，其余部分的校验和应该是0。

从快速浏览源代码和这些结果来看，我认为你需要从0xFFFFFFFF开始进行CRC - 但我可能错了，你可能需要与实现一起调试代码，使用相应的printf找出第一个差异，并逐个修复差异。

- mcdowella

Answer 3

在互联网上，有很多地方会说在计算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.

- Daniel Wisehart

---

这只是默认情况下，“第一个比特”和“最后一个比特”指的是传输顺序 - 由于这个原因，它们并没有说“最高有效位”或“最低有效位” :) - hobbs

该标准描述了CRC32 BZIP2，它是一种左移的CRC算法，并首先以最低位优先方式传输数据，但FCS的最高位（第31位）优先。另一种选择是使用右移的CRC32，这会导致CRC成为FCS的位反转，在此之后，数据和CRC都可以按最低有效位发送，从而实现相同的传输。该标准还提到，接收方应将其计算出的FCS与接收到的FCS进行比较，但另一种选择是在数据+FCS上生成CRC，从而得到一个取决于实现的固定非零值。 - rcgldr

Answer 4

循环冗余校验

包含以太网数据和大量重要细节，例如将多项式编码为32位值有（至少）两种约定：从最高项开始或从最低项开始。

- Dima Tisnek