CrcMoose

Source Code for Module CrcMoose

1 #!/usr/bin/python 2 # -*- Mode: Python; py-indent-offset: 4 -*- 3 # 4 # Copyright (C) 2005,2007 Ray Burr 5 # 6 # Permission is hereby granted, free of charge, to any person obtaining a copy 7 # of this software and associated documentation files (the "Software"), to deal 8 # in the Software without restriction, including without limitation the rights 9 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 10 # copies of the Software, and to permit persons to whom the Software is 11 # furnished to do so, subject to the following conditions: 12 # 13 # The above copyright notice and this permission notice shall be included in 14 # all copies or substantial portions of the Software. 15 # 16 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 22 # THE SOFTWARE. 23 # 24 25 # DISCLAIMER: I don't pretend to be a math wizard. I don't have a 26 # deep understanding of all of the theory behind CRCs. Part of the 27 # reason I originally wrote this is to help understand and verify CRC 28 # algorithms in practice. It is likely that some of my terminology is 29 # inaccurate. 30 31 # Requires at least Python 2.4; tested with 2.4 and 2.5. 32 33 """ 34 This module can model common CRC algorithms given the set of defining 35 parameters. This is intended to be easy to use for experimentation 36 rather than optimized for speed. It is slow even for a native Python 37 CRC implementation. 38 39 Several common CRC algorithms are predefined in this module. 40 41 :authors: Ray Burr 42 :license: MIT License 43 :contact: http://www.nightmare.com/~ryb/ 44 45 Examples 46 ======== 47 48 >>> '%X' % CRC32.calcString('123456789') 49 'CBF43926' 50 51 This test function runs all of the defined algorithms on the test 52 input string '123456789': 53 54 >>> _printResults() 55 CRC-5-USB: 19 56 CRC-8-SMBUS: F4 57 CRC-15: 059E 58 CRC-16: BB3D 59 CRC-16-USB: B4C8 60 CRC-CCITT: 29B1 61 CRC-HDLC: 906E 62 CRC-24: 21CF02 63 CRC-32: CBF43926 64 CRC-32C: E3069283 65 CRC-64: 46A5A9388A5BEFFE 66 CRC-256: 79B96BDC0C519B239BE759EC0688C86FD25A3F4DF1E7F054AD1F923D0739DAC8 67 68 Calculating in parts: 69 70 >>> value = CRC32.calcString('1234') 71 >>> '%X' % CRC32.calcString('56789', value) 72 'CBF43926' 73 74 Or, done a different way: 75 76 >>> crc = CrcRegister(CRC32) 77 >>> crc.takeString('1234') 78 >>> crc.takeString('56789') 79 >>> '%X' % crc.getFinalValue() 80 'CBF43926' 81 82 Inversion of a CRC function: 83 84 >>> CRC_CCITT.reverse().reflect().calcWord(54321, 16, 0) 85 1648 86 >>> CRC_CCITT.calcWord(_, 16, 0) 87 54321 88 89 A 15-bit CRC is used in CAN protocols. The following sample CAN frame 90 (in binary here) is converted to hexadecimal for the calcWord call. 91 The bits after the 15-bit CRC are not included in the CRC:: 92 93 0 11101000001 0 0 0 0001 00010010 011000010111011 1 1 1 1111111 94 95 This sample CAN frame was found in this paper: 96 <http://www.anthony-marino.com/documents/HDL_implementation_CAN.pdf> 97 98 >>> '%X' % CRC15.calcWord(0x3A08112, 27) 99 '30BB' 100 101 If the CRC is included, the remainder should always be zero: 102 103 >>> print CRC15.calcWord(0x1D0408930BB, 42) 104 0 105 106 A 5-bit CRC is used some kinds of USB packets. Here is a sample 107 start-of-frame packet: 108 109 10100101 01100111000 01111 110 111 (found at <http://www.nital.com/corporate/usb2snooper.html>) 112 113 The first field is the PID (not included in the CRC), the next 11-bit 114 field is the frame number (0xE6, LSb-first order), and the final five 115 bits are the CRC (0x1E, LSb-first order). 116 117 >>> '%X' % CRC5_USB.calcWord(0xE6, 11) 118 '1E' 119 """ 120 121 # <http://docutils.sourceforge.net/docs/ref/rst/restructuredtext.html> 122 __docformat__ = "restructuredtext en" 123 124 __version__ = "20070611" 125

