6 bit CRC check (24 bit data)

Hi guys,

I am communicating with a sensor through SPI as follow:

  • sending 5 bytes of data (1 command byte, followed by 4 bytes zero’ed out to keep the transfer alive)
  • receiving 5 bytes of data (the command byte is returned first, followed by 3 bytes of actual data, and last 1 byte with the 2 most significant bits error/warning, followed by a 6 bit CRC).

I am able to communicate fine, the data looks good. I am able to sort the data, i.e. separating the actual data from the CRC.

I am trying to write a CRC check the data, but I must have errors as I am showing only invalid data. (note that I know the data is likely good since I can connect the sensor to the manufacturer’s USB reader/gui which confirmed that.

Note that per manufacturer spec the CRC is sent in its “inverted” state. So I have a line of code to XOR mask it.

Here’s my function. I have added plenty of comments to make it more readable.

Cheers.
thanks for any help

void SPIPositionRead (bool SPI_EXT) {
  byte DataTX_Buffer[10];
  byte DataRX_Buffer[10];
  int i, j;
  uint32_t PZ_Position = 0;
  bool nERR = true;
  bool nWARN = true;
  byte CRC = 0;
  DataTX_Buffer[0] = 0xA6;       //COMMAND
  DataTX_Buffer[1] = 0x00;       //Empty Data to keep the transfer alive
  DataTX_Buffer[2] = 0x00;       //Empty Data to keep the transfer alive
  DataTX_Buffer[3] = 0x00;       //Empty Data to keep the transfer alive
  DataTX_Buffer[4] = 0x00;       //Empty Data to keep the transfer alive
  if (SPI_EXT) {
    //This is unused currently, basically there are 2 CRC modes. a 6 bit and a 16 bit,
    //The 16 bit CRC requires 2 additional bytes and I won't be needing that.
    //True:   CRC16bit - 7 bytes will be returned - need 2 more    
    DataTX_Buffer[5] = 0x00;
    DataTX_Buffer[6] = 0x00;     
     
  }
  else {
    //False:  CRC6bit - only 5 bytes will be returned from the SLAVE
    SPI.beginTransaction(SPIsettings); 
    digitalWrite(SELpin, LOW);
    for (i=0; i<5; i++) {
        DataRX_Buffer[i] = SPI.transfer(DataTX_Buffer[i]);
        //Serial.println(DataRX_Buffer[i]);
    }
    digitalWrite (SELpin, HIGH);
    SPI.endTransaction();

    //REBUILD POSITION DATA
    PZ_Position = 0 << 24 | DataRX_Buffer[1] << 16 | DataRX_Buffer[2] << 8 | DataRX_Buffer[3];
    Serial.print("Position Data (Decimal): ");
    Serial.println(PZ_Position);
    //This was checked on the serial plotter and everything looks good so far
    
    //nERR, nWARN, CRC byte
    if (DataRX_Buffer[4] & 0x80)    //bit 7 is nERR bit
        nERR = true;
    if (DataRX_Buffer[4] & 0x40)    //bit 6 is nWARN bit
        nWARN = true;
    //copying the raw 6bit CRC as received into a CRC byte variable
    CRC = DataRX_Buffer[4] & 0x3F;  //bits 5:0 are CRC (6 bit)
    
    //CRC INFORMATION
    //CRC is transmitted in its inverted state
    //6-bit CRC Polynominal: X^6 + X^1 + X^0
    //Equivalent divisor: 100 0011, truncated into: 00 0011 (0x3)
    
    //Here's where the stuff I am not sure about starts...
    byte CRC_Polynomial = 0x3;
    //Masking the 6 LSB 
    byte InversionMask = 0b00111111;
    Serial.print("CRC (inverted as received): ");
    Serial.println(CRC);
    
    //Actual inversion
    CRC ^= InversionMask;
    Serial.print("Actual CRC: ");
    Serial.println(CRC);   
    
    //And here is where most likely I am messing up
    byte CRC_Verif = 0;
    for (i=1; i<4; i++) {
      CRC_Verif ^= DataRX_Buffer[i];
      for (j=0; j<8; j++) {
        if (CRC_Verif & 1)
          CRC_Verif ^= CRC_Polynomial;
        CRC_Verif >>= 1; 
      }
    }
    Serial.print("CRC Verification: ");
    Serial.println(CRC_Verif);
    if (CRC == CRC_Verif)
      Serial.println("Data is valid");
    else
      Serial.println("Data is invalid");
  }
}

Post a link to the sensor datasheet please.
If you have an example of a valid message (that isn’t in the datasheet) post that as well.

Can you post a link to the CRC algorithm you are trying to replicate?

This is a wild stab in the dark, but

CRC_Verif >>= 1;

was this line intended to "rotate" the bits, not simply shift them? In other words, the bit on the right that is lost was meant to be fed back in to the most significant bit?

Thanks for the answers guys!

I don't have a link to the datasheet, just a paper version, here's what it says:

6bit CRC poly: X^6+ X^1+ X^0
Hamm. Dist. = 3
CRC code: 0x43

The 0x43 is from that I got the 100 0011.
I read online that normally the MSB is truncated, which gets me a 0x3.
Maybe that's the issue?

I don't see why they would go and say 0x43 if it's to end up using 0x3 as poly.

They don't provide a valid message, I haven't been able to get a single valid CRC from the code posted above. Surely there is something wrong. Their GUI is nice, but it doesn't show the CRC maths, only triggers an error when it's not valid and I haven't seen that happen on their GUI so my guess is that my code is wrong.

Seems you will have to reverse engineer the CRCC the hard way. You have a message that doesn't work. Beginning with x'00, try every value up to x'ff and see what value is accepted.

Paul

The information provided is not enough to uniquely identify the CRC calculation. The shift could be right or left, the order of the bytes processed from left to right, there could be initial or final XOR values, etc.

You really need examples of one or more valid messages, with valid CRCs in order to determine the correct approach. If you could post some of those, clearly identifying the message components, one of us can help.

Hint: RevEng can be used to reverse engineer CRC calculations.

Thank you for the replies.

I haven't been able to see any valid checksum yet.

here's a few lines of output of my code. Not sure if they will be helpful but I will look in "Reveng" and see what I can do:

All numbers below are Decimal. The position data is 24 bit, the CRC is 6 bit.
"CRC (Inverted as received)" is the 6 bit CRC as read (according to the spec, it is transferred "inverted"
"Actual CRC" is me inverting that received CRC
CRC Verification is my attempt at getting a CRC
I can't get my calculated CRC to match what's sent

######New Data#####
Position Data (Dec): 513193
CRC (inverted as received): 42
Actual CRC: 21
CRC Verification: 1
Data is invalid
######New Data#####
Position Data (Dec): 609300
CRC (inverted as received): 50
Actual CRC: 13
CRC Verification: 1
Data is invalid
######New Data#####
Position Data (Dec): 698064
CRC (inverted as received): 18
Actual CRC: 45
CRC Verification: 1
Data is invalid
######New Data#####
Position Data (Dec): 794512
CRC (inverted as received): 0
Actual CRC: 63
CRC Verification: 1
Data is invalid

If the sensor outputs complete messages, each with a valid CRC, that is the place to start.

If so, please post hexadecimal dumps of several different complete messages, and indicate the start/stop, data and CRC sections.

On the other hand, it is pretty unlikely that you will get corrupted data. So, is it really necessary to be able to calculate the CRC? If not, I suggest not to bother.

I can hook up the logic analyzer and capture some data but I won’t be sure the data isn’t corrupted

I won't be sure the data isn't corrupted

I can't imagine why it would be in a test bench environment. If the signal is that noisy, you will clearly see it. Precautions such as CRCs can be important in extremely noisy industrial settings, where sensors are placed on high power equipment, and long leads are involved.

A six bit CRC is not very secure, because 1 out of 64 randomly chosen CRC values will be correct for any message.

Please enlighten us as to why this is so important in your case.

At this point it's more of a completion/understanding standpoint than anything.
From what I've been reading a 6-bit CRC on 24-bit data can yield false positives. I never played with CRC and thought it would be good to learn so I did some research on how that's typically done.

I'll go through my code again, there is definitely something wrong since the CRC I'm calculating is always 0 or 1.

All CRCs and similar data checks have false positives. For example there are only 65536 possible 16 bit CRCs. If you get an error in the data and an error in the CRC, they can accidentally cancel.

Your tip on using Reveng to “brute force” the algorithm was good, thank you. At least I think it was:

I converted the data/CRC from Decimal to Hex (I used the short log I posted in one of my previous post) and used Reveng as follow:

reveng -w 6 -s 07D4A915 094C140D 0AA6D02D 0C1F903F

Here’s the output:

width=6  poly=0x03  init=0x37  refin=false  refout=false  xorout=0x00  check=0x04  residue=0x00  name=(none)

the poly of 0x03 confirms what I suspected, however I am a little puzzled by the other pieces that reveng output:
refin, refout, xorout, check
and specifically init = 0x37 - I’ll double check the sensor through the SPI/USB adapter/GUI but I’m pretty sure I’ve seen a “init” value for the CRC and that the default was 0x00, not 0x37

edit: I checked and the init value in the gui is 0x00. Not sure why reveng is picking up that number

byte CRC_Polynomial = 0x03;
    byte InversionMask = 0b00111111;
    Serial.print("CRC (inverted as received): ");
    Serial.println(CRC);
    CRC ^= InversionMask;
    Serial.print("Actual CRC: ");
    Serial.println(CRC);   
    byte CRC_Verif = 0x00; //Reveng says init is 0x37 - wrong? neither work.
    for (i=1; i<4; i++) {
      CRC_Verif ^= DataRX_Buffer[i];
      for (j=0; j<8; j++) {
        if (CRC_Verif & 0x80)
          CRC_Verif = (CRC_Verif << 1) ^ CRC_Polynomial;
        else
          CRC_Verif = CRC_Verif << 1; 
      }
    }
    CRC_Verif >>= 2; //both of these lines added to get a 6 bit CRC rather than a 8 bit CRC
    CRC_Verif &= 0x3F; //but that can't be right as I am more likely losing info from bit 0 and 1.
    Serial.print("CRC Verification: ");
    Serial.println(CRC_Verif);
    if (CRC == CRC_Verif)
      Serial.println("Data is valid");
    else
      Serial.println("Data is invalid");

In your quest, it may be good to know that not all CRCC bytes are at the end of the message. They may be imbedded anywhere in a fixt length message, just to confuse reverse engineering.

Paul

Thanks Paul, the datasheet may be missing some info but I know where the CRC is located and I am able to pull it out. So it's all a matter of decoding it now :slight_smile:

refin and refout indicate the direction of processing the data (ref=reflection). init means that to get the correct answer, RevEng had to initialize the CRC result with 0x37. "check" is the result of applying that particular CRC calculation to a standard character string, used for checking code correctness.

You should check more messages to make sure this is correct.

There are websites that will generate C code for arbitrary CRC calculations.

Thanks J.

I will try to run Reveng with more data. I have been cleaning up the code. At least I got the mechanics down now, hopefully it’s just a matter of finding the right settings.

I’ve dropped the array of bytes and its for loop as the XOR at the beginning of that for loop didn’t make sense to me. Instead I am using the already rebuilt 32bit unsigned int and shifting the polynomial left to align with the message

byte CRC_Polynomial = 0x3;
   byte InversionMask = 0x3F;
   Serial.print("CRC (inverted as received): ");
   Serial.println(CRC);
   CRC ^= InversionMask;
   Serial.print("Actual CRC: ");
   Serial.println(CRC);   
   uint32_t CRC_Verif = PZ_Position;
   uint32_t CRC_Poly = CRC_Polynomial;    
   for (j=0; j<24; j++) {
       if (CRC_Verif & 0x800000)
           CRC_Verif ^= CRC_Polynomial;
       CRC_Verif = CRC_Verif << 1; 
   }
   CRC_Verif >>= 26;   
   Serial.print("CRC Verification: ");
   Serial.println(CRC_Verif);
   if (CRC == CRC_Verif)
       Serial.println("Data is valid");
   else
       Serial.println("Data is invalid");

I’m thinking I need to align the polynomial to the MSB of my data.

Well, I decided to start from scratch and write my own code. And no it’s still not working but at this time I think I must be misinterpreting one or more of the parameters from the manufacturer. I’ve reached out to them, not sure I’ll even get a response but we’ll see.

Here’s the new function.

//shift position data 6 bit to the left to pad with zero's
    uint32_t CRC_Verif = PZ_Position << 6;
    //polynomial (Divisor) 
    
    //MSB Found boolean
    bool MSB_Found = false; 
    //find the MSB in the Position Data 
    i = 0;
    while (!MSB_Found) {
        if (CRC_Verif & (0x80000000 >> i)) {
            //Found the MSB
            MSB_Found = true; 
        }
        else {
            //MSB not found yet
            if (i >= 32){
                //no bit @ 1 which means position data 0
                MSB_Found = true;
                return; //let's figure out what to do later 
            }
            i++;
        }
    }
    //Shift divisor to align it with CRC_Verif
    uint32_t Divisor = CRC_Polynomial << (24 + 1 - i);
    
    while (CRC_Verif > 0x3F) {
        if (CRC_Verif & (0x80000000 >> i)) {
            CRC_Verif ^= Divisor;
            Divisor >>= 1;
            
        }
        else {
            Divisor >>= 1;
        }
        i++;
    }
 
    Serial.print("CRC Verification: ");
    Serial.println(CRC_Verif);
    if (CRC == CRC_Verif)
        Serial.println("Data is valid");
    else
        Serial.println("Data is invalid");

It’s pretty different than anything I found on the web but that’s my translation of wiki page on CRC:

11010011101100 000 <— input right padded by 3 bits
1011 <— divisor
01100011101100 000 <— result (note the first four bits are the XOR with the divisor beneath, the rest of the bits are unchanged)
1011 <— divisor …
00111011101100 000
1011
00010111101100 000
1011
00000001101100 000 <— note that the divisor moves over to align with the next 1 in the dividend (since quotient for that step was zero)
1011 (in other words, it doesn’t necessarily move one bit per iteration)
00000000110100 000
1011
00000000011000 000
1011
00000000001110 000
1011
00000000000101 000
101 1

00000000000000 100 <— remainder (3 bits). Division algorithm stops here as dividend is equal to zero.

The divisor is what gets initially aligned to the MSB in the data, then gets shifted right keep it aligned with the MSB in the data before the XOR. I stop my loop when the remainder fits within 6 bit.
Anyway, it doesn’t work, but it made a lot of sense when I wrote that haha.

I think the problem is probably around bits 0/1 or 6/7 depending on which way you look at it.
I’m not sure it’s correct to be using those bits at all to generate a 6 bit CRC.

The code where you XOR in the next byte is fine when you have an 8 bit (or more) CRC.
This is a shortcut for “for each bit in the data byte, XOR that bit with the bit shifted out of the CRC, repeat for all bits”.
The algorithm just does all the XOR of the message bits up front, then does all the polynomial work second.

But I don’t think it necessarily extends to CRCs where the CRC width is not 8 bits, or perhaps even a multiple of 8.

It’s common to see CRCs with various initial values. Most commonly all 0 or all 1s, but other values are used as well.

This produces 0 out for all your examples. So I assume it is correct…

uint8_t data1[] = { 0x07, 0xD4, 0xA9, 0x15 };
uint8_t data2[] = { 0x09, 0x4C, 0x14, 0x0D };
uint8_t data3[] = { 0x0A, 0xA6, 0xD0, 0x2D };
uint8_t data4[] = { 0x0C, 0x1F, 0x90, 0x3F };

void do_crc(uint8_t* data)
{
  uint8_t crc = 0x37;
  for (int i = 0; i < 4; i++)
  {
    uint8_t d = *data++;
    for (int b = 0; b < 8; b++)
    {
      bool bit_out = ((d & 0x80) != 0) ^ ((crc & 0x20) != 0);
      if (bit_out)
      {
        crc <<= 1;
        crc ^= 0x03;
      }
      else
      {
        crc <<= 1;
      }
      d <<= 1;
    }
  }
  Serial.println(crc & 0x3F);
}

void setup()
{
  Serial.begin(115200);
  do_crc(data1);
  do_crc(data2);
  do_crc(data3);
  do_crc(data4);    
}

void loop()
{
}