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>
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
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".
16 from nmigen
.hdl
.ast
import Signal
, Mux
, Cat
17 from nmigen
.hdl
.dsl
import Module
18 from nmigen
.hdl
.ir
import Elaboratable
19 from nmigen
.cli
import rtlil
22 def grev(input, chunk_sizes
, log2_width
):
23 """XXX start comments here with no space
24 Python reference implementation of generalized bit-reverse.
25 See `GRev` for documentation.
27 # mask inputs into range
28 input &= 2 ** 2 ** log2_width
- 1
29 chunk_sizes
&= 2 ** log2_width
- 1
32 for i
in range(2 ** log2_width
):
33 # don't use `if` so this can be used with nmigen values
34 bit
= (input & (1 << i
)) != 0
35 retval |
= bit
<< (i ^ chunk_sizes
)
39 class GRev(Elaboratable
):
40 """ <--no space here>Generalized bit-reverse.
42 https://bugs.libre-soc.org/show_bug.cgi?id=755
44 XXX this is documentation about Grev (the concept) which should be in
45 the docstring. the class string is reserved for describing how to
46 *use* the class (describe its inputs and outputs)
48 A generalized bit-reverse - also known as a butterfly network - is where
49 every output bit is the input bit at index `output_bit_index XOR
50 chunk_sizes` where `chunk_sizes` is the control input.
52 This is useful because many bit/byte reverse operations can be created by
53 setting `chunk_sizes` to different values. Some examples for a 64-bit
55 * `0b111111` -- reverse all bits in the 64-bit word
56 * `0b111000` -- reverse bytes in the 64-bit word
57 * `0b011000` -- reverse bytes in each 32-bit word independently
58 * `0b110000` -- reverse order of 16-bit words
60 This is implemented by using a series of `log2_width` 2:1 muxes, exactly
61 as in a butterfly network: https://en.wikipedia.org/wiki/Butterfly_network
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. (XXX i don't understand this at all!)
68 :reverse_order: if True the butterfly steps are performed
69 at offsets of 2^N ... 8 4 2.
70 if False, the order is 2 4 8 ... 2^N
73 def __init__(self
, log2_width
, reverse_order
=False):
74 self
.reverse_order
= reverse_order
# reverses the order of steps
75 self
.log2_width
= log2_width
76 self
.width
= 1 << log2_width
77 self
.input = Signal(self
.width
) # XXX mark this as an input
78 self
.chunk_sizes
= Signal(log2_width
) # XXX is this an input or output?
79 self
.output
= Signal(self
.width
) # XXX mark this as the output
81 def elaborate(self
, platform
):
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]
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"
100 # demonstrated below (with a rewrite)
102 step_i
= self
.input # start with input as the first step
104 for i
in range(self
.log2_width
):
105 # each chunk is a power-2 jump.
106 if self
.reverse_order
:
107 chunk_size
= 1 << (self
.log2_width
-i
-1)
110 # prepare a list of XOR-swapped bits of this layer/step
111 butterfly
= [step_i
[j ^ chunk_size
] for j
in range(self
.width
)]
112 # create muxes here: 1 bit of chunk_sizes decides swap/no-swap
113 step_o
= Signal(self
.width
, name
="step%d" % chunk_size
)
114 comb
+= step_o
.eq(Mux(self
.chunk_sizes
[i
], Cat(*butterfly
), step_i
))
115 # output becomes input to next layer
117 self
._steps
.append(step_o
) # record steps for test purposes (only)
119 # last layer is also the output
120 comb
+= self
.output
.eq(step_o
)
125 return [self
.input, self
.chunk_sizes
, self
.output
]
128 # useful to see what is going on: use yosys "read_ilang test_grev.il; show top"
129 if __name__
== '__main__':
131 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
132 with
open("test_grev.il", "w") as f
: