skrifa/outline/glyf/hint/
math.rs

1//! Fixed point math helpers that are specific to TrueType hinting.
2//!
3//! These are implemented in terms of font-types types when possible. It
4//! likely makes sense to use more strongly typed fixed point values
5//! in the future.
6
7use read_fonts::types::{Fixed, Point};
8
9pub fn floor(x: i32) -> i32 {
10    x & !63
11}
12
13pub fn round(x: i32) -> i32 {
14    floor(x.wrapping_add(32))
15}
16
17pub fn ceil(x: i32) -> i32 {
18    floor(x.wrapping_add(63))
19}
20
21fn floor_pad(x: i32, n: i32) -> i32 {
22    x & !(n - 1)
23}
24
25pub fn round_pad(x: i32, n: i32) -> i32 {
26    floor_pad(x.wrapping_add(n / 2), n)
27}
28
29#[inline(always)]
30pub fn mul(a: i32, b: i32) -> i32 {
31    (Fixed::from_bits(a) * Fixed::from_bits(b)).to_bits()
32}
33
34pub fn div(a: i32, b: i32) -> i32 {
35    (Fixed::from_bits(a) / Fixed::from_bits(b)).to_bits()
36}
37
38/// Fixed point multiply and divide: a * b / c
39pub fn mul_div(a: i32, b: i32, c: i32) -> i32 {
40    Fixed::from_bits(a)
41        .mul_div(Fixed::from_bits(b), Fixed::from_bits(c))
42        .to_bits()
43}
44
45/// Fixed point multiply and divide without rounding: a * b / c
46///
47/// Based on <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/base/ftcalc.c#L200>
48pub fn mul_div_no_round(a: i32, b: i32, c: i32) -> i32 {
49    let mut sign = 1;
50    let mut au = a as u64;
51    let mut bu = b as u64;
52    let mut cu = c as u64;
53    if a < 0 {
54        au = 0u64.wrapping_sub(au);
55        sign = -1;
56    }
57    if b < 0 {
58        bu = 0u64.wrapping_sub(bu);
59        sign = -sign;
60    }
61    if c < 0 {
62        cu = 0u64.wrapping_sub(cu);
63        sign = -sign;
64    }
65    let result = if cu > 0 {
66        au.wrapping_mul(bu) / cu
67    } else {
68        0x7FFFFFFF
69    };
70    if sign < 0 {
71        (result as i32).wrapping_neg()
72    } else {
73        result as i32
74    }
75}
76
77/// Multiplication for 2.14 fixed point.
78///
79/// Based on <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/truetype/ttinterp.c#L1234>
80pub fn mul14(a: i32, b: i32) -> i32 {
81    let mut v = a as i64 * b as i64;
82    v += 0x2000 + (v >> 63);
83    (v >> 14) as i32
84}
85
86/// Normalize a vector in 2.14 fixed point.
87///
88/// Direct port of <https://gitlab.freedesktop.org/freetype/freetype/-/blob/57617782464411201ce7bbc93b086c1b4d7d84a5/src/base/ftcalc.c#L800>
89pub fn normalize14(x: i32, y: i32) -> Point<i32> {
90    use core::num::Wrapping;
91    let (mut sx, mut sy) = (Wrapping(1i32), Wrapping(1i32));
92    let mut ux = Wrapping(x as u32);
93    let mut uy = Wrapping(y as u32);
94    const ZERO: Wrapping<u32> = Wrapping(0);
95    let mut result = Point::default();
96    if x < 0 {
97        ux = ZERO - ux;
98        sx = -sx;
99    }
100    if y < 0 {
101        uy = ZERO - uy;
102        sy = -sy;
103    }
104    if ux == ZERO {
105        result.x = x / 4;
106        if uy.0 > 0 {
107            result.y = (sy * Wrapping(0x10000) / Wrapping(4)).0;
108        }
109        return result;
110    }
111    if uy == ZERO {
112        result.y = y / 4;
113        if ux.0 > 0 {
114            result.x = (sx * Wrapping(0x10000) / Wrapping(4)).0;
115        }
116        return result;
117    }
118    let mut len = if ux > uy {
119        ux + (uy >> 1)
120    } else {
121        uy + (ux >> 1)
122    };
123    let mut shift = Wrapping(len.0.leading_zeros() as i32);
124    shift -= Wrapping(15)
125        + if len >= (Wrapping(0xAAAAAAAAu32) >> shift.0 as usize) {
126            Wrapping(1)
127        } else {
128            Wrapping(0)
129        };
130    if shift.0 > 0 {
131        let s = shift.0 as usize;
132        ux <<= s;
133        uy <<= s;
134        len = if ux > uy {
135            ux + (uy >> 1)
136        } else {
137            uy + (ux >> 1)
138        };
139    } else {
140        let s = -shift.0 as usize;
141        ux >>= s;
142        uy >>= s;
143        len >>= s;
144    }
145    let mut b = Wrapping(0x10000) - Wrapping(len.0 as i32);
146    let x = Wrapping(ux.0 as i32);
147    let y = Wrapping(uy.0 as i32);
148    let mut z;
149    let mut u;
150    let mut v;
151    loop {
152        u = Wrapping((x + ((x * b) >> 16)).0 as u32);
153        v = Wrapping((y + ((y * b) >> 16)).0 as u32);
154        z = Wrapping(-((u * u + v * v).0 as i32)) / Wrapping(0x200);
155        z = z * ((Wrapping(0x10000) + b) >> 8) / Wrapping(0x10000);
156        b += z;
157        if z <= Wrapping(0) {
158            break;
159        }
160    }
161    Point::new(
162        (Wrapping(u.0 as i32) * sx / Wrapping(4)).0,
163        (Wrapping(v.0 as i32) * sy / Wrapping(4)).0,
164    )
165}
166
167#[cfg(test)]
168mod tests {
169    use raw::types::{F2Dot14, Fixed};
170
171    /// Tolerance value for floating point sanity checks.
172    /// Tests with large sets of values show this is the best we can
173    /// expect from the fixed point implementations.
174    const FLOAT_TOLERANCE: f32 = 1e-4;
175
176    #[test]
177    fn mul_div_no_round() {
178        let cases = [
179            // computed with FT_MulDiv_NoRound():
180            // ((a, b, c), result) where result = a * b / c
181            ((-326, -11474, 9942), 376),
182            ((-6781, 13948, 11973), -7899),
183            ((3517, 15622, 8075), 6804),
184            ((-6127, 15026, 2276), -40450),
185            ((11257, 14828, 2542), 65664),
186            ((-12797, -16280, -9086), -22929),
187            ((-7994, -3340, 9583), 2786),
188            ((-16101, -13780, -1427), -155481),
189            ((10304, -16331, 15480), -10870),
190            ((-15879, 11912, -4650), 40677),
191            ((-5015, 6382, -15977), 2003),
192            ((2080, -11930, -15457), 1605),
193            ((-11071, 13350, 16138), -9158),
194            ((16084, -13564, -770), 283329),
195            ((14304, -10377, -21), 7068219),
196            ((-14056, -8853, -5488), -22674),
197            ((-10319, 14797, 8554), -17850),
198            ((-7820, 6826, 10555), -5057),
199            ((7257, 15928, 8159), 14167),
200            ((14929, 11579, -13204), -13091),
201            ((2808, 12070, -14697), -2306),
202            ((-13818, 8544, -1649), 71595),
203            ((3265, 7325, -1373), -17418),
204            ((14832, 10586, -6440), -24380),
205            ((4123, 8274, -2022), -16871),
206            ((4645, -4149, -7242), 2661),
207            ((-3891, 8366, 5771), -5640),
208            ((-15447, -3428, -9335), -5672),
209            ((13670, -14311, -11122), 17589),
210            ((12590, -6592, 13159), -6306),
211            ((-8369, -10193, 5051), 16888),
212            ((-9539, 5167, 2595), -18993),
213        ];
214        for ((a, b, c), expected_result) in cases {
215            let result = super::mul_div_no_round(a, b, c);
216            assert_eq!(result, expected_result);
217            let fa = Fixed::from_bits(a as _).to_f32();
218            let fb = Fixed::from_bits(b as _).to_f32();
219            let fc = Fixed::from_bits(c as _).to_f32();
220            let fresult = fa * fb / fc;
221            let fexpected_result = Fixed::from_bits(expected_result as _).to_f32();
222            assert!((fresult - fexpected_result).abs() < FLOAT_TOLERANCE);
223        }
224    }
225
226    #[test]
227    fn mul14() {
228        let cases = [
229            // computed with TT_MulFix14():
230            // ((a, b), result) where result = a * b
231            ((6236, -10078), -3836),
232            ((-6803, -5405), 2244),
233            ((-10006, -12852), 7849),
234            ((-15434, -4102), 3864),
235            ((-8681, 9269), -4911),
236            ((9449, -9130), -5265),
237            ((12643, 2161), 1668),
238            ((-6115, 9284), -3465),
239            ((316, 3390), 65),
240            ((15077, -12901), -11872),
241            ((-12182, 11613), -8635),
242            ((-7213, 8246), -3630),
243            ((13482, 8096), 6662),
244            ((5690, 15016), 5215),
245            ((-5991, 12613), -4612),
246            ((13112, -8404), -6726),
247            ((13524, 6786), 5601),
248            ((7156, 3291), 1437),
249            ((-2978, 353), -64),
250            ((-1755, 14626), -1567),
251            ((14402, 7886), 6932),
252            ((7124, 15730), 6840),
253            ((-12679, 14830), -11476),
254            ((-9374, -12999), 7437),
255            ((12301, -4685), -3517),
256            ((5324, 2066), 671),
257            ((6783, -4946), -2048),
258            ((12078, -968), -714),
259            ((-10137, 14116), -8734),
260            ((-13946, 11585), -9861),
261            ((-678, -2205), 91),
262            ((-2629, -3319), 533),
263        ];
264        for ((a, b), expected_result) in cases {
265            let result = super::mul14(a, b);
266            assert_eq!(result, expected_result);
267            let fa = F2Dot14::from_bits(a as _).to_f32();
268            let fb = F2Dot14::from_bits(b as _).to_f32();
269            let fresult = fa * fb;
270            let fexpected_result = F2Dot14::from_bits(expected_result as _).to_f32();
271            assert!((fresult - fexpected_result).abs() < FLOAT_TOLERANCE);
272        }
273    }
274
275    #[test]
276    fn normalize14() {
277        let cases = [
278            // computed with FT_Vector_NormLen():
279            // (input vector, expected normalized vector)
280            ((-13660, 11807), (-12395, 10713)),
281            ((-10763, 9293), (-12401, 10707)),
282            ((-3673, 673), (-16115, 2952)),
283            ((15886, -2964), (16106, -3005)),
284            ((15442, -2871), (16108, -2994)),
285            ((-6308, 5744), (-12114, 11031)),
286            ((9410, -10415), (10983, -12156)),
287            ((-10620, -14856), (-9528, -13328)),
288            ((-9372, 12029), (-10069, 12924)),
289            ((-1272, -1261), (-11635, -11534)),
290            ((-7076, -5517), (-12920, -10074)),
291            ((-10297, 179), (-16381, 284)),
292            ((9256, -13235), (9389, -13426)),
293            ((5315, -12449), (6433, -15068)),
294            ((8064, 15213), (7673, 14476)),
295            ((-8665, 41), (-16383, 77)),
296            ((-3455, -4720), (-9677, -13220)),
297            ((13449, -5152), (15299, -5861)),
298            ((-15605, 8230), (-14492, 7643)),
299            ((4716, -13690), (5336, -15490)),
300            ((12904, -11422), (12268, -10859)),
301            ((2825, -6396), (6619, -14987)),
302            ((4654, 15245), (4783, 15670)),
303            ((-14769, 15133), (-11443, 11725)),
304            ((-8090, -9057), (-10914, -12219)),
305            ((-472, 1953), (-3848, 15925)),
306            ((-12563, 1040), (-16328, 1351)),
307            ((-7938, 15587), (-7435, 14599)),
308            ((-9701, 5356), (-14343, 7919)),
309            ((-642, -14484), (-725, -16367)),
310            ((12963, -9690), (13123, -9809)),
311            ((7067, 5361), (13053, 9902)),
312            ((0x4000, 0), (0x4000, 0)),
313            ((0, 0x4000), (0, 0x4000)),
314            ((-0x4000, 0), (-0x4000, 0)),
315            ((0, -0x4000), (0, -0x4000)),
316        ];
317        for ((x, y), expected) in cases {
318            let n = super::normalize14(x, y);
319            assert_eq!((n.x, n.y), expected);
320            // Ensure the length of the vector is nearly 1.0
321            let fx = F2Dot14::from_bits(n.x as _).to_f32();
322            let fy = F2Dot14::from_bits(n.y as _).to_f32();
323            let flen = (fx * fx + fy * fy).sqrt();
324            assert!((flen - 1.0).abs() <= FLOAT_TOLERANCE);
325        }
326    }
327
328    #[test]
329    fn wrapping_rounding_extremes() {
330        // Note: wrapping behavior is ugly but matches FreeType and no
331        // real font should produce values that trigger this.
332        assert_eq!(super::round(i32::MAX), i32::MIN);
333        assert_eq!(super::ceil(i32::MAX), i32::MIN);
334        assert_eq!(super::round_pad(i32::MAX, 32), i32::MIN);
335    }
336
337    #[test]
338    fn mul_div_no_round_handles_min_value() {
339        assert_eq!(super::mul_div_no_round(i32::MIN, 1, 1), i32::MIN);
340        assert_eq!(super::mul_div_no_round(i32::MIN, -1, 1), i32::MIN);
341    }
342}
skrifa/outline/glyf/hint/math.rs

skrifa/outline/glyf/hint/
math.rs
