Cook your own CRC

This document provides some info on the Cyclic Redundancy Check and how to make your own (using the C programming language).
This document is inspired by Cyclic redundancy check and CRC16-CCITT
You may want to read them first.

Introduction

On a very basic level, a CRC considers your data to be one very large number, divides this 'number' by something called a polynomial and appends the remainder (dividend / devisor = quotient + remainder) of this division to the data. It does this using little more then XOR, Shift and compare.

The X-es thingy

As an example the CCITT 16-bit CRC polynomial;

X¹⁶ + X¹² + X⁵ + 1

To figure this out, write down the bits and number them from right to left, starting with zero.

         1            0
6  5432 1098  7654 3210
x  xxxx xxxx  xxxx xxxx

Now assign a one to bit numbers 16, 12, 5 and 0 ('1' actually means X⁰) and make the rest zero;

         1            0
6  5432 1098  7654 3210
1  0001 0000  0010 0001

This corresponds to hex 11021;

         1            0
6  5432 1098  7654 3210
1  0001 0000  0010 0001
1     1    0    2     1

A lot of documents refer to '0x1021' instead. This is because they leave out the leftmost bit, which is always '1'.
Note that for a 16-bit CRC you need a 17-bit polynomial.

Calculate a 16-bit CRC

First append two NULL-bytes (16 '0' bits) to the data.
Next, fill a variable which holds an unsigned 32-bit integer with 16 ones, or 0xFFFF;

0000 0000  0000 0000  1111 1111  1111 1111

Shift this one bit to the left (yielding 0x1FFFE) and fill the rightmost bit with the leftmost data bit ('d');

0000 0000  0000 0001  1111 1111  1111 111d

If the 17th bit from the right (marked '↓') is '1', XOR with the the polynomial. Otherwise, don't;

                   ↓
0000 0000  0000 0001  1111 1111  1111 111d
                   p  pppp pppp  pppp pppp
                   ----------------------- XOR
                   0  xxxx xxxx  xxxx xxxx

Since this bit is '1' in the polynomial, XOR will always make this bit zero (1 XOR 1 = 0).
And if this bit already was '0', there is no XOR with the polynomial so it remains '0'.

Shift this again and repeat;

0000 0000  0000 000x  xxxx xxxx  xxxx xxxd
                   p  pppp pppp  pppp pppp
                                           XOR

'x' is the result of the previous XOR, 'd' the next data bit.

After the last shift and data bit insertion;

0000 0000  0000 000x  xxxx xxxx  xxxx xxx0
                   p  pppp pppp  pppp pppp
                   ----------------------- XOR
                   0  cccc cccc  cccc cccc

The '0' at the right is the last of the 16 zeros that we appended to the data.
'cccc cccc cccc cccc' is the CRC.

CRC of 'A'

Below an example using the letter 'A' (01000001);

0xFFFF          A       0x0000
1111111111111111010000010000000000000000

11111111111111110 ← 1st bit of 'A'
10001000000100001 ← polynomial
----------------- XOR
01110111111011111    0xEFDF ← Result of 1st XOR
 11101111110111111 ← 2nd bit of 'A'
 10001000000100001
 ----------------- XOR
 01100111110011110    0xCF9E
  11001111100111100
  10001000000100001
  ----------------- XOR
  01000111100011101    0x8F1D
   10001111000111010
   10001000000100001
   ----------------- XOR
   00000111000011011    0x0E1B
    00001110000110110
     00011100001101100
      00111000011011000
       01110000110110001 ← Last bit of 'A'
        11100001101100010  ←  1st bit of 0x0000
        10001000000100001
        ----------------- XOR
        01101001101000011    0xD343
         11010011010000110
         10001000000100001
         ----------------- XOR
         01011011010100111    0xB6A7
          10110110101001110
          10001000000100001
          ----------------- XOR
          00111110101101111    0x7D6F
           01111101011011110
            11111010110111100
            10001000000100001
            ----------------- XOR
            01110010110011101    0xE59D
             11100101100111010
             10001000000100001
             ----------------- XOR
             01101101100011011    0xDB1B
              11011011000110110
              10001000000100001
              ----------------- XOR
              01010011000010111    0xA617
               10100110000101110
               10001000000100001
               ----------------- XOR
               00101110000001111    0x5C0F
                01011100000011110
                 10111000000111100
                 10001000000100001
                 ----------------- XOR
                 00110000000011101    0x601D
                  01100000000111010
                   11000000001110100
                   10001000000100001
                   ----------------- XOR
                   01001000001010101    0x9055
                    10010000010101010
                    10001000000100001
                    ----------------- XOR
                    00011000010001011    0x308B
                     00110000100010110
                      01100001000101100
                       11000010001011000 ← Last bit of 0x0000
                       10001000000100001
                       ----------------- XOR
                       01001010001111001    0x9479 ← Result

