//! Adaptation (http-delivery Appendix F, informative): reference policies that choose
//! among options of increasing size from measured delivery — throughput, a buffer
//! level, a utility-over-buffer rule and a short look-ahead — in integer arithmetic
//! only, so every platform chooses the same, and corpus vectors pin each choice.
//!
//! They act in two places, both deployer policy and never a change to what a sink may
//! decode:
//!
//! - [`order_entries`] reorders the selectable entries of one `WAI2` by size within
//!   each capability, putting the policy's choice first (SPEC §7.1 step 2 lets a
//!   deployer order entries); selection then runs unchanged on the head and on the
//!   whole envelope, so the pick is the same on every path (§7.2);
//! - [`depth`] chooses how many layer objects (§10.4) a client fetches over a base.
//!
//! An option's energy enters only as a figure a receipt labels with its acquisition
//! class ([`labelled_figure`]); a budget only ever lowers the policy's choice, to an
//! option with a labelled figure within it, and a budget with no labelled figure to act
//! on is reported as not applied ([`Budget::NotApplied`]). Nothing here reads a clock: samples carry the
//! caller's measurements.
//!
//! Every input has the bounds Appendix F states ([`check_state`], [`Policy::check`]):
//! within them each quantity is computed exactly, in 128-bit integers and a widened
//! cross-multiplication, never saturated; beyond them a state is refused
//! (`abr_state_out_of_bounds`).

use super::head::{Head, Version};
use crate::container::ManifestV2;

/// A state or a policy beyond Appendix F's bounds (`abr_state_out_of_bounds`), with
/// what is out of bounds.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct AbrError(pub &'static str);

impl AbrError {
    pub fn code(&self) -> &'static str {
        "abr_state_out_of_bounds"
    }
}

impl std::fmt::Display for AbrError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "abr_state_out_of_bounds: {}", self.0)
    }
}

impl std::error::Error for AbrError {}

/// The most options a state holds, and the most objects (a base and its layers) a depth
/// is chosen over (Appendix F).
/// cbindgen:ignore
pub const MAX_OPTIONS: usize = 256;

/// Appendix F's bounds on a state beyond those of its fields' types (each `ms` and `u32`
/// field below 2^32, each byte count, figure and budget below 2^64): at most
/// [`MAX_OPTIONS`] options and figures.
pub fn check_state(s: &AbrState) -> Result<(), AbrError> {
    if s.option_bytes.len() > MAX_OPTIONS || s.option_joules_micro.len() > MAX_OPTIONS {
        return Err(AbrError("more options than 256"));
    }
    Ok(())
}

/// One measured request: `bytes` of body received in `ms` milliseconds, finished at
/// `at_ms` on the caller's clock.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Sample {
    pub at_ms: u64,
    pub bytes: u64,
    pub ms: u64,
}

/// What a policy chooses from.
#[derive(Clone, Debug, PartialEq, Eq, Default)]
pub struct AbrState {
    /// Media buffered ahead of the play point, in milliseconds.
    pub buffer_ms: u32,
    /// Measured requests, oldest first.
    pub samples: Vec<Sample>,
    /// The option chosen last, if any.
    pub last: Option<usize>,
    /// Each option's bytes, in increasing order: a component's `len` from the head, or
    /// the bytes through a layer depth.
    pub option_bytes: Vec<u64>,
    /// Each option's energy in microjoules, only from a receipt figure labelled with its
    /// acquisition class ([`labelled_figure`]); `None` otherwise.
    pub option_joules_micro: Vec<Option<u64>>,
    /// A budget in microjoules for one option, if the client holds one.
    pub joule_budget_micro: Option<u64>,
    /// The media duration one option covers, in milliseconds.
    pub segment_ms: u32,
}

/// A policy: a pure function from the state to an option index.
pub trait Policy {
    /// The policy's identifier, as the vectors name it.
    fn id(&self) -> &'static str;
    /// The option chosen, before any budget: an index into `option_bytes` (0 when
    /// there are none). Exact for every value of the state's field types.
    fn choose(&self, s: &AbrState) -> usize;
    /// Appendix F's bounds on the policy's parameters beyond their types; none for the
    /// reference policies, whose every parameter value is in bounds.
    fn check(&self) -> Result<(), AbrError> {
        Ok(())
    }
}

