embfft 0.2.1

Non-blocking FFT for embedded systems
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

/* embfft | common.rs
 * Copyright (c) 2025 L. Sartory
 * SPDX-License-Identifier: MIT
 */

/******************************************************************************/

use core::ops::{Add, Mul, Neg, Sub};

/******************************************************************************/

pub struct Base<const N: usize>;

impl<const N: usize> Base<N> {
    /// Base 2 logarithm of the FFT size
    pub const LOG2_N: usize = {
        let mut x = N;
        let mut log2_n = 0;
        while x > 1 {
            x >>= 1;
            log2_n += 1;
        }
        log2_n
    };
    pub const IS_N_POW2: bool = {
        let mut n = 1;
        let mut i = Self::LOG2_N;
        while i > 0 {
            n <<= 1;
            i -= 1;
        }
        let is_n_pow2 = n == N;
        assert!(N >= 4, "The FFT data buffer size must be 4 or greater");
        assert!(is_n_pow2, "The FFT data buffer size must be a power of 2");
        is_n_pow2
    };

    /// Reverse all the bits in an integer
    ///
    /// Example: 0b11010010 --> 0b01001011
    /// Useful for sorting the output FFT values by frequency.
    pub const fn reverse_bits(x: usize) -> usize {
        let mut i = 0;
        let mut ret = 0;
        while i < Self::LOG2_N {
            ret |= ((x >> i) & 1) << ((Self::LOG2_N - 1) - i);
            i += 1;
        }
        ret
    }
}

/******************************************************************************/

/// A trait that allows generic implementations for float types
pub trait Float<const N: usize>:
    Copy + Add<Output = Self> + Mul<Output = Self> + Neg<Output = Self> + Sub<Output = Self>
{
    const ZERO: Self;
    const N_INV: Self;
    const SINE_TABLE: [Self; N];
}

macro_rules! gen_float_impl {
    ($T: ty) => {
        impl<const N: usize> Float<N> for $T {
            const ZERO: Self = 0.0;
            const N_INV: Self = 1.0 / N as $T;
            const SINE_TABLE: [Self; N] = {
                // TODO: the size should be N / 4...
                let mut table = [0.0; N];
                let mut i = 1;
                while i < N / 4 {
                    table[i] =
                        crate::cordic::sin(2.0 * core::f64::consts::PI * i as f64 / N as f64) as $T;
                    i += 1;
                }
                table
            };
        }
    };
}

gen_float_impl!(f32);
gen_float_impl!(f64);