sva_samples/machine/

renderer.rs

// Concern: the node renderer sva-engine hands this crate | Non-concern: building it (sva-engine lower.rs), running it (mod.rs, ops.rs) | IO: none

use std::sync::Arc;

use sva_formula::{Body, Shape};

use crate::collapse::Rows;
use crate::grid::{Extent, Grid, Round};
use crate::physics::Params;

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct BufId(pub u32);

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct SiteId(pub u32);

/// Reader sample `n` reads source sample `(a*n + b)/d`, `d > 0`: exactly, or rounded down or
/// to the nearest, ties to even. An exact map is whole, `d = 1`; nothing reads between samples.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Map {
    pub a: i128,
    pub b: i128,
    pub d: i128,
    pub between: Between,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Between {
    Exact,
    Floor,
    Even,
}

impl Map {
    pub const fn shift(b: i64) -> Map {
        Map::whole(1, b)
    }

    /// Reader sample `n` reads source sample `a*n + b`.
    pub const fn whole(a: i128, b: i64) -> Map {
        Map {
            a,
            b: b as i128,
            d: 1,
            between: Between::Exact,
        }
    }

    /// Lowest terms; `None` where a sample lands between two, or past what a map holds.
    pub fn new(a: i128, b: i128, d: i128) -> Option<Map> {
        Map::rounded(a, b, d, Between::Exact)
    }

    /// A rounding every sample takes alike is folded into an exact map.
    pub fn rounded(a: i128, b: i128, d: i128, between: Between) -> Option<Map> {
        let g = gcd(gcd(a.abs(), b.abs()), d.abs()).max(1);
        let sign = d.signum();
        let limit = 1i128 << 100;
        let map = Map {
            a: sign * a / g,
            b: sign * b / g,
            d: d.abs() / g,
            between,
        };
        let held = map.d > 0 && map.a.abs() < limit && map.b.abs() < limit && map.d < limit;
        held.then(|| map.settled())
            .filter(|m| m.d == 1 || m.between != Between::Exact)
    }

    fn settled(self) -> Map {
        let exact = match self.between {
            _ if self.d == 1 => true,
            Between::Exact => false,
            Between::Floor => self.a % self.d == 0,
            Between::Even => {
                let tie = 2 * self.b.rem_euclid(self.d) == self.d;
                self.a % self.d == 0 && (!tie || (self.a / self.d) % 2 == 0)
            }
        };
        match exact {
            true => Map {
                a: self.a / self.d,
                b: self.index_at(0),
                d: 1,
                between: Between::Exact,
            },
            false => self,
        }
    }

    pub fn moved(self) -> Option<i64> {
        (self.a == 1 && self.d == 1).then(|| i64::try_from(self.b).ok())?
    }

    pub fn at(self, n: i64) -> i64 {
        let clamp = |k: i128| k.clamp(i128::from(i64::MIN), i128::from(i64::MAX)) as i64;
        self.narrow_at(n)
            .unwrap_or_else(|| clamp(self.index_at(i128::from(n))))
    }

    /// `index_at` in `i64`, where every step of it fits one.
    fn narrow_at(self, n: i64) -> Option<i64> {
        if let Some(k) = self.whole_at(n) {
            return Some(k);
        }
        let [a, b, d] = [self.a, self.b, self.d].map(|v| i64::try_from(v).ok());
        let num = a?.checked_mul(n)?.checked_add(b?)?;
        let d = d?;
        let (floor, rem) = (num.div_euclid(d), num.rem_euclid(d));
        Some(match self.between {
            Between::Exact | Between::Floor => floor,
            Between::Even => match rem.cmp(&(d - rem)) {
                std::cmp::Ordering::Less => floor,
                std::cmp::Ordering::Greater => floor + 1,
                std::cmp::Ordering::Equal => floor + floor.rem_euclid(2),
            },
        })
    }

    fn whole_at(self, n: i64) -> Option<i64> {
        if self.d != 1 {
            return None;
        }
        let (a, b) = (i64::try_from(self.a).ok()?, i64::try_from(self.b).ok()?);
        a.checked_mul(n)?.checked_add(b)
    }

    pub fn ahead(self) -> bool {
        self.a != self.d || self.lead() > 0
    }

