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 from nmigen.hdl.ast import Signal
   8 from nmigen.hdl.dsl import Module
   9 from nmigen.hdl.ir import Elaboratable
  10
  11 # TODO link to bugreport
  12
  13 class GRev(Elaboratable):
  14     """TODO comments, "this is a half-butterfly aka "generalised reverse"
  15     so that it shows up in the auto-generated documentation
  16     link to wikipedia etc. etc. https://en.wikipedia.org/wiki/Butterfly_network
  17
  18     """
  19
  20     def __init__(self, log2_width):
  21         assert isinstance(log2_width, int) # TODO: remove. unnecessary.
  22         self.log2_width = log2_width
  23         self.width = 1 << log2_width
  24
  25         self.input = Signal(self.width)
  26         self.chunk_sizes = Signal(log2_width)
  27
  28         self.output = Signal(self.width)
  29
  30     def elaborate(self, platform):
  31         m = Module()
  32
  33         _steps = [] # cumulative list of steps (for unit test purposes only)
  34
  35         step_i = self.input # start combinatorial chain with the input
  36
  37         # TODO: comment that this creates a full combinatorial chain
  38         # of RADIX-2 butterfly-network "swappers"
  39         for i, step_o in enumerate(_steps):
  40             step_o = Signal(self.width, name="step_%d" % i)
  41             _steps.append(step_o)
  42             # TODO explain that chunk swap-sizes jump by a power2 each time
  43             chunk_size = 1 << i
  44             # TODO comment that this is creating the mux-swapper
  45             with m.If(self.chunk_sizes[i]):
  46                 # the mux swap path
  47                 for j in range(self.width):
  48                     # TODO explain what this XOR does
  49                     m.d.comb += step_o[j].eq(step_i[j ^ chunk_size])
  50             with m.Else():
  51                 # the mux straight path
  52                 m.d.comb += step_o.eq(step_i)
  53             step_i = step_o # for next loop, to create the combinatorial chain
  54         # TODO comment that the last "step" is the output
  55         m.d.comb += self.output.eq(_steps[-1]) # TODO: replace with step_o
  56
  57         # give access to the steps list for testing purposes
  58         self._steps = _steps
  59
  60         return m