Python routine for CRC of arbitrary length

[Wojciech M. Zabolotny]

I needed a Python function calculating CRC of arbitrary length.
There are a few packages available, but they either calculate
only a few standard CRC, or calculate CRC of only certain
length (e.g. 8 , 16 or 24 bits).
Therefore I prepares a simple implementation based strictly
on the calculation of the CRC presented in Wikipedia.
This is a PUBLIC DOMAIN code.
Please use it on yout own risk.

With best regards,
Wojtek
#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.15.2).
# To extract the files from this archive, save it to some FILE, remove
# everything before the '#!/bin/sh' line above, then type 'sh FILE'.
#
lock_dir=_sh07730
# Made on 2016-03-07 15:49 CET by <wzab@wzdell>.
# Source directory was '/home/wzab/biezace/CBM/crc_any_length'.
#
# Existing files will *not* be overwritten, unless '-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------
# 1567 -rw-r--r-- CRC_al.py
#
MD5SUM=${MD5SUM-md5sum}
f=`${MD5SUM} --version | egrep '^md5sum .*(core|text)utils'`
test -n "${f}" && md5check=true || md5check=false
${md5check} || \
echo 'Note: not verifying md5sums. Consider installing GNU coreutils.'
if test "X$1" = "X-c"
then keep_file=''
else keep_file=true
fi
echo=echo
save_IFS="${IFS}"
IFS="${IFS}:"
gettext_dir=
locale_dir=
set_echo=false

for dir in $PATH
do
if test -f $dir/gettext \
&& ($dir/gettext --version >/dev/null 2>&1)
then
case `$dir/gettext --version 2>&1 | sed 1q` in
*GNU*) gettext_dir=$dir
set_echo=true
break ;;
esac
fi
done

if ${set_echo}
then
set_echo=false
for dir in $PATH
do
if test -f $dir/shar \
&& ($dir/shar --print-text-domain-dir >/dev/null 2>&1)
then
locale_dir=`$dir/shar --print-text-domain-dir`
set_echo=true
break
fi
done

if ${set_echo}
then
TEXTDOMAINDIR=$locale_dir
export TEXTDOMAINDIR
TEXTDOMAIN=sharutils
export TEXTDOMAIN
echo="$gettext_dir/gettext -s"
fi
fi
IFS="$save_IFS"
if (echo "testing\c"; echo 1,2,3) | grep c >/dev/null
then if (echo -n test; echo 1,2,3) | grep n >/dev/null
then shar_n= shar_c='
'
else shar_n=-n shar_c= ; fi
else shar_n= shar_c='\c' ; fi
f=shar-touch.$$
st1=200112312359.59
st2=123123592001.59
st2tr=123123592001.5 # old SysV 14-char limit
st3=1231235901

if touch -am -t ${st1} ${f} >/dev/null 2>&1 && \
test ! -f ${st1} && test -f ${f}; then
shar_touch='touch -am -t $1$2$3$4$5$6.$7 "$8"'

elif touch -am ${st2} ${f} >/dev/null 2>&1 && \
test ! -f ${st2} && test ! -f ${st2tr} && test -f ${f}; then
shar_touch='touch -am $3$4$5$6$1$2.$7 "$8"'

elif touch -am ${st3} ${f} >/dev/null 2>&1 && \
test ! -f ${st3} && test -f ${f}; then
shar_touch='touch -am $3$4$5$6$2 "$8"'

else
shar_touch=:
echo
${echo} 'WARNING: not restoring timestamps. Consider getting and
installing GNU '\''touch'\'', distributed in GNU coreutils...'
echo
fi
rm -f ${st1} ${st2} ${st2tr} ${st3} ${f}
#
if test ! -d ${lock_dir} ; then :
else ${echo} "lock directory ${lock_dir} exists"
exit 1
fi
if mkdir ${lock_dir}
then ${echo} "x - created lock directory ${lock_dir}."
else ${echo} "x - failed to create lock directory ${lock_dir}."
exit 1
fi
# ============= CRC_al.py ==============
if test -n "${keep_file}" && test -f 'CRC_al.py'
then
${echo} "x - SKIPPING CRC_al.py (file already exists)"

