18b2398fb23b7cde3d3f5ec2746f353f443a07eb
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 # Funded by NLnet Assure Programme 2021-02-052, https://nlnet.nl/assure part
6 # of Horizon 2020 EU Programme 957073.
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".
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
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 # create (reversed?) list of steps
105 steps
= list(range(self
.log2_width
))
106 if self
.reverse_order
: steps
.reverse()
109 # each chunk is a power-2 jump.
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
118 self
._steps
.append(step_o
) # record steps for test purposes (only)
120 # last layer is also the output
121 comb
+= self
.output
.eq(step_o
)
123 if platform
!= 'formal':
126 # formal test comparing directly against the (simpler) version
127 m
.d
.comb
+= Assert(self
.output
== grev(self
.input,
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
)
138 return [self
.input, self
.chunk_sizes
, self
.output
]
141 # useful to see what is going on: use yosys "read_ilang test_grev.il; show top"
142 if __name__
== '__main__':
144 vl
= rtlil
.convert(dut
, ports
=dut
.ports())
145 with
open("test_grev.il", "w") as f
: