RE: CRC32C code -- please check

["THALER,PAT (A-Roseville,ex1)" <pat_thaler@agilent.com>]

Luben,

I think I see the problem:

Luben> Ok, so the receiver got M''(x) assuming no noise.

 Luben> M''(x) = Q(x)*G(x) + I(x).  (this is (3))

 Luben> Now we work the algorithm again: ..., find the remainder:
 Luben> Clearly, from (3) the remainder of M''(x) modulo G(x) is I(x).
                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                          this is not true.

 Luben> Then we complement the value as per the draft:

 Luben> ~I(x) = 0.

 Luben> And we end up with remainder 0.

Remember I(x) is the polynomial of order 31 with all the coefficients equal
to 1. G(x) is a polynomial of order 31 with some of its coefficients equal
to 0. Therefore, G(x) goes into I(x) once.

The remainder of M''(x) modulo G(x) is I(x) - G(x).

So that should explain the "magic number."

Regards,
Pat


-----Original Message-----
From: Paul Koning [mailto:ni1d@arrl.net]
Sent: Monday, November 26, 2001 7:12 AM
To: ltuikov@yahoo.com
Cc: ips@ece.cmu.edu
Subject: Re: CRC32C code -- please check


>>>>> "Luben" == Luben Tuikov <ltuikov@yahoo.com> writes:

 Luben> Here is some C code at the end, the draft quoted and my notes
 Luben> alongside it. ...

 Luben> So, here we get M'(x) = x^32 * M(x). Getting R(x) is trivial.
 Luben> So we have:

 Luben> M'(x) = Q(x)*G(x) + R(x) = Q(x)*G(x) - R(x), (1)

 Luben> since plus is same as minus in modulo 2 arithmetic.

 >> - the bit sequence is complemented and the result is the
 Luben> CRC

 Luben> Now, from boolean logic we know that b XOR 1 = ~b, then,

 Luben> ~R(x) = R(x) XOR I(x) = R(x) + I(x) (2)

 Luben> where I(x) is a polynomial of the same degree as R(x) and
 Luben> whose coefficients are all equal to 1. So, to get M''(x) which
 Luben> we send we have:

 Luben> M''(x) = M'(x) + ~R(x) (draft) = Q(x)*G(x) - R(x) + R(x) +
 Luben> I(x) (using (1) and (2)) = Q(x)*G(x) + I(x).

 Luben> or succinctly,

 Luben> M''(x) = Q(x)*G(x) + I(x), (3)

 Luben> and this is the message which we send. 

Not quite.  Your M' is taken from M by complementing the first 32
bits and appending 32 zeroes.  That's what you feed into the CRC
calculation -- but what you transmit has the original (uncomplemented)
first 32 bits.

 Luben> On the other end we
 Luben> get M''(x), assuming there was no noise, and all
 Luben> link/TCP/Ethernet transformations are transparent for the
 Luben> sender and the receiver. ...

 Luben> Ok, so the receiver got M''(x) assuming no noise.

 Luben> M''(x) = Q(x)*G(x) + I(x).  (this is (3))

 Luben> Now we work the algorithm again: ..., find the remainder:
 Luben> Clearly, from (3) the remainder of M''(x) modulo G(x) is I(x).

 Luben> Then we complement the value as per the draft:

 Luben> ~I(x) = 0.

 Luben> And we end up with remainder 0.

I think I see the problem.

In CRC generation, you process the message (M).

In CRC checking, there are two approaches:

1. You process M and compare the 4 bytes that follow (the CRC) with
what you computed.  This is fine, if you know ahead of time where M
ends. 

2. If you don't know where M ends ahead of time (as in the Ethernet
MAC layer) or you simply prefer to process the whole received message,
you run everything including the received CRC through the CRC
algorithm.  Note that the string processed in this case is 4 bytes
longer than in case (1), because it includes the CRC.  That's what you
described, but I believe you missed a step.

The CRC algorithm says: take the message (M'' in this case) and
multiply by x^32, then divide by the CRC polynomial.  You missed the
multiply.   In other words, you should have:

	    (M''(x)*x^32) mod G(x)
rather than simply
            M''(x) mod G(x)

and that is *not* zero.  I haven't done the math but I expect that you
will find the answer to be the non-zero constant that appears in the
spec. 

Ethernet works the same way, except for a change in the polynomial.
You suggested earlier that Ethernet is using a non-standard algorithm
because it comes up with a non-zero remainder at the receive end.
That is not the case.

You should not need any fudge factors to make the answer come out
according to the spec if you get the algorithm right...

	  paul