open-standards/wai/wai-vector/src/place.rs

//! Placement (§3.3), the load-time interval check (§3.4(a)) and the per-frame cost
//! (§3.4(b)), on the driver, in `i64`.
//!
//! The interval check is this interval computation, not the true range of the
//! device coordinates: every sink refuses the same documents.

use alloc::vec;
use alloc::vec::Vec;

use crate::arith::{floor_div, r_half_up, r_rat};
use crate::bounds::*;
use crate::refuse::{Code, Refusal, refuse};
use crate::wos1::Wos1;
use crate::wvg1::{Doc, Item, KIND_BEGIN, KIND_END, KIND_PATH, KIND_RUN, M00, M11, OP, TX, TY};

// ---------------------------------------------------------------- placement (§3.3)

/// The composed linear map `L_ij = R_rat(M_ij·s·w, dw·2^16)`, in Q16 device subpixels
/// per outline unit.
pub fn linear_map(m: [i64; 4], s: i64, w: i64, dw: i64) -> [i64; 4] {
    let den = dw << 16;
    m.map(|mij| r_rat(mij * s * w, den))
}

/// The origin of a glyph record at run-relative `(gx, gy)` design subpixels, for the
/// translation sum `o` and matrix `m`.
pub fn origin(o: [i64; 2], m: [i64; 4], g: [i64; 2], w: i64, dw: i64) -> [i64; 2] {
    let den = dw << 16;
    [
        r_rat(((o[0] << 16) + m[0] * g[0] + m[1] * g[1]) * w, den),
        r_rat(((o[1] << 16) + m[2] * g[0] + m[3] * g[1]) * w, den),
    ]
}

/// The point term `(R_half_up(L00·px + L01·py, 16), R_half_up(L10·px + L11·py, 16))`.
pub fn point_offset(l: [i64; 4], p: [i64; 2]) -> [i64; 2] {
    [r_half_up(l[0] * p[0] + l[1] * p[1], 16), r_half_up(l[2] * p[0] + l[3] * p[1], 16)]
}

/// The identity matrix, and the default of each slot when absent.
pub const IDENTITY: [i64; 4] = [65_536, 0, 0, 65_536];
pub const SLOT_DEFAULT: [i64; 7] = [65_536, 0, 0, 65_536, 0, 0, 255];

// ---------------------------------------------------------------- intervals (§3.4(a))

/// A closed integer interval.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Iv {
    pub lo: i64,
    pub hi: i64,
}

impl Iv {
    pub const fn point(v: i64) -> Iv {
        Iv { lo: v, hi: v }
    }
    pub fn plus(self, o: Iv) -> Iv {
        Iv { lo: self.lo + o.lo, hi: self.hi + o.hi }
    }
    /// The interval times a scalar: the interval between the two end products.
    pub fn scale(self, k: i64) -> Iv {
        let (a, b) = (self.lo * k, self.hi * k);
        Iv { lo: a.min(b), hi: a.max(b) }
    }
    /// The corner hull of two intervals' product.
    pub fn hull(self, o: Iv) -> Iv {
        let c = [self.lo * o.lo, self.lo * o.hi, self.hi * o.lo, self.hi * o.hi];
        Iv { lo: c.iter().copied().min().unwrap_or(0), hi: c.iter().copied().max().unwrap_or(0) }
    }
    /// A non-decreasing function applied at each end.
    pub fn map(self, f: impl Fn(i64) -> i64) -> Iv {
        Iv { lo: f(self.lo), hi: f(self.hi) }
    }
}

/// What the interval check and the cost need of each item, independent of the size.
pub struct Scene<'a> {
    pub d: &'a Doc,
    pub sets: &'a [Wos1],
    /// Each track's `[min, max]` over its key values.
    pub track_iv: Vec<Iv>,
    /// For each fill item, `O`'s interval per axis: its own translation plus every
    /// enclosing group's. For a group begin, its clip's: the group's own plus every
    /// enclosing group's.
    pub item_o: Vec<[Iv; 2]>,
    /// Each item's effective window, `[a, b)` with `a < b`, or `None` when empty.
    pub item_win: Vec<Option<(i64, i64)>>,
}

