Ejun recently used CRC check in her work, so she sorted out this article and studied it with everyone.
I. CRC concept
1. What is CRC?
Cyclic Redundancy Checksum (CRC) is an error-correcting technique that stands for Cyclic Redundancy Checksum.
The most commonly used error check code in the field of data communication. The information field and the length of the check field can be specified arbitrarily, but the CRC standards defined by the communication parties must be consistent. It is used to detect or verify errors that may occur after data transmission or saving. Its usage can be illustrated as follows:
In the process of data transmission, no matter how well designed the transmission system is, there will always be errors, such errors may cause one or more frames transmitted over the link to be corrupted (a bit error, 0 to 1, or 1 to 0), so that the receiver receives the wrong data.
In order to improve the accuracy rate of receiving data as much as possible, it is necessary to conduct error detection on the data before receiving the data, and only when the detection result is correct, the data is really accepted by the receiver. There are many detection methods, such as parity check, Internet check and cyclic redundancy check.
2. Overview of usage
Cyclic redundancy checkA calculation method used to verify the accuracy of digital transmission on a communication link (a mathematical operation to establish a convention between data bits and parity bits).
The sending computer calculates a value of the information contained in the transmitted data using a formula and attaches this value to the transmitted data. The receiving computer performs the same calculation on the same data and should get the same result.
If the two CRC results are inconsistent, an error occurred in the transmission, and the receiving computer can ask the sending computer to resend the data.
3. Widely used
CRC is one of the most famous error detection methods. The full name of CRC is cyclic redundancy check, which is characterized by strong error detection ability, low overhead, and easy to be realized by encoder and detection circuit. From the point of view of its error detection ability, the probability that it can not find the error is less than 0.0047%.
In terms of performance and cost, it is far superior to parity check and arithmetic and check.
CRC is therefore ubiquitous in data storage and data communication: The famous communication protocol X.25 FCS(Frame error detection sequence) uses CRC-CCITT, WinRAR, NERO, ARJ, LHA and other compression tools software uses CRC32, disk drive read and write uses CRC16, common image storage formats such as GIF and TIFF also use CRC as a means of error detection.
2. Definition of CRC name
There are several components or computational concepts that need to be known: polynomial formulas, polynomial abbreviations, data widths, initial values, resulting xOR values, input value inversion, output value inversion, and parametric models.
1. Polynomial formula
For CRC standard divisor, it is generally expressed by polynomial (or binomial) formula. In the following figure, the binomial of divisor 11011 (poly value 0x1b) is G(X)=X4+X3+X+1, and the exponent of X represents the data on the bit is 1 (the lowest value is 0).
And I’m going to pay special attention to the number of digits, the number of digits of the divisor is the highest power of the binomial plus 1 (4+1=5), which is important.
2. Polynomial shorthand
Through the basic knowledge of CRC as we know, the beginning and the end of the polynomial must is 1, the location of the 1 in the next step calculation must be 0, so just show the omitted in front of the 1, there was a call bsde type, in the example above divisor of bsde type 11011 to 1011, many have seen CRC senior language source code of the people will know, For CRC_16 standard G(X)=X16+X15+X2+1 (16#18005), the poly value is actually 8005, and the shorthand formula is used here. This usage will be explained later.
3. Data width
Data width refers to the length of CRC check code (binary number), know the CRC operation concept and polynomial, you can understand this concept, CRC length is always 1 less than the divisor number, and shorthand length is consistent.
The above three data points are the basic data that we often use
4. Xor value of initial value and result
In some standards, the initial value is specified, so before the above binomial operation, the data to be calculated should be xor with the lowest byte of the initial value, and then be calculated with the polynomial.
In the case that the result xOR value is not zero, the calculated CRC result value and the result xOR value need to perform xOR calculation again, and the final value is the CRC check code we need.
As you can see, the number of bits required for the initial and result values is consistent with the data width.
5. Input value inversion and output value inversion
Input-value inversion means that the binomial is inverted before the calculation, and then the calculation is performed with the new value and data. For example, for G(X)=X16+X15+X2+1 (16#18005), the forward value is 1 1000 0000 0000 0101, and the reverse value is 1010 0000 0000 0001 1
Output value inversion reverses the resulting CRC result.
Generally, the input value is reversed, so the two options are generally in the same direction, and we only see the free choice of positive and negative inversion in online CRC calculators.
Common CRC algorithms
Although CRC can arbitrarily define binomial, data length and so on, but without a unified standard, it will make the whole calculation becomes very troublesome. But in practice, different manufacturers often use different standard algorithms. Here are some models commonly used internationally:
| The name of the | polynomial | notation | Application, for example, |
|---|---|---|---|
| CRC-8 | X8+X2+X+1 | 0X107 | |
| CRC-12 | X12+X11+X3+X2+X+1 | 0X180F | telecom systems |
| CRC-16 | X16+X15+X2+ 1 | 0X18005 | Bisync, Modbus, USB, ANSI X3.28, SIA DC-07, many others; also known as CRC-16 and CRC-16-ANSI |
| CRC-CCITT | X16+X12+X5+ 1 | 0X11021 | ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS |
| CRC-32 | X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1 | 0x104C11DB7 | ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS |
| CRC-32C | X32+X28+X27+X26+X25+X23+X22+X20+X19+X18+X14+X13+X11+X10+X9+X8+X6+ 1 | 0x11EDC6F41 | ISCSI, SCTP, G. Payload, SSE4.2, Btrfs, ext4, Ceph |
4. Pre-knowledge of CRC check algorithm
Before studying the CRC check algorithm, let’s review the main algorithms involved in CRC.
1. Xor
Xor, which means different is 1, same is 0, and the operation sign is ^.
0 to the 0 is 0, 0 to the 1 is 1, 1 to the 1 is 0, 1 to the 0 is 1Copy the codeXor operation has the following rules, which need to be understood.
0^x = x is 0 xor any number is equal to any number 1^x = ~x is 1 xor any number is equal to any number inverse x^x = 0, any number is equal to itself, the result is 0 A ^ b = b ^ a Commutative law A ^ (b ^c) = a ^ b ^c associative lawCopy the code2. Mod 2 addition
The main difference between modular addition and ordinary arithmetic addition is that modular addition does not carry. The specific results are as follows. 0+0 = 0, 0+1 = 1, 1+1 = 0, 1+0 = 1 and we find that the addition of modulus 2 is the same as the xor or operation. Further extrapolation, we find that the five rules of xOR operation also apply to modular 2 addition. I won’t list them all here.
3. Subtraction of module 2
The main difference between modular 2 subtraction and ordinary arithmetic subtraction is that it does not do borrowing. The specific results are as follows. 0 minus 0 is 0, 0 minus 1 is 1, 1 minus 1 is 0, 1 minus 0 is 1 and we find that the subtraction of module 2 is exactly the same as the addition of module 2 and the xor. By further deduction, we find that the five rules of xOR operation also apply to modular 2 subtraction. I won’t list them all here.
4. Modular 2 division
Modulo 2 division is different from ordinary arithmetic division, the main difference is that modulo 2 division does not borrow upward, nor does it compare the size of the same digit value of the divisor and dividend, as long as it is divided by the same digit.
5. CRC principle
CRC principle: After the K-bit information code (the target sends data), the R-bit check code is spliced to make the whole code length N bits. Therefore, this code is also called (N,K) code.
Generally speaking, it is to add a number (check code) after the information to be sent, and generate a new data to be sent to the receiver. This data requires that the generated new data be divisible by a specific number. The idea of division here is to introduce the idea of division by modulo two.
So, the specific approach of CRC check is
(1) Select a standard divisor (K bit binary data string)
(2) Add k-1 bit 0 to the end of the data to be sent (m bit), and then divide the new number (m +K-1 bit) by the above standard divisor in modulo 2 division method. The remainder obtained is the CRC check code of the data (note: the remainder must be less than the divisor by only one bit, if not, 0 will be added).
(3) Attach the check code to the original M bit data to form a new M+K-1 bit data and send it to the receiver.
(4) The receiving end divides the received data by the standard divisor. If the remainder is 0, the data is considered correct.
Note: There are two key points in CRC verification:
One is to pre-determine a binary bit string (or polynomial) used by both sender and receiver as a divisor.
Second, the original frame is divided with the above selected binary division operation, calculate FCS.
The former can be selected randomly or according to internationally accepted standards, but the highest and lowest digit must be “1”.
Sixth, the calculation of cyclic redundancy
Example:
Because the coding process of CRC-32, CRC-16, CCITT and CRC-4 is basically the same, except for the differences of the bits and the generating polynomial, the following is an example to illustrate the CRC verification code generation process.
For 1110 0101 (16#E5), specify the divisor 11011 to obtain its CRC check code, the procedure is as follows:
Using the checksum and message data calculated above, you can create code words to be transmitted.
Sometimes, we need to fill the checksum to the specified location, which involves byte order. Memcpy () is recommended for copying.
Seven, code implementation
Implementation algorithm reference network code, collation and verification, can be used directly. crc.c
/* * Sip Linux *2021.6.21 *version: 1.0.0 */
#include "crc.h"
#include <stdio.h>
typedef enum {
REF_4BIT = 4,
REF_5BIT = 5,
REF_6BIT = 6,
REF_7BIT = 7,
REF_8BIT = 8,
REF_16BIT = 16,
REF_32BIT = 32
}REFLECTED_MODE;
uint32_t ReflectedData(uint32_t data, REFLECTED_MODE mode)
{
data = ((data & 0xffff0000) > >16) | ((data & 0x0000ffff) < <16);
data = ((data & 0xff00ff00) > >8) | ((data & 0x00ff00ff) < <8);
data = ((data & 0xf0f0f0f0) > >4) | ((data & 0x0f0f0f0f) < <4);
data = ((data & 0xcccccccc) > >2) | ((data & 0x33333333) < <2);
data = ((data & 0xaaaaaaaa) > >1) | ((data & 0x55555555) < <1);
switch (mode)
{
case REF_32BIT:
return data;
case REF_16BIT:
return (data >> 16) & 0xffff;
case REF_8BIT:
return (data >> 24) & 0xff;
case REF_7BIT:
return (data >> 25) & 0x7f;
case REF_6BIT:
return (data >> 26) & 0x7f;
case REF_5BIT:
return (data >> 27) & 0x1f;
case REF_4BIT:
return (data >> 28) & 0x0f;
}
return 0;
}
uint8_t CheckCrc4(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,
const uint8_t *buffer, uint32_t length)
{
uint8_t i;
uint8_t crc;
if (refIn == true)
{
crc = init;
poly = ReflectedData(poly, REF_4BIT);
while (length--)
{
crc ^= *buffer++;
for (i = 0; i < 8; i++)
{
if (crc & 0x01)
{
crc >>= 1;
crc ^= poly;
}
else
{
crc >>= 1; }}}return crc ^ xorOut;
}
else
{
crc = init << 4;
poly <<= 4;
while (length--)
{
crc ^= *buffer++;
for (i = 0; i < 8; i++)
{
if (crc & 0x80)
{
crc <<= 1;
crc ^= poly;
}
else
{
crc <<= 1; }}}return (crc >> 4) ^ xorOut; }}uint8_t CheckCrc5(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,
const uint8_t *buffer, uint32_t length)
{
uint8_t i;
uint8_t crc;
if (refIn == true)
{
crc = init;
poly = ReflectedData(poly, REF_5BIT);
while (length--)
{
crc ^= *buffer++;
for (i = 0; i < 8; i++)
{
if (crc & 0x01)
{
crc >>= 1;
crc ^= poly;
}
else
{
crc >>= 1; }}}return crc ^ xorOut;
}
else
{
crc = init << 3;
poly <<= 3;
while (length--)
{
crc ^= *buffer++;
for (i = 0; i < 8; i++)
{
if (crc & 0x80)
{
crc <<= 1;
crc ^= poly;
}
else
{
crc <<= 1; }}}return (crc >> 3) ^ xorOut; }}uint8_t CheckCrc6(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,
const uint8_t *buffer, uint32_t length)
{
uint8_t i;
uint8_t crc;
if (refIn == true)
{
crc = init;
poly = ReflectedData(poly, REF_6BIT);
while (length--)
{
crc ^= *buffer++;
for (i = 0; i < 8; i++)
{
if (crc & 0x01)
{
crc >>= 1;
crc ^= poly;
}
else
{
crc >>= 1; }}}return crc ^ xorOut;
}
else
{
crc = init << 2;
poly <<= 2;
while (length--)
{
crc ^= *buffer++;
for (i = 0; i < 8; i++)
{
if (crc & 0x80)
{
crc <<= 1;
crc ^= poly;
}
else
{
crc <<= 1; }}}return (crc >> 2) ^ xorOut; }}uint8_t CheckCrc7(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,
const uint8_t *buffer, uint32_t length)
{
uint8_t i;
uint8_t crc;
if (refIn == true)
{
crc = init;
poly = ReflectedData(poly, REF_7BIT);
while (length--)
{
crc ^= *buffer++;
for (i = 0; i < 8; i++)
{
if (crc & 0x01)
{
crc >>= 1;
crc ^= poly;
}
else
{
crc >>= 1; }}}return crc ^ xorOut;
}
else
{
crc = init << 1;
poly <<= 1;
while (length--)
{
crc ^= *buffer++;
for (i = 0; i < 8; i++)
{
if (crc & 0x80)
{
crc <<= 1;
crc ^= poly;
}
else
{
crc <<= 1; }}}return (crc >> 1) ^ xorOut; }}uint8_t CheckCrc8(uint8_t poly, uint8_t init, bool refIn, bool refOut, uint8_t xorOut,
const uint8_t *buffer, uint32_t length)
{
uint32_t i = 0;
uint8_t crc = init;
while (length--)
{
if (refIn == true)
{
crc ^= ReflectedData(*buffer++, REF_8BIT);
}
else
{
crc ^= *buffer++;
}
for (i = 0; i < 8; i++)
{
if (crc & 0x80)
{
crc <<= 1;
crc ^= poly;
}
else
{
crc <<= 1; }}}if (refOut == true)
{
crc = ReflectedData(crc, REF_8BIT);
}
return crc ^ xorOut;
}
uint16_t CheckCrc16(uint16_t poly, uint16_t init, bool refIn, bool refOut, uint16_t xorOut,
const uint8_t *buffer, uint32_t length)
{
uint32_t i = 0;
uint16_t crc = init;
while (length--)
{
if (refIn == true)
{
crc ^= ReflectedData(*buffer++, REF_8BIT) << 8;
}
else
{
crc ^= (*buffer++) << 8;
}
for (i = 0; i < 8; i++)
{
if (crc & 0x8000)
{
crc <<= 1;
crc ^= poly;
}
else
{
crc <<= 1; }}}if (refOut == true)
{
crc = ReflectedData(crc, REF_16BIT);
}
return crc ^ xorOut;
}
uint32_t CheckCrc32(uint32_t poly, uint32_t init, bool refIn, bool refOut, uint32_t xorOut,
const uint8_t *buffer, uint32_t length)
{
uint32_t i = 0;
uint32_t crc = init;
while (length--)
{
if (refIn == true)
{
crc ^= ReflectedData(*buffer++, REF_8BIT) << 24;
}
else
{
crc ^= (*buffer++) << 24;
}
for (i = 0; i < 8; i++)
{
if (crc & 0x80000000)
{
crc <<= 1;
crc ^= poly;
}
else
{
crc <<= 1; }}}if (refOut == true)
{
crc = ReflectedData(crc, REF_32BIT);
}
return crc ^ xorOut;
}
uint32_t CrcCheck(CRC_Type crcType, const uint8_t *buffer, uint32_t length)
{
switch (crcType.width)
{
case 4:
return CheckCrc4(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,
crcType.xorOut, buffer, length);
case 5:
return CheckCrc5(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,
crcType.xorOut, buffer, length);
case 6:
return CheckCrc6(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,
crcType.xorOut, buffer, length);
case 7:
return CheckCrc7(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,
crcType.xorOut, buffer, length);
case 8:
return CheckCrc8(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,
crcType.xorOut, buffer, length);
case 16:
return CheckCrc16(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,
crcType.xorOut, buffer, length);
case 32:
return CheckCrc32(crcType.poly, crcType.init, crcType.refIn, crcType.refOut,
crcType.xorOut, buffer, length);
}
return 0;
}
Copy the codecrc.h
/* * Sip Linux *2021.6.21 *version: 1.0.0 */
#ifndef __CRC_H__
#define __CRC_H__
#include <stdint.h>
#include <stdbool.h>
typedef struct {
uint8_t width;
uint32_t poly;
uint32_t init;
bool refIn;
bool refOut;
uint32_t xorOut;
}CRC_Type;
uint32_t CrcCheck(CRC_Type crcType, const uint8_t *buffer, uint32_t length);
#endif
Copy the codemain.c
/* * Sip Linux *2021.6.21 *version: 1.0.0 */
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include "crc.h"
#define LENGTH 8
const uint8_t data[3][LENGTH] = {
{ 0x01.0x02.0x03.0x04.0x05.0x06.0x07.0x08 },
{ 0x01.0x02.0x04.0x08.0x10.0x20.0x40.0x80 },
{ 0xfe.0xfd.0xfb.0xf7.0xef.0xdf.0xbf.0x7f }};
typedef struct {
CRC_Type crcType;
uint32_t result[3];
}CRC_Test;
CRC_Test crc4_ITU = { { 4.0x03.0x00.true.true.0x00 }, { 0x0f.0x0a.0x0e}}; CRC_Test crc5_EPC = { {5.0x09.0x09.false.false.0x00 }, { 0x00.0x0c.0x17}}; CRC_Test crc5_ITU = { {5.0x15.0x00.true.true.0x00 }, { 0x16.0x0a.0x17}}; CRC_Test crc5_USB = { {5.0x05.0x1f.true.true.0x1f }, { 0x10.0x09.0x17}}; CRC_Test crc6_ITU = { {6.0x03.0x00.true.true.0x00 }, { 0x1d.0x30.0x00}}; CRC_Test crc7_MMC = { {7.0x09.0x00.false.false.0x00 }, { 0x57.0x30.0x5b}}; CRC_Test crc8 = { {8.0x07.0x00.false.false.0x00 }, { 0x3e.0xe1.0x36}}; CRC_Test crc8_ITU = { {8.0x07.0x00.false.false.0x55 }, { 0x6b.0xb4.0x63}}; CRC_Test crc8_ROHC = { {8.0x07.0xff.true.true.0x00 }, { 0x6b.0x78.0x93}}; CRC_Test crc8_MAXIM = { {8.0x31.0x00.true.true.0x00 }, { 0x83.0x60.0xa9}}; CRC_Test crc16_IBM = { {16.0x8005.0x0000.true.true.0x0000 }, { 0xc4f0.0x2337.0xa776}}; CRC_Test crc16_MAXIM = { {16.0x8005.0x0000.true.true.0xffff }, { 0x3b0f.0xdcc8.0x5889}}; CRC_Test crc16_USB = { {16.0x8005.0xffff.true.true.0xffff }, { 0x304f.0xd788.0x53c9}}; CRC_Test crc16_MODBUS = { {16.0x8005.0xffff.true.true.0x0000 }, { 0xcfb0.0x2877.0xac36}}; CRC_Test crc16_CCITT = { {16.0x1021.0x0000.true.true.0x0000 }, { 0xeea7.0xfe7c.0x7919}}; CRC_Test crc16_CCITT_FALSE = { {16.0x1021.0xffff.false.false.0x0000 }, { 0x4792.0x13a7.0xb546}}; CRC_Test crc16_X25 = { {16.0x1021.0xffff.true.true.0xffff }, { 0x6dd5.0x7d0f.0xfa6a}}; CRC_Test crc16_XMODEM = { {16.0x1021.0x0000.false.false.0x0000 }, { 0x76ac.0x2299.0x8478}}; CRC_Test crc16_DNP = { {16.0x3D65.0x0000.true.true.0xffff }, { 0x7bda.0x0535.0x08c4}}; CRC_Test crc32 = { {32.0x04c11db7.0xffffffff.true.true.0xffffffff }, { 0x3fca88c5.0xe0631a53.0xa4051a26}}; CRC_Test crc32_MPEG2 = { {32.0x4c11db7.0xffffffff.false.false.0x00000000 }, { 0x14dbbdd8.0x6509b4b6.0xcb09d294}};void CrcTest(CRC_Test crcTest)
{
uint32_t i;
for (i = 0; i < 3; i++)
{
printf("%08x\t%08x\r\n", CrcCheck(crcTest.crcType, data[i], LENGTH), crcTest.result[i]);
}
printf("\r\n");
}
int main(void)
{
CrcTest(crc4_ITU);
CrcTest(crc5_EPC);
CrcTest(crc5_ITU);
CrcTest(crc5_USB);
CrcTest(crc6_ITU);
CrcTest(crc7_MMC);
CrcTest(crc8);
CrcTest(crc8_ITU);
CrcTest(crc8_ROHC);
CrcTest(crc8_MAXIM);
CrcTest(crc16_IBM);
CrcTest(crc16_MAXIM);
CrcTest(crc16_USB);
CrcTest(crc16_MODBUS);
CrcTest(crc16_CCITT);
CrcTest(crc16_CCITT_FALSE);
CrcTest(crc16_X25);
CrcTest(crc16_XMODEM);
CrcTest(crc16_DNP);
CrcTest(crc32);
CrcTest(crc32_MPEG2);
return 0;
}
Copy the codePay attention to
Different CRC algorithms have different calculation results for 00H or FFH data streams. Some algorithms have check results of 00H or FFH (that is, when the storage space is initialized: all 0 or all 1, CRC check is correct), which should be avoided in application.
Complete code, background reply key [CRC] can be obtained.