Alex Stewart Alex Stewart - 4 months ago 30
Python Question

CRC-CCITT 16-bit Python Manual Calculation

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.

http://bytes.com/topic/python/insights/887357-python-check-crc-frame-crc-16-ccitt

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 reg


Existing Online Solution

The following link calculates a 16 bit CRC correctly.

http://www.lammertbies.nl/comm/info/crc-calculation.html#intr

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.

Answer

Here is a python port of the C library from http://www.lammertbies.nl/comm/info/crc-calculation.html 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 crc

Your proposed checkCRC routine is CRC-CCITT variant '1D0F' if you replace poly = 0x11021 with poly = 0x1021 at the beginning.

Comments