0

I have some trouble implementing a CRC16 for can message, I followed the instructions given by this website https://barrgroup.com/embedded-systems/how-to/crc-calculation-c-code and http://www.sunshine2k.de/articles/coding/crc/understanding_crc.html#ch5, plus other implention I have seen in here ( for example Function to Calculate a CRC16 Checksum).

I don't understand how it is processed. My message here is in form of bytes, for example char message[4] = {0x12, 0x34, 0x56, 0x78}. When I go through the first loop I just take the first byte, shift it by 8 and calculate the remainder with a POLYNOME of 16 bits. That means we have 0x1200 and we go through the second loop with it, which mean I do a XOR with the POLYNOME that I store in the remainder but I don't quite understand why this works, especially when I look at this code, the 2nd, 3rd and 4th bytesof my message which should get XORed by the 8 first bits of the POLYNOME at some points aren't going through it at all. According to the wikipedia explanation https://en.wikipedia.org/wiki/Cyclic_redundancy_check the polynome goes through the whole message at once and not byte by byte. I don't know how that translates to doing the CRC of 0x12345678 byte by byte.

uint16_t Compute_CRC16_Simple(char* message, int nbOfBytes)
{
    uint16_t POLYNOME = 0xC599; 
    uint16_t remainder = 0; 
    for (int byte = 0;byte < nbOfBytes; byte++)
    {
        remainder ^= (message[byte] << 8); 

        for (int i = 0; i < 8; i++)
        {
            if (remainder  & 0x8000) 
            {
                remainder = (remainder << 1) ^ POLYNOME ;
            }
            else
            {
                remainder <<= 1;
            }
        }
    }
    return remainder;
}
yat
  • 35
  • 5
  • This CRC uses the high order bit of the first byte as the highest order bit of a polynomial. The algorithm takes advantage of the fact that cyclic math is "linear" and xoring the first byte shifted puts the bits in the correct position. You can verify this by writing code that calculates CRCs bit by bit. It's a lot slower of course. – doug Dec 12 '21 at 06:26
  • Too long to answer here. Read [Ross Williams' excellent tutorial](http://ross.net/crc/download/crc_v3.txt) on CRCs and their practical calculation. – Mark Adler Dec 12 '21 at 17:53
  • @doug - it might help to explain that a CRC is the remainder from a borrowless divide, where the CRC polynomial is the divisor, and the data logically padded by 16 zero bits at the end is the dividend, and that the remainder is "subtracted" from the 16 logical zero bits, but since this is GF(2), "add" and "subtract" are both XOR, so the remainder just replaces the 16 logically padded zero bits when encoding to append a CRC to the data. – rcgldr Dec 12 '21 at 19:34
  • @rcgldr True. I was hoping to get the OP to code it by doing 1 bit at a time to see that it works the same as processing a byte at a time. GF(2) operations are rather beautiful as are gf(256) used in ECC. It makes a lot more sense once one works with it a bit and develops an intuition of the math. – doug Dec 13 '21 at 02:10
  • @doug - you can process more than a byte at at time by "folding" data. Using XMM registers and PCLMULQDQ, CRC can be processed 128 bytes at a time (256 bytes at a time for the few processors that have AVX512). [Intel PCLMULQDQ | CRC](https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf). I converted example code to work with Visual Studio and added comments to the constants (which aren't explained in Intel's code): [jeffareid github crc](https://github.com/jeffareid/crc). – rcgldr Dec 13 '21 at 05:01
  • @rcgldr The intrinsics in the newer CPUs sure do speed that up. Lot of great stuff. Thanks for the info. Been 10 years or so since I last worked with ECC or CRCs. – doug Dec 13 '21 at 05:33
  • @doug - that github repository has some [ECC](https://github.com/jeffareid) and [BCH](https://github.com/jeffareid/misc) code as well. – rcgldr Dec 13 '21 at 07:51
  • Why are you implementing CRC16 for CAN frames? They already have CRC built-in. What is the actual problem you are trying to solve here? – Lundin Dec 13 '21 at 07:53
  • @rcgldr I have done the implentation bit by bit as you sugested me, I saw that it works, but I don't quite understand the logic behind it. I will look at @mark-adler link, thanks. @lundin the process to do the check isn't it the same ? I should do the calculcation of the `SOF`, `Arbitration Fiel`, `Control Field` and `CRC` field and I should have a remainder of 0 right ? – yat Dec 13 '21 at 16:14
  • @yacth it was doug that suggested you try bit by bit. The Ross Williams tutorial linked to by Mark Adler explains why this works. You can XOR 8 or even 16 bits at a time to the CRC "register", then cycle the CRC "register" 8 or 16 times, and instead of actually cycling, a table indexed by value, where each element is the value cycled 8 or 16 times can be used instead. – rcgldr Dec 13 '21 at 19:10
  • @rcgldr Yes following [Barr group tutorial](https://barrgroup.com/embedded-systems/how-to/crc-calculation-c-code), I have done the implementation with a table indexed by value. It works greatly, and it seems to be faster, I am trying to figure out why though. – yat Dec 13 '21 at 19:30
  • @yacth - I posted an answer that may help explain this. – rcgldr Dec 14 '21 at 06:09
  • @yacth The CRC15 of the CAN frame is already taking the arbitration field & control fields in account. And it's automatically handled by the CAN controller. While an application-tier CRC16 in the payload can only take the payload in account. Therefore what you are trying to do _makes no sense_. – Lundin Dec 14 '21 at 07:42
  • @Lundin Sorry I might not understand, but let's say I am wiring a CAN bus to a micro-controller and I want to send a CAN message to one of the actuators connected to this bus. How should I generate the whole CAN message to send ? . Because I know the ID of the actuators, I know the data I have to send. Plus in the cas I receive data how can I verify that my data is valid ? I thought calculating the CRC was the process. – yat Dec 14 '21 at 14:37
  • Unless you are transmitting massive amounts of data (many hundreds of bytes), you can rely on the built-in CRC. – Lundin Dec 14 '21 at 15:11
  • @Lundin I don't understand what do you mean by "built-in" CRC because I am writing a program to create the CAN messages from scratch using bosch documentation. – yat Dec 14 '21 at 16:15
  • Are you saying that you are bit-banging can using GPIO? That's a horrible idea and you are using the wrong CRC for that too. I suspect that you simply need to study CAN more, then use it as intended with the aid of a CAN controller. – Lundin Dec 14 '21 at 16:28
  • @Lundin What is the right CRC ? Because the polynomial I found on the documentation is : P(x) = X^15 + X^14 + X^10 + X^8 + X^7 + X^4 + X^3 + X^0 is it wrong ? Actually if you can direct me to something I should look up instead of saying "what you are trying to do makes no sense" or "I suspect that you simply need to study more" without explaining what process is the right one. – yat Dec 14 '21 at 19:22
  • The purpose of a CAN controller (physical integrated circuit) is to create the CAN frame. When the programmer interacts with the controller, they just fill in data, identifier and maybe some other bits like RTR. Then the controller takes care of everything including error handling, checksums, bus arbitration, re-sending messages, bit stuffing and so on and so on. It's a big topic. – Lundin Dec 14 '21 at 19:27
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/240150/discussion-between-yacth-and-lundin). – yat Dec 14 '21 at 19:30

1 Answers1

1

I don't understand how it is processed.

Maybe it will help to describe the bit by bit operations for 8 bits of data:

crc[bit15] ^= data[bit7]
if(crc[bit15] == 1) crc = (crc << 1) ^ poly
else crc = crc << 1
crc[bit15] ^= data[bit6]
if(crc[bit15] == 1) crc = (crc << 1) ^ poly
else crc = crc << 1
...
crc[bit15] ^= data[bit0]
if(crc[bit15] == 1) crc = (crc << 1) ^ poly
else crc = crc << 1

Note that the if statement only depends on the bit value in crc[bit15], so the fixed part of the XOR with data could be done in one step:

crc[bit15 .. bit8] ^= data[bit7 .. bit0]
if(crc[bit15] == 1) crc = (crc << 1) ^ poly
else crc = crc << 1
if(crc[bit15] == 1) crc = (crc << 1) ^ poly
else crc = crc << 1
...
if(crc[bit15] == 1) crc = (crc << 1) ^ poly
else crc = crc << 1

The cycling of the CRC 8 times using those if ... then (shift + xor poly) else (just shift) could be precomputed for all 256 possible values in crc[bit15 .. bit8], and stored in a table for table lookup to cycle the CRC 8 times.

rcgldr
  • 27,407
  • 3
  • 36
  • 61