Merge remote-tracking branch 'origin/master'

diff --git a/.gitignore b/.gitignore
index b3354e88a167b49bb0f23fe3046b5aed6d155016..3be7dbcdaf8f5513428e646a58888855de83f3dd 100644 (file)
--- a/.gitignore
+++ b/.gitignore
@@ -1,6 +1,9 @@
 __pycache__
-WaveForms
+/Waveforms/**
+**/*/Waveforms
 *.vcd
 .*.sw?
 *.py?
 *.v
+.mypy_cache
+!**/Waveforms/.gitkeep

diff --git a/.gitmodules b/.gitmodules
new file mode 100644 (file)
index 0000000..35089b9
--- /dev/null
+++ b/.gitmodules
@@ -0,0 +1,4 @@
+[submodule "nmigen-type-annotations"]
+       path = nmigen-type-annotations
+       url = https://salsa.debian.org/Kazan-team/nmigen-type-annotations.git
+       branch = master

diff --git a/TLB/src/LFSR2.py b/TLB/src/LFSR2.py
new file mode 100644 (file)
index 0000000..8cdb2cc
--- /dev/null
+++ b/TLB/src/LFSR2.py
@@ -0,0 +1,123 @@
+# SPDX-License-Identifier: LGPL-2.1-or-later
+# See Notices.txt for copyright information
+from nmigen import Signal, Module, Elaboratable, Const
+from typing import Iterable, FrozenSet, Optional, Iterator, Any, Union
+from typing_extensions import final
+from collections.abc import Set, Hashable
+
+
+@final
+class LFSRPolynomial(Set):
+    def __init__(self, exponents: Iterable[int] = ()):
+        max_exponent = 0
+
+        def elements() -> Iterable[int]:
+            nonlocal max_exponent
+            yield 0  # 0 is always required
+            for exponent in exponents:
+                if not isinstance(exponent, int):
+                    raise TypeError()
+                if exponent < 0:
+                    raise ValueError()
+                if exponent > max_exponent:
+                    max_exponent = exponent
+                if exponent != 0:
+                    yield exponent
+        self.__exponents = frozenset(elements())
+        self.__max_exponent = max_exponent
+
+    @property
+    def exponents(self) -> FrozenSet[int]:
+        return self.__exponents
+
+    @property
+    def max_exponent(self) -> int:
+        return self.__max_exponent
+
+    def __hash__(self) -> int:
+        return hash(self.exponents)
+
+    def __contains__(self, x: Any) -> bool:
+        return x in self.exponents
+
+    def __len__(self) -> int:
+        return len(self.exponents)
+
+    def __iter__(self) -> Iterator[int]:
+        return iter(self.exponents)
+
+    def __str__(self) -> str:
+        exponents = list(self.exponents)
+        exponents.sort(reverse=True)
+        retval = ""
+        separator = ""
+        for i in exponents:
+            retval += separator
+            separator = " + "
+            if i == 0:
+                retval += "1"
+            elif i == 1:
+                retval += "x"
+            else:
+                retval += f"x^{i}"
+        return retval
+
+    def __repr__(self) -> str:
+        exponents = list(self.exponents)
+        exponents.sort(reverse=True)
+        return f"LFSRPolynomial({exponents!r})"
+
+
+# list of selected polynomials from https://web.archive.org/web/20190418121923/https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Some_polynomials_for_maximal_LFSRs  # noqa
+LFSR_POLY_2 = LFSRPolynomial([2, 1, 0])
+LFSR_POLY_3 = LFSRPolynomial([3, 2, 0])
+LFSR_POLY_4 = LFSRPolynomial([4, 3, 0])
+LFSR_POLY_5 = LFSRPolynomial([5, 3, 0])
+LFSR_POLY_6 = LFSRPolynomial([6, 5, 0])
+LFSR_POLY_7 = LFSRPolynomial([7, 6, 0])
+LFSR_POLY_8 = LFSRPolynomial([8, 6, 5, 4, 0])
+LFSR_POLY_9 = LFSRPolynomial([9, 5, 0])
+LFSR_POLY_10 = LFSRPolynomial([10, 7, 0])
+LFSR_POLY_11 = LFSRPolynomial([11, 9, 0])
+LFSR_POLY_12 = LFSRPolynomial([12, 11, 10, 4, 0])
+LFSR_POLY_13 = LFSRPolynomial([13, 12, 11, 8, 0])
+LFSR_POLY_14 = LFSRPolynomial([14, 13, 12, 2, 0])
+LFSR_POLY_15 = LFSRPolynomial([15, 14, 0])
+LFSR_POLY_16 = LFSRPolynomial([16, 15, 13, 4, 0])
+LFSR_POLY_17 = LFSRPolynomial([17, 14, 0])
+LFSR_POLY_18 = LFSRPolynomial([18, 11, 0])
+LFSR_POLY_19 = LFSRPolynomial([19, 18, 17, 14, 0])
+LFSR_POLY_20 = LFSRPolynomial([20, 17, 0])
+LFSR_POLY_21 = LFSRPolynomial([21, 19, 0])
+LFSR_POLY_22 = LFSRPolynomial([22, 21, 0])
+LFSR_POLY_23 = LFSRPolynomial([23, 18, 0])
+LFSR_POLY_24 = LFSRPolynomial([24, 23, 22, 17, 0])
+
+
+@final
+class LFSR(Elaboratable):
+    def __init__(self, polynomial: Union[Iterable[int], LFSRPolynomial]):
+        self.__polynomial = LFSRPolynomial(polynomial)
+        self.state = Signal(self.width, reset=1)
+        self.enable = Signal(1, reset=1)
+
+    @property
+    def polynomial(self) -> LFSRPolynomial:
+        return self.__polynomial
+
+    @property
+    def width(self) -> int:
+        return self.polynomial.max_exponent
+
+    def elaborate(self, platform: Any) -> Module:
+        m = Module()
+        feedback: Value = Const(0)
+        for exponent in self.polynomial:
+            if exponent > 0:
+                feedback = feedback ^ self.state[exponent - 1]
+        if self.width > 1:
+            with m.If(self.enable):
+                m.d.sync += self.state[1:self.width].eq(
+                    self.state[0:self.width - 1])
+                m.d.sync += self.state[0].eq(feedback)
+        return m

