sound_to_patch/music/
rhythm.rs

1//! Rhythm arithmetic: Euclidean patterns, swing and ticks.
2//!
3//! A bar has 16 sixteenth slots, numbered 0 to 15. Ticks count 480 per
4//! quarter note, as in the MIDI files the tool writes.
5//!
6//! ```
7//! use sound_to_patch::music::rhythm::{euclid, onsets, ticks_for_ms};
8//!
9//! assert_eq!(onsets(&euclid(3, 8)), [0, 3, 6]);
10//! assert_eq!(ticks_for_ms(5.0, 120.0), Some(5));
11//! ```
12
13use crate::audio::{self, BeatGrid, Feel, NoteValue};
14use crate::cast;
15use crate::notes::{TICKS_PER_BEAT, ticks_per_second};
16use crate::units::{Bpm, Seconds};
17
18/// The Euclidean pattern of `k` onsets over `n` steps.
19///
20/// The grouping algorithm: start with `k` groups `1` and `n - k` groups `0`, pair each
21/// leading group with one trailing group, keep the unpaired ones as the
22/// remainder, and repeat on the pairs and the remainder until at most one
23/// remainder group is left. At least one pairing step runs. `k` above `n`
24/// is cut to `n`.
25#[must_use]
26pub fn euclid(k: usize, n: usize) -> Vec<bool> {
27    let k = k.min(n);
28    if k == 0 || k == n {
29        return vec![k == n; n];
30    }
31    let mut leading: Vec<Vec<bool>> = vec![vec![true]; k];
32    let mut trailing: Vec<Vec<bool>> = vec![vec![false]; n - k];
33    loop {
34        let pairs = leading.len().min(trailing.len());
35        let remainder = if leading.len() > pairs {
36            leading.split_off(pairs)
37        } else {
38            trailing.split_off(pairs)
39        };
40        for (group, tail) in leading.iter_mut().zip(&trailing) {
41            group.extend(tail);
42        }
43        trailing = remainder;
44        if trailing.len() <= 1 {
45            break;
46        }
47    }
48    leading.into_iter().chain(trailing).flatten().collect()
49}
50
51/// The steps that hold an onset.
52#[must_use]
53pub fn onsets(pattern: &[bool]) -> Vec<usize> {
54    pattern
55        .iter()
56        .enumerate()
57        .filter_map(|(step, onset)| onset.then_some(step))
58        .collect()
59}
60
61/// The pattern with every onset moved `rotation` steps later, wrapping
62/// around.
63#[must_use]
64pub fn rotate(pattern: &[bool], rotation: usize) -> Vec<bool> {
65    let mut turned = pattern.to_vec();
66    if let Some(steps) = rotation.checked_rem(turned.len()) {
67        turned.rotate_right(steps);
68    }
69    turned
70}
71
72/// The delay of the second note of a swung pair, in sixteenths, for a pair
73/// percent `pct` (50 is straight) and a pair of sixteenths.
74///
75/// Returns `None` where the delay is negative or not finite: for a pair
76/// percent below 50, an infinity or NaN.
77#[must_use]
78pub fn swing_delay(pct: f64) -> Option<f64> {
79    non_negative((pct / 100.0 - 0.5) * 2.0)
80}
81
82/// The long-to-short ratio of a pair percent.
83///
84/// Returns `None` where the ratio is negative or not finite: for a pair
85/// percent below 0, of 100 or more, or NaN.
86#[must_use]
87pub fn swing_ratio(pct: f64) -> Option<f64> {
88    non_negative(pct / (100.0 - pct))
89}
90
91/// The pair percent of a long-to-short ratio.
92///
93/// Returns `None` for a negative ratio, which no pair has, and where the
94/// percent is not finite: for an infinity or NaN.
95#[must_use]
96pub fn swing_pct(ratio: f64) -> Option<f64> {
97    if ratio < 0.0 {
98        return None;
99    }
100    // Dividing first keeps a huge ratio finite: `100 * ratio` overflows
101    // from about 1.8e306.
102    non_negative(ratio / (ratio + 1.0) * 100.0)
103}
104
105/// The two notes of a swung pair.
106#[derive(Clone, Copy, Debug, PartialEq, Eq)]
107pub enum Pair {
108    /// A pair of sixteenths, 240 ticks.
109    Sixteenths,
110    /// A pair of eighths, 480 ticks.
111    Eighths,
112}
113
114impl Pair {
115    /// The length of the pair in ticks.
116    fn ticks(self) -> u32 {
117        let note = match self {
118            Self::Sixteenths => Division::Sixteenth,
119            Self::Eighths => Division::Eighth,
120        };
121        2 * note.ticks()
122    }
123}
124
125/// The delay of the second note of a swung pair in ticks.
126///
127/// Returns `None` where the delay is negative or not finite: for a pair
128/// percent below 50, an infinity or NaN.
129#[must_use]
130pub fn swing_ticks(pct: f64, pair: Pair) -> Option<f64> {
131    non_negative((pct / 100.0 - 0.5) * f64::from(pair.ticks()))
132}
133
134/// The length of one tick in ms, `1000 / ticks per second`, the tick the
135/// MIDI writer uses.
136///
137/// Returns `None` for a tempo outside the 4 to 1000 BPM of [`Bpm`].
138#[must_use]
139pub fn tick_ms(bpm: f64) -> Option<f64> {
140    let bpm = Bpm::new(bpm).ok()?;
141    Some(1000.0 / ticks_per_second(bpm))
142}
143
144/// The length of a sixteenth in ms: a quarter of the beat period of the
145/// stem's beat grid.
146///
147/// Returns `None` for a tempo outside the 4 to 1000 BPM of [`Bpm`].
148#[must_use]
149pub fn sixteenth_ms(bpm: f64) -> Option<f64> {
150    let grid = BeatGrid::new(Bpm::new(bpm).ok()?, Seconds::from_const(0.0));
151    Some(grid.beat_period().get() / 4.0 * 1000.0)
152}
153
154/// `value` when it is finite and not negative, with `-0.0` stored as
155/// `+0.0`.
156fn non_negative(value: f64) -> Option<f64> {
157    (value.is_finite() && value >= 0.0).then_some(value + 0.0)
158}
159
160/// The whole ticks that cover `ms` at a tempo, rounded up, so an overlap
161/// is never shorter than asked.
162///
163/// Returns `None` for a tempo outside the 4 to 1000 BPM of [`Bpm`], a
164/// length that is NaN or negative, or a tick count beyond `u32`.
165#[must_use]
166pub fn ticks_for_ms(ms: f64, bpm: f64) -> Option<u32> {
167    let tick = tick_ms(bpm)?;
168    if ms.is_nan() || ms < 0.0 {
169        return None;
170    }
171    // The nanotick margin keeps a length of exactly n ticks at n.
172    let ticks = cast::ceil_to_usize((ms / tick - 1e-9).max(0.0))?;
173    u32::try_from(ticks).ok()
174}
175
176/// A note division and its length in ticks.
177#[derive(Clone, Copy, Debug, PartialEq, Eq)]
178pub enum Division {
179    /// A thirty-second note.
180    ThirtySecond,
181    /// A sixteenth note.
182    Sixteenth,
183    /// A sixteenth-note triplet.
184    SixteenthTriplet,
185    /// An eighth note.
186    Eighth,
187    /// An eighth-note triplet.
188    EighthTriplet,
189    /// A dotted eighth note.
190    DottedEighth,
191    /// A quarter-note triplet.
192    QuarterTriplet,
193    /// A quarter note.
194    Quarter,
195    /// A dotted quarter note.
196    DottedQuarter,
197    /// A bar of 4/4.
198    Bar,
199}
200
201impl Division {
202    /// Every division, shortest first.
203    pub const ALL: [Self; 10] = [
204        Self::ThirtySecond,
205        Self::SixteenthTriplet,
206        Self::Sixteenth,
207        Self::EighthTriplet,
208        Self::Eighth,
209        Self::QuarterTriplet,
210        Self::DottedEighth,
211        Self::Quarter,
212        Self::DottedQuarter,
213        Self::Bar,
214    ];
215
216    /// The division of the stem analysis with the same length. This list
217    /// is the dictionary's named subset of [`audio::Division::ALL`], which
218    /// holds the lengths.
219    fn division(self) -> audio::Division {
220        let (value, feel) = match self {
221            Self::ThirtySecond => (NoteValue::ThirtySecond, Feel::Straight),
222            Self::Sixteenth => (NoteValue::Sixteenth, Feel::Straight),
223            Self::SixteenthTriplet => (NoteValue::Sixteenth, Feel::Triplet),
224            Self::Eighth => (NoteValue::Eighth, Feel::Straight),
225            Self::EighthTriplet => (NoteValue::Eighth, Feel::Triplet),
226            Self::DottedEighth => (NoteValue::Eighth, Feel::Dotted),
227            Self::QuarterTriplet => (NoteValue::Quarter, Feel::Triplet),
228            Self::Quarter => (NoteValue::Quarter, Feel::Straight),
229            Self::DottedQuarter => (NoteValue::Quarter, Feel::Dotted),
230            Self::Bar => (NoteValue::Whole, Feel::Straight),
231        };
232        audio::Division { value, feel }
233    }
234
235    /// The length in ticks at 480 per quarter: the beats of the same
236    /// division in [`audio::Division::ALL`] times 480.
237    #[must_use]
238    pub fn ticks(self) -> u32 {
239        // Every division here lasts a whole number of ticks, and the
240        // product is exact for each, as the tests pin; the fallback is
241        // never taken.
242        let ticks = self.division().beats_per_cycle() * f64::from(TICKS_PER_BEAT);
243        cast::round_to_usize(ticks)
244            .and_then(|ticks| u32::try_from(ticks).ok())
245            .unwrap_or(u32::MAX)
246    }
247
248    /// The name for people.
249    #[must_use]
250    pub fn name(self) -> &'static str {
251        match self {
252            Self::ThirtySecond => "1/32",
253            Self::Sixteenth => "1/16",
254            Self::SixteenthTriplet => "1/16T",
255            Self::Eighth => "1/8",
256            Self::EighthTriplet => "1/8T",
257            Self::DottedEighth => "dotted 1/8",
258            Self::QuarterTriplet => "1/4T",
259            Self::Quarter => "1/4",
260            Self::DottedQuarter => "dotted 1/4",
261            Self::Bar => "bar",
262        }
263    }
264}
265
266/// The ticks of one slot of a bar of `grid` slots: 12, 16 or 24 slots give
267/// 160, 120 or 80 ticks.
268///
269/// Returns `None` for 0 slots and for a grid whose slots do not last a
270/// whole number of ticks, such as 7.
271#[must_use]
272pub fn slot_ticks(grid: u8) -> Option<u32> {
273    let bar = Division::Bar.ticks();
274    let grid = u32::from(grid);
275    (bar.checked_rem(grid)? == 0).then(|| bar / grid)
276}
277
278#[cfg(test)]
279mod tests {
280    use super::*;
281
282    /// The 20 patterns printed in the source paper, as onset steps.
283    const PRINTED: [(usize, usize, &[usize]); 20] = [
284        (2, 5, &[0, 2]),
285        (3, 4, &[0, 2, 3]),
286        (3, 5, &[0, 2, 4]),
287        (3, 7, &[0, 2, 4]),
288        (3, 8, &[0, 3, 6]),
289        (4, 7, &[0, 2, 4, 6]),
290        (4, 9, &[0, 2, 4, 6]),
291        (4, 11, &[0, 3, 6, 9]),
292        (5, 6, &[0, 2, 3, 4, 5]),
293        (5, 7, &[0, 2, 3, 5, 6]),
294        (5, 8, &[0, 2, 3, 5, 6]),
295        (5, 9, &[0, 2, 4, 6, 8]),
296        (5, 11, &[0, 2, 4, 6, 8]),
297        (5, 12, &[0, 3, 5, 8, 10]),
298        (5, 13, &[0, 3, 5, 8, 10]),
299        (7, 8, &[0, 2, 3, 4, 5, 6, 7]),
300        (7, 12, &[0, 2, 3, 5, 7, 8, 10]),
301        (5, 16, &[0, 3, 6, 9, 12]),
302        (7, 16, &[0, 3, 5, 7, 10, 12, 14]),
303        (9, 16, &[0, 2, 3, 5, 7, 9, 10, 12, 14]),
304    ];
305
306    /// E(k, 16) for k = 2 to 11, the bar table.
307    const BARS: [(usize, &[usize]); 10] = [
308        (2, &[0, 8]),
309        (3, &[0, 5, 10]),
310        (4, &[0, 4, 8, 12]),
311        (5, &[0, 3, 6, 9, 12]),
312        (6, &[0, 3, 5, 8, 11, 13]),
313        (7, &[0, 3, 5, 7, 10, 12, 14]),
314        (8, &[0, 2, 4, 6, 8, 10, 12, 14]),
315        (9, &[0, 2, 3, 5, 7, 9, 10, 12, 14]),
316        (10, &[0, 2, 3, 5, 7, 8, 10, 11, 13, 15]),
317        (11, &[0, 2, 3, 5, 6, 8, 9, 11, 12, 14, 15]),
318    ];
319
320    fn floor_form(k: usize, n: usize) -> Vec<bool> {
321        (0..n).map(|i| (i * k) % n < k).collect()
322    }
323
324    #[test]
325    fn reproduces_every_printed_pattern() {
326        for (k, n, steps) in PRINTED {
327            let pattern = euclid(k, n);
328            assert_eq!(pattern.len(), n);
329            assert_eq!(onsets(&pattern), steps, "E({k},{n})");
330        }
331    }
332
333    #[test]
334    fn reproduces_the_bar_table() {
335        for (k, steps) in BARS {
336            assert_eq!(onsets(&euclid(k, 16)), steps, "E({k},16)");
337        }
338        assert_eq!(onsets(&euclid(4, 16)), [0, 4, 8, 12]);
339    }
340
341    #[test]
342    fn the_two_lists_hold_27_distinct_patterns() {
343        let mut all: Vec<(usize, usize)> = PRINTED.iter().map(|(k, n, _)| (*k, *n)).collect();
344        all.extend(BARS.iter().map(|(k, _)| (*k, 16)));
345        all.sort_unstable();
346        all.dedup();
347        assert_eq!(all.len(), 27);
348    }
349
350    #[test]
351    fn the_floor_form_fails_exactly_nine_printed_patterns() {
352        let failing: Vec<(usize, usize)> = PRINTED
353            .iter()
354            .filter(|(k, n, _)| floor_form(*k, *n) != euclid(*k, *n))
355            .map(|(k, n, _)| (*k, *n))
356            .collect();
357        assert_eq!(
358            failing,
359            [
360                (2, 5),
361                (3, 7),
362                (4, 9),
363                (5, 8),
364                (5, 11),
365                (5, 13),
366                (7, 12),
367                (5, 16),
368                (9, 16)
369            ]
370        );
371    }
372
373    #[test]
374    fn rotation_moves_onsets_by_r_modulo_n() {
375        for (k, n, _) in PRINTED {
376            let pattern = euclid(k, n);
377            for r in 0..n {
378                let turned: Vec<usize> = onsets(&rotate(&pattern, r));
379                let mut expected: Vec<usize> =
380                    onsets(&pattern).iter().map(|s| (s + r) % n).collect();
381                expected.sort_unstable();
382                assert_eq!(turned, expected, "E({k},{n}) by {r}");
383            }
384        }
385        assert_eq!(euclid(0, 4), [false; 4]);
386        assert_eq!(euclid(4, 4), [true; 4]);
387    }
388
389    #[test]
390    fn swing_matches_the_published_table() {
391        let rows = [
392            (54.0, 1.17, 0.08, 9.6, [13.3, 10.0, 8.6]),
393            (58.0, 1.38, 0.16, 19.2, [26.7, 20.0, 17.1]),
394            (62.0, 1.63, 0.24, 28.8, [40.0, 30.0, 25.7]),
395            (66.7, 2.00, 0.33, 40.0, [55.6, 41.7, 35.7]),
396            (75.0, 3.00, 0.50, 60.0, [83.3, 62.5, 53.6]),
397        ];
398        for (pct, ratio, delay, ticks, ms) in rows {
399            assert!((swing_ratio(pct).unwrap() - ratio).abs() < 0.006, "{pct}");
400            assert!((swing_delay(pct).unwrap() - delay).abs() < 0.006, "{pct}");
401            assert!(
402                (swing_ticks(pct, Pair::Sixteenths).unwrap() - ticks).abs() < 0.1,
403                "{pct}"
404            );
405            for (bpm, late) in [90.0, 120.0, 140.0].into_iter().zip(ms) {
406                let computed = swing_ticks(pct, Pair::Sixteenths).unwrap() * tick_ms(bpm).unwrap();
407                assert!((computed - late).abs() < 0.1, "{pct} at {bpm}: {computed}");
408            }
409            assert!((swing_pct(swing_ratio(pct).unwrap()).unwrap() - pct).abs() < 1e-9);
410        }
411        assert_eq!(swing_delay(50.0), Some(0.0));
412        assert!((swing_ticks(66.7, Pair::Eighths).unwrap() - 80.16).abs() < 0.01);
413        assert_eq!(
414            [Pair::Sixteenths.ticks(), Pair::Eighths.ticks()],
415            [240, 480]
416        );
417    }
418
419    #[test]
420    fn swing_refuses_a_negative_or_infinite_result() {
421        for pct in [49.9, 0.0, -10.0, f64::NAN, f64::INFINITY, f64::NEG_INFINITY] {
422            assert_eq!(swing_delay(pct), None, "{pct}");
423            assert_eq!(swing_ticks(pct, Pair::Sixteenths), None, "{pct}");
424            assert_eq!(swing_ticks(pct, Pair::Eighths), None, "{pct}");
425        }
426        for pct in [100.0, 150.0, -1.0, f64::NAN, f64::INFINITY] {
427            assert_eq!(swing_ratio(pct), None, "{pct}");
428        }
429        assert_eq!(swing_ratio(0.0), Some(0.0));
430        assert_eq!(swing_ratio(75.0), Some(3.0));
431        for ratio in [-1.0, -2.0, -0.5, f64::NAN, f64::INFINITY] {
432            assert_eq!(swing_pct(ratio), None, "{ratio}");
433        }
434        assert_eq!(swing_pct(0.0), Some(0.0));
435        assert_eq!(swing_pct(3.0), Some(75.0));
436        assert_eq!(swing_pct(1e300), Some(100.0));
437        assert_eq!(swing_pct(1e307), Some(100.0));
438        assert_eq!(swing_pct(f64::MAX), Some(100.0));
439        for zero in [swing_ratio(-0.0), swing_pct(-0.0)] {
440            assert!(zero.is_some_and(f64::is_sign_positive), "{zero:?}");
441        }
442    }
443
444    #[test]
445    fn tempo_lengths_refuse_a_tempo_outside_the_bpm_range() {
446        for bpm in [0.0, -120.0, f64::NAN, f64::INFINITY, 3.9, 1000.5] {
447            assert_eq!(tick_ms(bpm), None, "{bpm}");
448            assert_eq!(sixteenth_ms(bpm), None, "{bpm}");
449        }
450        assert_eq!(tick_ms(120.0), Some(1000.0 / 960.0));
451        assert_eq!(sixteenth_ms(120.0), Some(125.0));
452        for bpm in [4.0, 1000.0] {
453            assert!(tick_ms(bpm).is_some(), "{bpm}");
454            assert!(sixteenth_ms(bpm).is_some(), "{bpm}");
455        }
456        assert_eq!(tick_ms(4.0), Some(31.25));
457        assert_eq!(sixteenth_ms(1000.0), Some(15.0));
458    }
459
460    /// The tick and the sixteenth come from the MIDI writer and the beat
461    /// grid. They stay within two ulp of the published formulas
462    /// `60000 / (BPM * 480)` and `60000 / BPM / 4`.
463    #[test]
464    fn tempo_lengths_match_the_published_formulas_to_two_ulp() {
465        let ulps = |a: f64, b: f64| a.to_bits().abs_diff(b.to_bits());
466        for hundredths in 400_u32..=100_000 {
467            let bpm = f64::from(hundredths) / 100.0;
468            let tick = 60_000.0 / (bpm * f64::from(TICKS_PER_BEAT));
469            assert!(ulps(tick_ms(bpm).unwrap(), tick) <= 2, "{bpm}");
470            assert!(
471                ulps(sixteenth_ms(bpm).unwrap(), 60_000.0 / bpm / 4.0) <= 2,
472                "{bpm}"
473            );
474        }
475    }
476
477    #[test]
478    fn ticks_for_ms_refuses_a_bad_tempo_or_length() {
479        for bpm in [0.0, -120.0, f64::NAN, f64::INFINITY, 3.9, 1000.5] {
480            assert_eq!(ticks_for_ms(5.0, bpm), None, "{bpm}");
481        }
482        for ms in [f64::NAN, -1.0, f64::INFINITY, 1e12] {
483            assert_eq!(ticks_for_ms(ms, 120.0), None, "{ms}");
484        }
485        assert_eq!(ticks_for_ms(0.0, 120.0), Some(0));
486        assert_eq!(ticks_for_ms(-0.0, 120.0), Some(0));
487        assert_eq!(ticks_for_ms(1000.0, 120.0), Some(960));
488        assert_eq!(ticks_for_ms(1000.0, 4.0), Some(32));
489    }
490
491    #[test]
492    fn slot_ticks_refuses_a_grid_that_does_not_split_the_bar() {
493        assert_eq!(slot_ticks(0), None);
494        assert_eq!(slot_ticks(7), None);
495        assert_eq!(slot_ticks(1), Some(1920));
496        assert_eq!(slot_ticks(32), Some(60));
497    }
498
499    #[test]
500    fn ticks_and_milliseconds_match_the_published_values() {
501        let ticks: Vec<u32> = Division::ALL
502            .iter()
503            .map(|division| division.ticks())
504            .collect();
505        assert_eq!(ticks, [60, 80, 120, 160, 240, 320, 360, 480, 720, 1920]);
506        for division in Division::ALL {
507            let beats = division.division().beats_per_cycle();
508            assert_eq!(
509                beats * f64::from(TICKS_PER_BEAT),
510                f64::from(division.ticks()),
511                "{}",
512                division.name()
513            );
514            assert!(audio::Division::ALL.contains(&division.division()));
515        }
516        for (bpm, ms) in [(120.0, 1.042), (140.0, 0.893), (174.0, 0.718)] {
517            assert!((tick_ms(bpm).unwrap() - ms).abs() < 0.001, "{bpm}");
518        }
519        for (bpm, ms) in [(90.0, 166.7), (120.0, 125.0), (140.0, 107.1), (174.0, 86.2)] {
520            assert!((sixteenth_ms(bpm).unwrap() - ms).abs() < 0.05, "{bpm}");
521        }
522        assert_eq!(ticks_for_ms(5.0, 120.0), Some(5));
523        assert_eq!(ticks_for_ms(5.0, 174.0), Some(7));
524        assert_eq!(
525            [slot_ticks(12), slot_ticks(16), slot_ticks(24)],
526            [Some(160), Some(120), Some(80)]
527        );
528        assert!([160, 120, 80].iter().all(|ticks| ticks % 20 == 0));
529    }
530}
sound_to_patch/music/rhythm.rs

sound_to_patch/music/
rhythm.rs
