CRC-16/CCITT-FALSE
Implement uint16_t crc16_ccitt(const uint8_t *data, size_t len) using polynomial 0x1021, initial value 0xFFFF, no input/output reflection and no final XOR (the "CCITT-FALSE" variant). The standard check value for the ASCII string "123456789" is 0x29B1.
Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.
XOR each byte into the top 8 bits of the CRC, then shift left 8 times; whenever the bit shifted out was 1, XOR in the polynomial.
#include <stdio.h>
#include <stdint.h>
#include <stddef.h>
#include <string.h>
uint16_t crc16_ccitt(const uint8_t *data, size_t len)
{
uint16_t crc = 0xFFFFu;
while (len--) {
crc ^= (uint16_t)(*data++) << 8;
for (int i = 0; i < 8; i++)
crc = (crc & 0x8000u) ? (uint16_t)((crc << 1) ^ 0x1021u) : (uint16_t)(crc << 1);
}
return crc;
}
This is polynomial long division in GF(2), processed MSB first. It costs 8 iterations per byte. A 256-entry uint16_t table (512 bytes of flash) processes a byte in one lookup: crc = (crc << 8) ^ table[(crc >> 8) ^ byte]. Many MCUs (STM32, nRF) include a hardware CRC unit.
There are dozens of "CRC-16" variants differing in polynomial, initial value, reflection and final XOR. Always confirm the parameters against a check value like the one in the test.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
const char *s = "123456789";
CHECK(crc16_ccitt((const uint8_t *)s, strlen(s)) == 0x29B1);
CHECK(crc16_ccitt(NULL, 0) == 0xFFFF);
const uint8_t a = 'A';
CHECK(crc16_ccitt(&a, 1) == 0xB915);
puts(fails ? "Some tests failed" : "All tests passed");
return fails != 0;
}