3

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;
}
user3791563
  • 57
  • 1
  • 4

2 Answers2

4

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 :)

bytefire
  • 4,156
  • 2
  • 27
  • 36
  • thanks for your answer and your efforts , I couldn't test the code you find on that site because I don't have the libraries used there. but how is possible that the output was equal to mine even that the two codes use two different polynomials ? – user3791563 Jul 01 '14 at 09:32
  • To run the linked code, `#include `. This code left shifts the polynomial while yours doesn't. I'll update more once I get time to look into this. – bytefire Jul 01 '14 at 09:38
  • Am not getting the same output , here is the code of main `int main() { unsigned char a[]={1}; printf("%d\n", crc8(a,1)); printf("%d\n", Crc8(a,1)); return 0; } ` – user3791563 Jul 01 '14 at 09:58
  • I'd use `printf("%x\n", crc8(a,1));` instead. Not sure why it is different. May be try running them in two separate programs. It's possible one function is modifying a common variable. – bytefire Jul 01 '14 at 10:07
  • I separated them but am getting always different outputs. – user3791563 Jul 01 '14 at 10:21
  • @user3791563 my bad. You are right. The two outputs are different. And that is because of different polynomials. The polynomial used by the code I posted is effectively 0x107 (0x1070 in code). The result for that polynomial is correct. If we replace 0x1070 with 0x1310 (effectively 0x131 which is polynomial in your posted code) we get same answer. Updated the post above. – bytefire Jul 01 '14 at 10:28
  • thanks for the update about the online calculator , your resolved a big mystery for me :) – user3791563 Jul 01 '14 at 10:28
  • I've very late to the party but it's incorrect that a crc isn't an invertible function. So if we know y of y = crc(x) then we can compute x. Just almost nobody is interested that computation. This needed so no two inputs map to the same output: crc(x) == crc(y) if and only if x==y. – MB Reynolds May 30 '22 at 09:23
2

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.

Community
  • 1
  • 1
Mark Adler
  • 101,978
  • 13
  • 118
  • 158