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

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

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