src/nmutil/clz.py

   1 # SPDX-License-Identifier: LGPL-3-or-later
   2 from nmigen import Module, Signal, Elaboratable, Cat, Repl
   3 import math
   4 """ This module is much more efficient than PriorityEncoder
   5     although it is functionally identical.
   6     see https://bugs.libre-soc.org/show_bug.cgi?id=326
   7
   8     This work is funded through NLnet under Grant 2019-02-012
   9
  10     License: LGPLv3+
  11
  12 """
  13
  14
  15 def clz(v, width):
  16     """count leading zeros."""
  17     assert isinstance(width, int) and 0 <= width
  18     max_v = (1 << width) - 1
  19     assert isinstance(v, int) and 0 <= v <= max_v
  20     return max_v.bit_length() - v.bit_length()
  21
  22
  23 class CLZ(Elaboratable):
  24     def __init__(self, width):
  25         self.width = width
  26         self.sig_in = Signal(width, reset_less=True)
  27         out_width = math.ceil(math.log2(width+1))
  28         self.lz = Signal(out_width)
  29
  30     def generate_pairs(self, m):
  31         comb = m.d.comb
  32         pairs = []
  33         for i in range(0, self.width, 2):
  34             if i+1 >= self.width:
  35                 pair = Signal(1, name="cnt_1_%d" % (i/2))
  36                 comb += pair.eq(~self.sig_in[i])
  37                 pairs.append((pair, 1))
  38             else:
  39                 pair = Signal(2, name="pair%d" % i)
  40                 comb += pair.eq(self.sig_in[i:i+2])
  41
  42                 pair_cnt = Signal(2, name="cnt_1_%d" % (i/2))
  43                 with m.Switch(pair):
  44                     with m.Case(0):
  45                         comb += pair_cnt.eq(2)
  46                     with m.Case(1):
  47                         comb += pair_cnt.eq(1)
  48                     with m.Default():
  49                         comb += pair_cnt.eq(0)
  50                 pairs.append((pair_cnt, 2))  # append pair, max_value
  51         return pairs
  52
  53     def combine_pairs(self, m, iteration, pairs):
  54         comb = m.d.comb
  55         length = len(pairs)
  56         ret = []
  57         for i in range(0, length, 2):
  58             if i+1 >= length:
  59                 right, mv = pairs[i]
  60                 width = right.width
  61                 new_pair = Signal(width, name="cnt_%d_%d" % (iteration, i))
  62                 comb += new_pair.eq(Cat(right, 0))
  63                 ret.append((new_pair, mv))
  64             else:
  65                 left, lv = pairs[i+1]
  66                 right, rv = pairs[i]
  67                 width = right.width + 1
  68                 new_pair = Signal(width, name="cnt_%d_%d" % (iteration, i))
  69                 if rv == lv:
  70                     with m.If(left[-1] == 1):
  71                         with m.If(right[-1] == 1):
  72                             comb += new_pair.eq(Cat(Repl(0, width-1), 1))
  73                         with m.Else():
  74                             comb += new_pair.eq(Cat(right[0:-1], 0b01))
  75                     with m.Else():
  76                         comb += new_pair.eq(Cat(left, 0))
  77                 else:
  78                     with m.If(left == lv):
  79                         comb += new_pair.eq(right + left)
  80                     with m.Else():
  81                         comb += new_pair.eq(left)
  82
  83                 ret.append((new_pair, lv+rv))
  84         return ret
  85
  86     def elaborate(self, platform):
  87         m = Module()
  88         comb = m.d.comb
  89
  90         pairs = self.generate_pairs(m)
  91         i = 2
  92         while len(pairs) > 1:
  93             pairs = self.combine_pairs(m, i, pairs)
  94             i += 1
  95
  96         comb += self.lz.eq(pairs[0][0])
  97
  98         return m