speed up ==, hash, <, >, <=, and >= for plain_data

[nmutil.git] / src / nmutil / prefix_sum.py

diff --git a/src/nmutil/prefix_sum.py b/src/nmutil/prefix_sum.py
index 65f2b33eaf079889590d5aa13ffb6fdb28f1628c..23eca36e2bb748c296c5a7ca88b9fa578258c653 100644 (file)
--- a/src/nmutil/prefix_sum.py
+++ b/src/nmutil/prefix_sum.py
@@ -20,20 +20,20 @@ class Op:
 
     def __init__(self, out, lhs, rhs, row):
         self.out = out
-        """index of the item to output to"""
+        "index of the item to output to"
 
         self.lhs = lhs
-        """index of the item the left-hand-side input comes from"""
+        "index of the item the left-hand-side input comes from"
 
         self.rhs = rhs
-        """index of the item the right-hand-side input comes from"""
+        "index of the item the right-hand-side input comes from"
 
         self.row = row
-        """row in the prefix-sum diagram"""
+        "row in the prefix-sum diagram"
 
 
 def prefix_sum_ops(item_count, *, work_efficient=False):
-    """ Get the associative operations needed to compute a parallel prefix-sum
+    """Get the associative operations needed to compute a parallel prefix-sum
     of `item_count` items.
 
     The operations aren't assumed to be commutative.
@@ -79,7 +79,7 @@ def prefix_sum_ops(item_count, *, work_efficient=False):
 
 
 def prefix_sum(items, fn=operator.add, *, work_efficient=False):
-    """ Compute the parallel prefix-sum of `items`, using associative operator
+    """Compute the parallel prefix-sum of `items`, using associative operator
     `fn` instead of addition.
 
     This has a depth of `O(log(N))` and an operation count of `O(N)` if
@@ -284,43 +284,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"