126 -class CrcAlgorithm:

127 """ 128 Represents the parameters of a CRC algorithm. 129 """ 130 131 # FIXME: Instances are supposed to be immutable, but attributes are 132 # writable. 133

134 - def __init__(self, width, polynomial, name=None, seed=0, 135 lsbFirst=False, lsbFirstData=None, xorMask=0):

136 """ 137 :param width: 138 139 The number of bits in the CRC register, or equivalently, the 140 degree of the polynomial. 141 142 :type width: 143 144 an integer 145 146 :param polynomial: 147 148 The generator polynomial as a sequence of exponents 149 150 :type polynomial: 151 152 sequence or integer 153 154 :param name: 155 156 A name identifying algorithm. 157 158 :type name: 159 160 *str* 161 162 :param seed: 163 164 The initial value to load into the register. (This is the 165 value without *xorMask* applied.) 166 167 :type seed: 168 169 an integer 170 171 :param lsbFirst: 172 173 If ``true``, the register shifts toward the 174 least-significant bit (sometimes called the *reflected* or 175 *reversed* algorithim). Otherwise, the register shifts 176 toward the most-significant bit. 177 178 :type lsbFirst: 179 180 *bool* 181 182 :param lsbFirstData: 183 184 If ``true``, input data is taken least-significant bit 185 first. Otherwise, data is taken most-significant bit first. 186 If ``None`` or not given, the value of *lsbFirst* is used. 187 188 :type lsbFirstData: 189 190 *bool* 191 192 :param xorMask: 193 194 An integer mask indicating which bits should be inverted 195 when returning the final result. This is also used for the 196 input value if provided. 197 198 :type xorMask: 199 200 an integer 201 """ 202 203 if width > 0: 204 try: 205 polyMask = long(polynomial) 206 except TypeError: 207 # Guess it is already a sequence of exponents. 208 polynomial = list(polynomial) 209 polynomial.sort() 210 polynomial.reverse() 211 polynomial = tuple(polynomial) 212 else: 213 # Convert a mask to a tuple of exponents. 214 if lsbFirst: 215 polyMask = reflect(polyMask, width) 216 polynomial = (width,) 217 for i in range(width-1,-1,-1): 218 if (polyMask >> i) & 1: 219 polynomial += (i,) 220 221 if polynomial[:1] != (width,): 222 ValueError("mismatch between width and polynomial degree") 223 224 self.width = width 225 self.polynomial = polynomial 226 self.name = name 227 self.seed = seed 228 self.lsbFirst = lsbFirst 229 self.lsbFirstData = lsbFirstData 230 self.xorMask = xorMask 231 232 if not hasattr(width, "__rlshift__"): 233 raise ValueError

234 235 # FIXME: Need more checking of parameters. 236

237 - def __repr__(self):

238 info = "" 239 if self.name is not None: 240 info = ' "%s"' % str(self.name) 241 result = "<%s.%s%s @ %#x>" % ( 242 self.__class__.__module__, 243 self.__class__.__name__, 244 info, id(self)) 245 return result

246

247 - def calcString(self, s, value=None):

248 """ 249 Calculate the CRC of the 8-bit string *s*. 250 """ 251 r = CrcRegister(self, value) 252 r.takeString(s) 253 return r.getFinalValue()

254

255 - def calcWord(self, word, width, value=None):

256 """ 257 Calculate the CRC of the integer *word* as a sequence of 258 *width* bits. 259 """ 260 r = CrcRegister(self, value) 261 r.takeWord(word, width) 262 return r.getFinalValue()

263

264 - def reflect(self):

265 """ 266 Return the algorithm with the bit-order reversed. 267 """ 268 ca = CrcAlgorithm(0, 0) 269 ca._initFromOther(self) 270 ca.lsbFirst = not self.lsbFirst 271 if self.lsbFirstData is not None: 272 ca.lsbFirstData = not self.lsbFirstData 273 if ca.name: 274 ca.name += " reflected" 275 return ca

276

277 - def reverse(self):

