I am in need of a highly optimized CRC8 algorithm. My goal is to develop a Slice-by-4 solution as known from CRC16 / CRC32. I want to keep the code as close to the solution which I am using for CRC16 posted below.
Functions to generate the CRC LookUp-Table:
void crcspeed16_genTable(crcfn16 crcfn, uint16_t table[8][256]) {
uint16_t crc;
/* generate CRCs for all single byte sequences */
for (int n = 0; n < 256; n++) {
table[0][n] = crcfn(0, &n, 1);
}
/* generate nested CRC table for future slice-by-8 lookup */
for (int n = 0; n < 256; n++) {
crc = table[0][n];
for (int k = 1; k < 8; k++) {
crc = table[0][(crc >> 8) & 0xff] ^ (crc << 8);
table[k][n] = crc;
}
}
}
uint16_t crc16(uint16_t crc, const void *in_data, uint64_t len) {
const uint8_t *data = (const uint8_t*) in_data;
for (uint64_t i = 0; i < len; i++) {
crc = crc ^ (data[i] << 8);
for (int j = 0; j < 8; j++) {
if (crc & 0x8000) {
crc = (crc << 1) ^ CRC16_POLYNOMINAL;
} else {
crc = (crc << 1);
}
}
}
return crc;
}
Call to generate the table:
crcspeed16_genTable(crc16, crc16_LUT);
Function to generate the CRC16 based on the Slice-by-4 solution:
uint16_t crc16_slice4(const void *buf, size_t len, uint16_t initialValue, uint16_t XOR_OUT) {
uint16_t crc = initialValue;
unsigned char *next = (unsigned char *)buf;
// process individual bytes until we reach an 8-byte aligned pointer
while (len && ((uintptr_t)next & 7) != 0) {
crc = crc16_LUT[0][((crc >> 8) ^ *next++) & 0xff] ^ (crc << 8);
len--;
}
// fast middle processing, 4 bytes (aligned!) per loop */
while (len >= 4) {
uint32_t n = *(uint32_t *)next;
crc = crc16_LUT[3][(n & 0xff) ^ ((crc >> 8) & 0xff)] ^
crc16_LUT[2][((n >> 8) & 0xff) ^ (crc & 0xff)] ^
crc16_LUT[1][(n >> 16) & 0xff] ^
crc16_LUT[0][n >> 24];
next += 4;
len -= 4;
}
// process remaining bytes (can't be larger than 8)
while (len) {
crc = crc16_LUT[0][((crc >> 8) ^ *next++) & 0xff] ^ (crc << 8);
len--;
}
return crc ^ XOR_OUT;
}
My aim is to adapt the algorithm to be working for CRC8 and CRC4. What I have managed so far is to change the LUT-Generator to be generating a valid first row of the LUT and process a valid CRC based on this LUT data. I am failing to adapt the middle part to calculate and utilize the full potential of the CRC table.
Adapted functions (not fully functional) for CRC8: Table generation:
void crcspeed8_genTable(crcfn8 crcfn, uint8_t table[8][256]) {
uint16_t crc;
/* generate CRCs for all single byte sequences */
for (int n = 0; n < 256; n++) {
table[0][n] = crcfn(0, &n, 1);
}
/* generate nested CRC table for future slice-by-8 lookup */
for (int n = 0; n < 256; n++) {
crc = table[0][n];
for (int k = 1; k < 8; k++) {
//crc = table[0][crc] ^ crc;
crc = table[0][(crc >> 4) & 0x0f] ^ (crc << 4);
table[k][n] = crc;
}
}
}
uint8_t crc8(uint8_t crc, const void *in_data, uint64_t len) {
const uint8_t *data = (const uint8_t*) in_data;
for (uint64_t i = 0; i < len; i++) {
//crc = crc ^ (data[i] << 8);
crc = crc ^ data[i];
for (int j = 0; j < 8; j++) {
if (crc & 0x80) {
crc = (crc << 1) ^ CRC8_POLYNOMINAL;
} else {
crc = (crc << 1);
}
}
}
return crc;
}
CRC calculation:
uint8_t crc8_slice4(const void *buf, size_t len, uint8_t initialValue, uint8_t XOR_OUT) {
uint8_t crc = initialValue;
unsigned char *next = (unsigned char *)buf;
// process individual bytes until we reach an 8-byte aligned pointer
while (len && ((uintptr_t)next & 7) != 0) {
printf("\nAlign processing");
crc = crc8_LUT[0][crc ^ *next++];
len--;
}
//fast middle processing, 4 bytes (aligned!) per loop
while (len >= 4) {
printf("\nSlice processing");
uint32_t n = *(uint32_t *)next;
//This part should be adopted to work for CRC8
/*crc = crc8_LUT[3][(n & 0xff) ^ crc] ^
crc8_LUT[2][(n >> 8) & 0xff] ^
crc8_LUT[1][(n >> 16) & 0xff] ^
crc8_LUT[0][n >> 24]; */
uint32_t n0 = (n & 0xFF) ^ crc;
uint32_t n1 = (n >> 8) & 0xFF;
uint32_t n2 = (n >> 16) & 0xFF;
uint32_t n3 = (n >> 24);
//Working multi step for CRC 4 only using first row of LUT
uint8_t crc0 = crc8_LUT[0][crc ^ n0];
uint8_t crc1 = crc8_LUT[0][crc0 ^ n1];
uint8_t crc2 = crc8_LUT[0][crc1 ^ n2];
uint8_t crc3 = crc8_LUT[0][crc2 ^ n3];
crc = crc3;
next += 4;
len -= 4;
}
// process remaining bytes (can't be larger than 8)
while (len) {
printf("\nRemain processing");
crc = crc8_LUT[0][crc ^ *next++];
len--;
}
return crc ^ XOR_OUT;
}
I tried to change the functions to be working for CRC8 but I can't figure out the middle part. A solution explaining the general approach to generating Look-Up-Tables for various CRCs (4/8/16/24/32...) would also be highly appreciated. Thanks for hopefully pointing me in the right direction.
You didn't provide your polynomial, initial value, or final exclusive or. With those (and that the CRC in your case is not reflected), you can use crcany to generate the code for you.
Here is an example for little-endian slice-by-4:
#include <stddef.h>
#include <stdint.h>
#define table_byte table_word[0]
static uint8_t const table_word[][256] = {
{0xbd, 0x92, 0xe3, 0xcc, 0x01, 0x2e, 0x5f, 0x70, 0xea, 0xc5, 0xb4, 0x9b, 0x56,
0x79, 0x08, 0x27, 0x13, 0x3c, 0x4d, 0x62, 0xaf, 0x80, 0xf1, 0xde, 0x44, 0x6b,
0x1a, 0x35, 0xf8, 0xd7, 0xa6, 0x89, 0xce, 0xe1, 0x90, 0xbf, 0x72, 0x5d, 0x2c,
0x03, 0x99, 0xb6, 0xc7, 0xe8, 0x25, 0x0a, 0x7b, 0x54, 0x60, 0x4f, 0x3e, 0x11,
0xdc, 0xf3, 0x82, 0xad, 0x37, 0x18, 0x69, 0x46, 0x8b, 0xa4, 0xd5, 0xfa, 0x5b,
0x74, 0x05, 0x2a, 0xe7, 0xc8, 0xb9, 0x96, 0x0c, 0x23, 0x52, 0x7d, 0xb0, 0x9f,
0xee, 0xc1, 0xf5, 0xda, 0xab, 0x84, 0x49, 0x66, 0x17, 0x38, 0xa2, 0x8d, 0xfc,
0xd3, 0x1e, 0x31, 0x40, 0x6f, 0x28, 0x07, 0x76, 0x59, 0x94, 0xbb, 0xca, 0xe5,
0x7f, 0x50, 0x21, 0x0e, 0xc3, 0xec, 0x9d, 0xb2, 0x86, 0xa9, 0xd8, 0xf7, 0x3a,
0x15, 0x64, 0x4b, 0xd1, 0xfe, 0x8f, 0xa0, 0x6d, 0x42, 0x33, 0x1c, 0x5e, 0x71,
0x00, 0x2f, 0xe2, 0xcd, 0xbc, 0x93, 0x09, 0x26, 0x57, 0x78, 0xb5, 0x9a, 0xeb,
0xc4, 0xf0, 0xdf, 0xae, 0x81, 0x4c, 0x63, 0x12, 0x3d, 0xa7, 0x88, 0xf9, 0xd6,
0x1b, 0x34, 0x45, 0x6a, 0x2d, 0x02, 0x73, 0x5c, 0x91, 0xbe, 0xcf, 0xe0, 0x7a,
0x55, 0x24, 0x0b, 0xc6, 0xe9, 0x98, 0xb7, 0x83, 0xac, 0xdd, 0xf2, 0x3f, 0x10,
0x61, 0x4e, 0xd4, 0xfb, 0x8a, 0xa5, 0x68, 0x47, 0x36, 0x19, 0xb8, 0x97, 0xe6,
0xc9, 0x04, 0x2b, 0x5a, 0x75, 0xef, 0xc0, 0xb1, 0x9e, 0x53, 0x7c, 0x0d, 0x22,
0x16, 0x39, 0x48, 0x67, 0xaa, 0x85, 0xf4, 0xdb, 0x41, 0x6e, 0x1f, 0x30, 0xfd,
0xd2, 0xa3, 0x8c, 0xcb, 0xe4, 0x95, 0xba, 0x77, 0x58, 0x29, 0x06, 0x9c, 0xb3,
0xc2, 0xed, 0x20, 0x0f, 0x7e, 0x51, 0x65, 0x4a, 0x3b, 0x14, 0xd9, 0xf6, 0x87,
0xa8, 0x32, 0x1d, 0x6c, 0x43, 0x8e, 0xa1, 0xd0, 0xff},
{0xfa, 0x13, 0x07, 0xee, 0x2f, 0xc6, 0xd2, 0x3b, 0x7f, 0x96, 0x82, 0x6b, 0xaa,
0x43, 0x57, 0xbe, 0xdf, 0x36, 0x22, 0xcb, 0x0a, 0xe3, 0xf7, 0x1e, 0x5a, 0xb3,
0xa7, 0x4e, 0x8f, 0x66, 0x72, 0x9b, 0xb0, 0x59, 0x4d, 0xa4, 0x65, 0x8c, 0x98,
0x71, 0x35, 0xdc, 0xc8, 0x21, 0xe0, 0x09, 0x1d, 0xf4, 0x95, 0x7c, 0x68, 0x81,
0x40, 0xa9, 0xbd, 0x54, 0x10, 0xf9, 0xed, 0x04, 0xc5, 0x2c, 0x38, 0xd1, 0x6e,
0x87, 0x93, 0x7a, 0xbb, 0x52, 0x46, 0xaf, 0xeb, 0x02, 0x16, 0xff, 0x3e, 0xd7,
0xc3, 0x2a, 0x4b, 0xa2, 0xb6, 0x5f, 0x9e, 0x77, 0x63, 0x8a, 0xce, 0x27, 0x33,
0xda, 0x1b, 0xf2, 0xe6, 0x0f, 0x24, 0xcd, 0xd9, 0x30, 0xf1, 0x18, 0x0c, 0xe5,
0xa1, 0x48, 0x5c, 0xb5, 0x74, 0x9d, 0x89, 0x60, 0x01, 0xe8, 0xfc, 0x15, 0xd4,
0x3d, 0x29, 0xc0, 0x84, 0x6d, 0x79, 0x90, 0x51, 0xb8, 0xac, 0x45, 0xfd, 0x14,
0x00, 0xe9, 0x28, 0xc1, 0xd5, 0x3c, 0x78, 0x91, 0x85, 0x6c, 0xad, 0x44, 0x50,
0xb9, 0xd8, 0x31, 0x25, 0xcc, 0x0d, 0xe4, 0xf0, 0x19, 0x5d, 0xb4, 0xa0, 0x49,
0x88, 0x61, 0x75, 0x9c, 0xb7, 0x5e, 0x4a, 0xa3, 0x62, 0x8b, 0x9f, 0x76, 0x32,
0xdb, 0xcf, 0x26, 0xe7, 0x0e, 0x1a, 0xf3, 0x92, 0x7b, 0x6f, 0x86, 0x47, 0xae,
0xba, 0x53, 0x17, 0xfe, 0xea, 0x03, 0xc2, 0x2b, 0x3f, 0xd6, 0x69, 0x80, 0x94,
0x7d, 0xbc, 0x55, 0x41, 0xa8, 0xec, 0x05, 0x11, 0xf8, 0x39, 0xd0, 0xc4, 0x2d,
0x4c, 0xa5, 0xb1, 0x58, 0x99, 0x70, 0x64, 0x8d, 0xc9, 0x20, 0x34, 0xdd, 0x1c,
0xf5, 0xe1, 0x08, 0x23, 0xca, 0xde, 0x37, 0xf6, 0x1f, 0x0b, 0xe2, 0xa6, 0x4f,
0x5b, 0xb2, 0x73, 0x9a, 0x8e, 0x67, 0x06, 0xef, 0xfb, 0x12, 0xd3, 0x3a, 0x2e,
0xc7, 0x83, 0x6a, 0x7e, 0x97, 0x56, 0xbf, 0xab, 0x42},
{0xd1, 0xdf, 0xcd, 0xc3, 0xe9, 0xe7, 0xf5, 0xfb, 0xa1, 0xaf, 0xbd, 0xb3, 0x99,
0x97, 0x85, 0x8b, 0x31, 0x3f, 0x2d, 0x23, 0x09, 0x07, 0x15, 0x1b, 0x41, 0x4f,
0x5d, 0x53, 0x79, 0x77, 0x65, 0x6b, 0x3e, 0x30, 0x22, 0x2c, 0x06, 0x08, 0x1a,
0x14, 0x4e, 0x40, 0x52, 0x5c, 0x76, 0x78, 0x6a, 0x64, 0xde, 0xd0, 0xc2, 0xcc,
0xe6, 0xe8, 0xfa, 0xf4, 0xae, 0xa0, 0xb2, 0xbc, 0x96, 0x98, 0x8a, 0x84, 0x20,
0x2e, 0x3c, 0x32, 0x18, 0x16, 0x04, 0x0a, 0x50, 0x5e, 0x4c, 0x42, 0x68, 0x66,
0x74, 0x7a, 0xc0, 0xce, 0xdc, 0xd2, 0xf8, 0xf6, 0xe4, 0xea, 0xb0, 0xbe, 0xac,
0xa2, 0x88, 0x86, 0x94, 0x9a, 0xcf, 0xc1, 0xd3, 0xdd, 0xf7, 0xf9, 0xeb, 0xe5,
0xbf, 0xb1, 0xa3, 0xad, 0x87, 0x89, 0x9b, 0x95, 0x2f, 0x21, 0x33, 0x3d, 0x17,
0x19, 0x0b, 0x05, 0x5f, 0x51, 0x43, 0x4d, 0x67, 0x69, 0x7b, 0x75, 0x1c, 0x12,
0x00, 0x0e, 0x24, 0x2a, 0x38, 0x36, 0x6c, 0x62, 0x70, 0x7e, 0x54, 0x5a, 0x48,
0x46, 0xfc, 0xf2, 0xe0, 0xee, 0xc4, 0xca, 0xd8, 0xd6, 0x8c, 0x82, 0x90, 0x9e,
0xb4, 0xba, 0xa8, 0xa6, 0xf3, 0xfd, 0xef, 0xe1, 0xcb, 0xc5, 0xd7, 0xd9, 0x83,
0x8d, 0x9f, 0x91, 0xbb, 0xb5, 0xa7, 0xa9, 0x13, 0x1d, 0x0f, 0x01, 0x2b, 0x25,
0x37, 0x39, 0x63, 0x6d, 0x7f, 0x71, 0x5b, 0x55, 0x47, 0x49, 0xed, 0xe3, 0xf1,
0xff, 0xd5, 0xdb, 0xc9, 0xc7, 0x9d, 0x93, 0x81, 0x8f, 0xa5, 0xab, 0xb9, 0xb7,
0x0d, 0x03, 0x11, 0x1f, 0x35, 0x3b, 0x29, 0x27, 0x7d, 0x73, 0x61, 0x6f, 0x45,
0x4b, 0x59, 0x57, 0x02, 0x0c, 0x1e, 0x10, 0x3a, 0x34, 0x26, 0x28, 0x72, 0x7c,
0x6e, 0x60, 0x4a, 0x44, 0x56, 0x58, 0xe2, 0xec, 0xfe, 0xf0, 0xda, 0xd4, 0xc6,
0xc8, 0x92, 0x9c, 0x8e, 0x80, 0xaa, 0xa4, 0xb6, 0xb8},
{0x84, 0x31, 0xc1, 0x74, 0x0e, 0xbb, 0x4b, 0xfe, 0xbf, 0x0a, 0xfa, 0x4f, 0x35,
0x80, 0x70, 0xc5, 0xf2, 0x47, 0xb7, 0x02, 0x78, 0xcd, 0x3d, 0x88, 0xc9, 0x7c,
0x8c, 0x39, 0x43, 0xf6, 0x06, 0xb3, 0x68, 0xdd, 0x2d, 0x98, 0xe2, 0x57, 0xa7,
0x12, 0x53, 0xe6, 0x16, 0xa3, 0xd9, 0x6c, 0x9c, 0x29, 0x1e, 0xab, 0x5b, 0xee,
0x94, 0x21, 0xd1, 0x64, 0x25, 0x90, 0x60, 0xd5, 0xaf, 0x1a, 0xea, 0x5f, 0x73,
0xc6, 0x36, 0x83, 0xf9, 0x4c, 0xbc, 0x09, 0x48, 0xfd, 0x0d, 0xb8, 0xc2, 0x77,
0x87, 0x32, 0x05, 0xb0, 0x40, 0xf5, 0x8f, 0x3a, 0xca, 0x7f, 0x3e, 0x8b, 0x7b,
0xce, 0xb4, 0x01, 0xf1, 0x44, 0x9f, 0x2a, 0xda, 0x6f, 0x15, 0xa0, 0x50, 0xe5,
0xa4, 0x11, 0xe1, 0x54, 0x2e, 0x9b, 0x6b, 0xde, 0xe9, 0x5c, 0xac, 0x19, 0x63,
0xd6, 0x26, 0x93, 0xd2, 0x67, 0x97, 0x22, 0x58, 0xed, 0x1d, 0xa8, 0x45, 0xf0,
0x00, 0xb5, 0xcf, 0x7a, 0x8a, 0x3f, 0x7e, 0xcb, 0x3b, 0x8e, 0xf4, 0x41, 0xb1,
0x04, 0x33, 0x86, 0x76, 0xc3, 0xb9, 0x0c, 0xfc, 0x49, 0x08, 0xbd, 0x4d, 0xf8,
0x82, 0x37, 0xc7, 0x72, 0xa9, 0x1c, 0xec, 0x59, 0x23, 0x96, 0x66, 0xd3, 0x92,
0x27, 0xd7, 0x62, 0x18, 0xad, 0x5d, 0xe8, 0xdf, 0x6a, 0x9a, 0x2f, 0x55, 0xe0,
0x10, 0xa5, 0xe4, 0x51, 0xa1, 0x14, 0x6e, 0xdb, 0x2b, 0x9e, 0xb2, 0x07, 0xf7,
0x42, 0x38, 0x8d, 0x7d, 0xc8, 0x89, 0x3c, 0xcc, 0x79, 0x03, 0xb6, 0x46, 0xf3,
0xc4, 0x71, 0x81, 0x34, 0x4e, 0xfb, 0x0b, 0xbe, 0xff, 0x4a, 0xba, 0x0f, 0x75,
0xc0, 0x30, 0x85, 0x5e, 0xeb, 0x1b, 0xae, 0xd4, 0x61, 0x91, 0x24, 0x65, 0xd0,
0x20, 0x95, 0xef, 0x5a, 0xaa, 0x1f, 0x28, 0x9d, 0x6d, 0xd8, 0xa2, 0x17, 0xe7,
0x52, 0x13, 0xa6, 0x56, 0xe3, 0x99, 0x2c, 0xdc, 0x69}
};
// This code assumes that integers are stored little-endian.
uint8_t crc8autosar_word(uint8_t crc, void const *mem, size_t len) {
unsigned char const *data = mem;
if (data == NULL)
return 0;
while (len && ((ptrdiff_t)data & 0x3)) {
len--;
crc = table_byte[crc ^ *data++];
}
size_t n = len >> 2;
for (size_t i = 0; i < n; i++) {
uint32_t word = crc ^ ((uint32_t const *)data)[i];
crc = table_word[3][word & 0xff] ^
table_word[2][(word >> 8) & 0xff] ^
table_word[1][(word >> 16) & 0xff] ^
table_word[0][word >> 24];
}
data += n << 2;
len &= 3;
while (len) {
len--;
crc = table_byte[crc ^ *data++];
}
return crc;
}
The convention for this code is that when called with mem == NULL, crc is ignored and the initial CRC, i.e. the CRC of an empty message, is returned.