    pub fn lead(self) -> i64 {
        let most = match self.between {
            Between::Exact | Between::Floor => self.b.div_euclid(self.d),
            Between::Even => (2 * self.b + self.d).div_euclid(2 * self.d),
        };
        most.clamp(i128::from(i64::MIN / 2), i128::from(i64::MAX / 2)) as i64
    }

    pub fn least(self) -> i64 {
        let least = match self.between {
            Between::Exact | Between::Floor => self.b.div_euclid(self.d),
            Between::Even => (2 * self.b + self.d - 1).div_euclid(2 * self.d),
        };
        least.clamp(i128::from(i64::MIN / 2), i128::from(i64::MAX / 2)) as i64
    }

    pub fn image(self, over: Extent) -> Extent {
        if over.is_empty() {
            return over;
        }
        if self.a == 0 {
            let at = self.at(0);
            return Extent::new(at, at.saturating_add(1));
        }
        let ends = (first(over), last(over));
        let at = |n: Option<i128>| n.map(|n| self.index_at(n));
        let (lo, hi) = match self.a > 0 {
            true => (at(ends.0), at(ends.1)),
            false => (at(ends.1), at(ends.0)),
        };
        extent(lo, hi.map(|h| h + 1))
    }

    /// The reader samples whose reading lands in `into`. Rounding to even reads at most one
    /// below rounding half up.
    pub fn preimage(self, into: Extent) -> Extent {
        if into.is_empty() {
            return into;
        }
        if self.between == Between::Even {
            let up = Map {
                a: 2 * self.a,
                b: 2 * self.b + self.d,
                d: 2 * self.d,
                between: Between::Floor,
            };
            let end = match into.end {
                i64::MAX => i64::MAX,
                e => e.saturating_add(1),
            };
            return up.preimage(Extent::new(into.start, end));
        }
        if self.a == 0 {
            return match into.contains(self.at(0)) {
                true => Extent::EVERYWHERE,
                false => Extent::NOWHERE,
            };
        }
        let (a, b, d) = (self.a, self.b, self.d);
        let (first, last) = (first(into), last(into));
        let lowest = |m: i128| ceil_div(m * d - b, a);
        let highest = |m: i128| floor_div((m + 1) * d - 1 - b, a);
        let (lo, hi) = match self.a > 0 {
            true => (first.map(lowest), last.map(highest)),
            false => (
                last.map(|m| ceil_div((m + 1) * d - 1 - b, a)),
                first.map(|m| floor_div(m * d - b, a)),
            ),
        };
        extent(lo, hi.map(|h| h + 1))
    }

    fn index_at(self, n: i128) -> i128 {
        #[cfg(test)]
        crate::grid::WIDE.with(|w| w.set(w.get() + 1));
        let num = self.a.saturating_mul(n).saturating_add(self.b);
        let (floor, rem) = (num.div_euclid(self.d), num.rem_euclid(self.d));
        match self.between {
            Between::Exact | Between::Floor => floor,
            Between::Even => match (2 * rem).cmp(&self.d) {
                std::cmp::Ordering::Less => floor,
                std::cmp::Ordering::Greater => floor + 1,
                std::cmp::Ordering::Equal => floor + floor.rem_euclid(2),
            },
        }
    }
}

fn gcd(a: i128, b: i128) -> i128 {
    match b {
        0 => a,
        b => gcd(b, a % b),
    }
}

fn first(e: Extent) -> Option<i128> {
    (e.start != i64::MIN).then(|| i128::from(e.start))
}

fn last(e: Extent) -> Option<i128> {
    (e.end != i64::MAX).then(|| i128::from(e.end) - 1)
}

fn floor_div(num: i128, den: i128) -> i128 {
    match den < 0 {
        true => (-num).div_euclid(-den),
        false => num.div_euclid(den),
    }
}

fn ceil_div(num: i128, den: i128) -> i128 {
    -floor_div(-num, den)
}

fn extent(lo: Option<i128>, hi: Option<i128>) -> Extent {
    let clamp = |n: i128| n.clamp(i128::from(i64::MIN + 1), i128::from(i64::MAX - 1)) as i64;
    let (start, end) = (lo.map_or(i64::MIN, clamp), hi.map_or(i64::MAX, clamp));
    match start < end {
        true => Extent::new(start, end),
        false => Extent::NOWHERE,
    }
}

