src/nmutil/grev.py

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