Skip to main content

alpha2_eval/
retime.rs

1use alpha2_model::{LoopMode, TimeMap};
2use alpha2_time::{FrameRate, MediaTime, TICKS_PER_SECOND, TimeRange};
3
4/// Frame grid that reverse playback and ping-pong backward passes mirror by: frame `k` starts
5/// at `floor(k * ticks / per)`, like project frames.
6///
7/// Pictures mirror by project frame, so a reversed clip shows the forward clip's frames in
8/// reverse order at any rate and clip bounds. Sound mirrors by tick, the closest ticks get to the
9/// mixer's per-sample mirror.
10#[derive(Copy, Clone, Debug, Eq, PartialEq)]
11pub(crate) struct Mirror {
12    ticks: i128,
13    per: i128,
14}
15
16impl Mirror {
17    /// One tick.
18    pub(crate) const TICK: Self = Self { ticks: 1, per: 1 };
19
20    /// One frame at `rate`.
21    pub(crate) fn frame(rate: FrameRate) -> Self {
22        Self {
23            ticks: i128::from(TICKS_PER_SECOND) * i128::from(rate.denominator()),
24            per: i128::from(rate.numerator()),
25        }
26    }
27
28    fn start_of(self, frame: i128) -> Option<i128> {
29        Some(frame.checked_mul(self.ticks)?.div_euclid(self.per))
30    }
31
32    fn frame_of(self, tick: i128) -> Option<i128> {
33        Some(
34            tick.checked_add(1)?
35                .checked_mul(self.per)?
36                .checked_sub(1)?
37                .div_euclid(self.ticks),
38        )
39    }
40
41    /// Forward offset `floor(e' * scale / length)` shown by the mirror of `elapsed` in a window
42    /// of `length` ticks from `start`.
43    ///
44    /// With `k0`/`k1` the first/last frames starting in the window and `k` the frame containing
45    /// `start + elapsed` (clamped to `k0`), `e'` is `start_of(k0 + k1 - k)` minus the time into
46    /// `k`, relative to the window start and floored at zero. A window with no frame start gives 0.
47    fn offset(self, start: i128, length: i128, elapsed: i128, scale: i128) -> Option<i128> {
48        let first = self.frame_of(start.checked_sub(1)?)?.checked_add(1)?;
49        let last = self.frame_of(start.checked_add(length)?.checked_sub(1)?)?;
50        if first > last {
51            return Some(0);
52        }
53        let tick = start.checked_add(elapsed)?;
54        let frame = self.frame_of(tick)?;
55        let (frame, into) = if frame < first {
56            (first, 0)
57        } else {
58            (frame, tick.checked_sub(self.start_of(frame)?)?)
59        };
60        let mirrored = self
61            .start_of(first.checked_add(last)?.checked_sub(frame)?)?
62            .checked_sub(into)?
63            .checked_sub(start)?;
64        if mirrored <= 0 {
65            return Some(0);
66        }
67        Some(mirrored.checked_mul(scale)?.div_euclid(length))
68    }
69}
70
71/// The source instant a clip shows at timeline `time`, in whole ticks.
72///
73/// With `e = time - timeline.start`, `T` the timeline duration, `S` the
74/// source duration, and `mirror` the frames reversing mirrors by:
75///
76/// - forward: `source.start + floor(e * S / T)`;
77/// - reverse: the forward instant at the mirrored frame less the time into the frame
78///   ([`Mirror`]), clamped to the source start;
79/// - freeze: its instant;
80/// - a repeating loop: `source.start + (e mod S)`;
81/// - a ping-pong loop: the same on even passes, mirrored on odd ones.
82///
83/// Returns `None` for an empty range or a value that does not fit in ticks.
84pub(crate) fn map_source_time(
85    timeline: TimeRange,
86    source: TimeRange,
87    time_map: TimeMap,
88    mirror: Mirror,
89    time: MediaTime,
90) -> Option<MediaTime> {
91    let timeline_duration = i128::from(timeline.duration()?.ticks());
92    let source_duration = i128::from(source.duration()?.ticks());
93    if timeline_duration == 0 || source_duration == 0 {
94        return None;
95    }
96    let elapsed = i128::from(time.ticks()) - i128::from(timeline.start().ticks());
97    let offset = match time_map {
98        TimeMap::Forward => elapsed
99            .checked_mul(source_duration)?
100            .div_euclid(timeline_duration),
101        TimeMap::Reverse => mirror.offset(
102            i128::from(timeline.start().ticks()),
103            timeline_duration,
104            elapsed,
105            source_duration,
106        )?,
107        TimeMap::Freeze { source_time } => return Some(source_time),
108        TimeMap::Loop { mode } => {
109            let within = elapsed.rem_euclid(source_duration);
110            let pass = elapsed.div_euclid(source_duration);
111            match mode {
112                LoopMode::PingPong if pass.rem_euclid(2) == 1 => mirror.offset(
113                    i128::from(timeline.start().ticks())
114                        .checked_add(pass.checked_mul(source_duration)?)?,
115                    source_duration,
116                    within,
117                    source_duration,
118                )?,
119                LoopMode::Repeat | LoopMode::PingPong => within,
120            }
121        }
122    };
123    let mapped = i128::from(source.start().ticks()).checked_add(offset)?;
124    i64::try_from(mapped).ok().map(MediaTime::from_ticks)
125}
126
127/// The source instant a clip's picture shows at timeline `time`, mirroring by project frames at
128/// `frame_rate` exactly as evaluation draws it.
129///
130/// `tests/golden/time-rules-corpus.json` pins this for the TypeScript port.
131///
132/// Returns `None` for an empty range or a value that does not fit in ticks.
133#[must_use]
134pub fn picture_source_time(
135    timeline: TimeRange,
136    source: TimeRange,
137    time_map: TimeMap,
138    frame_rate: FrameRate,
139    time: MediaTime,
140) -> Option<MediaTime> {
141    map_source_time(timeline, source, time_map, Mirror::frame(frame_rate), time)
142}
143
144/// One stretch of a clip's timeline over which the shown source time moves one way.
145#[derive(Copy, Clone)]
146enum Direction {
147    Rising,
148    Falling,
149    Still,
150}
151
152/// The stretches of `timeline` over which `time_map` moves the shown source time one way: the
153/// whole clip, or one per loop pass, made as they are read. `None` when a pass would end past
154/// the `i64` tick range.
155fn monotone_stretches(
156    timeline: TimeRange,
157    source: TimeRange,
158    time_map: TimeMap,
159) -> Option<impl Iterator<Item = (i64, i64, Direction)>> {
160    let (start, end) = (timeline.start().ticks(), timeline.end().ticks());
161    let source_length = source.duration()?.ticks();
162    let empty = start >= end || source_length <= 0;
163    let step = match time_map {
164        TimeMap::Loop { .. } if !empty => {
165            let passes = (i128::from(end) - i128::from(start) - 1) / i128::from(source_length);
166            let last_end = i128::from(start) + (passes + 1) * i128::from(source_length);
167            i64::try_from(last_end).ok()?;
168            source_length
169        }
170        _ => i64::MAX,
171    };
172    let mut from = if empty { end } else { start };
173    let mut pass = 0_i64;
174    Some(std::iter::from_fn(move || {
175        if from >= end {
176            return None;
177        }
178        let to = from.saturating_add(step).min(end);
179        let direction = match time_map {
180            TimeMap::Freeze { .. } => Direction::Still,
181            TimeMap::Reverse => Direction::Falling,
182            TimeMap::Loop {
183                mode: LoopMode::PingPong,
184            } if pass % 2 == 1 => Direction::Falling,
185            TimeMap::Forward | TimeMap::Loop { .. } => Direction::Rising,
186        };
187        let stretch = (from, to, direction);
188        from = to;
189        pass += 1;
190        Some(stretch)
191    }))
192}
193
194/// The first tick in `from..to` at which `reached` holds, for a `reached` that never stops
195/// holding once it does; `to` when it never holds.
196fn first_reached(from: i64, to: i64, reached: impl Fn(i64) -> bool) -> i64 {
197    let (mut low, mut high) = (from, to);
198    while low < high {
199        let middle = low + (high - low) / 2;
200        if reached(middle) {
201            high = middle;
202        } else {
203            low = middle + 1;
204        }
205    }
206    low
207}
208
209/// The timeline ranges of a clip at which its picture shows a source time in
210/// `[range_start, range_end)`, the full preimage of [`picture_source_time`].
211///
212/// Forward and stretched clips give one range, reversed clips one mirrored range, loops one per
213/// pass that reaches the interval, and a freeze the whole clip when its instant lies inside the
214/// interval. Ranges are in timeline order and disjoint. `None` for a time beyond ticks.
215#[must_use]
216pub fn source_range_to_timeline(
217    timeline: TimeRange,
218    source: TimeRange,
219    time_map: TimeMap,
220    frame_rate: FrameRate,
221    range_start: MediaTime,
222    range_end: MediaTime,
223) -> Option<Vec<TimeRange>> {
224    if range_start >= range_end {
225        return Some(Vec::new());
226    }
227    let shown = |tick: i64| {
228        picture_source_time(timeline, source, time_map, frame_rate, MediaTime(tick))
229            .map_or(i64::MIN, MediaTime::ticks)
230    };
231    let (low, high) = (range_start.ticks(), range_end.ticks());
232    // Every map but a freeze shows only times inside the source range, so an interval covering
233    // it is the whole clip, found without walking loop passes.
234    if !matches!(time_map, TimeMap::Freeze { .. })
235        && low <= source.start().ticks()
236        && high >= source.end().ticks()
237    {
238        return Some(if timeline.is_empty() || source.is_empty() {
239            Vec::new()
240        } else {
241            vec![timeline]
242        });
243    }
244    let mut ranges: Vec<TimeRange> = Vec::new();
245    for (from, to, direction) in monotone_stretches(timeline, source, time_map)? {
246        let (first, last) = match direction {
247            Direction::Rising => (
248                first_reached(from, to, |tick| shown(tick) >= low),
249                first_reached(from, to, |tick| shown(tick) >= high),
250            ),
251            Direction::Falling => (
252                first_reached(from, to, |tick| shown(tick) < high),
253                first_reached(from, to, |tick| shown(tick) < low),
254            ),
255            Direction::Still => {
256                if (low..high).contains(&shown(from)) {
257                    (from, to)
258                } else {
259                    (from, from)
260                }
261            }
262        };
263        if first < last {
264            let range = TimeRange::new(MediaTime(first), MediaTime(last)).ok()?;
265            match ranges.last_mut() {
266                Some(previous) if previous.end() == range.start() => {
267                    *previous = TimeRange::new(previous.start(), range.end()).ok()?;
268                }
269                _ => ranges.push(range),
270            }
271        }
272    }
273    Some(ranges)
274}
275
276/// The timeline times at which a clip's picture reaches source time `instant`: per stretch over
277/// which the shown time moves one way, the first tick at which it has reached `instant` in that
278/// stretch's direction, if the stretch passes it. A freeze passes nothing.
279#[must_use]
280pub fn source_instant_to_timeline(
281    timeline: TimeRange,
282    source: TimeRange,
283    time_map: TimeMap,
284    frame_rate: FrameRate,
285    instant: MediaTime,
286) -> Option<Vec<MediaTime>> {
287    let shown = |tick: i64| {
288        picture_source_time(timeline, source, time_map, frame_rate, MediaTime(tick))
289            .map_or(i64::MIN, MediaTime::ticks)
290    };
291    let at = instant.ticks();
292    let mut times = Vec::new();
293    for (from, to, direction) in monotone_stretches(timeline, source, time_map)? {
294        let found = match direction {
295            Direction::Rising if shown(from) <= at => {
296                first_reached(from, to, |tick| shown(tick) >= at)
297            }
298            Direction::Falling if shown(from) >= at => {
299                first_reached(from, to, |tick| shown(tick) <= at)
300            }
301            _ => to,
302        };
303        if found < to {
304            times.push(MediaTime(found));
305        }
306    }
307    Some(times)
308}