1111111111111111010000010000000000000000
0xFFFF          A       0x0000         ↑ Stop

The total number of steps is the number of ones at the beginning (16), plus the number of zeros at the end (16) minus the length of the polynomial (17) plus the number of data bits (eight per byte): 15 + 8 * Number_Of_Data_Bytes.
However, there is one additional step at the start of CRC calculation, which changes 0xFFFF to 0x1FFFE. So the total number of steps is 16 + 8 * Number_Of_Data_Bytes. Which is convenient if the CRC length is a whole number of bytes (16 = 2 * 8).

The program

This can be done with two nested loops. The outer one reads the bytes (including the two appended NULL-bytes), the inner one processes the bits, and runs eight times per byte;

Initialise variables

Outer loop:
{
	Read byte
	Set inner loop counter to zero
	Inner loop:
	{
		Shift
		Insert data
		XOR
		Increment inner loop counter
	}
	Increment outer loop counter
}

Present result

The program below reads text from stdin and calculates a 16-bit CRC (one per line of text). Modify to suit your needs.

#include <stdio.h>
#include <string.h>


/*
*    Calculates CCITT 16-bit CRC
*
*    Copyright (c) 2022 - 2023 R.J. van der Putten, Leiden, Holland, 
*    rob at sput dot nl.
* 
*    This program is free software; you can redistribute it and/or modify
*    it under the terms of the GNU General Public License version 3 as
*    published by the Free Software Foundation.
* 
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details.
*/


int main(void)
{
    char line[4096];
    int i, j, len;
    unsigned int c, poly, shft;

    c = 0;
    i = 0;
    j = 0;
    len = 0;
    shft = 0;
    memset(line, 0, 4096);

    /*
    *  Calculate CCITT 16-bit CRC
    *
    *    16   12   5
    *   X  + X  + X  + 1
    *
    *  17 bits
    *
    *     6 5432 1098 7654 3210
    *     1 0001 0000 0010 0001
    *     1    1    0    2    1
    */

    poly = 0x11021;

    while (fgets(line, 4088, stdin)) {
	i = 0;
	/*  Cleanup  */
	len = strlen(line) - 1;
	if (line[len] == 10) {
	    line[len] = 0;
	    len--;
	}
	if (line[len] == 13) {
	    line[len] = 0;
	    len--;
	}
	len++;
	/*  Pad for length of CRC  */
	line[len] = 0;
	len++;
	line[len] = 0;
	len++;

	shft = 0xFFFF;
	while (i < len) {
	    c = (unsigned int) ((unsigned char) line[i]);
	    j = 0;
	    while (j < 8) {
		shft = shft << 1;    /*  1st time this is 1FFFE  */
		if ((c & 0x80) != 0) {
		    /*  Data msb is one; make shft lsb one  */
		    shft = shft | 1;
		}
		c = c << 1;
		if ((shft & 0x10000) != 0) {
		    /* 1  xxxx xxxx  xxxx xxxx */
		    shft = shft ^ poly;
		}
		j++;
	    }
	    i++;
	}

	printf("%04X\n", shft);
    }

    return(0);
}

