Skip to main content

qualia_audio/features/peaks/
autocorrelation.rs

1//! Normalised time-domain autocorrelation (caller-buffered).
2
3use crate::types::AudioError;
4
5/// Normalised autocorrelation of `x` written into `out`.
6///
7/// `out[lag]` receives the biased autocorrelation
8/// `sum_{i=0}^{N-lag-1} x[i]*x[i+lag]` divided by the zero-lag energy
9/// `sum x[i]^2`, so `out[0] == 1.0`. One value is written per element of `out`;
10/// lags `>= N` (no overlap) are written as `0.0`. For a periodic signal of
11/// period `P` the strongest lag `> 0` sits at `P` (and its multiples).
12///
13/// Cost is `O(N * out.len())` — bounded by the caller's chosen lag count; no
14/// allocation.
15///
16/// # Errors
17/// - [`AudioError::InvalidParameter`] if `x` is empty or carries no energy.
18pub fn autocorrelation(x: &[f32], out: &mut [f32]) -> Result<usize, AudioError> {
19    if x.is_empty() {
20        return Err(AudioError::InvalidParameter);
21    }
22    if out.is_empty() {
23        return Ok(0);
24    }
25    let n = x.len();
26    let mut energy = 0.0f64;
27    for &v in x {
28        energy += (v as f64) * (v as f64);
29    }
30    if energy == 0.0 {
31        return Err(AudioError::InvalidParameter);
32    }
33
34    let lags = out.len();
35    for (lag, o) in out.iter_mut().enumerate() {
36        if lag >= n {
37            *o = 0.0;
38            continue;
39        }
40        let mut acc = 0.0f64;
41        for i in 0..n - lag {
42            acc += (x[i] as f64) * (x[i + lag] as f64);
43        }
44        *o = (acc / energy) as f32;
45    }
46    Ok(lags)
47}
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    /// Golden: an impulse train of period P peaks (over lag>0) at lag P.
54    #[test]
55    fn impulse_train_period() {
56        let period = 8usize;
57        let n = 64usize;
58        let mut x = vec![0.0f32; n];
59        let mut i = 0;
60        while i < n {
61            x[i] = 1.0;
62            i += period;
63        }
64        let mut out = [0.0f32; 40];
65        let lags = autocorrelation(&x, &mut out).expect("acf");
66        assert_eq!(lags, 40);
67        assert!((out[0] - 1.0).abs() < 1e-6, "out0={}", out[0]);
68
69        // argmax over lag > 0.
70        let mut best = 1usize;
71        for lag in 2..lags {
72            if out[lag] > out[best] {
73                best = lag;
74            }
75        }
76        assert_eq!(best, period, "argmax lag = {best}");
77        // Non-multiples of the period correlate to zero.
78        assert!(out[3].abs() < 1e-6, "out3={}", out[3]);
79    }
80
81    /// A sinusoid's autocorrelation returns to a local maximum near one period.
82    #[test]
83    fn sinusoid_local_peak_at_period() {
84        let period = 32usize;
85        let n = 512usize;
86        let mut x = vec![0.0f32; n];
87        for (i, xi) in x.iter_mut().enumerate() {
88            *xi = (2.0 * std::f32::consts::PI * i as f32 / period as f32).sin();
89        }
90        let mut out = [0.0f32; 48];
91        autocorrelation(&x, &mut out).expect("acf");
92        // out[P] is a local maximum vs its neighbours and strongly positive.
93        assert!(out[period] > out[period - 1]);
94        assert!(out[period] > out[period + 1]);
95        assert!(out[period] > 0.8, "out[P]={}", out[period]);
96    }
97
98    #[test]
99    fn rejects_empty_and_silent() {
100        let mut out = [0.0f32; 4];
101        assert_eq!(
102            autocorrelation(&[], &mut out),
103            Err(AudioError::InvalidParameter)
104        );
105        assert_eq!(
106            autocorrelation(&[0.0, 0.0, 0.0], &mut out),
107            Err(AudioError::InvalidParameter)
108        );
109    }
110
111    #[test]
112    fn zero_padded_beyond_length() {
113        let x = [1.0f32, 1.0];
114        let mut out = [0.0f32; 5];
115        autocorrelation(&x, &mut out).expect("acf");
116        assert_eq!(out[2], 0.0); // lag >= N -> no overlap
117        assert_eq!(out[3], 0.0);
118    }
119}