/// The highest option whose rate fits the measured throughput, less a safety margin.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Throughput {
    pub last_n: u8,
    pub safety_permille: u16,
}

/// The lowest option while the buffer is at or below the reservoir, the highest once it
/// reaches the reservoir and the cushion, and in between the highest option under a rate
/// rising linearly from the lowest option's to the highest's.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct BufferBased {
    pub reservoir_ms: u32,
    pub cushion_ms: u32,
}

/// A utility-over-buffer rule in the manner of BOLA: each option's utility is the log
/// of its size over the smallest's, and the option with the best ratio of
/// `V·(utility + 1) − buffer` to its size is chosen, `V` set by `v_milli` and
/// `max_buffer_ms`. It is not the published algorithm: where that one waits (no option
/// scores above zero), this one chooses the option closest to scoring, so it always
/// returns an option.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct BolaLike {
    pub v_milli: u32,
    pub max_buffer_ms: u32,
}

/// A look-ahead: every sequence of `horizon` choices (fewer when the options are many)
/// is played against the measured throughput less a margin, scored by utility, less
/// stalls and less changes of utility, and the first choice of the best sequence is
/// taken.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Mpc {
    pub horizon: u8,
    pub safety_permille: u16,
}

/// What a joule budget did to a choice.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Budget {
    /// No budget is held.
    NotSet,
    /// No option has a labelled figure: the budget is not applied, and the choice
    /// stands.
    NotApplied,
    /// The chosen option's labelled figure is within the budget.
    Within,
    /// The choice was lowered to the highest option below it with a labelled figure
    /// within the budget.
    Lowered,
    /// No option at or below the choice has a labelled figure within the budget: the
    /// lowest option, option 0, and the budget is not met. A budget never raises the
    /// choice.
    Unmet,
}

impl Budget {
    /// `not_set`, `not_applied`, `within`, `lowered` or `unmet`.
    pub fn label(self) -> &'static str {
        match self {
            Budget::NotSet => "not_set",
            Budget::NotApplied => "not_applied",
            Budget::Within => "within",
            Budget::Lowered => "lowered",
            Budget::Unmet => "unmet",
        }
    }
}

/// `round(65536 · log2(1 + i/16))` for `i` in `0..=16`.
///
/// cbindgen:ignore
pub const LOG2_TABLE: [u64; 17] = [0, 5732, 11136, 16248, 21098, 25711, 30109, 34312, 38336, 42196, 45904, 49472, 52911, 56229, 59434, 62534, 65536];

/// `log2(a / b)` in Q16 (×65536), 0 when `a ≤ b` (`b` taken as at least 1): the ratio
/// `x = ⌊65536·a/b⌋`, its exponent `e = ⌊log2 x⌋ − 16`, the mantissa `m = x >> e` in
/// `[65536, 131072)`, and `e·65536` plus [`LOG2_TABLE`] interpolated linearly on the
/// mantissa's top four fractional bits, its next twelve the weight, rounded down.
pub fn ilog2_q16(a: u64, b: u64) -> u64 {
    let b = b.max(1);
    if a <= b {
        return 0;
    }
    let x = (u128::from(a) << 16) / u128::from(b);
    let e = (127 - x.leading_zeros()) as u64 - 16;
    let f = ((x >> e) - 65536) as u64;
    let (i, r) = ((f >> 12) as usize, f & 4095);
    e * 65536 + LOG2_TABLE[i] + (((LOG2_TABLE[i + 1] - LOG2_TABLE[i]) * r) >> 12)
}