Legend

For those unfamiliar with C;

len--	len = len - 1
len++	len = len + 1
<<	Logical Shift to left
\|	Bitwise OR
&	Bitwise AND
^	Bitwise XOR

Compile with;

cc -O2 -Wall -o crc16 crc16.c

Table based calculation

Inspired by 'A painless guide to crc error detection algorithms' a table based calculation below. Modify to suit your needs.

#include <stdio.h>
#include <string.h>
#include "crc16tab.h"


/*
*    Calculates CRC
*
*    Copyright (c) 2022 - 2023 R.J. van der Putten, Leiden, Holland, 
*    rob at sput dot nl.
* 
*    This program is free software; you can redistribute it and/or modify
*    it under the terms of the GNU General Public License version 3 as
*    published by the Free Software Foundation.
* 
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details.
*/


int main(void)
{
    char line[4096];
    unsigned char t;
    int i, len;
    unsigned int r;

    memset(line, 0, 4096);

    while (fgets(line + 2, 4088, stdin)) {
	i = 0;
	/*  Cleanup  */
	len = strlen(line) - 1;
	if (line[len] == 10) {
	    line[len] = 0;
	    len--;
	}
	if (line[len] == 13) {
	    line[len] = 0;
	    len--;
	}
	len++;
	/*  Pad for length of CRC  */
	line[len] = 0;
	len++;
	line[len] = 0;
	len++;

	t = 0;

	r = 0xFFFF;

	while (i < len) {
	    /*  Shift CRC width - 8  */
	    t = (r >> 8) & 0xFF;
	    r = (r << 8) | (unsigned char) line[i];
	    r ^= crctab[t];
	    r = r & 0xFFFF;
	    i++;
	}

	printf("Crc: %04X\n", r);
    }

    return(0);
}

This program has a much smaller loop. And there is only one loop; Processing the data byte by byte. The per bit loop is missing. Which is more efficient.
For this program to work, you need a CRC lookup table;

/*  CCITT 16-bit CRC calculation table  */

