Computer Interfacing
Discussions about interfacing and electronics
 

crc32 simpliest understanding


 

       Computer Interfacing Forum Index -> Error detection and correction
Author Message
wanderer
Guest







Apr 11, 2014 7:00 am

Hello!

I'm not very interested in theory, but in practice.
I've studied a few papers about the topic and was aiming to come to implementation, but was stoped with some misunderstanding in the very begining.
I've started from just a bundle of zeros and found that I can't see how it worked (I mean on-line calculators results).
Even more, I thought that if we take less than 32-bit word it must add zeros, so the result mest be the same when input data is 1,2,3 or 4 bytes of zeros, but it's different. How could it be.

Please, does someone explain just every step how:
1. 00 turns to 0xD202EF8D
2. 0000 turns to 0x41D912FF
3. 000000 turns to 0xFF41D912
4. 00000000 turns to 0x2144DF1C

Thanks in forward!
Gammatester
Guest







Apr 14, 2014 6:50 am

If you are not very interested in theory, but in practice, then just accept the found facts and a step by step explanation makes no sense. Just two points without much theory:

There are CRC32 algorithms where leading zeroes do not contribute to the CRC32 (e.g. CRC32/Q or CRC32/XFER).

Basically a CRC32 is the remainder from the polynomial division of the message (prefixed by a 32-bit constant) by the CRC polynomial. If the prefix constant (the init value) is zero, then all messages consisting of zeros only will give the same remainder value, like division with remainder for normal numbers: 0 mod 7 = 0, 00 mod 7 = 0 etc. With a non-zero initial prefix value the remainder changes, for standard division and prefix 11 for example: 110 mod 7 = 5, 1100 mod 7 = 1, 11000 mod 7 = 3. (For the CRC32/Zip from the online calculator the prefix is 32 bits 1.)
wanderer
Guest







Apr 21, 2014 8:09 pm

Thanks!
No, I caught the theory in basic. I just can't do crc-division in program - that I meant... but no matter.

Yes, I've already found that it must be initial value and for crc32 it is 0xffffffff.
I've also found that I have to reverse (reflect) bits before outing XOR with 0xffffffff.

With any number of zeros I am OK now. Today it's another problem. Firstly, after making it with zeros, I tried to add a single bit of 1 and it failed again ((

Now I am going from another side - all 1s. And some mysteries again.

I've found from on-line calc, that 1s until 32 bits produce themselves with adding zeros:
0xff - 0xff000000 ...
0xffffffff - 0xffffffff.
It already breaks the rules as I see them because to get such result I must XOR the initial 0xffffffff with this short message (OK, may be I should have done it with 0s), but then I have to put only zeros... why? where must I leave those 1s?

Then it's even more paradoxical. If I want to crc the message of all 1s which has more than 32 bits, the only way I've found to get the correct result is to put into processing all 1s and not do XOR out with 0xffffffff. Again why?

I just can't catch the idea how to combine those "features" into one universal algorithm.

There is something I miss, didn't catch or misunderstand, so need help...

I reference with online calculator because the results it gives match my needs (I need crc32 for png encoding).

As I understand the practical algorithm, it looks so:
1. Initializing register with all 1s.
2. (?) XOR it with message or some part of it. I didn't find such step in ŤA Painless Guide to CRC Error Detection Algorithmsť, but I don't see how to get right results with message of 1s (according online calculator).
3. Shift one bit left.
4. Place the next message's bit (the lowest one first) to the right side of register.
5. If shifted bit was 1, than XOR register with polynom value 0x04C11DB7.
6. Do steps 3-5 until the end of the message.
7. Reflect register bits.
8. XOR out register with 0xffffffff.

But it doesn't work right this way. I've cracked my mind trying to gather all things together, but still far from finish.
Guest








May 02, 2014 12:23 pm

At last, I've got the reciept.

Share it with anyone, who need it:
1. Take first 4 bytes from message (if it less than 4 byte - add zeros). May be you will need to reflect bits in EVERY byte (I have to, but I think it depends on particular architecture). Put it into Register (uint).
2. Make Register XOR 0xFFFFFFFF.
3. Shift one bit left.
4. Place the next message's bit (the lowest one first) to the right side of Register.
5. If shifted bit was 1, than Register XOR 0x04C11DB7.
6. Do steps 3-5 until the end of the message.
7. Do steps 3-5 for 32 bits of zeros (if the message is less than 32 bits, than this number must correspond with input length).
7. Reflect bits in the whole Register.
8. Make Register XOR 0xffffffff.

That's it - you have the CRC32, which all online calculators show and, at least, correct for deflate, PNG, etc.

       Computer Interfacing Forum Index -> Error detection and correction
Page 1 of 1



Running on php BB © 2001, 2009 php BB Group
   Lammert Bies     Interfacing     Sitemap     Forum