3

I have been trying to understand what is the trick behind online calculator which gives me CRC value for any input. The thing is that results I get with doing maths by hand do not match results this calculator gives me. On the other hand, I also found this calculator, which always gives the results I get by doing XORing by hand.

Also, I have done my calculations the same way they are done in the following sections at Wikipedia and here. I know I'm doing it the right way, however that calculator (and other ones, like this one) always gives me different results, except for some custom polynomials.

There might be a catch to the way these CRCs are calculated - Wikipedia suggests that there are next following polynomial representations: normal, reversed, reciprocal, reversed reciprocal. And first calculator I mentioned uses two more parameters regarding polynomial: initial value and final XOR value (for purposes of verifying by-hand calculations I chose CRCs with those two values being 0x0).

I'm really struggling to understand if I'm doing something wrong, where some sources say it's done this way, and some other calculators give completely different results then expected.

EDIT:

If the message and polynomial are of the same value, then resulting CRC value should be 0, since there is no remainder. This is how I checked that there is some other processes to CRC calculations other then the XORing message and polynomial:

enter image description here

On the other hand, I just found out that (at least) custom defined polynomials ignore the highest term of polynomial (in the case of CRC-8, this would be \$ x^8 \$ which corresponds to 9th bit). This can be verified by inputting message that equals real polynomial (addition of "1" to message byte):

enter image description here

This corresponds to the following quote from Wikipedia:

Omission of the high-order bit of the divisor polynomial: Since the high-order bit is always 1, and since an n-bit CRC must be defined by an (n + 1)-bit divisor which overflows an n-bit register, some writers assume that it is unnecessary to mention the divisor's high-order bit.

Keno
  • 2,360
  • 2
  • 35
  • 65
  • 4
    Did you examine the online calculator's Javascript code to see how it's doing it? Hit `Ctrl-U` on most browsers to show page source. – Transistor Apr 09 '21 at 19:13
  • 6
    Also, did you note on the Wiki page this quote: *"The number of distinct CRCs in use has confused developers, a situation which authors have sought to address. There are three polynomials reported for CRC-12, twenty-two conflicting definitions of CRC-16, and seven of CRC-32."* It's possible that you are running up against this. It has certainly caused me a problem or two, before. – jonk Apr 09 '21 at 19:16
  • @jonk Not just a problem to me, more like a headache... – Keno Apr 09 '21 at 19:24
  • @Transistor 1200 lines of Javascript code are a bit to much for a beginner like me (currently programming in C). Also, code seems very complex and, of course, too long to quickly examine it. – Keno Apr 09 '21 at 19:25
  • What exactly are you calculating by hand then and what is the result? Some calculators feed bits in LSB first, some MSB first. There is no one true way, it's just that some algorithms are defined in a way that makes it clear how to calculate it. 1200 lines of javascript must have the 10 lines to do the CRC calculation like your C program would. – Justme Apr 09 '21 at 19:26
  • @jonk But does this variations CRC calculations affect detection of errors; meaning, for example, polynomial with highest term omitted and same polynomial with last term omitted have different error detecting properties? Seems to me that modified polynomial is completely different one. Also, how would one verify if modified polynomial has the same error detection capabilities as original one? – Keno Apr 10 '21 at 09:32

2 Answers2

4

You just have a false assumption.

Sending in a byte that matches the polynomial will not result into 0.

You might confuse that with the fact that calculating CRC over data which is appended with the CRC of the data, that will result into 0, which is a handy property - You don't have to calculate CRC and then compare if the CRC calculated matches the received CRC, you can calculate CRC over the data and received CRC and result is 0 if it matches.

Sending in a byte that matches what is in the CRC shift register will XOR out the shift register to 0, and then when the polynomial is applied to the zeroed shift register, it will also result into zero CRC value.

So if you use the Sunshine CRC calculator, and use the default settings with 8-bit polynomial of 0x07, and calculate a CRC of single byte of 0, the result is 0, which means that the initial CRC value was also 0, because a 0 stays as 0.

If you feed in single byte of 0x01, which only has the LSB bit on, you get the polynomial 0x07 out as the result. This confirms that the LSB is the last bit calculated, so data is sent in MSB first.

It also means if you send in data of say 0x01 0x07, the resulting CRC is 0.

This confirms that the default settings are so that initial CRC is 0, data is sent in MSB first, and the final XOR of the result is also 0.

Justme
  • 127,425
  • 3
  • 97
  • 261
4

Both calculators produce the same result. For CRC-8, the divisor is assumed to have 9 bits, and you must add 8 zero bits to the input before dividing. When you used the second calculator for CRC-8, you must designate that the divisor (shown as P(x) in the calculator) is a nine-bit number by adding the leading zeroes:

enter image description here

This causes the algorithm to correctly add the eight "zero" bits and gives you the result of 0x15, and eight bits are added to your string of "111". When you enter only "111" for P(x) you are calculating a two-bit CRC and only two zeroes are added so you get a different result (zero), and only two bits are added to your string ("00"). A two-bit CRC would be much weaker than an eight-bit for detecting errors.

I would also echo @Jonk by stating that there are an almost infinite number of "standard" ways to calculate CRC - just make sure that you use the same one to calculate and check.

In response to your question regarding the higher-order bit of the divisor, making it a "one" has no effect on the result:

enter image description here

John Birckhead
  • 10,524
  • 1
  • 11
  • 27
  • Hmm interesting.. But still, in this particular example, the CRC-8 polynomial is 0x7, which means \$ x^8 \$ or 9th bit of polynomial (which is generally "1" for CRC-8) is omitted, right? – Keno Apr 09 '21 at 21:07
  • If yes, then if it would be included in this polynomial as P(x) = "100000111", then no zeros would have to be appended to *right side* of polynomial, right? – Keno Apr 09 '21 at 21:09
  • But then, CRC would be calculated as different value... – Keno Apr 09 '21 at 21:10
  • It does not produce a different value, because the operation of the highest-order bit of the divisor is always "overflow" and discarded. See my edited answer (because I can't put a picture here in the comments.) – John Birckhead Apr 11 '21 at 20:01