1use core::fmt;
2use serde::{Deserialize, Serialize};
3
4pub const TICKS_PER_SECOND: i64 = 120_000;
6
7pub const MAX_SERIALIZED_TICKS: i64 = (1 << 53) - 1;
10
11pub const PRESENTATION_SLACK: MediaTime = MediaTime(TICKS_PER_SECOND / 2_000 + 1);
14
15pub const ROUNDING_SCAN_FRAMES: usize = 64;
18
19pub const ROUNDING_SCAN_BYTES: u64 = 16 * 1024 * 1024;
22
23#[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
57type Fraction = (i128, i128);
59
60fn 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 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 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#[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 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#[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 pub const ZERO: Self = Self(0);
209 #[must_use]
211 pub const fn from_ticks(ticks: i64) -> Self {
212 Self(ticks)
213 }
214 #[must_use]
216 pub const fn ticks(self) -> i64 {
217 self.0
218 }
219 #[must_use]
221 pub const fn presentation_deadline(self, slack: Self) -> Self {
222 Self(self.0.saturating_add(slack.0))
223 }
224 #[must_use]
226 pub const fn from_seconds(seconds: i64) -> Self {
227 Self(seconds.saturating_mul(TICKS_PER_SECOND))
228 }
229 #[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 #[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 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 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 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 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 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 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 assert_eq!(
322 rounding_quantum(&[0, 1_500, 3_000, 6_000, 7_500, 10_500]),
323 0
324 );
325 assert_eq!(rounding_quantum(&[0, 17, 33, 67, 83, 100, 133, 150]), 1);
327 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 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 assert_eq!(
347 rounding_quantum(&[0, 3_003, 6_757, 9_760, 13_514, 16_517]),
348 0
349 );
350 assert_eq!(
352 rounding_quantum(&[0, 270_000, 630_000, 900_000, 1_260_000]),
353 90_000
354 );
355 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}