Skip to main content

alpha2_time/
audio_grid.rs

1//! Where an audio stream's frames start when its container rounds their timestamps.
2
3use crate::media_time::rounding_quantum;
4
5/// Frame start samples of an audio stream, every `period` samples from `anchor`, inferred from
6/// its first packet timestamps ([`audio_frame_grid`]).
7///
8/// Containers that round timestamps (Matroska and `WebM` to the millisecond) place a frame up to
9/// half a unit (24 samples at 48 kHz) off its true start, and a seek and a straight decode are off
10/// by different amounts. For fixed-length frames (AAC's 1024 samples, Opus's 20 ms) the first
11/// timestamps together locate the grid far more precisely, so snapping to it makes a seek give
12/// the same samples as a straight decode.
13#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub struct AudioFrameGrid {
15    /// A source sample at which a frame starts.
16    pub anchor: i64,
17    /// Samples per frame.
18    pub period: i64,
19    /// Farthest a frame timestamp, in samples, can be from its true start: half the rounding
20    /// unit plus half a sample, rounded.
21    pub start_tolerance: i64,
22    /// Farthest the end of a trimmed frame (shorter than `period`, as after Opus pre-skip) can
23    /// be from the grid. The trim is rounded again, so this is a full unit plus a sample.
24    pub trimmed_tolerance: i64,
25}
26
27impl AudioFrameGrid {
28    /// Start of a `frames`-sample frame whose timestamp says `at`: snapped to the grid when
29    /// within tolerance, otherwise `at`.
30    ///
31    /// A frame shorter than [`Self::period`] is first tried as a trimmed frame ending on the grid.
32    #[must_use]
33    pub fn place(&self, at: i64, frames: i64) -> i64 {
34        if (1..self.period).contains(&frames) {
35            let end = at.saturating_add(frames);
36            let shift = self.shift_onto(end);
37            if shift.abs() <= self.trimmed_tolerance {
38                return at.saturating_add(shift);
39            }
40        }
41        let shift = self.shift_onto(at);
42        if shift.abs() <= self.start_tolerance {
43            return at.saturating_add(shift);
44        }
45        at
46    }
47
48    fn shift_onto(&self, position: i64) -> i64 {
49        let offset =
50            (i128::from(position) - i128::from(self.anchor)).rem_euclid(i128::from(self.period));
51        let shift = if offset * 2 <= i128::from(self.period) {
52            -offset
53        } else {
54            i128::from(self.period) - offset
55        };
56        i64::try_from(shift).unwrap_or(0)
57    }
58}
59
60/// Most whole-sample periods [`audio_frame_grid`] tries: enough for a rounding unit of about 4,000
61/// samples, far past any real stream's.
62const MAX_GRID_CANDIDATES: i128 = 4_096;
63
64/// The frame grid shown by an audio stream's first packet timestamps (any order, in `num / den`
65/// second units) at `sample_rate`, or `None`.
66///
67/// The rounding unit is [`rounding_quantum`], or one time-base unit when none shows. Every
68/// timestamp must lie within half a unit of the grid. Among whole-sample periods that fit, the one
69/// with the most slack wins (shortest on ties), and the anchor is the middle of its feasible range.
70///
71/// Returns `None` when half a unit is under a sample (timestamps are already exact), when fewer
72/// than three distinct timestamps are given or none fits (variable frame sizes, a missing packet),
73/// when no period exceeds twice the trimmed tolerance, when an argument is not positive, when the
74/// timestamps allow 4,096 periods or more, or when the arithmetic overflows.
75#[must_use]
76pub fn audio_frame_grid(
77    timestamps: &[i64],
78    num: i64,
79    den: i64,
80    sample_rate: u32,
81) -> Option<AudioFrameGrid> {
82    if num <= 0 || den <= 0 || sample_rate == 0 {
83        return None;
84    }
85    let mut sorted = timestamps.to_vec();
86    sorted.sort_unstable();
87    sorted.dedup();
88    let (&first, &last) = (sorted.first()?, sorted.last()?);
89    let count = i128::try_from(sorted.len()).ok()?;
90    if count < 3 {
91        return None;
92    }
93    let den = i128::from(den);
94    // Samples per time-base unit, times `den`.
95    let unit = i128::from(num) * i128::from(sample_rate);
96    // Rounding unit in samples, times `den`.
97    let rounding = unit.checked_mul(i128::from(rounding_quantum(&sorted).max(1)))?;
98    if rounding < 2 * den {
99        return None;
100    }
101    // Twice the trimmed tolerance must stay under the period for a timestamp to name one frame.
102    let trimmed_tolerance = rounding.checked_add(den)?.div_euclid(den);
103    // The span is off by up to a unit at either end, which bounds the candidate periods.
104    let span = (i128::from(last) - i128::from(first)).checked_mul(unit)?;
105    let step = den.checked_mul(count - 1)?;
106    let shortest = span
107        .checked_sub(rounding)?
108        .div_euclid(step)
109        .max(trimmed_tolerance.checked_mul(2)?.checked_add(1)?);
110    let longest = span
111        .checked_add(rounding)?
112        .div_euclid(step)
113        .checked_add(1)?;
114    if longest.checked_sub(shortest)? >= MAX_GRID_CANDIDATES {
115        return None;
116    }
117    let mut best: Option<(i128, i128, i128)> = None;
118    for period in shortest..=longest {
119        if let Fit::Window(low, high) = fit(&sorted, unit, rounding, den, period)?
120            && best.is_none_or(|(_, best_low, best_high)| high - low > best_high - best_low)
121        {
122            best = Some((period, low, high));
123        }
124    }
125    let (period, low, high) = best?;
126    let anchor = low
127        .checked_add(high)?
128        .checked_add(2 * den)?
129        .div_euclid(4 * den);
130    Some(AudioFrameGrid {
131        anchor: i64::try_from(anchor).ok()?,
132        period: i64::try_from(period).ok()?,
133        start_tolerance: i64::try_from((rounding + 2 * den).div_euclid(2 * den)).ok()?,
134        trimmed_tolerance: i64::try_from(trimmed_tolerance).ok()?,
135    })
136}
137
138/// Feasible first-frame starts of a period, in samples times `2 * den`.
139enum Fit {
140    Empty,
141    Window(i128, i128),
142}
143
144/// The starts for a `period` grid within `rounding` of every timestamp; `None` on overflow.
145fn fit(sorted: &[i64], unit: i128, rounding: i128, den: i128, period: i128) -> Option<Fit> {
146    let (mut low, mut high) = (i128::MIN, i128::MAX);
147    for (index, &timestamp) in sorted.iter().enumerate() {
148        let index = i128::try_from(index).ok()?;
149        let center = (2 * i128::from(timestamp))
150            .checked_mul(unit)?
151            .checked_sub((2 * index).checked_mul(period)?.checked_mul(den)?)?;
152        low = low.max(center.checked_sub(rounding)?);
153        high = high.min(center.checked_add(rounding)?);
154    }
155    Some(if low <= high {
156        Fit::Window(low, high)
157    } else {
158        Fit::Empty
159    })
160}
161
162#[cfg(test)]
163mod tests {
164    use super::{AudioFrameGrid, audio_frame_grid};
165
166    /// Frame timestamps rounded to `1 / den` s, half away from zero like `FFmpeg`'s `av_rescale_q`.
167    fn rounded(start: i64, period: i64, rate: i64, den: i64, count: i64) -> Vec<i64> {
168        (0..count)
169            .map(|k| {
170                let scaled = 2 * (start + k * period) * den;
171                scaled.signum() * ((scaled.abs() + rate) / (2 * rate))
172            })
173            .collect()
174    }
175
176    #[test]
177    fn rounded_timestamps_show_where_their_frames_start() {
178        // AAC in Matroska with a priming frame at -1024; a straight decode would start at -1008.
179        let aac = rounded(-1_024, 1_024, 48_000, 1_000, 64);
180        assert_eq!(&aac[..5], [-21, 0, 21, 43, 64]);
181        let grid = audio_frame_grid(&aac, 1, 1_000, 48_000).expect("a grid");
182        assert_eq!(
183            grid,
184            AudioFrameGrid {
185                anchor: -1_024,
186                period: 1_024,
187                start_tolerance: 25,
188                trimmed_tolerance: 49,
189            }
190        );
191        // Opus in WebM with libopus's 312-sample pre-skip.
192        let opus = rounded(-312, 960, 48_000, 1_000, 64);
193        assert_eq!(&opus[..3], [-7, 14, 34]);
194        let grid = audio_frame_grid(&opus, 1, 1_000, 48_000).expect("a grid");
195        assert_eq!((grid.anchor, grid.period), (-312, 960));
196        // At 44.1 kHz a millisecond is 44.1 samples.
197        let aac = rounded(-1_024, 1_024, 44_100, 1_000, 64);
198        let grid = audio_frame_grid(&aac, 1, 1_000, 44_100).expect("a grid");
199        assert_eq!((grid.anchor, grid.period), (-1_024, 1_024));
200        assert_eq!((grid.start_tolerance, grid.trimmed_tolerance), (23, 45));
201    }
202
203    #[test]
204    fn a_first_frame_is_placed_on_the_grid() {
205        let grid = audio_frame_grid(&rounded(-312, 960, 48_000, 1_000, 64), 1, 1_000, 48_000)
206            .expect("a grid");
207        assert_eq!(grid.place(34 * 48, 960), 1_608);
208        // A post-seek frame trimmed by 312 samples: 393.5 ms + 6.5 ms, each rounded up, is 401 ms.
209        assert_eq!(grid.place(401 * 48, 648), 19_200);
210        assert_eq!(grid.place(0, 648), 0);
211        // Beyond tolerance, the timestamp is used as is.
212        assert_eq!(grid.place(1_608 + 26, 960), 1_634);
213        assert_eq!(grid.place(19_200 + 50, 648), 19_250);
214    }
215
216    #[test]
217    fn timestamps_that_place_frames_exactly_or_unevenly_show_no_grid() {
218        // Sample-rate (MP4) and 1/90000 (MPEG-TS) time bases are exact to half a sample.
219        let exact: Vec<i64> = (0..64).map(|k| k * 1_024).collect();
220        assert_eq!(audio_frame_grid(&exact, 1, 48_000, 48_000), None);
221        let ts: Vec<i64> = (0..64).map(|k| 126_000 + k * 1_920).collect();
222        assert_eq!(audio_frame_grid(&ts, 1, 90_000, 48_000), None);
223        // Vorbis in WebM: long and short blocks, 0, 3, 15, 36, 58 ms.
224        assert_eq!(
225            audio_frame_grid(&[0, 3, 15, 36, 58, 79, 100], 1, 1_000, 48_000),
226            None
227        );
228        let mut gap = rounded(0, 1_024, 48_000, 1_000, 64);
229        gap.remove(10);
230        assert_eq!(audio_frame_grid(&gap, 1, 1_000, 48_000), None);
231        assert_eq!(audio_frame_grid(&[0, 21], 1, 1_000, 48_000), None);
232        assert_eq!(
233            audio_frame_grid(&rounded(0, 1_024, 48_000, 50, 64), 1, 50, 48_000),
234            None
235        );
236        assert_eq!(audio_frame_grid(&[0, 21, 43], 0, 1_000, 48_000), None);
237        assert_eq!(audio_frame_grid(&[0, 21, 43], 1, 1_000, 0), None);
238    }
239
240    #[test]
241    fn timestamps_that_keep_milliseconds_in_a_finer_time_base_show_their_grid() {
242        // Matroska's milliseconds copied into a 1/48000 time base: multiples of 48.
243        let copied: Vec<i64> = rounded(-1_024, 1_024, 48_000, 1_000, 64)
244            .into_iter()
245            .map(|ms| ms * 48)
246            .collect();
247        let grid = audio_frame_grid(&copied, 1, 48_000, 48_000).expect("a grid");
248        assert_eq!((grid.anchor, grid.period), (-1_024, 1_024));
249    }
250
251    #[test]
252    fn timestamps_that_allow_too_many_periods_have_no_grid() {
253        for q in [1_000_000_i64, 1_000_000_000, 1_000_000_000_000] {
254            assert_eq!(
255                audio_frame_grid(&[0, 3 * q, 7 * q], 1, 1_000, 48_000),
256                None,
257                "{q}"
258            );
259        }
260        let regular = (0..64).map(|k| 3 * k).collect::<Vec<_>>();
261        assert_eq!(audio_frame_grid(&regular, 10_000_000, 1, 48_000), None);
262    }
263
264    #[test]
265    fn arithmetic_that_overflows_has_no_grid() {
266        assert_eq!(
267            audio_frame_grid(&[i64::MIN, 0, i64::MAX], i64::MAX, 1, u32::MAX),
268            None
269        );
270    }
271}