Problem
I am writing code for an embedded device. A lot of solutions out there for CRC-CCITT 16-bit calculations require libraries.
Given that using libraries is almost impossible and a drain on its resources, a function is required.
Possible Solution
The following CRC calculation was found online. However, its implementation is incorrect.
def checkCRC(message): #CRC-16-CITT poly, the CRC sheme used by ymodem protocol poly = 0x11021 #16bit operation register, initialized to zeros reg = 0xFFFF #pad the end of the message with the size of the poly message += '\x00\x00' #for each bit in the message for byte in message: mask = 0x80 while(mask > 0): #left shift by one reg<<=1 #input the next bit from the message into the right hand side of the op reg if ord(byte) & mask: reg += 1 mask>>=1 #if a one popped out the left of the reg, xor reg w/poly if reg > 0xffff: #eliminate any one that popped out the left reg &= 0xffff #xor with the poly, this is the remainder reg ^= poly return regExisting Online Solution
The following link calculates a 16 bit CRC correctly.
The result under "CRC-CCITT (XModem)" is the correct CRC.
Specification
I believe the "CRC-CCITT (XModem)" calculation in the existing online solution uses a polynomial of 0x1021.
Question
If someone could write a new function or provide direction to solve the checkCRC function to the required specification. Please note that the use of libraries or any import's would not help.
7 Answers
Here is a python port of the C library from for CRC-CCITT XMODEM
This library is interesting for real use cases because it pre-computes a table of crc for enhanced speed.
Usage (with a string or a list of bytes) :
crc('123456789')
crcb(0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39)The test gives : '0x31c3'
POLYNOMIAL = 0x1021
PRESET = 0
def _initial(c): crc = 0 c = c << 8 for j in range(8): if (crc ^ c) & 0x8000: crc = (crc << 1) ^ POLYNOMIAL else: crc = crc << 1 c = c << 1 return crc
_tab = [ _initial(i) for i in range(256) ]
def _update_crc(crc, c): cc = 0xff & c tmp = (crc >> 8) ^ cc crc = (crc << 8) ^ _tab[tmp & 0xff] crc = crc & 0xffff print (crc) return crc
def crc(str): crc = PRESET for c in str: crc = _update_crc(crc, ord(c)) return crc
def crcb(*i): crc = PRESET for c in i: crc = _update_crc(crc, c) return crcYour proposed checkCRC routine is CRC-CCITT variant '1D0F' if you replace poly = 0x11021 with poly = 0x1021 at the beginning.
Here's a function that I use:
def crc16_ccitt(crc, data): msb = crc >> 8 lsb = crc & 255 for c in data: x = ord(c) ^ msb x ^= (x >> 4) msb = (lsb ^ (x >> 3) ^ (x << 4)) & 255 lsb = (x ^ (x << 5)) & 255 return (msb << 8) + lsbThe original function, checkCRC, can also do "CRC-CCITT (XModem)".
Just set:
poly = 0x1021
reg = 0Instead of
poly = 0x11021
reg = 0xFFFFHere is a C version that you can translate to Python:
#define POLY 0x1021
/* CRC-16 XMODEM: polynomial 0x1021, init = 0, xorout = 0, no reflection */
unsigned crc16x(unsigned crc, unsigned char *buf, size_t len)
{ while (len--) { crc ^= *buf++ << 8; crc = crc & 0x8000 ? (crc << 1) ^ POLY : crc << 1; crc = crc & 0x8000 ? (crc << 1) ^ POLY : crc << 1; crc = crc & 0x8000 ? (crc << 1) ^ POLY : crc << 1; crc = crc & 0x8000 ? (crc << 1) ^ POLY : crc << 1; crc = crc & 0x8000 ? (crc << 1) ^ POLY : crc << 1; crc = crc & 0x8000 ? (crc << 1) ^ POLY : crc << 1; crc = crc & 0x8000 ? (crc << 1) ^ POLY : crc << 1; crc = crc & 0x8000 ? (crc << 1) ^ POLY : crc << 1; } return crc & 0xffff;
}crc is initialized to zero.
The accepted answer above is wrong. It does not augment a zero-length input with 16 bits of 0, as given by . Luckily, it can be fixed very easily. I will only post the changes that I've made.
def crc(str): crc = PRESET # start crc with two zero bytes for _ in range(2): crc = _update_crc(crc, 0) for c in str: crc = _update_crc(crc, ord(c)) return crc
def crcb(*i): crc = PRESET for _ in range(2): crc = _update_crc(crc, 0) for c in i: crc = _update_crc(crc, c) return crcNow, if we compare the new implementation to the expected CRC values, we get the "good_crc" values instead of "bad_crc" values.
If anyone interested in CRC-16-CITT using python, there is now a built-in python package (binascii) that takes care of this: binascii.b2a_hqx(data, value).
I have developed a small python module to generate crc. Give it a shot and check the source code it may help!
For what you want you just need to use the following code
import crc
crccalc = crc.Crc()
crccalc.setCRCccitt() # Let's calculate the CRC CCITT of a value
crccalc.data = "My Data"
crccalc.compute()
print crccalc.resultHope it helps :)
