Mercurial > hgrepos > Python > apps > py-cutils

comparison cutils/crcmod/python3/test.py @ 180:d038f0a9ba49

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