impl<'a> Scene<'a> {
    pub fn new(d: &'a Doc, sets: &'a [Wos1]) -> Scene<'a> {
        let track_iv = (0..d.tracks.len())
            .map(|t| {
                let ks = d.track_keys(t);
                Iv {
                    lo: ks.iter().map(|k| i64::from(k.value)).min().unwrap_or(0),
                    hi: ks.iter().map(|k| i64::from(k.value)).max().unwrap_or(0),
                }
            })
            .collect();
        let mut s = Scene { d, sets, track_iv, item_o: Vec::with_capacity(d.items.len()), item_win: Vec::with_capacity(d.items.len()) };
        let doc_win = (i64::from(d.header.t0), i64::from(d.header.t0) + i64::from(d.header.dur));
        // Stacks of the enclosing groups' summed translation intervals and windows.
        let mut o_stack: Vec<[Iv; 2]> = vec![[Iv::point(0); 2]];
        let mut w_stack: Vec<(i64, i64)> = vec![doc_win];
        for it in &d.items {
            let acc = *o_stack.last().unwrap_or(&[Iv::point(0); 2]);
            let win = *w_stack.last().unwrap_or(&doc_win);
            if it.kind == KIND_END {
                if o_stack.len() > 1 {
                    o_stack.pop();
                    w_stack.pop();
                }
                s.item_o.push([Iv::point(0); 2]);
                s.item_win.push(None);
                continue;
            }
            let own = [acc[0].plus(s.slot(it, TX)), acc[1].plus(s.slot(it, TY))];
            let w = (win.0.max(i64::from(it.t_on)), win.1.min(i64::from(it.t_off)));
            s.item_o.push(own);
            s.item_win.push(if w.0 < w.1 { Some(w) } else { None });
            if it.kind == KIND_BEGIN {
                o_stack.push(own);
                w_stack.push(w);
            }
        }
        s
    }

    /// A slot's interval: its track's key range, or its default as one point.
    pub fn slot(&self, it: &Item, s: usize) -> Iv {
        match it.slots[s] {
            NONE => Iv::point(SLOT_DEFAULT[s]),
            t => self.track_iv[t as usize],
        }
    }

    /// The matrix intervals of a fill item (the identity for a clip).
    pub fn matrix(&self, it: &Item) -> [Iv; 4] {
        if it.kind == KIND_BEGIN {
            IDENTITY.map(Iv::point)
        } else {
            [self.slot(it, M00), self.slot(it, M00 + 1), self.slot(it, M00 + 2), self.slot(it, M11)]
        }
    }
}

/// The device interval of one fill instance on each axis (§3.4(a) step 4).
pub fn device_iv(o: [Iv; 2], m: [Iv; 4], l: [Iv; 4], g: [i64; 2], bx: [i16; 4], w: i64, dw: i64) -> [Iv; 2] {
    let den = dw << 16;
    let bxx = Iv { lo: i64::from(bx[0]), hi: i64::from(bx[2]) };
    let bxy = Iv { lo: i64::from(bx[1]), hi: i64::from(bx[3]) };
    let mut out = [Iv::point(0); 2];
    for ax in 0..2 {
        let (m1, m2) = (m[2 * ax], m[2 * ax + 1]);
        let (l1, l2) = (l[2 * ax], l[2 * ax + 1]);
        let num = o[ax].scale(1 << 16).plus(m1.scale(g[0])).plus(m2.scale(g[1]));
        let org = num.map(|e| r_rat(e * w, den));
        let pt = l1.hull(bxx).plus(l2.hull(bxy)).map(|e| r_half_up(e, 16));
        out[ax] = org.plus(pt);
    }
    out
}

