|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] 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
Home Last updated: Wed Nov 28 19:17:46 2001 7933 messages in chronological order |