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

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

diff --git a/src/nmutil/clz.py b/src/nmutil/clz.py
index fed98cf44ed40b58505458d2b2549807540a5850..70e0f513c45b52034c9aac5aac8d86dd55d76a38 100644 (file)
--- a/src/nmutil/clz.py
+++ b/src/nmutil/clz.py
@@ -1,5 +1,24 @@
+# SPDX-License-Identifier: LGPL-3-or-later
 from nmigen import Module, Signal, Elaboratable, Cat, Repl
 import math
+""" This module is much more efficient than PriorityEncoder
+    although it is functionally identical.
+    see https://bugs.libre-soc.org/show_bug.cgi?id=326
+
+    This work is funded through NLnet under Grant 2019-02-012
+
+    License: LGPLv3+
+
+"""
+
+
+def clz(v, width):
+    """count leading zeros."""
+    assert isinstance(width, int) and 0 <= width
+    max_v = (1 << width) - 1
+    assert isinstance(v, int) and 0 <= v <= max_v
+    return max_v.bit_length() - v.bit_length()
+
 
 class CLZ(Elaboratable):
     def __init__(self, width):
@@ -46,8 +65,7 @@ class CLZ(Elaboratable):
                 left, lv = pairs[i+1]
                 right, rv = pairs[i]
                 width = right.width + 1
-                new_pair = Signal(width, name="cnt_%d_%d" %
-                                  (iteration, i))
+                new_pair = Signal(width, name="cnt_%d_%d" % (iteration, i))
                 if rv == lv:
                     with m.If(left[-1] == 1):
                         with m.If(right[-1] == 1):
@@ -62,7 +80,6 @@ class CLZ(Elaboratable):
                     with m.Else():
                         comb += new_pair.eq(left)
 
-
                 ret.append((new_pair, lv+rv))
         return ret
 
@@ -79,5 +96,3 @@ class CLZ(Elaboratable):
         comb += self.lz.eq(pairs[0][0])
 
         return m
-
-