skrifa/outline/glyf/hint/
value_stack.rs

Help
1//! Value stack for TrueType interpreter.
2//!
3use raw::types::F26Dot6;
4use read_fonts::tables::glyf::bytecode::InlineOperands;
5
6use super::error::HintErrorKind;
7
8use HintErrorKind::{ValueStackOverflow, ValueStackUnderflow};
9
10/// Value stack for the TrueType interpreter.
11///
12/// This uses a slice as the backing store rather than a `Vec` to enable
13/// support for allocation from user buffers.
14///
15/// See <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#managing-the-stack>
16pub struct ValueStack<'a> {
17    values: &'a mut [i32],
18    len: usize,
19    pub(super) is_pedantic: bool,
20}
21
22impl<'a> ValueStack<'a> {
23    pub fn new(values: &'a mut [i32], is_pedantic: bool) -> Self {
24        Self {
25            values,
26            len: 0,
27            is_pedantic,
28        }
29    }
30
31    /// Returns the depth of the stack
32    /// <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#returns-the-depth-of-the-stack>
33    pub fn len(&self) -> usize {
34        self.len
35    }
36
37    #[cfg(test)]
38    fn is_empty(&self) -> bool {
39        self.len == 0
40    }
41
42    // This is used in tests and also useful for tracing.
43    #[allow(dead_code)]
44    pub fn values(&self) -> &[i32] {
45        &self.values[..self.len]
46    }
47
48    pub fn push(&mut self, value: i32) -> Result<(), HintErrorKind> {
49        let ptr = self
50            .values
51            .get_mut(self.len)
52            .ok_or(HintErrorKind::ValueStackOverflow)?;
53        *ptr = value;
54        self.len += 1;
55        Ok(())
56    }
57
58    /// Pushes values that have been decoded from the instruction stream
59    /// onto the stack.
60    ///
61    /// Implements the PUSHB[], PUSHW[], NPUSHB[] and NPUSHW[] instructions.
62    ///
63    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#pushing-data-onto-the-interpreter-stack>
64    pub fn push_inline_operands(&mut self, operands: &InlineOperands) -> Result<(), HintErrorKind> {
65        let push_count = operands.len();
66        let stack_base = self.len;
67        for (stack_value, value) in self
68            .values
69            .get_mut(stack_base..stack_base + push_count)
70            .ok_or(ValueStackOverflow)?
71            .iter_mut()
72            .zip(operands.values())
73        {
74            *stack_value = value;
75        }
76        self.len += push_count;
77        Ok(())
78    }
79
80    pub fn peek(&mut self) -> Option<i32> {
81        if self.len > 0 {
82            self.values.get(self.len - 1).copied()
83        } else {
84            None
85        }
86    }
87
88    /// Pops a value from the stack.
89    ///
90    /// Implements the POP[] instruction.
91    ///
92    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#pop-top-stack-element>
93    pub fn pop(&mut self) -> Result<i32, HintErrorKind> {
94        if let Some(value) = self.peek() {
95            self.len -= 1;
96            Ok(value)
97        } else if self.is_pedantic {
98            Err(ValueStackUnderflow)
99        } else {
100            Ok(0)
101        }
102    }
103
104    /// Convenience method for instructions that expect values in 26.6 format.
105    pub fn pop_f26dot6(&mut self) -> Result<F26Dot6, HintErrorKind> {
106        Ok(F26Dot6::from_bits(self.pop()?))
107    }
108
109    /// Convenience method for instructions that pop values that are used as an
110    /// index.
111    pub fn pop_usize(&mut self) -> Result<usize, HintErrorKind> {
112        Ok(self.pop()? as usize)
113    }
114
115    /// Convenience method for popping a value intended as a count.
116    ///
117    /// When a negative value is encountered, returns an error in pedantic mode
118    /// or 0 otherwise.
119    pub fn pop_count_checked(&mut self) -> Result<usize, HintErrorKind> {
120        let value = self.pop()?;
121        if value < 0 && self.is_pedantic {
122            Err(HintErrorKind::InvalidStackValue(value))
123        } else {
124            Ok(value.max(0) as usize)
125        }
126    }
127
128    /// Applies a unary operation.
129    ///
130    /// Pops `a` from the stack and pushes `op(a)`.
131    pub fn apply_unary(
132        &mut self,
133        mut op: impl FnMut(i32) -> Result<i32, HintErrorKind>,
134    ) -> Result<(), HintErrorKind> {
135        let a = self.pop()?;
136        self.push(op(a)?)
137    }
138
139    /// Applies a binary operation.
140    ///
141    /// Pops `b` and `a` from the stack and pushes `op(a, b)`.
142    pub fn apply_binary(
143        &mut self,
144        mut op: impl FnMut(i32, i32) -> Result<i32, HintErrorKind>,
145    ) -> Result<(), HintErrorKind> {
146        let b = self.pop()?;
147        let a = self.pop()?;
148        self.push(op(a, b)?)
149    }
150
151    /// Clear the entire stack.
152    ///
153    /// Implements the CLEAR[] instruction.
154    ///
155    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#clear-the-entire-stack>
156    pub fn clear(&mut self) {
157        self.len = 0;
158    }
159
160    /// Duplicate top stack element.
161    ///
162    /// Implements the DUP[] instruction.
163    ///
164    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#duplicate-top-stack-element>
165    pub fn dup(&mut self) -> Result<(), HintErrorKind> {
166        if let Some(value) = self.peek() {
167            self.push(value)
168        } else if self.is_pedantic {
169            Err(ValueStackUnderflow)
170        } else {
171            self.push(0)
172        }
173    }
174
175    /// Swap the top two elements on the stack.
176    ///
177    /// Implements the SWAP[] instruction.
178    ///
179    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#swap-the-top-two-elements-on-the-stack>
180    pub fn swap(&mut self) -> Result<(), HintErrorKind> {
181        let a = self.pop()?;
182        let b = self.pop()?;
183        self.push(a)?;
184        self.push(b)
185    }
186
187    /// Copy the indexed element to the top of the stack.
188    ///
189    /// Implements the CINDEX[] instruction.
190    ///
191    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#copy-the-indexed-element-to-the-top-of-the-stack>
192    pub fn copy_index(&mut self) -> Result<(), HintErrorKind> {
193        let top_ix = self.len.checked_sub(1).ok_or(ValueStackUnderflow)?;
194        let index = *self.values.get(top_ix).ok_or(ValueStackUnderflow)? as usize;
195        let element_ix = top_ix.checked_sub(index).ok_or(ValueStackUnderflow)?;
196        self.values[top_ix] = self.values[element_ix];
197        Ok(())
198    }
199
200    /// Moves the indexed element to the top of the stack.
201    ///
202    /// Implements the MINDEX[] instruction.
203    ///
204    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#move-the-indexed-element-to-the-top-of-the-stack>
205    pub fn move_index(&mut self) -> Result<(), HintErrorKind> {
206        let top_ix = self.len.checked_sub(1).ok_or(ValueStackUnderflow)?;
207        let index = *self.values.get(top_ix).ok_or(ValueStackUnderflow)? as usize;
208        let element_ix = top_ix.checked_sub(index).ok_or(ValueStackUnderflow)?;
209        let new_top_ix = top_ix.checked_sub(1).ok_or(ValueStackUnderflow)?;
210        let value = self.values[element_ix];
211        self.values
212            .copy_within(element_ix + 1..self.len, element_ix);
213        self.values[new_top_ix] = value;
214        self.len -= 1;
215        Ok(())
216    }
217
218    /// Roll the top three stack elements.
219    ///
220    /// Implements the ROLL[] instruction.
221    ///
222    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/tt_instructions#roll-the-top-three-stack-elements>
223    pub fn roll(&mut self) -> Result<(), HintErrorKind> {
224        let a = self.pop()?;
225        let b = self.pop()?;
226        let c = self.pop()?;
227        self.push(b)?;
228        self.push(a)?;
229        self.push(c)?;
230        Ok(())
231    }
232}
233
234#[cfg(test)]
235mod tests {
236    use super::{HintErrorKind, ValueStack};
237    use read_fonts::tables::glyf::bytecode::MockInlineOperands;
238
239    // The following are macros because functions can't return a new ValueStack
240    // with a borrowed parameter.
241    macro_rules! make_stack {
242        ($values:expr) => {
243            ValueStack {
244                values: $values,
245                len: $values.len(),
246                is_pedantic: true,
247            }
248        };
249    }
250    macro_rules! make_empty_stack {
251        ($values:expr) => {
252            ValueStack {
253                values: $values,
254                len: 0,
255                is_pedantic: true,
256            }
257        };
258    }
259
260    #[test]
261    fn push() {
262        let mut stack = make_empty_stack!(&mut [0; 4]);
263        for i in 0..4 {
264            stack.push(i).unwrap();
265            assert_eq!(stack.peek(), Some(i));
266        }
267        assert!(matches!(
268            stack.push(0),
269            Err(HintErrorKind::ValueStackOverflow)
270        ));
271    }
272
273    #[test]
274    fn push_args() {
275        let mut stack = make_empty_stack!(&mut [0; 32]);
276        let values = [-5, 2, 2845, 92, -26, 42, i16::MIN, i16::MAX];
277        let mock_args = MockInlineOperands::from_words(&values);
278        stack.push_inline_operands(&mock_args.operands()).unwrap();
279        let mut popped = vec![];
280        while !stack.is_empty() {
281            popped.push(stack.pop().unwrap());
282        }
283        assert!(values
284            .iter()
285            .rev()
286            .map(|x| *x as i32)
287            .eq(popped.iter().copied()));
288    }
289
290    #[test]
291    fn pop() {
292        let mut stack = make_stack!(&mut [0, 1, 2, 3]);
293        for i in (0..4).rev() {
294            assert_eq!(stack.pop().ok(), Some(i));
295        }
296        assert!(matches!(
297            stack.pop(),
298            Err(HintErrorKind::ValueStackUnderflow)
299        ));
300    }
301
302    #[test]
303    fn dup() {
304        let mut stack = make_stack!(&mut [1, 2, 3, 0]);
305        // pop extra element so we have room for dup
306        stack.pop().unwrap();
307        stack.dup().unwrap();
308        assert_eq!(stack.values(), &[1, 2, 3, 3]);
309    }
310
311    #[test]
312    fn swap() {
313        let mut stack = make_stack!(&mut [1, 2, 3]);
314        stack.swap().unwrap();
315        assert_eq!(stack.values(), &[1, 3, 2]);
316    }
317
318    #[test]
319    fn copy_index() {
320        let mut stack = make_stack!(&mut [4, 10, 2, 1, 3]);
321        stack.copy_index().unwrap();
322        assert_eq!(stack.values(), &[4, 10, 2, 1, 10]);
323    }
324
325    #[test]
326    fn move_index() {
327        let mut stack = make_stack!(&mut [4, 10, 2, 1, 3]);
328        stack.move_index().unwrap();
329        assert_eq!(stack.values(), &[4, 2, 1, 10]);
330    }
331
332    #[test]
333    fn roll() {
334        let mut stack = make_stack!(&mut [1, 2, 3]);
335        stack.roll().unwrap();
336        assert_eq!(stack.values(), &[2, 3, 1]);
337    }
338
339    #[test]
340    fn unnop() {
341        let mut stack = make_stack!(&mut [42]);
342        stack.apply_unary(|a| Ok(-a)).unwrap();
343        assert_eq!(stack.peek(), Some(-42));
344        stack.apply_unary(|a| Ok(!a)).unwrap();
345        assert_eq!(stack.peek(), Some(!-42));
346    }
347
348    #[test]
349    fn binop() {
350        let mut stack = make_empty_stack!(&mut [0; 32]);
351        for value in 1..=5 {
352            stack.push(value).unwrap();
353        }
354        stack.apply_binary(|a, b| Ok(a + b)).unwrap();
355        assert_eq!(stack.peek(), Some(9));
356        stack.apply_binary(|a, b| Ok(a * b)).unwrap();
357        assert_eq!(stack.peek(), Some(27));
358        stack.apply_binary(|a, b| Ok(a - b)).unwrap();
359        assert_eq!(stack.peek(), Some(-25));
360        stack.apply_binary(|a, b| Ok(a / b)).unwrap();
361        assert_eq!(stack.peek(), Some(0));
362    }
363
364    // Subtract with overflow when stack size is 1 and element index is 0
365    // https://oss-fuzz.com/testcase-detail/5765856825507840
366    #[test]
367    fn move_index_avoid_overflow() {
368        let mut stack = make_stack!(&mut [0]);
369        // Don't panic
370        let _ = stack.move_index();
371    }
372
373    #[test]
374    fn pop_count_checked() {
375        let mut stack = make_stack!(&mut [-1, 128, -1, 128]);
376        stack.is_pedantic = true;
377        assert_eq!(stack.pop_count_checked(), Ok(128));
378        // In pedantic mode, return an error for negative values
379        assert!(matches!(
380            stack.pop_count_checked(),
381            Err(HintErrorKind::InvalidStackValue(-1))
382        ));
383        stack.is_pedantic = false;
384        assert_eq!(stack.pop_count_checked(), Ok(128));
385        // In non-pedantic mode, return 0 instead of error
386        assert_eq!(stack.pop_count_checked(), Ok(0));
387    }
388}
skrifa/outline/glyf/hint/value_stack.rs

skrifa/outline/glyf/hint/
value_stack.rs
