lambdaworks_math/fft/cpu/
bit_reversing.rs

1/// In-place bit-reverse permutation algorithm. Requires input length to be a power of two.
2pub fn in_place_bit_reverse_permute<E>(input: &mut [E]) {
3    for i in 0..input.len() {
4        let bit_reversed_index = reverse_index(i, input.len() as u64);
5        if bit_reversed_index > i {
6            input.swap(i, bit_reversed_index);
7        }
8    }
9}
10
11/// Reverses the `log2(size)` first bits of `i`
12pub fn reverse_index(i: usize, size: u64) -> usize {
13    if size == 1 {
14        i
15    } else {
16        i.reverse_bits() >> (usize::BITS - size.trailing_zeros())
17    }
18}
19
20#[cfg(all(test, feature = "alloc"))]
21mod test {
22    use super::*;
23    use alloc::vec::Vec;
24
25    // TODO: proptest would be better.
26    #[test]
27    fn bit_reverse_permutation_works() {
28        let mut reversed: Vec<usize> = Vec::with_capacity(16);
29        for i in 0..reversed.capacity() {
30            reversed.push(reverse_index(i, reversed.capacity() as u64));
31        }
32        assert_eq!(
33            reversed[..],
34            [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
35        );
36
37        in_place_bit_reverse_permute(&mut reversed[..]);
38        assert_eq!(
39            reversed[..],
40            [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
41        );
42    }
43
44    #[test]
45    fn bit_reverse_permutation_edge_case() {
46        let mut edge_case = [0];
47
48        in_place_bit_reverse_permute(&mut edge_case[..]);
49        assert_eq!(edge_case[..], [0]);
50    }
51}
lambdaworks_math/fft/cpu/bit_reversing.rs

lambdaworks_math/fft/cpu/
bit_reversing.rs
