Mercurial > hgrepos > Python > apps > py-cutils

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