Skip to content

Instantly share code, notes, and snippets.

@aurelj
Created July 6, 2014 16:36
  • Star 4 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save aurelj/270bb8af82f65fa645c1 to your computer and use it in GitHub Desktop.
Simple CRC-16-MCRF4XX C implementation.
#include <stdint.h>
#include <stddef.h>
uint16_t crc16_mcrf4xx(uint16_t crc, uint8_t *data, size_t len)
{
if (!data || len < 0)
return crc;
while (len--) {
crc ^= *data++;
for (int i=0; i<8; i++) {
if (crc & 1) crc = (crc >> 1) ^ 0x8408;
else crc = (crc >> 1);
}
}
return crc;
}
@dazhbog
Copy link

dazhbog commented Jun 23, 2018

Thanks for this!

@mudgek1
Copy link

mudgek1 commented Apr 9, 2019

Consider this instead of your 8-bit loop:

#include <stdint.h>
#include <stddef.h>

uint16_t crc16_mcrf4xx(uint16_t crc, uint8_t *data, size_t len)
{
    uint8_t t;
    uint8_t L;
    if (!data || len < 0)
        return crc;

    while (len--) {
        crc ^= *data++;
        L = crc ^ (crc << 4);
        t = (L << 3) | (L >> 5);
        L ^= (t & 0x07);
        t = (t & 0xF8) ^ (((t << 1) | (t >> 7)) & 0x0F) ^ (uint8_t)(crc >> 8);
        crc = (L << 8) | t;
    }
    return crc;
}

@mudgek1
Copy link

mudgek1 commented Jan 6, 2020

I found this strategy on a site with various CRC techniques about 10 years ago. I ported it from assembly, and rearranged it to run in the fewest clock cycles (I was using an 8051 with 256 bytes of RAM), and have been using it ever since. It's about half the speed of a 256-byte lookup table, but many times faster than a bit-by-bit CRC. That's all I've got for an explanation - it is now optimized beyond my comprehension. At least it isn't as impossible to understand as the Fast Inverse Square Root or abusive as Duff's Device!

@alielbashir
Copy link

Thanks @mudgek1 , the version you posted works great

@ratin3
Copy link

ratin3 commented Jul 9, 2021

mudgek1 works great! Thanks

@CrystalPower
Copy link

Consider this instead of your 8-bit loop:

#include <stdint.h>
#include <stddef.h>

uint16_t crc16_mcrf4xx(uint16_t crc, uint8_t *data, size_t len)
{
    uint8_t t;
    uint8_t L;
    if (!data || len < 0)

Should not this be if (!data || len <= 0). I am not sure if should calculate CRC if length passed == 0;

    return crc;

while (len--) {
    crc ^= *data++;
    L = crc ^ (crc << 4);
    t = (L << 3) | (L >> 5);
    L ^= (t & 0x07);
    t = (t & 0xF8) ^ (((t << 1) | (t >> 7)) & 0x0F) ^ (uint8_t)(crc >> 8);
    crc = (L << 8) | t;
}
return crc;

}

@Kenzimatic
Copy link

You're right, it should be if (!data || len <= 0) for performance, but the functionality comes out the same because len-- returns 0 so it skips down to return crc; anyways. The CRC of an empty array is valid and should equal the CRC start value.

@MrJake222
Copy link

With just -O1 there is not much difference. Tested with 12 bytes:

$ g++ -O0 crc.cpp -o crc
$ ./crc                 
10M runs crc16_mcrf4xx: 945.964 ms
10M runs crc16_mcrf4xx_fast: 509.515 ms
$ g++ -O1 crc.cpp -o crc
$ ./crc                 
10M runs crc16_mcrf4xx: 12.783 ms
10M runs crc16_mcrf4xx_fast: 12.746 ms

1024 bytes:

$ g++ -O0 crc.cpp -o crc
$ ./crc                 
10k runs crc16_mcrf4xx: 352.066 ms
10k runs crc16_mcrf4xx_fast: 73.724 ms
$ g++ -O1 crc.cpp -o crc
$ ./crc                 
10k runs crc16_mcrf4xx: 0.016 ms
10k runs crc16_mcrf4xx_fast: 0.015 ms

@maxfreu
Copy link

maxfreu commented Nov 10, 2023

The initial implementation and the one by @mudgek1 produce different results for some numbers (e.g. 0x76). Which one is correct?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment