lib/common/algorithms.py

#  pycrc -- parameterisable CRC calculation utility and C source code generator
#
#  Copyright (c) 2006-2017  Thomas Pircher  <[email protected]>
#
#  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 is not 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