Of Stack

C language to implement the method of CRC check

  • 2020-04-01 23:31:59
  • OfStack

CRC(Cyclic Redundancy Check) checksum is widely used. In order to handle it easily, LRC(Longitudinal Redundancy Check) checksum was used in most programs. LRC checksum is easy to understand and easy to implement in programming. Spent a day to study the C language implementation of CRC, understand and master the basic principles and C language programming. Write it down with your understanding.

1. CRC introduction

The basic idea of CRC test is to use linear coding theory to generate a test code r bit (namely, CRC code) according to the k-bit binary code sequence to be transmitted at the sending end with certain rules, attach it to the information, form a new binary code sequence number (k+r) bit, and finally send it out. The receiver is checked by the same rule to see if there is an error in the transmission. There are two processing methods at the receiving end: 1. Calculate the CRC code of the k-bit sequence, and compare it with the received CRC. 2. Calculate the CRC code of the whole k+r bit. If it is 0, it is received correctly.
CRC code has a variety of check bits, 8, 16, 32, and so on, the same principle. The rule for generating a 16-bit CRC code is to first shift the number of binary sequences to the left by 16 bits (that is, multiply by 2 to the 16th power), divide by a polynomial, and the remainder is the CRC code.
The CRC code is the use of modular 2 algorithm, that is, the polynomial division method USES the subtraction without borrowing operation, operation is equal to xor operation. This, to be understood carefully, is fundamental to programming.
Crc-16: (used in American binary synchronization system) G (X) = X16 + X15 + X2 + 1
Crc-ccitt: (recommended by European CCITT) G (X) = X16 + X12 + X5 + 1
CRC-32: G(X) = X32 + X26 + X23 + X22 + X16 +X12 + X10 + X8 + X7 + X5 + X4 + X2 +X1 + 1

2. Calculate CRC by bit

The use of CRC-CCITT polynomial, the polynomial is 0x11021, C language programming, to participate in the calculation of 0x1021, this place has to think deeply to understand the mystery, share my thoughts: When CRC is calculated by bits, for example, when the binary sequence is 1001 1010 1010 1111, the binary sequence number is shifted 16 bits to the left, i.e. 1001 1010 1010 1111 (0000 0000 0000 0000 0000). In fact, the binary sequence can be split into 1000 0000 0000 0000 (0000 0000 0000) + 000 0000 0000 0000 (0000 0000 0000 0000) + 00 0000 0000 0000 (0000 0000 0000 0000) + 100 000 0000 0000 (0000 0000 0000 0000) + 1 0000 0000 (0000 0000 0000 0000) +...
Now to analyze the operation:
< 1 > For the remainder of the first binary sequence, the vertical division is 0x10000 ^ 0x11021, and the following 0 bits are reserved.
< 2 > Then, the remainder of the second binary sequence is calculated, and the remainder of the first step is calculated with the second binary sequence of 0x11021 after the remainder of the first step is calculated by *2. This step should not be a problem to understand. If the sequence is 0, no calculation is needed.
< 3 > The remainder of the binary sequence is the same as in the previous two steps.
< 4 > When the last bit is calculated, the remainder of the entire binary sequence is the CRC check code.
This method is equivalent to the calculation of each bit, the operation process is easy to understand, occupies less memory, disadvantage is the bit bit calculation is relatively time-consuming.
The following is the implementation method of C language: 


