dash_runtime/address/
timeline.rs

1//! `SegmentTimeline` as a lazy run table (ISO/IEC 23009-1 5.3.9.6).
2//!
3//! A timeline is never expanded into one entry per segment: each `S` becomes
4//! one run `(first time, first number, duration, count)` and a segment is
5//! found by binary search. A `@r` of four billion therefore costs one run;
6//! the total is still bounded by
7//! [`crate::limits::MAX_TIMELINE_SEGMENTS`] so index arithmetic cannot
8//! overflow.
9//!
10//! Rules (5.3.9.6.1, restated in `private/specs-verified/dash/docs-specs/23009-1/05-3-9-6-segment-timeline.md`):
11//! `@t` is absolute and never smaller than the previous run's end; absent, a
12//! run starts where the previous ended (the first at 0); `@n` restarts the
13//! numbering; `@r >= 0` gives `r + 1` segments; a negative `@r` repeats up to
14//! the next `S@t`, or for the last `S` to the Period end, as
15//! `ceil((end - time) / d)` (the spec prints no rounding rule; this is the
16//! reading the workspace's former second reader used, pinned by
17//! `vectors::timeline_numbers_gaps_negative_r_and_n`).
18
19use crate::limits::MAX_TIMELINE_SEGMENTS;
20use broadcast_dash::SegmentTimeline;
21
22use super::AddressError;
23
24/// One segment of a timeline.
25#[derive(Debug, Clone, Copy, PartialEq, Eq)]
26#[non_exhaustive]
27pub struct TimelineSegment {
28    /// `$Number$`.
29    pub number: u64,
30    /// Start on the media timeline in `@timescale` ticks (`$Time$`).
31    pub time: u64,
32    /// Duration in ticks.
33    pub duration: u64,
34}
35
36#[derive(Debug, Clone, Copy)]
37struct Run {
38    first_index: u64,
39    time: u64,
40    number: u64,
41    d: u64,
42    count: u64,
43    tail: u64,
44}
45
46/// The lazily expanded timeline.
47#[derive(Debug, Clone, Default)]
48pub struct TimelineIndex {
49    runs: Vec<Run>,
50    total: u64,
51}
52
53/// Tolerance, in `@timescale` ticks, applied to a declared `@t` that falls
54/// slightly below the computed end of the previous run: DASH 5.3.9.6.1
55/// requires `@t` to be at least that end, but nominal durations on the last
56/// Segment of a run can overshoot the real boundary by one tick, so a
57/// one-tick shortfall is trusted rather than rejected.
58const TIMELINE_T_TOLERANCE_TICKS: u64 = 1;
59
60impl TimelineIndex {
61    /// Build the run table.
62    ///
63    /// `period_end_ticks` is on the media timeline (`PTO + (PEwc - PSwc)`),
64    /// used by a trailing negative `@r`; `None` makes such a run a single
65    /// segment.
66    ///
67    /// # Errors
68    /// [`AddressError`] for a non-increasing `@t`/`@n`, an oversized or
69    /// overflowing timeline, or an unsupported feature.
70    pub fn build(
71        timeline: &SegmentTimeline,
72        start_number: u64,
73        period_end_ticks: Option<u64>,
74    ) -> Result<Self, AddressError> {
75        if let Some(u) = timeline.unsupported {
76            return Err(AddressError::Unsupported(u));
77        }
78        let entries = &timeline.entries;
79        let mut runs = Vec::with_capacity(entries.len());
80        let mut time: u64 = 0;
81        let mut number = start_number;
82        let mut total: u64 = 0;
83        for (i, s) in entries.iter().enumerate() {
84            if s.d == 0 {
85                return Err(AddressError::ZeroSegmentDuration);
86            }
87            if let Some(t) = s.t {
88                if time.saturating_sub(t) > TIMELINE_T_TOLERANCE_TICKS {
89                    return Err(AddressError::TimelineNotIncreasing { t, floor: time });
90                }
91                time = t;
92            }
93            if let Some(n) = s.n {
94                if n < number {
95                    return Err(AddressError::NumberNotIncreasing {
96                        n,
97                        expected: number,
98                    });
99                }
100                number = n;
101            }
102            let count = if s.r >= 0 {
103                s.r.unsigned_abs().saturating_add(1)
104            } else {
105                let next_t = entries.get(i + 1).and_then(|n| n.t);
106                if let Some(next_t) = next_t
107                    && time.saturating_sub(next_t) > TIMELINE_T_TOLERANCE_TICKS
108                {
109                    return Err(AddressError::TimelineNotIncreasing {
110                        t: next_t,
111                        floor: time,
112                    });
113                }
114                match next_t.or(period_end_ticks) {
115                    Some(end) => end.saturating_sub(time).div_ceil(s.d),
116                    None => 1,
117                }
118            };
119            if count > MAX_TIMELINE_SEGMENTS || total.saturating_add(count) > MAX_TIMELINE_SEGMENTS
120            {
121                return Err(AddressError::TimelineTooLong {
122                    count_hint: total.saturating_add(count),
123                });
124            }
125            let cut_at_next = s.r < 0 && entries.get(i + 1).is_some_and(|n| n.t.is_some());
126            if count > 0 {
127                let tail = match entries.get(i + 1).and_then(|n| n.t) {
128                    Some(next_t) if cut_at_next => {
129                        let last_start = time.saturating_add(s.d.saturating_mul(count - 1));
130                        next_t.saturating_sub(last_start).clamp(1, s.d)
131                    }
132                    _ => s.d,
133                };
134                runs.push(Run {
135                    first_index: total,
136                    time,
137                    number,
138                    d: s.d,
139                    count,
140                    tail,
141                });
142            }
143            if i + 1 < entries.len() {
144                time = if cut_at_next {
145                    entries[i + 1].t.unwrap_or(time)
146                } else {
147                    let span = s.d.checked_mul(count).ok_or(AddressError::Overflow)?;
148                    time.checked_add(span).ok_or(AddressError::Overflow)?
149                };
150            }
151            number = number.saturating_add(count);
152            total += count;
153        }
154        Ok(Self { runs, total })
155    }
156
157    /// Number of segments.
158    #[must_use]
159    pub fn len(&self) -> u64 {
160        self.total
161    }
162
163    /// Whether the timeline has no segment.
164    #[must_use]
165    pub fn is_empty(&self) -> bool {
166        self.total == 0
167    }
168
169    /// Segment at zero-based `index`.
170    #[must_use]
171    pub fn segment(&self, index: u64) -> Option<TimelineSegment> {
172        if index >= self.total {
173            return None;
174        }
175        let at = self.runs.partition_point(|r| r.first_index <= index) - 1;
176        let run = self.runs[at];
177        let k = index - run.first_index;
178        Some(TimelineSegment {
179            number: run.number.saturating_add(k),
180            time: run.time.saturating_add(k.saturating_mul(run.d)),
181            duration: if k + 1 == run.count { run.tail } else { run.d },
182        })
183    }
184
185    /// Index of the last segment whose start is at or before `time` (media
186    /// timeline ticks); `None` when `time` precedes the first segment.
187    #[must_use]
188    pub fn index_at_or_before(&self, time: u64) -> Option<u64> {
189        let at = self.runs.partition_point(|r| r.time <= time);
190        if at == 0 {
191            return None;
192        }
193        let run = self.runs[at - 1];
194        let k = ((time - run.time) / run.d).min(run.count - 1);
195        Some(run.first_index + k)
196    }
197
198    /// How many segments have a number at or below `max_number`
199    /// (`@endNumber`: a segment numbered above it is invalid, 5.3.9.5.3).
200    #[must_use]
201    pub fn count_up_to_number(&self, max_number: u64) -> u64 {
202        let mut count = 0u64;
203        for run in &self.runs {
204            if run.number > max_number {
205                break;
206            }
207            let fit = (max_number - run.number).saturating_add(1);
208            count += fit.min(run.count);
209            if fit < run.count {
210                break;
211            }
212        }
213        count
214    }
215
216    /// The segments in order (lazy).
217    pub fn iter(&self) -> impl Iterator<Item = TimelineSegment> + '_ {
218        (0..self.total).filter_map(|i| self.segment(i))
219    }
220}
dash_runtime/address/timeline.rs

dash_runtime/address/
timeline.rs
