EffectCraft: An open-source motion graphics and compositing tool written by scratch in pure Rust
//! Colour spaces (ISO 32000-1 §8.6) reduced to sRGB, and functions (§7.10: sampled,
//! exponential, stitching and PostScript calculator functions).
use std::collections::HashMap;
use std::sync::Arc;
use crate::object::{Dict, File, Obj, decode_stream};
#[derive(Clone, Debug, PartialEq)]
pub enum Cs {
Gray,
Rgb,
Cmyk,
/// CIE L*a*b* (approximated).
Lab,
Indexed {
base: Box<Cs>,
hival: usize,
lookup: Vec<u8>,
},
/// Separation / DeviceN: components → alternate space through a tint transform.
Tint {
n: usize,
alt: Box<Cs>,
func: Func,
},
Pattern,
}
impl Cs {
pub fn components(&self) -> usize {
match self {
Cs::Gray | Cs::Indexed { .. } => 1,
Cs::Rgb | Cs::Lab => 3,
Cs::Cmyk => 4,
Cs::Tint { n, .. } => *n,
Cs::Pattern => 0,
}
}
/// The initial colour of the space (black, or tint 1).
pub fn initial(&self) -> Vec<f64> {
match self {
Cs::Cmyk => vec![0.0, 0.0, 0.0, 1.0],
Cs::Tint { n, .. } => vec![1.0; *n],
Cs::Lab => vec![0.0, 0.0, 0.0],
c => vec![0.0; c.components()],
}
}
pub fn to_rgb(&self, c: &[f64]) -> [f64; 3] {
let g = |i: usize| c.get(i).copied().unwrap_or(0.0).clamp(0.0, 1.0);
match self {
Cs::Gray => [g(0); 3],
Cs::Rgb | Cs::Pattern => [g(0), g(1), g(2)],
Cs::Cmyk => {
let k = g(3);
[(1.0 - g(0)) * (1.0 - k), (1.0 - g(1)) * (1.0 - k), (1.0 - g(2)) * (1.0 - k)]
}
Cs::Lab => lab_to_rgb(c.first().copied().unwrap_or(0.0), c.get(1).copied().unwrap_or(0.0), c.get(2).copied().unwrap_or(0.0)),
Cs::Indexed { base, hival, lookup } => {
let i = (c.first().copied().unwrap_or(0.0).round().max(0.0) as usize).min(*hival);
let n = base.components();
let v: Vec<f64> = (0..n).map(|k| lookup.get(i * n + k).copied().unwrap_or(0) as f64 / 255.0).collect();
base.to_rgb(&v)
}
Cs::Tint { alt, func, .. } => alt.to_rgb(&func.eval(c)),
}
}
}
fn lab_to_rgb(l: f64, a: f64, b: f64) -> [f64; 3] {
let fy = (l + 16.0) / 116.0;
let fx = fy + a / 500.0;
let fz = fy - b / 200.0;
let f = |t: f64| if t > 6.0 / 29.0 { t * t * t } else { 3.0 * (6.0f64 / 29.0).powi(2) * (t - 4.0 / 29.0) };
let (x, y, z) = (0.9505 * f(fx), f(fy), 1.089 * f(fz));
let lin = [3.2406 * x - 1.5372 * y - 0.4986 * z, -0.9689 * x + 1.8758 * y + 0.0415 * z, 0.0557 * x - 0.204 * y + 1.057 * z];
lin.map(|v| {
let v = v.clamp(0.0, 1.0);
if v <= 0.003_130_8 { 12.92 * v } else { 1.055 * v.powf(1.0 / 2.4) - 0.055 }
})
}
/// How deep colour spaces nest (an Indexed base, the alternate of an ICCBased, Separation or
/// DeviceN space) and, counted separately, functions (in arrays and stitching functions).
/// References can make either a cycle, while real files nest two or three levels; anything deeper
/// reads as unreadable (DeviceGray, an unsupported function).
const MAX_DEPTH: usize = 8;
/// Read a colour space (a name, or an array such as `[/ICCBased 5 0 R]`); named resources are
/// looked up in `res` (`/ColorSpace`).
pub fn color_space(file: &File, o: &Obj, res: Option<&Dict>) -> Cs {
color_space_at(file, o, res, 0)
}
/// [`color_space`] nested `depth` levels deep: DeviceGray past [`MAX_DEPTH`].
fn color_space_at(file: &File, o: &Obj, res: Option<&Dict>, depth: usize) -> Cs {
if depth >= MAX_DEPTH {
return Cs::Gray;
}
let o = file.resolve(o);
match o {
Obj::Name(n) => match n.as_str() {
"DeviceGray" | "G" | "CalGray" => Cs::Gray,
"DeviceRGB" | "RGB" | "CalRGB" => Cs::Rgb,
"DeviceCMYK" | "CMYK" => Cs::Cmyk,
"Pattern" => Cs::Pattern,
other => match res.and_then(|r| file.get_dict(r, "ColorSpace")).and_then(|cs| file.get(cs, other)) {
Some(x) if !matches!(x, Obj::Name(m) if m == other) => color_space_at(file, x, None, depth + 1),
_ => Cs::Gray,
},
},
Obj::Array(a) => {
let head = a.first().map(|h| file.resolve(h)).and_then(Obj::name).unwrap_or("");
match head {
"ICCBased" => {
let d = a.get(1).map(|s| file.resolve(s)).and_then(Obj::dict);
// The profile's alternate space when it names one (profiles are not
// evaluated), else the device space with the same number of components.
if let Some(alt) = d.and_then(|d| file.get(d, "Alternate")) {
return color_space_at(file, alt, res, depth + 1);
}
let n = d.and_then(|d| file.get_num(d, "N")).unwrap_or(3.0) as usize;
match n {
1 => Cs::Gray,
4 => Cs::Cmyk,
_ => Cs::Rgb,
}
}
"CalRGB" => Cs::Rgb,
"CalGray" => Cs::Gray,
"Lab" => Cs::Lab,
"Pattern" => Cs::Pattern,
"Indexed" | "I" => {
let base = a.get(1).map(|b| color_space_at(file, b, res, depth + 1)).unwrap_or(Cs::Rgb);
// An indexed palette holds at most 256 entries, so hival (its largest index) is
// 0 to 255; an image builds its palette from every entry up to hival.
let hival = (a.get(2).and_then(|h| file.resolve(h).num()).unwrap_or(0.0) as usize).min(255);
let lookup = match a.get(3).map(|l| file.resolve(l)) {
Some(Obj::Str(s)) => s.clone(),
Some(Obj::Stream(d, raw)) => decode_stream(file, d, raw).unwrap_or_default(),
_ => vec![],
};
Cs::Indexed { base: Box::new(base), hival, lookup }
}
"Separation" | "DeviceN" => {
let n = if head == "Separation" { 1 } else { a.get(1).map(|x| file.resolve(x)).and_then(Obj::array).map_or(1, <[Obj]>::len) };
let alt = a.get(2).map(|b| color_space_at(file, b, res, depth + 1)).unwrap_or(Cs::Gray);
let func = a.get(3).map(|f| Func::read(file, f)).unwrap_or(Func::Unsupported);
// An unreadable tint transform: tint 1 = black, 0 = white.
if func == Func::Unsupported {
return Cs::Tint { n, alt: Box::new(Cs::Gray), func: Func::Exp { domain: [0.0, 1.0], c0: vec![1.0], c1: vec![0.0], n: 1.0 } };
}
Cs::Tint { n, alt: Box::new(alt), func }
}
_ => Cs::Rgb,
}
}
_ => Cs::Gray,
}
}
#[derive(Clone, Debug, PartialEq)]
pub enum Func {
/// Type 2.
Exp {
domain: [f64; 2],
c0: Vec<f64>,
c1: Vec<f64>,
n: f64,
},
/// Type 3.
Stitch {
domain: [f64; 2],
funcs: Vec<Func>,
bounds: Vec<f64>,
encode: Vec<f64>,
},
/// Type 0 with one input. Copies share the samples (a graphics state is copied at every `q`).
Sampled {
domain: [f64; 2],
size: usize,
outputs: usize,
encode: [f64; 2],
decode: Vec<f64>,
samples: Arc<[f64]>,
},
/// Type 0 with several inputs (function-based shadings): multilinear interpolation, the
/// first input varying fastest in the sample table.
SampledN {
domain: Vec<f64>,
size: Vec<usize>,
outputs: usize,
encode: Vec<f64>,
decode: Vec<f64>,
samples: Arc<[f64]>,
},
/// An array of one-output functions.
Array(Vec<Func>),
/// Type 4: a PostScript calculator program (§7.10.5).
Calc {
domain: Vec<f64>,
range: Vec<f64>,
code: Vec<PsOp>,
},
Unsupported,
}
/// A PostScript calculator token; procedures nest for `if` / `ifelse`.
#[derive(Clone, Debug, PartialEq)]
pub enum PsOp {
Num(f64),
Op(String),
Proc(Vec<PsOp>),
}
fn ps_parse(lx: &mut crate::object::Lexer, depth: usize) -> Vec<PsOp> {
let mut out = vec![];
while let Some(o) = lx.next() {
match o {
Obj::Num(n) => out.push(PsOp::Num(n)),
Obj::Bool(b) => out.push(PsOp::Num(if b { 1.0 } else { 0.0 })),
Obj::Op(op) if op == "{" && depth < 32 => out.push(PsOp::Proc(ps_parse(lx, depth + 1))),
// Nested too deep: skip the procedure's opening brace (never push it as an operator).
Obj::Op(op) if op == "{" => {}
Obj::Op(op) if op == "}" => return out,
Obj::Op(op) => out.push(PsOp::Op(op)),
_ => {}
}
}
out
}
/// A calculator function's operand stack holds at most 100 values (the PDF specification's
/// implementation limits); a real program uses a handful.
const MAX_STACK: usize = 100;
/// Push onto a calculator's operand stack; a full stack takes nothing more.
fn ps_push(st: &mut Vec<f64>, v: f64) {
if st.len() < MAX_STACK {
st.push(v);
}
}
fn ps_run(code: &[PsOp], st: &mut Vec<f64>, depth: usize) {
if depth > 32 {
return;
}
let mut procs: Vec<&[PsOp]> = vec![];
for op in code {
match op {
PsOp::Num(n) => ps_push(st, *n),
PsOp::Proc(p) => procs.push(p),
PsOp::Op(o) => {
let pop = |st: &mut Vec<f64>| st.pop().unwrap_or(0.0);
let b = |v: bool| if v { 1.0 } else { 0.0 };
match o.as_str() {
"if" => {
let p = procs.pop();
if pop(st) != 0.0
&& let Some(p) = p
{
ps_run(p, st, depth + 1);
}
}
"ifelse" => {
let (f, t) = (procs.pop(), procs.pop());
let c = pop(st) != 0.0;
if let Some(p) = if c { t } else { f } {
ps_run(p, st, depth + 1);
}
}
"true" => ps_push(st, 1.0),
"false" => ps_push(st, 0.0),
"pop" => {
st.pop();
}
"dup" => {
let v = st.last().copied().unwrap_or(0.0);
ps_push(st, v);
}
"exch" => {
let n = st.len();
if n >= 2 {
st.swap(n - 1, n - 2);
}
}
"copy" => {
let k = pop(st).max(0.0) as usize;
let n = st.len();
// A copy that would pass the cap copies nothing.
if k <= n && n + k <= MAX_STACK {
let tail = st.get(n - k..).unwrap_or_default().to_vec();
st.extend(tail);
}
}
"index" => {
let k = pop(st).max(0.0) as usize;
let v = k.checked_add(1).and_then(|k| st.len().checked_sub(k)).and_then(|i| st.get(i)).copied().unwrap_or(0.0);
ps_push(st, v);
}
"roll" => {
let j = pop(st) as i64;
let n = pop(st).max(0.0) as usize;
let len = st.len();
if n > 0 && n <= len {
let s = &mut st[len - n..];
let r = j.rem_euclid(n as i64) as usize;
s.rotate_right(r);
}
}
_ => {
// Unary and binary operators.
let unary: Option<fn(f64) -> f64> = match o.as_str() {
"abs" => Some(f64::abs),
"neg" => Some(|x| -x),
"ceiling" => Some(f64::ceil),
"floor" => Some(f64::floor),
"round" => Some(|x: f64| (x + 0.5).floor()),
"truncate" | "cvi" => Some(f64::trunc),
"cvr" => Some(|x| x),
"sqrt" => Some(|x: f64| x.max(0.0).sqrt()),
"sin" => Some(|x: f64| x.to_radians().sin()),
"cos" => Some(|x: f64| x.to_radians().cos()),
"ln" => Some(|x: f64| x.max(1e-300).ln()),
"log" => Some(|x: f64| x.max(1e-300).log10()),
"not" => Some(|x: f64| {
if x == 0.0 {
1.0
} else if x == 1.0 {
0.0
} else {
!(x as i64) as f64
}
}),
_ => None,
};
if let Some(f) = unary {
let x = pop(st);
ps_push(st, f(x));
continue;
}
let y = pop(st);
let x = pop(st);
let v = match o.as_str() {
"add" => x + y,
"sub" => x - y,
"mul" => x * y,
"div" => {
if y != 0.0 {
x / y
} else {
0.0
}
}
// `checked_*` give 0 both for a zero divisor and for the one overflowing
// case, `i64::MIN / -1` (`/` and `%` panic on it in every build).
"idiv" => (x as i64).checked_div(y as i64).unwrap_or(0) as f64,
"mod" => (x as i64).checked_rem(y as i64).unwrap_or(0) as f64,
"exp" => x.powf(y),
"atan" => {
let a = x.atan2(y).to_degrees();
if a < 0.0 { a + 360.0 } else { a }
}
"eq" => b(x == y),
"ne" => b(x != y),
"gt" => b(x > y),
"ge" => b(x >= y),
"lt" => b(x < y),
"le" => b(x <= y),
"and" => ((x as i64) & (y as i64)) as f64,
"or" => ((x as i64) | (y as i64)) as f64,
"xor" => ((x as i64) ^ (y as i64)) as f64,
"bitshift" => {
let (v, s) = (x as i64, y as i64);
(if s >= 0 { v << s.min(62) } else { v >> (-s).min(62) }) as f64
}
_ => {
ps_push(st, x);
y
}
};
ps_push(st, v);
}
}
}
}
}
}
/// The most `f64`s one sampled table holds: 16 Mi (128 MiB), room for a 33 × 33 × 33 × 33 grid
/// with four outputs (4_743_684 samples). One table this large is allowed; what stops a file from
/// building many of them is [`Budget`], which caps the samples decoded across a whole
/// [`Func::read`] at the same figure.
const MAX_SAMPLES: usize = 1 << 24;
/// The most inputs or outputs of a function: no colour space has more than 32 components (the most
/// a DeviceN space may have), so a sampled function needs no more. Also the most one-output
/// functions a [`Func::Array`] holds (one per output). It is NOT a limit on the pieces of a
/// stitching function — a repeating gradient lists one piece once per repeat, often many more.
const MAX_IO: usize = 32;
/// The most `Func` nodes one top-level [`Func::read`] builds, across the whole structure of
/// references. A real function is a handful of nodes; a cyclic or fan-out reference graph would
/// build far more, so past this the whole function is unreadable. It is a soft limit, and the only
/// one on the pieces of a stitching function: past it a colour space takes its fallback (a
/// Separation tint reads as grey), nothing unsafe.
const MAX_NODES: usize = 10_000;
/// Samples in a table of `total` entries × `outputs`; `None` when that overflows or passes
/// [`MAX_SAMPLES`].
fn sample_count(total: usize, outputs: usize) -> Option<usize> {
total.checked_mul(outputs).filter(|n| *n <= MAX_SAMPLES)
}
/// What one top-level [`Func::read`] may build before the whole function is treated as unreadable:
/// a running cap on `Func` nodes and on sampled-table samples across the entire structure, so a
/// reference graph that is cyclic or fans out (one object listed many times at each of several
/// levels) cannot build an unbounded tree or decode unbounded memory. Samples of a table shared by
/// repeat references (one `Arc`) are charged once; its nodes are charged per copy.
struct Budget {
nodes: usize,
samples: usize,
/// Set once either cap is passed; the top-level read then yields [`Func::Unsupported`].
overrun: bool,
}
impl Budget {
fn new() -> Self {
Budget { nodes: MAX_NODES, samples: MAX_SAMPLES, overrun: false }
}
/// Charge `n` nodes; `false` (and the read is abandoned) once the cap is passed.
fn take_nodes(&mut self, n: usize) -> bool {
match self.nodes.checked_sub(n) {
Some(left) => {
self.nodes = left;
true
}
None => {
self.overrun = true;
false
}
}
}
/// Charge `n` samples; `false` once the cap is passed.
fn take_samples(&mut self, n: usize) -> bool {
match self.samples.checked_sub(n) {
Some(left) => {
self.samples = left;
true
}
None => {
self.overrun = true;
false
}
}
}
}
/// `v` limited to the range between `a` and `b`, in either order. Unlike [`f64::clamp`] this never
/// panics, whether a file gives the bounds reversed (`/Domain [1 0]`) or a bound is NaN.
fn clamp(v: f64, a: f64, b: f64) -> f64 {
let (lo, hi) = (a.min(b), a.max(b));
if v < lo {
lo
} else if v > hi {
hi
} else {
v
}
}
impl Func {
pub fn read(file: &File, o: &Obj) -> Func {
let mut budget = Budget::new();
let f = Func::read_at(file, o, 0, &mut budget);
// Either cap passed anywhere in the structure: the whole function is unreadable.
if budget.overrun { Func::Unsupported } else { f }
}
/// [`Func::read`] nested `depth` levels deep, charging `budget`: unsupported past [`MAX_DEPTH`]
/// or once the budget is spent.
fn read_at(file: &File, o: &Obj, depth: usize, budget: &mut Budget) -> Func {
if depth >= MAX_DEPTH || !budget.take_nodes(1) {
return Func::Unsupported;
}
let o = file.resolve(o);
if let Obj::Array(a) = o {
// An array of one-output functions: one per output, so at most `MAX_IO`.
if a.len() > MAX_IO {
return Func::Unsupported;
}
return Func::read_all(file, a, depth + 1, budget).map_or(Func::Unsupported, Func::Array);
}
let Some(d) = o.dict() else { return Func::Unsupported };
let dom = file.get(d, "Domain").map(|x| file.nums(x)).unwrap_or_default();
let domain = [dom.first().copied().unwrap_or(0.0), dom.get(1).copied().unwrap_or(1.0)];
match file.get_num(d, "FunctionType").unwrap_or(-1.0) as i32 {
2 => Func::Exp {
domain,
c0: file.get(d, "C0").map(|x| file.nums(x)).unwrap_or_else(|| vec![0.0]),
c1: file.get(d, "C1").map(|x| file.nums(x)).unwrap_or_else(|| vec![1.0]),
n: file.get_num(d, "N").unwrap_or(1.0),
},
3 => {
// A stitching function's pieces: no element cap (a repeating gradient lists one
// piece once per repeat); the budget bounds the total work.
let funcs = match file.get(d, "Functions").and_then(Obj::array) {
Some(a) => Func::read_all(file, a, depth + 1, budget),
None => Some(vec![]),
};
let Some(funcs) = funcs else { return Func::Unsupported };
Func::Stitch {
domain,
funcs,
bounds: file.get(d, "Bounds").map(|x| file.nums(x)).unwrap_or_default(),
encode: file.get(d, "Encode").map(|x| file.nums(x)).unwrap_or_default(),
}
}
0 => {
let Obj::Stream(sd, raw) = o else { return Func::Unsupported };
let Some(data) = decode_stream(file, sd, raw) else { return Func::Unsupported };
let sizes: Vec<usize> = file.get(d, "Size").map(|x| file.nums(x)).unwrap_or_default().iter().map(|v| v.max(0.0) as usize).collect();
let size = sizes.first().copied().unwrap_or(0);
let bps = file.get_num(d, "BitsPerSample").unwrap_or(8.0) as usize;
let range = file.get(d, "Range").map(|x| file.nums(x)).unwrap_or_default();
let outputs = range.len() / 2;
if size == 0 || outputs == 0 || outputs > MAX_IO || sizes.len() > MAX_IO || !matches!(bps, 1 | 2 | 4 | 8 | 12 | 16 | 24 | 32) {
return Func::Unsupported;
}
let total = sizes.iter().try_fold(1usize, |a, b| a.checked_mul(*b)).filter(|t| *t > 0 && *t <= 1 << 22);
let Some(total) = total else { return Func::Unsupported };
let Some(count) = sample_count(total, outputs) else { return Func::Unsupported };
if !budget.take_samples(count) {
return Func::Unsupported;
}
let enc = file.get(d, "Encode").map(|x| file.nums(x)).unwrap_or_default();
let encode = [enc.first().copied().unwrap_or(0.0), enc.get(1).copied().unwrap_or(size as f64 - 1.0)];
let decode = file.get(d, "Decode").map(|x| file.nums(x)).filter(|v| v.len() >= outputs * 2).unwrap_or_else(|| range.clone());
let max = ((1u64 << bps) - 1) as f64;
let mut bit = 0usize;
let samples: Arc<[f64]> = (0..count)
.map(|_| {
let mut v = 0u64;
for _ in 0..bps {
let byte = data.get(bit / 8).copied().unwrap_or(0);
v = (v << 1) | ((byte >> (7 - bit % 8)) & 1) as u64;
bit += 1;
}
v as f64 / max
})
.collect();
if sizes.len() > 1 {
let m = sizes.len();
let encode =
(0..m).flat_map(|i| [enc.get(2 * i).copied().unwrap_or(0.0), enc.get(2 * i + 1).copied().unwrap_or(sizes[i] as f64 - 1.0)]).collect();
let domain = (0..m).flat_map(|i| [dom.get(2 * i).copied().unwrap_or(0.0), dom.get(2 * i + 1).copied().unwrap_or(1.0)]).collect();
return Func::SampledN { domain, size: sizes, outputs, encode, decode, samples };
}
Func::Sampled { domain, size, outputs, encode, decode, samples }
}
4 => {
let Obj::Stream(sd, raw) = o else { return Func::Unsupported };
let Some(data) = decode_stream(file, sd, raw) else { return Func::Unsupported };
let mut lx = crate::object::Lexer::new(&data, 0);
// The program is one procedure: `{ … }`.
let code = match ps_parse(&mut lx, 0).into_iter().next() {
Some(PsOp::Proc(p)) => p,
_ => return Func::Unsupported,
};
Func::Calc { domain: dom, range: file.get(d, "Range").map(|x| file.nums(x)).unwrap_or_default(), code }
}
_ => Func::Unsupported,
}
}
/// The functions of an array (of one-output functions, or a stitching function's
/// `/Functions`) read at `depth`, charging `budget`; `None` once the budget is spent. An object
/// the array refers to more than once is read once and copied: the copies share its samples
/// (one `Arc`, charged once), but each copy is charged its nodes again — so a reference listed
/// many times at each of several levels spends the node budget quickly rather than expanding.
fn read_all(file: &File, a: &[Obj], depth: usize, budget: &mut Budget) -> Option<Vec<Func>> {
let mut cache: HashMap<(u32, u16), (Func, usize)> = HashMap::new();
let mut funcs = Vec::with_capacity(a.len());
for o in a {
if budget.overrun {
return None;
}
let f = match o {
Obj::Ref(n, g) => {
if let Some((cached, cost)) = cache.get(&(*n, *g)) {
let (cached, cost) = (cached.clone(), *cost);
if !budget.take_nodes(cost) {
return None;
}
cached
} else {
let before = budget.nodes;
let f = Func::read_at(file, o, depth, budget);
let cost = before.saturating_sub(budget.nodes);
cache.insert((*n, *g), (f.clone(), cost));
f
}
}
_ => Func::read_at(file, o, depth, budget),
};
funcs.push(f);
}
Some(funcs)
}
/// Evaluate at the first input (the functions used by shadings and tints take one input
/// in practice; extra inputs of DeviceN tints are averaged in).
pub fn eval(&self, input: &[f64]) -> Vec<f64> {
if let Func::Calc { domain, range, code } = self {
// The inputs start the operand stack, which holds at most `MAX_STACK` values.
let mut st: Vec<f64> = input
.iter()
.take(MAX_STACK)
.enumerate()
.map(|(i, v)| match (domain.get(2 * i), domain.get(2 * i + 1)) {
(Some(a), Some(b)) => clamp(*v, *a, *b),
_ => *v,
})
.collect();
ps_run(code, &mut st, 0);
let n = range.len() / 2;
let k = st.len().saturating_sub(n);
return st.get(k..).unwrap_or_default().iter().zip(range.as_chunks::<2>().0).map(|(v, [a, b])| clamp(*v, *a, *b)).collect();
}
match self {
Func::SampledN { domain, size, outputs, encode, decode, samples } => {
let m = size.len();
// Each input → a sample-table coordinate, then the 2^m surrounding samples.
let mut base = vec![0usize; m];
let mut frac = vec![0.0f64; m];
for i in 0..m {
let x = input.get(i).copied().unwrap_or(0.0);
let (d0, d1) = (domain[2 * i], domain[2 * i + 1]);
let x = clamp(x, d0, d1);
let e = if d1 != d0 { encode[2 * i] + (x - d0) / (d1 - d0) * (encode[2 * i + 1] - encode[2 * i]) } else { encode[2 * i] };
let e = if e.is_finite() { clamp(e, 0.0, size[i] as f64 - 1.0) } else { 0.0 };
base[i] = e.floor() as usize;
frac[i] = e - e.floor();
}
let corners = if m <= 6 { 1usize << m } else { 1 };
let mut out = vec![0.0; *outputs];
for c in 0..corners {
let mut w = 1.0;
let mut idx = 0usize;
let mut stride = 1usize;
for i in 0..m {
let up = m <= 6 && (c >> i) & 1 == 1;
w *= if up { frac[i] } else { 1.0 - frac[i] };
let k = if up { (base[i] + 1).min(size[i] - 1) } else { base[i] };
idx += k * stride;
stride *= size[i];
}
if w == 0.0 {
continue;
}
for (o, v) in out.iter_mut().enumerate() {
*v += w * samples.get(idx * outputs + o).copied().unwrap_or(0.0);
}
}
for (o, v) in out.iter_mut().enumerate() {
let (d0, d1) = (decode.get(2 * o).copied().unwrap_or(0.0), decode.get(2 * o + 1).copied().unwrap_or(1.0));
*v = d0 + *v * (d1 - d0);
}
out
}
Func::Array(fs) if input.len() > 1 => fs.iter().map(|f| f.eval(input).first().copied().unwrap_or(0.0)).collect(),
_ => self.eval1(input.first().copied().unwrap_or(0.0)),
}
}
pub fn eval1(&self, t: f64) -> Vec<f64> {
match self {
Func::Exp { domain, c0, c1, n } => {
let t = clamp(t, domain[0], domain[1]);
let x = if *n == 1.0 { t } else { t.max(0.0).powf(*n) };
(0..c0.len().max(c1.len()))
.map(|i| c0.get(i).copied().unwrap_or(0.0) + x * (c1.get(i).copied().unwrap_or(1.0) - c0.get(i).copied().unwrap_or(0.0)))
.collect()
}
Func::Stitch { domain, funcs, bounds, encode } => {
if funcs.is_empty() {
return vec![0.0];
}
let t = clamp(t, domain[0], domain[1]);
let k = bounds.iter().take_while(|b| t >= **b).count().min(funcs.len() - 1);
let lo = if k == 0 { domain[0] } else { bounds[k - 1] };
let hi = bounds.get(k).copied().unwrap_or(domain[1]);
let (e0, e1) = (encode.get(2 * k).copied().unwrap_or(0.0), encode.get(2 * k + 1).copied().unwrap_or(1.0));
let u = if hi > lo { e0 + (t - lo) / (hi - lo) * (e1 - e0) } else { e0 };
funcs[k].eval1(u)
}
Func::Sampled { domain, size, outputs, encode, decode, samples } => {
let t = clamp(t, domain[0], domain[1]);
let e = if domain[1] > domain[0] { encode[0] + (t - domain[0]) / (domain[1] - domain[0]) * (encode[1] - encode[0]) } else { encode[0] };
let e = clamp(e, 0.0, *size as f64 - 1.0);
let (i0, f) = (e.floor() as usize, e.fract());
let i1 = (i0 + 1).min(size - 1);
(0..*outputs)
.map(|o| {
let s = samples[i0 * outputs + o] * (1.0 - f) + samples[i1 * outputs + o] * f;
let (d0, d1) = (decode.get(2 * o).copied().unwrap_or(0.0), decode.get(2 * o + 1).copied().unwrap_or(1.0));
d0 + s * (d1 - d0)
})
.collect()
}
Func::Array(fs) => fs.iter().map(|f| f.eval1(t).first().copied().unwrap_or(0.0)).collect(),
Func::Calc { .. } | Func::SampledN { .. } => self.eval(&[t]),
Func::Unsupported => vec![0.5],
}
}
/// Input values worth sampling exactly (stitching bounds).
pub fn breakpoints(&self) -> Vec<f64> {
match self {
Func::Stitch { bounds, .. } => bounds.clone(),
_ => vec![],
}
}
}
/// PDF text string → Rust string (UTF-16BE with a byte-order mark, else PDFDocEncoding ≈ Latin-1).
pub fn text_string(b: &[u8]) -> String {
if b.starts_with(&[0xFE, 0xFF]) {
let u: Vec<u16> = b[2..].as_chunks::<2>().0.iter().map(|c| u16::from_be_bytes([c[0], c[1]])).collect();
return String::from_utf16_lossy(&u);
}
if let Some(rest) = b.strip_prefix(&[0xEF, 0xBB, 0xBF]) {
return String::from_utf8_lossy(rest).into_owned();
}
b.iter().map(|&c| c as char).collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn sample_count_at_and_over_the_cap() {
// 4 Mi entries × 4 outputs fill the cap exactly; a fifth output passes it.
assert_eq!(sample_count(1 << 22, 4), Some(MAX_SAMPLES));
assert_eq!(sample_count(1 << 22, 5), None);
// A 33 × 33 × 33 × 33 grid with four outputs fits (4_743_684 samples, under the cap, so
// `Some`).
assert_eq!(sample_count(33 * 33 * 33 * 33, 4), Some(4_743_684));
// A product that overflows is refused (on 64-bit targets that takes a `/Range` of at least
// 2^41 numbers, too big to build in a test).
assert_eq!(sample_count(1 << 22, usize::MAX / (1 << 22) + 1), None);
}
#[test]
fn calculator_functions() {
// Two inputs → three outputs: { 2 copy mul 3 1 roll add 2 div dup 0.5 gt { pop 1 } if 0 }
let code = b"{ 2 copy mul 3 1 roll add 2 div dup 0.5 gt { pop 1 } { 0.25 mul } ifelse 0 }";
let mut lx = crate::object::Lexer::new(code, 0);
let Some(PsOp::Proc(code)) = ps_parse(&mut lx, 0).into_iter().next() else { panic!() };
let f = Func::Calc { domain: vec![0.0, 1.0, 0.0, 1.0], range: vec![0.0, 1.0, 0.0, 1.0, 0.0, 1.0], code };
assert_eq!(f.eval(&[0.5, 0.4]), vec![0.2, 0.1125, 0.0]);
assert_eq!(f.eval(&[1.0, 0.8]), vec![0.8, 1.0, 0.0]);
}
/// Run the calculator program `{ src }` on the stack `st`.
fn run(src: &str, mut st: Vec<f64>) -> Vec<f64> {
let src = format!("{{ {src} }}");
let mut lx = crate::object::Lexer::new(src.as_bytes(), 0);
let Some(PsOp::Proc(code)) = ps_parse(&mut lx, 0).into_iter().next() else { panic!() };
ps_run(&code, &mut st, 0);
st
}
#[test]
fn calculator_stack_holds_at_most_100_values() {
// `1 copy 2 copy 4 copy …`: 40 doublings asked for 2^40 values (8 TiB). The copies stop at
// 64 values, since the next would pass 100.
let doublings: String = (0..40).map(|i| format!("{} copy ", 1u64 << i)).collect();
assert_eq!(run(&doublings, vec![0.0]).len(), 64);
// A copy up to exactly 100 values is made; after it nothing grows the stack.
let fifty: Vec<f64> = (0..50).map(f64::from).collect();
let full = run("50 copy", fifty.clone());
assert_eq!(full.len(), 100);
assert_eq!(full[50..], fifty[..]);
for op in ["7", "true", "false", "dup", "0 index", "1 copy", "neg", "add", "nonsense"] {
assert!(run(op, full.clone()).len() <= 100, "{op}");
}
// Nor does a long program without loops: one push per operator, up to the cap.
for op in ["1 ", "true ", "dup ", "0 index "] {
assert_eq!(run(&op.repeat(1000), vec![1.0]).len(), 100, "{op}");
}
}
#[test]
fn calculator_index_past_the_stack_pushes_zero() {
// 10^20 is past usize::MAX: `k + 1` overflowed (a panic), or wrapped to read past the stack.
assert_eq!(run("99999999999999999999 index", vec![1.0, 2.0]), vec![1.0, 2.0, 0.0]);
assert_eq!(run("2 index", vec![1.0, 2.0]), vec![1.0, 2.0, 0.0]);
assert_eq!(run("1 index", vec![1.0, 2.0]), vec![1.0, 2.0, 1.0]);
}
#[test]
fn calculator_copy_index_and_roll_below_the_cap() {
assert_eq!(run("3 copy 1 index 4 1 roll", vec![1.0, 2.0, 3.0]), vec![1.0, 2.0, 3.0, 2.0, 1.0, 2.0, 3.0]);
assert_eq!(run("3 -1 roll dup", vec![1.0, 2.0, 3.0]), vec![2.0, 3.0, 1.0, 1.0]);
}
#[test]
fn calculator_idiv_and_mod_of_i64_min_by_minus_one() {
// `i64::MIN / -1` and `i64::MIN % -1` overflow and panic (in debug and release); `idiv` and
// `mod` must fall back like a zero divisor does. -2^63 is below any f64 the program sees,
// but the cast saturates to i64::MIN, which is enough to trigger it.
let min = -(2f64.powi(63));
assert_eq!(run("idiv", vec![min, -1.0]), vec![0.0]);
assert_eq!(run("mod", vec![min, -1.0]), vec![0.0]);
// Divide by zero still gives 0, ordinary division still works.
assert_eq!(run("idiv", vec![7.0, 0.0]), vec![0.0]);
assert_eq!(run("mod", vec![7.0, 0.0]), vec![0.0]);
assert_eq!(run("idiv", vec![7.0, 2.0]), vec![3.0]);
assert_eq!(run("mod", vec![7.0, 2.0]), vec![1.0]);
}
}