782ac90f80fcaf203bddccb7f07a02d9ed2550c3
1 # SPDX-License-Identifier: LGPL-3-or-later
2 # See Notices.txt for copyright information
4 # TODO add funding and explicit copyright notice (contractually required by
7 # TODO link to bugreport
9 from nmigen
.hdl
.ast
import Signal
10 from nmigen
.hdl
.dsl
import Module
11 from nmigen
.hdl
.ir
import Elaboratable
12 from itertools
import tee
15 def pairwise(iterable
):
17 itertools.pairwise, added in Python 3.10, copied here cuz we support 3.7+
18 https://docs.python.org/3.10/library/itertools.html#itertools.pairwise
20 # code copied from Python's docs
26 def grev(input, chunk_sizes
, log2_width
):
28 Python reference implementation of generalized bit-reverse.
29 See `GRev` for documentation.
31 # mask inputs into range
32 input &= 2 ** 2 ** log2_width
- 1
33 chunk_sizes
&= 2 ** log2_width
- 1
36 for i
in range(2 ** log2_width
):
37 # don't use `if` so this can be used with nmigen values
38 bit
= (input & (1 << i
)) != 0
39 retval |
= bit
<< (i ^ chunk_sizes
)
43 class GRev(Elaboratable
):
44 """ Generalized bit-reverse.
46 A generalized bit-reverse is where every output bit is the input bit at
47 index `output_bit_index XOR chunk_sizes` where `chunk_sizes` is the
50 This is useful because many bit/byte reverse operations can be created by
51 setting `chunk_sizes` to different values. Some examples for a 64-bit
53 * `0b111111` -- reverse bits in the 64-bit word
54 * `0b111000` -- reverse bytes in the 64-bit word
55 * `0b011000` -- reverse bytes in each 32-bit word independently
56 * `0b110000` -- reverse order of 16-bit words
58 This is implemented by using a series of `log2_width` 2:1 muxes, this is
59 similar, but not identical, to a butterfly network. This is also similar
60 to a common barrel-shifter/rotater design.
62 The 2:1 muxes are arranged to calculate successive `grev`-ed values where
63 the intermediate values 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.
67 https://en.wikipedia.org/wiki/Butterfly_network
68 https://en.wikipedia.org/wiki/Barrel_shifter#Implementation
71 def __init__(self
, log2_width
):
72 self
.log2_width
= log2_width
73 self
.width
= 1 << log2_width
74 self
.input = Signal(self
.width
)
75 self
.chunk_sizes
= Signal(log2_width
)
76 self
.output
= Signal(self
.width
)
77 self
._steps
= [self
.input]
78 """ internal signals for unit testing """
79 for i
in range(1, log2_width
):
80 self
._steps
.append(Signal(self
.width
, name
=f
"step{i}"))
81 self
._steps
.append(self
.output
)
83 def elaborate(self
, platform
):
86 # see class doc comment for algorithm docs.
87 for i
, (step_i
, step_o
) in enumerate(pairwise(self
._steps
)):
89 with m
.If(self
.chunk_sizes
[i
]):
90 for j
in range(self
.width
):
91 m
.d
.comb
+= step_o
[j
].eq(step_i
[j ^ chunk_size
])
93 m
.d
.comb
+= step_o
.eq(step_i
)