Mercurial > hgrepos > Python > apps > py-cutils

comparison cutils/crcmod/python3/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 algorithms in the hashlib module in the Python standard library. These
30 instances also provide a method for generating a C/C++ function to compute
31 the CRC.
32
33 mkCrcFun -- create a Python function to compute the CRC using the specified
34 polynomial and initial value. This provides a much simpler interface if
35 all you need is a function for CRC calculation.
36 '''
37
38 __all__ = '''mkCrcFun Crc'''.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.
43 try:
44 from . import _crcfunext as _crcfun
45 _usingExtension = True
46 except ImportError:
47 from . import _crcfunpy as _crcfun
48 _usingExtension = False
49
50 import sys, struct
51
52 #-----------------------------------------------------------------------------
53 class Crc:
54 '''Compute a Cyclic Redundancy Check (CRC) using the specified polynomial.
55
56 Instances of this class have the same interface as the algorithms in the
57 hashlib module in the Python standard library. See the documentation of
58 this module 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. The bits in this integer are the
72 coefficients of the polynomial. The only polynomials allowed are those
73 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=~0, 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(crc & 0xFF)
162 crc = crc >> 8
163 n -= 1
164 lst.reverse()
165 return bytes(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 #-----------------------------------------------------------------------------
268 def mkCrcFun(poly, initCrc=~0, 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
294 def _verifyPoly(poly):
295 msg = 'The degree of the polynomial must be 8, 16, 24, 32 or 64'
296 for n in (8,16,24,32,64):
297 low = 1<<n
298 high = low*2
299 if low <= poly < high:
300 return n
301 raise ValueError(msg)
302
303 #-----------------------------------------------------------------------------
304 # Bit reverse the input value.
305
306 def _bitrev(x, n):
307 y = 0
308 for i in range(n):
309 y = (y << 1) | (x & 1)
310 x = x >> 1
311 return y
312
313 #-----------------------------------------------------------------------------
314 # The following functions compute the CRC for a single byte. These are used
315 # to build up the tables needed in the CRC algorithm. Assumes the high order
316 # bit of the polynomial has been stripped off.
317
318 def _bytecrc(crc, poly, n):
319 mask = 1<<(n-1)
320 for i in range(8):
321 if crc & mask:
322 crc = (crc << 1) ^ poly
323 else:
324 crc = crc << 1
325 mask = (1<<n) - 1
326 crc = crc & mask
327 return crc
328
329 def _bytecrc_r(crc, poly, n):
330 for i in range(8):
331 if crc & 1:
332 crc = (crc >> 1) ^ poly
333 else:
334 crc = crc >> 1
335 mask = (1<<n) - 1
336 crc = crc & mask
337 return crc
338
339 #-----------------------------------------------------------------------------
340 # The following functions compute the table needed to compute the CRC. The
341 # table is returned as a list. Note that the array module does not support
342 # 64-bit integers on a 32-bit architecture as of Python 2.3.
343 #
344 # These routines assume that the polynomial and the number of bits in the CRC
345 # have been checked for validity by the caller.
346
347 def _mkTable(poly, n):
348 mask = (1<<n) - 1
349 poly = poly & mask
350 table = [_bytecrc(i<<(n-8),poly,n) for i in range(256)]
351 return table
352
353 def _mkTable_r(poly, n):
354 mask = (1<<n) - 1
355 poly = _bitrev(poly & mask, n)
356 table = [_bytecrc_r(i,poly,n) for i in range(256)]
357 return table
358
359 #-----------------------------------------------------------------------------
360 # Map the CRC size onto the functions that handle these sizes.
361
362 _sizeMap = {
363 8 : [_crcfun._crc8, _crcfun._crc8r],
364 16 : [_crcfun._crc16, _crcfun._crc16r],
365 24 : [_crcfun._crc24, _crcfun._crc24r],
366 32 : [_crcfun._crc32, _crcfun._crc32r],
367 64 : [_crcfun._crc64, _crcfun._crc64r],
368 }
369
370 #-----------------------------------------------------------------------------
371 # Build a mapping of size to struct module type code. This table is
372 # constructed dynamically so that it has the best chance of picking the best
373 # code to use for the platform we are running on. This should properly adapt
374 # to 32 and 64 bit machines.
375
376 _sizeToTypeCode = {}
377
378 for typeCode in 'B H I L Q'.split():
379 size = {1:8, 2:16, 4:32, 8:64}.get(struct.calcsize(typeCode),None)
380 if size is not None and size not in _sizeToTypeCode:
381 _sizeToTypeCode[size] = '256%s' % typeCode
382
383 _sizeToTypeCode[24] = _sizeToTypeCode[32]
384
385 del typeCode, size
386
387 #-----------------------------------------------------------------------------
388 # The following function validates the parameters of the CRC, namely,
389 # poly, and initial/final XOR values.
390 # It returns the size of the CRC (in bits), and "sanitized" initial/final XOR values.
391
392 def _verifyParams(poly, initCrc, xorOut):
393 sizeBits = _verifyPoly(poly)
394
395 mask = (1<<sizeBits) - 1
396
397 # Adjust the initial CRC to the correct data type (unsigned value).
398 initCrc = initCrc & mask
399
400 # Similar for XOR-out value.
401 xorOut = xorOut & mask
402
403 return (sizeBits, initCrc, xorOut)
404
405 #-----------------------------------------------------------------------------
406 # The following function returns a Python function to compute the CRC.
407 #
408 # It must be passed parameters that are already verified & sanitized by
409 # _verifyParams().
410 #
411 # The returned function calls a low level function that is written in C if the
412 # extension module could be loaded. Otherwise, a Python implementation is
413 # used.
414 #
415 # In addition to this function, a list containing the CRC table is returned.
416
417 def _mkCrcFun(poly, sizeBits, initCrc, rev, xorOut):
418 if rev:
419 tableList = _mkTable_r(poly, sizeBits)
420 _fun = _sizeMap[sizeBits][1]
421 else:
422 tableList = _mkTable(poly, sizeBits)
423 _fun = _sizeMap[sizeBits][0]
424
425 _table = tableList
426 if _usingExtension:
427 _table = struct.pack(_sizeToTypeCode[sizeBits], *tableList)
428
429 if xorOut == 0:
430 def crcfun(data, crc=initCrc, table=_table, fun=_fun):
431 return fun(data, crc, table)
432 else:
433 def crcfun(data, crc=initCrc, table=_table, fun=_fun):
434 return xorOut ^ fun(data, xorOut ^ crc, table)
435
436 return crcfun, tableList
437
438 #-----------------------------------------------------------------------------
439 _codeTemplate = '''// Automatically generated CRC function
440 // %(poly)s
441 %(crcType)s
442 %(name)s(%(dataType)s *data, int len, %(crcType)s crc)
443 {
444 static const %(crcType)s table[256] = {%(crcTable)s
445 };
446 %(preCondition)s
447 while (len > 0)
448 {
449 crc = %(crcAlgor)s;
450 data++;
451 len--;
452 }%(postCondition)s
453 return crc;
454 }
455 '''
456