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