 ## Cyclic Redundancy Check (CRC): bitwise, lookup table, fast crc without lookup table, reversing crc. C Implementation Using the Octave GNU Tool

### 2. Introduction

##### 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 XOR operation is used for the polynomial addition and subtraction operations. Let’s take two polynomials as an example:  ##### 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.   ### 3. Some Remarks about CRC Polynomials

##### Now some remarks about polynomials. Usually the CRC polynomial can be represented as (8): ##### This means that for CRC8, CRC16, CRC32, CRC64 we can determine the maximum size of the array: ##### CRC16: ##### CRC32: ##### CRC64: ### 4. Bitwise CRC Algorithm

##### The Bitwise CRC algorithm is easily implemented using HW. See the Figure 4-1.  ##### Input Array: ##### The C Code of the bitwise CRC algorithm:

#define CRC_POLYNOMIAL 0x…
#define CRC_BIT_NMB 8u/16u/32u/64u
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++)
{

{

crc_val <<= 1u;
crc_val ^= CRC_POLYNOMIAL;

}
else
{

crc_val <<= 1u;

}

}

}

### 5. Lookup Table Bytewise CRC Algorithm

##### 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
uint8/16/32/64 LookupTable;
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++)
{

{

crc_table_value <<= 1u;
crc_table_value ^= CRC_POLYNOMIAL;

}
else
{

crc_table_value <<= 1u;

}

}
LookupTable[index1] = crc_table_value;

}

### 6.1 Fast CRC Theory

##### Let’s introduce the notation: ##### 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): ##### Let’s introduce the notation: ##### Then: ##### Using (23) and (26): ##### Next we will use a useful formula: ### 6.2 Fast CRC Examples

##### Take the CRC polynomial h = 16 proposed by Nguyen in : #### Example 1

##### 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  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;
{

pol_x1 ^= CRC_POLYNOMIAL;

}

/* R( A(x)*x^2 ) */
pol_x2 = pol_x1 << 1u;
{

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

##### Using (33) and (36): ##### Let’s introduce the notation: ##### Then: ##### Given that the degrees of the polynomials in (45) are less than h=16, we rewrite (44): ##### C Code Implement from :

/*
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

##### 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

##### 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;

}

### 7.1 Reversing CRC16 using the method 

##### Lookup Table:

const uint16 lookupTable=
{
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
};

##### 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=
{
0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39
};

##### Let there be another modified array:

uint8 test_array_byte_corrupt=
{
0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, Byte0, Byte1
};

##### Thus we get an array with CRC16 = 0xEF6F:

uint8 test_array_byte_corrupt=
{
0x39, 0x38, 0x37, 0x36, 0x35, 0x34, 0x33, 0x9B, 0x08
};

### 7.2 Reversing CRC16 using the method 

##### 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: ##### 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: ##### 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. ##### Now we can write the inverse polynomial: ##### Then (74) in our case will take the form: ##### Realization (85) in C Code using . 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 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() */
{

ret_value <<= 1u;
ret_value ^= CRC_POLYNOMIAL;

}
else
{

ret_value <<= 1u;

}

/* crc_req*(x^16)^-1) */
{

ret_value ^= INVCRC_POLYNOMIAL;

}
crc_req <<= 1u;

}

/* R(crc_req*(x^16)^-1) + crc_current */
ret_value ^= crc_current;

return ret_value;

}

##### 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=
{
0x0031, 0x3233, 0x3435, 0x3637, 0x3839
};

##### Let there be another modified array:

uint16 test_array_corrupt=
{
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=
{
0x0039, 0x3837, 0x3635, 0x3433, 0x9B08
};

### 7.3 Reversing CRC Conclusions

• ##### CRC32 with the polynomial (19) is considered in : ### 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)

### 9. C Language crc_xxx.c/h

1. #### crc_x16_x2_x_1.c/hCRC16 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)

2. #### crc_x16_x12_x5_1.c/hCRC16 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)

3. #### crc32_0x04C11DB7.c/hCRC32 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 + 1Polynomial = 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)

4. #### crc_x64_x4_x3_x_1.c/hCRC64 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)

5. #### reverse_crc_x16_x2_x_1.c/hReverse implement for the Polynomial:x^16 + x^2 + x + 1Plynomial = 0x0007Using 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 CRC

Short Description:
Input:
crc_current = (C0, C1) = (C0 << 8u) + C1
crc_req = (P0, P1) = (P0 << 8u) + P1
ret_value = (B0, B1) = (B0 << 8u) + B1

Processing:
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 CRC

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

• ##### 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;
uint16 currentCRC = START_CRC_INIT;
uint16 stepLength = 10u;

/* Step 1 */

/* Step 2 */