Cyclic Redundancy Check (CRC): bitwise, lookup table, fast crc without lookup table, reversing crc. C Implementation Using the Octave GNU Tool
1. Abbreviation
DSP – Digital Signal Processing
CRC – Cyclic Redundancy Check / Code
XOR – Exclusive OR with the truth table:
0 + 0 = 0 ^ 0 = 0
1 + 0 = 1 ^ 0 = 1
0 + 1 = 0 ^ 1 = 1
1 + 1 = 1 ^ 1 = 0
+ XOR command
or
^ XOR command
or
^ degree, for example, x^3 + x^2 + x + 1
2. Introduction
Digital Signal Processing applications shall ensure reliable data transmission or storage. For it the data block is provided with a checksum, which is formed by a special hash function. It turns out that simple summation or logical AND does not lead to the formation of an optimal checksum. In this article I will consider the Cyclic Redundancy Check (CRC) hash function. This checksum is formed by dividing the polynomials.
Data stored in computer memory or transmitted via communication channels can be interpreted as polynomials. Consider an array of two bytes:
All data on the computer is stored in binary format. Let’s write these bits together and interpret this data as the coefficients of the polynomial:
The coefficients of a polynomial take only two values 0 or 1. For such polynomials the operations of addition, subtraction, multiplication and division with the remainder are defined.
-
The XOR operation is used for the polynomial addition and subtraction operations. Let’s take two polynomials as an example:
Add (2) and (3):
Subtract (2) – (3) and the result is gotten the same as by adding because the XOR operation is also used:
-
Multiply the polynomials (2) and (3):
-
The division of polynomials with a remainder is the most important operation for the CRC algorithm. Let’s take a polynomial (1) and divide it by a polynomial:
See the Figure 2-1:
How is the CRC algorithm working? h-bits of zeros are added to the end of the array where h is the degree of the divisor polynomial. Next the array polynomial is divided by the CRC polynomial and the remainder of the division is taken as the CRC value. In our example, the CRC polynomial is: x^8 + x^4 + x^3 + x^2 + 1 and the degree of the polynomial is h=8. We need to add 8 bits of zeros (1 byte) to the end of the array. Thus the CRC algorithm will perform the operations shown in Figure 2-2. As a result we get the value CRC8 = 0x34.
Notes:
-
It is possible to construct a CRC algorithm without the physical addition of zeros to the end of the array. The zeros addition is hidden in the implementation of the algorithm itself. See the description below
-
It is convenient to use CRC8, CRC16, CRC32, CRC64 in the software implementation, which is associated with the Byte/Word organization of most microprocessors. In this article I will give examples of CRC16, CRC32, CRC64. You can download the C Code of these implementations
-
There are several possible CRC implementations:
-
Bitwise implement. Calculations are done bitwise which requires a lot of calculation time. The variant is useful for understanding the algorithm but not for practical use in the SW applications.
Note: In other side the CRC with a HW implementation is uses a bitwise method
-
Lookup Table Method. Byte/Nibble-wise implementation.
Byte-wise method requires saving an array of 256 numbers. The CRC8: 256 bytes, CRC16: 256×16 bit words (512 bytes), CRC32: 256×32 bit words (1KB), CRC64: 256×64 bit words (2KB). This is usually the fastest method of CRC implementation.
The Nibble-wise method requires saving an array of 16 numbers. The CRC8:16 bytes, CRC16: 16×16 bit words (32 bytes), CRC32: 16×32 bit words (64 bytes), CRC64: 16×64 bit words (128 bytes). I don’t like the nibble-wise algorithm and will not describe the method here. -
Nguyen in [3], using the features of some polynomials, showed the possibility of developing a Fast CRC Algorithm. Usually the algorithm has less speed as the lookup table method but it does not require saving the lookaup table. In my article I will give examples of such an implementation
-
-
To write polynomials is used a binary or hex representation. As mentioned above the CRC applies divisor polynomial degree 8, 16, 32, 64. But to store such a polynomial 9, 17, 33, 65 bits are needed since a polynomial of h degree has x^h, …, x^0 and (h+1) coefficients. On the other hand the coefficient for the highest degree (x^h) is always 1 and it can be discarded when writing a polynomial in bit /hex format.
For example:
-
Ross N. Williams in [1] developed the CRC specification which is used by many developers:
Name – the name of the algorithm for example “CCITT“
Width – the degree of the polynomial for example: 8, 16, 32, 64
Polynomial – is represented in bit or hex format for example:
0001 0000 0010 0001 or 0x1021 which corresponds to the polynomial x^16 + x^12 + x^5 + 1Init – the initial value of the CRC
RefIn – boolean values FALSE / TRUE.
FALSE: processing starts with the highest bits in the byte which have a higher degree
TRUE: processing starts with the lowest bits in the byte which are assigned a higher degreeRefOut – boolean values FALSE / TRUE.
FALSE: the result of the calculations is passed unchanged to the next XorOut step
TRUE: the bits are passed to the next step in a mirror-reversed formXorOut – after calculation the CRC an XOR operation is performed with some template value for example: 0xFFFF for CRC16 (all CRC bits are inverted). If the template value is 0x0000 then the CRC value is passed to the output without changing
Check – here is the result of calculating the CRC for the array consisting of 9 bytes of data: 0x31 0x32 0x33 0x34 0x35 0x36 0x37 0x38 0x39
Note: this array is an ASCII codes of the number: 1 2 3 4 5 6 7 8 9In my article I will use a simple specification:
Name: “Name“
Width: 8 or 16 or 32 or 64
Polynomial: 0xXXXX
Init: 0x0 (initial value 0)
RefIn: FALSE (processing starts with the highest bits!)
RefOut: FALSE (sending bits to the output without mirroring!)
XorOut: 0x0 (the output CRC value is transmitted unchanged!)
Check: 0xXXXXNote: Sometimes the working array has a form of complex structures or words: 16 bits or 32 bits or 64 bits and CRC processing is carried out by byte. In this case it is also important to choose the byte order in the structure or word, for example: big-endian (from Motorola) or little-endian (from Intel). This information is not available in the specification
-
We have defined the operations of addition, subtraction and multiplication over binary polynomials above. Mathematicians call such a set of polynomials a ring given on the Galois field GF(2). GF(2) means that the polynomials use coefficients 0 or 1. These polynomials can be used to construct various Galois fields that solve many complex coding problems. You can find out more about this in [6]
3. Some Remarks about CRC Polynomials
The choice of the divisor polynomial in the CRC algorithm is a mathematical task and is solved by mathematicians. Therefore I recommend using standard polynomials. Nevertheless there are several considerations that I would like to mention here.
The data array is provided with a CRC checksum, which usually has the size:
CRC8 – 1 byte
CRC16 – 2 bytes
CRC32 – 4 bytes
CRC64 – 8 bytes
There are many modified arrays of the same size that have the same CRC value, but using a longer checksum reduces the likelihood that after errors occur in the array we will get the same CRC value and will not notice changes in our data. If you have the opportunity to use a longer CRC – use it!
Now some remarks about polynomials. Usually the CRC polynomial can be represented as (8):
The correct choice of the CRC polynomial ensures the recognition of the following errors:
-
(x + 1) provides recognition of an odd number of bit errors. This means that if there is an error in one, three, five, etc. bits of our array then our CRC check always recognizes it
-
The polynomial (x^(h-1) + … + 1) is selected so as to recognize at least up to two isolated bit errors in a bit array of size 2^(h-1) – 1. If we translate this into bytes then:
This means that for CRC8, CRC16, CRC32, CRC64 we can determine the maximum size of the array:
In this case the checksum value is also included in the size of the array in bytes. Therefore the CRC8 can be used for an array with size up to 14 bytes, and the CRC16 can be used for an array with size up to 4093 bytes etc.
-
Burst-error-detecting with the length up to h bits. It means that CRC8 will be recognized up to 8 burst error bits, CRC16 – up to 16 burst error bits, CRC32 – up to 32 burst error bits and CRC64 – up to 64 burst error bits
Here are some standard CRC polynomials:
CRC8:
CRC16:
CRC32:
CRC64:
For more information about the selection and analysis of polynomials, you can see in the works: [1], [2], [3], [6]
4. Bitwise CRC Algorithm
The Bitwise CRC algorithm is easily implemented using HW. See the Figure 4-1.
A bit stream of divisible polynomial coefficients is come to the HW input starting with the highest degrees and ending with h = 8 zeros at the end of the bit stream. After the bit stream passes through this scheme the CRC value will remain in the register starting with the lowest degrees. You can choose any test array / data stream yourself and check the correctness of this scheme based on the shift register. The feedback circuits correspond to the CRC polynomial. In our example: the highest degree x^8 comes to the degrees: x^4, x^3, x^2, x^0.
The simplicity of the HW CRC implementation brings to use the CRC frequently at the hardware level. Many microprocessors have an HW block for accelerated CRC calculation. The CRC HW shall be configured: the CRC size, the polynomial, Init., RefIn, RefOut, XorOut, etc. After it an array is sent to the HW input and the CRC is read at the HW output.
Let’s now return to the software implementation of bitwise CRC method. Usually the CRC algorithm is used in which it is not necessary to add zeros to the end of the array specifically. This is hidden in the implementation of the algorithm itself. Take for example an array of two bytes 0x32, 0x33 and we will calculate CRC8 with a polynomial
x^8 + x^4 + x^3 + x^2 + 1. Here we use the same example as in Figure 2-2.
Input Array:
CRC calculation:
-
CRC = 0x0 – initialization value
-
Step 1: first byte 0x32 processing
-
CRC = CRC ^ Byte1 = 0000 0000 ^ 0011 0010 = 0011 0010
-
CRC: 8 times (polynomial degree) of the left shift with analysis of the high bit, if the high bit is 1 then XOR with the polynomial value (0x1D) after the left shift
CRC:
0110 0100 <= Shift
1100 1000 <= Shift
1000 1101 <= Shift, XOR 0x1D = 0001 1101
0000 0111 <= Shift, XOR 0x1D = 0001 1101
0000 1110 <= Shift
0001 1100 <= Shift
0011 1000 <= Shift
0111 0000 <= ShiftCRC = 0x70 = 0111 0000 CRC result for the Byte1
-
-
Step 2: second byte 0x33 processing
-
CRC = CRC ^ Byte2 = 0111 0000 ^ 0011 0011 = 0100 0011
-
CRC: 8 times (polynomial degree) of the left shift with analysis of the high bit if the high bit is 1 then XOR with the polynomial value (0x1D) after the left shift
CRC:
1000 0110 <= Shift
0001 0001 <= Shift, XOR 0x1D = 0001 1101
0010 0010 <= Shift
0100 0100 <= Shift
1000 1000 <= Shift
0000 1101 <= Shift, XOR 0x1D = 0001 1101
0001 1010 <= Shift
0011 0100 <= ShiftCRC = 0x34 = 0011 0100 CRC result for array: Byte1, Byte2
-
The next byte is not added to the right from the current CRC but is added (XOR) directly to the current CRC. This corresponds to adding h zeros to the right from the current CRC and there is no need to add h zeros to the end of the array. It happens automatically.
Here we get the same result CRC = 0x34 as in Figure 2-2.
The C Code of the bitwise CRC algorithm:
#define CRC_POLYNOMIAL 0x…
#define CRC_BIT_NMB 8u/16u/32u/64u
#define CRC_MASK (1u<< (CRC_BIT_NMB-1))
uint8/16/32/64 buffer[ARRAY_SIZE] = { 0x32, 0x33, …};
uint8/16/32/64 crc_val = 0x0;
uint16 index1;
uint16 index2;
uint16 length = ARRAY_SIZE;
for(index1 = 0; index1 < length; index1++)
{
crc_val ^= buffer[index1];
for(index2 = 0; index2 < CRC_BIT_NMB; index2++)
{
if(0 != (CRC_MASK & crc_val))
{
crc_val <<= 1u;
crc_val ^= CRC_POLYNOMIAL;
}
else
{
crc_val <<= 1u;
}
}
}
Notes
-
The code uses uint8/16/32/64 for variants: CRC8 = > uint8, CRC16 = > uint16, CRC32= > uint32, CRC64= > uint64
-
Basic operations of the bitwise CRC algorithm:
-
Check the highest bit in the CRC register
-
Shift the register to the left by one bit
-
If the highest bit had the value 1, then CRC = CRC ^ Polynomial
-
-
The software implementation of the bitwise algorithm requires a lot of execution time, so it is preferable to use the lookup table CRC algorithm or fast CRC algorithm. See the description below
-
You can download the C Implement of the bitwise CRC algorithm
-
For a better understanding of the bitwise algorithm I recommend to look the article [1]
5. Lookup Table Bytewise CRC Algorithm
Knowing the value of the current high CRC byte and the next byte from the input data array, we can calculate the next CRC value in one step, instead of eight bitwise steps. The method idea: the next CRC value is determined by the (CRC_high_byte^DataByte) which will be pushed out of the CRC register by the next 8 bit shifts. The (CRC_highest_byte^DataByte) will determine the number of XOR with polynomial value operations. A byte can take the values 0 … 255, which corresponds to 256 numbers that can be mapped to CRC values in the lookup table for the case when the remaining low CRC bytes are zero. Then taking the prepared values from the lookup table, we add it (XOR) with the remaining low CRC bytes and get a next CRC value.
The C Code of the lookup table bytewise CRC algorithm:
#define CRC_BIT_NMB 8u/16u/32u/64u
#define BITS_IN_BYTE_NMB 8u
uint8 buffer[ARRAY_SIZE] = { 0x32, 0x33, …};
uint8/uint16/uint32 crc_val = 0x0;
uint16 index;
for(index = 0; index < length; index++)
{
crc_val ^= ((uint32)buffer[index])<<(CRC_BIT_NMB – BITS_IN_BYTE_NMB);
crc_val = (crc_val << BITS_IN_BYTE_NMB) ^ lookupTable[(uint8)(crc_val>>
(CRC_BIT_NMB – BITS_IN_BYTE_NMB))];
}
C Code for the lookup table generation:
#define CRC_POLYNOMIAL 0x…
#define BITS_IN_BYTE_NMB 8u
#define CRC_BIT_NMB 8u/16u/32u/64u
#define CRC_MASK (1u<< (CRC_BIT_NMB-1))
uint8/16/32/64 LookupTable[256];
uint8/16/32/64 crc_table_value = 0x0;
uint16 index1;
uint16 index2;
for(index1 = 0; index1 < 256; index1++)
{
crc_table_value = index1<<(CRC_BIT_NMB – BITS_IN_BYTE_NMB);
for(index2 = 0; index2 < BITS_IN_BYTE_NMB; index2++)
{
if(0 != (CRC_MASK & crc_table_value))
{
crc_table_value <<= 1u;
crc_table_value ^= CRC_POLYNOMIAL;
}
else
{
crc_table_value <<= 1u;
}
}
LookupTable[index1] = crc_table_value;
}
Notes:
-
The code uses uint8/16/32/64 for variants: CRC8 = > uint8, CRC16 = > uint16, CRC32= > uint32, CRC64= > uint64.
-
The algorithm does not require to add the h bits of zeros since the next data byte is added (XOR) with the high byte of the CRC register.
-
The lookup table takes: CRC8 = > 256×8 bits= 256 bytes, CRC16 = > 256×16 bits= 512 bytes, CRC32 = > 256×32 bits= 1 KB, CRC64 = > 256×64 bits= 2 KB
-
This is the fastest implementation of the CRC algorithm
-
You can download the C Implementation of the bytewise CRC algorithm
-
You can download the Octave Script for the Lookup Table Generation
-
For a better understanding of the bytewise CRC algorithm I recommend to look the article [1]
6. Fast CRC Algorithm without Lookup Table
Using the features of some polynomials it is possible to develop fast CRC algorithms without using additional tables. However these algorithms are usually inferior in speed to CRC with Lookup Table. Here I will give a overview of the Nguyen article [3] which explains the operation of such algorithms.
6.1 Fast CRC Theory
Let’s introduce the notation:
This function R calculates the remainder polynomial P (x) from the division of the polynomial U (x) by M(x). In our case: U (x) is the input array polynomial, M (x) is the CRC polynomial, P (x) is the CRC register or the remainder polynomial.
It is impossible to calculate the CRC (remainder polynomial) in one step for a large array U(x), so we determine s – the number of bits for which the intermediate value of the CRC will be calculated in one step. The s can be selected 4 bits (nibble), 8 bits( byte), 1 word (16 bits, 32 bits or 64 bits). For example for the bitwise CRC algorithm: s is usually chosen equal to the length of the CRC: CRC8 = > s = 8 bits, CRC16 = > s = 16 bits, CRC32 = > s = 32 bits, CRC64 = > s = 64 bits. The CRC with lookup table algorithm: s = 8 bits (byte-wise) or s = 4 (nibble-wise)
Let the CRC polynomial M (x) have degree h:
In order not to add specially h bits of zeros to the U(x) array end, the formula (23) is used instead of (21):
The formula (23) is equivalent to adding h bit zeros to the end of the array U.
Note. Multiplying an array by x is equivalent to a left bit shift.
Now we split the array U into cells of size s:
Let’s introduce the notation:
Then:
Using (23) and (26):
Next we will use a useful formula:
The formula (28) is obvious since the polynomial A (x) M(x) is always divisible without remainder by the polynomial M(x).
Another useful property of the function R (x). If degree(A (x)) < degree (M (x)), then R (A (x)) = A (x). We will use this property frequently in the future.
Now let’s consider two cases:
-
s = h (29)
Then the (27) can be written using (28) and (29):
-
s < h (31)
We split the polynomial Pi – 1 (x) into two parts:
Probably the formula (32) looks complicated, in fact, everything is very simple. The Pi – 1(x) polynomial is the intermediate value of the CRC register from i -1 step. Here the CRC register is splitted into two parts: the higher s bits that correspond to Pi – 1, 1(x) and the lower h-s bits – correspond to Pi – 1, 2(x).
Then (27) can be written using (32) and (28):
Note:
Formulas (30) and (33) allow to construct a fast CRC algorithm.
Now let’s move on to the examples.
6.2 Fast CRC Examples
Take the CRC polynomial h = 16 proposed by Nguyen in [3]:
Example 1
h = s = 16
case: s = h
CRC Polynomial (36)
Using (30) and (36):
Note: Do not forget that the XOR operation is used for the addition and subtraction of polynomials so: x^16 + x^16 = 0
Let’s introduce the notation:
Obviously, degree (A (x)) < 16 then
Using (38) and (39), we rewrite (37) as:
At the same time:
Thus:
C Code Implement from [3] and see the crc_x16_x2_x_1.c/h:
/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: from Nguyen “Fast CRCs”, wordwise
Input
uint16* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x2_x_1_Nguyen_fast_wordwise(uint16* buffer, uint16 length, uint16 init_crc)
{
uint16 ret_crc = init_crc;
uint16 pol_x1;
uint16 pol_x2;
uint16 index;
for(index = 0; index < length; index++)
{
/* A(x) */
ret_crc ^= buffer[index];
/* R( A(x)*x^1 ) */
pol_x1 = ret_crc << 1u;
if(0 != (ret_crc & CRC_MASK))
{
pol_x1 ^= CRC_POLYNOMIAL;
}
/* R( A(x)*x^2 ) */
pol_x2 = pol_x1 << 1u;
if(0 != (pol_x1 & CRC_MASK))
{
pol_x2 ^= CRC_POLYNOMIAL;
}
/* R( A(x)*x^2 + A(x)*x^1 + A(x) )*/
ret_crc = pol_x2 ^ pol_x1 ^ ret_crc;
}
return ret_crc;
}
Example 2
h = 16
s = 8
case: s < h
CRC Polynomial (36):
Using (33) and (36):
Let’s introduce the notation:
Then:
At the same time:
Given that the degrees of the polynomials in (45) are less than h=16, we rewrite (44):
C Code Implement from [3]:
/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: from Nguyen “Fast CRCs”, bytewise
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x2_x_1_Nguyen_fast_bytewise(uint8* buffer, uint16 length, uint16 init_crc)
{
uint16 ret_crc = init_crc;
uint16 pol_Ax_mult_x2_x1_1;
const uint8 s_val = 8u;
const uint8 h_s_val = CRC_BIT_NMB – s_val; /* 16 – 8 = 8 */
uint16 index;
for(index = 0; index < length; index++)
{
/* A(x) */
pol_Ax_mult_x2_x1_1 = (ret_crc >> h_s_val) ^ buffer[index];
/* A(x)*x^2 + A(x)*x^1 + A(x) */
pol_Ax_mult_x2_x1_1 =
(pol_Ax_mult_x2_x1_1 << 2u) ^ (pol_Ax_mult_x2_x1_1 << 1u) ^ pol_Ax_mult_x2_x1_1;
/* CRC */
ret_crc = (ret_crc << s_val) ^ pol_Ax_mult_x2_x1_1;
}
return ret_crc;
}
Example 3
h = 32
s = 4
case: s < h
CRC Polynomial:
Using (33) and (47):
Let’s introduce the notation:
Then:
At the same time:
Given that the degrees of the polynomials in (51) are less than h=32, we rewrite (50):
C Code Implement:
/*
Cyclic Redundancy Check
CRC polynomial: 0x04C11DB7
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
Method: from Nguyen “Fast CRCs”, nibblewise
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint32 init_crc – initial CRC
Return
uint32 – CRC value
*/
uint32 crc32_0x04C11DB7_Nguyen_fast_nibblewise(uint8* buffer, uint16 length, uint32 init_crc)
{
uint32 ret_crc = init_crc;
uint16 index;
const uint8 s_val = 4u;
const uint8 h_s_val = CRC_BIT_NMB – s_val; /* 32 – 4 = 28 */
for(index = 0; index < length; index++)
{
/* High Nibble: A(x) */
uint32 temp = (buffer[index]>> s_val) ^ (ret_crc >> h_s_val);
/* A(x)(x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1) */
temp = (temp << 26) ^ (temp << 23) ^ (temp << 22) ^ (temp << 16) ^ (temp << 12) ^ (temp << 11) ^
(temp << 10) ^ (temp << 8) ^ (temp << 7) ^ (temp << 5) ^ (temp << 4) ^ (temp << 2) ^ (temp << 1) ^ temp;
/* Current CRC: A(x)(x^26+..+x+1) + P(x) x^4 */
ret_crc = temp ^ (ret_crc << s_val);
/* Low Nibble: A(x) */
temp = (buffer[index]& 0x0F) ^ (ret_crc >> h_s_val);
/* A(x)(x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1) */
temp = (temp << 26) ^ (temp << 23) ^ (temp << 22) ^ (temp << 16) ^ (temp << 12) ^ (temp << 11) ^
(temp << 10) ^ (temp << 8) ^ (temp << 7) ^ (temp << 5) ^ (temp << 4) ^ (temp << 2) ^ (temp << 1) ^ temp;
/* Current CRC: A(x)(x^26+..+x+1) + P(x) x^4 */
ret_crc = temp ^ (ret_crc << s_val);
}
return ret_crc;
}
Example 4
h = 64
s = 32
case: s < h
CRC Polynomial:
Using (33) and (53):
Let’s introduce the notation:
Then:
At the same time:
Given that the degrees of the polynomials in (57) are less than h=64, we rewrite (56):
C Code Implement:
/*
Cyclic Redundancy Check
CRC polynomial: x^64 + x^4 + x^3 + x + 1
Method: from Nguyen “Fast CRCs”, word32wise
Input
uint32* buffer – input buffer
uint16 length – buffer length
uint64 init_crc – initial CRC
Return
uint64 – CRC value
*/
uint64 crc_x64_x4_x3_x_1_Nguyen_fast_word32wise(uint32* buffer, uint16 length, uint64 init_crc)
{
uint64 ret_crc = init_crc;
uint16 index;
const uint8 s_val = 32u;
const uint8 h_s_val = CRC_BIT_NMB – s_val; /* 64 – 32 = 32 */
for(index = 0; index < length; index++)
{
/* A(x) */
uint64 temp = buffer[index] ^ (ret_crc >> h_s_val);
/* A(x)(x^4 + x^3 + x + 1) */
temp = (temp << 4) ^ (temp << 3) ^ (temp << 1) ^ temp;
/* Current CRC: A(x)(x^4 + x^3 + x + 1) + P(x) x^32 */
ret_crc = temp ^ (ret_crc << s_val);
}
return ret_crc;
}
The CRC64 implementation is faster than the lookup table algorithm!
Notes
-
You can download all these examples (demo C Code)
-
Not all code examples are described here. Look at the implementation of Polynomial = 0x1021 in the crc_x16_x12_x5_1.c/h and understand for yourself how it works.
6.3 Fast CRC Rules
Now we will determine in which cases fast CRC implementation is possible.
-
If there are no high degrees in the CRC polynomial (exclude the x^h from consideration), then in this case it becomes possible to implement fast CRC. For example:
-
The CRC16 polynomial (36): 0x0007. The high 3 nibbles are equal to 0. It means that there are no high degrees in the polynomial. We can choose s = 3 nibbles * 4 bits = 12 bits. But in example 2 a CRC fast variant is implemented with s = 8 bits (byte-wise)
-
The CRC32 polynomial (47) is 0x04C11DB7. The highest nibble is equal to 0. It means that there are no higher degrees in the polynomial. We can choose s = 1 nibble * 4 bits = 4 bits. In Example 3 a CRC fast variant is implemented with s = 4 (nibble-wise)
-
The CRC64 polynomial (53): 0x000000000000001B. The highest 14 nibbles are equal to 0. It means that there are no higher degrees in the polynomial. We can choose s = 14 nibble * 4 bits = 56 bits. But in Example 4 a CRC fast variant is implemented with s = 32 (32 bits word-wise)
-
-
If one (or more) of low bits are set in the polynomial (some degrees of the polynomial are present) then CRC fast algorithm can be implemented but extra bit division steps are required. See the example 1: Polynomial (36): 0x0007, s = 16. The two extra bit divisions are required in the case
Note 1
Here for the description I use a simple CRC specification, which was described above:
Name: “Name“
Width: 8 or 16 or 32 or 64
Polynomial: 0xXXXX
Init: 0x0 (initial value is 0)
RefIn: FALSE (processing starts with the highest bits!)
RefOut: FALSE (sending bits to the output without mirroring!)
XorOut: 0x0 (the output CRC value is passed unchanged!)
Check: 0xXXXX
This means that the highest bits of the CRC of the polynomial and the data array correspond to the highest degrees of the polynomial. If you use a different mirror representation of the data, then you need to make an amendment in the above description. Be careful in interpreting the data!
Note 2.
I recommend that you read the article from Nguyen [3], which will help you better understand this method.
7. Reversing CRC
My CRC description would be incomplete without the topic of Reversing CRC. Here I use the articles Anarchriz [4] and Stigge, Ploetz, Mueller, Redlich [5].
Task description.
Let there be a data array Array1 for which the CRC is calculated:
Array1: A0, A1, A2, … , An-1, CRC
Now we want to take any other array Array2 (corrupt array):
Array2: D0, D1, D2, … , Dn-1, CRC
for which the last element(s) of the Array2 are calculated so that the CRCs of both arrays (Array1 and Array2) are equal. It was shown in [4] that for CRC8 it is necessary to calculate only one the last byte, for CRC16 – the last 16-bit word (the last two bytes), for CRC32-the last 32-bit word (the last 4 bytes), for CRC64 – the last 64-bit word (the last 8 bytes).
Notes:
-
Really there is no need for the last byte(s) of the array to be calculated to get the required CRC. For example: several data in the Array1 are changed and then a “patch” of one or more bytes (depending on the size of the CRC) is put to get the required CRC value. But for the simplicity I will consider the last byte(s) of the Array2
-
Next I will consider the Reversing CRC task for the CRC16
The reversing task (for CRC16) can be reformulated a little other. See the Figure 7-1. The crc_current value is calculated CRC value for an array without the last two bytes, and the crc_requirement value is the required CRC value. We have to calculate the values of the “patch”: Byte0 and Byte1:
(Byte0, Byte1) = Function(crc_current, crc_requirement) (59)
Figure 7-1: CRC16 Reverse Task
7.1 Reversing CRC16 using the method [4]
The CRC lookup table algorithm is used here. Let’s take for example the CRC polynomial (36):
Lookup Table:
const uint16 lookupTable[256]=
{
0x0000, 0x0007, 0x000E, 0x0009, 0x001C, 0x001B, 0x0012, 0x0015, 0x0038, 0x003F,
0x0036, 0x0031, 0x0024, 0x0023, 0x002A, 0x002D, 0x0070, 0x0077, 0x007E, 0x0079,
0x006C, 0x006B, 0x0062, 0x0065, 0x0048, 0x004F, 0x0046, 0x0041, 0x0054, 0x0053,
0x005A, 0x005D, 0x00E0, 0x00E7, 0x00EE, 0x00E9, 0x00FC, 0x00FB, 0x00F2, 0x00F5,
0x00D8, 0x00DF, 0x00D6, 0x00D1, 0x00C4, 0x00C3, 0x00CA, 0x00CD, 0x0090, 0x0097,
0x009E, 0x0099, 0x008C, 0x008B, 0x0082, 0x0085, 0x00A8, 0x00AF, 0x00A6, 0x00A1,
0x00B4, 0x00B3, 0x00BA, 0x00BD, 0x01C0, 0x01C7, 0x01CE, 0x01C9, 0x01DC, 0x01DB,
0x01D2, 0x01D5, 0x01F8, 0x01FF, 0x01F6, 0x01F1, 0x01E4, 0x01E3, 0x01EA, 0x01ED,
0x01B0, 0x01B7, 0x01BE, 0x01B9, 0x01AC, 0x01AB, 0x01A2, 0x01A5, 0x0188, 0x018F,
0x0186, 0x0181, 0x0194, 0x0193, 0x019A, 0x019D, 0x0120, 0x0127, 0x012E, 0x0129,
0x013C, 0x013B, 0x0132, 0x0135, 0x0118, 0x011F, 0x0116, 0x0111, 0x0104, 0x0103,
0x010A, 0x010D, 0x0150, 0x0157, 0x015E, 0x0159, 0x014C, 0x014B, 0x0142, 0x0145,
0x0168, 0x016F, 0x0166, 0x0161, 0x0174, 0x0173, 0x017A, 0x017D, 0x0380, 0x0387,
0x038E, 0x0389, 0x039C, 0x039B, 0x0392, 0x0395, 0x03B8, 0x03BF, 0x03B6, 0x03B1,
0x03A4, 0x03A3, 0x03AA, 0x03AD, 0x03F0, 0x03F7, 0x03FE, 0x03F9, 0x03EC, 0x03EB,
0x03E2, 0x03E5, 0x03C8, 0x03CF, 0x03C6, 0x03C1, 0x03D4, 0x03D3, 0x03DA, 0x03DD,
0x0360, 0x0367, 0x036E, 0x0369, 0x037C, 0x037B, 0x0372, 0x0375, 0x0358, 0x035F,
0x0356, 0x0351, 0x0344, 0x0343, 0x034A, 0x034D, 0x0310, 0x0317, 0x031E, 0x0319,
0x030C, 0x030B, 0x0302, 0x0305, 0x0328, 0x032F, 0x0326, 0x0321, 0x0334, 0x0333,
0x033A, 0x033D, 0x0240, 0x0247, 0x024E, 0x0249, 0x025C, 0x025B, 0x0252, 0x0255,
0x0278, 0x027F, 0x0276, 0x0271, 0x0264, 0x0263, 0x026A, 0x026D, 0x0230, 0x0237,
0x023E, 0x0239, 0x022C, 0x022B, 0x0222, 0x0225, 0x0208, 0x020F, 0x0206, 0x0201,
0x0214, 0x0213, 0x021A, 0x021D, 0x02A0, 0x02A7, 0x02AE, 0x02A9, 0x02BC, 0x02BB,
0x02B2, 0x02B5, 0x0298, 0x029F, 0x0296, 0x0291, 0x0284, 0x0283, 0x028A, 0x028D,
0x02D0, 0x02D7, 0x02DE, 0x02D9, 0x02CC, 0x02CB, 0x02C2, 0x02C5, 0x02E8, 0x02EF,
0x02E6, 0x02E1, 0x02F4, 0x02F3, 0x02FA, 0x02FD
};
Let’s introduce the notation:
crc_current = (C0, C1) = (C0 << 8u) + C1 (60)
where C0 – high byte of the crc_current, C1 – low byte of the crc_current
crc_requirement = (P0, P1) = (P0 << 8u) + P1 (61)
where P0 – high byte of the crc_requirement, P1 – low byte of the crc_requirement
It is required to calculate Byte0 and Byte1:
(Byte0,Byte1) = (B0, B1) (62)
where Byte0 = B0, Byte1 = B1
Now we calculate the next CRC16 value from crc_current and Byte0 using the lookup table algorithm:
lookupTable[Position0] = lookupTable[C0^B0] = (L0, L1) = (L0 << 8u) + L1 (63)
where Position0 = C0^B0 (63a) – position in the lookup table,
(L0,L1) – value from Lookup table
Then:
crc_next(crc_current, B0) = (L0^C1, L1) (64)
Now we calculate the next CRC16 value for all array including the Byte0, Byte1:
lookupTable[Position1] = lookupTable[L0^C1^B1] = (L2, L3) = (L2 << 8u) + L3 (65)
where Position1 = L0^C1^B1 (65a) – position in the lookup table,
(L2,L3) – value from Lookup table
Then:
crc_next(crc_current, B0, B1) = crc_requirement = (L2^L1, L3) = (P0,P1) (66)
CRC16 Reverse Algorithm:
-
Using the (66):
L3 = P1 = (crc_requirement & 0xFF) (67)
where P1 is low byte of the crc_requirement and L3 is low byte in the lookup tableIn the lookup table we will find an element whose low byte is equal to P1 and determine the Position1 in the lookup table. Next we read the L2 – high byte from the lookup table
-
Using (66) can be written:
P0 = L2 ^ L1
Then we can calcilate the L1:
L1 = P0 ^ L2 = (crc_req >> 8u) ^ L2 (68)
In the lookup table we will find an element whose low byte is L1 and determine the Position0 in the lookup table. Next we read the L0 – high byte from the lookup table.
-
Using (63a), Byte0 can be calculated:
Byte0 = B0 = Position0 ^ C0 = Position0 ^ (crc_current >> 8u) (69)
-
Using (65a), Byte1 can be calculated:
Byte1 = B1 = Position1 ^ L0 ^ C1 = Position1 ^ L0 ^ (crc_current & 0xFF) (70)
Now let’s move on to the practical example from reverse_crc_x16_x2_x_1.h/c. Let there be a byte array:
uint8 test_array_byte_orig[9]=
{
0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39
};
CRC16 of the test_array_byte_orig is 0xEF6F.
Let there be another modified array:
uint8 test_array_byte_corrupt[9]=
{
0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, Byte0, Byte1
};
The task is to calculate the last two bytes (Byte0, Byte1) in the modified array to get the crc_requirement = 0xEF6F. The CRC16 of the test_array_byte_corrupt array without the last two bytes: crc_current = 0xB971. And we have to calculate the bytes Byte0 = B0 and Byte1 = B1 using the described algorithm.
-
L3 = P1 = (crc_requirement & 0xFF) = 0x6F
Find an element in the lookup table whose low byte is 0x6F.
Position1 = 121 = 0x79 and lookupTable[121] = 0x016F => L2 = 0x01
-
L1 = P0 ^ L2 = (crc_req >> 8u) ^ L2 = 0xEF ^ 0x01 = 0xEE
Now we will find an element in the lookup table whose low byte is L1 = 0xEE:
Position0 = 34 = 0x22 and lookupTable[34] = 0x00EE => L0 = 0x00
-
Byte0 = B0 = Position0 ^ C0 = Position0 ^ (crc_current >> 8u) = 0x22 ^ 0xB9 = 0x9B
-
Byte1 = B1 = Position1 ^ L0 ^ C1 = Position1 ^ L0 ^ (crc_current & 0xFF) = 0x79 ^ 0x00 ^ 0x71 = 0x08
Thus we get an array with CRC16 = 0xEF6F:
uint8 test_array_byte_corrupt[9]=
{
0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, 0x9B, 0x08
};
7.2 Reversing CRC16 using the method [5]
Let’s consider the Reversing CRC problem in common form. Using the previous notation we can write:
where
LastWord is last word in the array:
last word is one byte for CRC8
last word is 16 bits word for CRC16
last word is 32 bits word for CRC32
last word is 64 bits word for CRC64,
and
h = degree(M(x))
In the formula (71) we need to find the LastWord knowing crc_requirement, crc_current and M (x) polynomial. For the analytical solution (71) we write the formula in another form:
(72) means that the polynomials in the left part and in the right part have the same remainder from division by the polynomial M (x). Solving equation (72):
Going back to the usual form:
It is obvious that:
because degree(LastWord) < degree(M(x))
Now we can finally write:
Now in (74) it is important to understand how to find the inverse polynomial q (x):
Obviously we can write:
Let’s rewrite (76) in another form:
Thus having found q(x), we can solve the Reverse CRC task using the formula (74).
Let us now proceed to a practical example, taking the same CRC16 polynomial (36) as in the previous paragraph:
Now we calculate the inverse polynomial q (x) with respect to M (x) using (77a):
It is obvious that:
See the Figure 7-2:
It is obvious that:
Substitute (79) and (80) in (78):
Opening the brackets, we get:
Now we divide the resulting polynomial by x^16 + x^2 + x + 1, while the remainder of the division should be equal to 1. See the Figure 7-3.
Since the remainder of the division of the polynomials must be equal to 1, it is possible to make equations for finding the unknown coefficients of the inverse polynomial:
a13 + a14 + a15 = 0
a12 + a13 + a14 = 0
…
a2 + a3 + a4 = 0
a1 + a2 + a3 + a15 = 0
a0 + a1+ a2 + a14 = 0
a0 + a1 + a14 = 0
a0 + a14 + a15 = 1 (82)
Solving the system of equations (82), we obtain:
a0 = 0
a1 = 0
a2 = 0
a3 = 1
a4 = 1
a5 = 0
a6 = 1
a7 = 1
a8 = 0
a9 = 1
a10 = 1
a11 = 0
a12 = 1
a13 = 1
a14 = 0
a15 = 1 (83)
Now we can write the inverse polynomial:
Then (74) in our case will take the form:
Realization (85) in C Code using [5]. See the reverse_crc_x16_x2_x_1.c/h:
/* Defines */
#define CRC_POLYNOMIAL 0x0007u
#define INVCRC_POLYNOMIAL 0xB6D8u /* x^15+x^13+x^12+x^10+x^9+x^7+x^6+x^4+x^3 */
#define CRC_BIT_NMB 16u
#define CRC_MASK (((uint16)1u)<<(CRC_BIT_NMB-1))
#define BITS_IN_BYTE_NMB 8u
/*
Reverse or the Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: using the (x^16)^-1
from Stigge, Ploetz, Mueller, Redlich “Reversing CRC”
Input
uint16 crc_current – current CRC
uint16 crc_req – required CRC
Return
uint16 – data for obtaining the necessary CRC
*/
uint16 reverse_crc_x16_x2_x_1_bitwise(uint16 crc_current, uint16 crc_req)
{
uint16 ret_value = 0;
uint16 index;
/* R(crc_req*(x^16)^-1) */
for(index = 0; index < CRC_BIT_NMB; index++)
{
/* R() */
if(0 != (CRC_MASK & ret_value))
{
ret_value <<= 1u;
ret_value ^= CRC_POLYNOMIAL;
}
else
{
ret_value <<= 1u;
}
/* crc_req*(x^16)^-1) */
if(0 != (CRC_MASK & crc_req))
{
ret_value ^= INVCRC_POLYNOMIAL;
}
crc_req <<= 1u;
}
/* R(crc_req*(x^16)^-1) + crc_current */
ret_value ^= crc_current;
return ret_value;
}
Notes:
-
This function ‘reverse_crc_x16_x2_x_1_bitwise ()’ can be implemented a little differently by eliminating the R(…) operation with a null ret_value at the first step of the loop. See the function ‘reverse_crc_x16_x2_x_1_bitwise_var1()’ in the reverse_crc_x16_x2_x_1.c/h
-
Also the algorithm can be implemented based on reverse_lookupTable[128]. The implementation uses the 7 bits-wise and requires additional bit-wise steps. See the function reverse_crc_x16_x2_x_1_7bitswise() in the file reverse_crc_x16_x2_x_1. c/h. The table is generated using the Octave script ‘ CRC_support. m’ with the function ‘ReversingCRC_lookupTable()’
Now let’s move on to the practical example from reverse_crc_x16_x2_x_1.h/c. Let there be an array:
uint16 test_array_orig[5]=
{
0x0031, 0x3233, 0x3435, 0x3637, 0x3839
};
CRC16 for the test_array_orig is 0xEF6F.
Let there be another modified array:
uint16 test_array_corrupt[5]=
{
0x0039, 0x3837, 0x3635, 0x3433, LastWord
};
The our task is to calculate the LastWord in the array to get the required crc_requirement = 0xEF6F. The CRC16 for the array without the last LastWord: crc_current = 0xB971. Running the function reverse_crc_x16_x2_x_1_bitwise( 0xB971, 0xEF6F), we get LastWord = 0x9B08. Thus we get an array with the required CRC = 0xEF6F.
uint16 test_array_corrupt[5]=
{
0x0039, 0x3837, 0x3635, 0x3433, 0x9B08
};
7.3 Reversing CRC Conclusions
-
CRC effectively protects against interference and failures in the system, but not from intruders. If you need to protect yourself from hackers, then you need to use cryptographic methods
-
For a more detailed introduction to the Reversing CRC, use the works [4], [5].
Note. My description and code are slightly different from [4] and [5], since I use a different CRC specification
-
Examples for CRC16 and CRC32 are considered in [4]
-
CRC32 with the polynomial (19) is considered in [5]:
-
8. Octave GNU file CRC_support.m
The script allows you to generate a table for the CRC lookup table algorithm:
% CRC Table to File
% Support C-Code
% Input parameters:
% Polynomial – for example: x^16+x^12+x^5+1 => 0x1021 Note: high degree x^16 is not use
% Norder – polynomial size, possible values: 8, 16, 32
% for example: x^16+x^12+x^5+1 => Norder=16
% FileNameString – output file name
function CRC_lookupTable(Polynomial, Norder, FileNameString)
The script also allows you to generate a table for Reversing CRC lookup table:
% Reversing CRC Table with 128 words to File
% Support C-Code
% Input parameters:
% Polynomial – for example: x^16+x^2+x+1 => 0x0007 Note: high degree x^16 is not use
% Norder – polynomial size, possible values: 8, 16, 32
% for example: x^16+x^2+x+1 => Norder=16
% InversePolynomial – for example: (x^16)^-1 = x^15+x^13+x^12+x^10+x^9+x^7+x^6+x^4+x^3 => 0xB6D8
% FileNameString – output file name
function ReversingCRC_lookupTable(Polynomial, Norder, InversePolynomial, FileNameString)
Note.
The script does not work for 64 bits (CRC64). I couldn’t get a lookup table for the case. It seems to me that this is an Octave Tool bug. If you need a table for CRC64, then you can write a similar script using another programming language, for example, Python
9. C Language crc_xxx.c/h
-
crc_x16_x2_x_1.c/h
CRC16 with polynomial: x^16 + x^2 + x + 1, Polynomial = 0x0007/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: bitwise
Input
uint16* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x2_x_1_bitwise(uint16* buffer, uint16 length, uint16 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: lookup table
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x2_x_1_lookupTable(uint8* buffer, uint16 length, uint16 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: from Nguyen “Fast CRCs”, wordwise
Input
uint16* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x2_x_1_Nguyen_fast_wordwise(uint16* buffer, uint16 length, uint16 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: from Nguyen “Fast CRCs”, bytewise
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x2_x_1_Nguyen_fast_bytewise(uint8* buffer, uint16 length, uint16 init_crc) -
crc_x16_x12_x5_1.c/h
CRC16 with polynomial: x^16 + x^12 + x^5 + 1, Polynomial = 0x1021/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^12 + x^5 + 1
Method: bitwise
Input
uint16* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x12_x5_1_bitwise(uint16* buffer, uint16 length, uint16 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^12 + x^5 + 1
Method: lookup table
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x12_x5_1_lookupTable(uint8* buffer, uint16 length, uint16 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^12 + x^5 + 1
Method: from Nguyen “Fast CRCs”, nibblewise
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x12_x5_1_Nguyen_fast_nibblewise(uint8* buffer, uint16 length, uint16 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^12 + x^5 + 1
Method: from Nguyen “Fast CRCs”, bytewise
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x12_x5_1_Nguyen_fast_bytewise(uint8* buffer, uint16 length, uint16 init_crc) -
crc32_0x04C11DB7.c/h
CRC32 with polynomial:
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
Polynomial = 0x04C11DB7/*
Cyclic Redundancy Check
CRC polynomial: 0x04C11DB7
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
Method: bitwise
Input
uint32* buffer – input buffer
uint16 length – buffer length
uint32 init_crc – initial CRC
Return
uint32 – CRC value
*/
uint32 crc32_0x04C11DB7_bitwise(uint32* buffer, uint16 length, uint32 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: 0x04C11DB7
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
Method: lookup table
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint32 init_crc – initial CRC
Return
uint32 – CRC value
*/
uint32 crc32_0x04C11DB7_lookupTable(uint8* buffer, uint16 length, uint32 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: 0x04C11DB7
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
Method: from Nguyen “Fast CRCs”, nibblewise
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint32 init_crc – initial CRC
Return
uint32 – CRC value
*/
uint32 crc32_0x04C11DB7_Nguyen_fast_nibblewise(uint8* buffer, uint16 length, uint32 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: 0x4C11DB7
x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1
Method: from Nguyen “Fast CRCs”, bytewise
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint32 init_crc – initial CRC
Return
uint32 – CRC value
*/
uint32 crc32_0x04C11DB7_Nguyen_fast_bytewise(uint8* buffer, uint16 length, uint32 init_crc) -
crc_x64_x4_x3_x_1.c/h
CRC64 with polynomial: x64 + x4 + x3 + x + 1
Polynomial = 0x000000000000001B/*
Cyclic Redundancy Check
CRC polynomial: x^64 + x^4 + x^3 + x + 1
Method: bitwise
Input
uint64* buffer – input buffer
uint16 length – buffer length
uint64 init_crc – initial CRC
Return
uint64 – CRC value
*/
uint64 crc_x64_x4_x3_x_1_bitwise(uint64* buffer, uint16 length, uint64 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: x^64 + x^4 + x^3 + x + 1
Method: from Nguyen “Fast CRCs”, word32wise
Input
uint32* buffer – input buffer
uint16 length – buffer length
uint64 init_crc – initial CRC
Return
uint64 – CRC value
*/
uint64 crc_x64_x4_x3_x_1_Nguyen_fast_word32wise(uint32* buffer, uint16 length, uint64 init_crc) -
reverse_crc_x16_x2_x_1.c/h
Reverse implement for the Polynomial:
x^16 + x^2 + x + 1
Plynomial = 0x0007
Using the Inverse Polynomial:
Inverse Polynomial = 0xB6D8/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: bitwise
Input
uint16* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x2_x_1_bitwise(uint16* buffer, uint16 length, uint16 init_crc)/*
Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: lookup table
Input
uint8* buffer – input buffer
uint16 length – buffer length
uint16 init_crc – initial CRC
Return
uint16 – CRC value
*/
uint16 crc_x16_x2_x_1_lookupTable(uint8* buffer, uint16 length, uint16 init_crc)/*
Reverse or the Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: using lookup table
from Anarchriz “CRC and how to reverse it”
Input
uint16 crc_current – current CRC
uint16 crc_req – required CRC
Return
uint16 – data for obtaining the necessary CRCShort Description:
Input:
crc_current = (C0, C1) = (C0 << 8u) + C1
crc_req = (P0, P1) = (P0 << 8u) + P1
ret_value = (B0, B1) = (B0 << 8u) + B1Processing:
lookupTable[Position0] = lookupTable[C0^B0] = (L0, L1) = (L0 << 8u) + L1
crc_next = (L0^C1, L1)
lookupTable[Position1] = lookupTable[L0^C1^B1] = (L2, L3) = (L2 << 8u) + L3
crc_req = (L2^L1, L3)Calculation:
L3 = P1 = (crc_req & 0xFF) => Position1
L1 = P0 ^ L2 = (crc_req >> 8u) ^ L2 => Position0
B0 = Position0 ^ C0 = Position0 ^ (crc_current >> 8u)
B1 = Position1 ^ L0 ^ C1 = Position1 ^ L0 ^ (crc_current & 0xFF)
ret_value = (B0 << 8u) | B1
*/
uint16 reverse_crc_x16_x2_x_1_LookupTable(uint16 crc_current, uint16 crc_req)/*
Reverse or the Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: using the (x^16)^-1
from Stigge, Ploetz, Mueller, Redlich “Reversing CRC”
Input
uint16 crc_current – current CRC
uint16 crc_req – required CRC
Return
uint16 – data for obtaining the necessary CRC
*/
uint16 reverse_crc_x16_x2_x_1_bitwise(uint16 crc_current, uint16 crc_req)/*
Reverse of the Cyclic Redundancy Check
CRC polynomial: x^16 + x^2 + x + 1
Method: using the (x^16)^-1
from Stigge, Ploetz, Mueller, Redlich “Reversing CRC”
Input
uint16 crc_current – current CRC
uint16 crc_req – required CRC
Return
uint16 – data for obtaining the necessary CRCNote: 15 cycles in the loop and extra polynomial multiplication
*/
uint16 reverse_crc_x16_x2_x_1_bitwise_var1(uint16 crc_current, uint16 crc_req)/*
Reverse of the Cyclic Redundancy Check using lookupTable
CRC polynomial: x^16 + x^2 + x + 1
Method: using the (x^16)^-1
from Stigge, Ploetz, Mueller, Redlich “Reversing CRC”
The function is used the reverse_lookupTable[128]
Input
uint16 crc_current – current CRC
uint16 crc_req – required CRC
Return
uint16 – data for obtaining the necessary CRC
*/
uint16 reverse_crc_x16_x2_x_1_7bitswise(uint16 crc_current, uint16 crc_req)
Notes:
-
There are some definitions in .h files: uint8, uint16, uint32, uint64, … There are various C Compilers standards that require different definitions of the above types. It is possible that you should change these definitions for your C compiler.
-
CRC bit-wise function (crc_xxx_bitwise) works very slowly and it is better not to use them in real applications
-
Sometimes the CRC calculation for large arrays should be done in small parts. In this case an intermediate CRC value is stored, and then the next time the function is called, this value is passed as the initial one. For example:
uint8 * currentAddr = & inputBuffer[0];
uint16 currentCRC = START_CRC_INIT;
uint16 stepLength = 10u;
/* Step 1 */
currentCRC = crc_x16_x2_x_1_lookupTable(currentAddr, stepLength, currentCRC);
/* Step 2 */
currentAddr += stepLength;
currentCRC = crc_x16_x2_x_1_lookupTable(currentAddr, stepLength, currentCRC);
…
-
In my description I use a simple CRC specification:
Name: “Name“
Width: 8 or 16 or 32 or 64
Polynomial: 0xXXXX
Init: 0x0 (initial value is 0)
RefIn: FALSE (processing starts with the highest bits!)
RefOut: FALSE(sending bits to the output without mirroring!)
XorOut: 0x0 (the output CRC value is passed unchanged!)
Check: 0xXXXXIn this specification the initial CRC value is Init = 0. In real applications I do not recommend using a zero initial value, since in this case the zero data array also has a zero CRC checksum. In my practice, there were cases of failures when the working memory was reset/clear as a result of errors and the software did not notice this, since the zero CRC corresponded to the zero data of the array.
So use Init = 0xFF…FF or 0xA5…C3 or something other