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