Skip to main content

qualia_audio/features/rhythm/
beat_tracker.rs

1//! Global-tempo estimation and beat placement from an onset-strength envelope.
2//! Estimates BPM from the autocorrelation tempogram (peak-picked with
3//! [`detect_peaks`]) and places beats with a comb-filter phase search. One
4//! public function; the only working state is bounded fixed-size stack scratch.
5
6use crate::features::peaks::detect_peaks;
7use crate::features::rhythm::tempogram::tempogram;
8use crate::types::AudioError;
9
10/// Tempo search range (BPM). Covers the musically common band; the low bound is
11/// raised automatically when the frame rate would need a lag beyond `ACF_CAP`.
12const BPM_MIN: f32 = 40.0;
13const BPM_MAX: f32 = 240.0;
14/// Salience bins over `[BPM_MIN, BPM_MAX]` → 1 BPM resolution.
15const SAL_BINS: usize = 201;
16/// Autocorrelation lag ceiling (frames). Bounds stack scratch to 16 KiB.
17const ACF_CAP: usize = 4096;
18/// Peak-list capacity: 201 samples admit at most 100 local maxima.
19const MAX_PEAKS: usize = 101;
20
21/// Estimate global tempo and place beat frames for `onset_env`.
22///
23/// `onset_env` is a per-frame onset-strength curve (e.g. the spectral-flux
24/// novelty behind [`super::spectral_flux_onset::onset_detection`]); `frame_rate_hz`
25/// is its sampling rate (`sample_rate / hop`). The tempo is the dominant peak of
26/// the autocorrelation [`tempogram`] (highest-salience [`detect_peaks`] maximum,
27/// falling back to the salience argmax). Given the beat period
28/// `P = frame_rate_hz*60/bpm` frames, a comb filter scores every integer phase
29/// offset `o ∈ [0, round(P))` by the summed onset strength at
30/// `o, o+P, o+2P, …` and keeps the best; beats are then laid at that phase and
31/// period and written (as frame indices) to `out_beat_frames`.
32///
33/// If the frame rate is so high that `BPM_MIN`'s lag exceeds `ACF_CAP`, the
34/// effective low bound is raised to keep the lag in range (documented, not
35/// silent failure — the returned BPM reflects the searched band).
36///
37/// Returns `(n_beats, bpm)`.
38///
39/// # Errors
40/// - [`AudioError::InvalidParameter`] if `onset_env` is empty, `frame_rate_hz`
41///   is non-positive, or the frame rate is so extreme the search band collapses.
42/// - [`AudioError::OutputBufferTooSmall`] if more beats are found than
43///   `out_beat_frames` can hold.
44pub fn track_beats(
45    onset_env: &[f32],
46    frame_rate_hz: f32,
47    out_beat_frames: &mut [u32],
48) -> Result<(usize, f32), AudioError> {
49    if onset_env.is_empty() || !(frame_rate_hz > 0.0) {
50        return Err(AudioError::InvalidParameter);
51    }
52
53    // Keep the slowest-tempo lag within the stack scratch.
54    let eff_bpm_min = BPM_MIN.max(frame_rate_hz * 60.0 / ((ACF_CAP - 2) as f32));
55    if !(eff_bpm_min < BPM_MAX) {
56        return Err(AudioError::InvalidParameter);
57    }
58
59    let mut sal = [0.0f32; SAL_BINS];
60    let mut scratch = [0.0f32; ACF_CAP];
61    let bins = tempogram(
62        onset_env,
63        frame_rate_hz,
64        eff_bpm_min,
65        BPM_MAX,
66        &mut sal,
67        &mut scratch,
68    )?;
69
70    // Dominant tempo: strongest local maximum of the salience curve.
71    let mut pos = [0.0f32; MAX_PEAKS];
72    let mut mag = [0.0f32; MAX_PEAKS];
73    let peak_bin = match detect_peaks(&sal[..bins], 0.0, 2, &mut pos, &mut mag) {
74        Ok(np) if np > 0 => {
75            let mut best = 0usize;
76            for k in 1..np {
77                if mag[k] > mag[best] {
78                    best = k;
79                }
80            }
81            pos[best]
82        }
83        // No clean peak (or overflow) → fall back to the salience argmax.
84        _ => {
85            let mut best = 0usize;
86            for b in 1..bins {
87                if sal[b] > sal[best] {
88                    best = b;
89                }
90            }
91            best as f32
92        }
93    };
94
95    let bpm = if bins > 1 {
96        eff_bpm_min + (BPM_MAX - eff_bpm_min) * peak_bin / ((bins - 1) as f32)
97    } else {
98        eff_bpm_min
99    };
100    if !(bpm > 0.0) {
101        return Err(AudioError::InvalidParameter);
102    }
103
104    let period = frame_rate_hz * 60.0 / bpm;
105    let n_beats = place_beats(onset_env, period, out_beat_frames)?;
106    Ok((n_beats, bpm))
107}
108
109/// Comb-filter phase alignment + beat emission. Chooses the integer phase offset
110/// maximising summed onset strength on the pulse grid, then writes beat frame
111/// indices spaced by `period`.
112fn place_beats(onset_env: &[f32], period: f32, out: &mut [u32]) -> Result<usize, AudioError> {
113    let len = onset_env.len();
114    let step = period.max(1.0);
115    let p_round = (step.round() as usize).max(1);
116
117    // Best phase offset in [0, p_round).
118    let mut best_off = 0usize;
119    let mut best_score = f32::NEG_INFINITY;
120    for off in 0..p_round {
121        let mut score = 0.0f32;
122        let mut p = off as f32;
123        loop {
124            let idx = p.round() as usize;
125            if idx >= len {
126                break;
127            }
128            score += onset_env[idx];
129            p += step;
130        }
131        if score > best_score {
132            best_score = score;
133            best_off = off;
134        }
135    }
136
137    // Emit beats at the chosen phase and period.
138    let mut w = 0usize;
139    let mut p = best_off as f32;
140    loop {
141        let idx = p.round() as usize;
142        if idx >= len {
143            break;
144        }
145        if w == out.len() {
146            return Err(AudioError::OutputBufferTooSmall);
147        }
148        out[w] = idx as u32;
149        w += 1;
150        p += step;
151    }
152    Ok(w)
153}
154
155#[cfg(test)]
156mod tests {
157    use super::*;
158
159    /// Impulse train onset envelope at a known BPM.
160    fn click_train(n: usize, period: usize) -> Vec<f32> {
161        let mut env = vec![0.0f32; n];
162        let mut i = 0;
163        while i < n {
164            env[i] = 1.0;
165            i += period;
166        }
167        env
168    }
169
170    /// GOLDEN: 120 BPM click train @ 100 Hz frame rate -> recover ~120 BPM.
171    #[test]
172    fn recovers_120_bpm() {
173        let frame_rate = 100.0f32; // 100 frames/s
174        let period = 50usize; // 0.5 s -> 120 BPM
175        let env = click_train(1000, period);
176        let mut beats = [0u32; 64];
177        let (n_beats, bpm) = track_beats(&env, frame_rate, &mut beats).expect("track");
178        assert!(
179            (bpm - 120.0).abs() <= 120.0 * 0.05,
180            "bpm = {bpm} (want ~120)"
181        );
182        // 1000 frames / 50 -> 20 beats.
183        assert_eq!(n_beats, 20, "n_beats = {n_beats}");
184        // Beats land on the click grid.
185        assert_eq!(beats[0], 0);
186        assert_eq!(beats[1], 50);
187        assert_eq!(beats[2], 100);
188    }
189
190    /// A second tempo to prove it is not hard-wired to 120.
191    #[test]
192    fn recovers_100_bpm() {
193        let frame_rate = 100.0f32;
194        let period = 60usize; // 0.6 s -> 100 BPM
195        let env = click_train(1200, period);
196        let mut beats = [0u32; 64];
197        let (_n, bpm) = track_beats(&env, frame_rate, &mut beats).expect("track");
198        assert!(
199            (bpm - 100.0).abs() <= 100.0 * 0.05,
200            "bpm = {bpm} (want ~100)"
201        );
202    }
203
204    /// Beats sit near real onsets even with an off-grid starting phase.
205    #[test]
206    fn phase_locks_to_offset_onsets() {
207        let frame_rate = 100.0f32;
208        let period = 50usize;
209        // First click at frame 17, then every 50.
210        let mut env = vec![0.0f32; 1000];
211        let mut i = 17usize;
212        while i < 1000 {
213            env[i] = 1.0;
214            i += period;
215        }
216        let mut beats = [0u32; 64];
217        let (n_beats, bpm) = track_beats(&env, frame_rate, &mut beats).expect("track");
218        assert!((bpm - 120.0).abs() <= 120.0 * 0.05, "bpm = {bpm}");
219        assert!(n_beats > 0);
220        assert_eq!(beats[0], 17, "first beat phase = {}", beats[0]);
221    }
222
223    #[test]
224    fn rejects_bad_input() {
225        let mut beats = [0u32; 8];
226        assert_eq!(
227            track_beats(&[], 100.0, &mut beats),
228            Err(AudioError::InvalidParameter)
229        );
230        let env = [1.0f32, 0.0, 1.0];
231        assert_eq!(
232            track_beats(&env, 0.0, &mut beats),
233            Err(AudioError::InvalidParameter)
234        );
235    }
236
237    #[test]
238    fn beat_buffer_too_small_errors() {
239        let env = click_train(1000, 50);
240        let mut beats = [0u32; 4]; // 20 beats will not fit
241        assert_eq!(
242            track_beats(&env, 100.0, &mut beats),
243            Err(AudioError::OutputBufferTooSmall)
244        );
245    }
246
247    #[test]
248    fn silence_bounds_gracefully() {
249        // Flat non-zero envelope: autocorrelation exists but carries no clear
250        // period; must still return a valid (n_beats, bpm) without panicking.
251        let env = vec![1.0f32; 500];
252        let mut beats = [0u32; 512];
253        let res = track_beats(&env, 100.0, &mut beats);
254        assert!(res.is_ok());
255        let (_n, bpm) = res.expect("ok");
256        assert!(bpm >= BPM_MIN && bpm <= BPM_MAX, "bpm = {bpm}");
257    }
258}