/// `L`'s interval from `M`'s, entry by entry.
pub fn linear_iv(m: [Iv; 4], s: i64, w: i64, dw: i64) -> [Iv; 4] {
    let den = dw << 16;
    m.map(|mi| mi.map(|e| r_rat(e * s * w, den)))
}

/// A fill instance: its item, its device interval, and its stored point count.
#[derive(Clone, Copy, Debug)]
pub struct Instance {
    pub item: usize,
    pub dev: [Iv; 2],
    pub points: u64,
}

/// Every fill instance at width `w`, in item order (a group's clip at its begin), with
/// a run's glyph records in order.
pub fn instances(sc: &Scene, w: i64, mut f: impl FnMut(Instance)) {
    let d = sc.d;
    let dw = i64::from(d.header.design_w);
    for (i, it) in d.items.iter().enumerate() {
        let s = i64::from(it.unit_scale);
        match it.kind {
            KIND_BEGIN if it.reference != NONE => {
                let m = sc.matrix(it);
                let l = linear_iv(m, s, w, dw);
                let p = &d.paths[it.reference as usize];
                let dev = device_iv(sc.item_o[i], m, l, [0, 0], p.bbox, w, dw);
                f(Instance { item: i, dev, points: u64::from(p.n_points) });
            }
            KIND_PATH => {
                let m = sc.matrix(it);
                let l = linear_iv(m, s, w, dw);
                let p = &d.paths[it.reference as usize];
                let dev = device_iv(sc.item_o[i], m, l, [0, 0], p.bbox, w, dw);
                f(Instance { item: i, dev, points: u64::from(p.n_points) });
            }
            KIND_RUN => {
                let m = sc.matrix(it);
                let l = linear_iv(m, s, w, dw);
                let set = &sc.sets[it.reference as usize];
                for g in d.run_glyphs(i) {
                    let gl = set.glyph(g.gid).expect("step 7 found every glyph");
                    let bx = [gl.xmin, gl.ymin, gl.xmax, gl.ymax];
                    let dev = device_iv(sc.item_o[i], m, l, [i64::from(g.x), i64::from(g.y)], bx, w, dw);
                    f(Instance { item: i, dev, points: u64::from(gl.n_points) });
                }
            }
            _ => {}
        }
    }
}

/// Step 8: every end of every device interval lies in `[−2^22, 2^22 − 1]`, at every
/// listed size, for every fill instance whether or not it is ever active.
pub fn interval_check(d: &Doc, sets: &[Wos1]) -> Result<(), Refusal> {
    let sc = Scene::new(d, sets);
    for (z, size) in d.sizes.iter().enumerate() {
        let mut bad = false;
        instances(&sc, i64::from(size.w), |inst| {
            for iv in inst.dev {
                if iv.lo < DEVICE_MIN || iv.hi > DEVICE_MAX {
                    bad = true;
                }
            }
        });
        if bad {
            return refuse(Code::GeometryRange, "8", "a device interval leaves [-2^22, 2^22 - 1]", z as u64);
        }
    }
    Ok(())
}

// ---------------------------------------------------------------- the cost (§3.4(b))

/// The clipped pixel box of a device interval: `(c_lo, c_hi, bw, r_lo, r_hi, bh)`.
pub fn pixel_box(dev: [Iv; 2], w: i64, h: i64) -> (i64, i64, i64, i64, i64, i64) {
    let c_lo = floor_div(dev[0].lo, 256).max(0);
    let c_hi = floor_div(dev[0].hi, 256).min(w - 1);
    let r_lo = floor_div(dev[1].lo, 256).max(0);
    let r_hi = floor_div(dev[1].hi, 256).min(h - 1);
    (c_lo, c_hi, (c_hi - c_lo + 1).max(0), r_lo, r_hi, (r_hi - r_lo + 1).max(0))
}