diff --git a/TLB/src/__init__.py b/TLB/src/__init__.py
new file mode 100644 (file)
index 0000000..e69de29

diff --git a/TLB/test/__init__.py b/TLB/test/__init__.py
new file mode 100644 (file)
index 0000000..e69de29

diff --git a/TLB/test/test_LFSR2.py b/TLB/test/test_LFSR2.py
new file mode 100644 (file)
index 0000000..f7eabc1
--- /dev/null
+++ b/TLB/test/test_LFSR2.py
@@ -0,0 +1,68 @@
+# SPDX-License-Identifier: LGPL-2.1-or-later
+# See Notices.txt for copyright information
+from ..src.LFSR2 import LFSR, LFSRPolynomial, LFSR_POLY_3
+from nmigen.back.pysim import Simulator, Delay, Tick
+import unittest
+
+
+class TestLFSR(unittest.TestCase):
+    def test_poly(self):
+        v = LFSRPolynomial()
+        self.assertEqual(repr(v), "LFSRPolynomial([0])")
+        self.assertEqual(str(v), "1")
+        v = LFSRPolynomial([1])
+        self.assertEqual(repr(v), "LFSRPolynomial([1, 0])")
+        self.assertEqual(str(v), "x + 1")
+        v = LFSRPolynomial([0, 1])
+        self.assertEqual(repr(v), "LFSRPolynomial([1, 0])")
+        self.assertEqual(str(v), "x + 1")
+        v = LFSRPolynomial([1, 2])
+        self.assertEqual(repr(v), "LFSRPolynomial([2, 1, 0])")
+        self.assertEqual(str(v), "x^2 + x + 1")
+        v = LFSRPolynomial([2])
+        self.assertEqual(repr(v), "LFSRPolynomial([2, 0])")
+        self.assertEqual(str(v), "x^2 + 1")
+        self.assertEqual(str(LFSR_POLY_3), "x^3 + x^2 + 1")
+
+    def test_lfsr_3(self):
+        module = LFSR(LFSR_POLY_3)
+        traces = [module.state, module.enable]
+        with Simulator(module,
+                       vcd_file=open("Waveforms/test_LFSR2.vcd", "w"),
+                       gtkw_file=open("Waveforms/test_LFSR2.gtkw", "w"),
+                       traces=traces) as sim:
+            sim.add_clock(1e-6, 0.25e-6)
+            delay = Delay(1e-7)
+
+            def async_process():
+                yield module.enable.eq(0)
+                yield Tick()
+                self.assertEqual((yield module.state), 0x1)
+                yield Tick()
+                self.assertEqual((yield module.state), 0x1)
+                yield module.enable.eq(1)
+                yield Tick()
+                yield delay
+                self.assertEqual((yield module.state), 0x2)
+                yield Tick()
+                yield delay
+                self.assertEqual((yield module.state), 0x5)
+                yield Tick()
+                yield delay
+                self.assertEqual((yield module.state), 0x3)
+                yield Tick()
+                yield delay
+                self.assertEqual((yield module.state), 0x7)
+                yield Tick()
+                yield delay
+                self.assertEqual((yield module.state), 0x6)
+                yield Tick()
+                yield delay
+                self.assertEqual((yield module.state), 0x4)
+                yield Tick()
+                yield delay
+                self.assertEqual((yield module.state), 0x1)
+                yield Tick()
+
+            sim.add_process(async_process)
+            sim.run()

diff --git a/Waveforms/.gitkeep b/Waveforms/.gitkeep
new file mode 100644 (file)
index 0000000..e69de29

diff --git a/mypy.ini b/mypy.ini
new file mode 100644 (file)
index 0000000..b569ead
--- /dev/null
+++ b/mypy.ini
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: LGPL-2.1-or-later
+# See Notices.txt for copyright information
+[mypy]
+python_version = 3.6
+mypy_path = ./nmigen-type-annotations
+warn_return_any = True
+warn_unused_configs = True
+disallow_untyped_defs = True

diff --git a/nmigen-type-annotations b/nmigen-type-annotations
new file mode 160000 (submodule)
index 0000000..227f399
--- /dev/null
+++ b/nmigen-type-annotations
@@ -0,0 +1 @@
+Subproject commit 227f39952a4529cea7f5da76c361bf6b650adff3