CODEWITHSUNDEEP
crc
Markus Fangerau
Markus Fangerau

Reputation: 31

Reducing a CRC32 value to 16 or 8 bit

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.

Upvotes: 3

Views: 3672

Answers (2)

Radzor
Radzor

Reputation: 194

If you can specify the polynomial in the hardware CRC then padding it with zeros for bits that you don't want will result in a CRC that also has zeros at those bit positions. Then you simply discard them.

Using default data from the calculator 0x31 0x32 0x33 0x34 0x35 0x36 0x37 0x38 0x39 http://www.sunshine2k.de/coding/javascript/crc/crc_js.html) initial value 0x0, final xor 0x0 - here is the example

  • CRC8 with 0x7 poly is 0xF4
  • CRC16 with 0x700 poly is 0xF400
  • CRC32 with 0x07000000 is 0xF4000000

Now, the problem is that the hardware may not support this kind of polynomial. For example hardware 16bit SPI hardware CRC calculator in STM32 processors only supports odd polynomials. 0xF4 is odd, but 0xF400 is even and it seemed to produce garbage.

Upvotes: 1

Mark Adler
Mark Adler

Reputation: 112374

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.

Upvotes: 5

Related Questions