OLD | NEW |
1 /***************************************************************************/ | 1 /***************************************************************************/ |
2 /* */ | 2 /* */ |
3 /* ftcalc.c */ | 3 /* ftcalc.c */ |
4 /* */ | 4 /* */ |
5 /* Arithmetic computations (body). */ | 5 /* Arithmetic computations (body). */ |
6 /* */ | 6 /* */ |
7 /* Copyright 1996-2006, 2008, 2012-2013 by */ | 7 /* Copyright 1996-2006, 2008, 2012-2014 by */ |
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */ | 8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */ |
9 /* */ | 9 /* */ |
10 /* This file is part of the FreeType project, and may only be used, */ | 10 /* This file is part of the FreeType project, and may only be used, */ |
11 /* modified, and distributed under the terms of the FreeType project */ | 11 /* modified, and distributed under the terms of the FreeType project */ |
12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ | 12 /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ |
13 /* this file you indicate that you have read the license and */ | 13 /* this file you indicate that you have read the license and */ |
14 /* understand and accept it fully. */ | 14 /* understand and accept it fully. */ |
15 /* */ | 15 /* */ |
16 /***************************************************************************/ | 16 /***************************************************************************/ |
17 | 17 |
18 /*************************************************************************/ | 18 /*************************************************************************/ |
19 /* */ | 19 /* */ |
20 /* Support for 1-complement arithmetic has been totally dropped in this */ | 20 /* Support for 1-complement arithmetic has been totally dropped in this */ |
21 /* release. You can still write your own code if you need it. */ | 21 /* release. You can still write your own code if you need it. */ |
22 /* */ | 22 /* */ |
23 /*************************************************************************/ | 23 /*************************************************************************/ |
24 | 24 |
25 /*************************************************************************/ | 25 /*************************************************************************/ |
26 /* */ | 26 /* */ |
27 /* Implementing basic computation routines. */ | 27 /* Implementing basic computation routines. */ |
28 /* */ | 28 /* */ |
29 /* FT_MulDiv(), FT_MulFix(), FT_DivFix(), FT_RoundFix(), FT_CeilFix(), */ | 29 /* FT_MulDiv(), FT_MulFix(), FT_DivFix(), FT_RoundFix(), FT_CeilFix(), */ |
30 /* and FT_FloorFix() are declared in freetype.h. */ | 30 /* and FT_FloorFix() are declared in freetype.h. */ |
31 /* */ | 31 /* */ |
32 /*************************************************************************/ | 32 /*************************************************************************/ |
33 | 33 |
34 | 34 |
35 #include "../../include/ft2build.h" | 35 #include <ft2build.h> |
36 #include "../../include/freetype/ftglyph.h" | 36 #include FT_GLYPH_H |
37 #include "../../include/freetype/fttrigon.h" | 37 #include FT_TRIGONOMETRY_H |
38 #include "../../include/freetype/internal/ftcalc.h" | 38 #include FT_INTERNAL_CALC_H |
39 #include "../../include/freetype/internal/ftdebug.h" | 39 #include FT_INTERNAL_DEBUG_H |
40 #include "../../include/freetype/internal/ftobjs.h" | 40 #include FT_INTERNAL_OBJECTS_H |
41 | 41 |
42 | 42 |
| 43 #ifdef FT_MULFIX_ASSEMBLER |
| 44 #undef FT_MulFix |
| 45 #endif |
| 46 |
43 /* we need to emulate a 64-bit data type if a real one isn't available */ | 47 /* we need to emulate a 64-bit data type if a real one isn't available */ |
44 | 48 |
45 #ifndef FT_LONG64 | 49 #ifndef FT_LONG64 |
46 | 50 |
47 typedef struct FT_Int64_ | 51 typedef struct FT_Int64_ |
48 { | 52 { |
49 FT_UInt32 lo; | 53 FT_UInt32 lo; |
50 FT_UInt32 hi; | 54 FT_UInt32 hi; |
51 | 55 |
52 } FT_Int64; | 56 } FT_Int64; |
53 | 57 |
54 #endif /* !FT_LONG64 */ | 58 #endif /* !FT_LONG64 */ |
55 | 59 |
56 | 60 |
57 /*************************************************************************/ | 61 /*************************************************************************/ |
58 /* */ | 62 /* */ |
59 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */ | 63 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */ |
60 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */ | 64 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */ |
61 /* messages during execution. */ | 65 /* messages during execution. */ |
62 /* */ | 66 /* */ |
63 #undef FT_COMPONENT | 67 #undef FT_COMPONENT |
64 #define FT_COMPONENT trace_calc | 68 #define FT_COMPONENT trace_calc |
65 | 69 |
66 | 70 |
| 71 /* transfer sign leaving a positive number */ |
| 72 #define FT_MOVE_SIGN( x, s ) \ |
| 73 FT_BEGIN_STMNT \ |
| 74 if ( x < 0 ) \ |
| 75 { \ |
| 76 x = -x; \ |
| 77 s = -s; \ |
| 78 } \ |
| 79 FT_END_STMNT |
| 80 |
67 /* The following three functions are available regardless of whether */ | 81 /* The following three functions are available regardless of whether */ |
68 /* FT_LONG64 is defined. */ | 82 /* FT_LONG64 is defined. */ |
69 | 83 |
70 /* documentation is in freetype.h */ | 84 /* documentation is in freetype.h */ |
71 | 85 |
72 FT_EXPORT_DEF( FT_Fixed ) | 86 FT_EXPORT_DEF( FT_Fixed ) |
73 FT_RoundFix( FT_Fixed a ) | 87 FT_RoundFix( FT_Fixed a ) |
74 { | 88 { |
75 return ( a >= 0 ) ? ( a + 0x8000L ) & ~0xFFFFL | 89 return ( a >= 0 ) ? ( a + 0x8000L ) & ~0xFFFFL |
76 : -((-a + 0x8000L ) & ~0xFFFFL ); | 90 : -((-a + 0x8000L ) & ~0xFFFFL ); |
(...skipping 12 matching lines...) Expand all Loading... |
89 | 103 |
90 /* documentation is in freetype.h */ | 104 /* documentation is in freetype.h */ |
91 | 105 |
92 FT_EXPORT_DEF( FT_Fixed ) | 106 FT_EXPORT_DEF( FT_Fixed ) |
93 FT_FloorFix( FT_Fixed a ) | 107 FT_FloorFix( FT_Fixed a ) |
94 { | 108 { |
95 return ( a >= 0 ) ? a & ~0xFFFFL | 109 return ( a >= 0 ) ? a & ~0xFFFFL |
96 : -((-a) & ~0xFFFFL ); | 110 : -((-a) & ~0xFFFFL ); |
97 } | 111 } |
98 | 112 |
| 113 #ifndef FT_MSB |
99 | 114 |
100 FT_BASE_DEF ( FT_Int ) | 115 FT_BASE_DEF ( FT_Int ) |
101 FT_MSB( FT_UInt32 z ) | 116 FT_MSB( FT_UInt32 z ) |
102 { | 117 { |
103 FT_Int shift = 0; | 118 FT_Int shift = 0; |
104 | 119 |
105 /* determine msb bit index in `shift' */ | 120 /* determine msb bit index in `shift' */ |
106 if ( z >= ( 1L << 16 ) ) | 121 if ( z & 0xFFFF0000U ) |
107 { | 122 { |
108 z >>= 16; | 123 z >>= 16; |
109 shift += 16; | 124 shift += 16; |
110 } | 125 } |
111 if ( z >= ( 1L << 8 ) ) | 126 if ( z & 0x0000FF00U ) |
112 { | 127 { |
113 z >>= 8; | 128 z >>= 8; |
114 shift += 8; | 129 shift += 8; |
115 } | 130 } |
116 if ( z >= ( 1L << 4 ) ) | 131 if ( z & 0x000000F0U ) |
117 { | 132 { |
118 z >>= 4; | 133 z >>= 4; |
119 shift += 4; | 134 shift += 4; |
120 } | 135 } |
121 if ( z >= ( 1L << 2 ) ) | 136 if ( z & 0x0000000CU ) |
122 { | 137 { |
123 z >>= 2; | 138 z >>= 2; |
124 shift += 2; | 139 shift += 2; |
125 } | 140 } |
126 if ( z >= ( 1L << 1 ) ) | 141 if ( z & 0x00000002U ) |
127 { | 142 { |
128 z >>= 1; | 143 /* z >>= 1; */ |
129 shift += 1; | 144 shift += 1; |
130 } | 145 } |
131 | 146 |
132 return shift; | 147 return shift; |
133 } | 148 } |
134 | 149 |
| 150 #endif /* !FT_MSB */ |
| 151 |
135 | 152 |
136 /* documentation is in ftcalc.h */ | 153 /* documentation is in ftcalc.h */ |
137 | 154 |
138 FT_BASE_DEF( FT_Fixed ) | 155 FT_BASE_DEF( FT_Fixed ) |
139 FT_Hypot( FT_Fixed x, | 156 FT_Hypot( FT_Fixed x, |
140 FT_Fixed y ) | 157 FT_Fixed y ) |
141 { | 158 { |
142 FT_Vector v; | 159 FT_Vector v; |
143 | 160 |
144 | 161 |
145 v.x = x; | 162 v.x = x; |
146 v.y = y; | 163 v.y = y; |
147 | 164 |
148 return FT_Vector_Length( &v ); | 165 return FT_Vector_Length( &v ); |
149 } | 166 } |
150 | 167 |
151 | 168 |
152 #ifdef FT_LONG64 | 169 #ifdef FT_LONG64 |
153 | 170 |
154 | 171 |
155 /* documentation is in freetype.h */ | 172 /* documentation is in freetype.h */ |
156 | 173 |
157 FT_EXPORT_DEF( FT_Long ) | 174 FT_EXPORT_DEF( FT_Long ) |
158 FT_MulDiv( FT_Long a, | 175 FT_MulDiv( FT_Long a, |
159 FT_Long b, | 176 FT_Long b, |
160 FT_Long c ) | 177 FT_Long c ) |
161 { | 178 { |
162 FT_Int s; | 179 FT_Int s = 1; |
163 FT_Long d; | 180 FT_Long d; |
164 | 181 |
165 | 182 |
166 s = 1; | 183 FT_MOVE_SIGN( a, s ); |
167 if ( a < 0 ) { a = -a; s = -1; } | 184 FT_MOVE_SIGN( b, s ); |
168 if ( b < 0 ) { b = -b; s = -s; } | 185 FT_MOVE_SIGN( c, s ); |
169 if ( c < 0 ) { c = -c; s = -s; } | |
170 | 186 |
171 d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c | 187 d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c |
172 : 0x7FFFFFFFL ); | 188 : 0x7FFFFFFFL ); |
173 | 189 |
174 return ( s > 0 ) ? d : -d; | 190 return ( s > 0 ) ? d : -d; |
175 } | 191 } |
176 | 192 |
177 | 193 |
178 /* documentation is in ftcalc.h */ | 194 /* documentation is in ftcalc.h */ |
179 | 195 |
180 FT_BASE_DEF( FT_Long ) | 196 FT_BASE_DEF( FT_Long ) |
181 FT_MulDiv_No_Round( FT_Long a, | 197 FT_MulDiv_No_Round( FT_Long a, |
182 FT_Long b, | 198 FT_Long b, |
183 FT_Long c ) | 199 FT_Long c ) |
184 { | 200 { |
185 FT_Int s; | 201 FT_Int s = 1; |
186 FT_Long d; | 202 FT_Long d; |
187 | 203 |
188 | 204 |
189 s = 1; | 205 FT_MOVE_SIGN( a, s ); |
190 if ( a < 0 ) { a = -a; s = -1; } | 206 FT_MOVE_SIGN( b, s ); |
191 if ( b < 0 ) { b = -b; s = -s; } | 207 FT_MOVE_SIGN( c, s ); |
192 if ( c < 0 ) { c = -c; s = -s; } | |
193 | 208 |
194 d = (FT_Long)( c > 0 ? (FT_Int64)a * b / c | 209 d = (FT_Long)( c > 0 ? (FT_Int64)a * b / c |
195 : 0x7FFFFFFFL ); | 210 : 0x7FFFFFFFL ); |
196 | 211 |
197 return ( s > 0 ) ? d : -d; | 212 return ( s > 0 ) ? d : -d; |
198 } | 213 } |
199 | 214 |
200 | 215 |
201 /* documentation is in freetype.h */ | 216 /* documentation is in freetype.h */ |
202 /* if defined FT_MULFIX_INLINED, use the inline FT_MULFIX_ASSEMBLER function.
*/ | 217 |
203 #ifndef FT_MULFIX_INLINED | |
204 FT_EXPORT_DEF( FT_Long ) | 218 FT_EXPORT_DEF( FT_Long ) |
205 FT_MulFix( FT_Long a, | 219 FT_MulFix( FT_Long a, |
206 FT_Long b ) | 220 FT_Long b ) |
207 { | 221 { |
208 #ifdef FT_MULFIX_ASSEMBLER | 222 #ifdef FT_MULFIX_ASSEMBLER |
209 | 223 |
210 return FT_MULFIX_ASSEMBLER( a, b ); | 224 return FT_MULFIX_ASSEMBLER( a, b ); |
211 | 225 |
212 #else | 226 #else |
213 | 227 |
214 FT_Int s = 1; | 228 FT_Int s = 1; |
215 FT_Long c; | 229 FT_Long c; |
216 | 230 |
217 | 231 |
218 if ( a < 0 ) | 232 FT_MOVE_SIGN( a, s ); |
219 { | 233 FT_MOVE_SIGN( b, s ); |
220 a = -a; | |
221 s = -1; | |
222 } | |
223 | |
224 if ( b < 0 ) | |
225 { | |
226 b = -b; | |
227 s = -s; | |
228 } | |
229 | 234 |
230 c = (FT_Long)( ( (FT_Int64)a * b + 0x8000L ) >> 16 ); | 235 c = (FT_Long)( ( (FT_Int64)a * b + 0x8000L ) >> 16 ); |
231 | 236 |
232 return ( s > 0 ) ? c : -c; | 237 return ( s > 0 ) ? c : -c; |
233 | 238 |
234 #endif /* FT_MULFIX_ASSEMBLER */ | 239 #endif /* FT_MULFIX_ASSEMBLER */ |
235 } | 240 } |
236 #endif/* FT_MULFIX_INLINED */ | 241 |
237 | 242 |
238 /* documentation is in freetype.h */ | 243 /* documentation is in freetype.h */ |
239 | 244 |
240 FT_EXPORT_DEF( FT_Long ) | 245 FT_EXPORT_DEF( FT_Long ) |
241 FT_DivFix( FT_Long a, | 246 FT_DivFix( FT_Long a, |
242 FT_Long b ) | 247 FT_Long b ) |
243 { | 248 { |
244 FT_Int32 s; | 249 FT_Int s = 1; |
245 FT_UInt32 q; | 250 FT_Long q; |
246 | 251 |
247 | 252 |
248 s = 1; | 253 FT_MOVE_SIGN( a, s ); |
249 if ( a < 0 ) | 254 FT_MOVE_SIGN( b, s ); |
250 { | |
251 a = -a; | |
252 s = -1; | |
253 } | |
254 if ( b < 0 ) | |
255 { | |
256 b = -b; | |
257 s = -s; | |
258 } | |
259 | 255 |
260 if ( b == 0 ) | 256 q = (FT_Long)( b > 0 ? ( ( (FT_UInt64)a << 16 ) + ( b >> 1 ) ) / b |
261 /* check for division by 0 */ | 257 : 0x7FFFFFFFL ); |
262 q = 0x7FFFFFFFL; | |
263 else | |
264 /* compute result directly */ | |
265 q = (FT_UInt32)( ( ( (FT_UInt64)a << 16 ) + ( b >> 1 ) ) / b ); | |
266 | 258 |
267 return ( s < 0 ? -(FT_Long)q : (FT_Long)q ); | 259 return ( s < 0 ? -q : q ); |
268 } | 260 } |
269 | 261 |
270 | 262 |
271 #else /* !FT_LONG64 */ | 263 #else /* !FT_LONG64 */ |
272 | 264 |
273 | 265 |
274 static void | 266 static void |
275 ft_multo64( FT_UInt32 x, | 267 ft_multo64( FT_UInt32 x, |
276 FT_UInt32 y, | 268 FT_UInt32 y, |
277 FT_Int64 *z ) | 269 FT_Int64 *z ) |
(...skipping 27 matching lines...) Expand all Loading... |
305 | 297 |
306 static FT_UInt32 | 298 static FT_UInt32 |
307 ft_div64by32( FT_UInt32 hi, | 299 ft_div64by32( FT_UInt32 hi, |
308 FT_UInt32 lo, | 300 FT_UInt32 lo, |
309 FT_UInt32 y ) | 301 FT_UInt32 y ) |
310 { | 302 { |
311 FT_UInt32 r, q; | 303 FT_UInt32 r, q; |
312 FT_Int i; | 304 FT_Int i; |
313 | 305 |
314 | 306 |
315 q = 0; | 307 if ( hi >= y ) |
316 r = hi; | |
317 | |
318 if ( r >= y ) | |
319 return (FT_UInt32)0x7FFFFFFFL; | 308 return (FT_UInt32)0x7FFFFFFFL; |
320 | 309 |
321 i = 32; | 310 /* We shift as many bits as we can into the high register, perform */ |
| 311 /* 32-bit division with modulo there, then work through the remaining */ |
| 312 /* bits with long division. This optimization is especially noticeable */ |
| 313 /* for smaller dividends that barely use the high register. */ |
| 314 |
| 315 i = 31 - FT_MSB( hi ); |
| 316 r = ( hi << i ) | ( lo >> ( 32 - i ) ); lo <<= i; /* left 64-bit shift */ |
| 317 q = r / y; |
| 318 r -= q * y; /* remainder */ |
| 319 |
| 320 i = 32 - i; /* bits remaining in low register */ |
322 do | 321 do |
323 { | 322 { |
324 r <<= 1; | |
325 q <<= 1; | 323 q <<= 1; |
326 r |= lo >> 31; | 324 r = ( r << 1 ) | ( lo >> 31 ); lo <<= 1; |
327 | 325 |
328 if ( r >= y ) | 326 if ( r >= y ) |
329 { | 327 { |
330 r -= y; | 328 r -= y; |
331 q |= 1; | 329 q |= 1; |
332 } | 330 } |
333 lo <<= 1; | |
334 } while ( --i ); | 331 } while ( --i ); |
335 | 332 |
336 return q; | 333 return q; |
337 } | 334 } |
338 | 335 |
339 | 336 |
340 static void | 337 static void |
341 FT_Add64( FT_Int64* x, | 338 FT_Add64( FT_Int64* x, |
342 FT_Int64* y, | 339 FT_Int64* y, |
343 FT_Int64 *z ) | 340 FT_Int64 *z ) |
344 { | 341 { |
345 register FT_UInt32 lo, hi; | 342 FT_UInt32 lo, hi; |
346 | 343 |
347 | 344 |
348 lo = x->lo + y->lo; | 345 lo = x->lo + y->lo; |
349 hi = x->hi + y->hi + ( lo < x->lo ); | 346 hi = x->hi + y->hi + ( lo < x->lo ); |
350 | 347 |
351 z->lo = lo; | 348 z->lo = lo; |
352 z->hi = hi; | 349 z->hi = hi; |
353 } | 350 } |
354 | 351 |
355 | 352 |
| 353 /* The FT_MulDiv function has been optimized thanks to ideas from */ |
| 354 /* Graham Asher and Alexei Podtelezhnikov. The trick is to optimize */ |
| 355 /* a rather common case when everything fits within 32-bits. */ |
| 356 /* */ |
| 357 /* We compute 'a*b+c/2', then divide it by 'c' (all positive values). */ |
| 358 /* */ |
| 359 /* The product of two positive numbers never exceeds the square of */ |
| 360 /* its mean values. Therefore, we always avoid the overflow by */ |
| 361 /* imposing */ |
| 362 /* */ |
| 363 /* (a + b) / 2 <= sqrt(X - c/2) , */ |
| 364 /* */ |
| 365 /* where X = 2^32 - 1, the maximum unsigned 32-bit value, and using */ |
| 366 /* unsigned arithmetic. Now we replace `sqrt' with a linear function */ |
| 367 /* that is smaller or equal for all values of c in the interval */ |
| 368 /* [0;X/2]; it should be equal to sqrt(X) and sqrt(3X/4) at the */ |
| 369 /* endpoints. Substituting the linear solution and explicit numbers */ |
| 370 /* we get */ |
| 371 /* */ |
| 372 /* a + b <= 131071.99 - c / 122291.84 . */ |
| 373 /* */ |
| 374 /* In practice, we should use a faster and even stronger inequality */ |
| 375 /* */ |
| 376 /* a + b <= 131071 - (c >> 16) */ |
| 377 /* */ |
| 378 /* or, alternatively, */ |
| 379 /* */ |
| 380 /* a + b <= 129894 - (c >> 17) . */ |
| 381 /* */ |
| 382 /* FT_MulFix, on the other hand, is optimized for a small value of */ |
| 383 /* the first argument, when the second argument can be much larger. */ |
| 384 /* This can be achieved by scaling the second argument and the limit */ |
| 385 /* in the above inequalities. For example, */ |
| 386 /* */ |
| 387 /* a + (b >> 8) <= (131071 >> 4) */ |
| 388 /* */ |
| 389 /* covers the practical range of use. The actual test below is a bit */ |
| 390 /* tighter to avoid the border case overflows. */ |
| 391 /* */ |
| 392 /* In the case of FT_DivFix, the exact overflow check */ |
| 393 /* */ |
| 394 /* a << 16 <= X - c/2 */ |
| 395 /* */ |
| 396 /* is scaled down by 2^16 and we use */ |
| 397 /* */ |
| 398 /* a <= 65535 - (c >> 17) . */ |
| 399 |
356 /* documentation is in freetype.h */ | 400 /* documentation is in freetype.h */ |
357 | 401 |
358 /* The FT_MulDiv function has been optimized thanks to ideas from */ | |
359 /* Graham Asher. The trick is to optimize computation when everything */ | |
360 /* fits within 32-bits (a rather common case). */ | |
361 /* */ | |
362 /* we compute 'a*b+c/2', then divide it by 'c'. (positive values) */ | |
363 /* */ | |
364 /* 46340 is FLOOR(SQRT(2^31-1)). */ | |
365 /* */ | |
366 /* if ( a <= 46340 && b <= 46340 ) then ( a*b <= 0x7FFEA810 ) */ | |
367 /* */ | |
368 /* 0x7FFFFFFF - 0x7FFEA810 = 0x157F0 */ | |
369 /* */ | |
370 /* if ( c < 0x157F0*2 ) then ( a*b+c/2 <= 0x7FFFFFFF ) */ | |
371 /* */ | |
372 /* and 2*0x157F0 = 176096 */ | |
373 /* */ | |
374 | |
375 FT_EXPORT_DEF( FT_Long ) | 402 FT_EXPORT_DEF( FT_Long ) |
376 FT_MulDiv( FT_Long a, | 403 FT_MulDiv( FT_Long a, |
377 FT_Long b, | 404 FT_Long b, |
378 FT_Long c ) | 405 FT_Long c ) |
379 { | 406 { |
380 long s; | 407 FT_Int s = 1; |
381 | 408 |
382 | 409 |
383 /* XXX: this function does not allow 64-bit arguments */ | 410 /* XXX: this function does not allow 64-bit arguments */ |
384 if ( a == 0 || b == c ) | 411 if ( a == 0 || b == c ) |
385 return a; | 412 return a; |
386 | 413 |
387 s = a; a = FT_ABS( a ); | 414 FT_MOVE_SIGN( a, s ); |
388 s ^= b; b = FT_ABS( b ); | 415 FT_MOVE_SIGN( b, s ); |
389 s ^= c; c = FT_ABS( c ); | 416 FT_MOVE_SIGN( c, s ); |
390 | 417 |
391 if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 ) | 418 if ( c == 0 ) |
392 a = ( a * b + ( c >> 1 ) ) / c; | 419 a = 0x7FFFFFFFL; |
393 | 420 |
394 else if ( (FT_Int32)c > 0 ) | 421 else if ( (FT_ULong)a + b <= 129894UL - ( c >> 17 ) ) |
| 422 a = ( (FT_ULong)a * b + ( c >> 1 ) ) / c; |
| 423 |
| 424 else |
395 { | 425 { |
396 FT_Int64 temp, temp2; | 426 FT_Int64 temp, temp2; |
397 | 427 |
398 | 428 |
399 ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp ); | 429 ft_multo64( a, b, &temp ); |
400 | 430 |
401 temp2.hi = 0; | 431 temp2.hi = 0; |
402 temp2.lo = (FT_UInt32)(c >> 1); | 432 temp2.lo = c >> 1; |
| 433 |
403 FT_Add64( &temp, &temp2, &temp ); | 434 FT_Add64( &temp, &temp2, &temp ); |
404 a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c ); | 435 |
| 436 /* last attempt to ditch long division */ |
| 437 a = temp.hi == 0 ? temp.lo / c |
| 438 : ft_div64by32( temp.hi, temp.lo, c ); |
405 } | 439 } |
406 else | |
407 a = 0x7FFFFFFFL; | |
408 | 440 |
409 return ( s < 0 ? -a : a ); | 441 return ( s < 0 ? -a : a ); |
410 } | 442 } |
411 | 443 |
412 | 444 |
413 FT_BASE_DEF( FT_Long ) | 445 FT_BASE_DEF( FT_Long ) |
414 FT_MulDiv_No_Round( FT_Long a, | 446 FT_MulDiv_No_Round( FT_Long a, |
415 FT_Long b, | 447 FT_Long b, |
416 FT_Long c ) | 448 FT_Long c ) |
417 { | 449 { |
418 long s; | 450 FT_Int s = 1; |
419 | 451 |
420 | 452 |
421 if ( a == 0 || b == c ) | 453 if ( a == 0 || b == c ) |
422 return a; | 454 return a; |
423 | 455 |
424 s = a; a = FT_ABS( a ); | 456 FT_MOVE_SIGN( a, s ); |
425 s ^= b; b = FT_ABS( b ); | 457 FT_MOVE_SIGN( b, s ); |
426 s ^= c; c = FT_ABS( c ); | 458 FT_MOVE_SIGN( c, s ); |
427 | 459 |
428 if ( a <= 46340L && b <= 46340L && c > 0 ) | 460 if ( c == 0 ) |
429 a = a * b / c; | 461 a = 0x7FFFFFFFL; |
430 | 462 |
431 else if ( (FT_Int32)c > 0 ) | 463 else if ( (FT_ULong)a + b <= 131071UL ) |
| 464 a = (FT_ULong)a * b / c; |
| 465 |
| 466 else |
432 { | 467 { |
433 FT_Int64 temp; | 468 FT_Int64 temp; |
434 | 469 |
435 | 470 |
436 ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp ); | 471 ft_multo64( a, b, &temp ); |
437 a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c ); | 472 |
| 473 /* last attempt to ditch long division */ |
| 474 a = temp.hi == 0 ? temp.lo / c |
| 475 : ft_div64by32( temp.hi, temp.lo, c ); |
438 } | 476 } |
439 else | |
440 a = 0x7FFFFFFFL; | |
441 | 477 |
442 return ( s < 0 ? -a : a ); | 478 return ( s < 0 ? -a : a ); |
443 } | 479 } |
444 | 480 |
445 | 481 |
446 /* documentation is in freetype.h */ | 482 /* documentation is in freetype.h */ |
447 #ifndef FT_MULFIX_INLINED | 483 |
448 FT_EXPORT_DEF( FT_Long ) | 484 FT_EXPORT_DEF( FT_Long ) |
449 FT_MulFix( FT_Long a, | 485 FT_MulFix( FT_Long a, |
450 FT_Long b ) | 486 FT_Long b ) |
451 { | 487 { |
452 #ifdef FT_MULFIX_ASSEMBLER | 488 #ifdef FT_MULFIX_ASSEMBLER |
453 | 489 |
454 return FT_MULFIX_ASSEMBLER( a, b ); | 490 return FT_MULFIX_ASSEMBLER( a, b ); |
455 | 491 |
456 #elif 0 | 492 #elif 0 |
457 | 493 |
(...skipping 30 matching lines...) Expand all Loading... |
488 * wrong. | 524 * wrong. |
489 */ | 525 */ |
490 sa = ( a >> ( sizeof ( a ) * 8 - 1 ) ); | 526 sa = ( a >> ( sizeof ( a ) * 8 - 1 ) ); |
491 a = ( a ^ sa ) - sa; | 527 a = ( a ^ sa ) - sa; |
492 sb = ( b >> ( sizeof ( b ) * 8 - 1 ) ); | 528 sb = ( b >> ( sizeof ( b ) * 8 - 1 ) ); |
493 b = ( b ^ sb ) - sb; | 529 b = ( b ^ sb ) - sb; |
494 | 530 |
495 ua = (FT_ULong)a; | 531 ua = (FT_ULong)a; |
496 ub = (FT_ULong)b; | 532 ub = (FT_ULong)b; |
497 | 533 |
498 if ( ua <= 2048 && ub <= 1048576L ) | 534 if ( ua + ( ub >> 8 ) <= 8190UL ) |
499 ua = ( ua * ub + 0x8000U ) >> 16; | 535 ua = ( ua * ub + 0x8000U ) >> 16; |
500 else | 536 else |
501 { | 537 { |
502 FT_ULong al = ua & 0xFFFFU; | 538 FT_ULong al = ua & 0xFFFFU; |
503 | 539 |
504 | 540 |
505 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + | 541 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + |
506 ( ( al * ( ub & 0xFFFFU ) + 0x8000U ) >> 16 ); | 542 ( ( al * ( ub & 0xFFFFU ) + 0x8000U ) >> 16 ); |
507 } | 543 } |
508 | 544 |
509 sa ^= sb, | 545 sa ^= sb, |
510 ua = (FT_ULong)(( ua ^ sa ) - sa); | 546 ua = (FT_ULong)(( ua ^ sa ) - sa); |
511 | 547 |
512 return (FT_Long)ua; | 548 return (FT_Long)ua; |
513 | 549 |
514 #else /* 0 */ | 550 #else /* 0 */ |
515 | 551 |
516 FT_Long s; | 552 FT_Int s = 1; |
517 FT_ULong ua, ub; | 553 FT_ULong ua, ub; |
518 | 554 |
519 | 555 |
520 if ( a == 0 || b == 0x10000L ) | 556 if ( a == 0 || b == 0x10000L ) |
521 return a; | 557 return a; |
522 | 558 |
523 s = a; a = FT_ABS( a ); | 559 FT_MOVE_SIGN( a, s ); |
524 s ^= b; b = FT_ABS( b ); | 560 FT_MOVE_SIGN( b, s ); |
525 | 561 |
526 ua = (FT_ULong)a; | 562 ua = (FT_ULong)a; |
527 ub = (FT_ULong)b; | 563 ub = (FT_ULong)b; |
528 | 564 |
529 if ( ua <= 2048 && ub <= 1048576L ) | 565 if ( ua + ( ub >> 8 ) <= 8190UL ) |
530 ua = ( ua * ub + 0x8000UL ) >> 16; | 566 ua = ( ua * ub + 0x8000UL ) >> 16; |
531 else | 567 else |
532 { | 568 { |
533 FT_ULong al = ua & 0xFFFFUL; | 569 FT_ULong al = ua & 0xFFFFUL; |
534 | 570 |
535 | 571 |
536 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + | 572 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + |
537 ( ( al * ( ub & 0xFFFFUL ) + 0x8000UL ) >> 16 ); | 573 ( ( al * ( ub & 0xFFFFUL ) + 0x8000UL ) >> 16 ); |
538 } | 574 } |
539 | 575 |
540 return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua ); | 576 return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua ); |
541 | 577 |
542 #endif /* 0 */ | 578 #endif /* 0 */ |
543 | 579 |
544 } | 580 } |
545 #endif | 581 |
546 | 582 |
547 /* documentation is in freetype.h */ | 583 /* documentation is in freetype.h */ |
548 | 584 |
549 FT_EXPORT_DEF( FT_Long ) | 585 FT_EXPORT_DEF( FT_Long ) |
550 FT_DivFix( FT_Long a, | 586 FT_DivFix( FT_Long a, |
551 FT_Long b ) | 587 FT_Long b ) |
552 { | 588 { |
553 FT_Int32 s; | 589 FT_Int s = 1; |
554 FT_UInt32 q; | 590 FT_Long q; |
555 | 591 |
556 | 592 |
557 /* XXX: this function does not allow 64-bit arguments */ | 593 /* XXX: this function does not allow 64-bit arguments */ |
558 s = (FT_Int32)a; a = FT_ABS( a ); | |
559 s ^= (FT_Int32)b; b = FT_ABS( b ); | |
560 | 594 |
561 if ( (FT_UInt32)b == 0 ) | 595 FT_MOVE_SIGN( a, s ); |
| 596 FT_MOVE_SIGN( b, s ); |
| 597 |
| 598 if ( b == 0 ) |
562 { | 599 { |
563 /* check for division by 0 */ | 600 /* check for division by 0 */ |
564 q = (FT_UInt32)0x7FFFFFFFL; | 601 q = 0x7FFFFFFFL; |
565 } | 602 } |
566 else if ( ( a >> 16 ) == 0 ) | 603 else if ( a <= 65535L - ( b >> 17 ) ) |
567 { | 604 { |
568 /* compute result directly */ | 605 /* compute result directly */ |
569 q = (FT_UInt32)( ( (FT_ULong)a << 16 ) + ( b >> 1 ) ) / (FT_UInt32)b; | 606 q = (FT_Long)( ( ( (FT_ULong)a << 16 ) + ( b >> 1 ) ) / b ); |
570 } | 607 } |
571 else | 608 else |
572 { | 609 { |
573 /* we need more bits; we have to do it by hand */ | 610 /* we need more bits; we have to do it by hand */ |
574 FT_Int64 temp, temp2; | 611 FT_Int64 temp, temp2; |
575 | 612 |
576 | 613 |
577 temp.hi = (FT_Int32)( a >> 16 ); | 614 temp.hi = a >> 16; |
578 temp.lo = (FT_UInt32)a << 16; | 615 temp.lo = a << 16; |
579 temp2.hi = 0; | 616 temp2.hi = 0; |
580 temp2.lo = (FT_UInt32)( b >> 1 ); | 617 temp2.lo = b >> 1; |
| 618 |
581 FT_Add64( &temp, &temp2, &temp ); | 619 FT_Add64( &temp, &temp2, &temp ); |
582 q = ft_div64by32( temp.hi, temp.lo, (FT_Int32)b ); | 620 q = (FT_Long)ft_div64by32( temp.hi, temp.lo, b ); |
583 } | 621 } |
584 | 622 |
585 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); | 623 return ( s < 0 ? -q : q ); |
586 } | 624 } |
587 | 625 |
588 | 626 |
589 #if 0 | |
590 | |
591 /* documentation is in ftcalc.h */ | |
592 | |
593 FT_EXPORT_DEF( void ) | |
594 FT_MulTo64( FT_Int32 x, | |
595 FT_Int32 y, | |
596 FT_Int64 *z ) | |
597 { | |
598 FT_Int32 s; | |
599 | |
600 | |
601 s = x; x = FT_ABS( x ); | |
602 s ^= y; y = FT_ABS( y ); | |
603 | |
604 ft_multo64( x, y, z ); | |
605 | |
606 if ( s < 0 ) | |
607 { | |
608 z->lo = (FT_UInt32)-(FT_Int32)z->lo; | |
609 z->hi = ~z->hi + !( z->lo ); | |
610 } | |
611 } | |
612 | |
613 | |
614 /* apparently, the second version of this code is not compiled correctly */ | |
615 /* on Mac machines with the MPW C compiler.. tsk, tsk, tsk... */ | |
616 | |
617 #if 1 | |
618 | |
619 FT_EXPORT_DEF( FT_Int32 ) | |
620 FT_Div64by32( FT_Int64* x, | |
621 FT_Int32 y ) | |
622 { | |
623 FT_Int32 s; | |
624 FT_UInt32 q, r, i, lo; | |
625 | |
626 | |
627 s = x->hi; | |
628 if ( s < 0 ) | |
629 { | |
630 x->lo = (FT_UInt32)-(FT_Int32)x->lo; | |
631 x->hi = ~x->hi + !x->lo; | |
632 } | |
633 s ^= y; y = FT_ABS( y ); | |
634 | |
635 /* Shortcut */ | |
636 if ( x->hi == 0 ) | |
637 { | |
638 if ( y > 0 ) | |
639 q = x->lo / y; | |
640 else | |
641 q = 0x7FFFFFFFL; | |
642 | |
643 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); | |
644 } | |
645 | |
646 r = x->hi; | |
647 lo = x->lo; | |
648 | |
649 if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */ | |
650 return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL ); | |
651 /* Return Max/Min Int32 if division overflow. */ | |
652 /* This includes division by zero! */ | |
653 q = 0; | |
654 for ( i = 0; i < 32; i++ ) | |
655 { | |
656 r <<= 1; | |
657 q <<= 1; | |
658 r |= lo >> 31; | |
659 | |
660 if ( r >= (FT_UInt32)y ) | |
661 { | |
662 r -= y; | |
663 q |= 1; | |
664 } | |
665 lo <<= 1; | |
666 } | |
667 | |
668 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); | |
669 } | |
670 | |
671 #else /* 0 */ | |
672 | |
673 FT_EXPORT_DEF( FT_Int32 ) | |
674 FT_Div64by32( FT_Int64* x, | |
675 FT_Int32 y ) | |
676 { | |
677 FT_Int32 s; | |
678 FT_UInt32 q; | |
679 | |
680 | |
681 s = x->hi; | |
682 if ( s < 0 ) | |
683 { | |
684 x->lo = (FT_UInt32)-(FT_Int32)x->lo; | |
685 x->hi = ~x->hi + !x->lo; | |
686 } | |
687 s ^= y; y = FT_ABS( y ); | |
688 | |
689 /* Shortcut */ | |
690 if ( x->hi == 0 ) | |
691 { | |
692 if ( y > 0 ) | |
693 q = ( x->lo + ( y >> 1 ) ) / y; | |
694 else | |
695 q = 0x7FFFFFFFL; | |
696 | |
697 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); | |
698 } | |
699 | |
700 q = ft_div64by32( x->hi, x->lo, y ); | |
701 | |
702 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); | |
703 } | |
704 | |
705 #endif /* 0 */ | |
706 | |
707 #endif /* 0 */ | |
708 | |
709 | |
710 #endif /* FT_LONG64 */ | 627 #endif /* FT_LONG64 */ |
711 | 628 |
712 | 629 |
713 /* documentation is in ftglyph.h */ | 630 /* documentation is in ftglyph.h */ |
714 | 631 |
715 FT_EXPORT_DEF( void ) | 632 FT_EXPORT_DEF( void ) |
716 FT_Matrix_Multiply( const FT_Matrix* a, | 633 FT_Matrix_Multiply( const FT_Matrix* a, |
717 FT_Matrix *b ) | 634 FT_Matrix *b ) |
718 { | 635 { |
719 FT_Fixed xx, xy, yx, yy; | 636 FT_Fixed xx, xy, yx, yy; |
(...skipping 87 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
807 FT_MulDiv( vector->y, matrix->xy, val ); | 724 FT_MulDiv( vector->y, matrix->xy, val ); |
808 | 725 |
809 yz = FT_MulDiv( vector->x, matrix->yx, val ) + | 726 yz = FT_MulDiv( vector->x, matrix->yx, val ) + |
810 FT_MulDiv( vector->y, matrix->yy, val ); | 727 FT_MulDiv( vector->y, matrix->yy, val ); |
811 | 728 |
812 vector->x = xz; | 729 vector->x = xz; |
813 vector->y = yz; | 730 vector->y = yz; |
814 } | 731 } |
815 | 732 |
816 | 733 |
| 734 #if 0 |
| 735 |
817 /* documentation is in ftcalc.h */ | 736 /* documentation is in ftcalc.h */ |
818 | 737 |
819 FT_BASE_DEF( FT_Int32 ) | 738 FT_BASE_DEF( FT_Int32 ) |
820 FT_SqrtFixed( FT_Int32 x ) | 739 FT_SqrtFixed( FT_Int32 x ) |
821 { | 740 { |
822 FT_UInt32 root, rem_hi, rem_lo, test_div; | 741 FT_UInt32 root, rem_hi, rem_lo, test_div; |
823 FT_Int count; | 742 FT_Int count; |
824 | 743 |
825 | 744 |
826 root = 0; | 745 root = 0; |
(...skipping 14 matching lines...) Expand all Loading... |
841 { | 760 { |
842 rem_hi -= test_div; | 761 rem_hi -= test_div; |
843 root += 1; | 762 root += 1; |
844 } | 763 } |
845 } while ( --count ); | 764 } while ( --count ); |
846 } | 765 } |
847 | 766 |
848 return (FT_Int32)root; | 767 return (FT_Int32)root; |
849 } | 768 } |
850 | 769 |
| 770 #endif /* 0 */ |
| 771 |
851 | 772 |
852 /* documentation is in ftcalc.h */ | 773 /* documentation is in ftcalc.h */ |
853 | 774 |
854 FT_BASE_DEF( FT_Int ) | 775 FT_BASE_DEF( FT_Int ) |
855 ft_corner_orientation( FT_Pos in_x, | 776 ft_corner_orientation( FT_Pos in_x, |
856 FT_Pos in_y, | 777 FT_Pos in_y, |
857 FT_Pos out_x, | 778 FT_Pos out_x, |
858 FT_Pos out_y ) | 779 FT_Pos out_y ) |
859 { | 780 { |
860 FT_Long result; /* avoid overflow on 16-bit system */ | 781 FT_Long result; /* avoid overflow on 16-bit system */ |
(...skipping 69 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
930 | 851 |
931 | 852 |
932 /* documentation is in ftcalc.h */ | 853 /* documentation is in ftcalc.h */ |
933 | 854 |
934 FT_BASE_DEF( FT_Int ) | 855 FT_BASE_DEF( FT_Int ) |
935 ft_corner_is_flat( FT_Pos in_x, | 856 ft_corner_is_flat( FT_Pos in_x, |
936 FT_Pos in_y, | 857 FT_Pos in_y, |
937 FT_Pos out_x, | 858 FT_Pos out_x, |
938 FT_Pos out_y ) | 859 FT_Pos out_y ) |
939 { | 860 { |
940 FT_Pos ax = in_x; | 861 FT_Pos ax = in_x + out_x; |
941 FT_Pos ay = in_y; | 862 FT_Pos ay = in_y + out_y; |
942 | 863 |
943 FT_Pos d_in, d_out, d_corner; | 864 FT_Pos d_in, d_out, d_hypot; |
944 | 865 |
945 | 866 |
946 if ( ax < 0 ) | 867 /* The idea of this function is to compare the length of the */ |
947 ax = -ax; | 868 /* hypotenuse with the `in' and `out' length. The `corner' */ |
948 if ( ay < 0 ) | 869 /* represented by `in' and `out' is flat if the hypotenuse's */ |
949 ay = -ay; | 870 /* length isn't too large. */ |
950 d_in = ax + ay; | 871 /* */ |
| 872 /* This approach has the advantage that the angle between */ |
| 873 /* `in' and `out' is not checked. In case one of the two */ |
| 874 /* vectors is `dominant', this is, much larger than the */ |
| 875 /* other vector, we thus always have a flat corner. */ |
| 876 /* */ |
| 877 /* hypotenuse */ |
| 878 /* x---------------------------x */ |
| 879 /* \ / */ |
| 880 /* \ / */ |
| 881 /* in \ / out */ |
| 882 /* \ / */ |
| 883 /* o */ |
| 884 /* Point */ |
951 | 885 |
952 ax = out_x; | 886 d_in = FT_HYPOT( in_x, in_y ); |
953 if ( ax < 0 ) | 887 d_out = FT_HYPOT( out_x, out_y ); |
954 ax = -ax; | 888 d_hypot = FT_HYPOT( ax, ay ); |
955 ay = out_y; | |
956 if ( ay < 0 ) | |
957 ay = -ay; | |
958 d_out = ax + ay; | |
959 | 889 |
960 ax = out_x + in_x; | 890 /* now do a simple length comparison: */ |
961 if ( ax < 0 ) | 891 /* */ |
962 ax = -ax; | 892 /* d_in + d_out < 17/16 d_hypot */ |
963 ay = out_y + in_y; | |
964 if ( ay < 0 ) | |
965 ay = -ay; | |
966 d_corner = ax + ay; | |
967 | 893 |
968 return ( d_in + d_out - d_corner ) < ( d_corner >> 4 ); | 894 return ( d_in + d_out - d_hypot ) < ( d_hypot >> 4 ); |
969 } | 895 } |
970 | 896 |
971 | 897 |
972 /* END */ | 898 /* END */ |
OLD | NEW |