1 //! Operand stack for CFF/CFF2 parsing. 2 3 use types::Fixed; 4 5 use 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> 13 const 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. 26 pub struct Stack { 27 values: [i32; MAX_STACK], 28 value_is_fixed: [bool; MAX_STACK], 29 top: usize, 30 } 31 32 impl Stack { new() -> Self33 pub fn new() -> Self { 34 Self { 35 values: [0; MAX_STACK], 36 value_is_fixed: [false; MAX_STACK], 37 top: 0, 38 } 39 } 40 is_empty(&self) -> bool41 pub fn is_empty(&self) -> bool { 42 self.top == 0 43 } 44 len(&self) -> usize45 pub fn len(&self) -> usize { 46 self.top 47 } 48 verify_exact_len(&self, len: usize) -> Result<(), Error>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 verify_at_least_len(&self, len: usize) -> Result<(), Error>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. len_is_odd(&self) -> bool70 pub fn len_is_odd(&self) -> bool { 71 self.top & 1 != 0 72 } 73 clear(&mut self)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. reverse(&mut self)82 pub fn reverse(&mut self) { 83 self.values[..self.top].reverse(); 84 self.value_is_fixed[..self.top].reverse(); 85 } 86 push(&mut self, number: impl Into<Number>) -> Result<(), Error>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. get_i32(&self, index: usize) -> Result<i32, Error>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. get_fixed(&self, index: usize) -> Result<Fixed, Error>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. pop_i32(&mut self) -> Result<i32, Error>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. pop_fixed(&mut self) -> Result<Fixed, Error>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. fixed_values(&self) -> impl Iterator<Item = Fixed> + '_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`. fixed_array<const N: usize>(&self, first_index: usize) -> Result<[Fixed; N], Error>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. number_values(&self) -> impl Iterator<Item = Number> + '_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 /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/cff2#table-6-operand-types> apply_delta_prefix_sum(&mut self)208 pub fn apply_delta_prefix_sum(&mut self) { 209 if self.top > 1 { 210 let mut sum = Fixed::ZERO; 211 for (value, is_fixed) in self.values[..self.top] 212 .iter_mut() 213 .zip(&mut self.value_is_fixed) 214 { 215 sum += if *is_fixed { 216 // FreeType reads delta values using cff_parse_num which 217 // which truncates the fractional parts of 16.16 values 218 // See delta parsing: 219 // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/cff/cffparse.c#L1427> 220 // See cff_parse_num "binary-coded decimal is truncated to 221 // integer": 222 // <https://gitlab.freedesktop.org/freetype/freetype/-/blob/80a507a6b8e3d2906ad2c8ba69329bd2fb2a85ef/src/cff/cffparse.c#L463> 223 Fixed::from_bits(*value).floor() 224 } else { 225 Fixed::from_i32(*value) 226 }; 227 *value = sum.to_bits(); 228 *is_fixed = true; 229 } 230 } 231 } 232 233 /// Apply the `blend` operator. 234 /// 235 /// See <https://learn.microsoft.com/en-us/typography/opentype/spec/cff2charstr#syntax-for-font-variations-support-operators> 236 #[inline(never)] apply_blend(&mut self, blend_state: &BlendState) -> Result<(), Error>237 pub fn apply_blend(&mut self, blend_state: &BlendState) -> Result<(), Error> { 238 // When the blend operator is invoked, the stack will contain a set 239 // of target values, followed by sets of deltas for those values for 240 // each variation region, followed by the count of target values. 241 // 242 // For example, if we're blending two target values across three 243 // variation regions, the stack would be setup as follows (parentheses 244 // added to signify grouping of deltas): 245 // 246 // value_0 value_1 (delta_0_0 delta_0_1 delta_0_2) (delta_1_0 delta_1_1 delta_1_2) 2 247 // 248 // where delta_i_j represents the delta for value i and region j. 249 // 250 // We compute the scalars for each region, multiply them by the 251 // associated deltas and add the result to the respective target value. 252 // Then the stack is popped so only the final target values remain. 253 let target_value_count = self.pop_i32()? as usize; 254 if target_value_count > self.top { 255 return Err(Error::StackUnderflow); 256 } 257 let region_count = blend_state.region_count()?; 258 // We expect at least `target_value_count * (region_count + 1)` 259 // elements on the stack. 260 let operand_count = target_value_count * (region_count + 1); 261 if self.len() < operand_count { 262 return Err(Error::StackUnderflow); 263 } 264 // The stack may contain more elements than necessary, so keep track of 265 // our active range. 266 let start = self.len() - operand_count; 267 let end = start + operand_count; 268 // For simplicity, convert all elements to fixed up front. 269 for (value, is_fixed) in self.values[start..end] 270 .iter_mut() 271 .zip(&mut self.value_is_fixed[start..]) 272 { 273 if !*is_fixed { 274 *value = Fixed::from_i32(*value).to_bits(); 275 *is_fixed = true; 276 } 277 } 278 let (values, deltas) = self.values[start..].split_at_mut(target_value_count); 279 // Note: we specifically loop over scalars in the outer loop to avoid 280 // computing them more than once in the case that we overflow our 281 // precomputed cache. 282 for (region_ix, maybe_scalar) in blend_state.scalars()?.enumerate() { 283 let scalar = maybe_scalar?; 284 // We could omit these in `BlendState::scalars()` but that would 285 // significantly reduce the clarity of the already complex 286 // chained iterator code there. Do the simple thing here instead. 287 if scalar == Fixed::ZERO { 288 continue; 289 } 290 for (value_ix, value) in values.iter_mut().enumerate() { 291 let delta_ix = (region_count * value_ix) + region_ix; 292 let delta = Fixed::from_bits(deltas[delta_ix]); 293 *value = (Fixed::from_bits(*value).wrapping_add(delta * scalar)).to_bits(); 294 } 295 } 296 self.top = start + target_value_count; 297 Ok(()) 298 } 299 push_impl(&mut self, value: i32, is_fixed: bool) -> Result<(), Error>300 fn push_impl(&mut self, value: i32, is_fixed: bool) -> Result<(), Error> { 301 if self.top == MAX_STACK { 302 return Err(Error::StackOverflow); 303 } 304 self.values[self.top] = value; 305 self.value_is_fixed[self.top] = is_fixed; 306 self.top += 1; 307 Ok(()) 308 } 309 pop(&mut self) -> Result<usize, Error>310 fn pop(&mut self) -> Result<usize, Error> { 311 if self.top > 0 { 312 self.top -= 1; 313 Ok(self.top) 314 } else { 315 Err(Error::StackUnderflow) 316 } 317 } 318 } 319 320 impl Default for Stack { default() -> Self321 fn default() -> Self { 322 Self::new() 323 } 324 } 325 326 /// Either a signed 32-bit integer or a 16.16 fixed point number. 327 /// 328 /// This represents the CFF "number" operand type. 329 /// See "Table 6 Operand Types" at <https://adobe-type-tools.github.io/font-tech-notes/pdfs/5176.CFF.pdf> 330 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Debug)] 331 pub enum Number { 332 I32(i32), 333 Fixed(Fixed), 334 } 335 336 impl Number { from_stack(raw: i32, is_fixed: bool) -> Self337 fn from_stack(raw: i32, is_fixed: bool) -> Self { 338 if is_fixed { 339 Self::Fixed(Fixed::from_bits(raw)) 340 } else { 341 Self::I32(raw) 342 } 343 } 344 } 345 346 impl From<i32> for Number { from(value: i32) -> Self347 fn from(value: i32) -> Self { 348 Self::I32(value) 349 } 350 } 351 352 impl From<Fixed> for Number { from(value: Fixed) -> Self353 fn from(value: Fixed) -> Self { 354 Self::Fixed(value) 355 } 356 } 357 358 impl std::fmt::Display for Number { fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result359 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { 360 match self { 361 Self::I32(value) => value.fmt(f), 362 Self::Fixed(value) => value.fmt(f), 363 } 364 } 365 } 366 367 #[cfg(test)] 368 mod tests { 369 use types::{F2Dot14, Fixed}; 370 371 use super::Stack; 372 use crate::{ 373 tables::{postscript::BlendState, variations::ItemVariationStore}, 374 FontData, FontRead, 375 }; 376 377 #[test] push_pop()378 fn push_pop() { 379 let mut stack = Stack::new(); 380 stack.push(20).unwrap(); 381 stack.push(Fixed::from_f64(42.42)).unwrap(); 382 assert!(!stack.len_is_odd()); 383 stack.verify_exact_len(2).unwrap(); 384 stack.verify_at_least_len(2).unwrap(); 385 assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(42.42)); 386 assert_eq!(stack.pop_i32().unwrap(), 20); 387 } 388 389 #[test] push_fixed_pop_i32()390 fn push_fixed_pop_i32() { 391 let mut stack = Stack::new(); 392 stack.push(Fixed::from_f64(42.42)).unwrap(); 393 assert!(stack.pop_i32().is_err()); 394 } 395 396 #[test] push_i32_pop_fixed()397 fn push_i32_pop_fixed() { 398 let mut stack = Stack::new(); 399 stack.push(123).unwrap(); 400 assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(123.0)); 401 } 402 403 #[test] reverse()404 fn reverse() { 405 let mut stack = Stack::new(); 406 stack.push(Fixed::from_f64(1.5)).unwrap(); 407 stack.push(42).unwrap(); 408 stack.push(Fixed::from_f64(4.2)).unwrap(); 409 stack.reverse(); 410 assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(1.5)); 411 assert_eq!(stack.pop_i32().unwrap(), 42); 412 assert_eq!(stack.pop_fixed().unwrap(), Fixed::from_f64(4.2)); 413 } 414 415 #[test] delta_prefix_sum()416 fn delta_prefix_sum() { 417 let mut stack = Stack::new(); 418 stack.push(Fixed::from_f64(1.5)).unwrap(); 419 stack.push(42).unwrap(); 420 stack.push(Fixed::from_f64(4.2)).unwrap(); 421 stack.apply_delta_prefix_sum(); 422 assert!(stack.len_is_odd()); 423 let values: Vec<_> = stack.fixed_values().collect(); 424 let expected = &[ 425 Fixed::from_f64(1.0), 426 Fixed::from_f64(43.0), 427 Fixed::from_f64(47.0), 428 ]; 429 assert_eq!(&values, expected); 430 } 431 432 #[test] blend()433 fn blend() { 434 let ivs_data = &font_test_data::cff2::EXAMPLE[18..]; 435 let ivs = ItemVariationStore::read(FontData::new(ivs_data)).unwrap(); 436 // This coordinate will generate scalars [0.5, 0.5] 437 let coords = &[F2Dot14::from_f32(-0.75)]; 438 let blend_state = BlendState::new(ivs, coords, 0).unwrap(); 439 let mut stack = Stack::new(); 440 // Push our target values 441 stack.push(10).unwrap(); 442 stack.push(20).unwrap(); 443 // Push deltas for 2 regions for the first value 444 stack.push(4).unwrap(); 445 stack.push(-8).unwrap(); 446 // Push deltas for 2 regions for the second value 447 stack.push(-60).unwrap(); 448 stack.push(2).unwrap(); 449 // Push target value count 450 stack.push(2).unwrap(); 451 stack.apply_blend(&blend_state).unwrap(); 452 let result: Vec<_> = stack.fixed_values().collect(); 453 // Expected values: 454 // 0: 10 + (4 * 0.5) + (-8 * 0.5) = 8 455 // 1: 20 + (-60 * 0.5) + (2 * 0.5) = -9 456 let expected = &[Fixed::from_f64(8.0), Fixed::from_f64(-9.0)]; 457 assert_eq!(&result, expected); 458 } 459 } 460