unsigned int crctab[] = { \
	0x0000, 0x1021, 0x2042, 0x3063,
	0x4084, 0x50A5, 0x60C6, 0x70E7,
	0x8108, 0x9129, 0xA14A, 0xB16B,
	0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
	0x1231, 0x0210, 0x3273, 0x2252,
	0x52B5, 0x4294, 0x72F7, 0x62D6,
	0x9339, 0x8318, 0xB37B, 0xA35A,
	0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
	0x2462, 0x3443, 0x0420, 0x1401,
	0x64E6, 0x74C7, 0x44A4, 0x5485,
	0xA56A, 0xB54B, 0x8528, 0x9509,
	0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
	0x3653, 0x2672, 0x1611, 0x0630,
	0x76D7, 0x66F6, 0x5695, 0x46B4,
	0xB75B, 0xA77A, 0x9719, 0x8738,
	0xF7DF, 0xE7FE, 0xD79D, 0xC7BC,
	0x48C4, 0x58E5, 0x6886, 0x78A7,
	0x0840, 0x1861, 0x2802, 0x3823,
	0xC9CC, 0xD9ED, 0xE98E, 0xF9AF,
	0x8948, 0x9969, 0xA90A, 0xB92B,
	0x5AF5, 0x4AD4, 0x7AB7, 0x6A96,
	0x1A71, 0x0A50, 0x3A33, 0x2A12,
	0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E,
	0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
	0x6CA6, 0x7C87, 0x4CE4, 0x5CC5,
	0x2C22, 0x3C03, 0x0C60, 0x1C41,
	0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD,
	0xAD2A, 0xBD0B, 0x8D68, 0x9D49,
	0x7E97, 0x6EB6, 0x5ED5, 0x4EF4,
	0x3E13, 0x2E32, 0x1E51, 0x0E70,
	0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC,
	0xBF1B, 0xAF3A, 0x9F59, 0x8F78,
	0x9188, 0x81A9, 0xB1CA, 0xA1EB,
	0xD10C, 0xC12D, 0xF14E, 0xE16F,
	0x1080, 0x00A1, 0x30C2, 0x20E3,
	0x5004, 0x4025, 0x7046, 0x6067,
	0x83B9, 0x9398, 0xA3FB, 0xB3DA,
	0xC33D, 0xD31C, 0xE37F, 0xF35E,
	0x02B1, 0x1290, 0x22F3, 0x32D2,
	0x4235, 0x5214, 0x6277, 0x7256,
	0xB5EA, 0xA5CB, 0x95A8, 0x8589,
	0xF56E, 0xE54F, 0xD52C, 0xC50D,
	0x34E2, 0x24C3, 0x14A0, 0x0481,
	0x7466, 0x6447, 0x5424, 0x4405,
	0xA7DB, 0xB7FA, 0x8799, 0x97B8,
	0xE75F, 0xF77E, 0xC71D, 0xD73C,
	0x26D3, 0x36F2, 0x0691, 0x16B0,
	0x6657, 0x7676, 0x4615, 0x5634,
	0xD94C, 0xC96D, 0xF90E, 0xE92F,
	0x99C8, 0x89E9, 0xB98A, 0xA9AB,
	0x5844, 0x4865, 0x7806, 0x6827,
	0x18C0, 0x08E1, 0x3882, 0x28A3,
	0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E,
	0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
	0x4A75, 0x5A54, 0x6A37, 0x7A16,
	0x0AF1, 0x1AD0, 0x2AB3, 0x3A92,
	0xFD2E, 0xED0F, 0xDD6C, 0xCD4D,
	0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9,
	0x7C26, 0x6C07, 0x5C64, 0x4C45,
	0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
	0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C,
	0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8,
	0x6E17, 0x7E36, 0x4E55, 0x5E74,
	0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
};

Below the program which generates this table. Note that the first '1' in the polynomial is now missing!
So the first few entries in the table above are in fact multples of the polynomial (0x1021); 0x0000, 0x1021, 0x2042, 0x3063, 0x4084.
A table like this always has 256 entries. The width of each entry is the width of the CRC. So that's 256 16-bit numbers for a 16-bit CRC and 256 32-bit numbers for a 32-bit CRC.

#include <stdio.h>


/*
*    Generates CCITT 16-bit CRC calculation table
*
*    Copyright (c) 2022 - 2023 R.J. van der Putten, Leiden, Holland, 
*    rob at sput dot nl.
* 
*    This program is free software; you can redistribute it and/or modify
*    it under the terms of the GNU General Public License version 3 as
*    published by the Free Software Foundation.
* 
*    This program is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*    GNU General Public License for more details.
*/


int main(void)
{
    int i, j;
    unsigned int r;

    unsigned int poly = 0x1021;

    printf("unsigned int crctab[] = { \\\n\t");
    for (i = 0; i < 256; i++) {
	/*  CRC Width - 8  */
	r = i << 8;
	for (j = 0; j < 8; j++) {
	    if ((r & 0x8000) != 0) {
		/*  1xxx xxxx  xxxx xxxx  */
		r = (r < 1) ^ poly;
	    } else {
		r = r << 1;
	    }
	    r = r & 0xFFFF;
	}
	if (i != 0) {
	    if ((i % 4) == 0)
		printf("\n\t");
	    else
		printf(" ");
	}
	printf("0x%04X", r);
	if(i != 255)
	    printf(",");
    }
    printf("\n};\n");

    return(0);
}

Compile this program;

cc -O2 -Wall -o gen16tab gen16tab.c

Generate the table;

gen16tab > crc16tab.h

Compile the CRC generation program;

cc -O2 -Wall -o calcrc16 calcrc16.c

You can modify these programs for other polynomials. The table based calculation however, only works when the CRC length is a whole number of bytes.

