Skip to main content

qualia_audio/features/rhythm/
tempogram.rs

1//! Autocorrelation-based tempogram: a tempo-salience curve over a BPM range,
2//! computed from an onset-strength envelope. One public function; caller
3//! supplies both the salience output and an autocorrelation scratch buffer
4//! (zero-heap — no internal allocation).
5
6use crate::features::peaks::autocorrelation;
7use crate::types::AudioError;
8
9/// Map bin `b` of an `n`-bin salience curve to its BPM.
10///
11/// Bins are spaced linearly and inclusively over `[bpm_min, bpm_max]`:
12/// `bpm(b) = bpm_min + (bpm_max - bpm_min) * b / (n - 1)` for `n > 1`, and
13/// `bpm_min` for `n == 1`.
14#[inline]
15pub fn bpm_for_bin(bin: usize, n_bins: usize, bpm_min: f32, bpm_max: f32) -> f32 {
16    if n_bins <= 1 {
17        return bpm_min;
18    }
19    bpm_min + (bpm_max - bpm_min) * (bin as f32) / ((n_bins - 1) as f32)
20}
21
22/// Linear interpolation of an autocorrelation buffer at a (possibly fractional)
23/// lag. Out-of-range lags return `0.0`.
24#[inline]
25fn acf_at(acf: &[f32], lag: f32) -> f32 {
26    if lag < 0.0 {
27        return 0.0;
28    }
29    let i = lag.floor() as usize;
30    if i + 1 >= acf.len() {
31        return 0.0;
32    }
33    let frac = lag - i as f32;
34    acf[i] * (1.0 - frac) + acf[i + 1] * frac
35}
36
37/// Compute a tempo-salience curve of `onset_env` across `[bpm_min, bpm_max]`.
38///
39/// The onset envelope's normalised autocorrelation is evaluated at the frame lag
40/// implied by each candidate tempo — a periodic beat at `bpm` recurs every
41/// `lag = frame_rate_hz * 60 / bpm` frames, so `salience[b] = acf(lag(bpm_b))`.
42/// Peaks in the returned curve mark the tempi (and their sub/harmonics) the
43/// envelope most strongly supports. Bin→BPM spacing is [`bpm_for_bin`].
44///
45/// `acf_scratch` receives the autocorrelation and must be long enough to reach
46/// the slowest tempo's lag: `len >= ceil(frame_rate_hz*60/bpm_min) + 2`. The
47/// autocorrelation is delegated to [`autocorrelation()`] (no reimplementation);
48/// nothing here allocates.
49///
50/// Returns the number of salience bins written (`= out_salience.len()`).
51///
52/// # Errors
53/// - [`AudioError::InvalidParameter`] if `onset_env` is empty, either BPM bound
54///   is non-positive, `bpm_max <= bpm_min`, `frame_rate_hz <= 0`, or
55///   `out_salience` is empty.
56/// - [`AudioError::WorkspaceTooSmall`] if `acf_scratch` cannot reach the lag for
57///   `bpm_min`.
58pub fn tempogram(
59    onset_env: &[f32],
60    frame_rate_hz: f32,
61    bpm_min: f32,
62    bpm_max: f32,
63    out_salience: &mut [f32],
64    acf_scratch: &mut [f32],
65) -> Result<usize, AudioError> {
66    if onset_env.is_empty()
67        || out_salience.is_empty()
68        || !(frame_rate_hz > 0.0)
69        || !(bpm_min > 0.0)
70        || !(bpm_max > bpm_min)
71    {
72        return Err(AudioError::InvalidParameter);
73    }
74
75    // Slowest tempo needs the longest lag; require scratch to cover it.
76    let max_lag = (frame_rate_hz * 60.0 / bpm_min).ceil() as usize + 2;
77    if acf_scratch.len() < max_lag.min(onset_env.len()) + 1 {
78        return Err(AudioError::WorkspaceTooSmall);
79    }
80
81    // Only lags we will actually sample are needed; cap at the envelope length
82    // (autocorrelation writes 0 for lags >= N anyway).
83    let want_lags = (max_lag + 1).min(acf_scratch.len());
84    let acf = &mut acf_scratch[..want_lags];
85    let lags = autocorrelation(onset_env, acf)?;
86    let acf = &acf[..lags];
87
88    let n = out_salience.len();
89    for (b, s) in out_salience.iter_mut().enumerate() {
90        let bpm = bpm_for_bin(b, n, bpm_min, bpm_max);
91        let lag = frame_rate_hz * 60.0 / bpm;
92        // Half-wave rectify: negative correlation is not tempo evidence.
93        *s = acf_at(acf, lag).max(0.0);
94    }
95    Ok(n)
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    /// Impulse train at a known frame period → salience peaks at the true tempo.
103    #[test]
104    fn peaks_at_true_tempo() {
105        // 100 Hz frame rate, beat every 50 frames -> 120 BPM.
106        let frame_rate = 100.0f32;
107        let period = 50usize;
108        let n = 1000usize;
109        let mut env = vec![0.0f32; n];
110        let mut i = 0;
111        while i < n {
112            env[i] = 1.0;
113            i += period;
114        }
115
116        let bpm_min = 40.0f32;
117        let bpm_max = 240.0f32;
118        let mut sal = [0.0f32; 201]; // 1 BPM resolution
119        let mut scratch = [0.0f32; 256];
120        let bins = tempogram(&env, frame_rate, bpm_min, bpm_max, &mut sal, &mut scratch)
121            .expect("tempogram");
122        assert_eq!(bins, 201);
123
124        // Argmax bin -> BPM.
125        let mut best = 0usize;
126        for b in 1..bins {
127            if sal[b] > sal[best] {
128                best = b;
129            }
130        }
131        let bpm = bpm_for_bin(best, bins, bpm_min, bpm_max);
132        assert!((bpm - 120.0).abs() <= 120.0 * 0.05, "peak BPM = {bpm}");
133
134        // 120 BPM (lag 50) must beat its half-tempo 60 BPM (lag 100).
135        let b60 = ((60.0 - bpm_min) / (bpm_max - bpm_min) * (bins - 1) as f32).round() as usize;
136        let b120 = ((120.0 - bpm_min) / (bpm_max - bpm_min) * (bins - 1) as f32).round() as usize;
137        assert!(
138            sal[b120] >= sal[b60],
139            "120 BPM salience {} vs 60 BPM {}",
140            sal[b120],
141            sal[b60]
142        );
143    }
144
145    #[test]
146    fn rejects_bad_params() {
147        let env = [1.0f32, 0.0, 1.0, 0.0];
148        let mut sal = [0.0f32; 4];
149        let mut scratch = [0.0f32; 64];
150        assert_eq!(
151            tempogram(&[], 100.0, 40.0, 240.0, &mut sal, &mut scratch),
152            Err(AudioError::InvalidParameter)
153        );
154        assert_eq!(
155            tempogram(&env, 0.0, 40.0, 240.0, &mut sal, &mut scratch),
156            Err(AudioError::InvalidParameter)
157        );
158        assert_eq!(
159            tempogram(&env, 100.0, 240.0, 40.0, &mut sal, &mut scratch),
160            Err(AudioError::InvalidParameter)
161        );
162    }
163
164    #[test]
165    fn scratch_too_small_errors() {
166        let env = vec![1.0f32; 200];
167        let mut sal = [0.0f32; 16];
168        // bpm_min 40 @ 100Hz -> lag 150; scratch of 8 cannot reach it.
169        let mut scratch = [0.0f32; 8];
170        assert_eq!(
171            tempogram(&env, 100.0, 40.0, 240.0, &mut sal, &mut scratch),
172            Err(AudioError::WorkspaceTooSmall)
173        );
174    }
175}