1 # SPDX-License-Identifier: LGPL-3-or-later
2 # Copyright Jacob Lifshay
4 # TODO(lkcl): add NGI POINTER funding notice, idk what we need for that...
6 """Generalized bit-reverse. See `GRev` for docs."""
8 from nmigen
.hdl
.ast
import Signal
9 from nmigen
.hdl
.dsl
import Module
10 from nmigen
.hdl
.ir
import Elaboratable
11 from itertools
import tee
14 def pairwise(iterable
):
16 itertools.pairwise, added in Python 3.10, copied here cuz we support 3.7+
17 https://docs.python.org/3.10/library/itertools.html#itertools.pairwise
19 # code copied from Python's docs
25 def grev(input, chunk_sizes
, log2_width
):
27 Python reference implementation of generalized bit-reverse.
28 See `GRev` for documentation.
30 # mask inputs into range
31 input &= 2 ** 2 ** log2_width
- 1
32 chunk_sizes
&= 2 ** log2_width
- 1
35 for i
in range(2 ** log2_width
):
36 # don't use `if` so this can be used with nmigen values
37 bit
= (input & (1 << i
)) != 0
38 retval |
= bit
<< (i ^ chunk_sizes
)
42 class GRev(Elaboratable
):
43 """ Generalized bit-reverse.
45 https://bugs.libre-soc.org/show_bug.cgi?id=755
47 A generalized bit-reverse is where every output bit is the input bit at
48 index `output_bit_index XOR chunk_sizes` where `chunk_sizes` is the
51 This is useful because many bit/byte reverse operations can be created by
52 setting `chunk_sizes` to different values. Some examples for a 64-bit
54 * `0b111111` -- reverse bits in the 64-bit word
55 * `0b111000` -- reverse bytes in the 64-bit word
56 * `0b011000` -- reverse bytes in each 32-bit word independently
57 * `0b110000` -- reverse order of 16-bit words
59 This is implemented by using a series of `log2_width` 2:1 muxes, this is
60 similar, but not identical, to a butterfly network. This is also similar
61 to a common barrel-shifter/rotater design.
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.
68 https://en.wikipedia.org/wiki/Butterfly_network
69 https://en.wikipedia.org/wiki/Barrel_shifter#Implementation
72 def __init__(self
, log2_width
):
73 self
.log2_width
= log2_width
74 self
.width
= 1 << log2_width
75 self
.input = Signal(self
.width
)
76 self
.chunk_sizes
= Signal(log2_width
)
77 self
.output
= Signal(self
.width
)
78 self
._steps
= [self
.input]
79 """ internal signals, exposed for unit testing """
80 for i
in range(1, log2_width
):
81 self
._steps
.append(Signal(self
.width
, name
=f
"step{i}"))
82 self
._steps
.append(self
.output
)
84 def elaborate(self
, platform
):
87 # see class doc comment for algorithm docs.
88 for i
, (step_i
, step_o
) in enumerate(pairwise(self
._steps
)):
90 with m
.If(self
.chunk_sizes
[i
]):
91 for j
in range(self
.width
):
92 m
.d
.comb
+= step_o
[j
].eq(step_i
[j ^ chunk_size
])
94 m
.d
.comb
+= step_o
.eq(step_i
)