Skip to main content

qualia_core_db/medical/reconstruction/
spectral_fft.rs

1//! Exact `f64` O(N log N) Cooley-Tukey radix-2 & Bluestein chirp-z arbitrary-length
2//! 1D/2D/3D FFT/IFFT, `fftshift`/`ifftshift`, Marple analytic Hilbert envelope, and windows.
3use crate::solvers::transforms::fourier::Cplx;
4use core::f64::consts::PI;
5
6#[derive(Clone, Copy, Debug, PartialEq, Eq)]
7pub enum WindowKind {
8    Boxcar,
9    Hanning,
10    Hamming,
11}
12
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
14pub enum SpectralError {
15    EmptyInput,
16    ShapeMismatch,
17    NonFiniteInput,
18    SizeLimit,
19}
20
21impl std::fmt::Display for SpectralError {
22    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
23        write!(f, "spectral transform error: {self:?}")
24    }
25}
26impl std::error::Error for SpectralError {}
27
28#[inline]
29fn cmul(a: Cplx, b: Cplx) -> Cplx {
30    (a.0 * b.0 - a.1 * b.1, a.0 * b.1 + a.1 * b.0)
31}
32
33#[inline]
34fn cadd(a: Cplx, b: Cplx) -> Cplx {
35    (a.0 + b.0, a.1 + b.1)
36}
37
38#[inline]
39fn csub(a: Cplx, b: Cplx) -> Cplx {
40    (a.0 - b.0, a.1 - b.1)
41}
42
43pub fn validate_finite_complex(buf: &[Cplx]) -> Result<(), SpectralError> {
44    if buf.iter().any(|&(re, im)| !re.is_finite() || !im.is_finite()) {
45        return Err(SpectralError::NonFiniteInput);
46    }
47    Ok(())
48}
49
50/// In-place iterative Cooley-Tukey radix-2 DIT FFT (`sign = -1.0` forward, `+1.0` inverse; unscaled).
51fn fft_pow2_inplace(buf: &mut [Cplx], sign: f64) {
52    let n = buf.len();
53    if n <= 1 {
54        return;
55    }
56    let mut j = 0usize;
57    for i in 1..n {
58        let mut bit = n >> 1;
59        while (j & bit) != 0 {
60            j ^= bit;
61            bit >>= 1;
62        }
63        j ^= bit;
64        if i < j {
65            buf.swap(i, j);
66        }
67    }
68    let mut len = 2usize;
69    while len <= n {
70        let ang = sign * 2.0 * PI / len as f64;
71        let wlen = (ang.cos(), ang.sin());
72        let half = len >> 1;
73        for start in (0..n).step_by(len) {
74            let mut w = (1.0, 0.0);
75            for k in 0..half {
76                let u = buf[start + k];
77                let v = cmul(buf[start + k + half], w);
78                buf[start + k] = cadd(u, v);
79                buf[start + k + half] = csub(u, v);
80                w = cmul(w, wlen);
81            }
82        }
83        len <<= 1;
84    }
85}
86
87/// Bluestein Chirp-Z O(M log M) arbitrary-length 1D unscaled transform.
88fn fft_bluestein(buf: &[Cplx], sign: f64) -> Result<Vec<Cplx>, SpectralError> {
89    let n = buf.len();
90    let m = (2 * n - 1).checked_next_power_of_two().ok_or(SpectralError::SizeLimit)?;
91    let mut a = vec![(0.0, 0.0); m];
92    let mut b = vec![(0.0, 0.0); m];
93    let mut chirps = Vec::with_capacity(n);
94
95    for k in 0..n {
96        let theta = sign * PI * ((k * k) % (2 * n)) as f64 / n as f64;
97        let w = (theta.cos(), theta.sin());
98        chirps.push(w);
99        a[k] = cmul(buf[k], w);
100        b[k] = (w.0, -w.1);
101        if k > 0 {
102            b[m - k] = b[k];
103        }
104    }
105
106    fft_pow2_inplace(&mut a, -1.0);
107    fft_pow2_inplace(&mut b, -1.0);
108    for (ai, bi) in a.iter_mut().zip(b.iter()) {
109        *ai = cmul(*ai, *bi);
110    }
111    fft_pow2_inplace(&mut a, 1.0);
112
113    let inv_m = 1.0 / m as f64;
114    let mut out = Vec::with_capacity(n);
115    for k in 0..n {
116        let conv = (a[k].0 * inv_m, a[k].1 * inv_m);
117        out.push(cmul(conv, chirps[k]));
118    }
119    Ok(out)
120}
121
122/// Forward 1D DFT (`X[k] = sum_n x[n] exp(-2*pi*i*k*n/N)`), matching `solvers::transforms::fourier::dft`.
123pub fn fft_1d(x: &[Cplx]) -> Result<Vec<Cplx>, SpectralError> {
124    if x.is_empty() {
125        return Err(SpectralError::EmptyInput);
126    }
127    validate_finite_complex(x)?;
128    if x.len().is_power_of_two() {
129        let mut out = x.to_vec();
130        fft_pow2_inplace(&mut out, -1.0);
131        Ok(out)
132    } else {
133        fft_bluestein(x, -1.0)
134    }
135}
136
137/// Inverse 1D DFT (`x[n] = (1/N) * sum_k X[k] exp(+2*pi*i*k*n/N)`), matching `solvers::transforms::fourier::idft`.
138pub fn ifft_1d(x: &[Cplx]) -> Result<Vec<Cplx>, SpectralError> {
139    if x.is_empty() {
140        return Err(SpectralError::EmptyInput);
141    }
142    validate_finite_complex(x)?;
143    let n = x.len();
144    let mut out = if n.is_power_of_two() {
145        let mut v = x.to_vec();
146        fft_pow2_inplace(&mut v, 1.0);
147        v
148    } else {
149        fft_bluestein(x, 1.0)?
150    };
151    let scale = 1.0 / n as f64;
152    for v in &mut out {
153        v.0 *= scale;
154        v.1 *= scale;
155    }
156    Ok(out)
157}
158
159pub fn fftshift_1d<T: Copy>(data: &[T], out: &mut [T]) {
160    let n = data.len();
161    if n == 0 {
162        return;
163    }
164    let split = n / 2;
165    let tail = n - split;
166    out[..tail].copy_from_slice(&data[split..]);
167    out[tail..].copy_from_slice(&data[..split]);
168}
169
170pub fn ifftshift_1d<T: Copy>(data: &[T], out: &mut [T]) {
171    let n = data.len();
172    if n == 0 {
173        return;
174    }
175    let split = n.div_ceil(2);
176    let tail = n - split;
177    out[..tail].copy_from_slice(&data[split..]);
178    out[tail..].copy_from_slice(&data[..split]);
179}
180
181pub fn fft_2d(data: &[Cplx], rows: usize, cols: usize, inverse: bool) -> Result<Vec<Cplx>, SpectralError> {
182    if rows == 0 || cols == 0 || data.len() != rows * cols {
183        return Err(SpectralError::ShapeMismatch);
184    }
185    validate_finite_complex(data)?;
186    let mut work = vec![(0.0, 0.0); rows * cols];
187    for r in 0..rows {
188        let row = &data[r * cols..(r + 1) * cols];
189        let tf = if inverse { ifft_1d(row)? } else { fft_1d(row)? };
190        work[r * cols..(r + 1) * cols].copy_from_slice(&tf);
191    }
192    let mut col_buf = vec![(0.0, 0.0); rows];
193    for c in 0..cols {
194        for r in 0..rows {
195            col_buf[r] = work[r * cols + c];
196        }
197        let tf = if inverse { ifft_1d(&col_buf)? } else { fft_1d(&col_buf)? };
198        for r in 0..rows {
199            work[r * cols + c] = tf[r];
200        }
201    }
202    Ok(work)
203}
204
205pub fn fft_3d(
206    data: &[Cplx],
207    slices: usize,
208    rows: usize,
209    cols: usize,
210    inverse: bool,
211) -> Result<Vec<Cplx>, SpectralError> {
212    let plane = rows.checked_mul(cols).ok_or(SpectralError::SizeLimit)?;
213    let total = slices.checked_mul(plane).ok_or(SpectralError::SizeLimit)?;
214    if slices == 0 || data.len() != total {
215        return Err(SpectralError::ShapeMismatch);
216    }
217    let mut work = vec![(0.0, 0.0); total];
218    for s in 0..slices {
219        let sl = fft_2d(&data[s * plane..(s + 1) * plane], rows, cols, inverse)?;
220        work[s * plane..(s + 1) * plane].copy_from_slice(&sl);
221    }
222    let mut z_buf = vec![(0.0, 0.0); slices];
223    for idx in 0..plane {
224        for s in 0..slices {
225            z_buf[s] = work[s * plane + idx];
226        }
227        let tf = if inverse { ifft_1d(&z_buf)? } else { fft_1d(&z_buf)? };
228        for s in 0..slices {
229            work[s * plane + idx] = tf[s];
230        }
231    }
232    Ok(work)
233}
234
235pub fn fftshift_3d<T: Copy + Default>(
236    data: &[T],
237    slices: usize,
238    rows: usize,
239    cols: usize,
240    inverse: bool,
241) -> Result<Vec<T>, SpectralError> {
242    let plane = rows * cols;
243    if data.len() != slices * plane {
244        return Err(SpectralError::ShapeMismatch);
245    }
246    let sz = if inverse { slices.div_ceil(2) } else { slices / 2 };
247    let sy = if inverse { rows.div_ceil(2) } else { rows / 2 };
248    let sx = if inverse { cols.div_ceil(2) } else { cols / 2 };
249    let mut out = vec![T::default(); data.len()];
250    for s in 0..slices {
251        let ds = (s + sz) % slices;
252        for r in 0..rows {
253            let dr = (r + sy) % rows;
254            for c in 0..cols {
255                let dc = (c + sx) % cols;
256                out[ds * plane + dr * cols + dc] = data[s * plane + r * cols + c];
257            }
258        }
259    }
260    Ok(out)
261}
262
263/// Exact Marple frequency-domain analytic signal envelope (`|x_a[n]| = hypot(x, H{x})`).
264pub fn analytic_hilbert_envelope_1d(signal: &[f64]) -> Result<Vec<f64>, SpectralError> {
265    if signal.is_empty() {
266        return Err(SpectralError::EmptyInput);
267    }
268    if signal.iter().any(|v| !v.is_finite()) {
269        return Err(SpectralError::NonFiniteInput);
270    }
271    let n = signal.len();
272    let cx: Vec<Cplx> = signal.iter().map(|&v| (v, 0.0)).collect();
273    let mut spec = fft_1d(&cx)?;
274    if n > 1 {
275        let half = n / 2;
276        for k in 1..half {
277            spec[k] = (spec[k].0 * 2.0, spec[k].1 * 2.0);
278        }
279        if n % 2 == 1 {
280            spec[half] = (spec[half].0 * 2.0, spec[half].1 * 2.0);
281        }
282        for k in (half + 1)..n {
283            spec[k] = (0.0, 0.0);
284        }
285    }
286    let analytic = ifft_1d(&spec)?;
287    Ok(analytic.into_iter().map(|(re, im)| re.hypot(im)).collect())
288}
289
290/// Normalized symmetric apodization window (`[0..n]`, max `1.0`).
291pub fn apodization_weight(kind: WindowKind, t_norm_abs: f64) -> f64 {
292    if t_norm_abs > 1.0 {
293        return 0.0;
294    }
295    match kind {
296        WindowKind::Boxcar => 1.0,
297        WindowKind::Hanning => 0.5 * (1.0 + (PI * t_norm_abs).cos()),
298        WindowKind::Hamming => 0.54 + 0.46 * (PI * t_norm_abs).cos(),
299    }
300}