pdfrum_page/function/postscript/
mod.rs

1//! Type 4: the PostScript calculator (ISO 32000-1 §7.10.5).
2//!
3//! A program is one outer `{ … }` procedure. Parsing is strict about
4//! exactly two things — the program must **begin** with `{`, and an
5//! unterminated `{` is a failure — and lenient about everything else: an
6//! unrecognised token becomes the constant `0.0`.
7//!
8//! Nesting is capped at 128, compared with `>`, so **129 levels** including
9//! the outer procedure are accepted and the 130th is refused. Execution
10//! recursion has no separate limit; it is bounded by that parse depth.
11
12mod eval;
13mod op;
14
15pub use op::PsOp;
16
17use super::Common;
18use crate::names;
19use eval::Machine;
20use pdfrum_common::{DiagKind, Diagnostics, Limits, Severity};
21use pdfrum_filters::decode_chain;
22use pdfrum_object::{Resolve, Stream};
23
24/// Nesting cap, compared with `>` so 128 is accepted.
25pub const MAX_NESTING: u32 = 128;
26
27/// One instruction inside a procedure.
28#[derive(Debug, Clone, PartialEq)]
29enum ProcItem {
30    /// A nested `{ … }` block.
31    Proc(Proc),
32    /// A literal value.
33    Const(f32),
34    /// A named operator.
35    Op(PsOp),
36}
37
38/// A `{ … }` block.
39#[derive(Debug, Clone, PartialEq, Default)]
40struct Proc {
41    items: Vec<ProcItem>,
42}
43
44/// A type 4 function.
45#[derive(Debug, Clone, PartialEq)]
46pub struct PostScript {
47    /// `/Domain`.
48    pub domain: Box<[f32]>,
49    /// `/Range`, which is required for this type.
50    pub range: Box<[f32]>,
51    /// How many outputs, from `/Range`.
52    pub outputs: usize,
53    /// The parsed program.
54    program: Proc,
55}
56
57impl PostScript {
58    /// Load from a stream, parsing the program.
59    pub(super) fn load<R: Resolve>(
60        stream: &Stream,
61        common: &Common,
62        r: &R,
63        limits: &Limits,
64        diags: &mut Diagnostics,
65    ) -> Option<Self> {
66        // `/Range` is required for this type.
67        let outputs = common.outputs();
68        if outputs == 0 {
69            return None;
70        }
71        let _ = names::FUNCTION_TYPE;
72        let source = decode_chain(stream, 0, r, limits, diags).data;
73        let program = parse(&source)?;
74        Some(Self {
75            domain: common.domain.clone(),
76            range: common.range.clone(),
77            outputs,
78            program,
79        })
80    }
81
82    /// Evaluate.
83    ///
84    /// The only condition that reports failure is the stack holding fewer
85    /// values than there are outputs; every other misbehaviour is absorbed
86    /// silently, exactly as the C++ absorbs it.
87    pub(super) fn eval(&self, input: &[f32], out: &mut [f32]) -> bool {
88        let mut machine = Machine::new();
89        machine.push_inputs(input);
90        let _ = machine.run(&self.program);
91        machine.take_outputs(out, self.outputs)
92    }
93
94    /// Evaluate, reporting what the engine noticed going wrong.
95    ///
96    /// The plain `eval` path swallows these, which is the behaviour
97    /// contract; this variant exists so a caller that owns a diagnostics sink
98    /// can record them.
99    pub fn eval_with_diagnostics(
100        &self,
101        input: &[f32],
102        out: &mut [f32],
103        diags: &mut Diagnostics,
104    ) -> bool {
105        let mut machine = Machine::new();
106        machine.push_inputs(input);
107        let _ = machine.run(&self.program);
108        if machine.abused_stack {
109            diags.record(Severity::Suspicious, DiagKind::PostScriptStackAbuse, None);
110        }
111        if machine.malformed_proc {
112            diags.record(
113                Severity::Suspicious,
114                DiagKind::PostScriptMalformedProc,
115                None,
116            );
117        }
118        machine.take_outputs(out, self.outputs)
119    }
120
121    /// How many values the program leaves on the stack for the given input,
122    /// for tests that need to see the machine rather than the function.
123    #[must_use]
124    pub fn stack_depth_after(&self, input: &[f32]) -> usize {
125        let mut machine = Machine::new();
126        machine.push_inputs(input);
127        let _ = machine.run(&self.program);
128        machine.len()
129    }
130}
131
132/// Split a program into words, treating `{` and `}` as one-byte tokens and
133/// skipping `%` comments to end of line.
134struct Words<'a> {
135    data: &'a [u8],
136    pos: usize,
137}
138
139impl<'a> Iterator for Words<'a> {
140    type Item = &'a [u8];
141
142    fn next(&mut self) -> Option<Self::Item> {
143        loop {
144            let b = self.data.get(self.pos).copied()?;
145            if matches!(b, 0x00 | 0x09 | 0x0A | 0x0C | 0x0D | 0x20) {
146                self.pos += 1;
147            } else if b == b'%' {
148                while let Some(c) = self.data.get(self.pos).copied() {
149                    self.pos += 1;
150                    if c == b'\r' || c == b'\n' {
151                        break;
152                    }
153                }
154            } else {
155                break;
156            }
157        }
158        let start = self.pos;
159        let first = self.data.get(self.pos).copied()?;
160        if matches!(
161            first,
162            b'{' | b'}' | b'[' | b']' | b'(' | b')' | b'<' | b'>' | b'/'
163        ) {
164            self.pos += 1;
165            return self.data.get(start..self.pos);
166        }
167        while let Some(b) = self.data.get(self.pos).copied() {
168            if matches!(b, 0x00 | 0x09 | 0x0A | 0x0C | 0x0D | 0x20)
169                || matches!(
170                    b,
171                    b'{' | b'}' | b'[' | b']' | b'(' | b')' | b'<' | b'>' | b'/' | b'%'
172                )
173            {
174                break;
175            }
176            self.pos += 1;
177        }
178        self.data.get(start..self.pos)
179    }
180}
181
182/// Parse a program: a single outer procedure.
183fn parse(source: &[u8]) -> Option<Proc> {
184    let mut words = Words {
185        data: source,
186        pos: 0,
187    };
188    // The program **must** begin with `{`.
189    if words.next()? != b"{" {
190        return None;
191    }
192    parse_proc(&mut words, 0)
193}
194
195/// Parse the body of a procedure whose `{` has already been consumed.
196fn parse_proc(words: &mut Words<'_>, depth: u32) -> Option<Proc> {
197    if depth > MAX_NESTING {
198        return None;
199    }
200    let mut items = Vec::new();
201    loop {
202        // End of data with the brace still open is a parse failure.
203        let word = words.next()?;
204        match word {
205            b"}" => return Some(Proc { items }),
206            b"{" => items.push(ProcItem::Proc(parse_proc(words, depth + 1)?)),
207            _ => items.push(match PsOp::from_name(word) {
208                Some(op) => ProcItem::Op(op),
209                // An unrecognised token is a constant, and one that will not
210                // parse as a number is the constant zero.
211                None => ProcItem::Const(parse_number(word)),
212            }),
213        }
214    }
215}
216
217/// `StringToFloat`: a decimal reading that yields 0.0 for anything else.
218fn parse_number(word: &[u8]) -> f32 {
219    std::str::from_utf8(word)
220        .ok()
221        .and_then(|s| s.parse::<f32>().ok())
222        .filter(|v| v.is_finite())
223        .unwrap_or(0.0)
224}
225
226/// Build a function from a bare program, for tests and for callers that hold
227/// a program rather than a stream.
228#[must_use]
229pub fn parse_program(source: &[u8], domain: &[f32], range: &[f32]) -> Option<PostScript> {
230    Some(PostScript {
231        domain: domain.into(),
232        range: range.into(),
233        outputs: range.len() / 2,
234        program: parse(source)?,
235    })
236}
237
238#[cfg(test)]
239mod tests {
240    // Test fixtures quote the oracle's own vectors, compare floats exactly
241    // where the behaviour being pinned is exact, and index arrays whose
242    // length the fixture itself fixes.
243    #![allow(
244        clippy::unreadable_literal,
245        clippy::float_cmp,
246        clippy::indexing_slicing,
247        clippy::cast_precision_loss,
248        clippy::cast_possible_truncation,
249        reason = "test fixtures quote oracle vectors verbatim and compare exactly"
250    )]
251
252    use super::eval::STACK_SIZE;
253    use super::{MAX_NESTING, PostScript, PsOp, parse_program};
254
255    fn run(program: &str, inputs: &[f32], outputs: usize) -> Vec<f32> {
256        let range: Vec<f32> = (0..outputs).flat_map(|_| [-1e30, 1e30]).collect();
257        let domain: Vec<f32> = (0..inputs.len()).flat_map(|_| [-1e30, 1e30]).collect();
258        let f = parse_program(program.as_bytes(), &domain, &range).expect("parses");
259        let mut out = vec![0.0f32; outputs];
260        assert!(f.eval(inputs, &mut out), "evaluation should succeed");
261        out
262    }
263
264    fn one(program: &str) -> f32 {
265        run(program, &[], 1).first().copied().unwrap_or(f32::NAN)
266    }
267
268    fn close(a: f32, b: f32) -> bool {
269        (a - b).abs() < 1e-4
270    }
271
272    #[test]
273    fn arithmetic_basics() {
274        assert!(close(one("{100 200 add}"), 300.0));
275        assert!(close(one("{100 150 sub}"), -50.0));
276        assert!(close(one("{5 120 mul}"), 600.0));
277        assert!(close(one("{15 10 div}"), 1.5));
278        assert!(close(one("{15 10 idiv}"), 1.0));
279        assert!(close(one("{15 10 mod}"), 5.0));
280        assert!(close(one("{-5 neg}"), 5.0));
281        assert!(close(one("{-5 abs}"), 5.0));
282    }
283
284    #[test]
285    fn division_by_zero_yields_zero_everywhere() {
286        assert!(close(one("{100 0 idiv}"), 0.0));
287        assert!(close(one("{100 0 mod}"), 0.0));
288        assert!(close(one("{100 0 div}"), 0.0));
289    }
290
291    #[test]
292    fn rounding_operators() {
293        assert!(close(one("{5.5 round}"), 6.0));
294        // Half-way values round *up*, so −5.5 becomes −5.
295        assert!(close(one("{-5.5 round}"), -5.0));
296        assert!(close(one("{5.9 ceiling}"), 6.0));
297        assert!(close(one("{-5.1 ceiling}"), -5.0));
298        assert!(close(one("{5.9 floor}"), 5.0));
299        assert!(close(one("{-5.1 floor}"), -6.0));
300        assert!(close(one("{5.9 truncate}"), 5.0));
301        assert!(close(one("{-5.9 truncate}"), -5.0));
302        assert!(close(one("{5.9 cvi}"), 5.0));
303    }
304
305    #[test]
306    fn truncate_saturates_rather_than_overflowing() {
307        // crbug 42270316: `f32(i32::MAX) * -1.5` saturates to `i32::MIN`,
308        // whose float value is `-f32(i32::MAX) - 1`.
309        let program = format!("{{{} truncate}}", (i32::MAX as f32) * -1.5);
310        let got = one(&program);
311        assert!(got <= -2.0e9, "got {got}");
312        assert!(got.is_finite());
313    }
314
315    #[test]
316    fn comparisons_push_one_or_zero() {
317        for (program, want) in [
318            ("{0 0 eq}", 1.0),
319            ("{0 1 eq}", 0.0),
320            ("{0 0 ne}", 0.0),
321            ("{0 1 ne}", 1.0),
322            ("{255 1 gt}", 1.0),
323            ("{-1 0 gt}", 0.0),
324            ("{0 0 ge}", 1.0),
325            ("{-1 0 lt}", 1.0),
326            ("{255 1 le}", 0.0),
327        ] {
328            assert!(close(one(program), want), "{program} should give {want}");
329        }
330    }
331
332    #[test]
333    fn logic_operators_are_bitwise_except_not() {
334        assert!(close(one("{true}"), 1.0));
335        assert!(close(one("{false}"), 0.0));
336        assert!(close(one("{1 1 and}"), 1.0));
337        assert!(close(one("{1 0 and}"), 0.0));
338        assert!(close(one("{1 0 or}"), 1.0));
339        assert!(close(one("{1 1 xor}"), 0.0));
340        assert!(close(one("{6 3 and}"), 2.0));
341        // `not` is logical, not a bitwise complement: 1 gives 0, not −2.
342        assert!(close(one("{0 not}"), 1.0));
343        assert!(close(one("{1 not}"), 0.0));
344    }
345
346    #[test]
347    fn maths_functions_work_in_degrees() {
348        assert!(close(one("{2 sqrt}"), std::f32::consts::SQRT_2));
349        assert!(close(one("{60 sin}"), 0.8660254));
350        assert!(close(one("{60 cos}"), 0.5));
351        assert!(close(one("{1 1 atan}"), 45.0));
352        assert!(close(one("{10 3 exp}"), 1000.0));
353        assert!(close(one("{1000 log}"), 3.0));
354        assert!(close(one("{10 ln}"), std::f32::consts::LN_10));
355    }
356
357    #[test]
358    fn atan_normalizes_into_zero_to_three_sixty() {
359        let got = one("{-1 -1 atan}");
360        assert!((0.0..360.0).contains(&got), "got {got}");
361        assert!(close(got, 225.0));
362    }
363
364    #[test]
365    fn unknown_tokens_become_the_constant_zero() {
366        assert!(close(one("{invalid}"), 0.0));
367        assert!(close(one("{55}"), 55.0));
368        assert!(close(one("{123.4}"), 123.4));
369        assert!(close(one("{-5}"), -5.0));
370        assert!(PsOp::from_name(b"invalid").is_none());
371    }
372
373    #[test]
374    fn a_program_must_begin_with_a_brace_and_be_terminated() {
375        assert!(parse_program(b"100 200 add", &[], &[0.0, 1.0]).is_none());
376        assert!(parse_program(b"{100 200 add", &[], &[0.0, 1.0]).is_none());
377        assert!(parse_program(b"", &[], &[0.0, 1.0]).is_none());
378        assert!(parse_program(b"{}", &[], &[0.0, 1.0]).is_some());
379    }
380
381    #[test]
382    fn nesting_is_accepted_to_the_cap_and_refused_beyond() {
383        let build = |levels: u32| {
384            let mut s = String::new();
385            for _ in 0..levels {
386                s.push('{');
387            }
388            for _ in 0..levels {
389                s.push('}');
390            }
391            s
392        };
393        // The outer procedure is level one, so `MAX_NESTING + 1` levels fit.
394        let ok = build(MAX_NESTING + 1);
395        assert!(parse_program(ok.as_bytes(), &[], &[0.0, 1.0]).is_some());
396        let too_deep = build(MAX_NESTING + 2);
397        assert!(parse_program(too_deep.as_bytes(), &[], &[0.0, 1.0]).is_none());
398    }
399
400    #[test]
401    fn if_and_ifelse_locate_their_procedures_lexically() {
402        assert!(close(one("{1 {7} if}"), 7.0));
403        // A false condition runs nothing, so the earlier constant survives.
404        assert!(close(one("{3 0 {7} if}"), 3.0));
405        // True selects the **first** procedure.
406        assert!(close(one("{1 {7} {9} ifelse}"), 7.0));
407        assert!(close(one("{0 {7} {9} ifelse}"), 9.0));
408    }
409
410    #[test]
411    fn truthiness_truncates_so_a_half_reads_as_false() {
412        assert!(close(one("{3 0.5 {7} if}"), 3.0));
413        assert!(close(one("{1.5 {7} if}"), 7.0));
414    }
415
416    #[test]
417    fn a_malformed_if_aborts_only_its_own_procedure() {
418        // An `if` with no preceding procedure aborts the procedure it is in,
419        // so the trailing `9` is never pushed. The abort itself is *not* an
420        // error — `Execute`'s return value is discarded — so evaluation
421        // succeeds with whatever the stack happens to hold.
422        let f = parse_program(b"{5 9 if 7}", &[], &[-1e30, 1e30]).expect("parses");
423        let mut out = [0.0f32];
424        assert!(f.eval(&[], &mut out));
425        // The structural check runs *before* the condition is popped, so
426        // nothing was consumed and the `7` after the abort never ran: the
427        // stack still holds `5 9`, and the single output takes the top.
428        assert!(close(out[0], 9.0), "got {}", out[0]);
429        // Inside a branch, a structural failure does not abort the parent.
430        assert!(close(one("{4 1 {if} if}"), 4.0));
431    }
432
433    #[test]
434    fn stack_overflow_drops_pushes_silently() {
435        let mut program = String::from("{");
436        for _ in 0..STACK_SIZE + 5 {
437            program.push_str("1 ");
438        }
439        program.push('}');
440        let f = parse_program(program.as_bytes(), &[], &[-1e30, 1e30]).expect("parses");
441        assert_eq!(f.stack_depth_after(&[]), STACK_SIZE);
442        let mut out = [0.0f32];
443        assert!(f.eval(&[], &mut out));
444    }
445
446    #[test]
447    fn copy_index_and_roll_bounds_cases() {
448        // `copy` with an out-of-range count is a no-op that still eats `n`.
449        assert!(close(one("{7 5 copy}"), 7.0));
450        assert!(close(one("{7 -1 copy}"), 7.0));
451        assert!(close(one("{7 0 copy}"), 7.0));
452        // A legal copy duplicates.
453        assert_eq!(run("{1 2 2 copy}", &[], 4), vec![1.0, 2.0, 1.0, 2.0]);
454        // `index` 0 is the top.
455        assert!(close(one("{9 8 0 index}"), 8.0));
456        // Out of range pushes nothing, so the stack net-shrinks.
457        assert!(close(one("{9 8 5 index}"), 8.0));
458        // `roll` rotates towards the top for a positive count.
459        assert_eq!(run("{1 2 3 3 1 roll}", &[], 3), vec![3.0, 1.0, 2.0]);
460        assert_eq!(run("{1 2 3 3 -1 roll}", &[], 3), vec![2.0, 3.0, 1.0]);
461        // Degenerate counts are no-ops.
462        assert_eq!(run("{1 2 3 0 0 roll}", &[], 3), vec![1.0, 2.0, 3.0]);
463    }
464
465    #[test]
466    fn bitshift_collapses_every_overflow_to_zero() {
467        assert!(close(one("{1 4 bitshift}"), 16.0));
468        assert!(close(one("{16 -4 bitshift}"), 1.0));
469        // Arithmetic, so a negative value keeps its sign.
470        assert!(close(one("{-16 -2 bitshift}"), -4.0));
471        // A shift past the word width, and INT_MIN's negation, both give 0.
472        assert!(close(one("{1 99 bitshift}"), 0.0));
473        assert!(close(one(&format!("{{1 {} bitshift}}", i32::MIN)), 0.0));
474    }
475
476    #[test]
477    fn outputs_come_off_the_top_of_the_stack_in_reverse() {
478        // The topmost value is the *last* output.
479        assert_eq!(run("{1 2 3}", &[], 3), vec![1.0, 2.0, 3.0]);
480        // Residue below the outputs is ignored.
481        assert_eq!(run("{9 9 1 2}", &[], 2), vec![1.0, 2.0]);
482    }
483
484    #[test]
485    fn too_few_stack_values_is_the_one_reported_failure() {
486        let f = parse_program(b"{1}", &[], &[0.0, 1.0, 0.0, 1.0]).expect("parses");
487        let mut out = [0.0f32; 2];
488        assert!(!f.eval(&[], &mut out));
489    }
490
491    #[test]
492    fn diagnostics_report_what_the_silent_paths_swallowed() {
493        let mut program = String::from("{");
494        for _ in 0..STACK_SIZE + 5 {
495            program.push_str("1 ");
496        }
497        program.push('}');
498        let f: PostScript = parse_program(program.as_bytes(), &[], &[-1e30, 1e30]).expect("parses");
499        let mut diags = pdfrum_common::Diagnostics::default();
500        let mut out = [0.0f32];
501        f.eval_with_diagnostics(&[], &mut out, &mut diags);
502        assert!(diags.contains(&pdfrum_common::DiagKind::PostScriptStackAbuse));
503    }
504}
pdfrum_page/function/postscript/mod.rs

pdfrum_page/function/postscript/
mod.rs
