Skip to main content

qualia_audio/features/rhythm/
bpm_histogram.rs

1//! Histogram of inter-beat-interval tempi → dominant and secondary BPM. One
2//! public function; caller supplies the histogram bins (zero-heap, no internal
3//! allocation).
4
5use crate::types::AudioError;
6
7/// Minimum bin separation between the dominant and secondary peaks, so the two
8/// reported tempi are distinct modes rather than two bins of one peak.
9const MIN_PEAK_SEP: usize = 2;
10
11/// BPM at the centre of histogram bin `b` (of `n` bins over `[bpm_min, bpm_max]`).
12#[inline]
13fn bin_center_bpm(b: usize, n_bins: usize, bpm_min: f32, bpm_max: f32) -> f32 {
14    bpm_min + (b as f32 + 0.5) / (n_bins as f32) * (bpm_max - bpm_min)
15}
16
17/// Build a BPM histogram from beat frame indices and report the dominant and
18/// secondary tempi.
19///
20/// Each adjacent beat pair contributes one inter-beat interval `d = beat[i+1] -
21/// beat[i]` frames, an instantaneous tempo `bpm = frame_rate_hz*60/d`. Tempi
22/// inside `[bpm_min, bpm_max]` are binned into `out_hist` (linearly, `out_hist`
23/// spanning the whole range). The **dominant** tempo is the most-populated bin;
24/// the **secondary** tempo is the most-populated bin at least `MIN_PEAK_SEP`
25/// bins away from the dominant (a distinct mode, e.g. a half/double-time
26/// alias), or `0.0` if there is no such bin. Both are returned as bin-centre
27/// BPMs.
28///
29/// Returns `(dominant_bpm, secondary_bpm)`.
30///
31/// # Errors
32/// - [`AudioError::InvalidParameter`] if fewer than two beats, `out_hist` is
33///   empty, `frame_rate_hz <= 0`, either bound is non-positive, or
34///   `bpm_max <= bpm_min`.
35pub fn bpm_histogram(
36    beat_frames: &[u32],
37    frame_rate_hz: f32,
38    bpm_min: f32,
39    bpm_max: f32,
40    out_hist: &mut [u32],
41) -> Result<(f32, f32), AudioError> {
42    let n_bins = out_hist.len();
43    if beat_frames.len() < 2
44        || n_bins == 0
45        || !(frame_rate_hz > 0.0)
46        || !(bpm_min > 0.0)
47        || !(bpm_max > bpm_min)
48    {
49        return Err(AudioError::InvalidParameter);
50    }
51
52    for h in out_hist.iter_mut() {
53        *h = 0;
54    }
55
56    let span = bpm_max - bpm_min;
57    let mut counted = 0u32;
58    for pair in beat_frames.windows(2) {
59        // Guard against non-monotone / duplicate beats.
60        let d = pair[1].saturating_sub(pair[0]);
61        if d == 0 {
62            continue;
63        }
64        let bpm = frame_rate_hz * 60.0 / d as f32;
65        if bpm < bpm_min || bpm > bpm_max {
66            continue;
67        }
68        let mut bin = ((bpm - bpm_min) / span * n_bins as f32) as usize;
69        if bin >= n_bins {
70            bin = n_bins - 1; // bpm == bpm_max lands in the last bin
71        }
72        out_hist[bin] += 1;
73        counted += 1;
74    }
75
76    if counted == 0 {
77        // Beats exist but every interval fell outside the tempo range.
78        return Err(AudioError::InvalidParameter);
79    }
80
81    // Dominant = most populated bin.
82    let mut dom = 0usize;
83    for b in 1..n_bins {
84        if out_hist[b] > out_hist[dom] {
85            dom = b;
86        }
87    }
88
89    // Secondary = most populated bin at least MIN_PEAK_SEP away from dominant.
90    let mut sec: Option<usize> = None;
91    for b in 0..n_bins {
92        if out_hist[b] == 0 {
93            continue;
94        }
95        let far = b.abs_diff(dom) >= MIN_PEAK_SEP;
96        if !far {
97            continue;
98        }
99        match sec {
100            Some(s) if out_hist[b] <= out_hist[s] => {}
101            _ => sec = Some(b),
102        }
103    }
104
105    let dominant_bpm = bin_center_bpm(dom, n_bins, bpm_min, bpm_max);
106    let secondary_bpm = match sec {
107        Some(s) => bin_center_bpm(s, n_bins, bpm_min, bpm_max),
108        None => 0.0,
109    };
110    Ok((dominant_bpm, secondary_bpm))
111}
112
113#[cfg(test)]
114mod tests {
115    use super::*;
116
117    /// Steady 120 BPM beats @ 100 Hz -> dominant ~120, no secondary.
118    #[test]
119    fn steady_tempo_dominant() {
120        let frame_rate = 100.0f32;
121        // Beats every 50 frames -> 120 BPM.
122        let beats: Vec<u32> = (0..20).map(|k| (k * 50) as u32).collect();
123        let mut hist = [0u32; 200]; // 40..240, 1 BPM/bin
124        let (dom, sec) = bpm_histogram(&beats, frame_rate, 40.0, 240.0, &mut hist).expect("hist");
125        assert!((dom - 120.0).abs() <= 120.0 * 0.05, "dominant = {dom}");
126        assert_eq!(sec, 0.0, "no secondary expected, got {sec}");
127    }
128
129    /// Two interleaved intervals (mostly 120 BPM, some 60 BPM) -> dominant 120,
130    /// secondary 60.
131    #[test]
132    fn bimodal_dominant_and_secondary() {
133        let frame_rate = 100.0f32;
134        // Intervals in frames: 50 (120 BPM) x many, 100 (60 BPM) x few.
135        let intervals = [50u32, 50, 50, 50, 100, 50, 50, 100, 50, 50];
136        let mut beats = vec![0u32];
137        let mut acc = 0u32;
138        for d in intervals {
139            acc += d;
140            beats.push(acc);
141        }
142        let mut hist = [0u32; 200];
143        let (dom, sec) = bpm_histogram(&beats, frame_rate, 40.0, 240.0, &mut hist).expect("hist");
144        assert!((dom - 120.0).abs() <= 120.0 * 0.05, "dominant = {dom}");
145        assert!((sec - 60.0).abs() <= 60.0 * 0.05, "secondary = {sec}");
146    }
147
148    #[test]
149    fn rejects_insufficient_beats() {
150        let mut hist = [0u32; 32];
151        assert_eq!(
152            bpm_histogram(&[10], 100.0, 40.0, 240.0, &mut hist),
153            Err(AudioError::InvalidParameter)
154        );
155    }
156
157    #[test]
158    fn out_of_range_intervals_error() {
159        // Beats 1 frame apart @ 100 Hz -> 6000 BPM, outside 40..240.
160        let beats = [0u32, 1, 2, 3];
161        let mut hist = [0u32; 32];
162        assert_eq!(
163            bpm_histogram(&beats, 100.0, 40.0, 240.0, &mut hist),
164            Err(AudioError::InvalidParameter)
165        );
166    }
167
168    #[test]
169    fn non_monotone_beats_skipped() {
170        // A duplicate/backward beat must not panic or mis-bin.
171        let beats = [0u32, 50, 50, 100, 150];
172        let mut hist = [0u32; 200];
173        let (dom, _sec) = bpm_histogram(&beats, 100.0, 40.0, 240.0, &mut hist).expect("hist");
174        assert!((dom - 120.0).abs() <= 120.0 * 0.05, "dominant = {dom}");
175    }
176}