From af620acc0a02e29ba8efcba8d55cf7c5f1f171c2 Mon Sep 17 00:00:00 2001
From: Luke Kenneth Casson Leighton <lkcl@lkcl.net>
Date: Thu, 18 Aug 2022 10:37:38 +0100
Subject: [PATCH] moved pop_count to its own separate module so that it is
 obvious it exists. anyone looking at the top-level directory of nmutil will
 see "oh there is a popcount.py in here"

---
 src/nmutil/popcount.py             | 62 ++++++++++++++++++++++++++++++
 src/nmutil/prefix_sum.py           | 37 ------------------
 src/nmutil/test/test_prefix_sum.py |  3 +-
 3 files changed, 64 insertions(+), 38 deletions(-)
 create mode 100644 src/nmutil/popcount.py

diff --git a/src/nmutil/popcount.py b/src/nmutil/popcount.py
new file mode 100644
index 0000000..cdbe3b2
--- /dev/null
+++ b/src/nmutil/popcount.py
@@ -0,0 +1,62 @@
+# SPDX-License-Identifier: LGPL-3-or-later
+# Copyright 2022 Jacob Lifshay programmerjake@gmail.com
+
+# Funded by NLnet Assure Programme 2021-02-052, https://nlnet.nl/assure part
+# of Horizon 2020 EU Programme 957073.
+
+from nmigen import Module
+from nmigen.hdl.ast import Value, Const, Signal
+from nmutil.plain_data import plain_data
+from nmutil.prefix_sum import tree_reduction
+from nmigen.cli import rtlil
+
+
+def pop_count(v, *, width=None, process_temporary=lambda v: v):
+    """return the population count (number of 1 bits) of `v`.
+    Arguments:
+    v: nmigen.Value | int
+        the value to calculate the pop-count of.
+    width: int | None
+        the bit-width of `v`.
+        If `width` is None, then `v` must be a nmigen Value or
+        match `v`'s width.
+    process_temporary: function of (type(v)) -> type(v)
+        called after every addition operation, can be used to introduce
+        `Signal`s for the intermediate values in the pop-count computation
+        like so:
+
+        ```
+        def process_temporary(v):
+            sig = Signal.like(v)
+            m.d.comb += sig.eq(v)
+            return sig
+        ```
+    """
+    if isinstance(v, Value):
+        if width is None:
+            width = len(v)
+        assert width == len(v)
+        bits = [v[i] for i in range(width)]
+        if len(bits) == 0:
+            return Const(0)
+    else:
+        assert width is not None, "width must be given"
+        # v and width are ints
+        bits = [(v & (1 << i)) != 0 for i in range(width)]
+        if len(bits) == 0:
+            return 0
+    return tree_reduction(bits, fn=lambda a, b: process_temporary(a + b))
+
+
+# run this as simply "python3 popcount.py" to create an ilang file that
+# can be viewed with yosys "read_ilang test_popcount.il; show top"
+if __name__ == "__main__":
+    m = Module()
+    v = Signal(8)
+    x = Signal(8)
+    pc = pop_count(v, width=8)
+    m.d.comb += v.eq(pc)
+    vl = rtlil.convert(m)
+    with open("test_popcount.il", "w") as f:
+        f.write(vl)
+
diff --git a/src/nmutil/prefix_sum.py b/src/nmutil/prefix_sum.py
index bd13219..51e28ac 100644
--- a/src/nmutil/prefix_sum.py
+++ b/src/nmutil/prefix_sum.py
@@ -277,43 +277,6 @@ def tree_reduction(items, fn=operator.add):
     return items[-1]
 
 
-def pop_count(v, *, width=None, process_temporary=lambda v: v):
-    """return the population count (number of 1 bits) of `v`.
-    Arguments:
-    v: nmigen.Value | int
-        the value to calculate the pop-count of.
-    width: int | None
-        the bit-width of `v`.
-        If `width` is None, then `v` must be a nmigen Value or
-        match `v`'s width.
-    process_temporary: function of (type(v)) -> type(v)
-        called after every addition operation, can be used to introduce
-        `Signal`s for the intermediate values in the pop-count computation
-        like so:
-
-        ```
-        def process_temporary(v):
-            sig = Signal.like(v)
-            m.d.comb += sig.eq(v)
-            return sig
-        ```
-    """
-    if isinstance(v, Value):
-        if width is None:
-            width = len(v)
-        assert width == len(v)
-        bits = [v[i] for i in range(width)]
-        if len(bits) == 0:
-            return Const(0)
-    else:
-        assert width is not None, "width must be given"
-        # v and width are ints
-        bits = [(v & (1 << i)) != 0 for i in range(width)]
-        if len(bits) == 0:
-            return 0
-    return tree_reduction(bits, fn=lambda a, b: process_temporary(a + b))
-
-
 if __name__ == "__main__":
     print("the non-work-efficient algorithm, matches the diagram in wikipedia:"
           "\n"
diff --git a/src/nmutil/test/test_prefix_sum.py b/src/nmutil/test/test_prefix_sum.py
index 7f1c45a..cef9da1 100644
--- a/src/nmutil/test/test_prefix_sum.py
+++ b/src/nmutil/test/test_prefix_sum.py
@@ -9,7 +9,8 @@ from nmutil.formaltest import FHDLTestCase
 from nmutil.sim_util import write_il
 from itertools import accumulate
 import operator
-from nmutil.prefix_sum import (Op, pop_count, prefix_sum,
+from nmutil.popcount import pop_count
+from nmutil.prefix_sum import (Op, prefix_sum,
                                render_prefix_sum_diagram,
                                tree_reduction, tree_reduction_ops)
 import unittest
-- 
2.30.2