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

dash_runtime/address/
plan.rs
