read_fonts/ps/cff/
stack.rs

1//! Operand stack for CFF/CFF2 parsing.
2
3use super::{super::error::Error, blend::BlendState};
4use types::Fixed;
5
6/// Maximum size of the operand stack.
7///
8/// "Operators in Top DICT, Font DICTs, Private DICTs and CharStrings may be
9/// preceded by up to a maximum of 513 operands."
10///
11/// <https://learn.microsoft.com/en-us/typography/opentype/spec/cff2#table-9-top-dict-operator-entries>
12const MAX_STACK: usize = 513;
13
14/// Operand stack for DICTs and charstrings.
15///
16/// The operand stack can contain either 32-bit integers or 16.16 fixed point
17/// values. The type is known when pushing to the stack and the expected type
18/// is also known (based on the operator) when reading from the stack, so the
19/// conversion is performed on demand at read time.
20///
21/// Storing the entries as an enum would require 8 bytes each and since these
22/// objects are created on the _stack_, we reduce the required size by storing
23/// the entries in parallel arrays holding the raw 32-bit value and a flag that
24/// tracks which values are fixed point.
25pub struct Stack {
26    values: [i32; MAX_STACK],
27    value_is_fixed: [bool; MAX_STACK],
28    top: usize,
29}
30
31impl Stack {
32    pub fn new() -> Self {
33        Self {
34            values: [0; MAX_STACK],
35            value_is_fixed: [false; MAX_STACK],
36            top: 0,
37        }
38    }
39
40    pub fn is_empty(&self) -> bool {
41        self.top == 0
42    }
43
44    pub fn len(&self) -> usize {
45        self.top
46    }
47
48    pub fn verify_exact_len(&self, len: usize) -> Result<(), Error> {
49        if self.top != len {
50            Err(Error::StackUnderflow)
51        } else {
52            Ok(())
53        }
54    }
55
56    pub fn verify_at_least_len(&self, len: usize) -> Result<(), Error> {
57        if self.top < len {
58            Err(Error::StackUnderflow)
59        } else {
60            Ok(())
61        }
62    }
63
64    /// Returns true if the number of elements on the stack is odd.
65    ///
66    /// Used for processing some charstring operators where an odd
67    /// count represents the presence of the glyph advance width at the
68    /// bottom of the stack.
69    pub fn len_is_odd(&self) -> bool {
70        self.top & 1 != 0
71    }
72
73    pub fn clear(&mut self) {
74        self.top = 0;
75    }
76
77    /// Reverse the order of all elements on the stack.
78    ///
79    /// Some charstring operators are simpler to process on a reversed
80    /// stack.
81    pub fn reverse(&mut self) {
82        self.values[..self.top].reverse();
83        self.value_is_fixed[..self.top].reverse();
84    }
85
86    /// Swaps the top two elements.
87    pub(crate) fn exch(&mut self) -> Result<(), Error> {
88        if self.top < 2 {
89            return Err(Error::StackUnderflow);
90        }
91        let a = self.top - 1;
92        let b = a - 1;
93        self.values.swap(a, b);
94        self.value_is_fixed.swap(a, b);
95        Ok(())
96    }
97
98    pub fn push(&mut self, number: impl Into<Number>) -> Result<(), Error> {
99        match number.into() {
100            Number::I32(value) => self.push_impl(value, false),
101            Number::Fixed(value) => self.push_impl(value.to_bits(), true),
102        }
103    }
104
105    /// Sets the element at `index` to the given `number`.
106    pub fn set(&mut self, index: usize, number: impl Into<Number>) -> Result<(), Error> {
107        if index >= self.top {
108            return Err(Error::StackOverflow);
109        }
110        match number.into() {
111            Number::I32(value) => {
112                self.value_is_fixed[index] = false;
113                self.values[index] = value;
114            }
115            Number::Fixed(value) => {
116                self.value_is_fixed[index] = true;
117                self.values[index] = value.to_bits();
118            }
119        }
120        Ok(())
121    }
122
123    /// Drops `n` elements from the top of the stack.
124    ///
125    /// If `n` is greater than the length of the stack, this simply acts as
126    /// a clear operation.
127    pub fn drop(&mut self, n: usize) {
128        self.top = self.top.saturating_sub(n);
129    }
130
131    /// Returns the 32-bit integer at the given index on the stack.
132    ///
133    /// Will return an error if the value at that index was not pushed as an
134    /// integer.
135    pub fn get_i32(&self, index: usize) -> Result<i32, Error> {
136        // FreeType just returns 0 for OOB access
137        // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psaux/psstack.c#L143>
138        let Some(value) = self.values.get(index).copied() else {
139            return Ok(0);
140        };
141        if self.value_is_fixed[index] {
142            // FreeType returns an error here rather than converting
143            // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psaux/psstack.c#L145>
144            Err(Error::ExpectedI32StackEntry(index))
145        } else {
146            Ok(value)
147        }
148    }
149
150    /// Returns the 16.16 fixed point value at the given index on the stack.
151    ///
152    /// If the value was pushed as an integer, it will be automatically
153    /// converted to 16.16 fixed point.
154    pub fn get_fixed(&self, index: usize) -> Result<Fixed, Error> {
155        // FreeType just returns 0 for OOB access
156        // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psaux/psstack.c#L193>
157        let Some(value) = self.values.get(index).copied() else {
158            return Ok(Fixed::ZERO);
159        };
160        Ok(if self.value_is_fixed[index] {
161            Fixed::from_bits(value)
162        } else {
163            Fixed::from_i32(value)
164        })
165    }
166
167    /// Pops a 32-bit integer from the top of stack.
168    ///
169    /// Will return an error if the top value on the stack was not pushed as an
170    /// integer.
171    pub fn pop_i32(&mut self) -> Result<i32, Error> {
172        let i = self.pop()?;
173        self.get_i32(i)
174    }
175
176    /// Pops a 16.16 fixed point value from the top of the stack.
177    ///
178    /// If the value was pushed as an integer, it will be automatically
179    /// converted to 16.16 fixed point.
180    pub fn pop_fixed(&mut self) -> Result<Fixed, Error> {
181        let i = self.pop()?;
182        self.get_fixed(i)
183    }
184
185    /// Returns an iterator yielding all elements on the stack
186    /// as 16.16 fixed point values.
187    ///
188    /// Used to read array style DICT entries such as blue values,
189    /// font matrix and font bounding box.
190    pub fn fixed_values(&self) -> impl Iterator<Item = Fixed> + '_ {
191        self.values[..self.top]
192            .iter()
193            .zip(&self.value_is_fixed)
194            .map(|(value, is_real)| {
195                if *is_real {
196                    Fixed::from_bits(*value)
197                } else {
198                    Fixed::from_i32(*value)
199                }
200            })
201    }
202
203    /// Returns an array of `N` 16.16 fixed point values starting at
204    /// `first_index`.
205    pub fn fixed_array<const N: usize>(&self, first_index: usize) -> Result<[Fixed; N], Error> {
206        let mut result = [Fixed::ZERO; N];
207        let end = first_index + N;
208        // FreeType doesn't have an equivalent to this function but always
209        // returns 0 on failure so we take the maximum valid range and
210        // pad the remainder with zeros
211        let range = first_index.min(self.top)..end.min(self.top);
212        for ((src, is_fixed), dest) in self.values[range.clone()]
213            .iter()
214            .zip(&self.value_is_fixed[range])
215            .zip(&mut result)
216        {
217            let value = if *is_fixed {
218                Fixed::from_bits(*src)
219            } else {
220                Fixed::from_i32(*src)
221            };
222            *dest = value;
223        }
224        Ok(result)
225    }
226
227    /// Returns an iterator yielding all elements on the stack as number
228    /// values.
229    ///
230    /// This is useful for capturing the current state of the stack.
231    pub fn number_values(&self) -> impl Iterator<Item = Number> + '_ {
232        self.values[..self.top]
233            .iter()
234            .zip(&self.value_is_fixed)
235            .map(|(value, is_fixed)| Number::from_stack(*value, *is_fixed))
236    }
237
238    /// Apply a prefix sum to decode delta-encoded numbers.
239    ///
240    /// "The second and subsequent numbers in a delta are encoded as the
241    /// difference between successive values."
242    ///
243    /// Roughly equivalent to the FreeType logic at
244    /// <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/cff/cffparse.c#L1431>
245    ///
246    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/cff2#table-6-operand-types>
247    pub fn apply_delta_prefix_sum(&mut self) {
248        if self.top > 1 {
249            let mut sum = Fixed::ZERO;
250            for (value, is_fixed) in self.values[..self.top]
251                .iter_mut()
252                .zip(&mut self.value_is_fixed)
253            {
254                let fixed_value = if *is_fixed {
255                    Fixed::from_bits(*value)
256                } else {
257                    Fixed::from_i32(*value)
258                };
259                // See <https://github.com/googlefonts/fontations/issues/1193>
260                // The "DIN Alternate" font contains incorrect blue values
261                // that cause an overflow in this computation. FreeType does
262                // not use checked arithmetic so we need to explicitly use
263                // wrapping behavior to produce matching outlines.
264                sum = sum.wrapping_add(fixed_value);
265                *value = sum.to_bits();
266                *is_fixed = true;
267            }
268        }
269    }
270
271    /// Apply the `blend` operator.
272    ///
273    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/cff2charstr#syntax-for-font-variations-support-operators>
274    #[inline(never)]
275    pub fn apply_blend(&mut self, blend_state: &BlendState) -> Result<(), Error> {
276        // When the blend operator is invoked, the stack will contain a set
277        // of target values, followed by sets of deltas for those values for
278        // each variation region, followed by the count of target values.
279        //
280        // For example, if we're blending two target values across three
281        // variation regions, the stack would be setup as follows (parentheses
282        // added to signify grouping of deltas):
283        //
284        // value_0 value_1 (delta_0_0 delta_0_1 delta_0_2) (delta_1_0 delta_1_1 delta_1_2) 2
285        //
286        // where delta_i_j represents the delta for value i and region j.
287        //
288        // We compute the scalars for each region, multiply them by the
289        // associated deltas and add the result to the respective target value.
290        // Then the stack is popped so only the final target values remain.
291        let target_value_count = self.pop_i32()? as usize;
292        if target_value_count > self.top {
293            return Err(Error::StackUnderflow);
294        }
295        let region_count = blend_state.region_count()?;
296        // We expect at least `target_value_count * (region_count + 1)`
297        // elements on the stack.
298        let operand_count = target_value_count * (region_count + 1);
299        if self.len() < operand_count {
300            return Err(Error::StackUnderflow);
301        }
302        // The stack may contain more elements than necessary, so keep track of
303        // our active range.
304        let start = self.len() - operand_count;
305        let end = start + operand_count;
306        // For simplicity, convert all elements to fixed up front.
307        for (value, is_fixed) in self.values[start..end]
308            .iter_mut()
309            .zip(&mut self.value_is_fixed[start..])
310        {
311            if !*is_fixed {
312                *value = Fixed::from_i32(*value).to_bits();
313                *is_fixed = true;
314            }
315        }
316        let (values, deltas) = self.values[start..].split_at_mut(target_value_count);
317        // Note: we specifically loop over scalars in the outer loop to avoid
318        // computing them more than once in the case that we overflow our
319        // precomputed cache.
320        for (region_ix, maybe_scalar) in blend_state.scalars()?.enumerate() {
321            let scalar = maybe_scalar?;
322            // We could omit these in `BlendState::scalars()` but that would
323            // significantly reduce the clarity of the already complex
324            // chained iterator code there. Do the simple thing here instead.
325            if scalar == Fixed::ZERO {
326                continue;
327            }
328            for (value_ix, value) in values.iter_mut().enumerate() {
329                let delta_ix = (region_count * value_ix) + region_ix;
330                let delta = Fixed::from_bits(deltas[delta_ix]);
331                *value = (Fixed::from_bits(*value).wrapping_add(delta * scalar)).to_bits();
332            }
333        }
334        self.top = start + target_value_count;
335        Ok(())
336    }
337
338    /// Pops the top two elements from the stack and pushes the quotient.
339    ///
340    /// Implements special behavior for Type1 fonts to handle the case of
341    /// integers greater than 32k per FreeType.
342    pub(crate) fn div(&mut self, is_type1: bool) -> Result<(), Error> {
343        let b_idx = self.pop()?;
344        let a_idx = self.pop()?;
345        let (a, b) = if self.value_is_fixed[a_idx] {
346            (self.get_fixed(a_idx)?, self.get_fixed(b_idx)?)
347        } else {
348            // In type1 fonts, we can end up with an integer greater than
349            // 32k. In this case, FT just reinterprets both as fixed point
350            // and divides: <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psaux/psintrp.c#L1594>
351            let a = self.get_i32(a_idx)?;
352            if is_type1 && !(-32000..=32000).contains(&a) {
353                (Fixed::from_bits(a), Fixed::from_bits(self.get_i32(b_idx)?))
354            } else {
355                (self.get_fixed(a_idx)?, self.get_fixed(b_idx)?)
356            }
357        };
358        self.push(a / b)
359    }
360
361    fn push_impl(&mut self, value: i32, is_fixed: bool) -> Result<(), Error> {
362        if self.top == MAX_STACK {
363            return Err(Error::StackOverflow);
364        }
365        self.values[self.top] = value;
366        self.value_is_fixed[self.top] = is_fixed;
367        self.top += 1;
368        Ok(())
369    }
370
371    fn pop(&mut self) -> Result<usize, Error> {
372        if self.top > 0 {
373            self.top -= 1;
374            Ok(self.top)
375        } else {
376            Ok(0)
377        }
378    }
379}
380
381impl Default for Stack {
382    fn default() -> Self {
383        Self::new()
384    }
385}
386
387/// Either a signed 32-bit integer or a 16.16 fixed point number.
388///
389/// This represents the CFF "number" operand type.
390/// See "Table 6 Operand Types" at <https://adobe-type-tools.github.io/font-tech-notes/pdfs/5176.CFF.pdf>
391#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
392pub enum Number {
393    I32(i32),
394    Fixed(Fixed),
395}
396
397impl Number {
398    fn from_stack(raw: i32, is_fixed: bool) -> Self {
399        if is_fixed {
400            Self::Fixed(Fixed::from_bits(raw))
401        } else {
402            Self::I32(raw)
403        }
404    }
405}
406
407impl From<i32> for Number {
408    fn from(value: i32) -> Self {
409        Self::I32(value)
410    }
411}
412
413impl From<Fixed> for Number {
414    fn from(value: Fixed) -> Self {
415        Self::Fixed(value)
416    }
417}
418
419impl std::fmt::Display for Number {
420    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
421        match self {
422            Self::I32(value) => value.fmt(f),
423            Self::Fixed(value) => value.fmt(f),
424        }
425    }
426}
427
428#[cfg(test)]
429mod tests {
430    use super::*;
431    use crate::{tables::variations::ItemVariationStore, FontData, FontRead};
432    use types::{F2Dot14, Fixed};
433
434    #[test]
435    fn push_pop() {
436        let mut stack = Stack::new();
437        stack.push(20).unwrap();
438        stack.push(Fixed::from_f64(42.42)).unwrap();
439        assert!(!stack.len_is_odd());
440        stack.verify_exact_len(2).unwrap();
441        stack.verify_at_least_len(2).unwrap();
442        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(42.42));
443        assert_eq!(stack.pop_i32().unwrap(), 20);
444    }
445
446    #[test]
447    fn push_fixed_pop_i32() {
448        let mut stack = Stack::new();
449        stack.push(Fixed::from_f64(42.42)).unwrap();
450        assert!(stack.pop_i32().is_err());
451    }
452
453    #[test]
454    fn push_i32_pop_fixed() {
455        let mut stack = Stack::new();
456        stack.push(123).unwrap();
457        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(123.0));
458    }
459
460    #[test]
461    fn reverse() {
462        let mut stack = Stack::new();
463        stack.push(Fixed::from_f64(1.5)).unwrap();
464        stack.push(42).unwrap();
465        stack.push(Fixed::from_f64(4.2)).unwrap();
466        stack.reverse();
467        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(1.5));
468        assert_eq!(stack.pop_i32().unwrap(), 42);
469        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(4.2));
470    }
471
472    #[test]
473    fn delta_prefix_sum() {
474        let mut stack = Stack::new();
475        stack.push(Fixed::from_f64(1.5)).unwrap();
476        stack.push(42).unwrap();
477        stack.push(Fixed::from_f64(4.2)).unwrap();
478        stack.apply_delta_prefix_sum();
479        assert!(stack.len_is_odd());
480        let values: Vec<_> = stack.fixed_values().collect();
481        let expected = &[
482            Fixed::from_f64(1.5),
483            Fixed::from_f64(43.5),
484            Fixed::from_f64(47.69999694824219),
485        ];
486        assert_eq!(&values, expected);
487    }
488
489    #[test]
490    fn blend() {
491        let ivs_data = &font_test_data::cff2::EXAMPLE[18..];
492        let ivs = ItemVariationStore::read(FontData::new(ivs_data)).unwrap();
493        // This coordinate will generate scalars [0.5, 0.5]
494        let coords = &[F2Dot14::from_f32(-0.75)];
495        let blend_state = BlendState::new(ivs, coords, 0).unwrap();
496        let mut stack = Stack::new();
497        // Push our target values
498        stack.push(10).unwrap();
499        stack.push(20).unwrap();
500        // Push deltas for 2 regions for the first value
501        stack.push(4).unwrap();
502        stack.push(-8).unwrap();
503        // Push deltas for 2 regions for the second value
504        stack.push(-60).unwrap();
505        stack.push(2).unwrap();
506        // Push target value count
507        stack.push(2).unwrap();
508        stack.apply_blend(&blend_state).unwrap();
509        let result: Vec<_> = stack.fixed_values().collect();
510        // Expected values:
511        // 0: 10 + (4 * 0.5) + (-8 * 0.5) = 8
512        // 1: 20 + (-60 * 0.5) + (2 * 0.5) = -9
513        let expected = &[Fixed::from_f64(8.0), Fixed::from_f64(-9.0)];
514        assert_eq!(&result, expected);
515    }
516
517    #[test]
518    fn invalid_access_yields_zero() {
519        let mut stack = Stack::new();
520        assert_eq!(stack.pop_i32().unwrap(), 0);
521        assert_eq!(stack.pop_fixed().unwrap(), Fixed::ZERO);
522        assert_eq!(stack.get_i32(10).unwrap(), 0);
523        assert_eq!(stack.get_fixed(10).unwrap(), Fixed::ZERO);
524        // In this case, we get the first valid value followed by the
525        // remainder of the requested array size padded with zeros
526        stack.push(5).unwrap();
527        assert_eq!(
528            stack.fixed_array::<3>(0).unwrap(),
529            [Fixed::from_i32(5), Fixed::ZERO, Fixed::ZERO]
530        );
531    }
532
533    #[test]
534    fn exch() {
535        let mut stack = Stack::new();
536        stack.push(4).unwrap();
537        stack.push(Fixed::from_f64(2.5)).unwrap();
538        stack.exch().unwrap();
539        assert_eq!(stack.pop_i32().unwrap(), 4);
540        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(2.5));
541        // Error when we don't have at least two elements
542        stack.clear();
543        stack.push(1).unwrap();
544        assert!(stack.exch().is_err());
545    }
546
547    #[test]
548    fn div() {
549        let mut stack = Stack::new();
550        // Simple division
551        stack.push(200).unwrap();
552        stack.push(50).unwrap();
553        stack.div(false).unwrap();
554        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_i32(4));
555        stack.push(Fixed::from_f64(151.0)).unwrap();
556        stack.push(2).unwrap();
557        stack.div(false).unwrap();
558        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(75.5));
559        // Handle large numbers (magnitude greater than 32k)
560        stack.push(40000).unwrap();
561        stack.push(20).unwrap();
562        stack.div(true).unwrap();
563        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_i32(2000));
564        stack.push(-40000).unwrap();
565        stack.push(20).unwrap();
566        stack.div(true).unwrap();
567        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_i32(-2000));
568    }
569
570    #[test]
571    fn set() {
572        let mut stack = Stack::new();
573        stack.push(0).unwrap();
574        stack.push(0).unwrap();
575        stack.push(0).unwrap();
576        stack.set(0, Fixed::from_f64(-4.2)).unwrap();
577        stack.set(2, 25).unwrap();
578        assert_eq!(
579            stack.fixed_array(0).unwrap(),
580            [Fixed::from_f64(-4.2), Fixed::ZERO, Fixed::from_f64(25.0)]
581        );
582    }
583
584    #[test]
585    fn drop() {
586        let mut stack = Stack::new();
587        for _ in 0..20 {
588            stack.push(0).unwrap();
589        }
590        assert_eq!(stack.len(), 20);
591        stack.drop(4);
592        assert_eq!(stack.len(), 16);
593        stack.drop(10);
594        assert_eq!(stack.len(), 6);
595        // Only 6 left, but be lenient because processing fonts is often
596        // best effort
597        stack.drop(7);
598        assert_eq!(stack.len(), 0);
599    }
600}
read_fonts/ps/cff/stack.rs

read_fonts/ps/cff/
stack.rs