unsigned char test[16] = {0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
unsigned char len = 16;
void main( void )
{
   unsigned long temp = 0;
   unsigned int crc;
   unsigned char i;
   unsigned char *ptr = test;
   while( len-- ) {
      for(i = 0x80; i != 0; i = i >> 1) {
         temp = temp * 2;
         if((temp & 0x10000) != 0)
            temp = temp ^ 0x11021;

         if((*ptr & i) != 0) 
            temp = temp ^ (0x10000 ^ 0x11021); 
     }
    ptr++;
   }
   crc = temp;
   printf("0x%x ",crc);
}

The above program is based on arithmetic analysis and is easy to understand. To save memory space, we have further simplified the program. The analysis shows that when the 15th bit of the remainder of the previous bit of the binary sequence is 1, that is (the remainder of the previous bit of the computation & 0x8000)! = 0, in the calculation of standard, the remainder of the previous digit * 2 can be calculated on 0x11021, and then the remainder of the standard calculation can be added. That's easy to understand, which is to say, for example, think of it as a simple division, where you take the remainder of the previous digit and you multiply it by 2, and if it's bigger you can take the dividend, and you get rid of the divisor and take the remainder. One difference from normal division is that 0x10000 can also be divided by 0x11021, since polynomial division USES subtraction without borrowing. The remainder is not 0x10000, but 0x1021. I'll just do it myself. The sum of the remainder is also an addition operation without carry, or xor. The last thing I want to emphasize is that because the binary sequence is moved 16 bits to the left, it can be divided all the way to the last bit of the sequence. The simplified C language implementation is given below. 

unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
unsigned char len = 16;
void main( void )
{
   unsigned int crc = 0;
   unsigned char i;
   unsigned char *ptr = test;
   while( len-- ) {
      for(i = 0x80; i != 0; i = i >> 1) {
        if((crc & 0x8000) != 0) {
           crc = crc << 1;
           crc = crc ^ 0x1021;
        }
        else {
           crc = crc << 1;
        }
        if((*ptr & i) != 0) {
          crc = crc ^ 0x1021; 
        }
     }
     ptr++;
   }
   printf("0x%x ",crc);
}

The above program is more common on the Internet, but it needs detailed explanation. Through my above detailed analysis, if this section of the program is still difficult to understand, you can compare not to simplify the previous program, savor a ha, or relatively easy to understand. If you still can't understand, or read again from the beginning, I code so many words easy...
It is relatively simple to calculate the CRC code by bits, which takes up less memory, but it needs to be calculated bit by bit. The following is another method to quickly calculate CRC by byte lookup table.

3. Calculate CRC by bytes

With the above knowledge of bitwise calculation, it is a little case to understand this. Or the previous example: when the bytes CRC, for example to calculate the binary sequence is 1001 1010 1010 1111, or 0 x9a9f, binary sequence number to the left 16, namely 0 x9a9f (0 0 0 0), actually the binary sequence can be broken up into 0 x9a00 (0 0 0 0) + 0 x009f (0 0 0 0), analysis and calculation as well as the steps above, when the only difference is the remainder of CRC calculation upper step to 2 times of the eight power to participate in the next step of operation, this should be well understood. In order to simplify the programming, the CRC in the calculation is divided into the form of high eight bits and low eight bits. The value of high eight bits is directly added to the standard value to find the remainder. The value of low eight bits is multiplied by 2 to the eighth power as the remainder and added to the calculated remainder. In order to improve the calculation speed, we calculate all the CRC of 8-bit binary sequence Numbers and put them in a table.
How did you get the table? Of course, it is calculated. The following program shows the calculation program with a polynomial of 0x11021. 


void main( void )
{
   unsigned int crc = 0;
   unsigned char i;
   unsigned int j;
   for(j = 0; j < 256; j++) {
      crc = 0;
      for(i = 0x80; i != 0; i = i >> 1) {
         if((crc & 0x8000) != 0) {
            crc = crc << 1;
            crc = crc ^ 0x1021;
        }
        else {
            crc = crc << 1;
        }
        if((j & i) != 0) {
            crc = crc ^ 0x1021;
        }
   }
   printf("0x");
   if(crc < 0x10) {
      printf("000");
   }
   else if(crc < 0x100) {
      printf("00");
   }
   else if(crc < 0x1000) {
      printf("0");
   }
   printf("%x, ",crc);
   }
}

If you are not using the 0x11021 polynomial, just replace 0x1021 in the program with something else. The next few printf statements are to keep the generated tables in order, if it doesn't matter, you can directly use printf("0x%x, ", CRC); Instead. The generated table is as follows:
0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xb16a, 0xb18c, 0xd1ad, 0xe1ce, 0xf1ef, 0x1231, 0x0210, 0x3273, 0x52b5, 0x72f7, 0x62d6, 0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, 0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74e6, 0x44a4, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, 0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, 0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, 0x5af5, 0x4ad4, 0x7ab7, 0x7a7, 0x0a50, 0x3a33, 0x2a12, 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 0x7e97, 0x6eb6, 0x4ef4, 0x3e13, 0x2e32, 0x0e70, 0xff9f, 0xfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x83b9, 0x9398, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x6447, 0x5424, 0x4405, 0xa7db, 0xb98a, 0xe7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc73c, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x3615, 0x5615, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0,
Okay, let's write the source program in bytes: 

unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
unsigned char len = 16;
unsigned int crc_table[256] ={
x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef, 0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6, 0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, 0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485, 0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d, 0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, 0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, 0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, 0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, 0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, 0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, 0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, 0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0};
void main(void)
{
   unsigned int crc = 0;
   unsigned char crc_H8;
   unsigned char *ptr = test;
   while( len-- ) {
      crc_H8 = (unsigned char)(crc >> 8);
      crc = crc << 8;
      crc = crc ^ crc_table[ crc_H8 ^ *ptr];
      ptr++;
   }
   printf("0x%x ",crc);
}

4. Calculate CRC by half byte

Do you feel that the above table is too big, not very cool, let's improve it again, by half a byte calculation, I will not repeat the principle, the procedure is as follows: 


unsigned char test[16] ={0x00,0x11,0x22,0x33,0x44,0x55,0x66,0x77,0x88,0x99,0xaa,0xbb,0xcc,0xdd,0xee,0xff};
unsigned char len = 16;
unsigned int crc_table[16] =
{0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef
};
void main(void)
{
unsigned int crc = 0;
unsigned char crc_H4;
unsigned char *ptr = test;
while( len-- )
{
crc_H4 = (unsigned char)(crc >> 12);
crc = crc << 4;
crc = crc ^ crc_table[ crc_H4 ^ (*ptr >> 4)];
crc_H4 = (unsigned char)(crc >> 12);
crc = crc << 4;
crc = crc ^ crc_table[ crc_H4 ^ (*ptr & 0x0f)];
ptr++;
}
printf("0x%x ",crc);
}

Related articles: