Squashed 'third_party/pycrc/' content from commit cb91196b9
Change-Id: Iaed6f7d683e3c11395f10f0724f973363aad2cdb
git-subtree-dir: third_party/pycrc
git-subtree-split: cb91196b920d1f892c05941ed470c7a80cba7596
diff --git a/pycrc/algorithms.py b/pycrc/algorithms.py
new file mode 100644
index 0000000..3ebcebd
--- /dev/null
+++ b/pycrc/algorithms.py
@@ -0,0 +1,235 @@
+# pycrc -- parameterisable CRC calculation utility and C source code generator
+#
+# Copyright (c) 2006-2017 Thomas Pircher <tehpeh-web@tty1.net>
+#
+# Permission is hereby granted, free of charge, to any person obtaining a copy
+# of this software and associated documentation files (the "Software"), to
+# deal in the Software without restriction, including without limitation the
+# rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+# sell copies of the Software, and to permit persons to whom the Software is
+# furnished to do so, subject to the following conditions:
+#
+# The above copyright notice and this permission notice shall be included in
+# all copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+# FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+# IN THE SOFTWARE.
+
+
+"""
+CRC algorithms implemented in Python.
+If you want to study the Python implementation of the CRC routines, then this
+is a good place to start from.
+
+The algorithms Bit by Bit, Bit by Bit Fast and Table-Driven are implemented.
+
+This module can also be used as a library from within Python.
+
+Examples
+========
+
+This is an example use of the different algorithms:
+
+ from pycrc.algorithms import Crc
+
+ crc = Crc(width = 16, poly = 0x8005,
+ reflect_in = True, xor_in = 0x0000,
+ reflect_out = True, xor_out = 0x0000)
+ print("{0:#x}".format(crc.bit_by_bit("123456789")))
+ print("{0:#x}".format(crc.bit_by_bit_fast("123456789")))
+ print("{0:#x}".format(crc.table_driven("123456789")))
+"""
+
+class Crc(object):
+ """
+ A base class for CRC routines.
+ """
+ # pylint: disable=too-many-instance-attributes
+
+ def __init__(self, width, poly, reflect_in, xor_in, reflect_out, xor_out, table_idx_width=None, slice_by=1):
+ """The Crc constructor.
+
+ The parameters are as follows:
+ width
+ poly
+ reflect_in
+ xor_in
+ reflect_out
+ xor_out
+ """
+ # pylint: disable=too-many-arguments
+
+ self.width = width
+ self.poly = poly
+ self.reflect_in = reflect_in
+ self.xor_in = xor_in
+ self.reflect_out = reflect_out
+ self.xor_out = xor_out
+ self.tbl_idx_width = table_idx_width
+ self.slice_by = slice_by
+
+ self.msb_mask = 0x1 << (self.width - 1)
+ self.mask = ((self.msb_mask - 1) << 1) | 1
+ if self.tbl_idx_width != None:
+ self.tbl_width = 1 << self.tbl_idx_width
+ else:
+ self.tbl_idx_width = 8
+ self.tbl_width = 1 << self.tbl_idx_width
+
+ self.direct_init = self.xor_in
+ self.nondirect_init = self.__get_nondirect_init(self.xor_in)
+ if self.width < 8:
+ self.crc_shift = 8 - self.width
+ else:
+ self.crc_shift = 0
+
+
+ def __get_nondirect_init(self, init):
+ """
+ return the non-direct init if the direct algorithm has been selected.
+ """
+ crc = init
+ for dummy_i in range(self.width):
+ bit = crc & 0x01
+ if bit:
+ crc ^= self.poly
+ crc >>= 1
+ if bit:
+ crc |= self.msb_mask
+ return crc & self.mask
+
+
+ def reflect(self, data, width):
+ """
+ reflect a data word, i.e. reverts the bit order.
+ """
+ # pylint: disable=no-self-use
+
+ res = data & 0x01
+ for dummy_i in range(width - 1):
+ data >>= 1
+ res = (res << 1) | (data & 0x01)
+ return res
+
+
+ def bit_by_bit(self, in_data):
+ """
+ Classic simple and slow CRC implementation. This function iterates bit
+ by bit over the augmented input message and returns the calculated CRC
+ value at the end.
+ """
+ # If the input data is a string, convert to bytes.
+ if isinstance(in_data, str):
+ in_data = bytearray(in_data, 'utf-8')
+
+ reg = self.nondirect_init
+ for octet in in_data:
+ if self.reflect_in:
+ octet = self.reflect(octet, 8)
+ for i in range(8):
+ topbit = reg & self.msb_mask
+ reg = ((reg << 1) & self.mask) | ((octet >> (7 - i)) & 0x01)
+ if topbit:
+ reg ^= self.poly
+
+ for i in range(self.width):
+ topbit = reg & self.msb_mask
+ reg = ((reg << 1) & self.mask)
+ if topbit:
+ reg ^= self.poly
+
+ if self.reflect_out:
+ reg = self.reflect(reg, self.width)
+ return (reg ^ self.xor_out) & self.mask
+
+
+ def bit_by_bit_fast(self, in_data):
+ """
+ This is a slightly modified version of the bit-by-bit algorithm: it
+ does not need to loop over the augmented bits, i.e. the Width 0-bits
+ wich are appended to the input message in the bit-by-bit algorithm.
+ """
+ # If the input data is a string, convert to bytes.
+ if isinstance(in_data, str):
+ in_data = bytearray(in_data, 'utf-8')
+
+ reg = self.direct_init
+ for octet in in_data:
+ if self.reflect_in:
+ octet = self.reflect(octet, 8)
+ for i in range(8):
+ topbit = reg & self.msb_mask
+ if octet & (0x80 >> i):
+ topbit ^= self.msb_mask
+ reg <<= 1
+ if topbit:
+ reg ^= self.poly
+ reg &= self.mask
+ if self.reflect_out:
+ reg = self.reflect(reg, self.width)
+ return reg ^ self.xor_out
+
+
+ def gen_table(self):
+ """
+ This function generates the CRC table used for the table_driven CRC
+ algorithm. The Python version cannot handle tables of an index width
+ other than 8. See the generated C code for tables with different sizes
+ instead.
+ """
+ table_length = 1 << self.tbl_idx_width
+ tbl = [[0 for i in range(table_length)] for j in range(self.slice_by)]
+ for i in range(table_length):
+ reg = i
+ if self.reflect_in:
+ reg = self.reflect(reg, self.tbl_idx_width)
+ reg = reg << (self.width - self.tbl_idx_width + self.crc_shift)
+ for dummy_j in range(self.tbl_idx_width):
+ if reg & (self.msb_mask << self.crc_shift) != 0:
+ reg = (reg << 1) ^ (self.poly << self.crc_shift)
+ else:
+ reg = (reg << 1)
+ if self.reflect_in:
+ reg = self.reflect(reg >> self.crc_shift, self.width) << self.crc_shift
+ tbl[0][i] = (reg >> self.crc_shift) & self.mask
+
+ for j in range(1, self.slice_by):
+ for i in range(table_length):
+ tbl[j][i] = (tbl[j - 1][i] >> 8) ^ tbl[0][tbl[j - 1][i] & 0xff]
+ return tbl
+
+
+ def table_driven(self, in_data):
+ """
+ The Standard table_driven CRC algorithm.
+ """
+ # pylint: disable = line-too-long
+
+ # If the input data is a string, convert to bytes.
+ if isinstance(in_data, str):
+ in_data = bytearray(in_data, 'utf-8')
+
+ tbl = self.gen_table()
+
+ if not self.reflect_in:
+ reg = self.direct_init << self.crc_shift
+ for octet in in_data:
+ tblidx = ((reg >> (self.width - self.tbl_idx_width + self.crc_shift)) ^ octet) & 0xff
+ reg = ((reg << (self.tbl_idx_width - self.crc_shift)) ^ (tbl[0][tblidx] << self.crc_shift)) & (self.mask << self.crc_shift)
+ reg = reg >> self.crc_shift
+ else:
+ reg = self.reflect(self.direct_init, self.width)
+ for octet in in_data:
+ tblidx = (reg ^ octet) & 0xff
+ reg = ((reg >> self.tbl_idx_width) ^ tbl[0][tblidx]) & self.mask
+ reg = self.reflect(reg, self.width) & self.mask
+
+ if self.reflect_out:
+ reg = self.reflect(reg, self.width)
+ return reg ^ self.xor_out
+