I'm writing an embedded application on an ARM7 processor and I need some form of checksum for data that I'm sending over a serial link as well for data that I'm storing in the flash. I was wondering which of the two CRCs would be better suited for the purpose. The main trade-off are code speed versus robustness. Should I consider another CRC? Do you have a link to an efficient implementation for ARM?
views:
743answers:
5
+2
A:
Take the best checksum you can afford in the situation. Flashing might not be done often, so the flash-checksum can be more sophisticated than the one for the serial communication.
Additional checksums I have in mind:
- CRC32
- MD5
- SHA1
but this depends entirely on the application you are doing and the harm that can be done if you don't detect an error.
Take a look here for more input: http://en.wikipedia.org/wiki/List_of_checksum_algorithms
Tobias Langner
2009-07-28 14:56:22
CRC also allows for error correction, MD5 and SHA1 are specifically designed not to allow for error correction. They are also quite a bit slower to calculate (several times on most hardware). I would always suggest CRC for stream data integrity checks, cryptographic ones should only really be needed when it is truly important not to be able to find a collision if you aren't needing to code against man in the middle attacks or authentication mechanisms (e.g. computer -> device over USB cable) then a CRC should be fine.
ewanm89
2009-07-28 15:03:56
Also to note, CRC32 is standard in a lot of things now including ethernet. Even embedded machines can handle it rather quickly these days.
ewanm89
2009-07-28 15:11:56
MD5/SHA1/etc are for cryptographic data integrity e.g. to detect tampering. CRC is just for transmission integrity which is probably what the OP wants.
Jason S
2009-07-28 16:07:36
actually - MD5, SHA1 etc. can detect any types of changes. They can't correct them though. Since MD5 for example uses more bits, any change will be more likely not to create a colision. If you have the bandwidth, you can use it to detect transmission errors (like ms did with the windows 7 isos).
Tobias Langner
2009-07-29 06:01:50
Sure, MD5, SHA1 can detect changes. But being designed for cryptographic purposes, they're overkill (more CPU cycles than necessary) for non-malicious error detection.
Craig McQueen
2009-07-31 01:00:36
+2
A:
CRC32 is relatively cheap and quick to implement. There's a reputable and efficient implementation in the PNG sample code on W3C's website (cost=1Kbyte RAM for table & it can be generated easily w/o needing EEPROM resources). You can tradeoff table memory size for calculation time if you look out there for other CRC implementations.
Jason S
2009-07-28 16:10:47
+2
A:
Flash data is likely something you don't want to be corrupted, so crc is good. The other part is a serial protocol. Given the slow speed of serial link, you should go with a crc. ARM7 chip can handle ethernet checksuming at speed much higher than the speed of a serial link, so code speed should not be a problem, and you will get a huge increase in robustness.
shodanex
2009-07-28 16:27:52
+2
A:
RFC1071 is a simple 16-bit sum of pairs of bytes. As such, it's possible that two errors could "cancel out", and still give a "pass" checksum. E.g. a bit error flips a bit from 1 to 0. Then another bit error 16 bits later flips a bit from 0 to 1. RFC1071 will not detect this. But the same double-bit-flip error, if being checked with a CRC, would be detected.
This sort of double-bit-flip error is possible in a serial transmission. (It is much more likely on a parallel cable especially if one wire is "noisy" but who uses parallel these days?) It's also possible in a Flash chip, especially if the PCB has a bad solder joint between micro and Flash chip. Overall, a CRC is statistically more robust at detecting errors because a single bit change in the input affects multiple bits in the CRC shift register.
In practice the other thing that's likely, that you want to detect, is an incomplete Flash upload, so a large chunk of the code is simply missing. For that, statistically a checksum is probably fine but I've always favoured a CRC in projects I've worked on. With a table-based CRC algorithm, we've been able to get the calculation speeds required.
Craig McQueen
2009-07-31 01:20:23
A:
For things like flash memory or (especially) OTP, it's often good to have both something like a CRC which will do a good job of catching random combinations of errors, and a one's-complement checksum which is long enough not to overflow. The latter will have the advantage that any combination of errors which includes only erroneously-set bits or includes only erroneously-cleared bits will be detected.
supercat
2010-08-23 23:21:35