src/nmutil/grev.py

   1 # SPDX-License-Identifier: LGPL-3-or-later
   2 # Copyright Jacob Lifshay ADD EMAIL ADDRESS ADD YEAR - FOLLOW STANDARD PRACTICE
   3 # Copyright (C) 2021 Luke Kenneth Casson Leighton <lkcl@lkcl.net>
   4
   5 # TODO(lkcl): add NGI POINTER funding notice, idk what we need for that...
   6 # realised it is actually NLnet (not NGI) so just "funded by NLnet Assure
   7 # and put URL)
   8
   9
  10 """Generalized bit-reverse. See `GRev` for docs. - no: move the
  11 module docstring here, to describe the Grev concept.
  12 * module docs tell you "about the concept and anything generally useful to know"
  13 * class docs are for "how to actually use the class".
  14 """
  15
  16 from nmigen.hdl.ast import Signal, Mux, Cat
  17 from nmigen.hdl.ast import Assert
  18 from nmigen.hdl.dsl import Module
  19 from nmigen.hdl.ir import Elaboratable
  20 from nmigen.cli import rtlil
  21
  22
  23 def grev(input, chunk_sizes, log2_width):
  24     """XXX start comments here with no space
  25     Python reference implementation of generalized bit-reverse.
  26     See `GRev` for documentation.
  27     """
  28     # mask inputs into range
  29     input &= 2 ** 2 ** log2_width - 1
  30     chunk_sizes &= 2 ** log2_width - 1
  31     # core algorithm:
  32     retval = 0
  33     for i in range(2 ** log2_width):
  34         # don't use `if` so this can be used with nmigen values
  35         bit = (input & (1 << i)) != 0
  36         retval |= bit << (i ^ chunk_sizes)
  37     return retval
  38
  39
  40 class GRev(Elaboratable):
  41     """ <--no space here>Generalized bit-reverse.
  42
  43     https://bugs.libre-soc.org/show_bug.cgi?id=755
  44
  45     XXX this is documentation about Grev (the concept) which should be in
  46     the docstring.  the class string is reserved for describing how to
  47     *use* the class (describe its inputs and outputs)
  48
  49     A generalized bit-reverse - also known as a butterfly network - is where
  50     every output bit is the input bit at index `output_bit_index XOR
  51     chunk_sizes` where `chunk_sizes` is the control input.
  52
  53     This is useful because many bit/byte reverse operations can be created by
  54     setting `chunk_sizes` to different values. Some examples for a 64-bit
  55     `grev` operation:
  56     * `0b111111` -- reverse all bits in the 64-bit word
  57     * `0b111000` -- reverse bytes in the 64-bit word
  58     * `0b011000` -- reverse bytes in each 32-bit word independently
  59     * `0b110000` -- reverse order of 16-bit words
  60
  61     This is implemented by using a series of `log2_width` 2:1 muxes, exactly
  62     as in a butterfly network: https://en.wikipedia.org/wiki/Butterfly_network
  63
  64     The 2:1 muxes are arranged to calculate successive `grev`-ed values where
  65     each intermediate value's corresponding `chunk_sizes` is progressively
  66     changed from all zeros to the input `chunk_sizes` by adding one bit at a
  67     time from the LSB to MSB.  (XXX i don't understand this at all!)
  68
  69     :reverse_order: if True the butterfly steps are performed
  70                     at offsets of 2^N ... 8 4 2.
  71                     if False, the order is 2 4 8 ... 2^N
  72     """
  73
  74     def __init__(self, log2_width, reverse_order=False):
  75         self.reverse_order = reverse_order    # reverses the order of steps
  76         self.log2_width = log2_width
  77         self.width = 1 << log2_width
  78         self.input = Signal(self.width)       # XXX mark this as an input
  79         self.chunk_sizes = Signal(log2_width) # XXX is this an input or output?
  80         self.output = Signal(self.width)      # XXX mark this as the output
  81
  82     def elaborate(self, platform):
  83         m = Module()
  84         comb = m.d.comb
  85
  86         # accumulate list of internal signals, exposed only for unit testing.
  87         # contains the input, intermediary steps, and the output.
  88         self._steps = [self.input]
  89
  90         # TODO: no. "see class doc comment for algorithm docs." <-- document
  91         #           *in* the code, not "see another location elsewhere"
  92         #           (unless it is a repeated text/concept of course, like
  93         #            with BitwiseLut, and that's because the API is identical)
  94         #           "see elsewhere" entirely defeats the object of the exercise.
  95         #           jumping back and forth (page-up, page-down)
  96         #           between the text and the code splits attention.
  97         #           the purpose of comments is to be able to understand
  98         #           (in plain english) the code *at* the point of seeing it
  99         #           it should contain "the thoughts going through your head"
 100         #
 101         #           demonstrated below (with a rewrite)
 102
 103         step_i = self.input # start with input as the first step
 104
 105         for i in range(self.log2_width):
 106             # each chunk is a power-2 jump.
 107             if self.reverse_order:
 108                 chunk_size = 1 << (self.log2_width-i-1)
 109             else:
 110                 chunk_size = 1 << i
 111             # prepare a list of XOR-swapped bits of this layer/step
 112             butterfly = [step_i[j ^ chunk_size] for j in range(self.width)]
 113             # create muxes here: 1 bit of chunk_sizes decides swap/no-swap
 114             step_o = Signal(self.width, name="step%d" % chunk_size)
 115             comb += step_o.eq(Mux(self.chunk_sizes[i], Cat(*butterfly), step_i))
 116             # output becomes input to next layer
 117             step_i = step_o
 118             self._steps.append(step_o) # record steps for test purposes (only)
 119
 120         # last layer is also the output
 121         comb += self.output.eq(step_o)
 122
 123         if platform != 'formal':
 124             return m
 125
 126         # formal test comparing directly against the (simpler) version
 127         m.d.comb += Assert(self.output == grev(self.input,
 128                                               self.chunk_sizes,
 129                                               self.log2_width))
 130         for i, step in enumerate(self._steps):
 131             cur_chunk_sizes = self.chunk_sizes & (2 ** i - 1)
 132             step_expected = grev(self.input, cur_chunk_sizes, self.log2_width)
 133             m.d.comb += Assert(step == step_expected)
 134
 135         return m
 136
 137     def ports(self):
 138         return [self.input, self.chunk_sizes, self.output]
 139
 140
 141 # useful to see what is going on: use yosys "read_ilang test_grev.il; show top"
 142 if __name__ == '__main__':
 143     dut = GRev(3)
 144     vl = rtlil.convert(dut, ports=dut.ports())
 145     with open("test_grev.il", "w") as f:
 146         f.write(vl)