/// The throughput the last `n` samples give, in bits per second: `⌊8000·Σbytes / Σms⌋`,
/// each sample's `ms` taken as at least 1; 0 with no sample. `n` 0 is taken as 1. Exact:
/// at most 255 samples of at most 2^64 − 1 bytes, below 2^85.
pub fn throughput_bps(samples: &[Sample], n: u8) -> u128 {
    let k = usize::from(n.max(1)).min(samples.len());
    let tail = &samples[samples.len() - k..];
    let (b, t) = tail.iter().fold((0u128, 0u128), |(b, t), s| (b + u128::from(s.bytes), t + u128::from(s.ms.max(1))));
    if t == 0 {
        return 0;
    }
    b * 8000 / t
}

/// An option's rate in bits per second: `⌈8000·bytes / segment_ms⌉`, `segment_ms` taken
/// as at least 1. Exact: below 2^77.
pub fn option_bps(bytes: u64, segment_ms: u32) -> u128 {
    (u128::from(bytes) * 8000).div_ceil(u128::from(segment_ms.max(1)))
}

/// The highest index whose rate is at most `budget_bps`; 0 when none is.
fn highest_under(s: &AbrState, budget_bps: u128) -> usize {
    s.option_bytes.iter().enumerate().rev().find(|(_, b)| option_bps(**b, s.segment_ms) <= budget_bps).map_or(0, |(k, _)| k)
}

/// `⌊x·p/1000⌋`, exact for `x` below 2^111.
fn permille(x: u128, p: u16) -> u128 {
    x * u128::from(p) / 1000
}

/// Whether `a·b > c·d` for `a`, `c` below 2^127 and `b`, `d` below 2^64: the products,
/// below 2^191, compared exactly in two 128-bit halves.
fn product_greater(a: u128, b: u64, c: u128, d: u64) -> bool {
    // x·y = (x_hi·2^64 + x_lo)·y, with x_lo·y < 2^128 and x_hi·y < 2^127.
    let wide = |x: u128, y: u64| -> (u128, u128) {
        let (hi, lo) = (x >> 64, x & u128::from(u64::MAX));
        let low = lo * u128::from(y);
        let mid = hi * u128::from(y);
        let (sum, carry) = low.overflowing_add(mid << 64);
        ((mid >> 64) + u128::from(carry), sum)
    };
    wide(a, b) > wide(c, d)
}

impl Policy for Throughput {
    fn id(&self) -> &'static str {
        "throughput"
    }
    fn choose(&self, s: &AbrState) -> usize {
        if s.option_bytes.is_empty() {
            return 0;
        }
        highest_under(s, permille(throughput_bps(&s.samples, self.last_n), self.safety_permille))
    }
}

impl Policy for BufferBased {
    fn id(&self) -> &'static str {
        "buffer_based"
    }
    fn choose(&self, s: &AbrState) -> usize {
        let k = s.option_bytes.len();
        if k == 0 {
            return 0;
        }
        let (b, r, c) = (u64::from(s.buffer_ms), u64::from(self.reservoir_ms), u64::from(self.cushion_ms));
        if b <= r {
            return 0;
        }
        if c == 0 || b >= r + c {
            return k - 1;
        }
        let lo = option_bps(s.option_bytes[0], s.segment_ms);
        let hi = option_bps(s.option_bytes[k - 1], s.segment_ms);
        // (hi − lo)·(b − r) is below 2^109.
        let target = lo + hi.saturating_sub(lo) * u128::from(b - r) / u128::from(c);
        highest_under(s, target)
    }
}

/// Each option's utility, `ilog2_q16(bytes, the first option's bytes)`.
fn utilities(s: &AbrState) -> Vec<u64> {
    let s0 = s.option_bytes.first().copied().unwrap_or(1).max(1);
    s.option_bytes.iter().map(|&b| ilog2_q16(b.max(1), s0)).collect()
}

