Skip to main content

qualia_audio/features/peaks/
crosscorrelation.rs

1//! Normalised time-domain cross-correlation (caller-buffered).
2
3use crate::types::AudioError;
4
5/// Normalised cross-correlation of `a` against `b`, written into `out`.
6///
7/// `out[lag]` receives `sum_i a[i]*b[i+lag]` divided by
8/// `sqrt(energy(a) * energy(b))`, giving a correlation coefficient in
9/// `[-1, 1]`. The peak lag is the shift at which `b` best aligns with `a`: if
10/// `b` is `a` delayed by `d` samples then `out` peaks at `lag == d` with value
11/// `~1.0`. One value is written per element of `out`; lags with no overlap are
12/// written as `0.0`.
13///
14/// Cost is `O(min(|a|,|b|) * out.len())`; no allocation.
15///
16/// # Errors
17/// - [`AudioError::InvalidParameter`] if either input is empty or has no energy.
18pub fn crosscorrelation(a: &[f32], b: &[f32], out: &mut [f32]) -> Result<usize, AudioError> {
19    if a.is_empty() || b.is_empty() {
20        return Err(AudioError::InvalidParameter);
21    }
22    if out.is_empty() {
23        return Ok(0);
24    }
25    let mut ea = 0.0f64;
26    for &v in a {
27        ea += (v as f64) * (v as f64);
28    }
29    let mut eb = 0.0f64;
30    for &v in b {
31        eb += (v as f64) * (v as f64);
32    }
33    if ea == 0.0 || eb == 0.0 {
34        return Err(AudioError::InvalidParameter);
35    }
36    let norm = (ea * eb).sqrt();
37
38    let na = a.len();
39    let nb = b.len();
40    let lags = out.len();
41    for (lag, o) in out.iter_mut().enumerate() {
42        if lag >= nb {
43            *o = 0.0; // b[i+lag] out of range for every i
44            continue;
45        }
46        let upper = na.min(nb - lag); // i < na and i+lag < nb
47        let mut acc = 0.0f64;
48        for i in 0..upper {
49            acc += (a[i] as f64) * (b[i + lag] as f64);
50        }
51        *o = (acc / norm) as f32;
52    }
53    Ok(lags)
54}
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    /// Golden: `b` is `a` delayed by 2 -> cross-correlation peaks at lag 2 (~1.0).
61    #[test]
62    fn peak_at_delay() {
63        let a = [1.0f32, 2.0, 3.0, 4.0, 0.0, 0.0, 0.0, 0.0];
64        let b = [0.0f32, 0.0, 1.0, 2.0, 3.0, 4.0, 0.0, 0.0]; // a shifted right by 2
65        let mut out = [0.0f32; 8];
66        let lags = crosscorrelation(&a, &b, &mut out).expect("xcorr");
67        assert_eq!(lags, 8);
68        let mut best = 0usize;
69        for lag in 1..lags {
70            if out[lag] > out[best] {
71                best = lag;
72            }
73        }
74        assert_eq!(best, 2, "argmax lag = {best}");
75        assert!((out[2] - 1.0).abs() < 1e-5, "out[2]={}", out[2]);
76    }
77
78    /// Identical inputs correlate to 1.0 at lag 0.
79    #[test]
80    fn identical_unity_at_zero() {
81        let a = [1.0f32, -2.0, 3.0, -1.0];
82        let mut out = [0.0f32; 4];
83        crosscorrelation(&a, &a, &mut out).expect("xcorr");
84        assert!((out[0] - 1.0).abs() < 1e-6, "out0={}", out[0]);
85    }
86
87    #[test]
88    fn rejects_empty_and_silent() {
89        let mut out = [0.0f32; 4];
90        assert_eq!(
91            crosscorrelation(&[], &[1.0], &mut out),
92            Err(AudioError::InvalidParameter)
93        );
94        assert_eq!(
95            crosscorrelation(&[0.0, 0.0], &[1.0, 2.0], &mut out),
96            Err(AudioError::InvalidParameter)
97        );
98    }
99
100    #[test]
101    fn lag_beyond_b_is_zero() {
102        let a = [1.0f32, 2.0, 3.0];
103        let b = [1.0f32, 2.0];
104        let mut out = [0.0f32; 4];
105        crosscorrelation(&a, &b, &mut out).expect("xcorr");
106        assert_eq!(out[2], 0.0);
107        assert_eq!(out[3], 0.0);
108    }
109}