src/nmutil/grev.py

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