278 """ 279 Return the algorithm with the reverse polynomial. 280 """ 281 ca = CrcAlgorithm(0, 0) 282 ca._initFromOther(self) 283 ca.polynomial = [ (self.width - e) for e in self.polynomial ] 284 ca.polynomial.sort() 285 ca.polynomial.reverse() 286 ca.polynomial = tuple(ca.polynomial) 287 if ca.name: 288 ca.name += " reversed" 289 return ca

290

291 - def _initFromOther(self, other):

292 self.width = other.width 293 self.polynomial = other.polynomial 294 self.name = other.name 295 self.seed = other.seed 296 self.lsbFirst = other.lsbFirst 297 self.lsbFirstData = other.lsbFirstData 298 self.xorMask = other.xorMask

299 300

301 -class CrcRegister:

302 """ 303 Holds the intermediate state of the CRC algorithm. 304 """ 305

306 - def __init__(self, crcAlgorithm, value=None):

307 """ 308 :param crcAlgorithm: 309 310 The CRC algorithm to use. 311 312 :type crcAlgorithm: 313 314 `CrcAlgorithm` 315 316 :param value: 317 318 The initial register value to use. The result previous of a 319 previous CRC calculation, can be used here to continue 320 calculation with more data. If this parameter is ``None`` 321 or not given, the register will be initialized with 322 algorithm's default seed value. 323 324 :type value: 325 326 an integer 327 """ 328 329 self.crcAlgorithm = crcAlgorithm 330 p = crcAlgorithm 331 332 self.bitMask = (1 << p.width) - 1 333 334 word = 0 335 for n in p.polynomial: 336 word |= 1 << n 337 self.polyMask = word & self.bitMask 338 339 if p.lsbFirst: 340 self.polyMask = reflect(self.polyMask, p.width) 341 342 if p.lsbFirst: 343 self.inBitMask = 1 << (p.width - 1) 344 self.outBitMask = 1 345 else: 346 self.inBitMask = 1 347 self.outBitMask = 1 << (p.width - 1) 348 349 if p.lsbFirstData is not None: 350 self.lsbFirstData = p.lsbFirstData 351 else: 352 self.lsbFirstData = p.lsbFirst 353 354 self.reset() 355 356 if value is not None: 357 self.value = value ^ p.xorMask

358

359 - def __str__(self):

360 return formatBinaryString(self.value, self.crcAlgorithm.width)

361

362 - def reset(self):

363 """ 364 Reset the state of the register with the default seed value. 365 """ 366 self.value = long(self.crcAlgorithm.seed)

367

368 - def takeBit(self, bit):

369 """ 370 Process a single input bit. 371 """ 372 outBit = ((self.value & self.outBitMask) != 0) 373 if self.crcAlgorithm.lsbFirst: 374 self.value >>= 1 375 else: 376 self.value <<= 1 377 self.value &= self.bitMask 378 if outBit ^ bool(bit): 379 self.value ^= self.polyMask

380

381 - def takeWord(self, word, width=8):

382 """ 383 Process a binary input word. 384 385 :param word: 386 387 The input word. Since this can be a Python ``long``, there 388 is no coded limit to the number of bits the word can 389 represent. 390 391 :type word: 392 393 an integer 394 395 :param width: 396 397 The number of bits *word* represents. 398 399 :type width: 400 401 an integer 402 """ 403 if self.lsbFirstData: 404 bitList = range(0,width) 405 else: 406 bitList = range(width-1,-1,-1) 407 for n in bitList: 408 self.takeBit((word >> n) & 1)

409

410 - def takeString(self, s):

411 """ 412 Process a string as input. It is handled as a sequence of 413 8-bit integers. 414 """ 415 for c in s: 416 self.takeWord(ord(c))

417

418 - def getValue(self):

419 """ 420 Return the current value of the register as an integer. 421 """ 422 return self.value

423

424 - def getFinalValue(self):

425 """ 426 Return the current value of the register as an integer with 427 *xorMask* applied. This can be used after all input data is 428 processed to obtain the final result. 429 """ 430 p = self.crcAlgorithm 431 return self.value ^ p.xorMask

432 433

434 -def reflect(value, width):

435 return sum( 436 ((value >> x) & 1) << (width - 1 - x) 437 for x in range(width))

438

439 -def formatBinaryString(value, width):

440 return "".join( 441 "01"[(value >> i) & 1] for i in range(width-1,-1,-1))