impl Policy for BolaLike {
    fn id(&self) -> &'static str {
        "bola_like"
    }
    fn choose(&self, s: &AbrState) -> usize {
        let k = s.option_bytes.len();
        if k == 0 {
            return 0;
        }
        let seg = i128::from(s.segment_ms.max(1));
        let q = i128::from(s.buffer_ms) * 65536 / seg;
        let qmax = i128::from(self.max_buffer_ms) * 65536 / seg;
        let u = utilities(s);
        let u_top = i128::from(*u.iter().max().unwrap_or(&0));
        let (vn, vd) = ((qmax - 65536).max(0), u_top + 65536);
        // V_n·v·(u_k + 65536) is below 2^103, and a score below 2^77 in magnitude.
        let score: Vec<i128> = u.iter().map(|&uk| vn * i128::from(self.v_milli) * (i128::from(uk) + 65536) / (vd * 1000) - q).collect();
        let size = |i: usize| s.option_bytes[i].max(1);
        let mut best: Option<usize> = None;
        if score.iter().any(|&n| n > 0) {
            for i in (0..k).filter(|&i| score[i] > 0) {
                // score[i]/size(i) > score[b]/size(b), by cross-multiplication widened
                // past 128 bits: a score times a size reaches 2^141.
                if best.is_none_or(|b| product_greater(score[i] as u128, size(b), score[b] as u128, size(i))) {
                    best = Some(i);
                }
            }
        } else {
            for i in 0..k {
                if best.is_none_or(|b| score[i] > score[b]) {
                    best = Some(i);
                }
            }
        }
        best.unwrap_or(0)
    }
}

impl Policy for Mpc {
    fn id(&self) -> &'static str {
        "mpc"
    }
    fn choose(&self, s: &AbrState) -> usize {
        let k = s.option_bytes.len();
        let pred = permille(throughput_bps(&s.samples, 5), self.safety_permille);
        if k == 0 || pred == 0 {
            return 0;
        }
        let mut h = u32::from(self.horizon.clamp(1, 5));
        while h > 1 && (k as u128).pow(h) > 65536 {
            h -= 1;
        }
        let u = utilities(s);
        let u_top = i128::from(*u.iter().max().unwrap_or(&0));
        let seg = u128::from(s.segment_ms);
        let mut best: Option<(i128, usize)> = None;
        let total = (k as u64).pow(h);
        let mut seq = vec![0usize; h as usize];
        for code in 0..total {
            // The sequence `code` names, most significant choice first.
            let mut c = code;
            for t in (0..h as usize).rev() {
                seq[t] = (c % k as u64) as usize;
                c /= k as u64;
            }
            // Exact in 128 bits: a download below 2^77 ms, the buffer below 2^35, the
            // stall below 2^80, and the stall times the utility bound below 2^103.
            let (mut b, mut rebuf, mut qoe) = (u128::from(s.buffer_ms), 0u128, 0i128);
            let mut prev: Option<i128> = s.last.filter(|&l| l < k).map(|l| i128::from(u[l]));
            for &o in &seq {
                let dl = (u128::from(s.option_bytes[o]) * 8000).div_ceil(pred);
                if dl > b {
                    rebuf += dl - b;
                    b = 0;
                } else {
                    b -= dl;
                }
                b += seg;
                let uo = i128::from(u[o]);
                qoe += 1000 * uo;
                if let Some(p) = prev {
                    qoe -= 1000 * (uo - p).abs();
                }
                prev = Some(uo);
            }
            qoe -= rebuf as i128 * (u_top + 65536);
            if best.is_none_or(|(q, _)| qoe > q) {
                best = Some((qoe, seq[0]));
            }
        }
        best.map_or(0, |(_, o)| o)
    }
}

/// The figure a receipt states, usable for a budget only when it carries its
/// acquisition class and the two cohere: an unlabelled figure, an unmetered one, or a
/// class beside a zero figure gives `None`.
pub fn labelled_figure(joules_micro: u64, class: Option<&crate::energy_class::EnergyProvenance>) -> Option<u64> {
    (class.is_some() && joules_micro > 0 && crate::energy_class::figure_and_class_cohere(joules_micro, class)).then_some(joules_micro)
}

