Development: Cyclic Redundancy Check

From WxWiki
Jump to: navigation, search

(POLYNOMIAL, INITVALUE, REVERSED)

http://www.repairfaq.org/filipg/LINK/F_crc_v3.html


Overview

Algorithms

Outlined here are four algorithms for computing the CRC of a block of data:


Normal Table

#ifndef SWAPPED
	crc = (crc << B) ^ crctab[(crc >> (W - B)) ^ *cp++];
#else
	crc = (crc >> B) ^ crctab[(crc & ((1 << B) - 1)) ^ *cp++]; 
#endif SWAPPED
#ifndef SWAPPED
	for( v = b << (W - B), i = B; --i >= 0; )
		v = v & ((WTYPE)1 << (W - 1)) ? (v << 1) ^ P : v << 1;
#else
	for( v = b, i = B; --i >= 0; )
		v = v & 1 ? (v >> 1) ^ P : v >> 1;
#endif

Bit

inline void Update(const unsigned char& value)
{
	crc ^= value << ((sizeof(TYPE) * 8) - 8);
	for (unsigned short index = 0; index < 8; ++index)
	{
		if (crc & (1 << ((sizeof(TYPE) * 8)  - 1)  ))
			crc = (crc << 1) ^ POLYNOMIAL;
		else
			crc <<= 1;
	}
}

Byte

/*****************************************************
* Purpose: Calculates the 16-bit CCITT CRC check of
* a sequence of bytes
* Inputs: inBuf() input array of bytes
* nStart starting point in inBuf
* nBytes number of bytes to use
* Returns: The unsigned 16-bit CRC as a long
* Method: Devised by Andy Lowry, Columbia University
* The magic number &H1081 is derived from
* the CRC-CCITT polynomial x^16+x^12+x^5+1
* Translated to C from Visual Basic By Ryan Norton
* MSB First version devised By Ryan Norton
******************************************************/
 
#define Q ((((crc >> 8) ^ (value)) & 0xF0) >> 4 )
#define Q2 ((((crc >> 8) ^ (value << 4)) & 0xF0) >> 4)
#define QR ((crc ^ (value)) & 0xF)
#define QR2 ((crc ^ (value >> 4)) & 0xF)
 
inline void Update(const unsigned char& value)                                                                   
{      
	if (!REVERSE) //MSB first
	{
		crc = (crc << 4) ^ (Q * POLYNOMIAL);
		crc = (crc << 4) ^ (Q2 * POLYNOMIAL);
	}
	else //LSB first
	{
		crc = (crc >> 4) ^ (QR * POLYNOMIAL);
		crc = (crc >> 4) ^ (QR2 * POLYNOMIAL); 
	}		
}

Resources