aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMichael Buesch <m@bues.ch>2019-08-14 20:09:59 +0200
committerMichael Buesch <m@bues.ch>2019-08-14 20:11:20 +0200
commitfe465a179c0556e16899be0f0fa8dcb123087ac7 (patch)
tree4074044579c50efb3aaa87c41169e2de33a701a7
parent55fffec98468a51256f231a8bc6c704f3b770398 (diff)
downloadpyprofibus-fe465a179c0556e16899be0f0fa8dcb123087ac7.tar.xz
pyprofibus-fe465a179c0556e16899be0f0fa8dcb123087ac7.zip
Update crcgen
Signed-off-by: Michael Buesch <m@bues.ch>
-rw-r--r--.gitmodules3
-rwxr-xr-xmaintenance/makerelease.sh3
-rw-r--r--phy_fpga/.gitignore1
-rw-r--r--phy_fpga/Makefile13
m---------phy_fpga/crcgen0
-rwxr-xr-xphy_fpga/crcgen.py584
-rwxr-xr-xphy_fpga/crcgen_test.py256
7 files changed, 17 insertions, 843 deletions
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
+Subproject 1e8118161a52c7681f3887f38a54ab612d946b9
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 <m@bues.ch>
-#
-# 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 <stdint.h>")
- 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 <m@bues.ch>
-#
-# 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()))
bues.ch cgit interface