From e80ef2e1770b2c81d3c5d8117100c38373de78f6 Mon Sep 17 00:00:00 2001 From: Jacob Lifshay Date: Tue, 14 May 2024 23:23:09 -0700 Subject: [PATCH] hdl/gfbmadd.py: add FSM-based reference python code --- src/nmigen_gf/hdl/gfbmadd.py | 160 +++++++++++++++++++++++++ src/nmigen_gf/hdl/test/test_gfbmadd.py | 69 +++++++++++ 2 files changed, 229 insertions(+) create mode 100644 src/nmigen_gf/hdl/gfbmadd.py create mode 100644 src/nmigen_gf/hdl/test/test_gfbmadd.py diff --git a/src/nmigen_gf/hdl/gfbmadd.py b/src/nmigen_gf/hdl/gfbmadd.py new file mode 100644 index 0000000..7a29974 --- /dev/null +++ b/src/nmigen_gf/hdl/gfbmadd.py @@ -0,0 +1,160 @@ +# SPDX-License-Identifier: LGPL-3-or-later +# Copyright 2024 Jacob Lifshay programmerjake@gmail.com + +# Funded by NLnet Assure Programme 2021-02-052, https://nlnet.nl/assure part +# of Horizon 2020 EU Programme 957073. + +""" GF(2^n) + +https://bugs.libre-soc.org/show_bug.cgi?id=785 +""" + +from nmigen.hdl.ast import Signal +from nmigen.hdl.ir import Elaboratable +from nmigen.hdl.dsl import Module +from nmutil.plain_data import plain_data, fields +from nmigen_gf.reference.state import ST +from nmigen_gf.reference.decode_reducing_polynomial import \ + decode_reducing_polynomial +from nmutil.clz import clz, CLZ + + +@plain_data(frozen=True, unsafe_hash=True) +class GFBMAddShape: + __slots__ = "width", + + def __init__(self, width): + # type: (int) -> None + self.width = width + + @property + def mul_step_last(self): + return self.mul_step_end - 1 + + @property + def mul_step_end(self): + return self.width + + @property + def reduce_input_width(self): + return self.width * 2 + + @property + def reduce_step_count(self): + return self.reduce_input_width + + @property + def reduce_step_end(self): + return self.mul_step_end + self.reduce_step_count + + @property + def rpoly_width(self): + return self.width + 1 + + @property + def acc_width(self): + return self.width + self.reduce_input_width + + +@plain_data(frozen=True, unsafe_hash=True) +class PyGFBMAddState: + __slots__ = "shape", "rpoly", "factor1", "factor2", "term", "acc", "step" + + def __init__(self, shape, rpoly, factor1, factor2, term, acc, step): + # type: (GFBMAddShape, int, int, int, int, int, int) -> None + assert 0 <= rpoly < 2 ** shape.rpoly_width + assert 0 <= factor1 < 2 ** shape.width + assert 0 <= factor2 < 2 ** shape.width + assert 0 <= term < 2 ** shape.width + assert 0 <= acc < 2 ** shape.acc_width + self.shape = shape + self.rpoly = rpoly + self.factor1 = factor1 + self.factor2 = factor2 + self.term = term + self.acc = acc + self.step = step + + @property + def sh_rpoly(self): + return self.rpoly << (self.shape.reduce_input_width - 1) + + @property + def sh_rpoly_clz(self): + return clz(self.sh_rpoly, self.shape.acc_width) + + @property + def next_state(self): + # type: () -> PyGFBMAddState + factor1 = self.factor1 + acc = self.acc + step = self.step + if self.step < self.shape.mul_step_end: + if factor1 & 1: + acc ^= self.factor2 << self.shape.width + acc >>= 1 + factor1 >>= 1 + if step == self.shape.mul_step_last: + acc ^= self.term + step += 1 + elif self.step < self.shape.reduce_step_end: + acc_clz = clz(acc, self.shape.acc_width) + if acc_clz == self.sh_rpoly_clz: + acc ^= self.sh_rpoly + acc <<= 1 + step += 1 + else: + return self + return PyGFBMAddState( + shape=self.shape, + rpoly=self.rpoly, + factor1=factor1, + factor2=self.factor2, + term=self.term, + acc=acc, + step=step, + ) + + @property + def output(self): + # type: () -> None | int + if self.step == self.shape.reduce_step_end: + return self.acc >> self.shape.reduce_input_width + else: + return None + + @staticmethod + def initial_state(width, rpoly, factor1, factor2, term): + # type: (int, int, int, int, int) -> PyGFBMAddState + assert 0 < width + assert 0 < rpoly < 2 ** (width + 1) + assert 0 <= factor1 < 2 ** width + assert 0 <= factor2 < 2 ** width + assert 0 <= term < 2 ** width + return PyGFBMAddState( + shape=GFBMAddShape(width), + rpoly=rpoly, + acc=0, + factor1=factor1, + factor2=factor2, + term=term, + step=0, + ) + + +def py_gfbmadd_algorithm(XLEN, REDPOLY, factor1, factor2, term): + # type: (int, int, int, int, int) -> int + ST.reinit(XLEN=XLEN, GFBREDPOLY=REDPOLY) + rpoly = decode_reducing_polynomial() + state = PyGFBMAddState.initial_state( + width=XLEN, + rpoly=rpoly, + factor1=factor1, + factor2=factor2, + term=term, + ) + while True: + output = state.output + if output is not None: + return output + state = state.next_state diff --git a/src/nmigen_gf/hdl/test/test_gfbmadd.py b/src/nmigen_gf/hdl/test/test_gfbmadd.py new file mode 100644 index 0000000..4aaa94f --- /dev/null +++ b/src/nmigen_gf/hdl/test/test_gfbmadd.py @@ -0,0 +1,69 @@ +# SPDX-License-Identifier: LGPL-3-or-later +# Copyright 2024 Jacob Lifshay programmerjake@gmail.com + +# Funded by NLnet Assure Programme 2021-02-052, https://nlnet.nl/assure part +# of Horizon 2020 EU Programme 957073. + +""" GF(2^n) + +https://bugs.libre-soc.org/show_bug.cgi?id=785 +""" + +import unittest +from nmigen.hdl.ast import Const, unsigned +from nmutil.formaltest import FHDLTestCase +from nmigen_gf.reference.gfbmadd import gfbmadd +from nmigen_gf.hdl.gfbmadd import py_gfbmadd_algorithm +from nmigen.sim import Delay +from nmutil.sim_util import do_sim, hash_256 +from nmigen_gf.reference.state import ST +import itertools + + +class TestPyGFBMAdd(FHDLTestCase): + def tst(self, XLEN, full): + # type: (int, bool) -> None + def case(REDPOLY, factor1, factor2, term): + # type: (int, int, int, int) -> None + ST.reinit(XLEN=XLEN, GFBREDPOLY=REDPOLY) + expected = gfbmadd(factor1, factor2, term) + output = py_gfbmadd_algorithm( + XLEN, REDPOLY, factor1, factor2, term) + with self.subTest(expected=hex(expected), + output=hex(output)): + self.assertEqual(expected, output) + if full: + itr = itertools.product(range(1 << XLEN), repeat=4) + for REDPOLY, factor1, factor2, term in itr: + with self.subTest(REDPOLY=hex(REDPOLY), + factor1=hex(factor1), + factor2=hex(factor2), + term=hex(term)): + case(REDPOLY, factor1, factor2, term) + else: + for i in range(100): + v = hash_256("py_gfbmadd %i REDPOLY %i" % (XLEN, i)) + shift = hash_256("py_gfbmadd %i REDPOLY shift %i" % (XLEN, i)) + v >>= shift % XLEN + REDPOLY = Const.normalize(v, unsigned(XLEN)) + v = hash_256("py_gfbmadd %i factor1 %i" % (XLEN, i)) + factor1 = Const.normalize(v, unsigned(XLEN)) + v = hash_256("py_gfbmadd %i factor2 %i" % (XLEN, i)) + factor2 = Const.normalize(v, unsigned(XLEN)) + v = hash_256("py_gfbmadd %i term %i" % (XLEN, i)) + term = Const.normalize(v, unsigned(XLEN)) + with self.subTest(REDPOLY=hex(REDPOLY), + factor1=hex(factor1), + factor2=hex(factor2), + term=hex(term)): + case(REDPOLY, factor1, factor2, term) + + def test_4(self): + self.tst(XLEN=4, full=True) + + def test_64(self): + self.tst(XLEN=64, full=False) + + +if __name__ == "__main__": + unittest.main() -- 2.30.2