Site map  

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.

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>


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"


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>

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.
Note: Not all CRCs initialise on a bunch of ones (such as 0xFF, 0xFFFF, 0xFFFFFF or 0xFFFFFFFF). A lot initialise on zero. Some on something different entirely.

Calculate a 24-bit CRC

In the CRC calculation:

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: