shva shva - 5 months ago 63
C Question

Understand C code implementing CRC for Bluetooth Low Energy

Bluetooth Low Energy (BLE) uses 24-bit CRC with generator polynomial of

x^24 + x^10 + x^9 + x^6 + x^4 + x^3 + x + 1

I came across this article which implemented this CRC in C, using "the initial value of 0x555555". I paste the code as follows:

void btLeCrc(const uint8_t* data, uint8_t len, uint8_t* dst){
uint8_t v, t, d;
d = *data++;
for(v = 0; v < 8; v++, d >>= 1){
t = dst[0] >> 7;
dst[0] <<= 1;
if(dst[1] & 0x80) dst[0] |= 1;
dst[1] <<= 1;
if(dst[2] & 0x80) dst[1] |= 1;
dst[2] <<= 1;

if(t != (d & 1)){
dst[2] ^= 0x5B;
dst[1] ^= 0x06;

However, I have a hard time understanding this code. It seems a little different from the CRC code I saw in the past. For example, he used initial value of 0x555555 rather than 0x000000 or 0xffffff, and the bit manipulation looked magic to me. Can anyone explain what he was doing? Thanks!

Answer Source

Perhaps uint8_t is the only available integer type, which would explain why the author is shifting and exclusive-oring a 24-bit value, dst[0..2] 8 bits at a time.

The code implements a basic CRC shift register, where the data is shifted in a bit at a time, and the CRC exclusive-or'ed with the polynomial when the data bit exclusive-or'ed with the bit shifted out of the register is one. Note that the exclusive-or of the polynomial is only on two of the three register bytes due to the fact that the polynomial's highest power below x24 is x10.

The initialization with 0x555555 instead of 0xffffff is simply a matter of taste. Initializing with any value other than zero is a good idea, since then an initial string of zeros in the data doesn't leave the CRC unchanged.