src/ieee754/cordic/clz.py

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