src/nmutil/clz.py

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