src/nmutil/grev.py

   1 # SPDX-License-Identifier: LGPL-3-or-later
   2 # See Notices.txt for copyright information
   3
   4 # TODO add funding and explicit copyright notice (contractually required by
   5 # NGI POINTER)
   6
   7 # TODO link to bugreport
   8
   9 from nmigen.hdl.ast import Signal
  10 from nmigen.hdl.dsl import Module
  11 from nmigen.hdl.ir import Elaboratable
  12 from itertools import tee
  13
  14
  15 def pairwise(iterable):
  16     """
  17     itertools.pairwise, added in Python 3.10, copied here cuz we support 3.7+
  18     https://docs.python.org/3.10/library/itertools.html#itertools.pairwise
  19     """
  20     # code copied from Python's docs
  21     a, b = tee(iterable)
  22     next(b, None)
  23     return zip(a, b)
  24
  25
  26 def grev(input, chunk_sizes, log2_width):
  27     """
  28     Python reference implementation of generalized bit-reverse.
  29     See `GRev` for documentation.
  30     """
  31     # mask inputs into range
  32     input &= 2 ** 2 ** log2_width - 1
  33     chunk_sizes &= 2 ** log2_width - 1
  34     # core algorithm:
  35     retval = 0
  36     for i in range(2 ** log2_width):
  37         # don't use `if` so this can be used with nmigen values
  38         bit = (input & (1 << i)) != 0
  39         retval |= bit << (i ^ chunk_sizes)
  40     return retval
  41
  42
  43 class GRev(Elaboratable):
  44     """ Generalized bit-reverse.
  45
  46     A generalized bit-reverse is where every output bit is the input bit at
  47     index `output_bit_index XOR chunk_sizes` where `chunk_sizes` is the
  48     control input.
  49
  50     This is useful because many bit/byte reverse operations can be created by
  51     setting `chunk_sizes` to different values. Some examples for a 64-bit
  52     `grev` operation:
  53     * `0b111111` -- reverse bits in the 64-bit word
  54     * `0b111000` -- reverse bytes in the 64-bit word
  55     * `0b011000` -- reverse bytes in each 32-bit word independently
  56     * `0b110000` -- reverse order of 16-bit words
  57
  58     This is implemented by using a series of `log2_width` 2:1 muxes, this is
  59     similar, but not identical, to a butterfly network. This is also similar
  60     to a common barrel-shifter/rotater design.
  61
  62     The 2:1 muxes are arranged to calculate successive `grev`-ed values where
  63     the intermediate values corresponding `chunk_sizes` is progressively
  64     changed from all zeros to the input `chunk_sizes` by adding one bit at a
  65     time from the LSB to MSB.
  66
  67     https://en.wikipedia.org/wiki/Butterfly_network
  68     https://en.wikipedia.org/wiki/Barrel_shifter#Implementation
  69     """
  70
  71     def __init__(self, log2_width):
  72         self.log2_width = log2_width
  73         self.width = 1 << log2_width
  74         self.input = Signal(self.width)
  75         self.chunk_sizes = Signal(log2_width)
  76         self.output = Signal(self.width)
  77         self._steps = [self.input]
  78         """ internal signals for unit testing """
  79         for i in range(1, log2_width):
  80             self._steps.append(Signal(self.width, name=f"step{i}"))
  81         self._steps.append(self.output)
  82
  83     def elaborate(self, platform):
  84         m = Module()
  85
  86         # see class doc comment for algorithm docs.
  87         for i, (step_i, step_o) in enumerate(pairwise(self._steps)):
  88             chunk_size = 1 << i
  89             with m.If(self.chunk_sizes[i]):
  90                 for j in range(self.width):
  91                     m.d.comb += step_o[j].eq(step_i[j ^ chunk_size])
  92             with m.Else():
  93                 m.d.comb += step_o.eq(step_i)
  94
  95         return m