CRC32 half-byte/nibble lookup-table algorithm

[HwAoRrDk]

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

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.

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.

Code: [Select]

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

Code: [Select]

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.

[eutectique]

The table here is rather different:

Code: [Select]

// 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
};


[eutectique]

Here is some useful theory and use cases: https://github.com/Michaelangel007/crc32

[HwAoRrDk]

The table here 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 one I was previously referencing. But I suppose that's not surprising given that the accompanying blog post is in Russian, so English search terms would never have matched it.

Using that table and adapting my code accordingly, it works!

Code: [Select]

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?