use crate::media_time::rounding_quantum;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct AudioFrameGrid {
pub anchor: i64,
pub period: i64,
pub start_tolerance: i64,
pub trimmed_tolerance: i64,
}
impl AudioFrameGrid {
#[must_use]
pub fn place(&self, at: i64, frames: i64) -> i64 {
if (1..self.period).contains(&frames) {
let end = at.saturating_add(frames);
let shift = self.shift_onto(end);
if shift.abs() <= self.trimmed_tolerance {
return at.saturating_add(shift);
}
}
let shift = self.shift_onto(at);
if shift.abs() <= self.start_tolerance {
return at.saturating_add(shift);
}
at
}
fn shift_onto(&self, position: i64) -> i64 {
let offset =
(i128::from(position) - i128::from(self.anchor)).rem_euclid(i128::from(self.period));
let shift = if offset * 2 <= i128::from(self.period) {
-offset
} else {
i128::from(self.period) - offset
};
i64::try_from(shift).unwrap_or(0)
}
}
const MAX_GRID_CANDIDATES: i128 = 4_096;
#[must_use]
pub fn audio_frame_grid(
timestamps: &[i64],
num: i64,
den: i64,
sample_rate: u32,
) -> Option<AudioFrameGrid> {
if num <= 0 || den <= 0 || sample_rate == 0 {
return None;
}
let mut sorted = timestamps.to_vec();
sorted.sort_unstable();
sorted.dedup();
let (&first, &last) = (sorted.first()?, sorted.last()?);
let count = i128::try_from(sorted.len()).ok()?;
if count < 3 {
return None;
}
let den = i128::from(den);
let unit = i128::from(num) * i128::from(sample_rate);
let rounding = unit.checked_mul(i128::from(rounding_quantum(&sorted).max(1)))?;
if rounding < 2 * den {
return None;
}
let trimmed_tolerance = rounding.checked_add(den)?.div_euclid(den);
let span = (i128::from(last) - i128::from(first)).checked_mul(unit)?;
let step = den.checked_mul(count - 1)?;
let shortest = span
.checked_sub(rounding)?
.div_euclid(step)
.max(trimmed_tolerance.checked_mul(2)?.checked_add(1)?);
let longest = span
.checked_add(rounding)?
.div_euclid(step)
.checked_add(1)?;
if longest.checked_sub(shortest)? >= MAX_GRID_CANDIDATES {
return None;
}
let mut best: Option<(i128, i128, i128)> = None;
for period in shortest..=longest {
if let Fit::Window(low, high) = fit(&sorted, unit, rounding, den, period)?
&& best.is_none_or(|(_, best_low, best_high)| high - low > best_high - best_low)
{
best = Some((period, low, high));
}
}
let (period, low, high) = best?;
let anchor = low
.checked_add(high)?
.checked_add(2 * den)?
.div_euclid(4 * den);
Some(AudioFrameGrid {
anchor: i64::try_from(anchor).ok()?,
period: i64::try_from(period).ok()?,
start_tolerance: i64::try_from((rounding + 2 * den).div_euclid(2 * den)).ok()?,
trimmed_tolerance: i64::try_from(trimmed_tolerance).ok()?,
})
}
enum Fit {
Empty,
Window(i128, i128),
}
fn fit(sorted: &[i64], unit: i128, rounding: i128, den: i128, period: i128) -> Option<Fit> {
let (mut low, mut high) = (i128::MIN, i128::MAX);
for (index, ×tamp) in sorted.iter().enumerate() {
let index = i128::try_from(index).ok()?;
let center = (2 * i128::from(timestamp))
.checked_mul(unit)?
.checked_sub((2 * index).checked_mul(period)?.checked_mul(den)?)?;
low = low.max(center.checked_sub(rounding)?);
high = high.min(center.checked_add(rounding)?);
}
Some(if low <= high {
Fit::Window(low, high)
} else {
Fit::Empty
})
}
#[cfg(test)]
mod tests {
use super::{AudioFrameGrid, audio_frame_grid};
fn rounded(start: i64, period: i64, rate: i64, den: i64, count: i64) -> Vec<i64> {
(0..count)
.map(|k| {
let scaled = 2 * (start + k * period) * den;
scaled.signum() * ((scaled.abs() + rate) / (2 * rate))
})
.collect()
}
#[test]
fn rounded_timestamps_show_where_their_frames_start() {
let aac = rounded(-1_024, 1_024, 48_000, 1_000, 64);
assert_eq!(&aac[..5], [-21, 0, 21, 43, 64]);
let grid = audio_frame_grid(&aac, 1, 1_000, 48_000).expect("a grid");
assert_eq!(
grid,
AudioFrameGrid {
anchor: -1_024,
period: 1_024,
start_tolerance: 25,
trimmed_tolerance: 49,
}
);
let opus = rounded(-312, 960, 48_000, 1_000, 64);
assert_eq!(&opus[..3], [-7, 14, 34]);
let grid = audio_frame_grid(&opus, 1, 1_000, 48_000).expect("a grid");
assert_eq!((grid.anchor, grid.period), (-312, 960));
let aac = rounded(-1_024, 1_024, 44_100, 1_000, 64);
let grid = audio_frame_grid(&aac, 1, 1_000, 44_100).expect("a grid");
assert_eq!((grid.anchor, grid.period), (-1_024, 1_024));
assert_eq!((grid.start_tolerance, grid.trimmed_tolerance), (23, 45));
}
#[test]
fn a_first_frame_is_placed_on_the_grid() {
let grid = audio_frame_grid(&rounded(-312, 960, 48_000, 1_000, 64), 1, 1_000, 48_000)
.expect("a grid");
assert_eq!(grid.place(34 * 48, 960), 1_608);
assert_eq!(grid.place(401 * 48, 648), 19_200);
assert_eq!(grid.place(0, 648), 0);
assert_eq!(grid.place(1_608 + 26, 960), 1_634);
assert_eq!(grid.place(19_200 + 50, 648), 19_250);
}
#[test]
fn timestamps_that_place_frames_exactly_or_unevenly_show_no_grid() {
let exact: Vec<i64> = (0..64).map(|k| k * 1_024).collect();
assert_eq!(audio_frame_grid(&exact, 1, 48_000, 48_000), None);
let ts: Vec<i64> = (0..64).map(|k| 126_000 + k * 1_920).collect();
assert_eq!(audio_frame_grid(&ts, 1, 90_000, 48_000), None);
assert_eq!(
audio_frame_grid(&[0, 3, 15, 36, 58, 79, 100], 1, 1_000, 48_000),
None
);
let mut gap = rounded(0, 1_024, 48_000, 1_000, 64);
gap.remove(10);
assert_eq!(audio_frame_grid(&gap, 1, 1_000, 48_000), None);
assert_eq!(audio_frame_grid(&[0, 21], 1, 1_000, 48_000), None);
assert_eq!(
audio_frame_grid(&rounded(0, 1_024, 48_000, 50, 64), 1, 50, 48_000),
None
);
assert_eq!(audio_frame_grid(&[0, 21, 43], 0, 1_000, 48_000), None);
assert_eq!(audio_frame_grid(&[0, 21, 43], 1, 1_000, 0), None);
}
#[test]
fn timestamps_that_keep_milliseconds_in_a_finer_time_base_show_their_grid() {
let copied: Vec<i64> = rounded(-1_024, 1_024, 48_000, 1_000, 64)
.into_iter()
.map(|ms| ms * 48)
.collect();
let grid = audio_frame_grid(&copied, 1, 48_000, 48_000).expect("a grid");
assert_eq!((grid.anchor, grid.period), (-1_024, 1_024));
}
#[test]
fn timestamps_that_allow_too_many_periods_have_no_grid() {
for q in [1_000_000_i64, 1_000_000_000, 1_000_000_000_000] {
assert_eq!(
audio_frame_grid(&[0, 3 * q, 7 * q], 1, 1_000, 48_000),
None,
"{q}"
);
}
let regular = (0..64).map(|k| 3 * k).collect::<Vec<_>>();
assert_eq!(audio_frame_grid(®ular, 10_000_000, 1, 48_000), None);
}
#[test]
fn arithmetic_that_overflows_has_no_grid() {
assert_eq!(
audio_frame_grid(&[i64::MIN, 0, i64::MAX], i64::MAX, 1, u32::MAX),
None
);
}
}