Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(375)

Side by Side Diff: third_party/freetype/src/base/ftcalc.c

Issue 815103002: Update freetype to 2.5.4. (Closed) Base URL: https://pdfium.googlesource.com/pdfium.git@master
Patch Set: Adjust GYP and GN Created 6 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « third_party/freetype/src/base/ftbitmap.c ('k') | third_party/freetype/src/base/ftcid.c » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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
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
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
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
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
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 */
OLDNEW
« no previous file with comments | « third_party/freetype/src/base/ftbitmap.c ('k') | third_party/freetype/src/base/ftcid.c » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698