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//! `transmux::SegmentTimeline::resolve` reading, which the differential test
17//! holds this to).
18
19use crate::limits::MAX_TIMELINE_SEGMENTS;
20use crate::mpd::model::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}
44
45/// The lazily expanded timeline.
46#[derive(Debug, Clone, Default)]
47pub struct TimelineIndex {
48    runs: Vec<Run>,
49    total: u64,
50}
51
52/// Tolerance, in `@timescale` ticks, applied to a declared `@t` that falls
53/// slightly below the computed end of the previous run: DASH 5.3.9.6.1
54/// requires `@t` to be at least that end, but nominal durations on the last
55/// Segment of a run can overshoot the real boundary by one tick, so a
56/// one-tick shortfall is trusted rather than rejected.
57const TIMELINE_T_TOLERANCE_TICKS: u64 = 1;
58
59impl TimelineIndex {
60    /// Build the run table.
61    ///
62    /// `period_end_ticks` is on the media timeline (`PTO + (PEwc - PSwc)`),
63    /// used by a trailing negative `@r`; `None` makes such a run a single
64    /// segment.
65    ///
66    /// # Errors
67    /// [`AddressError`] for a non-increasing `@t`/`@n`, an oversized or
68    /// overflowing timeline, or an unsupported feature.
69    pub fn build(
70        timeline: &SegmentTimeline,
71        start_number: u64,
72        period_end_ticks: Option<u64>,
73    ) -> Result<Self, AddressError> {
74        if let Some(u) = timeline.unsupported {
75            return Err(AddressError::Unsupported(u));
76        }
77        let entries = &timeline.entries;
78        let mut runs = Vec::with_capacity(entries.len());
79        let mut time: u64 = 0;
80        let mut number = start_number;
81        let mut total: u64 = 0;
82        for (i, s) in entries.iter().enumerate() {
83            if s.d == 0 {
84                return Err(AddressError::ZeroSegmentDuration);
85            }
86            if let Some(t) = s.t {
87                if time.saturating_sub(t) > TIMELINE_T_TOLERANCE_TICKS {
88                    return Err(AddressError::TimelineNotIncreasing { t, floor: time });
89                }
90                time = t;
91            }
92            if let Some(n) = s.n {
93                if n < number {
94                    return Err(AddressError::NumberNotIncreasing {
95                        n,
96                        expected: number,
97                    });
98                }
99                number = n;
100            }
101            let count = if s.r >= 0 {
102                s.r.unsigned_abs().saturating_add(1)
103            } else {
104                let next_t = entries.get(i + 1).and_then(|n| n.t);
105                if let Some(next_t) = next_t
106                    && time.saturating_sub(next_t) > TIMELINE_T_TOLERANCE_TICKS
107                {
108                    return Err(AddressError::TimelineNotIncreasing {
109                        t: next_t,
110                        floor: time,
111                    });
112                }
113                match next_t.or(period_end_ticks) {
114                    Some(end) => end.saturating_sub(time).div_ceil(s.d),
115                    None => 1,
116                }
117            };
118            if count > MAX_TIMELINE_SEGMENTS || total.saturating_add(count) > MAX_TIMELINE_SEGMENTS
119            {
120                return Err(AddressError::TimelineTooLong {
121                    count_hint: total.saturating_add(count),
122                });
123            }
124            if count > 0 {
125                runs.push(Run {
126                    first_index: total,
127                    time,
128                    number,
129                    d: s.d,
130                    count,
131                });
132            }
133            let span = s.d.checked_mul(count).ok_or(AddressError::Overflow)?;
134            let cut_at_next = s.r < 0 && entries.get(i + 1).is_some_and(|n| n.t.is_some());
135            time = if cut_at_next {
136                entries[i + 1].t.unwrap_or(time)
137            } else {
138                time.checked_add(span).ok_or(AddressError::Overflow)?
139            };
140            number = number.saturating_add(count);
141            total += count;
142        }
143        Ok(Self { runs, total })
144    }
145
146    /// Number of segments.
147    #[must_use]
148    pub fn len(&self) -> u64 {
149        self.total
150    }
151
152    /// Whether the timeline has no segment.
153    #[must_use]
154    pub fn is_empty(&self) -> bool {
155        self.total == 0
156    }
157
158    /// Segment at zero-based `index`.
159    #[must_use]
160    pub fn segment(&self, index: u64) -> Option<TimelineSegment> {
161        if index >= self.total {
162            return None;
163        }
164        let at = self.runs.partition_point(|r| r.first_index <= index) - 1;
165        let run = self.runs[at];
166        let k = index - run.first_index;
167        Some(TimelineSegment {
168            number: run.number.saturating_add(k),
169            time: run.time.saturating_add(k.saturating_mul(run.d)),
170            duration: run.d,
171        })
172    }
173
174    /// Index of the last segment whose start is at or before `time` (media
175    /// timeline ticks); `None` when `time` precedes the first segment.
176    #[must_use]
177    pub fn index_at_or_before(&self, time: u64) -> Option<u64> {
178        let at = self.runs.partition_point(|r| r.time <= time);
179        if at == 0 {
180            return None;
181        }
182        let run = self.runs[at - 1];
183        let k = ((time - run.time) / run.d).min(run.count - 1);
184        Some(run.first_index + k)
185    }
186
187    /// How many segments have a number at or below `max_number`
188    /// (`@endNumber`: a segment numbered above it is invalid, 5.3.9.5.3).
189    #[must_use]
190    pub fn count_up_to_number(&self, max_number: u64) -> u64 {
191        let mut count = 0u64;
192        for run in &self.runs {
193            if run.number > max_number {
194                break;
195            }
196            let fit = (max_number - run.number).saturating_add(1);
197            count += fit.min(run.count);
198            if fit < run.count {
199                break;
200            }
201        }
202        count
203    }
204
205    /// The segments in order (lazy).
206    pub fn iter(&self) -> impl Iterator<Item = TimelineSegment> + '_ {
207        (0..self.total).filter_map(|i| self.segment(i))
208    }
209}
dash_runtime/address/timeline.rs

dash_runtime/address/
timeline.rs
