CODEWITHSUNDEEP
calgorithmcrc
user3791563
user3791563

Reputation: 57

Cyclic redundancy check (crc) questions and properties?

I have some questions about crc algorithm, in this case about crc8.

  1. is crc standard ? I mean if I tell somebody that I am using crc8 in my frame , should I give him my crc8 code for it or he can find it online because it is a standard ?

  2. is crc reversible ? this mean if crc(x)=y can I find x if I have y ?

  3. if crc(A)=a and crc(B)=b , can I use a and b to find crc(AB) ?

  4. does crc have any algebraical properties ?

  5. I have found online a crc8 code in C , how I can verify the correctness of the code ? I found an some online calculators but no one is corresponding to my code , why ? these are the sites I used:
    Site: 1
    Site: 2
    and here is my code for the crc8 in C: 

char crc8(char arr[], char arrLen){
    char crc=0;
    char i;
    char shift;
  for (i = 0; i < arrLen; i++){
      crc ^= (arr[i]);
      for (shift = 8; shift > 0; shift--){
          if (crc & 10000000) crc = (crc << 1) ^ 0x131;
          else crc = (crc << 1);
      }
  }
  return crc;
}

Upvotes: 3

Views: 3759

Answers (2)

Mark Adler
Mark Adler

Reputation: 112557

To correct one of @bytefire's answers:

if crc(A)=a and crc(B)=b , can I use a and b to find crc(AB) ?

Yes, if you also have the length of A. You can look at crc32_combine_() in zlib for an example of how it's done.

See this answer for CRC-8 code using an optimal polynomial.

Upvotes: 3

bytefire
bytefire

Reputation: 4432

CRC is usually used to validate a piece of data (which really means an array of bytes). It computes a n-bit value corresponding to a given set of bytes (data), where n is the number in CRC-n (so 8 bits for CRC-8). It is like a hash function but it is not a secure hash and must be used for limited purposes, like error checking.

Following are simple answers to some of your questions.

is crc standard ? I mean if I tell somebody that I am using crc8 in my frame , should I give him my crc8 code for it or he can find it online because it is a standard ?

CRC is standard? Yes. CRC-16 and CRC-32 are the more commonly used. CRC-8, I am not sure about it's efficiency as it can only generate up to 256 unique values.

is crc reversible ? this mean if crc(x)=y can I find x if I have y ?

No

if crc(A)=a and crc(B)=b , can I use a and b to find crc(AB) ?

No

does crc have any algebraical properties ?

Did you mean associative, commutative etc? It is a hash function. So same thing applies to CRC-8 as to MD5 etc. From Wikipedia (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRCs_and_data_integrity), CRC has this property: 

CRC(x^y^z) == crc(x) ^ crc(y) ^ crc(z)

I have found online a crc8 code in C , how I can verify the correctness of the code ?

I tried running the code you posted and another crc8 code found here: https://chromium.googlesource.com/chromiumos/platform/vboot_reference/+/d96b25d0c0a739d351b8f09b128782ca12b7b0e1/firmware/lib/crc8.c. Both seem to be giving same output for same polynomial (0x1310 instead of 0x1070 in the linked code). Regarding comparison with the output from the sites that you compared against, you may want to consider tweaking the polynomial part. I'll update here if I find time to investigate it later today.

Update

The CRC calculator http://depa.usst.edu.cn/chenjq/www2/software/crc/CRC_Javascript/CRCcalculation.htm takes 8-bit polynomial and assumes that the ninth bit is always set. The polynomial used in your posted code is 0x131. If you zero out the ninth bit, then it becomes 0x31. So, if you use 31 as polynomial in the CRC calculator, you get same answer.

Also comparing the code you posted to the CRC algorithm, it looks fine.

Hope it helps :)

Upvotes: 5

Related Questions