read_fonts/tables/postscript/
stack.rs

1//! Operand stack for CFF/CFF2 parsing.
2
3use types::Fixed;
4
5use super::{BlendState, Error};
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    pub fn verify_exact_len(&self, len: usize) -> Result<(), Error> {
50        if self.top != len {
51            Err(Error::StackUnderflow)
52        } else {
53            Ok(())
54        }
55    }
56
57    pub fn verify_at_least_len(&self, len: usize) -> Result<(), Error> {
58        if self.top < len {
59            Err(Error::StackUnderflow)
60        } else {
61            Ok(())
62        }
63    }
64
65    /// Returns true if the number of elements on the stack is odd.
66    ///
67    /// Used for processing some charstring operators where an odd
68    /// count represents the presence of the glyph advance width at the
69    /// bottom of the stack.
70    pub fn len_is_odd(&self) -> bool {
71        self.top & 1 != 0
72    }
73
74    pub fn clear(&mut self) {
75        self.top = 0;
76    }
77
78    /// Reverse the order of all elements on the stack.
79    ///
80    /// Some charstring operators are simpler to process on a reversed
81    /// stack.
82    pub fn reverse(&mut self) {
83        self.values[..self.top].reverse();
84        self.value_is_fixed[..self.top].reverse();
85    }
86
87    pub fn push(&mut self, number: impl Into<Number>) -> Result<(), Error> {
88        match number.into() {
89            Number::I32(value) => self.push_impl(value, false),
90            Number::Fixed(value) => self.push_impl(value.to_bits(), true),
91        }
92    }
93
94    /// Returns the 32-bit integer at the given index on the stack.
95    ///
96    /// Will return an error if the value at that index was not pushed as an
97    /// integer.
98    pub fn get_i32(&self, index: usize) -> Result<i32, Error> {
99        let value = *self
100            .values
101            .get(index)
102            .ok_or(Error::InvalidStackAccess(index))?;
103        if self.value_is_fixed[index] {
104            // FreeType returns an error here rather than converting
105            // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/psaux/psstack.c#L145>
106            Err(Error::ExpectedI32StackEntry(index))
107        } else {
108            Ok(value)
109        }
110    }
111
112    /// Returns the 16.16 fixed point value at the given index on the stack.
113    ///
114    /// If the value was pushed as an integer, it will be automatically
115    /// converted to 16.16 fixed point.
116    pub fn get_fixed(&self, index: usize) -> Result<Fixed, Error> {
117        let value = *self
118            .values
119            .get(index)
120            .ok_or(Error::InvalidStackAccess(index))?;
121        Ok(if self.value_is_fixed[index] {
122            Fixed::from_bits(value)
123        } else {
124            Fixed::from_i32(value)
125        })
126    }
127
128    /// Pops a 32-bit integer from the top of stack.
129    ///
130    /// Will return an error if the top value on the stack was not pushed as an
131    /// integer.
132    pub fn pop_i32(&mut self) -> Result<i32, Error> {
133        let i = self.pop()?;
134        self.get_i32(i)
135    }
136
137    /// Pops a 16.16 fixed point value from the top of the stack.
138    ///
139    /// If the value was pushed as an integer, it will be automatically
140    /// converted to 16.16 fixed point.
141    pub fn pop_fixed(&mut self) -> Result<Fixed, Error> {
142        let i = self.pop()?;
143        self.get_fixed(i)
144    }
145
146    /// Returns an iterator yielding all elements on the stack
147    /// as 16.16 fixed point values.
148    ///
149    /// Used to read array style DICT entries such as blue values,
150    /// font matrix and font bounding box.
151    pub fn fixed_values(&self) -> impl Iterator<Item = Fixed> + '_ {
152        self.values[..self.top]
153            .iter()
154            .zip(&self.value_is_fixed)
155            .map(|(value, is_real)| {
156                if *is_real {
157                    Fixed::from_bits(*value)
158                } else {
159                    Fixed::from_i32(*value)
160                }
161            })
162    }
163
164    /// Returns an array of `N` 16.16 fixed point values starting at
165    /// `first_index`.
166    pub fn fixed_array<const N: usize>(&self, first_index: usize) -> Result<[Fixed; N], Error> {
167        let mut result = [Fixed::ZERO; N];
168        if first_index >= self.top {
169            return Err(Error::InvalidStackAccess(first_index));
170        }
171        let end = first_index + N;
172        if end > self.top {
173            return Err(Error::InvalidStackAccess(end - 1));
174        }
175        let range = first_index..end;
176        for ((src, is_fixed), dest) in self.values[range.clone()]
177            .iter()
178            .zip(&self.value_is_fixed[range])
179            .zip(&mut result)
180        {
181            let value = if *is_fixed {
182                Fixed::from_bits(*src)
183            } else {
184                Fixed::from_i32(*src)
185            };
186            *dest = value;
187        }
188        Ok(result)
189    }
190
191    /// Returns an iterator yielding all elements on the stack as number
192    /// values.
193    ///
194    /// This is useful for capturing the current state of the stack.
195    pub fn number_values(&self) -> impl Iterator<Item = Number> + '_ {
196        self.values[..self.top]
197            .iter()
198            .zip(&self.value_is_fixed)
199            .map(|(value, is_fixed)| Number::from_stack(*value, *is_fixed))
200    }
201
202    /// Apply a prefix sum to decode delta-encoded numbers.
203    ///
204    /// "The second and subsequent numbers in a delta are encoded as the
205    /// difference between successive values."
206    ///
207    /// Roughly equivalent to the FreeType logic at
208    /// <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/cff/cffparse.c#L1431>
209    ///
210    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/cff2#table-6-operand-types>
211    pub fn apply_delta_prefix_sum(&mut self) {
212        if self.top > 1 {
213            let mut sum = Fixed::ZERO;
214            for (value, is_fixed) in self.values[..self.top]
215                .iter_mut()
216                .zip(&mut self.value_is_fixed)
217            {
218                let fixed_value = if *is_fixed {
219                    Fixed::from_bits(*value)
220                } else {
221                    Fixed::from_i32(*value)
222                };
223                // See <https://github.com/googlefonts/fontations/issues/1193>
224                // The "DIN Alternate" font contains incorrect blue values
225                // that cause an overflow in this computation. FreeType does
226                // not use checked arithmetic so we need to explicitly use
227                // wrapping behavior to produce matching outlines.
228                sum = sum.wrapping_add(fixed_value);
229                *value = sum.to_bits();
230                *is_fixed = true;
231            }
232        }
233    }
234
235    /// Apply the `blend` operator.
236    ///
237    /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/cff2charstr#syntax-for-font-variations-support-operators>
238    #[inline(never)]
239    pub fn apply_blend(&mut self, blend_state: &BlendState) -> Result<(), Error> {
240        // When the blend operator is invoked, the stack will contain a set
241        // of target values, followed by sets of deltas for those values for
242        // each variation region, followed by the count of target values.
243        //
244        // For example, if we're blending two target values across three
245        // variation regions, the stack would be setup as follows (parentheses
246        // added to signify grouping of deltas):
247        //
248        // value_0 value_1 (delta_0_0 delta_0_1 delta_0_2) (delta_1_0 delta_1_1 delta_1_2) 2
249        //
250        // where delta_i_j represents the delta for value i and region j.
251        //
252        // We compute the scalars for each region, multiply them by the
253        // associated deltas and add the result to the respective target value.
254        // Then the stack is popped so only the final target values remain.
255        let target_value_count = self.pop_i32()? as usize;
256        if target_value_count > self.top {
257            return Err(Error::StackUnderflow);
258        }
259        let region_count = blend_state.region_count()?;
260        // We expect at least `target_value_count * (region_count + 1)`
261        // elements on the stack.
262        let operand_count = target_value_count * (region_count + 1);
263        if self.len() < operand_count {
264            return Err(Error::StackUnderflow);
265        }
266        // The stack may contain more elements than necessary, so keep track of
267        // our active range.
268        let start = self.len() - operand_count;
269        let end = start + operand_count;
270        // For simplicity, convert all elements to fixed up front.
271        for (value, is_fixed) in self.values[start..end]
272            .iter_mut()
273            .zip(&mut self.value_is_fixed[start..])
274        {
275            if !*is_fixed {
276                *value = Fixed::from_i32(*value).to_bits();
277                *is_fixed = true;
278            }
279        }
280        let (values, deltas) = self.values[start..].split_at_mut(target_value_count);
281        // Note: we specifically loop over scalars in the outer loop to avoid
282        // computing them more than once in the case that we overflow our
283        // precomputed cache.
284        for (region_ix, maybe_scalar) in blend_state.scalars()?.enumerate() {
285            let scalar = maybe_scalar?;
286            // We could omit these in `BlendState::scalars()` but that would
287            // significantly reduce the clarity of the already complex
288            // chained iterator code there. Do the simple thing here instead.
289            if scalar == Fixed::ZERO {
290                continue;
291            }
292            for (value_ix, value) in values.iter_mut().enumerate() {
293                let delta_ix = (region_count * value_ix) + region_ix;
294                let delta = Fixed::from_bits(deltas[delta_ix]);
295                *value = (Fixed::from_bits(*value).wrapping_add(delta * scalar)).to_bits();
296            }
297        }
298        self.top = start + target_value_count;
299        Ok(())
300    }
301
302    fn push_impl(&mut self, value: i32, is_fixed: bool) -> Result<(), Error> {
303        if self.top == MAX_STACK {
304            return Err(Error::StackOverflow);
305        }
306        self.values[self.top] = value;
307        self.value_is_fixed[self.top] = is_fixed;
308        self.top += 1;
309        Ok(())
310    }
311
312    fn pop(&mut self) -> Result<usize, Error> {
313        if self.top > 0 {
314            self.top -= 1;
315            Ok(self.top)
316        } else {
317            Err(Error::StackUnderflow)
318        }
319    }
320}
321
322impl Default for Stack {
323    fn default() -> Self {
324        Self::new()
325    }
326}
327
328/// Either a signed 32-bit integer or a 16.16 fixed point number.
329///
330/// This represents the CFF "number" operand type.
331/// See "Table 6 Operand Types" at <https://adobe-type-tools.github.io/font-tech-notes/pdfs/5176.CFF.pdf>
332#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
333pub enum Number {
334    I32(i32),
335    Fixed(Fixed),
336}
337
338impl Number {
339    fn from_stack(raw: i32, is_fixed: bool) -> Self {
340        if is_fixed {
341            Self::Fixed(Fixed::from_bits(raw))
342        } else {
343            Self::I32(raw)
344        }
345    }
346}
347
348impl From<i32> for Number {
349    fn from(value: i32) -> Self {
350        Self::I32(value)
351    }
352}
353
354impl From<Fixed> for Number {
355    fn from(value: Fixed) -> Self {
356        Self::Fixed(value)
357    }
358}
359
360impl std::fmt::Display for Number {
361    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
362        match self {
363            Self::I32(value) => value.fmt(f),
364            Self::Fixed(value) => value.fmt(f),
365        }
366    }
367}
368
369#[cfg(test)]
370mod tests {
371    use types::{F2Dot14, Fixed};
372
373    use super::Stack;
374    use crate::{
375        tables::{postscript::BlendState, variations::ItemVariationStore},
376        FontData, FontRead,
377    };
378
379    #[test]
380    fn push_pop() {
381        let mut stack = Stack::new();
382        stack.push(20).unwrap();
383        stack.push(Fixed::from_f64(42.42)).unwrap();
384        assert!(!stack.len_is_odd());
385        stack.verify_exact_len(2).unwrap();
386        stack.verify_at_least_len(2).unwrap();
387        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(42.42));
388        assert_eq!(stack.pop_i32().unwrap(), 20);
389    }
390
391    #[test]
392    fn push_fixed_pop_i32() {
393        let mut stack = Stack::new();
394        stack.push(Fixed::from_f64(42.42)).unwrap();
395        assert!(stack.pop_i32().is_err());
396    }
397
398    #[test]
399    fn push_i32_pop_fixed() {
400        let mut stack = Stack::new();
401        stack.push(123).unwrap();
402        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(123.0));
403    }
404
405    #[test]
406    fn reverse() {
407        let mut stack = Stack::new();
408        stack.push(Fixed::from_f64(1.5)).unwrap();
409        stack.push(42).unwrap();
410        stack.push(Fixed::from_f64(4.2)).unwrap();
411        stack.reverse();
412        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(1.5));
413        assert_eq!(stack.pop_i32().unwrap(), 42);
414        assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(4.2));
415    }
416
417    #[test]
418    fn delta_prefix_sum() {
419        let mut stack = Stack::new();
420        stack.push(Fixed::from_f64(1.5)).unwrap();
421        stack.push(42).unwrap();
422        stack.push(Fixed::from_f64(4.2)).unwrap();
423        stack.apply_delta_prefix_sum();
424        assert!(stack.len_is_odd());
425        let values: Vec<_> = stack.fixed_values().collect();
426        let expected = &[
427            Fixed::from_f64(1.5),
428            Fixed::from_f64(43.5),
429            Fixed::from_f64(47.69999694824219),
430        ];
431        assert_eq!(&values, expected);
432    }
433
434    #[test]
435    fn blend() {
436        let ivs_data = &font_test_data::cff2::EXAMPLE[18..];
437        let ivs = ItemVariationStore::read(FontData::new(ivs_data)).unwrap();
438        // This coordinate will generate scalars [0.5, 0.5]
439        let coords = &[F2Dot14::from_f32(-0.75)];
440        let blend_state = BlendState::new(ivs, coords, 0).unwrap();
441        let mut stack = Stack::new();
442        // Push our target values
443        stack.push(10).unwrap();
444        stack.push(20).unwrap();
445        // Push deltas for 2 regions for the first value
446        stack.push(4).unwrap();
447        stack.push(-8).unwrap();
448        // Push deltas for 2 regions for the second value
449        stack.push(-60).unwrap();
450        stack.push(2).unwrap();
451        // Push target value count
452        stack.push(2).unwrap();
453        stack.apply_blend(&blend_state).unwrap();
454        let result: Vec<_> = stack.fixed_values().collect();
455        // Expected values:
456        // 0: 10 + (4 * 0.5) + (-8 * 0.5) = 8
457        // 1: 20 + (-60 * 0.5) + (2 * 0.5) = -9
458        let expected = &[Fixed::from_f64(8.0), Fixed::from_f64(-9.0)];
459        assert_eq!(&result, expected);
460    }
461}
read_fonts/tables/postscript/stack.rs

read_fonts/tables/postscript/
stack.rs
