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         # XXX internal signals do not need to be members of the module.
  34         # more to the point: why is the array needed at all?  just
  35         # assign step_i = self.input outside the loop, create one
  36         # step_o Signal at the start and assign step_i=step_o at the end
  37         def step(i):
  38             return Signal(self.width, name=f"step{i}")
  39         _steps = [step(i) for i in range(self.log2_width)]
  40
  41         # TODO: comment that this creates a full combinatorial chain
  42         # of RADIX-2 butterfly-network "swappers"
  43         for i, step_o in enumerate(_steps):
  44             step_i = self.input if i == 0 else _steps[i - 1]
  45             # TODO explain that chunk swap-sizes jump by a power2 each time
  46             chunk_size = 1 << i
  47             # TODO comment that this is creating the mux-swapper
  48             with m.If(self.chunk_sizes[i]):
  49                 # swap path
  50                 for j in range(self.width):
  51                     # TODO explain what this XOR does
  52                     m.d.comb += step_o[j].eq(step_i[j ^ chunk_size])
  53             with m.Else():
  54                 # straight path
  55                 m.d.comb += step_o.eq(step_i)
  56         # TODO comment that the last "step" is the output
  57         m.d.comb += self.output.eq(_steps[-1])
  58         return m