Reducing a CRC32 value to 16 or 8 bit

Question

In a message framing scheme I want to secure packets with a CRC error detection. Those packets are sent over TCP connection.

For small packets with a length smaller than 16 bytes, I'd choose CRC8. For packets smaller than 4096 bytes a CRC16 algorithm. For larger packets the CRC32 algorithm.

The most attractive CRC implementation currently is the CRC32C because of hardware support (at least on some Intel CPUs). But there are no special instructions for 8bit and 16bit CRCs.

My question is now: is it possible to reduce the 32Bit value of the CRC32C algorithm to a 16 or 8 bit value, without hurting the error detection performance in comparison to native CRC16 or CRC8 algorithms?

An example:

char buffer[256];
...
uint32_t crc32 = compute_crc32c_of_block( buffer, 256 );
uint16_t fake_crc16 = ( crc32 >> 16 ) ^ crc32;
uint8_t fake_crc8 = ( fake_crc16 >> 8 ) ^ fake_crc16;

Is fake_crc8 as good as a real CRC8 implementation?

Thanks in advance.

Interesting question. I just wonder, does reducing payload size by 3 bytes really have any return on investment? Taking into account runtime impact of handling special cases (I assume you will have different struct definitions), byte alignment instead of dword alignment, etc.? — Denis Itskovich
Yes, packets are byte-aligned but internal offsets of members are aligned to the requirements of the respective data type. With header compression some (mostly signaling) packets may shrink as small as 2 bytes, using an additional 4-byte check value for these seems a little excessive. The protocol should impose minimal framing overhead for usage on slow mobile connections i.e. GSM where all bandwidth should be given for actual payload. — Markus Fangerau

Mark Adler Mark Adler · Accepted Answer · 2014-03-12T15:36:24

The low 8 bits of a 32-bit CRC will not have as good error-correcting properties as an 8-bit CRC, e.g. the assurance of detecting burst errors. However it may be good enough for your application, depending the characteristics of the noise source. If you have a good number of bit errors with correlation in their location, then you should use a real CRC. If you have either rare bit flips or lots of gross errors, then a portion of a CRC would likely work just as well.

There is no substitute for testing to see how they perform.

Reducing a CRC32 value to 16 or 8 bit

1 Answers