CRC Demystified

[Raven Luni]

I'm not sure if this constitutes an article so I'll post it here for now.

This is mostly for anyone working with SD cards or similar. From what I've found, CRC calculation is not the easiest of subjects to read up on, and some of the algorithms just aren't explained correctly at all, and anyone who posts code will usually give you a table-based function which is not much good for a small MCU.

The simple explanation of how to do a CRC check of any bit length:

The polynomial: Do not be afraid. This is just a number, a standard number used for a particular application. This number should be given to you in the spec for whichever application you are coding for. If not, then it is most likely a standard one which you can easily look up. The way they like to define these is as a list of powers of x - for example the standard CRC7 poly is 0x89, which is x^7 + x^3 + 1. The x is a 2 by the way, I don't know why they made it an x. So, that just means you have a number with bits 7, 3 and 1 set, which is your 'polynomial'. To make things more confusing, the highest bit isnt even included in the calculation (for a 7 bit number, the highest possible bit value is 2^6) - so the actual CRC7 polynomial is 0x09.

The calculation: This is very easy and you do it like this:

- Initialise your result to 0
- For every bit in the data sequence
- - - Shift out the MSB of the result
- - - Shift the MSB of the data into the LSB of the result
- - - If the bit shifted out of the result is a 1, then XOR the new result with the polynomial
- Finally, make sure to shift through as many 0s as there are bits in the polynomial to make sure all the data bits have come out the other end and been acted upon.


Here are my C functions based on the above. They're tried and tested and I've been using them from my raspberry pi:

// crc.h

//=================================
// SD and File System CRC Routines
// Peter Hanratty - 01/09/2013
//=================================

#define CRC7_POLY	0x09
#define CRC16_POLY	0x1021  
#define CRC32_POLY	0x04C11DB7  

char crc7 (char *aData, int aBits);
unsigned short crc16 (char *aData, int aBits);
unsigned long crc32 (char *aData, int aBits);

//=================================

char crc7 (char *aData, int aBits)
{
	int bitcount = 0;
	int bittotal = aBits + 7;
	char *dpos = aData;
	char dbyte = *dpos;
	char result = 0;
	
	while (bitcount < bittotal)
	{
		result <<= 1;
		result |= ((dbyte & 0x80) >> 7);
		if (result & 0x80)
			result ^= CRC7_POLY;
		result &= 0x7F;
		bitcount++;
		if (!(bitcount & 0x07))
		{
			dpos++;
			if (bitcount < aBits)
				dbyte = *dpos;
			else
				dbyte = 0;
		}
		else
			dbyte <<= 1;
	}
	
	return result;
}

//---------------------------------

unsigned short crc16 (char *aData, int aBits)
{
	int bitcount = 0;
	int bittotal = aBits + 16;
	char *dpos = aData;
	char dbyte = *dpos;
	unsigned short msb;
	unsigned short result = 0;
	
	while (bitcount < bittotal)
	{
		msb = result & 0x8000;
		result <<= 1;
		result |= ((dbyte & 0x80) >> 7);
		if (msb)
			result ^= CRC16_POLY;
		bitcount++;
		if (!(bitcount & 0x07))
		{
			dpos++;
			if (bitcount < aBits)
				dbyte = *dpos;
			else
				dbyte = 0;
		}
		else
			dbyte <<= 1;
	}
	
	return result;
}

//---------------------------------

unsigned long crc32 (char *aData, int aBits)
{
	int bitcount = 0;
	int bittotal = aBits + 32;
	char *dpos = aData;
	char dbyte = *dpos;
	unsigned long msb;
	unsigned long result = 0;
	
	while (bitcount < bittotal)
	{
		msb = result & 0x80000000;
		result <<= 1;
		result |= ((dbyte & 0x80) >> 7);
		if (msb)
			result ^= CRC32_POLY;
		bitcount++;
		if (!(bitcount & 0x07))
		{
			dpos++;
			if (bitcount < aBits)
				dbyte = *dpos;
			else
				dbyte = 0;
		}
		else
			dbyte <<= 1;
	}
	
	return result;
}

//=================================