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'''Unit tests for crcmod functionality''' 24 25 26import unittest 27 28import binascii 29 30from crcmod import mkCrcFun, Crc 31try: 32 from crcmod.crcmod import _usingExtension 33 from crcmod.predefined import PredefinedCrc 34 from crcmod.predefined import mkPredefinedCrcFun 35 from crcmod.predefined import _crc_definitions as _predefined_crc_definitions 36except ImportError: 37 from crcmod import _usingExtension 38 from predefined import PredefinedCrc 39 from predefined import mkPredefinedCrcFun 40 from predefined import _crc_definitions as _predefined_crc_definitions 41 42 43#----------------------------------------------------------------------------- 44# This polynomial was chosen because it is the product of two irreducible 45# polynomials. 46# g8 = (x^7+x+1)*(x+1) 47g8 = 0x185 48 49#----------------------------------------------------------------------------- 50# The following reproduces all of the entries in the Numerical Recipes table. 51# This is the standard CCITT polynomial. 52g16 = 0x11021 53 54#----------------------------------------------------------------------------- 55g24 = 0x15D6DCB 56 57#----------------------------------------------------------------------------- 58# This is the standard AUTODIN-II polynomial which appears to be used in a 59# wide variety of standards and applications. 60g32 = 0x104C11DB7 61 62 63#----------------------------------------------------------------------------- 64# I was able to locate a couple of 64-bit polynomials on the web. To make it 65# easier to input the representation, define a function that builds a 66# polynomial from a list of the bits that need to be turned on. 67 68def polyFromBits(bits): 69 p = 0L 70 for n in bits: 71 p = p | (1L << n) 72 return p 73 74# The following is from the paper "An Improved 64-bit Cyclic Redundancy Check 75# for Protein Sequences" by David T. Jones 76 77g64a = polyFromBits([64, 63, 61, 59, 58, 56, 55, 52, 49, 48, 47, 46, 44, 41, 78 37, 36, 34, 32, 31, 28, 26, 23, 22, 19, 16, 13, 12, 10, 9, 6, 4, 79 3, 0]) 80 81# The following is from Standard ECMA-182 "Data Interchange on 12,7 mm 48-Track 82# Magnetic Tape Cartridges -DLT1 Format-", December 1992. 83 84g64b = polyFromBits([64, 62, 57, 55, 54, 53, 52, 47, 46, 45, 40, 39, 38, 37, 85 35, 33, 32, 31, 29, 27, 24, 23, 22, 21, 19, 17, 13, 12, 10, 9, 7, 86 4, 1, 0]) 87 88#----------------------------------------------------------------------------- 89# This class is used to check the CRC calculations against a direct 90# implementation using polynomial division. 91 92class poly: 93 '''Class implementing polynomials over the field of integers mod 2''' 94 def __init__(self,p): 95 p = long(p) 96 if p < 0: raise ValueError('invalid polynomial') 97 self.p = p 98 99 def __long__(self): 100 return self.p 101 102 def __eq__(self,other): 103 return self.p == other.p 104 105 def __ne__(self,other): 106 return self.p != other.p 107 108 # To allow sorting of polynomials, use their long integer form for 109 # comparison 110 def __cmp__(self,other): 111 return cmp(self.p, other.p) 112 113 def __nonzero__(self): 114 return self.p != 0L 115 116 def __neg__(self): 117 return self # These polynomials are their own inverse under addition 118 119 def __invert__(self): 120 n = max(self.deg() + 1, 1) 121 x = (1L << n) - 1 122 return poly(self.p ^ x) 123 124 def __add__(self,other): 125 return poly(self.p ^ other.p) 126 127 def __sub__(self,other): 128 return poly(self.p ^ other.p) 129 130 def __mul__(self,other): 131 a = self.p 132 b = other.p 133 if a == 0 or b == 0: return poly(0) 134 x = 0L 135 while b: 136 if b&1: 137 x = x ^ a 138 a = a<<1 139 b = b>>1 140 return poly(x) 141 142 def __divmod__(self,other): 143 u = self.p 144 m = self.deg() 145 v = other.p 146 n = other.deg() 147 if v == 0: raise ZeroDivisionError('polynomial division by zero') 148 if n == 0: return (self,poly(0)) 149 if m < n: return (poly(0),self) 150 k = m-n 151 a = 1L << m 152 v = v << k 153 q = 0L 154 while k > 0: 155 if a & u: 156 u = u ^ v 157 q = q | 1L 158 q = q << 1 159 a = a >> 1 160 v = v >> 1 161 k -= 1 162 if a & u: 163 u = u ^ v 164 q = q | 1L 165 return (poly(q),poly(u)) 166 167 def __div__(self,other): 168 return self.__divmod__(other)[0] 169 170 def __mod__(self,other): 171 return self.__divmod__(other)[1] 172 173 def __repr__(self): 174 return 'poly(0x%XL)' % self.p 175 176 def __str__(self): 177 p = self.p 178 if p == 0: return '0' 179 lst = { 0:[], 1:['1'], 2:['x'], 3:['1','x'] }[p&3] 180 p = p>>2 181 n = 2 182 while p: 183 if p&1: lst.append('x^%d' % n) 184 p = p>>1 185 n += 1 186 lst.reverse() 187 return '+'.join(lst) 188 189 def deg(self): 190 '''return the degree of the polynomial''' 191 a = self.p 192 if a == 0: return -1 193 n = 0 194 while a >= 0x10000L: 195 n += 16 196 a = a >> 16 197 a = int(a) 198 while a > 1: 199 n += 1 200 a = a >> 1 201 return n 202 203#----------------------------------------------------------------------------- 204# The following functions compute the CRC using direct polynomial division. 205# These functions are checked against the result of the table driven 206# algorithms. 207 208g8p = poly(g8) 209x8p = poly(1L<<8) 210def crc8p(d): 211 d = map(ord, d) 212 p = 0L 213 for i in d: 214 p = p*256L + i 215 p = poly(p) 216 return long(p*x8p%g8p) 217 218g16p = poly(g16) 219x16p = poly(1L<<16) 220def crc16p(d): 221 d = map(ord, d) 222 p = 0L 223 for i in d: 224 p = p*256L + i 225 p = poly(p) 226 return long(p*x16p%g16p) 227 228g24p = poly(g24) 229x24p = poly(1L<<24) 230def crc24p(d): 231 d = map(ord, d) 232 p = 0L 233 for i in d: 234 p = p*256L + i 235 p = poly(p) 236 return long(p*x24p%g24p) 237 238g32p = poly(g32) 239x32p = poly(1L<<32) 240def crc32p(d): 241 d = map(ord, d) 242 p = 0L 243 for i in d: 244 p = p*256L + i 245 p = poly(p) 246 return long(p*x32p%g32p) 247 248g64ap = poly(g64a) 249x64p = poly(1L<<64) 250def crc64ap(d): 251 d = map(ord, d) 252 p = 0L 253 for i in d: 254 p = p*256L + i 255 p = poly(p) 256 return long(p*x64p%g64ap) 257 258g64bp = poly(g64b) 259def crc64bp(d): 260 d = map(ord, d) 261 p = 0L 262 for i in d: 263 p = p*256L + i 264 p = poly(p) 265 return long(p*x64p%g64bp) 266 267 268class KnownAnswerTests(unittest.TestCase): 269 test_messages = [ 270 'T', 271 'CatMouse987654321', 272 ] 273 274 known_answers = [ 275 [ (g8,0,0), (0xFE, 0x9D) ], 276 [ (g8,-1,1), (0x4F, 0x9B) ], 277 [ (g8,0,1), (0xFE, 0x62) ], 278 [ (g16,0,0), (0x1A71, 0xE556) ], 279 [ (g16,-1,1), (0x1B26, 0xF56E) ], 280 [ (g16,0,1), (0x14A1, 0xC28D) ], 281 [ (g24,0,0), (0xBCC49D, 0xC4B507) ], 282 [ (g24,-1,1), (0x59BD0E, 0x0AAA37) ], 283 [ (g24,0,1), (0xD52B0F, 0x1523AB) ], 284 [ (g32,0,0), (0x6B93DDDB, 0x12DCA0F4) ], 285 [ (g32,0xFFFFFFFFL,1), (0x41FB859FL, 0xF7B400A7L) ], 286 [ (g32,0,1), (0x6C0695EDL, 0xC1A40EE5L) ], 287 [ (g32,0,1,0xFFFFFFFF), (0xBE047A60L, 0x084BFF58L) ], 288 ] 289 290 def test_known_answers(self): 291 for crcfun_params, v in self.known_answers: 292 crcfun = mkCrcFun(*crcfun_params) 293 self.assertEqual(crcfun('',0), 0, "Wrong answer for CRC parameters %s, input ''" % (crcfun_params,)) 294 for i, msg in enumerate(self.test_messages): 295 self.assertEqual(crcfun(msg), v[i], "Wrong answer for CRC parameters %s, input '%s'" % (crcfun_params,msg)) 296 self.assertEqual(crcfun(msg[4:], crcfun(msg[:4])), v[i], "Wrong answer for CRC parameters %s, input '%s'" % (crcfun_params,msg)) 297 self.assertEqual(crcfun(msg[-1:], crcfun(msg[:-1])), v[i], "Wrong answer for CRC parameters %s, input '%s'" % (crcfun_params,msg)) 298 299 300class CompareReferenceCrcTest(unittest.TestCase): 301 test_messages = [ 302 '', 303 'T', 304 '123456789', 305 'CatMouse987654321', 306 ] 307 308 test_poly_crcs = [ 309 [ (g8,0,0), crc8p ], 310 [ (g16,0,0), crc16p ], 311 [ (g24,0,0), crc24p ], 312 [ (g32,0,0), crc32p ], 313 [ (g64a,0,0), crc64ap ], 314 [ (g64b,0,0), crc64bp ], 315 ] 316 317 @staticmethod 318 def reference_crc32(d, crc=0): 319 """This function modifies the return value of binascii.crc32 320 to be an unsigned 32-bit value. I.e. in the range 0 to 2**32-1.""" 321 # Work around the future warning on constants. 322 if crc > 0x7FFFFFFFL: 323 x = int(crc & 0x7FFFFFFFL) 324 crc = x | -2147483648 325 x = binascii.crc32(d,crc) 326 return long(x) & 0xFFFFFFFFL 327 328 def test_compare_crc32(self): 329 """The binascii module has a 32-bit CRC function that is used in a wide range 330 of applications including the checksum used in the ZIP file format. 331 This test compares the CRC-32 implementation of this crcmod module to 332 that of binascii.crc32.""" 333 # The following function should produce the same result as 334 # self.reference_crc32 which is derived from binascii.crc32. 335 crc32 = mkCrcFun(g32,0,1,0xFFFFFFFF) 336 337 for msg in self.test_messages: 338 self.assertEqual(crc32(msg), self.reference_crc32(msg)) 339 340 def test_compare_poly(self): 341 """Compare various CRCs of this crcmod module to a pure 342 polynomial-based implementation.""" 343 for crcfun_params, crc_poly_fun in self.test_poly_crcs: 344 # The following function should produce the same result as 345 # the associated polynomial CRC function. 346 crcfun = mkCrcFun(*crcfun_params) 347 348 for msg in self.test_messages: 349 self.assertEqual(crcfun(msg), crc_poly_fun(msg)) 350 351 352class CrcClassTest(unittest.TestCase): 353 """Verify the Crc class""" 354 355 msg = 'CatMouse987654321' 356 357 def test_simple_crc32_class(self): 358 """Verify the CRC class when not using xorOut""" 359 crc = Crc(g32) 360 361 str_rep = \ 362'''poly = 0x104C11DB7 363reverse = True 364initCrc = 0xFFFFFFFF 365xorOut = 0x00000000 366crcValue = 0xFFFFFFFF''' 367 self.assertEqual(str(crc), str_rep) 368 self.assertEqual(crc.digest(), '\xff\xff\xff\xff') 369 self.assertEqual(crc.hexdigest(), 'FFFFFFFF') 370 371 crc.update(self.msg) 372 self.assertEqual(crc.crcValue, 0xF7B400A7L) 373 self.assertEqual(crc.digest(), '\xf7\xb4\x00\xa7') 374 self.assertEqual(crc.hexdigest(), 'F7B400A7') 375 376 # Verify the .copy() method 377 x = crc.copy() 378 self.assertTrue(x is not crc) 379 str_rep = \ 380'''poly = 0x104C11DB7 381reverse = True 382initCrc = 0xFFFFFFFF 383xorOut = 0x00000000 384crcValue = 0xF7B400A7''' 385 self.assertEqual(str(crc), str_rep) 386 self.assertEqual(str(x), str_rep) 387 388 def test_full_crc32_class(self): 389 """Verify the CRC class when using xorOut""" 390 391 crc = Crc(g32, initCrc=0, xorOut= ~0L) 392 393 str_rep = \ 394'''poly = 0x104C11DB7 395reverse = True 396initCrc = 0x00000000 397xorOut = 0xFFFFFFFF 398crcValue = 0x00000000''' 399 self.assertEqual(str(crc), str_rep) 400 self.assertEqual(crc.digest(), '\x00\x00\x00\x00') 401 self.assertEqual(crc.hexdigest(), '00000000') 402 403 crc.update(self.msg) 404 self.assertEqual(crc.crcValue, 0x84BFF58L) 405 self.assertEqual(crc.digest(), '\x08\x4b\xff\x58') 406 self.assertEqual(crc.hexdigest(), '084BFF58') 407 408 # Verify the .copy() method 409 x = crc.copy() 410 self.assertTrue(x is not crc) 411 str_rep = \ 412'''poly = 0x104C11DB7 413reverse = True 414initCrc = 0x00000000 415xorOut = 0xFFFFFFFF 416crcValue = 0x084BFF58''' 417 self.assertEqual(str(crc), str_rep) 418 self.assertEqual(str(x), str_rep) 419 420 # Verify the .new() method 421 y = crc.new() 422 self.assertTrue(y is not crc) 423 self.assertTrue(y is not x) 424 str_rep = \ 425'''poly = 0x104C11DB7 426reverse = True 427initCrc = 0x00000000 428xorOut = 0xFFFFFFFF 429crcValue = 0x00000000''' 430 self.assertEqual(str(y), str_rep) 431 432 433class PredefinedCrcTest(unittest.TestCase): 434 """Verify the predefined CRCs""" 435 436 test_messages_for_known_answers = [ 437 '', # Test cases below depend on this first entry being the empty string. 438 'T', 439 'CatMouse987654321', 440 ] 441 442 known_answers = [ 443 [ 'crc-aug-ccitt', (0x1D0F, 0xD6ED, 0x5637) ], 444 [ 'x-25', (0x0000, 0xE4D9, 0x0A91) ], 445 [ 'crc-32', (0x00000000, 0xBE047A60, 0x084BFF58) ], 446 ] 447 448 def test_known_answers(self): 449 for crcfun_name, v in self.known_answers: 450 crcfun = mkPredefinedCrcFun(crcfun_name) 451 self.assertEqual(crcfun('',0), 0, "Wrong answer for CRC '%s', input ''" % crcfun_name) 452 for i, msg in enumerate(self.test_messages_for_known_answers): 453 self.assertEqual(crcfun(msg), v[i], "Wrong answer for CRC %s, input '%s'" % (crcfun_name,msg)) 454 self.assertEqual(crcfun(msg[4:], crcfun(msg[:4])), v[i], "Wrong answer for CRC %s, input '%s'" % (crcfun_name,msg)) 455 self.assertEqual(crcfun(msg[-1:], crcfun(msg[:-1])), v[i], "Wrong answer for CRC %s, input '%s'" % (crcfun_name,msg)) 456 457 def test_class_with_known_answers(self): 458 for crcfun_name, v in self.known_answers: 459 for i, msg in enumerate(self.test_messages_for_known_answers): 460 crc1 = PredefinedCrc(crcfun_name) 461 crc1.update(msg) 462 self.assertEqual(crc1.crcValue, v[i], "Wrong answer for crc1 %s, input '%s'" % (crcfun_name,msg)) 463 464 crc2 = crc1.new() 465 # Check that crc1 maintains its same value, after .new() call. 466 self.assertEqual(crc1.crcValue, v[i], "Wrong state for crc1 %s, input '%s'" % (crcfun_name,msg)) 467 # Check that the new class instance created by .new() contains the initialisation value. 468 # This depends on the first string in self.test_messages_for_known_answers being 469 # the empty string. 470 self.assertEqual(crc2.crcValue, v[0], "Wrong state for crc2 %s, input '%s'" % (crcfun_name,msg)) 471 472 crc2.update(msg) 473 # Check that crc1 maintains its same value, after crc2 has called .update() 474 self.assertEqual(crc1.crcValue, v[i], "Wrong state for crc1 %s, input '%s'" % (crcfun_name,msg)) 475 # Check that crc2 contains the right value after calling .update() 476 self.assertEqual(crc2.crcValue, v[i], "Wrong state for crc2 %s, input '%s'" % (crcfun_name,msg)) 477 478 def test_function_predefined_table(self): 479 for table_entry in _predefined_crc_definitions: 480 # Check predefined function 481 crc_func = mkPredefinedCrcFun(table_entry['name']) 482 calc_value = crc_func("123456789") 483 self.assertEqual(calc_value, table_entry['check'], "Wrong answer for CRC '%s'" % table_entry['name']) 484 485 def test_class_predefined_table(self): 486 for table_entry in _predefined_crc_definitions: 487 # Check predefined class 488 crc1 = PredefinedCrc(table_entry['name']) 489 crc1.update("123456789") 490 self.assertEqual(crc1.crcValue, table_entry['check'], "Wrong answer for CRC '%s'" % table_entry['name']) 491 492 493def runtests(): 494 print "Using extension:", _usingExtension 495 print 496 unittest.main() 497 498 499if __name__ == '__main__': 500 runtests() 501