442 443 # Some standard algorithms are defined here. I believe I was able to 444 # verify the correctness of each of these in some way (against an 445 # existing implementation or sample data with a known result). 446 447 #: Same CRC algorithm as Python's zlib.crc32 448 CRC32 = CrcAlgorithm( 449 name = "CRC-32", 450 width = 32, 451 polynomial = (32, 26, 23, 22, 16, 12, 11, 10, 8, 7, 5, 4, 2, 1, 0), 452 seed = 0xFFFFFFFF, 453 lsbFirst = True, 454 xorMask = 0xFFFFFFFF) 455 456 CRC16 = CrcAlgorithm( 457 name = "CRC-16", 458 width = 16, 459 polynomial = (16, 15, 2, 0), 460 seed = 0x0000, 461 lsbFirst = True, 462 xorMask = 0x0000) 463 464 #: Used in USB data packets. 465 CRC16_USB = CrcAlgorithm( 466 name = "CRC-16-USB", 467 width = 16, 468 polynomial = (16, 15, 2, 0), 469 seed = 0xFFFF, 470 lsbFirst = True, 471 xorMask = 0xFFFF) 472 473 CRC_CCITT = CrcAlgorithm( 474 name = "CRC-CCITT", 475 width = 16, 476 polynomial = (16, 12, 5, 0), 477 seed = 0xFFFF, 478 lsbFirst = False, 479 xorMask = 0x0000) 480 481 #: This is the algorithm used in X.25 and for the HDLC 2-byte FCS. 482 CRC_HDLC = CrcAlgorithm( 483 name = "CRC-HDLC", 484 width = 16, 485 polynomial = (16, 12, 5, 0), 486 seed = 0xFFFF, 487 lsbFirst = True, 488 xorMask = 0xFFFF) 489 490 #: Used in ATM HEC and SMBus. 491 CRC8_SMBUS = CrcAlgorithm( 492 name = "CRC-8-SMBUS", 493 width = 8, 494 polynomial = (8, 2, 1, 0), 495 seed = 0, 496 lsbFirst = False, 497 xorMask = 0) 498 499 #: Used in RFC-2440 and MIL STD 188-184. 500 CRC24 = CrcAlgorithm( 501 name = "CRC-24", 502 width = 24, 503 polynomial = (24, 23, 18, 17, 14, 11, 10, 7, 6, 5, 4, 3, 1, 0), 504 seed = 0xB704CE, 505 lsbFirst = False, 506 xorMask = 0) 507 508 #: Used in Controller Area Network frames. 509 CRC15 = CrcAlgorithm( 510 name = "CRC-15", 511 width = 15, 512 polynomial = (15, 14, 10, 8, 7, 4, 3, 0), 513 seed = 0, 514 lsbFirst = False, 515 xorMask = 0) 516 517 #: Used in iSCSI (RFC-3385); usually credited to Guy Castagnoli. 518 CRC32C = CrcAlgorithm( 519 name = "CRC-32C", 520 width = 32, 521 polynomial = (32, 28, 27, 26, 25, 23, 22, 20, 19, 18, 14, 13, 11, 10, 9, 8, 6, 0), 522 seed = 0xFFFFFFFF, 523 lsbFirst = True, 524 xorMask = 0xFFFFFFFF) 525 526 #: CRC used in USB Token and Start-Of-Frame packets 527 CRC5_USB = CrcAlgorithm( 528 name = "CRC-5-USB", 529 width = 5, 530 polynomial = (5, 2, 0), 531 seed = 0x1F, 532 lsbFirst = True, 533 xorMask = 0x1F) 534 535 #: ISO 3309 536 CRC64 = CrcAlgorithm( 537 name = "CRC-64", 538 width = 64, 539 polynomial = (64, 4, 3, 1, 0), 540 seed = 0, 541 lsbFirst = True, 542 xorMask = 0) 543 544 #: This is just to show off the ability to handle a very wide CRC. 545 # If this is a standard, I don't know where it is from. I found the 546 # polynomial on a web page of an apparent Czech "Lady Killer" 547 # <http://www.volny.cz/lk77/crc256mmx/>. 548 CRC256 = CrcAlgorithm( 549 name = "CRC-256", 550 width = 256, 551 polynomial = 0x82E2443E6320383A20B8A2A0A1EA91A3CCA99A30C5205038349C82AAA3A8FD27, 552 seed = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, 553 lsbFirst = True, 554 xorMask = 0) 555 556 # For the following I haven't found complete information and/or have 557 # no way to verify the result. I started with the list on Wikipedia 558 # <http://en.wikipedia.org/wiki/Cyclic_redundancy_check>. 559 # 560 #CRC4_ITU = CrcAlgorithm( 561 # name = "CRC-4-ITU", 562 # width = 4, 563 # polynomial = (4, 1, 0), 564 # seed = ?, 565 # lsbFirst = ?, 566 # xorMask = ?) 567 # 568 #CRC5_ITU = CrcAlgorithm( 569 # name = "CRC-5-ITU", 570 # width = 5, 571 # polynomial = (5, 4, 2, 0), 572 # seed = ?, 573 # lsbFirst = ?, 574 # xorMask = ?) 575 # 576 #CRC6_ITU = CrcAlgorithm( 577 # name = "CRC-6-ITU", 578 # width = 6, 579 # polynomial = (6, 1, 0), 580 # seed = ?, 581 # lsbFirst = ?, 582 # xorMask = ?) 583 # 584 #CRC7 = CrcAlgorithm( 585 # name = "CRC-7", 586 # width = 7, 587 # polynomial = (7, 3, 0), 588 # seed = ?, 589 # lsbFirst = ?, 590 # xorMask = ?) 591 # 592 #CRC8_CCITT = CrcAlgorithm( 593 # name = "CRC-8-CCITT", 594 # width = 8, 595 # polynomial = (8, 7, 3, 2, 0), 596 # seed = ?, 597 # lsbFirst = ?, 598 # xorMask = ?) 599 # 600 #CRC8_DALLAS = CrcAlgorithm( 601 # name = "CRC-8-Dallas", 602 # width = 8, 603 # polynomial = (8, 5, 4, 0), 604 # seed = ?, 605 # lsbFirst = ?, 606 # xorMask = ?) 607 # 608 #CRC8 = CrcAlgorithm( 609 # name = "CRC-8", 610 # width = 8, 611 # polynomial = (8, 7, 6, 4, 2, 0), 612 # seed = ?, 613 # lsbFirst = ?, 614 # xorMask = ?) 615 # 616 #CRC8_J1850 = CrcAlgorithm( 617 # name = "CRC-8-J1850", 618 # width = 8, 619 # polynomial = (8, 4, 3, 2, 0), 620 # seed = ?, 621 # lsbFirst = ?, 622 # xorMask = ?) 623 # 624 #CRC10 = CrcAlgorithm( 625 # name = "CRC-10", 626 # width = 10, 627 # polynomial = (10, 9, 5, 4, 1, 0), 628 # seed = ?, 629 # lsbFirst = ?, 630 # xorMask = ?) 631 # 632 #CRC12 = CrcAlgorithm( 633 # name = "CRC-12", 634 # width = 12, 635 # polynomial = (12, 11, 3, 2, 1, 0), 636 # seed = ?, 637 # lsbFirst = ?, 638 # xorMask = ?) 639 # 640 #CRC64_ECMA182 = CrcAlgorithm( 641 # name = "CRC-64-ECMA-182", 642 # width = 64, 643 # polynomial = (64, 62, 57, 55, 54, 53, 52, 47, 46, 45, 40, 39, 38, 37, 35, 33, 32, 31, 29, 27, 24, 23, 22, 21, 19, 17, 13, 12, 10, 9, 7, 4, 1, 0), 644 # seed = ?, 645 # lsbFirst = ?, 646 # xorMask = ?) 647

648 -def _callCalcString123456789(v):

649 return v.calcString('123456789')

650

651 -def _printResults(fn=_callCalcString123456789):

652 import sys 653 d = sys.modules[__name__].__dict__ 654 algorithms = sorted( 655 (v for (k, v) in d.iteritems() if isinstance(v, CrcAlgorithm)), 656 key=lambda v: (v.width, v.name)) 657 for a in algorithms: 658 format = ("%%0%dX" % ((a.width + 3) // 4)) 659 print "%s:" % a.name, 660 print format % fn(a)

661

662 -def _test():

663 import doctest, sys 664 return doctest.testmod(sys.modules[__name__])

665 666 if __name__ == "__main__": 667 _test() 668