CRC Confusion

Not all CRCs initialise on a bunch of ones (such as 0xFFFF, 0xFFFFFF or 0xFFFFFFFF). A lot initialise on zero. Some on something different entirely. And some start calculating right away.
And not all append a bunch of zeros. Some append nothing at all.
Some start with the least- instead of the most significant bit.
And some flip the bits of the CRC.
The cksum program for instance, works from the end of the file to the beginning and then includes the length of the file. Next it flips the bits of the CRC.
Obviously, the exact implementation determines the resulting CRC. So different implementations may use the same polynomial or the same lookup table, but yield a different CRC!

The table below shows the CRC for the string '123456789', using the above method. So initialise with '-1', append 0, MSb first and don't flip the CRC;

CRC Results for string '123456789'
Bits	Hex Polynomial	Hex CRC
16	11021	E5CC
24	17B01BD	2E4A1E
32	104C11DB7	373C5870
48	1000000000007	7374549C8E9D

'cksum' yields 930766865 or 0x377A6011 for the the same string, in spite of the fact that it uses 0x104C11DB7 as it's polynomial.
Some claim that 0x29B1 is the result applying polynomial 0x11021 to '123456789'. This is however, incorrect; A result may be 0x29B1, but not using the above method.
This document literally shows you every bit of the calculation: 16-Bit CRC of 123456789.

Calculate a 24-bit CRC

In the CRC calculation:

Append 24 NULL-bytes to the data
Initialise 'r' with 24 ones: r = 0xFFFFFF;
Shift 16 instead of 8 bits (CRC width - 8): t = (r >> 16) & 0xFF;
Limit the size of 'r' to 24 bits: r = r & 0xFFFFFF;
Two more hex digits in the printf: printf("Crc: %06X\n", r);

The loop;

    while (i < len) {
	/*  Shift CRC width - 8  */
	t = (r >> 16) & 0xFF;
	r = (r << 8) | (unsigned char) str[i];
	r ^= crctab[t];
	r = r & 0xFFFFFF;
	i++;
    }

In the table generation:

Shift 16 instead of 8 bits (CRC width - 8): r = i << 16;
Check for a one byte higher msb (1xxx xxxx xxxx xxxx xxxx xxxx): if ((r & 0x800000) != 0) {
Limit the size of 'r' to 24 bits: r = r & 0xFFFFFF;
Two more hex digits in the printf: printf("0x%06X", r);

Calculate a 32-bit CRC

The properties;

Uses polynomial 0x104C11DB7 (0x04C11DB7)
Initialise with 0xFFFFFFFF
Most significant bit first
Append 0x00000000
Don't flip the CRC

In the CRC calculation:

Append 32 NULL-bytes to the data; 0x00000000
Initialise 'r' with 32 ones: r = 0xFFFFFFFF;
Shift 24 instead of 16 bits (CRC width - 8): t = (r >> 24) & 0xFF;
The size is already limited to 32-bits. So there is no need for 'r = r & 0xFFFFFFFF'.
Two more hex digits in the printf: printf("Crc: %08X\n", r);

Note: There are other CRC implementations using this polynomial!

The loop;

    while (i < len) {
	/*  Shift CRC width - 8  */
	t = (char) ((r >> 24) & 0xFF);
	r = (r << 8) | (unsigned char) line[i];
	r ^= crctab[t];
	i++;
    }

The complete program: calcrc32.c
The lookup table: crc32tab.h

In the table generation:

Shift 24 instead of 16 bits (CRC width - 8): r = i << 24;
Check for a one byte higher msb (1xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx): if ((r & 0x80000000) != 0) {
The size is already limited to 32-bits. So there is no need for 'r = r & 0xFFFFFFFF'.
Two more hex digits in the printf: printf("0x%08X", r);

Generate the table: gen32tab.c

Modify to suit your needs;
You can use the same table for different ways of using polynomial 0x04C11DB7.