Add count leading zeros module (should probably go somewhere else)

diff --git a/src/ieee754/cordic/clz.py b/src/ieee754/cordic/clz.py
new file mode 100644 (file)
index 0000000..a6dec14
--- /dev/null
+++ b/src/ieee754/cordic/clz.py
@@ -0,0 +1,68 @@
+from nmigen import Module, Signal, Elaboratable, Cat, Repl
+import math
+
+class CLZ(Elaboratable):
+    def __init__(self, width):
+        self.width = width
+        self.sig_in = Signal(width, reset_less=True)
+        out_width = math.ceil(math.log2(width+1))
+        self.lz = Signal(out_width)
+
+    def generate_pairs(self, m):
+        comb = m.d.comb
+        assert self.width % 2 == 0  # TODO handle odd widths
+        pairs = []
+        for i in range(0, self.width, 2):
+            pair = Signal(2, name="pair%d" % i)
+            comb += pair.eq(self.sig_in[i:i+2])
+
+            pair_cnt = Signal(2, name="cnt_1_%d" % (i/2))
+            with m.Switch(pair):
+                with m.Case(0):
+                    comb += pair_cnt.eq(2)
+                with m.Case(1):
+                    comb += pair_cnt.eq(1)
+                with m.Default():
+                    comb += pair_cnt.eq(0)
+            pairs.append(pair_cnt)
+        return pairs
+
+    def combine_pairs(self, m, iteration, pairs):
+        comb = m.d.comb
+        length = len(pairs)
+        assert length % 2 == 0  # TODO handle non powers of 2
+        ret = []
+        for i in range(0, length, 2):
+            left = pairs[i+1]
+            right = pairs[i]
+            width = left.width + 1
+            print(left)
+            print(f"pair({i}, {i+1}) - cnt_{iteration}_{i}")
+            new_pair = Signal(left.width + 1, name="cnt_%d_%d" %
+                              (iteration, i))
+            with m.If(left[-1] == 1):
+                with m.If(right[-1] == 1):
+                    comb += new_pair.eq(Cat(Repl(0, width-1), 1))
+                with m.Else():
+                    comb += new_pair.eq(Cat(right[0:-1], 0b01))
+            with m.Else():
+                comb += new_pair.eq(Cat(left, 0))
+
+            ret.append(new_pair)
+        return ret
+
+    def elaborate(self, platform):
+        m = Module()
+        comb = m.d.comb
+
+        pairs = self.generate_pairs(m)
+        i = 2
+        while len(pairs) > 1:
+            pairs = self.combine_pairs(m, i, pairs)
+            i += 1
+
+        comb += self.lz.eq(pairs[0])
+
+        return m
+
+        

diff --git a/src/ieee754/cordic/test/test_clz.py b/src/ieee754/cordic/test/test_clz.py
new file mode 100644 (file)
index 0000000..78d43e3
--- /dev/null
+++ b/src/ieee754/cordic/test/test_clz.py
@@ -0,0 +1,42 @@
+from nmigen import Module, Signal
+from nmigen.back.pysim import Simulator, Delay
+from nmigen.test.utils import FHDLTestCase
+
+from ieee754.cordic.clz import CLZ
+import unittest
+import math
+import random
+
+
+class CLZTestCase(FHDLTestCase):
+    def run_test(self, inputs, width=8):
+
+        m = Module()
+
+        m.submodules.dut = dut = CLZ(width)
+        sig_in = Signal.like(dut.sig_in)
+        count = Signal.like(dut.lz)
+
+
+        m.d.comb += [
+            dut.sig_in.eq(sig_in),
+            count.eq(dut.lz)]
+
+        sim = Simulator(m)
+
+        def process():
+            for i in inputs:
+                yield sig_in.eq(i)
+                yield Delay(1e-6)
+        sim.add_process(process)
+        with sim.write_vcd("clz.vcd", "clz.gtkw", traces=[
+                sig_in, count]):
+            sim.run()
+
+    def test_selected(self):
+        inputs = [0, 15, 10, 127]
+        self.run_test(iter(inputs), width=8)
+
+
+if __name__ == "__main__":
+    unittest.main()