/// `scale*t + shift + gain*((inner_scale*t + inner_shift) mod period)` at sample `n`'s
/// instant, each a rational `(num, den)` with `den > 0` and `period > 0`. The remainder and
/// the sum are integers over one denominator, so which side of a jump an instant falls on is
/// decided exactly and only the quotient that states the sum rounds.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Wrap {
    pub scale: (i128, i128),
    pub shift: (i128, i128),
    pub gain: (i128, i128),
    pub inner: [(i128, i128); 2],
    pub period: (i128, i128),
}

impl Wrap {
    /// `None` where its constants overflow.
    pub fn on(self, grid: Grid) -> Option<Stepped> {
        let (_, rate) = grid.exact(0)?;
        let [(s, sd), (o, od)] = self.inner;
        let over = sd.checked_mul(rate)?;
        let den = lcm(lcm(over, od)?, self.period.1)?;
        let line = self.scale.1.checked_mul(rate)?;
        let wrapped = self.gain.1.checked_mul(den)?;
        let whole = lcm(lcm(line, self.shift.1)?, wrapped)?;
        Some(Stepped {
            step: grid.a,
            inner: s,
            over: den / over,
            offset: o.checked_mul(den / od)?,
            period: self.period.0.checked_mul(den / self.period.1)?,
            scale: self.scale.0,
            line: whole / line,
            shift: self.shift.0.checked_mul(whole / self.shift.1)?,
            gain: self.gain.0,
            wrapped: whole / wrapped,
            whole,
        })
    }

