Please help me understand this piece of CRC code

Projects Programming
1

The code takes a 14 byte message and iterated through it to calculate the CRC.

While I get the principle of the bit-shifting, this code makes no sense to me.
E.g. why would I right-shift 15 on an uint8_t?

    for (uint8_t i = 0; i < MSG_LENGTH; i++)
    {
        data = msg_buf[i];

        for (uint8_t j = 0; j < 8; j++)
        {
            new_bit = (uint8_t)(crc >> 15);
            crc <<= 1;
            crc |= (data >> 7);

            if (new_bit)
            {
                crc ^= CRC_POLYNOMIAL;
            }

            data <<= 1;
        }
    }

The code works, but I don't get the weird bit-shifting.

2

your assumption is that crc is 8 bit, but there is no code that confirms this,
it might be any type of variable (my guess 16 bit)

For all details - Cyclic redundancy check - Wikipedia

1 Like
3 
            new_bit = (uint8_t)(crc >> 15);

It is the result of the bit-shift that is cast to uint8_t not the crc variable, which we don't know the type of from the code snippet that you posted

1 Like
4

Why indeed?

If you mean this

           new_bit = (uint8_t)(crc >> 15);

and we assume crc is a 16 bit integer, it is a way to get at the MSB by shifting out the lower 15 bits.

It's odd code, however, as new_bit is only used as the test in an if statement, which coukd just have been

  if (crc & 0x8000) {

AmIRight?

a7

1 Like
5

I updated my O.P. with the varibale definitions... (apologies for the initial omission).

Looks like I fooled myself...
CRC is indeed 16 bit.
It is cast afterwards to 8 bit.

I better isolate this code fragment and added some Serial.write()s to see what is actually happening there.

Thank you all for your input.

6

Whilst your provision of extra information is appreciated it would have been better to have done it in a new post rather than revising a post that had already been commented on

Good luck with your further examination of the code

7

Not so fast, there. By the time of the if statement, crc has a new value, so it was a klunky way to check for later.

            bool msb = crc & 0x8000;

            crc <<= 1;
            crc |= (data >> 7);

            if (msb)
            {
                crc ^= CRC_POLYNOMINAL;
            }

In the old days, the left shift of the crc itself might have put the MSB somewhere that woukd survive until it needed testing.

a7

8

Please, specify your 14 bytes message (data) on which yo wish to compute 8-bit CRC. Also, don't forget to provide the polynomial.

9 
#define CRC_POLYNOMIAL 0x1021                   // CRC polynomial
const uint8_t MESSAGE[MSG_LENGTH] = {
    MSG_HEADER_1, MSG_HEADER_2, MSG_ID, MSG_LENGTH,
    0x08, 0x00, 0x02, 0xFF, 0xFE, 0x00, 0x20, 0x29, 0xBD, 0xB8};

    // 2-byte header
    // 1-byte message ID
    // 1-byte length (always 14)
    // 8 data bytes = 2 byte word x 4
    // 2-byte CRC (polynomial 0x1021)

[updated O.P.]

10 
2-byte header: 0x08, 0x00    -- Correct?
1-byte message ID: 0x02   -- correct?
1-byte length: 14 (0x0E) -- where it is in your above example?
8 data bytes:  Give an example: ----, ----, ----, ----, ----, ----, ----, ----
2-byte CRC polynomial: 0x1021 -- correct?
------------------------------------------------------
Total: 14 bytes

The intention to receive the above information is to present the mechanism/algorithm of computing 8-bit CRC from a given data. his will hep you to understnd why the bit shifing and XOR are bing done in the coding. In your case, the data legth is: 12 bytes.

11

These are the eight data bytes in the example, leading to CRC 0xBD, 0xB8:

12 
#define MSG_HEADER_1 0x55                       // always 0x55
#define MSG_HEADER_2 0xAA                       // always 0xAA
#define MSG_ID 0x12                             // always 0x12
#define MSG_LENGTH 14                           // length of all messages

Thank you, I wasn't expecting this level of support; I updated the O.P. too.

13

Please DO NOT update the original post. It makes subsequent replies difficult or impossible to follow.

14

==>

#define MSG_HEADER_1     0x55
#define MSG_HEADER_2     0xAA
#define MSG_ID           0x12
#define MSG_LENGTH       0x0E       //14
#define CRC_POLYNOMIAL   0x1021     //0001 0000 0010 0001 

const uint8_t MESSAGE[MSG_LENGTH] =  //messsage to be ransmitted
{
    MSG_HEADER_1, MSG_HEADER_2, MSG_ID, MSG_LENGTH,
    0x08, 0x00, 0x02, 0xFF, 0xFE, 0x00, 0x20, 0x29, 
    0xBD, 0xB8
};

byte myData[] =  //to calculate 16-bit CRC
{
      MSG_HEADER_1, MSG_HEADER_2, MSG_ID, MSG_LENGTH,
      0x08, 0x00, 0x02, 0xFF, 0xFE, 0x00, 0x20, 0x29
};

OP is calculating 16-bit CRC. In his example it is: 0xB8BD -- correct (lower byte first)?

1 Like
15

This is contrary to what I experience on other forums; things develop (get added to and corrected) over time.

So is the approach here then --- in this case --- where I buggered up the original post by not providing enough information, to orphan the post and open a new one. I am almost certain some will say: "double posting".

Given the further requests for information, these would have led to three new posts. I am sure I'd have lost my audience by then.

16

This forum has different rules. "Do not update the OP" is one of them.

Good luck with your project.

17

So long, I have taken OP for Original Poster; now, I see that it is for Original Post!

Hence forth, should I refer the Original Poster by TO (Thread Owner) as I have seen other people to use?

18

Happy to oblige; where can I find this and other rule(s)?

I wouldn't sweat it :slight_smile:

image
image620×583 51.8 KB

19

From post #18, it appears that OP is more inclined to a person (the Original Poster).

Then what does it mean in Arduino Forum --

Original Poster?

or

Original Post (the very first post)?

20

Not orphaning. Just leave the previous posts unchanged, aside from typos and such.

Add to the thread, do not open a new one.

If you have a new sketch, post it in its entirety rather than saying "I did what you said, blah blah blah".

In this case, you did say that

The code works

Changing the posts that we have all read can make trash of the comments, and make ppl look like idiots. No one likes that!

You must have rushed past the pinned threads at the top of the fora sections. Don't worry, to a first approximation eveyone does.

a7