Skip to main content

qualia_audio/features/framing/
griffin_lim.rs

1//! Griffin-Lim magnitude-only reconstruction.
2//!
3//! Recovers a time-domain signal from an STFT **magnitude** target when the phase
4//! is unknown, by alternating projection (Griffin & Lim, 1984): invert the
5//! current complex estimate to the time domain (ISTFT), re-analyse it (STFT),
6//! then replace the magnitude with the target while keeping the freshly-estimated
7//! phase. Each round is non-increasing in the magnitude inconsistency.
8//!
9//! Reuses `crate::features::istft()` for the inverse and
10//! [`crate::features::fft::fft_radix2`] for the forward analysis. Zero-heap hot
11//! path: every buffer (including the evolving spectra) is caller-owned.
12
13use crate::features::fft::fft_radix2;
14use crate::features::framing::istft::istft;
15use crate::types::AudioError;
16
17/// Run `iterations` Griffin-Lim rounds and write the reconstructed time signal.
18///
19/// - `target_mags`: `num_frames × (N/2 + 1)` non-negative magnitude targets,
20///   frame `i` at `target_mags[i*(N/2+1) .. (i+1)*(N/2+1)]`.
21/// - `spectra`: `num_frames × 2N` interleaved-complex working buffer, **seeded by
22///   the caller** with an initial estimate (typically `target magnitude × e^{jφ}`
23///   for some initial phase φ, Hermitian-symmetric). Updated in place;
24///   `num_frames = spectra.len() / (2N)`.
25/// - `fft_size`: `N`, a power of two.
26/// - `hop`: sample advance between frames (`> 0`).
27/// - `iterations`: number of projection rounds (`0` just inverts the seed).
28/// - `analysis_window` / `synthesis_window`: length-`N` windows (WOLA pair).
29/// - `ifft_scratch`: `≥ N` floats (clobbered).
30/// - `norm`: `≥ out_len` floats, ISTFT normalisation scratch (clobbered).
31/// - `out`: `≥ out_len` floats; receives the reconstruction, where
32///   `out_len = (num_frames − 1)·hop + N`.
33///
34/// Returns `out_len`. Errors mirror [`istft`], plus
35/// [`AudioError::InvalidParameter`] if `target_mags.len()` does not equal
36/// `num_frames × (N/2 + 1)`.
37#[allow(clippy::too_many_arguments)]
38pub fn griffin_lim(
39    target_mags: &[f32],
40    spectra: &mut [f32],
41    fft_size: usize,
42    hop: usize,
43    iterations: usize,
44    analysis_window: &[f32],
45    synthesis_window: &[f32],
46    ifft_scratch: &mut [f32],
47    norm: &mut [f32],
48    out: &mut [f32],
49) -> Result<usize, AudioError> {
50    let n = fft_size;
51    if n == 0 || !n.is_power_of_two() || hop == 0 {
52        return Err(AudioError::InvalidParameter);
53    }
54    if analysis_window.len() != n || synthesis_window.len() != n {
55        return Err(AudioError::InvalidParameter);
56    }
57    let two_n = 2 * n;
58    if !spectra.len().is_multiple_of(two_n) {
59        return Err(AudioError::InvalidParameter);
60    }
61    let num_frames = spectra.len() / two_n;
62    if num_frames == 0 {
63        return Ok(0);
64    }
65    let bins = n / 2 + 1;
66    if target_mags.len() != num_frames * bins {
67        return Err(AudioError::InvalidParameter);
68    }
69    let out_len = (num_frames - 1)
70        .checked_mul(hop)
71        .and_then(|v| v.checked_add(n))
72        .ok_or(AudioError::InvalidParameter)?;
73    if ifft_scratch.len() < n || norm.len() < out_len || out.len() < out_len {
74        return Err(AudioError::OutputBufferTooSmall);
75    }
76
77    for _ in 0..iterations {
78        // Project onto the consistent-STFT set: invert to time.
79        istft(
80            spectra,
81            n,
82            hop,
83            analysis_window,
84            synthesis_window,
85            ifft_scratch,
86            norm,
87            out,
88        )?;
89        // Re-analyse and project onto the target-magnitude set.
90        for i in 0..num_frames {
91            let seg = &mut spectra[i * two_n..(i + 1) * two_n];
92            let base = i * hop;
93            for j in 0..n {
94                seg[2 * j] = out[base + j] * analysis_window[j];
95                seg[2 * j + 1] = 0.0;
96            }
97            fft_radix2(seg, false)?;
98            impose_magnitude(seg, &target_mags[i * bins..(i + 1) * bins], n);
99        }
100    }
101
102    // Final inversion of the magnitude-consistent estimate.
103    istft(
104        spectra,
105        n,
106        hop,
107        analysis_window,
108        synthesis_window,
109        ifft_scratch,
110        norm,
111        out,
112    )?;
113    Ok(out_len)
114}
115
116/// Replace the magnitude of the half-spectrum `0..=N/2` of `seg` (interleaved
117/// complex, length `2N`) with `target`, keeping each bin's phase, then restore
118/// Hermitian symmetry so the inverse transform is real. DC and Nyquist are made
119/// purely real.
120fn impose_magnitude(seg: &mut [f32], target: &[f32], n: usize) {
121    const EPS: f32 = 1e-12;
122    let half = n / 2;
123    for k in 0..=half {
124        let re = seg[2 * k];
125        let im = seg[2 * k + 1];
126        let mag = (re * re + im * im).sqrt();
127        let (nr, ni) = if mag > EPS {
128            let s = target[k] / mag;
129            (re * s, im * s)
130        } else {
131            // No phase information: assume zero phase at the target magnitude.
132            (target[k], 0.0)
133        };
134        seg[2 * k] = nr;
135        seg[2 * k + 1] = ni;
136    }
137    // DC and Nyquist are real for a real signal.
138    seg[1] = 0.0;
139    seg[2 * half + 1] = 0.0;
140    // Hermitian mirror: X[N-k] = conj(X[k]) for k in 1..N/2.
141    for k in 1..half {
142        seg[2 * (n - k)] = seg[2 * k];
143        seg[2 * (n - k) + 1] = -seg[2 * k + 1];
144    }
145}
146
147#[cfg(test)]
148mod tests {
149    use super::*;
150    use crate::features::fft::real_fft_magnitude;
151    use crate::features::framing::frame_cutter::frame_count;
152    use crate::features::window::hann_window;
153    use core::f32::consts::{PI, TAU};
154
155    /// Deterministic LCG in [0, 1) — reproducible "random" phase seed.
156    struct Lcg(u64);
157    impl Lcg {
158        fn next_f32(&mut self) -> f32 {
159            self.0 = self
160                .0
161                .wrapping_mul(6364136223846793005)
162                .wrapping_add(1442695040888963407);
163            ((self.0 >> 40) as f32) / ((1u64 << 24) as f32)
164        }
165    }
166
167    fn analyse_mags(signal: &[f32], n: usize, hop: usize, window: &[f32]) -> (Vec<f32>, usize) {
168        let frames = frame_count(signal.len(), n, hop);
169        let bins = n / 2 + 1;
170        let mut mags = vec![0.0f32; frames * bins];
171        let mut frame = vec![0.0f32; n];
172        let mut scratch = vec![0.0f32; 2 * n];
173        for i in 0..frames {
174            for j in 0..n {
175                frame[j] = signal[i * hop + j] * window[j];
176            }
177            real_fft_magnitude(&frame, &mut scratch, &mut mags[i * bins..(i + 1) * bins]).unwrap();
178        }
179        (mags, frames)
180    }
181
182    /// Total absolute STFT-magnitude error of `signal` against `target` mags.
183    fn magnitude_error(
184        signal: &[f32],
185        target: &[f32],
186        n: usize,
187        hop: usize,
188        window: &[f32],
189    ) -> f64 {
190        let (got, _) = analyse_mags(signal, n, hop, window);
191        got.iter()
192            .zip(target.iter())
193            .map(|(a, b)| (a - b).abs() as f64)
194            .sum()
195    }
196
197    /// Build a Hermitian interleaved-complex seed = target magnitude × e^{jφ}.
198    fn seed_random_phase(target: &[f32], n: usize, frames: usize, rng: &mut Lcg) -> Vec<f32> {
199        let bins = n / 2 + 1;
200        let two_n = 2 * n;
201        let half = n / 2;
202        let mut spectra = vec![0.0f32; frames * two_n];
203        for i in 0..frames {
204            let seg = &mut spectra[i * two_n..(i + 1) * two_n];
205            let mags = &target[i * bins..(i + 1) * bins];
206            for k in 0..=half {
207                let phi = (rng.next_f32() * 2.0 - 1.0) * PI;
208                seg[2 * k] = mags[k] * phi.cos();
209                seg[2 * k + 1] = mags[k] * phi.sin();
210            }
211            seg[1] = 0.0;
212            seg[2 * half + 1] = 0.0;
213            for k in 1..half {
214                seg[2 * (n - k)] = seg[2 * k];
215                seg[2 * (n - k) + 1] = -seg[2 * k + 1];
216            }
217        }
218        spectra
219    }
220
221    #[test]
222    fn griffin_lim_reduces_magnitude_error() {
223        // GOLDEN: from a random-phase start, more Griffin-Lim iterations lower the
224        // STFT-magnitude inconsistency of the reconstruction against the target.
225        let n = 256usize;
226        let hop = n / 4; // 75% overlap — good conditioning for GL.
227        let len = 4096usize;
228        let fs = 16_000.0f32;
229        let signal: Vec<f32> = (0..len)
230            .map(|i| {
231                let t = i as f32 / fs;
232                0.5 * (TAU * 300.0 * t).sin() + 0.3 * (TAU * 900.0 * t).sin()
233            })
234            .collect();
235
236        let mut window = vec![0.0f32; n];
237        hann_window(&mut window).unwrap();
238        let (target, frames) = analyse_mags(&signal, n, hop, &window);
239        let out_len = (frames - 1) * hop + n;
240
241        // Same random-phase seed for both runs.
242        let mut rng = Lcg(0x1234_5678_9abc_def0);
243        let seed = seed_random_phase(&target, n, frames, &mut rng);
244
245        let run = |iters: usize| -> Vec<f32> {
246            let mut spectra = seed.clone();
247            let mut ifft_scratch = vec![0.0f32; n];
248            let mut norm = vec![0.0f32; out_len];
249            let mut out = vec![0.0f32; out_len];
250            griffin_lim(
251                &target,
252                &mut spectra,
253                n,
254                hop,
255                iters,
256                &window,
257                &window,
258                &mut ifft_scratch,
259                &mut norm,
260                &mut out,
261            )
262            .unwrap();
263            out
264        };
265
266        let out1 = run(1);
267        let out40 = run(40);
268        let e1 = magnitude_error(&out1, &target, n, hop, &window);
269        let e40 = magnitude_error(&out40, &target, n, hop, &window);
270
271        assert!(e40 < e1, "Griffin-Lim did not improve: e1={e1}, e40={e40}");
272        // Substantial, not marginal, improvement expected on a clean two-tone.
273        assert!(e40 < e1 * 0.9, "improvement too small: e1={e1}, e40={e40}");
274    }
275
276    #[test]
277    fn rejects_mismatched_target_len() {
278        let n = 8usize;
279        let mut spectra = vec![0.0f32; 2 * 2 * n]; // 2 frames
280        let target = vec![0.0f32; 2 * (n / 2 + 1) - 1]; // wrong length
281        let w = vec![0.0f32; n];
282        let mut sc = vec![0.0f32; n];
283        let out_len = hop_out_len(2, 4, n);
284        let mut nm = vec![0.0f32; out_len];
285        let mut out = vec![0.0f32; out_len];
286        assert_eq!(
287            griffin_lim(
288                &target,
289                &mut spectra,
290                n,
291                4,
292                5,
293                &w,
294                &w,
295                &mut sc,
296                &mut nm,
297                &mut out
298            ),
299            Err(AudioError::InvalidParameter)
300        );
301    }
302
303    fn hop_out_len(frames: usize, hop: usize, n: usize) -> usize {
304        (frames - 1) * hop + n
305    }
306}