Skip to main content

read_fonts/ps/cff/
stack.rs

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