1use crate::media_time::rounding_quantum;
4
5#[derive(Clone, Copy, Debug, PartialEq, Eq)]
14pub struct AudioFrameGrid {
15 pub anchor: i64,
17 pub period: i64,
19 pub start_tolerance: i64,
22 pub trimmed_tolerance: i64,
25}
26
27impl AudioFrameGrid {
28 #[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
60const MAX_GRID_CANDIDATES: i128 = 4_096;
63
64#[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 let unit = i128::from(num) * i128::from(sample_rate);
96 let rounding = unit.checked_mul(i128::from(rounding_quantum(&sorted).max(1)))?;
98 if rounding < 2 * den {
99 return None;
100 }
101 let trimmed_tolerance = rounding.checked_add(den)?.div_euclid(den);
103 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
138enum Fit {
140 Empty,
141 Window(i128, i128),
142}
143
144fn 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, ×tamp) 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 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 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 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 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 assert_eq!(grid.place(401 * 48, 648), 19_200);
210 assert_eq!(grid.place(0, 648), 0);
211 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 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 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 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(®ular, 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}