Debugging checksum calculations

Introduction

CRC:s are notoriously tricky to get exactly right. You have either processed the exactly right byte sequence in exactly the right order, or you have not. One problem with a typical crc-algorithm is that there is no way to see that you are getting closer to the answer.

If you are supposed to checksum 0x1000-0x3FFF with the polynomial 0x1021 and you actually checksum 0x0100-0x3FFF with the polynomial 0x1201 you will get a different result. Then you discover one of the two errors and get a new result, that is also incorrect but there is no indication that the result is closer to what you want, it does not match, and that is all the information you will get.

A list of common pitfalls and how to handle them is presented below.

1. Verify that the external checksum's range and what the program checksums match

The tool that generates the checksum should report what range was used to generate that checksum. Both IAR XLINK linker and the ielftool tool supplies this information. If the reported range is, say, 0x40-0x3FFB,0x4000-0x7FFF, you need to checksum those exact bytes, not 0x40-0x7FFF or any other variant, you need to make sure that the bytes on addresses 0x3FFC-0c3FFF are excluded from the crc.

2. Verify that the checksums use the same polynomial

Two checksums that use different polynomials on the same checksum range will not match. CRC-16 has the polynomial value 0x1021, it is really 0x11021 but the most significant 1 does not fit in 16 bits and it is usually dropped. The same is true for other standardized crc-values, bit X in an X-bit polynomial is set and not included in the polynomial's X-bit representation as it does not fit (bit 0 to bit X needs X+1 bits so bit X does not fit in X bits).

Sometimes the polynomial is expressed as a traditional mathematical polynomial, x to the power of something + x to a lesser power, etc. In such cases the polynomial can be translated to the corresponding hexadecimal number by using the exponent of each x as the bit index and set that bit to 1. Example: x ^ 16 + x ^ 12 + x ^ 5 + 1. This uses bit 16, 12, 5 and 0. 0x10000 + 0x1000 + 0x20 + 0x1 = 0x11021 = 0x1021 = CRC-16

3. Verify that the checksums view reflection/mirroring the same way

Reflection/mirroring is sometimes used by crc-algorithms. Mirroring/reflection is achieved by reversing the order of bits in a byte.

Examples:
mirror(0x1) = 0x80
mirror(0x17) = 0xE8
mirror(0xE2) = 0x47
mirror(mirror(x)) = x

If one checksum use reflection and the other does not, the checksums will typically not match (a byte sequence can contain bytes who’s bit sequence is a palindrome) as the crc algorithms effectively see different byte sequences. Reflection/mirroring is usually handled through a mirroring table, a 256-byte array where each index’s byte contains the index’s reverse. The crc-code then looks the byte up in a mirror table and use the table entry instead of the byte for the crc-calculation.

One problem with mirroring/reflection is that those that use it might not know that they are using it. The easiest way to test if reflection/mirroring is used is to try both variants and see if either result matches.

4. Possibly feed additional bytes into the algorithm

If you are not using a table driven algorithm you typically need to process additional 0-bytes after the byte sequence has been handled. One 0-byte is needed for each byte in the checksum symbol. If you are using a table driven algorithm there is no need for additional bytes. See "A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS" by Ross N. Williams, for more information.

5. Make sure that you read bytes from the correct address space

Note: This only matters if the processor has more than one address space.

Processing the right address ranges, but in the wrong address space can be one source of error. Make sure that the pointer that the crc-algorithm uses is of the right type, the pointer used must point to the correct address space. You might have to add a memory specifier to the pointer declaration, something like this:

typedef __code unsigned char * CodePtr;

uint16_t
crc(uint16_t sum, CodePtr p, uint32_t len)
{
 .
 .
 .
}

6. Be careful when using "small" pointers in "big" ranges

Note: This only matters if there are several types of pointers where at least one can address less memory than at least one other pointer.

If you are using a pointer that cannot reach the entire memory (typically a __near pointer on a system that has more than 64k of addressable memory) you will run into problems when you reach the last address. If a 16-bit pointer has the value 0xFFFF, incrementing it will result in 0x0, not 0x10000. The end result is of course that the wrong bytes will be checksummed.

If you want to checksum 0x4000-0x27FFF you should use a pointer can that can reach all the addresses, just incrementing and dereferencing a small pointer 0x24000 times is not enough. Using a __near pointer that starts on 0x4000 will result in the range 0x4000-0XFFFF,0x0-0xFFFF,0x0-0x7FFF being checksummed, not the expected 0x4000-0x27FFF. Typically a __far or __huge pointer is sufficient. It might be possible to use a __near pointer and handle the switching at 0x10000 and 0x20000 in some other way, but using a larger pointer tends to be safer.

Regardless, the fact that you want checksum more than 64k bytes means that you will need to handle the crossing of 64k boundaries in some way.

7. Start small

If possible, start with a small example when trying to get checksums to match. A single byte is the easiest to handle in many ways, in the table driven version it is a single lookup, in the classic version it is a single iteration of the bit manipulations. There are no boundary crossings and it is usually easy to check that both checksums use the same byte value.

If the polynomial, the initial value, the mirroring/reflection approach and the address space is the same, the checksum will be the same, but in some cases the final checksum is XOR:ed with a value or it can be 1's or 2's complemented.

Once the 1-byte checksum matches you can extend the checksum to cover a few more bytes. This is to minimize the risk that the single byte you used had some special property that made the checksums match by coincidence (for instance 0 does not detect a mismatch in the view on reflection). If the multi byte checksum does not match, but the single byte does go back to the single byte checksum but use a different byte.

Once the slightly larger example matches you should try the entire range. If the small example matches, but the larger does not, you should look into page boundary problems (crossing a 16-bit address boundary), the location of checksums (checksums are typically excluded from checksums) or if any addresses can have unexpected content (such addresses should not be checksummed).

8. Special cases

There are, of course, special cases where the standard approach (a char pointer which reads each byte between 2 addresses) does not work "out of the box". In cases like that it might be necessary to use assembler help routine to access the bytes in the expected order.

It can also be helpful to use a different fill pattern. Many use the fill pattern 0xFF. If the architecture always reads every fourth byte as a 0 (some architectures use a "ghost byte") the checksums will never match as one checksum (the one generated from the object file) will use 0xFF for the ghost bytes while the one that actually reads bytes on the hardware will use 0x0 for the ghost bytes. In this case using the fill string 0xFFFFFF00 (and making sure that fills start on a 4-byte aligned address) will make sure that the different checksum algorithms see the same bytes.

If the checksum range contains bytes that have unpredictable content (for whatever reason) such bytes should be excluded from the checksum.

All product names are trademarks or registered trademarks of their respective owners.