EEVblog Electronics Community Forum
Products => Computers => Programming => Topic started by: HwAoRrDk on December 08, 2023, 11:04:05 pm
-
I've currently got some code that calculates a POSIX-compatible (aka 'cksum') CRC32 with a bitwise algorithm, but in order to get some speed improvement I'd like to try and change to using a lookup table. I don't want to use up too much space for the LUT, so I'm attempting to use an algorithm variant that uses a smaller 16-element half-byte/nibble table. I'm attempting to follow the algorithm as described here: https://create.stephan-brumme.com/crc32/#half-byte (https://create.stephan-brumme.com/crc32/#half-byte)
But I can't for the life of me figure what I'm supposed to do to adapt the technique to calculate a POSIX CRC32 instead of a common regular CRC32. |O
My previous bitwise code is as follows. This is just the meat of it: the function that updates the CRC value for a new byte of data. This works fine and is verified as correct.
uint32_t crc32_posix_update(uint32_t crc, uint8_t data) {
crc ^= (uint32_t)data << 24;
for(uint8_t i = 0; i < 8; i++) {
if(crc & 0x80000000UL) {
crc = (crc << 1) ^ 0x04C11DB7UL;
} else {
crc = (crc << 1);
}
}
return crc;
}
For the LUT approach, I took my table values from the calculator here: http://www.sunshine2k.de/coding/javascript/crc/crc_js.html (http://www.sunshine2k.de/coding/javascript/crc/crc_js.html). I gather that for the smaller half-byte table, you simply take every 16th value (i.e. entries 0, 16, etc.) from the larger table given.
static const uint32_t crc32_posix_lut[16] = {
0x00000000, 0x4C11DB70, 0x9823B6E0, 0xD4326D90, 0x34867077, 0x7897AB07, 0xACA5C697, 0xE0B41DE7,
0x690CE0EE, 0x251D3B9E, 0xF12F560E, 0xBD3E8D7E, 0x5D8A9099, 0x119B4BE9, 0xC5A92679, 0x89B8FD09
};
uint32_t crc32_posix_update_lut(uint32_t crc, uint8_t data) {
crc = crc32_posix_lut[(crc ^ data) & 0x0F] ^ (crc >> 4);
crc = crc32_posix_lut[(crc ^ (data >> 4)) & 0x0F] ^ (crc >> 4);
return crc;
}
But this doesn't work, and gives incorrect results. :(
I've tried various changes:
- When calculating the table index, XOR the data byte with MSB of the CRC instead - i.e. crc32_posix_lut[((crc >> 24) ^ data) & 0x0F].
- Left-shift CRC by 4 instead of right - i.e. (crc << 4).
- Both of the above together.
At this stage I just don't know whether my code is wrong, my table is wrong, or both are wrong! To be honest, I haven't quite wrapped my head around exactly what the table-lookup code is doing and why, so it may be something obvious I'm overlooking.
Any help very much appreciated.
-
The table here (https://alex-exe.ru/files/source/stm32_crc32.c) is rather different:
// Nibble lookup table for 0x04C11DB7 polynomial
const unsigned long sw_crc32_by_nibble_table[16] = {
0x00000000,0x04C11DB7,0x09823B6E,0x0D4326D9,
0x130476DC,0x17C56B6B,0x1A864DB2,0x1E475005,
0x2608EDB8,0x22C9F00F,0x2F8AD6D6,0x2B4BCB61,
0x350C9B64,0x31CD86D3,0x3C8EA00A,0x384FBDBD
};
-
Here is some useful theory and use cases: https://github.com/Michaelangel007/crc32
-
The table here (https://alex-exe.ru/files/source/stm32_crc32.c) is rather different:
Thank you! :-+ I spent ages looking for some other implementation to reference - even just another source for the table - but couldn't find anything apart from non-POSIX implementations like the Brumme (https://create.stephan-brumme.com/crc32/#half-byte) one I was previously referencing. But I suppose that's not surprising given that the accompanying blog post (https://alex-exe.ru/radio/stm32/stm32-crc32/) is in Russian, so English search terms would never have matched it.
Using that table and adapting my code accordingly, it works! :D
static const uint32_t crc32_posix_lut[16] = {
0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD
};
uint32_t crc32_posix_update_lut(uint32_t crc, uint8_t data) {
crc ^= (uint32_t)data << 24;
crc = (crc << 4) ^ crc32_posix_lut[crc >> 28];
crc = (crc << 4) ^ crc32_posix_lut[crc >> 28];
return crc;
}
I already figured that, like my existing code, XOR-ing the data byte with the MSB of the CRC is important, and had started to figure that I need to shift by 28 to get the most-significant nibble of the CRC to use as the index into the LUT, but hadn't yet put the pieces together in the right order. But as I had the wrong table (or, rather, the wrong selection of values in the table), I was still on the wrong track.
One thing that puzzles me is that this table is the first 16 elements of the larger byte-wise table, not every 16th element like the Brumme implementation... Why?