CRC-CCITT 16-bit Python Manual Calculation

Question

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.

There is a library that is very usable: [pycrc](http://www.tty1.net/pycrc/index_en.html) calculates any CRC poly in python; also can output C code. — Antti Haapala -- Слава Україні, Aug 12 '14 at 04:20
Hi Antti, looking for a function based solution that does not use libraries. Thanks — Alex Stewart, Aug 13 '14 at 08:47
You can copy the classes from [GitHub](https://github.com/tpircher/pycrc/blob/master/crc_algorithms.py), they are pure python. — Antti Haapala -- Слава Україні, Aug 13 '14 at 09:07
There is also a [recently documented](https://bugs.python.org/issue29004) function in the Python [2](https://docs.python.org/2/library/binascii.html#binascii.crc_hqx) and [3](https://docs.python.org/3/library/binascii.html#binascii.crc_hqx) standard library to do CCITT CRCs :-) — Abbafei, Dec 03 '19 at 01:13

Serge Ballesta · Accepted Answer · 2014-08-12T08:12:27.577

16

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.

edited Aug 12 '14 at 08:12

answered Aug 12 '14 at 08:05

Serge Ballesta

143,923
11
122
252

How do i perform a CRC calculation on a hex stored as a string? e.g. `crc_string = "0A0A0A0A0A0A0A"` – Alex Stewart Aug 13 '14 at 10:52
2

You first convert the string to a list of bytes and then call crcb : `crcb(*[ int(crc_string[i:i+2], 16) for i in range(0, len(crc_string), 2)])` - for `crc_string = "0A0A0A0A0A0A0A"` it gives `53769` = `0xd209` – Serge Ballesta Aug 13 '14 at 11:35
I'm going to see if this lines up with boost's [crc_ccitt_type](http://www.boost.org/doc/libs/1_60_0/libs/crc/crc.html#crc_ex). The `CRC-CCITT (0xFFFF)` offering they have looks like `typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt_type`; I can see that the InitRem parameter (0xFFFF) matches but I need to dig in for the other params. – jxramos May 23 '16 at 21:09
The webpage seems to agree with the boost implementation for a handful of checks. Is there a quick update to your port to change it from CRC-CCITT (XMODEM) to CRC-CCITT (0xFFFF). I'll study the source, but from the guys readme lib_crc.txt it looks like CRC-CCITT XModem, 0xFFFF, and 0x1D0F all differ by the starting value which I'm guessing is your `PRESET` variable. – jxramos May 24 '16 at 21:11
1

`crcb` would be a lot more useful as `def crcb(i)` instead of `def crcb(*i)`. Nothing else needs to be changed and then lists can be passed in directly. – Anthony Dec 17 '17 at 18:16

score 2 · Answer 2 · answered May 20 '15 at 18:17

2

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) + lsb

answered May 20 '15 at 18:17

Luciano Barcaro

388
2
6

1

I like how short your function is. I still don't understand the algorithm though, what do you set your crc variable to for a standard x^16 + x^12+x^5 +1 polynomial? I assume its crc = 0x1021, but how would one arrive to this conclusion? – andNoob Jul 27 '15 at 19:19
1

Hi, to be honest, I found this magic code in ASM. I just rewrote it in python some time ago. – Luciano Barcaro Aug 24 '15 at 17:37
I am unable to get the same result from this code as I get from Serge Ballesta's response. – Omegaman Sep 12 '15 at 00:23
Which parameters are you passing to the function? – Luciano Barcaro Sep 12 '15 at 00:29
1

This would be helpful if there was an explanation about how to use it. In its current form, it's not helpful at all. – Anthony Dec 17 '17 at 16:59

score 2 · Answer 3 · answered Jul 29 '16 at 09:38

2

The original function, checkCRC, can also do "CRC-CCITT (XModem)".

Just set:

poly = 0x1021
reg = 0

Instead of

poly = 0x11021
reg = 0xFFFF

answered Jul 29 '16 at 09:38

Arik Yavilevich

421
4
6

score 0 · Answer 4 · answered Aug 12 '14 at 04:14

0

Here 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.

answered Aug 12 '14 at 04:14

Mark Adler

101,978
13
118
158

Hi Mark, i had a crack at converting to Python, but was largely unsuccessful. Thank you for your help! – Alex Stewart Aug 13 '14 at 11:38
@AlexStewart: https://pypi.org/project/crccheck/ implements this, and more, in Python. The [`Crc16` baseclass](https://bitbucket.org/martin_scharrer/crccheck/src/03a259fdaa07147c027a8e3424faeaf91b91e145/crccheck/crc.py#lines-175:211) closely follows Mark's implementation here, with configurable reflection and polynomial (as well as configurable init and xor output, as hinted at by the comment in the code here, for other CRC16 variants). – Martijn Pieters Mar 26 '19 at 11:40
Considering this is a Python question, a C response seems kind of...out there? – Sherlock70 Feb 04 '20 at 08:19
@Sherlock70 The C code provides a correct and verified algorithm. It should be trivial for someone who knows Python to translate it. – Mark Adler Feb 04 '20 at 20:31
@MarkAdler One should think that, but I for one am not someone who knows the other half of that equation, namely C. But apart from that, If it is that simple... why didn't you do it? Sorry if this sounds harsh, I just feel that a question asked for one language should be answered in it. Just look at Alex's comment... – Sherlock70 Feb 05 '20 at 07:52

Axel Jacobsen · Answer 5 · 2020-09-23T17:37:00.387

The accepted answer above is wrong. It does not augment a zero-length input with 16 bits of 0, as given by http://srecord.sourceforge.net/crc16-ccitt.html. 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 crc

Now, if we compare the new implementation to the expected CRC values, we get the "good_crc" values instead of "bad_crc" values.

score 0 · Answer 6 · answered Oct 07 '20 at 02:40

0

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).

answered Oct 07 '20 at 02:40

p8me

1,840
1
15
23

Though this doesn't answer the OP question, I found binascii.b2a_hqx to be exactly what I needed - a standard Python implementation of CRC-16, without installing any 3rd-party packages – kheld Mar 26 '21 at 17:42

score 0 · Answer 7 · answered Aug 14 '22 at 14:25

A nice module :https://fastcrc.readthedocs.io/en/stable/

import fastcrc
data = bytes.fromhex("0900000000423046444f3231323630553058000000000000000000a38e90da0e020000000000000000004149522d415032383032492d452d4b392020202000440188b4034130464357323532335030504c0000000000004c0200010064000102000c006400010200ff5630354149522d415032383032492d452d4b392020000000000000000000000000500f801ca6a01000500f801ca6b01000490189d6051c018b2c0541503238303020202020202020202020202020202021072500000000000000000000000000000000000000")
print(hex(fastcrc.crc16.genibus(data)))

An online API:https://crccalc.com/

score -1 · Answer 8 · answered Aug 31 '15 at 13:10

I have developed a small python module to generate crc. Give it a shot and check the source code it may help!

https://github.com/killercode/PythonCRC

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.result

Hope it helps :)

CRC-CCITT 16-bit Python Manual Calculation

8 Answers8

Linked