    /// The largest magnitude it takes over instants no later than `t`.
    pub fn most(self, t: f64) -> f64 {
        let q = |(num, den): (i128, i128)| num as f64 / den as f64;
        q(self.scale).abs() * t.abs() + q(self.shift).abs() + q(self.gain).abs() * q(self.period)
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Stepped {
    step: i128,
    inner: i128,
    over: i128,
    offset: i128,
    period: i128,
    scale: i128,
    line: i128,
    shift: i128,
    gain: i128,
    wrapped: i128,
    whole: i128,
}

impl Stepped {
    /// `None` where the integers it is computed in would overflow.
    pub fn at(self, n: i64) -> Option<f64> {
        let n = self.step.checked_mul(i128::from(n))?;
        let x = self
            .inner
            .checked_mul(n)?
            .checked_mul(self.over)?
            .checked_add(self.offset)?;
        let rem = x.rem_euclid(self.period);
        let sum = self
            .scale
            .checked_mul(n)?
            .checked_mul(self.line)?
            .checked_add(self.shift)?
            .checked_add(self.gain.checked_mul(rem)?.checked_mul(self.wrapped)?)?;
        Some(sum as f64 / self.whole as f64)
    }
}

fn lcm(a: i128, b: i128) -> Option<i128> {
    (a / gcd(a, b)).checked_mul(b)
}

/// An integer every sample evaluates exactly, `None` past `i64`.
#[derive(Clone, Debug, PartialEq)]
pub enum Index<T = Box<NodeRenderer>> {
    At(Map),
    Step(T, Round),
    Add(Vec<Index<T>>),
    Neg(Box<Index<T>>),
    Mul(Vec<Index<T>>),
}

impl<T> Index<T> {
    pub fn times(&self) -> Vec<&T> {
        let mut out = Vec::new();
        self.each(&mut |t| out.push(t));
        out
    }

    fn each<'a>(&'a self, f: &mut impl FnMut(&'a T)) {
        match self {
            Index::At(_) => {}
            Index::Step(t, _) => f(t),
            Index::Add(parts) | Index::Mul(parts) => parts.iter().for_each(|p| p.each(f)),
            Index::Neg(p) => p.each(f),
        }
    }

    pub fn mapped<U, E>(&self, f: &mut impl FnMut(&T) -> Result<U, E>) -> Result<Index<U>, E> {
        let mut each = |parts: &[Index<T>]| -> Result<Vec<Index<U>>, E> {
            parts.iter().map(|p| p.mapped(f)).collect()
        };
        Ok(match self {
            Index::At(map) => Index::At(*map),
            Index::Step(t, round) => Index::Step(f(t)?, *round),
            Index::Add(parts) => Index::Add(each(parts)?),
            Index::Mul(parts) => Index::Mul(each(parts)?),
            Index::Neg(p) => Index::Neg(Box::new(p.mapped(f)?)),
        })
    }

    pub fn at(&self, n: i64, grid: Grid, time: &impl Fn(&T) -> f64) -> Option<i64> {
        match self {
            Index::At(map) => map
                .narrow_at(n)
                .or_else(|| i64::try_from(map.index_at(i128::from(n))).ok()),
            Index::Step(t, round) => grid.step_at(time(t), *round),
            Index::Add(parts) => parts
                .iter()
                .try_fold(0i64, |held, p| held.checked_add(p.at(n, grid, time)?)),
            Index::Mul(parts) => parts
                .iter()
                .try_fold(1i64, |held, p| held.checked_mul(p.at(n, grid, time)?)),
            Index::Neg(p) => p.at(n, grid, time)?.checked_neg(),
        }
    }
}

/// Another node's samples, or this node's own past.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub enum Slot {
    Read(BufId),
    Own,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Unary {
    Sin,
    Cos,
    Exp,
    Sqrt,
    Abs,
    Tanh,
    Log,
    Sat,
    Step,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Binary {
    Max,
    Min,
    Mod,
}

/// What the machine evaluates at an instant it computes: a closed form's own rows, a written
/// form reading other forms, or the noise.
#[derive(Clone, Debug)]
pub enum Formula {
    Rows(Arc<Rows>),
    Written(Box<Written>),
    Drawn { seed: u64, rate: u32 },
}

impl PartialEq for Formula {
    fn eq(&self, other: &Formula) -> bool {
        match (self, other) {
            (Formula::Rows(a), Formula::Rows(b)) => Arc::ptr_eq(a, b),
            (Formula::Written(a), Formula::Written(b)) => a == b,
            (Formula::Drawn { seed, rate }, Formula::Drawn { seed: s, rate: r }) => {
                (seed, rate) == (s, r)
            }
            _ => false,
        }
    }
}

/// A written form and each form it reads, `Body::Node(k)` in either naming `refs[k]`.
#[derive(Clone, Debug, PartialEq)]
pub struct Written {
    pub body: Body,
    pub refs: Vec<Body>,
}

/// Every closed form-typed subterm was collapsed to a buffer, inlined or held as a formula
/// before this tree was built, so there is no oscillator, no series and no delta here.
#[derive(Clone, Debug, PartialEq)]
pub enum NodeRenderer {
    Const(f64),
    Time,
    Wrap(Wrap),
    Read {
        slot: Slot,
        map: Map,
    },
    /// A closed form at the instant `time` names, `width` components wide.
    Formula {
        formula: Formula,
        width: usize,
        time: Box<NodeRenderer>,
    },
    Noise(u64),
    /// The stored sample at the integer `index` names, within `reach` of the sample being
    /// written where that is known.
    Indexed {
        slot: Slot,
        index: Index,
        reach: Option<(i64, i64)>,
    },
    /// The instant of the sample `index` names.
    Instant(Index),
    Add(Vec<NodeRenderer>),
    Mul(Vec<NodeRenderer>),
    Sub(Box<NodeRenderer>, Box<NodeRenderer>),
    Div(Box<NodeRenderer>, Box<NodeRenderer>),
    Pow(Box<NodeRenderer>, Box<NodeRenderer>),
    Map(Unary, Box<NodeRenderer>),
    Zip(Binary, Box<NodeRenderer>, Box<NodeRenderer>),
    /// `x` over the samples `window` holds, the instants `[a, b)` it was written as, with a
    /// raised-cosine `rise` and `fall` inside it; zero at every sample outside.
    Crop {
        x: Box<NodeRenderer>,
        window: (i64, i64),
        a: f64,
        b: f64,
        rise: f64,
        fall: f64,
    },
    Join(Vec<NodeRenderer>),
    Channel {
        x: Box<NodeRenderer>,
        k: usize,
    },
    /// Zero, stepping nothing, before `from`, where its state starts.
    Filter {
        site: SiteId,
        from: i64,
        x: Box<NodeRenderer>,
        cutoff: Box<NodeRenderer>,
        q: Box<NodeRenderer>,
        gain: Box<NodeRenderer>,
    },
    Physics {
        site: SiteId,
        from: i64,
        args: Vec<NodeRenderer>,
    },
}

impl NodeRenderer {
    /// Holds no call site and reads none of its own past, so skipping a sample of it changes
    /// no later one.
    pub fn stateless(&self) -> bool {
        !self.holds_state() && self.operands().into_iter().all(NodeRenderer::stateless)
    }

    pub(crate) fn holds_state(&self) -> bool {
        matches!(
            self,
            NodeRenderer::Filter { .. }
                | NodeRenderer::Physics { .. }
                | NodeRenderer::Read {
                    slot: Slot::Own,
                    ..
                }
                | NodeRenderer::Indexed {
                    slot: Slot::Own,
                    ..
                }
        )
    }

    /// Every operand in the order the op array lowers them.
    pub(crate) fn operands(&self) -> Vec<&NodeRenderer> {
        match self {
            NodeRenderer::Add(set) | NodeRenderer::Mul(set) | NodeRenderer::Join(set) => {
                set.iter().collect()
            }
            NodeRenderer::Sub(a, b)
            | NodeRenderer::Div(a, b)
            | NodeRenderer::Pow(a, b)
            | NodeRenderer::Zip(_, a, b) => vec![a, b],
            NodeRenderer::Map(_, x)
            | NodeRenderer::Crop { x, .. }
            | NodeRenderer::Channel { x, .. } => vec![x],
            NodeRenderer::Filter {
                x, cutoff, q, gain, ..
            } => vec![x, cutoff, q, gain],
            NodeRenderer::Physics { args, .. } => args.iter().collect(),
            NodeRenderer::Formula { time, .. } => vec![time],
            NodeRenderer::Indexed { index, .. } | NodeRenderer::Instant(index) => {
                index.times().into_iter().map(|t| &**t).collect()
            }
            NodeRenderer::Const(_)
            | NodeRenderer::Time
            | NodeRenderer::Wrap(_)
            | NodeRenderer::Noise(_)
            | NodeRenderer::Read { .. } => Vec::new(),
        }
    }
}

#[derive(Clone, Debug, PartialEq)]
pub enum Site {
    Filter(Shape),
    Physics(Box<Params>),
}

impl From<sva_formula::Unary> for Unary {
    fn from(written: sva_formula::Unary) -> Unary {
        match written {
            sva_formula::Unary::Sin => Unary::Sin,
            sva_formula::Unary::Cos => Unary::Cos,
            sva_formula::Unary::Exp => Unary::Exp,
            sva_formula::Unary::Sqrt => Unary::Sqrt,
            sva_formula::Unary::Abs => Unary::Abs,
            sva_formula::Unary::Tanh => Unary::Tanh,
            sva_formula::Unary::Log => Unary::Log,
            sva_formula::Unary::Sat => Unary::Sat,
            sva_formula::Unary::Step => Unary::Step,
        }
    }
}

impl Unary {
    pub fn apply(self, x: f64) -> f64 {
        match self {
            Unary::Sin => x.sin(),
            Unary::Cos => x.cos(),
            Unary::Exp => x.exp(),
            Unary::Sqrt => x.sqrt(),
            Unary::Abs => x.abs(),
            Unary::Tanh => x.tanh(),
            Unary::Log => x.ln(),
            Unary::Sat => x.clamp(-1.0, 1.0),
            Unary::Step => sva_formula::affine::step(x),
        }
    }
}

impl Binary {
    pub fn apply(self, a: f64, b: f64) -> f64 {
        match self {
            Binary::Max => a.max(b),
            Binary::Min => a.min(b),
            Binary::Mod => a.rem_euclid(b),
        }
    }
}

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

    #[test]
    fn a_rounded_map_reads_alike_narrow_and_wide() {
        for (a, b, d) in [(1, 0, 2), (3, -7, 4), (-5, 11, 6), (2, 1, 4), (7, 3, 2)] {
            for between in [super::Between::Floor, super::Between::Even] {
                let Some(map) = Map::rounded(a, b, d, between) else {
                    continue;
                };
                for n in -50..50 {
                    let wide = i64::try_from(map.index_at(i128::from(n))).ok();
                    assert_eq!(map.narrow_at(n), wide, "{map:?} at {n}");
                }
            }
        }
    }
}