CRC16 checksum: HCS08 vs. Kermit vs. XMODEM

Question

I'm trying to add CRC16 error detection to a Motorola HCS08 microcontroller application. My checksums don't match, though. One online CRC calculator provides both the result I see in my PC program and the result I see on the micro.

It calls the micro's result "XModem" and the PC's result "Kermit."

What is the difference between the way those two ancient protocols specify the use of CRC16?

Kathrynekathy

Answer 1

you can implement 16 bit IBM, CCITT, XModem, Kermit, and CCITT 1D0F using the same basic code base. see http://www.acooke.org/cute/16bitCRCAl0.html which uses code from http://www.barrgroup.com/Embedded-Systems/How-To/CRC-Calculation-C-Code

the following table shows how they differ:

name    polynomial  initial val  reverse byte?  reverse result?  swap result?
CCITT         1021         ffff             no               no            no
XModem        1021         0000             no               no            no
Kermit        1021         0000            yes              yes           yes
CCITT 1D0F    1021         1d0f             no               no            no
IBM           8005         0000            yes              yes            no

where 'reverse byte' means that each byte is bit-reversed before processing; 'reverse result' means that the 16 bit result is bit-reversed after processing; 'swap result' means that the two bytes in the result are swapped after processing.

all the above was validated with test vectors against http://www.lammertbies.nl/comm/info/crc-calculation.html (if that is wrong, we are all lost...).

so, in your particular case, you can convert code for XModem to Kermit by bit-reversing each byte, bit reversing the final result, and then swapping the two bytes in the result.

[i believe, but haven't checked or worked out the details, that reversing each byte is equivalent to reversing the polynomial (plus some extra details). which is why you'll see very different explanations in different places for what is basically the same algorithm.

also, the approach above is not efficient, but is good for testing. if you want efficient the best thing to do is translate the above to lookup-tables.]

edit what i have called CCITT above is documented in the RevEng catalogue as CCITT-FALSE. for more info, see the update to my blog post at the link above.

Habitable

In your link you mention being able to generate the lookup table based on the information above. How can that be done? Also, is there any correlation between the way you're using the phrase "reverse" and the way this article is using it? danielvik.com/2010/10/calculating-reverse-crc.html His are all implemented with the look up table approach so I'm struggling to see the differences/commonalities if there are any. Thanks. – Slr

@Slr NO - that article is doing something very weird which is very very unlikely to be what you want. it's calculating what text should be added to something so that the CRC comes out with a certain value. // you would use the code above to generate a lookup table by rewriting it so that the same logic is applied in a loop to the values 0 to 255, and then those values are saved and used later to replace the "inner loop" of the crc algorithm. – Habitable

ps if you're not sure how to convert to a table, are you sure you need to? i use the code i gave in a deployed product - it works fine. you likely only need to worry about efficiency if you're on embedded hardware or processing a lot of data. – Habitable

well that article is describing exactly what i need to do except for weird constraints i cannot put my patch at the end. i was hoping i could convert my current crc implementation into table form, and then use a similar technique to the one described in the article i liked to... – Slr

Answer 2

My recollection (I used to do modem stuff way back when) is that Kermit processes the bits in each byte of the data using the least significant bit first.

Most software CRC implementations (Xmodem, probably) run through the data bytes most significant bit first.

When looking at the library source (download it from http://www.lammertbies.nl/comm/software/index.html) used for the CRC Calculation page you linked to, you'll see that XModem uses CRC16-CCITT, the polynomial for which is:

x^16 + x^12 + x^5 + 1  /* the '^' character here represents exponentition, not xor */

The polynomial is represented by the bitmap (note that bit 16 is implied)

0x1021 == 0001 0000 0010 0001  binary

The Kermit implementation uses:

0x8408 == 1000 0100 0000 1000  binary

which is the same bitmap as XModem's, only reversed.

The text file that accompanies the library also mentions the following difference for Kermit:

Only for CRC-Kermit and CRC-SICK: After all input processing, the one's complement of the CRC is calculated and the two bytes of the CRC are swapped.

So it should probably be easy to modify your CRC routine to match the PC result. Note that the source in the CRC library seems to have a pretty liberal license - it might make sense to use it more or less as is (at least the portions that apply for your application).

Dicephalous

This is 90% of it. In addition, looking at that code, the CCITT method swaps the bytes in the checksum. It would be easier if the code were C… actually the PC's program is in LabView, so it wasn't really easy to see what the checksum algorithm actually was. The solution was to get another CRC library which advertised itself as CCITT, and arbitrarily reverse the bytes from the micro to match its results. – Kathrynekathy

The note in the text file about performing one's complement of the CRC for CRC-Kermit and CRC-SICK appears to be a "copy typo." In the same text file, there is a note above for CRC-DNP which discusses the required one's complement operation (which supports the 'copy typo' theory). Examination of the source code appears to confirm that the one's complement operation applies only to CRC-DNP and not CRC-Kermit and CRC-SICK. – Bargeman

Why does KERMIT do the reflection, but not XMODEM? Is there some statistical benefit, perhaps based on intended input data? Could it be related to differences in intended hardware of the time, or differences in language used? Is there actual purpose to reflection? Really wish I knew. – Lutherlutheran

Answer 3

X-Modem 1K CRC16.

Process for bytewise CRC-16 using input data {0x01, 0x02} and polynomial 0x1021

1. Init crc = 0

2. Handle first input byte 0x01: 2.1 'Xor-in' first input byte 0x01 into MSB(!) of crc: 0000 0000 0000 0000 (crc) 0000 0001 0000 0000 (input byte 0x01 left-shifted by 8)

   ---

   0000 0001 0000 0000 = 0x0100 The MSB of this result is our current divident: MSB(0x100) = 0x01. 2.2 So 0x01 is the divident. Get the remainder for divident from our table: crctable16[0x01] = 0x1021. (Well this value is famila from the manual computation above.) Remember the current crc value is 0x0000. Shift out the MSB of current crc and xor it with the current remainder to get the new CRC: 0001 0000 0010 0001 (0x1021) 0000 0000 0000 0000 (CRC 0x0000 left-shifted by 8 = 0x0000)

   ---

   0001 0000 0010 0001 = 0x1021 = intermediate crc.

3. Handle next input byte 0x02: Currently we have intermediate crc = 0x1021 = 0001 0000 0010 0001. 3.1 'Xor-in' input byte 0x02 into MSB(!) of crc: 0001 0000 0010 0001 (crc 0x1021) 0000 0010 0000 0000 (input byte 0x02 left-shifted by 8)

   ---

   0001 0010 0010 0001 = 0x1221 The MSB of this result is our current divident: MSB(0x1221) = 0x12. 3.2 So 0x12 is the divident. Get the remainder for divident from our table: crctable16[0x12] = 0x3273. Remember the current crc value is 0x1021. Shift out the MSB of current crc and xor it with the current remainder to get the new CRC: 0011 0010 0111 0011 (0x3273) 0010 0001 0000 0000 (CRC 0x1021 left-shifted by 8 = 0x2100)

   ---

   0001 0011 0111 0011 = 0x1373 = final crc.

Rubato

Answer 4

CRC16 XModem is the same as CCIT Zero

Bawd