/// A fill's cost `c(f) = p·(2^10 + bw + bh) + bw·bh`.
pub fn fill_cost(p: u64, bw: u64, bh: u64) -> u64 {
    p * (1024 + bw + bh) + bw * bh
}

/// Each item's cost at size `(w, h)` (§3.4(b) step 3).
pub fn item_costs(sc: &Scene, w: i64, h: i64) -> Vec<u64> {
    let d = sc.d;
    let mut cost = vec![0u64; d.items.len()];
    // A run's hull over its glyph records whose box is not empty.
    let mut hull: Vec<Option<(i64, i64, i64, i64)>> = vec![None; d.items.len()];
    for (i, it) in d.items.iter().enumerate() {
        if it.kind == KIND_BEGIN {
            cost[i] = (w * h) as u64;
        }
    }
    instances(sc, w, |inst| {
        let (c_lo, c_hi, bw, r_lo, r_hi, bh) = pixel_box(inst.dev, w, h);
        cost[inst.item] += fill_cost(inst.points, bw as u64, bh as u64);
        if d.items[inst.item].kind == KIND_RUN && bw > 0 && bh > 0 {
            let e = &mut hull[inst.item];
            *e = Some(match *e {
                None => (c_lo, c_hi, r_lo, r_hi),
                Some((a, b, c, dd)) => (a.min(c_lo), b.max(c_hi), c.min(r_lo), dd.max(r_hi)),
            });
        }
    });
    for (i, hl) in hull.iter().enumerate() {
        if let Some((c_lo, c_hi, r_lo, r_hi)) = *hl {
            cost[i] += ((c_hi - c_lo + 1) * (r_hi - r_lo + 1)) as u64;
        }
    }
    cost
}

/// `cost(z) = w·h + max over every integer tick of the summed costs of the items whose
/// effective window holds it`, by sorting the windows' edges, ends before starts at
/// equal ticks.
pub fn size_cost(sc: &Scene, w: i64, h: i64) -> u64 {
    let costs = item_costs(sc, w, h);
    let mut edges: Vec<(i64, u8, u64)> = Vec::new();
    for (i, c) in costs.iter().enumerate() {
        if let (Some((a, b)), true) = (sc.item_win[i], *c > 0) {
            edges.push((a, 1, *c));
            edges.push((b, 0, *c));
        }
    }
    edges.sort_unstable();
    let (mut cur, mut best) = (0u64, 0u64);
    for (_, start, c) in edges {
        if start == 1 {
            cur += c;
            best = best.max(cur);
        } else {
            cur -= c;
        }
    }
    (w * h) as u64 + best
}

/// Every listed size's cost, in `SIZE` order.
pub fn costs(d: &Doc, sets: &[Wos1]) -> Vec<u64> {
    let sc = Scene::new(d, sets);
    d.sizes.iter().map(|z| size_cost(&sc, i64::from(z.w), i64::from(z.h))).collect()
}

/// Step 9: for each listed size in order, `too_large` above the ceiling, otherwise
/// `payload_malformed` when it differs from `SIZE.cost`.
pub fn check_costs(d: &Doc, sets: &[Wos1]) -> Result<Vec<u64>, Refusal> {
    let all = costs(d, sets);
    for (z, (&c, size)) in all.iter().zip(&d.sizes).enumerate() {
        if c > COST_CEILING {
            return refuse(Code::TooLarge, "9", "cost above 2^32 - 1", z as u64);
        }
        if c != u64::from(size.cost) {
            return refuse(Code::PayloadMalformed, "9", "SIZE.cost differs from the cost", z as u64);
        }
    }
    Ok(all)
}

/// The slot index of an item's opacity, for callers outside this module.
pub const OPACITY_SLOT: usize = OP;
/// Whether an item is a fill.
pub fn is_fill(it: &Item) -> bool {
    it.kind == KIND_PATH || it.kind == KIND_RUN
}