dash_runtime/address/
plan.rs

1//! The lazy Segment plan of one Representation within one Period.
2//!
3//! Formulas (all integer, `i128` microseconds; ticks via `@timescale`, which
4//! defaults to 1):
5//!
6//! * `$Number$` with `@duration`: `MPDstart(n) = (n - startNumber) * d`,
7//!   `n = startNumber + k - 1` (5.3.9.5.3; the printed `(kstart-1)` variant
8//!   is a misprint settled by the real captures, DESIGN section 11 item 1).
9//!   The last segment of a Period is `PeriodEnd - start` (A.3.3 case 1);
10//!   `@endNumber` caps the count; neither `@duration` nor a timeline is one
11//!   segment starting at 0 (A.3.3 case 3).
12//! * Timeline: `$Time$` is the raw `S@t` (decision D3: the standard's three
13//!   statements disagree when `@presentationTimeOffset != 0`); the
14//!   Period-relative start is `(time - PTO) / timescale` (5.3.9.6.1).
15//! * Availability (dynamic only): [`crate::timing::availability`].
16
17use transmux::SegmentIndexBox;
18
19use super::AddressError;
20use super::base_index::{self, IndexedSegment};
21use super::list;
22use super::template::{self, TemplateFault, TemplateUse};
23use super::timeline::TimelineIndex;
24use crate::error::Unsupported;
25use crate::mpd::inherit::{ListInfo, ResolvedMulti, SegmentInfo, TemplateInfo};
26use crate::mpd::model::{BaseInfo, ByteRange, UrlType};
27use crate::timing::availability::{
28    init_available_from, segment_available_from_ticks, segment_available_until_ticks, ticks_to_us,
29};
30
31const MICROS: i128 = 1_000_000;
32
33fn us_to_ticks_ceil(us: i128, timescale: u64) -> u64 {
34    let n = us.max(0).saturating_mul(i128::from(timescale));
35    let t = n.div_euclid(MICROS) + i128::from(n.rem_euclid(MICROS) != 0);
36    u64::try_from(t).unwrap_or(u64::MAX)
37}
38
39/// What a dynamic MPD adds to the plan.
40#[derive(Debug, Clone, PartialEq, Eq)]
41#[non_exhaustive]
42pub struct DynamicContext {
43    /// `MPD@availabilityStartTime` as Unix microseconds.
44    pub availability_start_us: i128,
45    /// The effective `@timeShiftBufferDepth` (Representation level over MPD
46    /// level), microseconds; `None` means unbounded.
47    pub time_shift_buffer_depth_us: Option<i128>,
48    /// Sum of `@availabilityTimeOffset` over every level that built the URL,
49    /// microseconds; zero unless the caller opted into early requests.
50    pub availability_time_offset_us: i128,
51    /// `FetchTime + minimumUpdatePeriod` in UTC microseconds: where a trailing
52    /// negative `@r` runs to when the Period has no known end (A.3.2).
53    pub horizon_utc_us: Option<i128>,
54}
55
56impl DynamicContext {
57    /// A context with no ATO and no horizon.
58    #[must_use]
59    pub fn new(availability_start_us: i128, time_shift_buffer_depth_us: Option<i128>) -> Self {
60        Self {
61            availability_start_us,
62            time_shift_buffer_depth_us,
63            availability_time_offset_us: 0,
64            horizon_utc_us: None,
65        }
66    }
67}
68
69/// Everything [`SegmentPlan::build`] needs.
70#[derive(Debug, Clone)]
71#[non_exhaustive]
72pub struct PlanInput<'a> {
73    /// `Representation@id` (`$RepresentationID$`).
74    pub representation_id: &'a str,
75    /// `Representation@bandwidth` (`$Bandwidth$`).
76    pub bandwidth: u64,
77    /// The resolved Segment information.
78    pub info: &'a SegmentInfo,
79    /// PeriodStart in microseconds from the presentation start.
80    pub period_start_us: i128,
81    /// The Period end in the same domain, when known.
82    pub period_end_us: Option<i128>,
83    /// Dynamic-MPD context; `None` for a static MPD.
84    pub dynamic: Option<DynamicContext>,
85    /// The parsed `sidx` and the anchor offset (SegmentBase only).
86    pub index: Option<(&'a SegmentIndexBox, u64)>,
87}
88
89impl<'a> PlanInput<'a> {
90    /// A static plan starting at 0 with no known end.
91    #[must_use]
92    pub fn new(representation_id: &'a str, bandwidth: u64, info: &'a SegmentInfo) -> Self {
93        Self {
94            representation_id,
95            bandwidth,
96            info,
97            period_start_us: 0,
98            period_end_us: None,
99            dynamic: None,
100            index: None,
101        }
102    }
103}
104
105/// One Media Segment.
106#[derive(Debug, Clone, PartialEq, Eq)]
107#[non_exhaustive]
108pub struct SegmentRef {
109    /// Zero-based position in the plan.
110    pub index: u64,
111    /// `$Number$`.
112    pub number: u64,
113    /// `$Time$` value in ticks.
114    pub time_ticks: u64,
115    /// Duration in ticks.
116    pub duration_ticks: u64,
117    /// Ticks per second.
118    pub timescale: u64,
119    /// Start relative to the Period start, microseconds
120    /// (`(time - PTO) / timescale` for a timeline).
121    pub start_us: i128,
122    /// Duration in microseconds.
123    pub duration_us: i128,
124    /// The URL reference to resolve against the BaseURL chain; empty means the
125    /// BaseURL itself.
126    pub reference: String,
127    /// The byte range, when the segment is a part of a file.
128    pub byte_range: Option<ByteRange>,
129    /// Availability start (dynamic MPD).
130    pub available_from_us: Option<i128>,
131    /// Availability end (dynamic MPD with a time-shift buffer).
132    pub available_until_us: Option<i128>,
133}
134
135/// An Initialization or Index Segment address.
136#[derive(Debug, Clone, PartialEq, Eq)]
137#[non_exhaustive]
138pub struct ResourceRef {
139    /// URL reference (empty: the BaseURL itself).
140    pub reference: String,
141    /// Byte range.
142    pub byte_range: Option<ByteRange>,
143    /// Availability start (dynamic MPD).
144    pub available_from_us: Option<i128>,
145    /// Availability end: that of the last Media Segment.
146    pub available_until_us: Option<i128>,
147}
148
149#[derive(Debug, Clone)]
150struct Fixed {
151    number: u64,
152    time: u64,
153    start_ticks: i128,
154    duration: u64,
155    reference: String,
156    range: Option<ByteRange>,
157}
158
159#[derive(Debug, Clone)]
160enum Kind {
161    Duration {
162        d: u64,
163        start_number: u64,
164        count: Option<u64>,
165        last_duration: u64,
166    },
167    Timeline(TimelineIndex),
168    Fixed(Vec<Fixed>),
169}
170
171#[derive(Debug, Clone)]
172struct Avail {
173    ast_us: i128,
174    ato_us: i128,
175    tsb_us: Option<i128>,
176}
177
178#[derive(Debug, Clone)]
179struct MediaTemplate {
180    template: String,
181    representation_id: String,
182    bandwidth: u64,
183}
184
185/// The ordered Media Segments of one Representation in one Period.
186#[derive(Debug, Clone)]
187pub struct SegmentPlan {
188    kind: Kind,
189    timescale: u64,
190    pto: u64,
191    period_start_us: i128,
192    avail: Option<Avail>,
193    media: Option<MediaTemplate>,
194    init: Option<(String, Option<ByteRange>)>,
195    index: Option<(String, Option<ByteRange>)>,
196    len_cap: Option<u64>,
197}
198
199fn fault(template: &str, f: TemplateFault) -> AddressError {
200    AddressError::InvalidTemplate {
201        template: template.to_owned(),
202        fault: f,
203    }
204}
205
206fn reject_sequences(used: TemplateUse) -> Result<(), AddressError> {
207    if used.sub_number {
208        Err(AddressError::Unsupported(Unsupported::SegmentSequence))
209    } else {
210        Ok(())
211    }
212}
213
214fn url_ref(u: &UrlType) -> (String, Option<ByteRange>) {
215    (u.source_url.clone().unwrap_or_default(), u.range)
216}
217
218fn period_end_media_ticks(
219    multi: &ResolvedMulti,
220    input: &PlanInput<'_>,
221    period_duration_ticks: Option<u64>,
222) -> Option<u64> {
223    let pto = multi.presentation_time_offset;
224    if let Some(pd) = period_duration_ticks {
225        return Some(pd.saturating_add(pto));
226    }
227    let dynamic = input.dynamic.as_ref()?;
228    let horizon = dynamic.horizon_utc_us?;
229    let rel = horizon
230        .saturating_sub(dynamic.availability_start_us)
231        .saturating_sub(input.period_start_us);
232    Some(us_to_ticks_ceil(rel, multi.timescale).saturating_add(pto))
233}
234
235impl SegmentPlan {
236    /// Build the plan.
237    ///
238    /// # Errors
239    /// [`AddressError`]: the Representation is to be dropped (or, for
240    /// [`AddressError::IndexRequired`], planned again once the `sidx` is
241    /// fetched).
242    pub fn build(input: &PlanInput<'_>) -> Result<Self, AddressError> {
243        let avail = input.dynamic.as_ref().map(|d| Avail {
244            ast_us: d.availability_start_us,
245            ato_us: d.availability_time_offset_us,
246            tsb_us: d.time_shift_buffer_depth_us,
247        });
248        let mut plan = match input.info {
249            SegmentInfo::Template(t) => Self::from_template(input, t)?,
250            SegmentInfo::List(l) => Self::from_list(input, l)?,
251            SegmentInfo::Base(b) => Self::from_base(input, b)?,
252        };
253        plan.avail = avail;
254        plan.period_start_us = input.period_start_us;
255        Ok(plan)
256    }
257
258    fn period_duration_us(input: &PlanInput<'_>) -> Option<i128> {
259        input
260            .period_end_us
261            .map(|e| e.saturating_sub(input.period_start_us).max(0))
262    }
263
264    fn from_template(input: &PlanInput<'_>, t: &TemplateInfo) -> Result<Self, AddressError> {
265        let media = t
266            .media
267            .as_deref()
268            .ok_or(AddressError::MissingMediaTemplate)?;
269        let used = template::scan_media(media).map_err(|f| fault(media, f))?;
270        reject_sequences(used)?;
271        let mut init = t.multi.base.initialization.as_ref().map(url_ref);
272        if let Some(tpl) = &t.initialization {
273            let used = template::scan_initialization(tpl).map_err(|f| fault(tpl, f))?;
274            reject_sequences(used)?;
275            init = Some((
276                template::substitute(tpl, input.representation_id, None, None, input.bandwidth),
277                None,
278            ));
279        }
280        let mut index = t.multi.base.representation_index.as_ref().map(url_ref);
281        if let Some(tpl) = &t.index {
282            let used = template::scan(tpl).map_err(|f| fault(tpl, f))?;
283            reject_sequences(used)?;
284            if !used.number && !used.time {
285                index = Some((
286                    template::substitute(tpl, input.representation_id, None, None, input.bandwidth),
287                    None,
288                ));
289            }
290        }
291        let m = &t.multi;
292        let ts = m.timescale;
293        let pd_us = Self::period_duration_us(input);
294        let pd_ticks = pd_us.map(|d| us_to_ticks_ceil(d, ts));
295        let (kind, len_cap) = if let Some(tl) = &m.timeline {
296            let end = period_end_media_ticks(m, input, pd_ticks);
297            let idx = TimelineIndex::build(tl, m.start_number, end)?;
298            let cap = m.end_number.map(|en| idx.count_up_to_number(en));
299            (Kind::Timeline(idx), cap)
300        } else if let Some(d) = m.duration {
301            let mut count = pd_us.map(|dur| {
302                let num = dur.saturating_mul(i128::from(ts));
303                let den = i128::from(d).saturating_mul(MICROS);
304                let c = num.div_euclid(den) + i128::from(num.rem_euclid(den) != 0);
305                u64::try_from(c).unwrap_or(u64::MAX)
306            });
307            if let Some(en) = m.end_number {
308                let cap = if en < m.start_number {
309                    0
310                } else {
311                    en.saturating_sub(m.start_number).saturating_add(1)
312                };
313                count = Some(count.map_or(cap, |c| c.min(cap)));
314            }
315            let last_duration = match (count, pd_ticks) {
316                (Some(c), Some(pd)) if c > 0 => {
317                    let full = (c - 1).saturating_mul(d);
318                    pd.saturating_sub(full).clamp(1, d)
319                }
320                _ => d,
321            };
322            (
323                Kind::Duration {
324                    d,
325                    start_number: m.start_number,
326                    count,
327                    last_duration,
328                },
329                None,
330            )
331        } else {
332            let seg = Fixed {
333                number: m.start_number,
334                time: 0,
335                start_ticks: 0,
336                duration: pd_ticks.unwrap_or(0),
337                reference: String::new(),
338                range: None,
339            };
340            (Kind::Fixed(vec![seg]), None)
341        };
342        Ok(Self {
343            kind,
344            timescale: ts,
345            pto: m.presentation_time_offset,
346            period_start_us: 0,
347            avail: None,
348            media: Some(MediaTemplate {
349                template: media.to_owned(),
350                representation_id: input.representation_id.to_owned(),
351                bandwidth: input.bandwidth,
352            }),
353            init,
354            index,
355            len_cap,
356        })
357    }
358
359    fn from_list(input: &PlanInput<'_>, l: &ListInfo) -> Result<Self, AddressError> {
360        let m = &l.multi;
361        let ts = m.timescale;
362        let pd_ticks = Self::period_duration_us(input).map(|d| us_to_ticks_ceil(d, ts));
363        let timeline = match &m.timeline {
364            Some(tl) => {
365                let end = period_end_media_ticks(m, input, pd_ticks);
366                Some(TimelineIndex::build(tl, m.start_number, end)?)
367            }
368            None => None,
369        };
370        let segs = list::expand(l, timeline.as_ref(), pd_ticks)?;
371        let pto = i128::from(m.presentation_time_offset);
372        let fixed = segs
373            .into_iter()
374            .map(|s| Fixed {
375                number: s.number,
376                time: s.time,
377                start_ticks: if timeline.is_some() {
378                    i128::from(s.time) - pto
379                } else {
380                    i128::from(s.time)
381                },
382                duration: s.duration,
383                reference: s.reference,
384                range: s.range,
385            })
386            .collect();
387        Ok(Self {
388            kind: Kind::Fixed(fixed),
389            timescale: ts,
390            pto: m.presentation_time_offset,
391            period_start_us: 0,
392            avail: None,
393            media: None,
394            init: m.base.initialization.as_ref().map(url_ref),
395            index: m.base.representation_index.as_ref().map(url_ref),
396            len_cap: None,
397        })
398    }
399
400    fn from_base(input: &PlanInput<'_>, b: &BaseInfo) -> Result<Self, AddressError> {
401        let init = b.initialization.as_ref().map(url_ref);
402        let index = b
403            .representation_index
404            .as_ref()
405            .map(url_ref)
406            .or_else(|| b.index_range.map(|r| (String::new(), Some(r))));
407        let pto = b.presentation_time_offset.unwrap_or(0);
408        let base_ts = b.timescale.unwrap_or(1);
409        if let Some(r) = &b.index_range {
410            let (sidx, anchor) = input.index.ok_or(AddressError::IndexRequired)?;
411            let _ = base_index::anchor_after(r)?;
412            let ts = u64::from(sidx.timescale).max(1);
413            let segs: Vec<IndexedSegment> = base_index::segments(sidx, anchor)?;
414            let fixed = segs
415                .into_iter()
416                .enumerate()
417                .map(|(i, s)| Fixed {
418                    number: i as u64 + 1,
419                    time: s.time,
420                    start_ticks: i128::from(s.time) - i128::from(pto),
421                    duration: s.duration,
422                    reference: String::new(),
423                    range: Some(s.range),
424                })
425                .collect();
426            return Ok(Self {
427                kind: Kind::Fixed(fixed),
428                timescale: ts,
429                pto,
430                period_start_us: 0,
431                avail: None,
432                media: None,
433                init,
434                index,
435                len_cap: None,
436            });
437        }
438        let pd_ticks = Self::period_duration_us(input).map(|d| us_to_ticks_ceil(d, base_ts));
439        let seg = Fixed {
440            number: 1,
441            time: 0,
442            start_ticks: 0,
443            duration: pd_ticks.unwrap_or(0),
444            reference: String::new(),
445            range: None,
446        };
447        Ok(Self {
448            kind: Kind::Fixed(vec![seg]),
449            timescale: base_ts,
450            pto,
451            period_start_us: 0,
452            avail: None,
453            media: None,
454            init,
455            index,
456            len_cap: None,
457        })
458    }
459
460    /// `@timescale` in effect.
461    #[must_use]
462    pub fn timescale(&self) -> u64 {
463        self.timescale
464    }
465
466    /// `@presentationTimeOffset` in ticks.
467    #[must_use]
468    pub fn presentation_time_offset(&self) -> u64 {
469        self.pto
470    }
471
472    /// PeriodStart in microseconds.
473    #[must_use]
474    pub fn period_start_us(&self) -> i128 {
475        self.period_start_us
476    }
477
478    /// Whether availability data is attached (dynamic MPD).
479    #[must_use]
480    pub fn is_dynamic(&self) -> bool {
481        self.avail.is_some()
482    }
483
484    /// Number of segments; `None` when the plan is open-ended (a duration
485    /// template of a Period with no known end).
486    #[must_use]
487    pub fn len(&self) -> Option<u64> {
488        let raw = match &self.kind {
489            Kind::Duration { count, .. } => *count,
490            Kind::Timeline(t) => Some(t.len()),
491            Kind::Fixed(v) => Some(v.len() as u64),
492        };
493        match (raw, self.len_cap) {
494            (Some(a), Some(b)) => Some(a.min(b)),
495            (a, None) => a,
496            (None, b) => b,
497        }
498    }
499
500    /// Whether the plan has no segment.
501    #[must_use]
502    pub fn is_empty(&self) -> bool {
503        self.len() == Some(0)
504    }
505
506    fn reference(&self, number: u64, time: u64, fixed: Option<&str>) -> String {
507        match (&self.media, fixed) {
508            (Some(m), _) => template::substitute(
509                &m.template,
510                &m.representation_id,
511                Some(number),
512                Some(time),
513                m.bandwidth,
514            ),
515            (None, Some(r)) => r.to_owned(),
516            (None, None) => String::new(),
517        }
518    }
519
520    /// The segment at zero-based `index`.
521    #[must_use]
522    pub fn get(&self, index: u64) -> Option<SegmentRef> {
523        if self.len().is_some_and(|n| index >= n) {
524            return None;
525        }
526        let (number, time, start_ticks, duration, reference, range) = match &self.kind {
527            Kind::Duration {
528                d,
529                start_number,
530                count,
531                last_duration,
532            } => {
533                let start = index.checked_mul(*d)?;
534                let dur = if count.is_some_and(|c| index + 1 == c) {
535                    *last_duration
536                } else {
537                    *d
538                };
539                let number = start_number.saturating_add(index);
540                (
541                    number,
542                    start,
543                    i128::from(start),
544                    dur,
545                    self.reference(number, start, None),
546                    None,
547                )
548            }
549            Kind::Timeline(t) => {
550                let s = t.segment(index)?;
551                (
552                    s.number,
553                    s.time,
554                    i128::from(s.time) - i128::from(self.pto),
555                    s.duration,
556                    self.reference(s.number, s.time, None),
557                    None,
558                )
559            }
560            Kind::Fixed(v) => {
561                let f = v.get(usize::try_from(index).ok()?)?;
562                (
563                    f.number,
564                    f.time,
565                    f.start_ticks,
566                    f.duration,
567                    self.reference(f.number, f.time, Some(&f.reference)),
568                    f.range,
569                )
570            }
571        };
572        let start_us = ticks_to_us(start_ticks, self.timescale);
573        let duration_us = ticks_to_us(i128::from(duration), self.timescale);
574        let (available_from_us, available_until_us) = match &self.avail {
575            Some(a) => (
576                Some(segment_available_from_ticks(
577                    a.ast_us,
578                    self.period_start_us,
579                    start_ticks,
580                    i128::from(duration),
581                    self.timescale,
582                    a.ato_us,
583                )),
584                segment_available_until_ticks(
585                    a.ast_us,
586                    self.period_start_us,
587                    start_ticks,
588                    i128::from(duration),
589                    self.timescale,
590                    a.tsb_us,
591                ),
592            ),
593            None => (None, None),
594        };
595        Some(SegmentRef {
596            index,
597            number,
598            time_ticks: time,
599            duration_ticks: duration,
600            timescale: self.timescale,
601            start_us,
602            duration_us,
603            reference,
604            byte_range: range,
605            available_from_us,
606            available_until_us,
607        })
608    }
609
610    /// The segments in order. For an open-ended plan this never ends; bound it
611    /// with `take`.
612    pub fn iter(&self) -> impl Iterator<Item = SegmentRef> + '_ {
613        let mut i = 0u64;
614        std::iter::from_fn(move || {
615            let r = self.get(i)?;
616            i += 1;
617            Some(r)
618        })
619    }
620
621    /// The Initialization Segment address, with its availability window.
622    #[must_use]
623    pub fn init(&self) -> Option<ResourceRef> {
624        self.init
625            .as_ref()
626            .map(|(reference, range)| self.resource(reference, *range))
627    }
628
629    /// The Index Segment address (the `sidx` of a SegmentBase Representation,
630    /// or a `RepresentationIndex`).
631    #[must_use]
632    pub fn index(&self) -> Option<ResourceRef> {
633        self.index
634            .as_ref()
635            .map(|(reference, range)| self.resource(reference, *range))
636    }
637
638    fn resource(&self, reference: &str, range: Option<ByteRange>) -> ResourceRef {
639        let from = self
640            .avail
641            .as_ref()
642            .map(|a| init_available_from(a.ast_us, self.period_start_us));
643        let until = self
644            .len()
645            .and_then(|n| n.checked_sub(1))
646            .and_then(|last| self.get(last))
647            .and_then(|s| s.available_until_us);
648        ResourceRef {
649            reference: reference.to_owned(),
650            byte_range: range,
651            available_from_us: from,
652            available_until_us: until,
653        }
654    }
655
656    /// Index of the last segment whose Period-relative start is at or before
657    /// `period_time_us`; `None` before the first segment.
658    #[must_use]
659    pub fn index_at_or_before(&self, period_time_us: i128) -> Option<u64> {
660        let n = self.len();
661        let (mut lo, mut hi) = (0u64, n.unwrap_or(u64::MAX / 2));
662        while lo < hi {
663            let mid = lo + (hi - lo) / 2;
664            match self.get(mid) {
665                Some(s) if s.start_us <= period_time_us => lo = mid + 1,
666                Some(_) => hi = mid,
667                None => hi = mid,
668            }
669        }
670        lo.checked_sub(1)
671    }
672
673    /// Availability start of the segment at `index`.
674    #[must_use]
675    pub fn available_from_us(&self, index: u64) -> Option<i128> {
676        self.get(index)?.available_from_us
677    }
678
679    /// Availability end of the segment at `index`.
680    #[must_use]
681    pub fn available_until_us(&self, index: u64) -> Option<i128> {
682        self.get(index)?.available_until_us
683    }
684
685    /// The first index, and the number of segments, for which `pred` holds on
686    /// a monotone-in-index predicate over `[0, bound)`: the count of leading
687    /// indices where `pred` is true.
688    pub(crate) fn leading_true(&self, bound: u64, pred: impl Fn(&SegmentRef) -> bool) -> u64 {
689        let (mut lo, mut hi) = (0u64, bound);
690        while lo < hi {
691            let mid = lo + (hi - lo) / 2;
692            match self.get(mid) {
693                Some(s) if pred(&s) => lo = mid + 1,
694                _ => hi = mid,
695            }
696        }
697        lo
698    }
699
700    pub(crate) fn constant_duration(&self) -> Option<u64> {
701        match &self.kind {
702            Kind::Duration { d, .. } => Some(*d),
703            _ => None,
704        }
705    }
706
707    pub(crate) fn avail_parts(&self) -> Option<(i128, i128)> {
708        self.avail.as_ref().map(|a| (a.ast_us, a.ato_us))
709    }
710}
dash_runtime/address/plan.rs

dash_runtime/address/
plan.rs