/// Apply the state's joule budget to `choice` (Appendix F). A budget never raises the
/// choice: unchanged when no budget is held (`not_set`), or when no option has a
/// labelled figure (`not_applied`); otherwise the highest option at or below the choice
/// whose labelled figure is within the budget — the choice itself (`within`) or one below
/// it (`lowered`) — and, when there is none, option 0 with the budget unmet (`unmet`).
/// An option is one of `option_bytes` (or the choice, with none); a figure past them
/// names no option.
pub fn clamp_to_budget(s: &AbrState, choice: usize) -> (usize, Budget) {
    let Some(b) = s.joule_budget_micro else { return (choice, Budget::NotSet) };
    let n = s.option_bytes.len().max(choice + 1);
    let fig = |k: usize| if k < n { s.option_joules_micro.get(k).copied().flatten() } else { None };
    if (0..n).all(|k| fig(k).is_none()) {
        return (choice, Budget::NotApplied);
    }
    match (0..=choice).rev().find(|&k| fig(k).is_some_and(|j| j <= b)) {
        Some(k) if k == choice => (k, Budget::Within),
        Some(k) => (k, Budget::Lowered),
        None => (0, Budget::Unmet),
    }
}

/// The policy's choice under the state's budget; refused beyond Appendix F's bounds.
pub fn decide(p: &dyn Policy, s: &AbrState) -> Result<(usize, Budget), AbrError> {
    p.check()?;
    check_state(s)?;
    Ok(clamp_to_budget(s, p.choose(s)))
}

/// How many layers to fetch over a base (§10.4, the counterpart of a MoQ subscriber's
/// layer cap): `layers_n[0]` is the base's `envelope_len` and `layers_n[k]` layer `k`'s;
/// option `k` is fetching through layer `k`, its bytes the sum through it and its energy
/// the sum of the state's per-object labelled figures through it (`None` when any is
/// unlabelled). Returns the depth (0: the base alone) and what the budget did. Refused
/// beyond Appendix F's bounds: more than [`MAX_OPTIONS`] objects, or the bytes or the
/// figure through a depth past 2^64 − 1.
pub fn depth(layers_n: &[u64], p: &dyn Policy, s: &AbrState) -> Result<(usize, Budget), AbrError> {
    p.check()?;
    check_state(s)?;
    if layers_n.len() > MAX_OPTIONS {
        return Err(AbrError("more layer objects than 256"));
    }
    let mut st = s.clone();
    let mut acc = 0u64;
    st.option_bytes = Vec::with_capacity(layers_n.len());
    for &n in layers_n {
        acc = acc.checked_add(n).ok_or(AbrError("the bytes through a depth pass 2^64 - 1"))?;
        st.option_bytes.push(acc);
    }
    st.option_joules_micro = Vec::with_capacity(layers_n.len());
    let mut fig = Some(0u64);
    for k in 0..layers_n.len() {
        fig = match (fig, s.option_joules_micro.get(k).copied().flatten()) {
            (Some(a), Some(f)) => Some(a.checked_add(f).ok_or(AbrError("the figure through a depth passes 2^64 - 1"))?),
            _ => None,
        };
        st.option_joules_micro.push(fig);
    }
    if layers_n.is_empty() {
        return Ok((0, clamp_to_budget(&st, 0).1));
    }
    Ok(clamp_to_budget(&st, p.choose(&st)))
}

/// SPEC §7.1 step 2's order for one `WAI2`, as a deployer policy: the selectable
/// entries whose capability `eligible` accepts, grouped by capability in the order each
/// first appears; within a group, the entries by component length (then table index)
/// are the options, `option_bytes` their lengths and `option_joules_micro` the state's
/// figure of each entry by its table index; the group is ordered as the policy's choice
/// under the budget, then the options below it from the nearest down, then those above
/// it from the nearest up. Every other entry follows in table order. A `WAI1` gives
/// `[0]`. Refused beyond Appendix F's bounds, a group of more than [`MAX_OPTIONS`]
/// entries among them.
pub fn order_entries(head: &Head, eligible: &dyn Fn(&str) -> bool, p: &dyn Policy, s: &AbrState) -> Result<Vec<usize>, AbrError> {
    p.check()?;
    check_state(s)?;
    if head.version != Version::Wai2 {
        return Ok(vec![0]);
    }
    match head.manifest_v2() {
        Ok(m) => order_manifest(head, &m, eligible, p, s),
        Err(_) => Ok((0..head.components.len()).collect()),
    }
}

