1

I'm looking for a good checksum for short binary data messages (3-5 bytes typical) on a microcontroller. I would like something that detects the kinds of errors that can sometimes happen on an SPI bus, for example off-by-ones and repeats ("abc" -> "bcd", and "abc"->"aab"). Also it should catch the edge cases of all-zeros, all-ones and all-same-value. The checksum can add 2-4 bytes.

Running speed is not as critical as this will not process very much data; but code size is somewhat important.

Alex I
  • 19,689
  • 9
  • 86
  • 158
  • 1
    For that size, the easiest solution would be to send the message twice, and request retransmission if the two don't match. – Sneftel May 15 '15 at 00:23
  • 1
    @Sneftel: I thought about it. But a single off-by-one error can mess up both messages: "abaaba" -> "aabaab". I would like something that (somewhat like a crypto hash) flips half the bits in a way that doesn't have a simple pattern. – Alex I May 15 '15 at 00:43
  • Maybe you can do something like this checksum_byte = (data[0] * 11 + data[1] * 11^2 + data[2] * 11^3 ....) % 255;. Then send checksum_byte + data? – invisal May 15 '15 at 01:20

2 Answers2

3

I ended up using CRC16 CCITT. This is only ~50 bytes of compiled code on the target system (not using any lookup tables!), runs reasonably fast, and handles all-zero and all-one cases pretty decently.

Code (from http://www.sal.wisc.edu/st5000/documents/tables/crc16.c):

unsigned short int
crc16(unsigned char *p, int n)
{
    unsigned short int crc = 0xffff;

    while (n-- > 0) {
        crc  = (unsigned char)(crc >> 8) | (crc << 8);
        crc ^= *p++;
        crc ^= (unsigned char)(crc & 0xff) >> 4;
        crc ^= (crc << 8) << 4;
        crc ^= ((crc & 0xff) << 4) << 1;
    }

    return(crc);
}
Alex I
  • 19,689
  • 9
  • 86
  • 158
  • 1
    Pretty sure this code is wrong - where the heck is the polynomial? Proper code for CRC-16 CCITT is here: https://people.cs.umu.se/isak/snippets/crc-16.c – bryc Mar 18 '19 at 17:07
  • 2
    Correction: This is not CRC-16/CCITT, but it's actually [CRC-16/CCITT-FALSE](https://gist.githubusercontent.com/tijnkooijmans/10981093/raw/crc16.c). So it's still a valid CRC-16 variant. But wow.. what is this black magic?! Somehow the polynomial is _baked_ into the shifts and is extremely efficient (although it cannot be easily converted to other CRC variants). [This version](https://stackoverflow.com/a/23726131/815680) is the same, but possibly even more efficient. – bryc Mar 18 '19 at 19:18
1

See http://pubs.opengroup.org/onlinepubs/009695299/utilities/cksum.html for the algorithm used by cksum, which is itself based on the one used within the ethernet standard. Its use within ethernet is to catch errors that are similar to the ones that you face.

That algorithm will give you a 4 byte checksum for any size of data that you wish.

btilly
  • 43,296
  • 3
  • 59
  • 88