1#----------------------------------------------------------------------------- 2# Copyright (c) 2010 Raymond L. Buvel 3# Copyright (c) 2010 Craig McQueen 4# 5# Permission is hereby granted, free of charge, to any person obtaining a copy 6# of this software and associated documentation files (the "Software"), to deal 7# in the Software without restriction, including without limitation the rights 8# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 9# copies of the Software, and to permit persons to whom the Software is 10# furnished to do so, subject to the following conditions: 11# 12# The above copyright notice and this permission notice shall be included in 13# all copies or substantial portions of the Software. 14# 15# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 20# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 21# SOFTWARE. 22#----------------------------------------------------------------------------- 23'''crcmod is a Python module for gererating objects that compute the Cyclic 24Redundancy Check. Any 8, 16, 24, 32, or 64 bit polynomial can be used. 25 26The following are the public components of this module. 27 28Crc -- a class that creates instances providing the same interface as the 29md5 and sha modules in the Python standard library. These instances also 30provide a method for generating a C/C++ function to compute the CRC. 31 32mkCrcFun -- create a Python function to compute the CRC using the specified 33polynomial and initial value. This provides a much simpler interface if 34all you need is a function for CRC calculation. 35''' 36 37import struct 38import sys 39 40__all__ = '''mkCrcFun Crc 41'''.split() 42 43# Select the appropriate set of low-level CRC functions for this installation. 44# If the extension module was not built, drop back to the Python implementation 45# even though it is significantly slower. 46try: 47 import _crcfunext as _crcfun 48 _usingExtension = True 49except ImportError: 50 if sys.version_info.major == 2: 51 import _crcfunpy as _crcfun 52 else: # PY3 53 import crcmod._crcfunpy as _crcfun 54 _usingExtension = False 55 56if sys.version_info.major > 2: 57 long = int 58 59_CRC_INIT = ~(long(0)) 60 61#----------------------------------------------------------------------------- 62class Crc: 63 '''Compute a Cyclic Redundancy Check (CRC) using the specified polynomial. 64 65 Instances of this class have the same interface as the md5 and sha modules 66 in the Python standard library. See the documentation for these modules 67 for examples of how to use a Crc instance. 68 69 The string representation of a Crc instance identifies the polynomial, 70 initial value, XOR out value, and the current CRC value. The print 71 statement can be used to output this information. 72 73 If you need to generate a C/C++ function for use in another application, 74 use the generateCode method. If you need to generate code for another 75 language, subclass Crc and override the generateCode method. 76 77 The following are the parameters supplied to the constructor. 78 79 poly -- The generator polynomial to use in calculating the CRC. The value 80 is specified as a Python integer or long integer. The bits in this integer 81 are the coefficients of the polynomial. The only polynomials allowed are 82 those that generate 8, 16, 24, 32, or 64 bit CRCs. 83 84 initCrc -- Initial value used to start the CRC calculation. This initial 85 value should be the initial shift register value XORed with the final XOR 86 value. That is equivalent to the CRC result the algorithm should return for 87 a zero-length string. Defaults to all bits set because that starting value 88 will take leading zero bytes into account. Starting with zero will ignore 89 all leading zero bytes. 90 91 rev -- A flag that selects a bit reversed algorithm when True. Defaults to 92 True because the bit reversed algorithms are more efficient. 93 94 xorOut -- Final value to XOR with the calculated CRC value. Used by some 95 CRC algorithms. Defaults to zero. 96 ''' 97 def __init__(self, poly, initCrc=_CRC_INIT, rev=True, xorOut=0, initialize=True): 98 if not initialize: 99 # Don't want to perform the initialization when using new or copy 100 # to create a new instance. 101 return 102 103 (sizeBits, initCrc, xorOut) = _verifyParams(poly, initCrc, xorOut) 104 self.digest_size = sizeBits//8 105 self.initCrc = initCrc 106 self.xorOut = xorOut 107 108 self.poly = poly 109 self.reverse = rev 110 111 (crcfun, table) = _mkCrcFun(poly, sizeBits, initCrc, rev, xorOut) 112 self._crc = crcfun 113 self.table = table 114 115 self.crcValue = self.initCrc 116 117 def __str__(self): 118 lst = [] 119 lst.append('poly = 0x%X' % self.poly) 120 lst.append('reverse = %s' % self.reverse) 121 fmt = '0x%%0%dX' % (self.digest_size*2) 122 lst.append('initCrc = %s' % (fmt % self.initCrc)) 123 lst.append('xorOut = %s' % (fmt % self.xorOut)) 124 lst.append('crcValue = %s' % (fmt % self.crcValue)) 125 return '\n'.join(lst) 126 127 def new(self, arg=None): 128 '''Create a new instance of the Crc class initialized to the same 129 values as the original instance. The current CRC is set to the initial 130 value. If a string is provided in the optional arg parameter, it is 131 passed to the update method. 132 ''' 133 n = Crc(poly=None, initialize=False) 134 n._crc = self._crc 135 n.digest_size = self.digest_size 136 n.initCrc = self.initCrc 137 n.xorOut = self.xorOut 138 n.table = self.table 139 n.crcValue = self.initCrc 140 n.reverse = self.reverse 141 n.poly = self.poly 142 if arg is not None: 143 n.update(arg) 144 return n 145 146 def copy(self): 147 '''Create a new instance of the Crc class initialized to the same 148 values as the original instance. The current CRC is set to the current 149 value. This allows multiple CRC calculations using a common initial 150 string. 151 ''' 152 c = self.new() 153 c.crcValue = self.crcValue 154 return c 155 156 def update(self, data): 157 '''Update the current CRC value using the string specified as the data 158 parameter. 159 ''' 160 self.crcValue = self._crc(data, self.crcValue) 161 162 def digest(self): 163 '''Return the current CRC value as a string of bytes. The length of 164 this string is specified in the digest_size attribute. 165 ''' 166 n = self.digest_size 167 crc = self.crcValue 168 lst = [] 169 while n > 0: 170 lst.append(chr(crc & 0xFF)) 171 crc = crc >> 8 172 n -= 1 173 lst.reverse() 174 return ''.join(lst) 175 176 def hexdigest(self): 177 '''Return the current CRC value as a string of hex digits. The length 178 of this string is twice the digest_size attribute. 179 ''' 180 n = self.digest_size 181 crc = self.crcValue 182 lst = [] 183 while n > 0: 184 lst.append('%02X' % (crc & 0xFF)) 185 crc = crc >> 8 186 n -= 1 187 lst.reverse() 188 return ''.join(lst) 189 190 def generateCode(self, functionName, out, dataType=None, crcType=None): 191 '''Generate a C/C++ function. 192 193 functionName -- String specifying the name of the function. 194 195 out -- An open file-like object with a write method. This specifies 196 where the generated code is written. 197 198 dataType -- An optional parameter specifying the data type of the input 199 data to the function. Defaults to UINT8. 200 201 crcType -- An optional parameter specifying the data type of the CRC 202 value. Defaults to one of UINT8, UINT16, UINT32, or UINT64 depending 203 on the size of the CRC value. 204 ''' 205 if dataType is None: 206 dataType = 'UINT8' 207 208 if crcType is None: 209 size = 8*self.digest_size 210 if size == 24: 211 size = 32 212 crcType = 'UINT%d' % size 213 214 if self.digest_size == 1: 215 # Both 8-bit CRC algorithms are the same 216 crcAlgor = 'table[*data ^ (%s)crc]' 217 elif self.reverse: 218 # The bit reverse algorithms are all the same except for the data 219 # type of the crc variable which is specified elsewhere. 220 crcAlgor = 'table[*data ^ (%s)crc] ^ (crc >> 8)' 221 else: 222 # The forward CRC algorithms larger than 8 bits have an extra shift 223 # operation to get the high byte. 224 shift = 8*(self.digest_size - 1) 225 crcAlgor = 'table[*data ^ (%%s)(crc >> %d)] ^ (crc << 8)' % shift 226 227 fmt = '0x%%0%dX' % (2*self.digest_size) 228 if self.digest_size <= 4: 229 fmt = fmt + 'U,' 230 else: 231 # Need the long long type identifier to keep gcc from complaining. 232 fmt = fmt + 'ULL,' 233 234 # Select the number of entries per row in the output code. 235 n = {1:8, 2:8, 3:4, 4:4, 8:2}[self.digest_size] 236 237 lst = [] 238 for i, val in enumerate(self.table): 239 if (i % n) == 0: 240 lst.append('\n ') 241 lst.append(fmt % val) 242 243 poly = 'polynomial: 0x%X' % self.poly 244 if self.reverse: 245 poly = poly + ', bit reverse algorithm' 246 247 if self.xorOut: 248 # Need to remove the comma from the format. 249 preCondition = '\n crc = crc ^ %s;' % (fmt[:-1] % self.xorOut) 250 postCondition = preCondition 251 else: 252 preCondition = '' 253 postCondition = '' 254 255 if self.digest_size == 3: 256 # The 24-bit CRC needs to be conditioned so that only 24-bits are 257 # used from the 32-bit variable. 258 if self.reverse: 259 preCondition += '\n crc = crc & 0xFFFFFFU;' 260 else: 261 postCondition += '\n crc = crc & 0xFFFFFFU;' 262 263 264 parms = { 265 'dataType' : dataType, 266 'crcType' : crcType, 267 'name' : functionName, 268 'crcAlgor' : crcAlgor % dataType, 269 'crcTable' : ''.join(lst), 270 'poly' : poly, 271 'preCondition' : preCondition, 272 'postCondition' : postCondition, 273 } 274 out.write(_codeTemplate % parms) 275 276#----------------------------------------------------------------------------- 277def mkCrcFun(poly, initCrc=_CRC_INIT, rev=True, xorOut=0): 278 '''Return a function that computes the CRC using the specified polynomial. 279 280 poly -- integer representation of the generator polynomial 281 initCrc -- default initial CRC value 282 rev -- when true, indicates that the data is processed bit reversed. 283 xorOut -- the final XOR value 284 285 The returned function has the following user interface 286 def crcfun(data, crc=initCrc): 287 ''' 288 289 # First we must verify the params 290 (sizeBits, initCrc, xorOut) = _verifyParams(poly, initCrc, xorOut) 291 # Make the function (and table), return the function 292 return _mkCrcFun(poly, sizeBits, initCrc, rev, xorOut)[0] 293 294#----------------------------------------------------------------------------- 295# Naming convention: 296# All function names ending with r are bit reverse variants of the ones 297# without the r. 298 299#----------------------------------------------------------------------------- 300# Check the polynomial to make sure that it is acceptable and return the number 301# of bits in the CRC. 302 303def _verifyPoly(poly): 304 msg = 'The degree of the polynomial must be 8, 16, 24, 32 or 64' 305 poly = long(poly) # Use a common representation for all operations 306 for n in (8,16,24,32,64): 307 low = long(1)<<n 308 high = low*2 309 if low <= poly < high: 310 return n 311 raise ValueError(msg) 312 313#----------------------------------------------------------------------------- 314# Bit reverse the input value. 315 316def _bitrev(x, n): 317 x = long(x) 318 y = long(0) 319 for i in xrange(n): 320 y = (y << 1) | (x & long(1)) 321 x = x >> 1 322 if ((long(1)<<n)-1) <= sys.maxint: 323 return int(y) 324 return y 325 326#----------------------------------------------------------------------------- 327# The following functions compute the CRC for a single byte. These are used 328# to build up the tables needed in the CRC algorithm. Assumes the high order 329# bit of the polynomial has been stripped off. 330 331def _bytecrc(crc, poly, n): 332 crc = long(crc) 333 poly = long(poly) 334 mask = long(1)<<(n-1) 335 for i in xrange(8): 336 if crc & mask: 337 crc = (crc << 1) ^ poly 338 else: 339 crc = crc << 1 340 mask = (long(1)<<n) - 1 341 crc = crc & mask 342 if mask <= sys.maxint: 343 return int(crc) 344 return crc 345 346def _bytecrc_r(crc, poly, n): 347 crc = long(crc) 348 poly = long(poly) 349 for i in xrange(8): 350 if crc & long(1): 351 crc = (crc >> 1) ^ poly 352 else: 353 crc = crc >> 1 354 mask = (long(1)<<n) - 1 355 crc = crc & mask 356 if mask <= sys.maxint: 357 return int(crc) 358 return crc 359 360#----------------------------------------------------------------------------- 361# The following functions compute the table needed to compute the CRC. The 362# table is returned as a list. Note that the array module does not support 363# 64-bit integers on a 32-bit architecture as of Python 2.3. 364# 365# These routines assume that the polynomial and the number of bits in the CRC 366# have been checked for validity by the caller. 367 368def _mkTable(poly, n): 369 mask = (long(1)<<n) - 1 370 poly = long(poly) & mask 371 table = [_bytecrc(long(i)<<(n-8),poly,n) for i in xrange(256)] 372 return table 373 374def _mkTable_r(poly, n): 375 mask = (long(1)<<n) - 1 376 poly = _bitrev(long(poly) & mask, n) 377 table = [_bytecrc_r(long(i),poly,n) for i in xrange(256)] 378 return table 379 380#----------------------------------------------------------------------------- 381# Map the CRC size onto the functions that handle these sizes. 382 383_sizeMap = { 384 8 : [_crcfun._crc8, _crcfun._crc8r], 385 16 : [_crcfun._crc16, _crcfun._crc16r], 386 24 : [_crcfun._crc24, _crcfun._crc24r], 387 32 : [_crcfun._crc32, _crcfun._crc32r], 388 64 : [_crcfun._crc64, _crcfun._crc64r], 389} 390 391#----------------------------------------------------------------------------- 392# Build a mapping of size to struct module type code. This table is 393# constructed dynamically so that it has the best chance of picking the best 394# code to use for the platform we are running on. This should properly adapt 395# to 32 and 64 bit machines. 396 397_sizeToTypeCode = {} 398 399for typeCode in 'B H I L Q'.split(): 400 size = {1:8, 2:16, 4:32, 8:64}.get(struct.calcsize(typeCode),None) 401 if size is not None and size not in _sizeToTypeCode: 402 _sizeToTypeCode[size] = '256%s' % typeCode 403 404_sizeToTypeCode[24] = _sizeToTypeCode[32] 405 406del typeCode, size 407 408#----------------------------------------------------------------------------- 409# The following function validates the parameters of the CRC, namely, 410# poly, and initial/final XOR values. 411# It returns the size of the CRC (in bits), and "sanitized" initial/final XOR values. 412 413def _verifyParams(poly, initCrc, xorOut): 414 sizeBits = _verifyPoly(poly) 415 416 mask = (long(1)<<sizeBits) - 1 417 418 # Adjust the initial CRC to the correct data type (unsigned value). 419 initCrc = long(initCrc) & mask 420 if mask <= sys.maxint: 421 initCrc = int(initCrc) 422 423 # Similar for XOR-out value. 424 xorOut = long(xorOut) & mask 425 if mask <= sys.maxint: 426 xorOut = int(xorOut) 427 428 return (sizeBits, initCrc, xorOut) 429 430#----------------------------------------------------------------------------- 431# The following function returns a Python function to compute the CRC. 432# 433# It must be passed parameters that are already verified & sanitized by 434# _verifyParams(). 435# 436# The returned function calls a low level function that is written in C if the 437# extension module could be loaded. Otherwise, a Python implementation is 438# used. 439# 440# In addition to this function, a list containing the CRC table is returned. 441 442def _mkCrcFun(poly, sizeBits, initCrc, rev, xorOut): 443 if rev: 444 tableList = _mkTable_r(poly, sizeBits) 445 _fun = _sizeMap[sizeBits][1] 446 else: 447 tableList = _mkTable(poly, sizeBits) 448 _fun = _sizeMap[sizeBits][0] 449 450 _table = tableList 451 if _usingExtension: 452 _table = struct.pack(_sizeToTypeCode[sizeBits], *tableList) 453 454 if xorOut == 0: 455 def crcfun(data, crc=initCrc, table=_table, fun=_fun): 456 return fun(data, crc, table) 457 else: 458 def crcfun(data, crc=initCrc, table=_table, fun=_fun): 459 return xorOut ^ fun(data, xorOut ^ crc, table) 460 461 return crcfun, tableList 462 463#----------------------------------------------------------------------------- 464_codeTemplate = '''// Automatically generated CRC function 465// %(poly)s 466%(crcType)s 467%(name)s(%(dataType)s *data, int len, %(crcType)s crc) 468{ 469 static const %(crcType)s table[256] = {%(crcTable)s 470 }; 471 %(preCondition)s 472 while (len > 0) 473 { 474 crc = %(crcAlgor)s; 475 data++; 476 len--; 477 }%(postCondition)s 478 return crc; 479} 480''' 481 482