/// [`order_entries`] with the manifest already read from `head`.
pub fn order_manifest(head: &Head, m: &ManifestV2, eligible: &dyn Fn(&str) -> bool, p: &dyn Policy, s: &AbrState) -> Result<Vec<usize>, AbrError> {
    let e = &m.renditions;
    let len = |i: usize| head.components.get(i).map_or(0, |c| c.len);
    let mut groups: Vec<(String, Vec<usize>)> = Vec::new();
    for (i, r) in e.iter().enumerate() {
        if !r.is_selectable() || !eligible(&r.capability) {
            continue;
        }
        match groups.iter_mut().find(|(c, _)| *c == r.capability) {
            Some((_, g)) => g.push(i),
            None => groups.push((r.capability.clone(), vec![i])),
        }
    }
    let mut order = Vec::with_capacity(e.len());
    for (_, mut g) in groups {
        g.sort_by_key(|&i| (len(i), i));
        let mut st = s.clone();
        st.option_bytes = g.iter().map(|&i| len(i)).collect();
        st.option_joules_micro = g.iter().map(|&i| s.option_joules_micro.get(i).copied().flatten()).collect();
        let (c, _) = decide(p, &st)?;
        let c = c.min(g.len() - 1);
        order.push(g[c]);
        order.extend(g[..c].iter().rev());
        order.extend(&g[c + 1..]);
    }
    let rest: Vec<usize> = (0..e.len()).filter(|i| !order.contains(i)).collect();
    order.extend(rest);
    Ok(order)
}

/// A [`super::session::Selector`] order from a policy and a state: [`order_manifest`]
/// over the head the session verified, on both paths. Refused when the policy or the
/// state is beyond Appendix F's bounds; a head whose group passes them keeps table
/// order, on which selection runs unchanged.
pub fn selector_order(
    p: Box<dyn Policy>,
    s: AbrState,
    eligible: impl Fn(&str) -> bool + 'static,
) -> Result<Box<dyn Fn(&Head, &ManifestV2) -> Vec<usize>>, AbrError> {
    p.check()?;
    check_state(&s)?;
    Ok(Box::new(move |h: &Head, m: &ManifestV2| order_manifest(h, m, &eligible, p.as_ref(), &s).unwrap_or_else(|_| (0..m.renditions.len()).collect())))
}

#[cfg(test)]
mod tests {
    use super::*;

    /// The widened cross-multiplication against products small enough for 128 bits, and
    /// at the widths the utility-over-buffer rule reaches, where 128 bits wrap.
    #[test]
    fn product_greater_is_exact_past_128_bits() {
        for (a, b, c, d) in [(3u128, 5u64, 4u128, 4u64), (4, 4, 3, 5), (7, 7, 7, 7), (0, 9, 0, 1), (1 << 100, 3, 1 << 101, 1)] {
            assert_eq!(product_greater(a, b, c, d), a * u128::from(b) > c * u128::from(d), "{a}·{b} > {c}·{d}");
        }
        // 2^76·(2^64 − 1) against (2^76 − 1)·(2^64 − 1) and 2^76·(2^64 − 2): both products
        // pass 2^128, where a 128-bit product wraps.
        let (big, top) = (1u128 << 76, u64::MAX);
        assert!(product_greater(big, top, big - 1, top));
        assert!(product_greater(big, top, big, top - 1));
        assert!(!product_greater(big - 1, top, big, top));
        assert!(!product_greater(big, top, big, top));
        // Just past 2^128 against just below it: a 128-bit product wraps to the smaller.
        let (a, b, c, d) = (1u128 << 65, (1u64 << 63) + 1, 1u128 << 64, u64::MAX);
        assert!(product_greater(a, b, c, d) && !product_greater(c, d, a, b));
        assert!(a.wrapping_mul(u128::from(b)) < c.wrapping_mul(u128::from(d)), "128 bits would answer wrongly here");
        // The largest operands: (2^127 − 1)·(2^64 − 1).
        assert!(product_greater(i128::MAX as u128, top, i128::MAX as u128 - 1, top));
    }
}
