From caaf4a5d66d519cd3bfe2eb42d65a94aed61a676 Mon Sep 17 00:00:00 2001
From: Jacob Lifshay <programmerjake@gmail.com>
Date: Tue, 14 May 2024 21:04:49 -0700
Subject: [PATCH] add HDL implementation of decode_reducing_polynomial

---
 .../hdl/decode_reducing_polynomial.py         | 51 ++++++++++++++
 .../test/test_decode_reducing_polynomial.py   | 68 +++++++++++++++++++
 2 files changed, 119 insertions(+)
 create mode 100644 src/nmigen_gf/hdl/decode_reducing_polynomial.py
 create mode 100644 src/nmigen_gf/hdl/test/test_decode_reducing_polynomial.py

diff --git a/src/nmigen_gf/hdl/decode_reducing_polynomial.py b/src/nmigen_gf/hdl/decode_reducing_polynomial.py
new file mode 100644
index 0000000..f50dee8
--- /dev/null
+++ b/src/nmigen_gf/hdl/decode_reducing_polynomial.py
@@ -0,0 +1,51 @@
+# 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
+
+
+class DecodeReducingPolynomial(Elaboratable):
+    """Decode the reducing polynomial from the REDPOLY SPR
+
+    Properties:
+    XLEN: int
+    REDPOLY: Signal of width XLEN
+        input from the REDPOLY SPR
+    reducing_polynomial: Signal of width XLEN + 1
+        decoded reducing polynomial output
+    """
+
+    def __init__(self, XLEN):
+        # type: (int) -> None
+        self.XLEN = XLEN
+        self.REDPOLY = Signal(XLEN)
+        self.reducing_polynomial = Signal(XLEN + 1)
+
+    def elaborate(self, platform):
+        m = Module()
+        v = self.REDPOLY
+        with m.If((v == 0) | (v == 0b10)):  # GF(2)
+            # degree = 1, poly = x
+            m.d.comb += self.reducing_polynomial.eq(0b10)
+        with m.Elif(v[0] == 0):
+            # all reducing polynomials of degree > 1 must have the LSB set,
+            # because they must be irreducible polynomials (meaning they
+            # can't be factored), if the LSB was clear, then they would
+            # have `x` as a factor. Therefore, we can reuse the LSB clear
+            # to instead mean the polynomial has degree XLEN.
+            m.d.comb += self.reducing_polynomial.eq(v)
+            m.d.comb += self.reducing_polynomial[self.XLEN].eq(1)
+            m.d.comb += self.reducing_polynomial[0].eq(1)  # LSB must be set
+        with m.Else():
+            m.d.comb += self.reducing_polynomial.eq(v)
+        return m
diff --git a/src/nmigen_gf/hdl/test/test_decode_reducing_polynomial.py b/src/nmigen_gf/hdl/test/test_decode_reducing_polynomial.py
new file mode 100644
index 0000000..47f4ce2
--- /dev/null
+++ b/src/nmigen_gf/hdl/test/test_decode_reducing_polynomial.py
@@ -0,0 +1,68 @@
+# 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.decode_reducing_polynomial import \
+    decode_reducing_polynomial
+from nmigen_gf.hdl.decode_reducing_polynomial import DecodeReducingPolynomial
+from nmigen.sim import Delay
+from nmutil.sim_util import do_sim, hash_256
+from nmigen_gf.reference.state import ST
+
+
+class TestDecodeReducingPolynomial(FHDLTestCase):
+    def tst(self, XLEN):
+        # type: (int) -> None
+        dut = DecodeReducingPolynomial(XLEN)
+        self.assertEqual(dut.XLEN, XLEN)
+        self.assertEqual(dut.REDPOLY.width, XLEN)
+        self.assertEqual(dut.reducing_polynomial.width, XLEN + 1)
+
+        def case(REDPOLY):
+            ST.reinit(XLEN=XLEN, GFBREDPOLY=REDPOLY)
+            expected = decode_reducing_polynomial()
+            with self.subTest(XLEN=XLEN,
+                              REDPOLY=hex(REDPOLY),
+                              expected=hex(expected)):
+                yield dut.REDPOLY.eq(REDPOLY)
+                yield Delay(1e-6)
+                reducing_polynomial = yield dut.reducing_polynomial
+                with self.subTest(output=hex(reducing_polynomial)):
+                    self.assertEqual(expected, reducing_polynomial)
+
+        def process():
+            for i in range(100):
+                v = hash_256("dec_rpoly XLEN %i %i REDPOLY" % (XLEN, i))
+                shift = hash_256("dec_rpoly XLEN %i %i shift" % (XLEN, i))
+                v >>= shift % XLEN
+                REDPOLY = Const.normalize(v, unsigned(XLEN))
+                yield from case(REDPOLY)
+        with do_sim(self, dut, [dut.REDPOLY, dut.reducing_polynomial]) as sim:
+            sim.add_process(process)
+            sim.run()
+
+    def test_8(self):
+        self.tst(8)
+
+    def test_16(self):
+        self.tst(16)
+
+    def test_32(self):
+        self.tst(32)
+
+    def test_64(self):
+        self.tst(64)
+
+
+if __name__ == "__main__":
+    unittest.main()
-- 
2.30.2