Skip to main content

alpha2_time/
media_time.rs

1use core::fmt;
2use serde::{Deserialize, Serialize};
3
4/// Fixed alpha2 timeline ticks per second.
5pub const TICKS_PER_SECOND: i64 = 120_000;
6
7/// Largest magnitude of a serialized time: 2^53 - 1 ticks (about 2,378 years), the largest
8/// integer a JavaScript number holds exactly, so every host reads JSON times the same.
9pub const MAX_SERIALIZED_TICKS: i64 = (1 << 53) - 1;
10
11/// [`presentation_slack`] for an unknown time base: 0.5 ms plus one tick (61 ticks), as for
12/// milliseconds. Also the cap for streams whose timestamps show no rounding.
13pub const PRESENTATION_SLACK: MediaTime = MediaTime(TICKS_PER_SECOND / 2_000 + 1);
14
15/// Most leading packets whose timestamps feed [`rounding_quantum`], also capped by
16/// [`ROUNDING_SCAN_BYTES`].
17pub const ROUNDING_SCAN_FRAMES: usize = 64;
18
19/// Byte cap on the leading packets read for [`rounding_quantum`]. A native decoder holds the
20/// packets it read until it decodes them, so this keeps a 4K stream to about a second.
21pub const ROUNDING_SCAN_BYTES: u64 = 16 * 1024 * 1024;
22
23/// The unit a stream's timestamps are rounded to, in time-base units, or 0 when none shows.
24///
25/// `timestamps` are the stream's first presentation timestamps in any order. Rounding turns a
26/// frame interval into two lengths one unit apart (29.97 fps in milliseconds is 33 and 34 ms), so
27/// the unit is the GCD of the differences between intervals. Equal intervals mean exact frames.
28/// Differences of at least half the shortest interval are a variable frame rate, not rounding.
29/// The unit also has to explain the timestamps: every one lies on the first's grid of units, and
30/// one constant period, frames skipped allowed, places each within a unit of it. Otherwise
31/// (stills held for unequal times, two exact frame rates mixed) the gaps are real and 0 is
32/// returned. Fewer than three distinct timestamps return 0.
33#[must_use]
34pub fn rounding_quantum(timestamps: &[i64]) -> i64 {
35    let mut sorted = timestamps.to_vec();
36    sorted.sort_unstable();
37    sorted.dedup();
38    let intervals = sorted
39        .windows(2)
40        .map(|pair| i128::from(pair[1]) - i128::from(pair[0]))
41        .collect::<Vec<_>>();
42    let (Some(&first), Some(&shortest)) = (intervals.first(), intervals.iter().min()) else {
43        return 0;
44    };
45    let quantum = intervals.iter().fold(0_i128, |quantum, &interval| {
46        gcd(quantum, (interval - first).abs())
47    });
48    if quantum == 0
49        || quantum.saturating_mul(2) >= shortest
50        || !fits_one_period(&sorted, &intervals, shortest, quantum)
51    {
52        return 0;
53    }
54    i64::try_from(quantum).unwrap_or(0)
55}
56
57/// A numerator and a positive denominator.
58type Fraction = (i128, i128);
59
60/// Whether `sorted` is one constant period rounded to `unit`: every timestamp congruent to the
61/// first modulo `unit`, and a period `P` with `|(t_k - t_j) - (N_k - N_j) P| <= unit` for every
62/// pair, `N` counting frames. An interval is `round(d / p0)` frames, `p0` the mean of the
63/// intervals within a unit of the shortest. An overflow means no period.
64fn fits_one_period(sorted: &[i64], intervals: &[i128], shortest: i128, unit: i128) -> bool {
65    let first = i128::from(sorted[0]);
66    if sorted
67        .iter()
68        .any(|&time| (i128::from(time) - first).rem_euclid(unit) != 0)
69    {
70        return false;
71    }
72    let (sum, count) = intervals
73        .iter()
74        .filter(|&&interval| interval - shortest <= unit)
75        .fold((0_i128, 0_i128), |(sum, count), &interval| {
76            (sum.saturating_add(interval), count + 1)
77        });
78    let mut frames = vec![0_i128];
79    for &interval in intervals {
80        // round(interval * count / sum), halves up.
81        let Some(scaled) = interval
82            .checked_mul(2 * count)
83            .and_then(|twice| twice.checked_add(sum))
84        else {
85            return false;
86        };
87        let Some(next) = frames
88            .last()
89            .and_then(|&last| last.checked_add(scaled / (2 * sum)))
90        else {
91            return false;
92        };
93        frames.push(next);
94    }
95    // The largest lower bound and the smallest upper bound on P, as fractions.
96    let (mut low, mut high): (Option<Fraction>, Option<Fraction>) = (None, None);
97    let below = |a: Fraction, b: Fraction| -> Option<bool> {
98        Some(a.0.checked_mul(b.1)? < b.0.checked_mul(a.1)?)
99    };
100    for j in 0..sorted.len() {
101        for k in j + 1..sorted.len() {
102            let span = i128::from(sorted[k]) - i128::from(sorted[j]);
103            let count = frames[k] - frames[j];
104            if count <= 0 {
105                return false;
106            }
107            let (from, to) = ((span - unit, count), (span + unit, count));
108            match low.map(|low| below(low, from)) {
109                None | Some(Some(true)) => low = Some(from),
110                Some(Some(false)) => {}
111                Some(None) => return false,
112            }
113            match high.map(|high| below(to, high)) {
114                None | Some(Some(true)) => high = Some(to),
115                Some(Some(false)) => {}
116                Some(None) => return false,
117            }
118        }
119    }
120    match (low, high) {
121        (Some(low), Some(high)) => below(high, low) == Some(false),
122        _ => false,
123    }
124}
125
126fn gcd(mut a: i128, mut b: i128) -> i128 {
127    while b != 0 {
128        (a, b) = (b, a % b);
129    }
130    a
131}
132
133/// How much later than source time `t` a decoded frame's timestamp may be and still be the
134/// frame shown at `t`, for a `num / den` time base rounded to `quantum` units
135/// ([`rounding_quantum`], 0 for none).
136///
137/// A frame timestamp is its true time rounded to the stream's unit and then to the tick grid,
138/// while sampled times are floored ([`crate::FrameRate::frame_start`]). A 29.97 fps Matroska
139/// file stores its third frame (66.73 ms) at 67 ms, 32 ticks after the project frame that shows
140/// it. The slack is half the rounding unit (or half the time-base unit when no rounding shows,
141/// capped at [`PRESENTATION_SLACK`]) rounded up to a tick, plus one tick. Hosts show the last
142/// frame at or before [`MediaTime::presentation_deadline`].
143///
144/// A non-positive `num` or `den` returns [`PRESENTATION_SLACK`]; a negative `quantum` means none.
145#[must_use]
146pub fn presentation_slack(num: i64, den: i64, quantum: i64) -> MediaTime {
147    if num <= 0 || den <= 0 {
148        return PRESENTATION_SLACK;
149    }
150    let (units, cap) = if quantum > 0 {
151        (i128::from(quantum), i128::MAX)
152    } else {
153        (1, i128::from(PRESENTATION_SLACK.0))
154    };
155    // Half the rounding in ticks, rounded up: (ticks per second * num * units) / (2 * den).
156    let (rounding, halves) = (
157        i128::from(TICKS_PER_SECOND)
158            .saturating_mul(i128::from(num))
159            .saturating_mul(units),
160        2 * i128::from(den),
161    );
162    let half = rounding.saturating_add(halves - 1) / halves;
163    let slack = half.saturating_add(1).min(cap);
164    MediaTime(i64::try_from(slack).unwrap_or(MAX_SERIALIZED_TICKS))
165}
166
167/// A signed position or duration in timeline ticks (120 000 per second).
168///
169/// Deserialization rejects magnitudes above [`MAX_SERIALIZED_TICKS`].
170#[derive(
171    Copy, Clone, Debug, Default, Deserialize, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize,
172)]
173#[serde(try_from = "i64")]
174pub struct MediaTime(pub i64);
175
176#[cfg(feature = "schema")]
177impl schemars::JsonSchema for MediaTime {
178    fn schema_name() -> std::borrow::Cow<'static, str> {
179        "MediaTime".into()
180    }
181
182    fn json_schema(_: &mut schemars::SchemaGenerator) -> schemars::Schema {
183        schemars::json_schema!({
184            "description": "A signed position or duration in timeline ticks (120 000 per second), at most the largest integer a JavaScript number holds exactly either way.",
185            "type": "integer",
186            "format": "int64",
187            "minimum": -MAX_SERIALIZED_TICKS,
188            "maximum": MAX_SERIALIZED_TICKS,
189        })
190    }
191}
192
193impl TryFrom<i64> for MediaTime {
194    type Error = String;
195
196    fn try_from(ticks: i64) -> Result<Self, Self::Error> {
197        if ticks.unsigned_abs() > MAX_SERIALIZED_TICKS.unsigned_abs() {
198            return Err(format!(
199                "a time of {ticks} ticks is beyond {MAX_SERIALIZED_TICKS} either way"
200            ));
201        }
202        Ok(Self(ticks))
203    }
204}
205
206impl MediaTime {
207    /// Timeline origin.
208    pub const ZERO: Self = Self(0);
209    /// Creates a value from ticks.
210    #[must_use]
211    pub const fn from_ticks(ticks: i64) -> Self {
212        Self(ticks)
213    }
214    /// Returns raw ticks.
215    #[must_use]
216    pub const fn ticks(self) -> i64 {
217        self.0
218    }
219    /// Latest timestamp a decoded frame may carry and still be shown at this source time.
220    #[must_use]
221    pub const fn presentation_deadline(self, slack: Self) -> Self {
222        Self(self.0.saturating_add(slack.0))
223    }
224    /// Creates a value from whole seconds, saturating at the `i64` bounds.
225    #[must_use]
226    pub const fn from_seconds(seconds: i64) -> Self {
227        Self(seconds.saturating_mul(TICKS_PER_SECOND))
228    }
229    /// Checked addition.
230    #[must_use]
231    pub const fn checked_add(self, other: Self) -> Option<Self> {
232        match self.0.checked_add(other.0) {
233            Some(value) => Some(Self(value)),
234            None => None,
235        }
236    }
237    /// Checked subtraction.
238    #[must_use]
239    pub const fn checked_sub(self, other: Self) -> Option<Self> {
240        match self.0.checked_sub(other.0) {
241            Some(value) => Some(Self(value)),
242            None => None,
243        }
244    }
245}
246
247impl fmt::Display for MediaTime {
248    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
249        write!(f, "{} ticks", self.0)
250    }
251}
252
253#[cfg(test)]
254mod tests {
255    use super::*;
256    #[test]
257    fn seconds_and_overflow() {
258        assert_eq!(MediaTime::from_seconds(1).ticks(), TICKS_PER_SECOND);
259        assert_eq!(MediaTime(i64::MAX).checked_add(MediaTime(1)), None);
260    }
261
262    #[test]
263    fn a_time_base_bounds_how_late_a_shown_frame_may_be() {
264        // Milliseconds round by up to 60 ticks; 1/90000 by two thirds of one; 1/30000 by two.
265        assert_eq!(presentation_slack(1, 1_000, 0), MediaTime(61));
266        assert_eq!(presentation_slack(1, 90_000, 0), MediaTime(2));
267        assert_eq!(presentation_slack(1, 30_000, 0), MediaTime(3));
268        assert_eq!(presentation_slack(1, 15_360, 0), MediaTime(5));
269        assert_eq!(presentation_slack(1, TICKS_PER_SECOND, 0), MediaTime(2));
270        // A coarse unit with no rounding is capped at the millisecond slack.
271        assert_eq!(presentation_slack(1_001, 30_000, 0), PRESENTATION_SLACK);
272        assert_eq!(presentation_slack(1, 600, 0), PRESENTATION_SLACK);
273        assert_eq!(presentation_slack(0, 1, 0), PRESENTATION_SLACK);
274        assert_eq!(presentation_slack(1, 0, 0), PRESENTATION_SLACK);
275        assert_eq!(presentation_slack(1, 0, 16), PRESENTATION_SLACK);
276        assert_eq!(
277            MediaTime(8_008).presentation_deadline(presentation_slack(1, 1_000, 0)),
278            MediaTime(8_069)
279        );
280    }
281
282    #[test]
283    fn a_rounding_the_timestamps_show_bounds_it_however_coarse() {
284        // An MP4 that kept a Matroska file's milliseconds in 1/16000, 29.97 fps in 1/600 and 1/100.
285        assert_eq!(presentation_slack(1, 16_000, 16), MediaTime(61));
286        assert_eq!(presentation_slack(1, 600, 1), MediaTime(101));
287        assert_eq!(presentation_slack(1, 100, 1), MediaTime(601));
288        assert_eq!(presentation_slack(1, 1_000, 1), MediaTime(61));
289        assert_eq!(presentation_slack(1, 90_000, 90), MediaTime(61));
290        assert_eq!(presentation_slack(1, 1_000, -1), MediaTime(61));
291        assert_eq!(
292            presentation_slack(i64::MAX, 1, i64::MAX),
293            MediaTime(MAX_SERIALIZED_TICKS)
294        );
295    }
296
297    /// The first `count` frame starts of `num / den` fps, rounded to the nearest of `1 / base` s.
298    fn rounded(num: i64, den: i64, base: i64, count: i64) -> Vec<i64> {
299        (0..count)
300            .map(|frame| (2 * frame * den * base + num) / (2 * num))
301            .collect()
302    }
303
304    #[test]
305    fn the_spacing_of_the_first_timestamps_shows_their_rounding() {
306        // 29.97 fps in milliseconds (33, 34), the same kept in 1/16000 (528, 544), in 1/600
307        // (20, 21) and in 1/100 (3, 4).
308        assert_eq!(rounding_quantum(&rounded(30_000, 1_001, 1_000, 64)), 1);
309        let remuxed = rounded(30_000, 1_001, 1_000, 64)
310            .into_iter()
311            .map(|ms| ms * 16)
312            .collect::<Vec<_>>();
313        assert_eq!(rounding_quantum(&remuxed), 16);
314        assert_eq!(rounding_quantum(&rounded(30_000, 1_001, 600, 64)), 1);
315        assert_eq!(rounding_quantum(&rounded(30_000, 1_001, 100, 64)), 1);
316        // Exact frames: 30 fps in 1/600, 25 fps in milliseconds, 29.97 in 1001/30000.
317        assert_eq!(rounding_quantum(&rounded(30, 1, 600, 64)), 0);
318        assert_eq!(rounding_quantum(&rounded(25, 1, 1_000, 64)), 0);
319        assert_eq!(rounding_quantum(&(0..64).collect::<Vec<_>>()), 0);
320        // 60 and 30 fps frames in an exact 1/90000 time base are a variable rate, not a rounding.
321        assert_eq!(
322            rounding_quantum(&[0, 1_500, 3_000, 6_000, 7_500, 10_500]),
323            0
324        );
325        // A screen recording in milliseconds: 60 and 30 fps frames, each rounded.
326        assert_eq!(rounding_quantum(&[0, 17, 33, 67, 83, 100, 133, 150]), 1);
327        // Decode order, repeats, and too few frames to show a spacing.
328        assert_eq!(rounding_quantum(&[67, 0, 33, 33, 100, 133]), 1);
329        assert_eq!(rounding_quantum(&[0, 33]), 0);
330        assert_eq!(rounding_quantum(&[]), 0);
331        assert_eq!(rounding_quantum(&[i64::MIN, 0, i64::MAX]), 1);
332    }
333
334    #[test]
335    fn a_coarse_unit_counts_only_when_one_period_explains_the_timestamps() {
336        // Stills held 3, 3, 3, 4, 4 and 4 s: gaps of whole seconds, not a rounding.
337        let stills = |units: i64| {
338            [0, 3, 6, 9, 13, 17, 21]
339                .iter()
340                .map(|second| second * units)
341                .collect::<Vec<_>>()
342        };
343        assert_eq!(rounding_quantum(&stills(90_000)), 0);
344        assert_eq!(rounding_quantum(&stills(1_000)), 0);
345        // Exact 29.97 and 23.976 fps frames mixed in 1/90000 (3003 and 3754).
346        assert_eq!(
347            rounding_quantum(&[0, 3_003, 6_757, 9_760, 13_514, 16_517]),
348            0
349        );
350        // Stills at 0, 3, 7, 10 and 14 s are also a 3.5 s period rounded to seconds.
351        assert_eq!(
352            rounding_quantum(&[0, 270_000, 630_000, 900_000, 1_260_000]),
353            90_000
354        );
355        // AAC in Matroska copied into a 1/48000 track: 0, 1024, then every frame 8 short.
356        let remux = [0, 1_024]
357            .into_iter()
358            .chain((2..64).map(|k| k * 1_024 - 8))
359            .collect::<Vec<_>>();
360        assert_eq!(rounding_quantum(&remux), 8);
361    }
362}