From fe465a179c0556e16899be0f0fa8dcb123087ac7 Mon Sep 17 00:00:00 2001 From: Michael Buesch Date: Wed, 14 Aug 2019 20:09:59 +0200 Subject: Update crcgen Signed-off-by: Michael Buesch --- .gitmodules | 3 + maintenance/makerelease.sh | 3 + phy_fpga/.gitignore | 1 + phy_fpga/Makefile | 13 +- phy_fpga/crcgen | 1 + phy_fpga/crcgen.py | 584 --------------------------------------------- phy_fpga/crcgen_test.py | 256 -------------------- 7 files changed, 18 insertions(+), 843 deletions(-) create mode 100644 .gitmodules create mode 160000 phy_fpga/crcgen delete mode 100755 phy_fpga/crcgen.py delete mode 100755 phy_fpga/crcgen_test.py diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..79b5f8b --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "phy_fpga/crcgen"] + path = phy_fpga/crcgen + url = https://git.bues.ch/git/crcgen.git diff --git a/maintenance/makerelease.sh b/maintenance/makerelease.sh index 19e1b23..cff50f0 100755 --- a/maintenance/makerelease.sh +++ b/maintenance/makerelease.sh @@ -25,6 +25,9 @@ hook_get_version() hook_post_checkout() { + info "Pulling in git submodules" + git submodule update --init + default_hook_post_checkout "$@" rm -r "$1"/maintenance diff --git a/phy_fpga/.gitignore b/phy_fpga/.gitignore index 06d03fc..e390565 100644 --- a/phy_fpga/.gitignore +++ b/phy_fpga/.gitignore @@ -4,5 +4,6 @@ *.bin *.rpt *.log +*.stamp crc8_func.v pll_mod.v diff --git a/phy_fpga/Makefile b/phy_fpga/Makefile index 4ec5fc7..e468279 100644 --- a/phy_fpga/Makefile +++ b/phy_fpga/Makefile @@ -17,6 +17,9 @@ PRINTF := printf RM := rm FALSE := false TR := tr +TEST := test +TOUCH := touch +GIT := git TARGET_LOWER := $(shell $(PRINTF) '%s' '$(TARGET)' | $(TR) A-Z a-z) TARGET_UPPER := $(shell $(PRINTF) '%s' '$(TARGET)' | $(TR) a-z A-Z) @@ -59,8 +62,12 @@ PLL_HZ := 16000000 PLL_MOD_V := endif -crc8_func.v: crcgen.py - $(PYTHON) crcgen.py --algorithm CRC-8-CCITT --verilog-function --name crc8 > $@ +crcgen.stamp: + $(TEST) -d ./crcgen || $(GIT) submodule update --init + $(TOUCH) $@ + +crc8_func.v: crcgen.stamp + PYTHONPATH=./crcgen $(PYTHON) ./crcgen/crcgen --algorithm CRC-8-CCITT --verilog-function --name crc8 > $@ %.blif: $(TOP_FILE) $(wildcard *.v) $(GENERATED_V) $(PLL_MOD_V) $(YOSYS) -p 'read_verilog -DTARGET_$(TARGET_UPPER)=1 -DCLK_HZ=$(CLK_HZ) -DPLL_HZ=$(PLL_HZ) $(if $(filter-out 0,$(DEBUG)),-DDEBUG=1) $<' \ @@ -92,7 +99,7 @@ boot: $(TINYPROG) -b clean: - $(RM) -f *.blif *.json *.asc *.bin *.rpt $(YOSYS_LOG) $(NEXTPNR_LOG) $(ICEPACK_LOG) $(ICETIME_LOG) $(GENERATED_V) $(PLL_MOD_V_FILE) + $(RM) -f *.blif *.json *.asc *.bin *.rpt crcgen.stamp $(YOSYS_LOG) $(NEXTPNR_LOG) $(ICEPACK_LOG) $(ICETIME_LOG) $(GENERATED_V) $(PLL_MOD_V_FILE) .PHONY: all install boot clean .PRECIOUS: %.json %.blif %.asc diff --git a/phy_fpga/crcgen b/phy_fpga/crcgen new file mode 160000 index 0000000..1e81181 --- /dev/null +++ b/phy_fpga/crcgen @@ -0,0 +1 @@ +Subproject commit 1e8118161a52c7681f3887f38a54ab612d946b90 diff --git a/phy_fpga/crcgen.py b/phy_fpga/crcgen.py deleted file mode 100755 index 70d629e..0000000 --- a/phy_fpga/crcgen.py +++ /dev/null @@ -1,584 +0,0 @@ -#!/usr/bin/env python3 -# vim: ts=8 sw=8 noexpandtab -# -# CRC code generator -# -# Copyright (c) 2019 Michael Buesch -# -# This program is free software; you can redistribute it and/or modify -# it under the terms of the GNU General Public License as published by -# the Free Software Foundation; either version 2 of the License, or -# (at your option) any later version. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License along -# with this program; if not, write to the Free Software Foundation, Inc., -# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. -# - -from dataclasses import dataclass -import argparse -import sys - - -__all__ = [ - "CrcGen", -] - - -CRC_PARAMETERS = { - "CRC-32" : { - "polynomial" : 0xEDB88320, - "nrBits" : 32, - "shiftRight" : True, - }, - "CRC-16" : { - "polynomial" : 0xA001, - "nrBits" : 16, - "shiftRight" : True, - }, - "CRC-16-CCITT" : { - "polynomial" : 0x1021, - "nrBits" : 16, - "shiftRight" : False, - }, - "CRC-8-CCITT" : { - "polynomial" : 0x07, - "nrBits" : 8, - "shiftRight" : False, - }, - "CRC-8-IBUTTON" : { - "polynomial" : 0x8C, - "nrBits" : 8, - "shiftRight" : True, - }, -} - - -class CrcReference(object): - """Generic CRC reference implementation. - """ - - @classmethod - def crc(cls, crc, data, polynomial, nrBits, shiftRight): - mask = (1 << nrBits) - 1 - msb = 1 << (nrBits - 1) - lsb = 1 - if shiftRight: - tmp = (crc ^ data) & 0xFF - for i in range(8): - if tmp & lsb: - tmp = ((tmp >> 1) ^ polynomial) & mask - else: - tmp = (tmp >> 1) & mask - crc = ((crc >> 8) ^ tmp) & mask - else: - tmp = (crc ^ (data << (nrBits - 8))) & mask - for i in range(8): - if tmp & msb: - tmp = ((tmp << 1) ^ polynomial) & mask - else: - tmp = (tmp << 1) & mask - crc = tmp - return crc - - @classmethod - def crcBlock(cls, crc, data, polynomial, nrBits, shiftRight, preFlip, postFlip): - mask = (1 << nrBits) - 1 - if preFlip: - crc ^= mask - for b in data: - crc = cls.crc(crc, b, polynomial, nrBits, shiftRight) - if postFlip: - crc ^= mask - return crc - -@dataclass -class AbstractBit(object): - def flatten(self): - return self - - def optimize(self): - pass - -@dataclass -class Bit(AbstractBit): - name: str - index: int - - def gen_python(self): - return "%s[%d]" % (self.name, self.index) - - def gen_c(self): - if self.index: - return "((%s >> %du) & 1u)" % (self.name, self.index) - return "(%s & 1u)" % (self.name) - - def gen_verilog(self): - return "%s[%d]" % (self.name, self.index) - -@dataclass -class ConstBit(AbstractBit): - value: int - - def gen_python(self): - return "1" if self.value else "0" - - def gen_c(self): - return "1u" if self.value else "0u" - - def gen_verilog(self): - return "1'b1" if self.value else "1'b0" - -class XOR(object): - def __init__(self, *items): - self.items = items - - def flatten(self): - newItems = [] - for item in self.items: - if isinstance(item, XOR): - newItems.extend(item.flatten().items) - else: - newItems.append(item) - self.items = newItems - return self - - def optimize(self): - newItems = [] - for item in self.items: - if isinstance(item, ConstBit): - if item.value == 0: - # Constant 0 does not change the XOR result. - # Remove it. - pass - else: - # Keep it. - newItems.append(item) - elif isinstance(item, Bit): - if item in newItems: - # We already have this bit. - # Remove it. - pass - else: - if sum(1 if (isinstance(i, Bit) and i == item) else 0 - for i in self.items) % 2: - # We have an uneven count of this bit. - # Keep it once. - newItems.append(item) - else: - # An even amount cancels out in XOR. - # Remove it. - pass - else: - # This is something else. - # Keep it. - newItems.append(item) - if not newItems: - # All items have been optimized out. - # This term shall be zero. - newItems.append(ConstBit(0)) - self.items = newItems - - def gen_python(self): - assert(self.items) - return "(%s)" % (" ^ ".join(item.gen_python() for item in self.items)) - - def gen_c(self): - assert(self.items) - return "(%s)" % (" ^ ".join(item.gen_c() for item in self.items)) - - def gen_verilog(self): - assert(self.items) - return "(%s)" % (" ^ ".join(item.gen_verilog() for item in self.items)) - -class Word(object): - def __init__(self, *items, MSBFirst=True): - if MSBFirst: - # Reverse items, so that it's always LSB-first. - items = reversed(items) - self.items = list(items) - - def __getitem__(self, index): - return self.items[index] - - def flatten(self): - self.items = [ item.flatten() for item in self.items ] - - def optimize(self): - for item in self.items: - item.optimize() - -class CrcGenError(Exception): - pass - -class CrcGen(object): - """Combinatorial CRC algorithm generator. - """ - - OPT_FLATTEN = 1 << 0 - OPT_ELIMINATE = 1 << 1 - - OPT_NONE = 0 - OPT_ALL = OPT_FLATTEN | OPT_ELIMINATE - - def __init__(self, - P, - nrBits, - shiftRight=False, - optimize=OPT_ALL): - self.__P = P - self.__nrBits = nrBits - self.__shiftRight = shiftRight - self.__optimize = optimize - - def __gen(self, dataVarName, crcVarName): - nrBits = self.__nrBits - assert nrBits in (8, 16, 32), "Invalid nrBits" - - # Construct the function input data word. - inData = Word(*( - Bit(dataVarName, i) - for i in reversed(range(8)) - )) - - # Construct the function input CRC word. - inCrc = Word(*( - Bit(crcVarName, i) - for i in reversed(range(nrBits)) - )) - - # Construct the base word. - # This is the start word for the bit shifting loop below. - if self.__shiftRight: - base = Word(*( - XOR(inData[i], inCrc[i]) if i <= 7 else ConstBit(0) - for i in reversed(range(nrBits)) - )) - else: - base = Word(*( - XOR(inData[i - (nrBits - 8)] if i >= nrBits - 8 else ConstBit(0), - inCrc[i]) - for i in reversed(range(nrBits)) - )) - - # Helper function to XOR a polynomial bit with the data bit 'dataBit', - # if the decision bit 'queryBit' is set. - # This is done reversed, because the polynomial is constant. - def xor_P(dataBit, queryBit, bitNr): - if (self.__P >> bitNr) & 1: - return XOR(dataBit, queryBit) - return dataBit - - # Run the main shift loop. - prevWord = base - for _ in range(8): - if self.__shiftRight: - # Shift to the right: i + 1 - word = Word(*( - xor_P(prevWord[i + 1] if i < nrBits - 1 else ConstBit(0), - prevWord[0], - i) - for i in reversed(range(nrBits)) - )) - else: - # Shift to the left: i - 1 - word = Word(*( - xor_P(prevWord[i - 1] if i > 0 else ConstBit(0), - prevWord[nrBits - 1], - i) - for i in reversed(range(nrBits)) - )) - prevWord = word - - # Construct the function output CRC word. - if self.__shiftRight: - outCrc = Word(*( - XOR(inCrc[i + 8] if i < nrBits - 8 else ConstBit(0), - word[i]) - for i in reversed(range(nrBits)) - )) - else: - outCrc = word - - # Optimize the algorithm. This removes unnecessary operations. - if self.__optimize & self.OPT_FLATTEN: - outCrc.flatten() - if self.__optimize & self.OPT_ELIMINATE: - outCrc.optimize() - - return outCrc - - def __header(self): - return """\ -THIS IS GENERATED CODE. - -This code is Public Domain. -Permission to use, copy, modify, and/or distribute this software for any -purpose with or without fee is hereby granted. - -THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES -WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF -MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY -SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER -RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, -NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE -USE OR PERFORMANCE OF THIS SOFTWARE.""" - - def __algDescription(self): - return ("CRC polynomial = 0x%X (hex)\n" - "CRC width = %d bits\n" - "CRC shift direction = %s\n" % ( - self.__P, - self.__nrBits, - "right" if self.__shiftRight else "left", - )) - - def genPython(self, - funcName="crc", - crcVarName="crc", - dataVarName="data"): - word = self.__gen(dataVarName, crcVarName) - ret = [] - ret.append("# vim: ts=8 sw=8 noexpandtab") - ret.append("") - ret.extend("# " + l for l in self.__header().splitlines()) - ret.append("") - ret.extend("# " + l for l in self.__algDescription().splitlines()) - ret.append("") - ret.append("def %s(%s, %s):" % (funcName, crcVarName, dataVarName)) - ret.append("\tclass bitwrapper:") - ret.append("\t\tdef __init__(self, value):") - ret.append("\t\t\tself.value = value") - ret.append("\t\tdef __getitem__(self, index):") - ret.append("\t\t\treturn ((self.value >> index) & 1)") - ret.append("\t\tdef __setitem__(self, index, value):") - ret.append("\t\t\tif value:") - ret.append("\t\t\t\tself.value |= 1 << index") - ret.append("\t\t\telse:") - ret.append("\t\t\t\tself.value &= ~(1 << index)") - ret.append("\t%s = bitwrapper(%s)" % (crcVarName, crcVarName)) - ret.append("\t%s = bitwrapper(%s)" % (dataVarName, dataVarName)) - ret.append("\tret = bitwrapper(0)") - for i, bit in enumerate(word): - ret.append("\tret[%d] = %s" % (i, bit.gen_python())) - ret.append("\treturn ret.value") - return "\n".join(ret) - - def genVerilog(self, - genFunction=True, - name="crc", - inDataName="inData", - inCrcName="inCrc", - outCrcName="outCrc"): - word = self.__gen(inDataName, inCrcName) - ret = [] - ret.append("// vim: ts=4 sw=4 noexpandtab") - ret.append("") - ret.extend("// " + l for l in self.__header().splitlines()) - ret.append("") - if not genFunction: - ret.append("`ifndef %s_V_" % name.upper()) - ret.append("`define %s_V_" % name.upper()) - ret.append("") - ret.extend("// " + l for l in self.__algDescription().splitlines()) - ret.append("") - if genFunction: - ret.append("function automatic [%d:0] %s;" % (self.__nrBits - 1, name)) - else: - ret.append("module %s (" % name) - ret.append("\tinput [%d:0] %s%s" % (self.__nrBits - 1, inCrcName, - ";" if genFunction else ",")) - ret.append("\tinput [7:0] %s%s" % (inDataName, - ";" if genFunction else ",")) - if genFunction: - ret.append("begin") - else: - ret.append("\toutput [%d:0] %s," % (self.__nrBits - 1, outCrcName)) - ret.append(");") - for i, bit in enumerate(word): - ret.append("\t%s%s[%d] = %s;" % ("" if genFunction else "assign ", - name if genFunction else outCrcName, - i, bit.gen_verilog())) - if genFunction: - ret.append("end") - ret.append("endfunction") - else: - ret.append("endmodule") - ret.append("") - ret.append("`endif // %s_V_" % name.upper()) - return "\n".join(ret) - - def genC(self, - funcName="crc", - crcVarName="crc", - dataVarName="data", - static=False, - inline=False): - word = self.__gen(dataVarName, crcVarName) - cType = "uint%s_t" % self.__nrBits - ret = [] - ret.append("// vim: ts=4 sw=4 noexpandtab") - ret.append("") - ret.extend("// " + l for l in self.__header().splitlines()) - ret.append("") - ret.append("#ifndef %s_H_" % funcName.upper()) - ret.append("#define %s_H_" % funcName.upper()) - ret.append("") - ret.append("#include ") - ret.append("") - ret.extend("// " + l for l in self.__algDescription().splitlines()) - ret.append("") - ret.append("%s%s%s %s(%s %s, uint8_t %s)" % ("static " if static else "", - "inline " if inline else "", - cType, - funcName, - cType, - crcVarName, - dataVarName)) - ret.append("{") - ret.append("\t%s ret;" % cType) - for i, bit in enumerate(word): - if i: - operator = "|=" - shift = " << %du" % i - else: - operator = "=" - shift = "" - ret.append("\tret %s (%s)%s;" % (operator, bit.gen_c(), shift)) - ret.append("\treturn ret;") - ret.append("}") - ret.append("") - ret.append("#endif /* %s_H_ */" % funcName.upper()) - return "\n".join(ret) - - def runTests(self, name=None, extra=None): - import random - - rng = random.Random() - rng.seed(424242) - - print("Testing%s P=0x%X, nrBits=%d, shiftRight=%d %s..." % ( - (" " + name) if name else "", - self.__P, - self.__nrBits, - int(bool(self.__shiftRight)), - (extra + " ") if extra else "")) - - # Generate the CRC function as Python code. - pyCode = self.genPython(funcName="crc_func") - execEnv = {} - exec(pyCode, execEnv) - crc_func = execEnv["crc_func"] - - mask = (1 << self.__nrBits) - 1 - for i in range(0xFF + 1): - if i == 0: - crc = 0 - elif i == 1: - crc = mask - else: - crc = rng.randint(1, mask - 1) - for data in range(0xFF + 1): - a = CrcReference.crc( - crc=crc, - data=data, - polynomial=self.__P, - nrBits=self.__nrBits, - shiftRight=self.__shiftRight) - b = crc_func(crc, data) - if a != b: - raise CrcGenError("Test failed. " - "(P=0x%X, nrBits=%d, shiftRight=%d, " - "a=0x%X, b=0x%X)" % ( - self.__P, self.__nrBits, - int(bool(self.__shiftRight)), - a, b)) - -if __name__ == "__main__": - try: - def argInt(string): - if string.startswith("0x"): - return int(string[2:], 16) - return int(string) - p = argparse.ArgumentParser() - g = p.add_mutually_exclusive_group(required=True) - g.add_argument("-p", "--python", action="store_true", help="Generate Python code") - g.add_argument("-v", "--verilog-function", action="store_true", help="Generate Verilog function") - g.add_argument("-m", "--verilog-module", action="store_true", help="Generate Verilog module") - g.add_argument("-c", "--c", action="store_true", help="Generate C code") - g.add_argument("-t", "--test", action="store_true", help="Run unit tests for the specified algorithm") - p.add_argument("-a", "--algorithm", type=str, - choices=CRC_PARAMETERS.keys(), default="CRC-8-CCITT", - help="Select the CRC algorithm. " - "Individual algorithm parameters (e.g. polynomial) can be overridden with the options below.") - p.add_argument("-P", "--polynomial", type=argInt, help="CRC polynomial") - p.add_argument("-B", "--nr-bits", type=argInt, choices=[8, 16, 32], help="Number of bits") - g = p.add_mutually_exclusive_group() - g.add_argument("-R", "--shift-right", action="store_true", help="CRC algorithm shift direction: right shift") - g.add_argument("-L", "--shift-left", action="store_true", help="CRC algorithm shift direction: left shift") - p.add_argument("-n", "--name", type=str, default="crc", help="Generated function/module name") - p.add_argument("-D", "--data-param", type=str, default="data", help="Generated function/module data parameter name") - p.add_argument("-C", "--crc-in-param", type=str, default="crcIn", help="Generated function/module crc input parameter name") - p.add_argument("-o", "--crc-out-param", type=str, default="crcOut", help="Generated module crc output parameter name") - p.add_argument("-S", "--static", action="store_true", help="Generate static C function") - p.add_argument("-I", "--inline", action="store_true", help="Generate inline C function") - p.add_argument("-O", "--optimize", type=argInt, default=CrcGen.OPT_ALL, help="Enable algorithm optimizer steps") - args = p.parse_args() - - crcParameters = CRC_PARAMETERS[args.algorithm].copy() - if args.polynomial is not None: - crcParameters["polynomial"] = args.polynomial - if args.nr_bits is not None: - crcParameters["nrBits"] = args.nr_bits - if args.shift_right: - crcParameters["shiftRight"] = True - if args.shift_left: - crcParameters["shiftRight"] = False - - polynomial = crcParameters["polynomial"] - nrBits = crcParameters["nrBits"] - shiftRight = crcParameters["shiftRight"] - - if polynomial > ((1 << nrBits) - 1): - raise CrcGenError("Invalid polynomial. " - "It is bigger than the CRC width " - "of (2**%d)-1." % nrBits) - - gen = CrcGen(P=polynomial, - nrBits=nrBits, - shiftRight=shiftRight, - optimize=args.optimize) - if args.test: - gen.runTests() - else: - if args.python: - print(gen.genPython(funcName=args.name, - crcVarName=args.crc_in_param, - dataVarName=args.data_param)) - elif args.verilog_function: - print(gen.genVerilog(genFunction=True, - name=args.name, - inDataName=args.data_param, - inCrcName=args.crc_in_param, - outCrcName=args.crc_out_param)) - elif args.verilog_module: - print(gen.genVerilog(genFunction=False, - name=args.name, - inDataName=args.data_param, - inCrcName=args.crc_in_param, - outCrcName=args.crc_out_param)) - elif args.c: - print(gen.genC(funcName=args.name, - crcVarName=args.crc_in_param, - dataVarName=args.data_param, - static=args.static, - inline=args.inline)) - sys.exit(0) - except CrcGenError as e: - print("ERROR: %s" % str(e), file=sys.stderr) - sys.exit(1) diff --git a/phy_fpga/crcgen_test.py b/phy_fpga/crcgen_test.py deleted file mode 100755 index 3009ad5..0000000 --- a/phy_fpga/crcgen_test.py +++ /dev/null @@ -1,256 +0,0 @@ -#!/usr/bin/env python3 -# -# Test of CRC generator. -# -# Copyright (C) 2019 Michael Buesch -# -# Some CRC implementations are derived from AVR-libc. -# These copyright notices apply to the AVR-libc parts: -# -# Copyright (c) 2002, 2003, 2004 Marek Michalkiewicz -# Copyright (c) 2005, 2007 Joerg Wunsch -# Copyright (c) 2013 Dave Hylands -# Copyright (c) 2013 Frederic Nadeau -# All rights reserved. -# -# -# Redistribution and use in source and binary forms, with or without -# modification, are permitted provided that the following conditions are met: -# -# * Redistributions of source code must retain the above copyright -# notice, this list of conditions and the following disclaimer. -# -# * Redistributions in binary form must reproduce the above copyright -# notice, this list of conditions and the following disclaimer in -# the documentation and/or other materials provided with the -# distribution. -# -# * Neither the name of the copyright holders nor the names of -# contributors may be used to endorse or promote products derived -# from this software without specific prior written permission. -# -# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" -# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE -# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR -# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF -# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS -# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN -# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) -# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE -# POSSIBILITY OF SUCH DAMAGE. -# - -from crcgen import CrcReference, CrcGen, CRC_PARAMETERS -import random -import multiprocessing - - -# Derived from CRC-32 version 2.0.0 by Craig Bruce, 2006-04-29. (Public Domain): -def crc32(crc, data): - crcTable = ( - 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F, 0xE963A535, - 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD, - 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148, 0x84BE41DE, 0x1ADAD47D, - 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7, 0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, - 0x14015C4F, 0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, - 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C, - 0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC, - 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423, 0xCFBA9599, 0xB8BDA50F, - 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, - 0xB6662D3D, 0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, - 0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, - 0x086D3D2D, 0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E, - 0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950, 0x8BBEB8EA, - 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65, 0x4DB26158, 0x3AB551CE, - 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, - 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, - 0x5005713C, 0x270241AA, 0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, - 0xCE61E49F, 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81, - 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, - 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E, 0x7A6A5AA8, - 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1, 0xF00F9344, 0x8708A3D2, 0x1E01F268, - 0x6906C2FE, 0xF762575D, 0x806567CB, 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, - 0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, - 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, - 0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55, 0x316E8EEF, - 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236, 0xCC0C7795, 0xBB0B4703, - 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, - 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, - 0x9C0906A9, 0xEB0E363F, 0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, - 0x0CB61B38, 0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242, - 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777, 0x88085AE6, - 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45, - 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661, 0xD06016F7, 0x4969474D, - 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC, 0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, - 0x47B2CF7F, 0x30B5FFE9, 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, - 0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94, - 0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D, - ) - return (crc >> 8) ^ crcTable[(crc ^ data) & 0xFF] - -# Derived from AVR-libc: -def crc16(crc, data): - crc ^= data - for i in range(8): - if crc & 1: - crc = (crc >> 1) ^ 0xA001 - else: - crc = (crc >> 1) - return crc - -# Derived from AVR-libc: -def crc16_ccitt(crc, data): - data ^= crc & 0xFF - data = (data ^ (data << 4)) & 0xFF - return ((((data << 8) & 0xFFFF) | (crc >> 8)) ^ - (data >> 4) ^ - ((data << 3) & 0xFFFF)) - -def crc16_ccitt_reversed(crc, data): - return bitreverse(crc16_ccitt(bitreverse(crc, 16), - bitreverse(data, 8)), - 16) - -# Derived from AVR-libc: -def crc16_xmodem(crc, data): - crc ^= (data << 8) - for i in range(8): - if crc & 0x8000: - crc = ((crc << 1) ^ 0x1021) & 0xFFFF - else: - crc = (crc << 1) & 0xFFFF - return crc - -# Derived from AVR-libc: -def crc8_ibutton(crc, data): - crc ^= data - for i in range(8): - if crc & 1: - crc = (crc >> 1) ^ 0x8C - else: - crc = (crc >> 1) - return crc - -# Derived from AVR-libc: -def crc8_ccitt(crc, data): - crc ^= data - for i in range(8): - if crc & 0x80: - crc = ((crc << 1) ^ 0x07) & 0xFF - else: - crc = (crc << 1) & 0xFF - return crc - -def crcRange(nrBits): - rng = random.Random() - rng.seed(42) - mask = (1 << nrBits) - 1 - for i in range(0x300): - if i == 0: - crc = 0 - elif i == 1: - crc = mask - else: - crc = rng.randint(1, mask - 1) - yield crc - -def dataRange(): - yield from (0x00, 0xAA, 0x55, 0xFF, - 0x3E, 0x92, 0x0A, 0x7D, 0x4E, 0x07, 0x23, 0xDD, - 0x4C, 0xE4, 0x1E, 0x8B, 0x5C, 0xD8, 0x1F, 0x74) - -def bitreverse(value, nrBits): - ret = 0 - for _ in range(nrBits): - ret = (ret << 1) | (value & 1) - value >>= 1 - return ret - -def compareReferenceImpl(name, crcFunc): - print("Testing %s..." % name) - crcParameters = CRC_PARAMETERS[name] - for crc in crcRange(crcParameters["nrBits"]): - for data in dataRange(): - a = crcFunc(crc, data) - b = CrcReference.crc(crc, data, - crcParameters["polynomial"], - crcParameters["nrBits"], - crcParameters["shiftRight"]) - if a != b: - raise Exception("%s test FAILED!" % name) - -def checkReferenceReversed(nrBits, polynomial): - print("Testing CrcReference reversed (nrBits=%d, P=%X)..." % ( - nrBits, polynomial)) - for shiftRight in (True, False): - for crc in crcRange(nrBits): - for data in dataRange(): - a = CrcReference.crc( - crc, - data, - polynomial, - nrBits, - shiftRight) - b = bitreverse(CrcReference.crc( - bitreverse(crc, nrBits), - bitreverse(data, 8), - bitreverse(polynomial, nrBits), - nrBits, - not shiftRight), - nrBits) - if a != b: - raise Exception("CrcReference reversed test " - "FAILED! (nrBits=%d, P=%X)" % ( - nrBits, polynomial)) - -def compareGeneratedImpl(optimize, alg, crcParameters): - polynomial = crcParameters["polynomial"] - nrBits = crcParameters["nrBits"] - shiftRight = crcParameters["shiftRight"] - gen = CrcGen(P=polynomial, - nrBits=nrBits, - shiftRight=shiftRight, - optimize=optimize) - gen.runTests(name=alg, - extra=("-O=%d" % optimize)) - -if __name__ == "__main__": - assert bitreverse(0xE0, 8) == 0x07 - assert bitreverse(0x8408, 16) == 0x1021 - assert bitreverse(0xEDB88320, 32) == 0x04C11DB7 - - print("*** Comparing reference implementation to itself reversed ***") - params = ( - (32, 0xEDB88320), - (16, 0xA001), - (16, 0x1021), - (8, 0x07), - (8, 0x8C), - ) - with multiprocessing.Pool() as p: - p.starmap(checkReferenceReversed, params) - - print("*** Comparing reference implementation to discrete implementations ***") - params = ( - ("CRC-32", crc32), - ("CRC-16", crc16), - ("CRC-16-CCITT", crc16_ccitt_reversed), - ("CRC-16-CCITT", crc16_xmodem), - ("CRC-8-CCITT", crc8_ccitt), - ("CRC-8-IBUTTON", crc8_ibutton), - ) - with multiprocessing.Pool() as p: - p.starmap(compareReferenceImpl, params) - - print("*** Comparing generated CRC functions to reference implementation ***") - def makeParams(): - for optimize in (CrcGen.OPT_ALL, - CrcGen.OPT_FLATTEN, - CrcGen.OPT_ELIMINATE, - CrcGen.OPT_NONE): - for alg, crcParameters in CRC_PARAMETERS.items(): - yield optimize, alg, crcParameters - with multiprocessing.Pool() as p: - p.starmap(compareGeneratedImpl, tuple(makeParams())) -- cgit v1.2.3