Development: Cyclic Redundancy Check
From WxWiki
(POLYNOMIAL, INITVALUE, REVERSED)
http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
Contents |
Overview
Algorithms
Outlined here are four algorithms for computing the CRC of a block of data:
Normal Table
UPD
#ifndef SWAPPED crc = (crc << B) ^ crctab[(crc >> (W - B)) ^ *cp++]; #else crc = (crc >> B) ^ crctab[(crc & ((1 << B) - 1)) ^ *cp++]; #endif SWAPPED
MAK
#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
- Accelerating non-table crcs
- Provides a fast byte-at-a-time crc16ccitt algorithm
- Online javascript crc generator
- Polynomial reversing is incorrect