else
${echo} "x - extracting CRC_al.py (text)"
sed 's/^X//' << 'SHAR_EOF' > 'CRC_al.py' &&
"""
This module implements the CRC of arbitrary length. The implementation is not the
most efficient one, but it is intended to be as simple (from the code point
of view) as possible and follows the explanation provided in
https://en.wikipedia.org/wiki/Cyclic_redundancy_check
"""
def crc_al(bdata,bdiv,n):
X """
X bdata - binary value of arbitrary length with either CRC bits to be checked
X or n 0 bits (if we want to calculate the CRC)
X bdiv - CRC divisor
X n - length of the CRC
X
X Output:
X dout,dcrc
X
X dout - data with last bits replaced with the result of calculation
X dcrc - value of the CRC
X
X In the implementation we heavily depend on implementation of the
X "bin" function...
X """
X #Check if bdiv is correct for the given CRC length
X div_len=len(bin(bdiv))-2 # There was '0b' at the beginning!
X if div_len != n+1:
X raise Exception("Incorrect CRC divisor for given CRC length")
X data_len=len(bin(bdata))-2
X #Create the copy of data
X sdata = bdata
X #Now we create the mask used to check if the highest bit is set
X mask = 1<<data_len
X #Create the shifted divisor
X i = data_len-div_len
X sdiv = bdiv << i
X #Now in the loop we compute CRC
X while i>0:
X if sdata & mask:
X sdata ^= sdiv
X mask >>= 1
X sdiv >>= 1
X i -= 1
X crc_mask = (1<<n)-1
X crc_val = sdata & crc_mask
X #In the line below we do the dirty trick to clear some bits
X #In the binary number with unknown length...
X bdata = ((bdata | crc_mask) ^ crc_mask) | crc_val;
X return (bdata, crc_val)
X
SHAR_EOF
(set 20 16 03 07 11 46 01 'CRC_al.py'
eval "${shar_touch}") && \
chmod 0644 'CRC_al.py'
if test $? -ne 0
then ${echo} "restore of CRC_al.py failed"
fi
if ${md5check}
then (
${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'CRC_al.py': 'MD5 check failed'
) << \SHAR_EOF
fda9f5664217e6af1695da38ce939b7d CRC_al.py
SHAR_EOF

else
test `LC_ALL=C wc -c < 'CRC_al.py'` -ne 1567 && \
${echo} "restoration warning: size of 'CRC_al.py' is not 1567"
fi
fi
if rm -fr ${lock_dir}
then ${echo} "x - removed lock directory ${lock_dir}."
else ${echo} "x - failed to remove lock directory ${lock_dir}."
exit 1
fi
exit 0

[Wojciech M. Zabołotny]

The previous version of my Python arbitrary length CRC routine was fast, but
also quite limited.
Therefore I've prepared yet another one, based on the animated explanation
of the CRC calculation, available at:
https://en.wikipedia.org/wiki/Computation_of_cyclic_redundancy_checks

The new version uses the bitarray package, so you can work with data sets
of any length, you can call CRC update multiple times.
You can also decide whetje the data should be transmitted LSB first
or MSB first (the internal representation is MSB first - "big").

The code is so simple, that you can easily modify it to your needs.
And it is a PUBLIC DOMAIN code. So you can do anything you want with it.
Of course I don't give any warranty! You use it at your own risk.

#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.15.2).
# To extract the files from this archive, save it to some FILE, remove
# everything before the '#!/bin/sh' line above, then type 'sh FILE'.
#

lock_dir=_sh03690
# Made on 2016-03-08 18:58 CET by <wzab@wzab>.

# Source directory was '/home/wzab/biezace/CBM/crc_any_length'.
#
# Existing files will *not* be overwritten, unless '-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------

# 1622 -rw-r--r-- CRC_ba.py

# ============= CRC_ba.py ==============
if test -n "${keep_file}" && test -f 'CRC_ba.py'
then
${echo} "x - SKIPPING CRC_ba.py (file already exists)"

else
${echo} "x - extracting CRC_ba.py (text)"
sed 's/^X//' << 'SHAR_EOF' > 'CRC_ba.py' &&
import bitarray as ba
class CRC(object):
X def __init__(self,poly,clen,cdir=1):
X """
X poly - CRC polynomial as an integer, must agree with the CRC length
X clen - CRC length
X cdir - informs, whether the data should be taken MSB first (1) or LSB first (0)
X
X example of usage:
X
X d=ba.bitarray('11010011101110')
X f=CRC(0b1011,3)
X f.update(d)
X cr=f.checkCRC()
X print cr #CRC gets displayed
X
X f=CRC(0b1011,3)
X f.update(d)
X tst=f.checkCRC(cr)
X print tst #We should get all zeroes
X
X Of course for longer data, you can call update multiple times!
X
X This is a PUBLIC DOMAIN code, written by Wojciech M. Zabolotny
X wzab<at>ise.pw.edu.pl (2016.03.08)
X
X """
X self.cdir = cdir
X self.CRC = ba.bitarray(clen*'0')
X self.div = ba.bitarray(bin(poly)[3:]) #We reject the leading 1
X if len(self.CRC) != len(self.div):
X raise Exception("Wrong polynomial for that CRC length!")
X def update(self,bdata):
X """
X Updates the CRC basing on the bdata
X """
X #Create the iterator depending on the data "direction"
X if self.cdir:
X ix = xrange(0,len(bdata))
X else:
X ix = xrange(len(bdata)-1,-1,-1)
X for i in ix:
X #Shift the CRC
X b=bdata[i]
X c=self.CRC.pop(0)
X self.CRC.append(b)
X print b, self.CRC
X if c:
X self.CRC = self.CRC ^ self.div
X def check_CRC(self,test_CRC=None):
X if test_CRC==None:
X test_CRC=ba.bitarray(len(self.CRC)*'0')
X self.update(test_CRC)
X if self.cdir:
X return self.CRC
X else:
X c=self.CRC
X c.reverse()
X return c
X
X
SHAR_EOF
(set 20 16 03 08 18 54 12 'CRC_ba.py'

eval "${shar_touch}") && \

chmod 0644 'CRC_ba.py'

if test $? -ne 0

then ${echo} "restore of CRC_ba.py failed"

fi
if ${md5check}
then (

${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'CRC_ba.py': 'MD5 check failed'
) << \SHAR_EOF
e27f5561fcedee0f5666891b8192d467 CRC_ba.py
SHAR_EOF

else
test `LC_ALL=C wc -c < 'CRC_ba.py'` -ne 1622 && \
${echo} "restoration warning: size of 'CRC_ba.py' is not 1622"

[wza...@gmail.com]

Of course, for production use, you should remove or comment out the "print" command inside the update function.

Regards,
Wojtek

[Wojciech M. Zabołotny]

I needed a Python function calculating CRC of arbitrary length.
There are a few packages available, but they either calculate
only a few standard CRC, or calculate CRC of only certain
length (e.g. 8 , 16 or 24 bits).
Therefore I prepares a simple implementation based strictly
on the calculation of the CRC presented in Wikipedia.
This is a PUBLIC DOMAIN code.
Please use it on yout own risk.

In this version I've changed the name of the CRC checking
function from check_CRC to checkCRC (so it agrees with the
doc-string). I have also removed print command from the update
function.

With best regards,
Wojtek

#!/bin/sh
# This is a shell archive (produced by GNU sharutils 4.15.2).
# To extract the files from this archive, save it to some FILE, remove
# everything before the '#!/bin/sh' line above, then type 'sh FILE'.
#

lock_dir=_sh02880
# Made on 2016-03-10 09:01 CET by <wzab@wzab>.

# Source directory was '/home/wzab/biezace/CBM/crc_any_length'.
#
# Existing files will *not* be overwritten, unless '-c' is specified.
#
# This shar contains:
# length mode name
# ------ ---------- ------------------------------------------

# 1622 -rw-r--r-- CRC_ba.py

# ============= CRC_ba.py ==============
if test -n "${keep_file}" && test -f 'CRC_ba.py'
then
${echo} "x - SKIPPING CRC_ba.py (file already exists)"

else

X #print b, self.CRC

X if c:
X self.CRC = self.CRC ^ self.div

X def checkCRC(self,test_CRC=None):

X if test_CRC==None:
X test_CRC=ba.bitarray(len(self.CRC)*'0')
X self.update(test_CRC)
X if self.cdir:
X return self.CRC
X else:
X c=self.CRC
X c.reverse()
X return c
X

X
SHAR_EOF
(set 20 16 03 10 09 00 30 'CRC_ba.py'

eval "${shar_touch}") && \

chmod 0644 'CRC_ba.py'

if test $? -ne 0

then ${echo} "restore of CRC_ba.py failed"

fi
if ${md5check}
then (

${MD5SUM} -c >/dev/null 2>&1 || ${echo} 'CRC_ba.py': 'MD5 check failed'
) << \SHAR_EOF
6d0b188357ba893617edbfbd5d3493bc CRC_ba.py
SHAR_EOF

else
test `LC_ALL=C wc -c < 'CRC_ba.py'` -ne 1622 && \
${echo} "restoration warning: size of 'CRC_ba.py' is not 1622"