Python – Ethernet CRC32 calculation – software vs algorithmic result

algorithmcrc32ethernetpython

I'm trying to calculate the Frame Check Sequence (FCS) of an Ethernet packet byte by byte. The polynomial is 0x104C11DB7.
I did follow the XOR-SHIFT algorithm seen here http://en.wikipedia.org/wiki/Cyclic_redundancy_check or here http://www.woodmann.com/fravia/crctut1.htm

Assume the information that is supposed have a CRC is only one byte. Let's say it is 0x03.

step: pad with 32 bits to the right

0x0300000000
align the polynomial and the data at the left hand side with their first bit that is not zero and xor them

0x300000000 xor 0x209823B6E = 0x109823b6e
take remainder align and xor again

0x109823b6e xor 0x104C11DB7 = 0x0d4326d9

Since there are no more bit left the CRC32 of 0x03 should be 0x0d4326d9

Unfortunately all the software implementations tell me I'm wrong, but what did I do wrong or what are they doing differently?

Python tells me:

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

The online tool here http://www.lammertbies.nl/comm/info/crc-calculation.html#intr gets the same result.
What is the difference between my hand calculation and the algorithm the mentioned software uses?

UPDATE:

Turns out there was a similar question already on stack overflow:

You find an answer here Python CRC-32 woes

Although this is not very intuitive. If you want a more formal description on how it is done for Ethernet frames you can look at the Ethernet Standard document 802.3 Part 3 – Chapter 3.2.9 Frame Check Sequence Field

Lets continue the example from above:

Reverse the bit order of your message. That represents the way they would come into the receiver bit by bit.

0x03 therefore is 0xC0
Complement the first 32 bit of your message. Notice we pad the single byte with 32 bit again.

0xC000000000 xor 0xFFFFFFFF = 0x3FFFFFFF00
Complete the Xor and shift method from above again. After about 6 step you get:

0x13822f2d
The above bit sequense is then complemented.

0x13822f2d xor 0xFFFFFFFF = 0xec7dd0d2
Remember that we reversed the bit order to get the representation on the Ethernet wire in step one. Now we have to reverse this step and we finally fulfill our quest.

0x4b0bbe37

Whoever came up with this way of doing it should be …

A lot of times you actually want to know it the message you received is correct. In order to achieve this you take your received message including the FCS and do the same step 1 through 5 as above. The result should be what they call residue. Which is a constant for a given polynomial. In this case it is 0xC704DD7B.

As mcdowella mentions you have to play around with your bits until you get it right, depending on the Application you are using.

Best Answer

This snippet writes the correct CRC for Ethernet.

Python 3

# write payload
for byte in data:
    f.write(f'{byte:02X}\n')
# write FCS
crc = zlib.crc32(data) & 0xFFFF_FFFF
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)

Would have saved me some time if I found this here.

Related Solutions

How to determine whether the calculation of pi is accurate

Since I'm the current world record holder for the most digits of pi, I'll add my two cents:

Unless you're actually setting a new world record, the common practice is just to verify the computed digits against the known values. So that's simple enough.

In fact, I have a webpage that lists snippets of digits for the purpose of verifying computations against them: http://www.numberworld.org/digits/Pi/

But when you get into world-record territory, there's nothing to compare against.

Historically, the standard approach for verifying that computed digits are correct is to recompute the digits using a second algorithm. So if either computation goes bad, the digits at the end won't match.

This does typically more than double the amount of time needed (since the second algorithm is usually slower). But it's the only way to verify the computed digits once you've wandered into the uncharted territory of never-before-computed digits and a new world record.

Back in the days where supercomputers were setting the records, two different AGM algorithms were commonly used:

These are both O(N log(N)^2) algorithms that were fairly easy to implement.

However, nowadays, things are a bit different. In the last three world records, instead of performing two computations, we performed only one computation using the fastest known formula (Chudnovsky Formula):

This algorithm is much harder to implement, but it is a lot faster than the AGM algorithms.

Then we verify the binary digits using the BBP formulas for digit extraction.

This formula allows you to compute arbitrary binary digits without computing all the digits before it. So it is used to verify the last few computed binary digits. Therefore it is much faster than a full computation.

The advantage of this is:

Only one expensive computation is needed.

The disadvantage is:

An implementation of the Bailey–Borwein–Plouffe (BBP) formula is needed.
An additional step is needed to verify the radix conversion from binary to decimal.

_{I've glossed over some details of why verifying the last few digits implies that all the digits are correct. But it is easy to see this since any computation error will propagate to the last digits.}

Now this last step (verifying the conversion) is actually fairly important. One of the previous world record holders actually called us out on this because, initially, I didn't give a sufficient description of how it worked.

So I've pulled this snippet from my blog:

N = # of decimal digits desired
p = 64-bit prime number

Compute A using base 10 arithmetic and B using binary arithmetic.

If A = B, then with "extremely high probability", the conversion is correct.

For further reading, see my blog post Pi - 5 Trillion Digits.

R – Logging requests/responses in a WCF REST service

Notice that if you want to intercept the raw message, and not the parameters, you can inject your implementation of IDispatchMessageInspector instead of the IParameterInspector extension point that Dani suggests.