Recipe 2.30. Calculating CRC-64 Cyclic Redundancy Checks
Credit: Gian Paolo Ciceri
You need to ensure the integrity of some data by computing the data's cyclic redundancy check (CRC), and you need to do so according to the CRC-64 specifications of the ISO-3309 standard.
The Python Standard Library does not include any implementation of CRC-64 (only one of CRC-32 in function
), so we need to program it
# prepare two auxiliary tables tables (using a function, for speed), # then remove the function, since it's not needed any more: CRCTableh =  * 256 CRCTablel =  * 256 def _inittables(CRCTableh, CRCTablel, POLY64REVh, BIT_TOGGLE): for i in xrange(256): partl = i parth = 0L for j in xrange(8): rflag = partl & 1L partl >>= 1L if parth & 1: partl ^= BIT_TOGGLE parth >>= 1L if rflag: parth ^= POLY64REVh CRCTableh[i] = parth CRCTablel[i] = partl # first 32 bits of generator polynomial for CRC64 (the 32 lower bits are # assumed to be zero) and bit-toggle mask used in _inittables POLY64REVh = 0xd8000000L BIT_TOGGLE = 1L << 31L # run the function to prepare the tables _inittables(CRCTableh, CRCTablel, POLY64REVh, BIT_TOGGLE) # remove all names we don't need any more, including the function del _inittables, POLY64REVh, BIT_TOGGLE # this module exposes the following two functions: crc64, crc64digest def crc64(bytes, (crch, crcl)=(0,0)): for byte in bytes: shr = (crch & 0xFF) << 24 temp1h = crch >> 8L temp1l = (crcl >> 8L) shr tableindex = (crcl ^ ord(byte)) & 0xFF crch = temp1h ^ CRCTableh[tableindex] crcl = temp1l ^ CRCTablel[tableindex] return crch, crcl def crc64digest(aString): return "%08X%08X" % (crc64(bytes)) if _ _name_ _ == '_ _main_ _': # a little test/demo, for when this module runs as main-script assert crc64("IHATEMATH") == (3822890454, 2600578513) assert crc64digest("IHATEMATH") == "E3DCADD69B01ADD1" print 'crc64: dumb test successful'
Cyclic redundancy checks (CRCs) are a popular way to ensure that data (in particular, a file) has not been
Mathematically speaking, a CRC is computed as a polynomial over the bits of the data we're
The algorithm to compute the standard CRC-64 checksum is described in the ISO-3309 standard, and this recipe does nothing more than implement that algorithm. The generator polynomial is x64 + x4 + x3 + x + 1 . (The "See Also" section within this recipe provides a reference for obtaining information about the computation.)
We represent the 64-bit result as a pair of Python
s, holding the low and high 32-bit
W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Numerical Recipes in C , 2d ed. (Cambridge University Press), pp. 896ff.