Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
3918 | Serge | 1 | /***************************************************************************/ |
2 | /* */ |
||
3 | /* ftcalc.c */ |
||
4 | /* */ |
||
5 | /* Arithmetic computations (body). */ |
||
6 | /* */ |
||
7 | /* Copyright 1996-2006, 2008, 2012-2013 by */ |
||
8 | /* David Turner, Robert Wilhelm, and Werner Lemberg. */ |
||
9 | /* */ |
||
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 */ |
||
12 | /* license, LICENSE.TXT. By continuing to use, modify, or distribute */ |
||
13 | /* this file you indicate that you have read the license and */ |
||
14 | /* understand and accept it fully. */ |
||
15 | /* */ |
||
16 | /***************************************************************************/ |
||
17 | |||
18 | /*************************************************************************/ |
||
19 | /* */ |
||
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. */ |
||
22 | /* */ |
||
23 | /*************************************************************************/ |
||
24 | |||
25 | /*************************************************************************/ |
||
26 | /* */ |
||
27 | /* Implementing basic computation routines. */ |
||
28 | /* */ |
||
29 | /* FT_MulDiv(), FT_MulFix(), FT_DivFix(), FT_RoundFix(), FT_CeilFix(), */ |
||
30 | /* and FT_FloorFix() are declared in freetype.h. */ |
||
31 | /* */ |
||
32 | /*************************************************************************/ |
||
33 | |||
34 | |||
35 | #include |
||
36 | #include FT_GLYPH_H |
||
37 | #include FT_TRIGONOMETRY_H |
||
38 | #include FT_INTERNAL_CALC_H |
||
39 | #include FT_INTERNAL_DEBUG_H |
||
40 | #include FT_INTERNAL_OBJECTS_H |
||
41 | |||
42 | #ifdef FT_MULFIX_INLINED |
||
43 | #undef FT_MulFix |
||
44 | #endif |
||
45 | |||
46 | /* we need to emulate a 64-bit data type if a real one isn't available */ |
||
47 | |||
48 | #ifndef FT_LONG64 |
||
49 | |||
50 | typedef struct FT_Int64_ |
||
51 | { |
||
52 | FT_UInt32 lo; |
||
53 | FT_UInt32 hi; |
||
54 | |||
55 | } FT_Int64; |
||
56 | |||
57 | #endif /* !FT_LONG64 */ |
||
58 | |||
59 | |||
60 | /*************************************************************************/ |
||
61 | /* */ |
||
62 | /* The macro FT_COMPONENT is used in trace mode. It is an implicit */ |
||
63 | /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */ |
||
64 | /* messages during execution. */ |
||
65 | /* */ |
||
66 | #undef FT_COMPONENT |
||
67 | #define FT_COMPONENT trace_calc |
||
68 | |||
69 | |||
70 | /* The following three functions are available regardless of whether */ |
||
71 | /* FT_LONG64 is defined. */ |
||
72 | |||
73 | /* documentation is in freetype.h */ |
||
74 | |||
75 | FT_EXPORT_DEF( FT_Fixed ) |
||
76 | FT_RoundFix( FT_Fixed a ) |
||
77 | { |
||
78 | return ( a >= 0 ) ? ( a + 0x8000L ) & ~0xFFFFL |
||
79 | : -((-a + 0x8000L ) & ~0xFFFFL ); |
||
80 | } |
||
81 | |||
82 | |||
83 | /* documentation is in freetype.h */ |
||
84 | |||
85 | FT_EXPORT_DEF( FT_Fixed ) |
||
86 | FT_CeilFix( FT_Fixed a ) |
||
87 | { |
||
88 | return ( a >= 0 ) ? ( a + 0xFFFFL ) & ~0xFFFFL |
||
89 | : -((-a + 0xFFFFL ) & ~0xFFFFL ); |
||
90 | } |
||
91 | |||
92 | |||
93 | /* documentation is in freetype.h */ |
||
94 | |||
95 | FT_EXPORT_DEF( FT_Fixed ) |
||
96 | FT_FloorFix( FT_Fixed a ) |
||
97 | { |
||
98 | return ( a >= 0 ) ? a & ~0xFFFFL |
||
99 | : -((-a) & ~0xFFFFL ); |
||
100 | } |
||
101 | |||
102 | |||
103 | FT_BASE_DEF ( FT_Int ) |
||
104 | FT_MSB( FT_UInt32 z ) |
||
105 | { |
||
106 | FT_Int shift = 0; |
||
107 | |||
108 | /* determine msb bit index in `shift' */ |
||
109 | if ( z >= ( 1L << 16 ) ) |
||
110 | { |
||
111 | z >>= 16; |
||
112 | shift += 16; |
||
113 | } |
||
114 | if ( z >= ( 1L << 8 ) ) |
||
115 | { |
||
116 | z >>= 8; |
||
117 | shift += 8; |
||
118 | } |
||
119 | if ( z >= ( 1L << 4 ) ) |
||
120 | { |
||
121 | z >>= 4; |
||
122 | shift += 4; |
||
123 | } |
||
124 | if ( z >= ( 1L << 2 ) ) |
||
125 | { |
||
126 | z >>= 2; |
||
127 | shift += 2; |
||
128 | } |
||
129 | if ( z >= ( 1L << 1 ) ) |
||
130 | { |
||
131 | z >>= 1; |
||
132 | shift += 1; |
||
133 | } |
||
134 | |||
135 | return shift; |
||
136 | } |
||
137 | |||
138 | |||
139 | /* documentation is in ftcalc.h */ |
||
140 | |||
141 | FT_BASE_DEF( FT_Fixed ) |
||
142 | FT_Hypot( FT_Fixed x, |
||
143 | FT_Fixed y ) |
||
144 | { |
||
145 | FT_Vector v; |
||
146 | |||
147 | |||
148 | v.x = x; |
||
149 | v.y = y; |
||
150 | |||
151 | return FT_Vector_Length( &v ); |
||
152 | } |
||
153 | |||
154 | |||
155 | #ifdef FT_LONG64 |
||
156 | |||
157 | |||
158 | /* documentation is in freetype.h */ |
||
159 | |||
160 | FT_EXPORT_DEF( FT_Long ) |
||
161 | FT_MulDiv( FT_Long a, |
||
162 | FT_Long b, |
||
163 | FT_Long c ) |
||
164 | { |
||
165 | FT_Int s; |
||
166 | FT_Long d; |
||
167 | |||
168 | |||
169 | s = 1; |
||
170 | if ( a < 0 ) { a = -a; s = -1; } |
||
171 | if ( b < 0 ) { b = -b; s = -s; } |
||
172 | if ( c < 0 ) { c = -c; s = -s; } |
||
173 | |||
174 | d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c |
||
175 | : 0x7FFFFFFFL ); |
||
176 | |||
177 | return ( s > 0 ) ? d : -d; |
||
178 | } |
||
179 | |||
180 | |||
181 | /* documentation is in ftcalc.h */ |
||
182 | |||
183 | FT_BASE_DEF( FT_Long ) |
||
184 | FT_MulDiv_No_Round( FT_Long a, |
||
185 | FT_Long b, |
||
186 | FT_Long c ) |
||
187 | { |
||
188 | FT_Int s; |
||
189 | FT_Long d; |
||
190 | |||
191 | |||
192 | s = 1; |
||
193 | if ( a < 0 ) { a = -a; s = -1; } |
||
194 | if ( b < 0 ) { b = -b; s = -s; } |
||
195 | if ( c < 0 ) { c = -c; s = -s; } |
||
196 | |||
197 | d = (FT_Long)( c > 0 ? (FT_Int64)a * b / c |
||
198 | : 0x7FFFFFFFL ); |
||
199 | |||
200 | return ( s > 0 ) ? d : -d; |
||
201 | } |
||
202 | |||
203 | |||
204 | /* documentation is in freetype.h */ |
||
205 | |||
206 | FT_EXPORT_DEF( FT_Long ) |
||
207 | FT_MulFix( FT_Long a, |
||
208 | FT_Long b ) |
||
209 | { |
||
210 | #ifdef FT_MULFIX_ASSEMBLER |
||
211 | |||
212 | return FT_MULFIX_ASSEMBLER( a, b ); |
||
213 | |||
214 | #else |
||
215 | |||
216 | FT_Int s = 1; |
||
217 | FT_Long c; |
||
218 | |||
219 | |||
220 | if ( a < 0 ) |
||
221 | { |
||
222 | a = -a; |
||
223 | s = -1; |
||
224 | } |
||
225 | |||
226 | if ( b < 0 ) |
||
227 | { |
||
228 | b = -b; |
||
229 | s = -s; |
||
230 | } |
||
231 | |||
232 | c = (FT_Long)( ( (FT_Int64)a * b + 0x8000L ) >> 16 ); |
||
233 | |||
234 | return ( s > 0 ) ? c : -c; |
||
235 | |||
236 | #endif /* FT_MULFIX_ASSEMBLER */ |
||
237 | } |
||
238 | |||
239 | |||
240 | /* documentation is in freetype.h */ |
||
241 | |||
242 | FT_EXPORT_DEF( FT_Long ) |
||
243 | FT_DivFix( FT_Long a, |
||
244 | FT_Long b ) |
||
245 | { |
||
246 | FT_Int32 s; |
||
247 | FT_UInt32 q; |
||
248 | |||
249 | |||
250 | s = 1; |
||
251 | if ( a < 0 ) |
||
252 | { |
||
253 | a = -a; |
||
254 | s = -1; |
||
255 | } |
||
256 | if ( b < 0 ) |
||
257 | { |
||
258 | b = -b; |
||
259 | s = -s; |
||
260 | } |
||
261 | |||
262 | if ( b == 0 ) |
||
263 | /* check for division by 0 */ |
||
264 | q = 0x7FFFFFFFL; |
||
265 | else |
||
266 | /* compute result directly */ |
||
267 | q = (FT_UInt32)( ( ( (FT_UInt64)a << 16 ) + ( b >> 1 ) ) / b ); |
||
268 | |||
269 | return ( s < 0 ? -(FT_Long)q : (FT_Long)q ); |
||
270 | } |
||
271 | |||
272 | |||
273 | #else /* !FT_LONG64 */ |
||
274 | |||
275 | |||
276 | static void |
||
277 | ft_multo64( FT_UInt32 x, |
||
278 | FT_UInt32 y, |
||
279 | FT_Int64 *z ) |
||
280 | { |
||
281 | FT_UInt32 lo1, hi1, lo2, hi2, lo, hi, i1, i2; |
||
282 | |||
283 | |||
284 | lo1 = x & 0x0000FFFFU; hi1 = x >> 16; |
||
285 | lo2 = y & 0x0000FFFFU; hi2 = y >> 16; |
||
286 | |||
287 | lo = lo1 * lo2; |
||
288 | i1 = lo1 * hi2; |
||
289 | i2 = lo2 * hi1; |
||
290 | hi = hi1 * hi2; |
||
291 | |||
292 | /* Check carry overflow of i1 + i2 */ |
||
293 | i1 += i2; |
||
294 | hi += (FT_UInt32)( i1 < i2 ) << 16; |
||
295 | |||
296 | hi += i1 >> 16; |
||
297 | i1 = i1 << 16; |
||
298 | |||
299 | /* Check carry overflow of i1 + lo */ |
||
300 | lo += i1; |
||
301 | hi += ( lo < i1 ); |
||
302 | |||
303 | z->lo = lo; |
||
304 | z->hi = hi; |
||
305 | } |
||
306 | |||
307 | |||
308 | static FT_UInt32 |
||
309 | ft_div64by32( FT_UInt32 hi, |
||
310 | FT_UInt32 lo, |
||
311 | FT_UInt32 y ) |
||
312 | { |
||
313 | FT_UInt32 r, q; |
||
314 | FT_Int i; |
||
315 | |||
316 | |||
317 | q = 0; |
||
318 | r = hi; |
||
319 | |||
320 | if ( r >= y ) |
||
321 | return (FT_UInt32)0x7FFFFFFFL; |
||
322 | |||
323 | i = 32; |
||
324 | do |
||
325 | { |
||
326 | r <<= 1; |
||
327 | q <<= 1; |
||
328 | r |= lo >> 31; |
||
329 | |||
330 | if ( r >= y ) |
||
331 | { |
||
332 | r -= y; |
||
333 | q |= 1; |
||
334 | } |
||
335 | lo <<= 1; |
||
336 | } while ( --i ); |
||
337 | |||
338 | return q; |
||
339 | } |
||
340 | |||
341 | |||
342 | static void |
||
343 | FT_Add64( FT_Int64* x, |
||
344 | FT_Int64* y, |
||
345 | FT_Int64 *z ) |
||
346 | { |
||
347 | register FT_UInt32 lo, hi; |
||
348 | |||
349 | |||
350 | lo = x->lo + y->lo; |
||
351 | hi = x->hi + y->hi + ( lo < x->lo ); |
||
352 | |||
353 | z->lo = lo; |
||
354 | z->hi = hi; |
||
355 | } |
||
356 | |||
357 | |||
358 | /* documentation is in freetype.h */ |
||
359 | |||
360 | /* The FT_MulDiv function has been optimized thanks to ideas from */ |
||
361 | /* Graham Asher. The trick is to optimize computation when everything */ |
||
362 | /* fits within 32-bits (a rather common case). */ |
||
363 | /* */ |
||
364 | /* we compute 'a*b+c/2', then divide it by 'c'. (positive values) */ |
||
365 | /* */ |
||
366 | /* 46340 is FLOOR(SQRT(2^31-1)). */ |
||
367 | /* */ |
||
368 | /* if ( a <= 46340 && b <= 46340 ) then ( a*b <= 0x7FFEA810 ) */ |
||
369 | /* */ |
||
370 | /* 0x7FFFFFFF - 0x7FFEA810 = 0x157F0 */ |
||
371 | /* */ |
||
372 | /* if ( c < 0x157F0*2 ) then ( a*b+c/2 <= 0x7FFFFFFF ) */ |
||
373 | /* */ |
||
374 | /* and 2*0x157F0 = 176096 */ |
||
375 | /* */ |
||
376 | |||
377 | FT_EXPORT_DEF( FT_Long ) |
||
378 | FT_MulDiv( FT_Long a, |
||
379 | FT_Long b, |
||
380 | FT_Long c ) |
||
381 | { |
||
382 | long s; |
||
383 | |||
384 | |||
385 | /* XXX: this function does not allow 64-bit arguments */ |
||
386 | if ( a == 0 || b == c ) |
||
387 | return a; |
||
388 | |||
389 | s = a; a = FT_ABS( a ); |
||
390 | s ^= b; b = FT_ABS( b ); |
||
391 | s ^= c; c = FT_ABS( c ); |
||
392 | |||
393 | if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 ) |
||
394 | a = ( a * b + ( c >> 1 ) ) / c; |
||
395 | |||
396 | else if ( (FT_Int32)c > 0 ) |
||
397 | { |
||
398 | FT_Int64 temp, temp2; |
||
399 | |||
400 | |||
401 | ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp ); |
||
402 | |||
403 | temp2.hi = 0; |
||
404 | temp2.lo = (FT_UInt32)(c >> 1); |
||
405 | FT_Add64( &temp, &temp2, &temp ); |
||
406 | a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c ); |
||
407 | } |
||
408 | else |
||
409 | a = 0x7FFFFFFFL; |
||
410 | |||
411 | return ( s < 0 ? -a : a ); |
||
412 | } |
||
413 | |||
414 | |||
415 | FT_BASE_DEF( FT_Long ) |
||
416 | FT_MulDiv_No_Round( FT_Long a, |
||
417 | FT_Long b, |
||
418 | FT_Long c ) |
||
419 | { |
||
420 | long s; |
||
421 | |||
422 | |||
423 | if ( a == 0 || b == c ) |
||
424 | return a; |
||
425 | |||
426 | s = a; a = FT_ABS( a ); |
||
427 | s ^= b; b = FT_ABS( b ); |
||
428 | s ^= c; c = FT_ABS( c ); |
||
429 | |||
430 | if ( a <= 46340L && b <= 46340L && c > 0 ) |
||
431 | a = a * b / c; |
||
432 | |||
433 | else if ( (FT_Int32)c > 0 ) |
||
434 | { |
||
435 | FT_Int64 temp; |
||
436 | |||
437 | |||
438 | ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp ); |
||
439 | a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c ); |
||
440 | } |
||
441 | else |
||
442 | a = 0x7FFFFFFFL; |
||
443 | |||
444 | return ( s < 0 ? -a : a ); |
||
445 | } |
||
446 | |||
447 | |||
448 | /* documentation is in freetype.h */ |
||
449 | |||
450 | FT_EXPORT_DEF( FT_Long ) |
||
451 | FT_MulFix( FT_Long a, |
||
452 | FT_Long b ) |
||
453 | { |
||
454 | #ifdef FT_MULFIX_ASSEMBLER |
||
455 | |||
456 | return FT_MULFIX_ASSEMBLER( a, b ); |
||
457 | |||
458 | #elif 0 |
||
459 | |||
460 | /* |
||
461 | * This code is nonportable. See comment below. |
||
462 | * |
||
463 | * However, on a platform where right-shift of a signed quantity fills |
||
464 | * the leftmost bits by copying the sign bit, it might be faster. |
||
465 | */ |
||
466 | |||
467 | FT_Long sa, sb; |
||
468 | FT_ULong ua, ub; |
||
469 | |||
470 | |||
471 | if ( a == 0 || b == 0x10000L ) |
||
472 | return a; |
||
473 | |||
474 | /* |
||
475 | * This is a clever way of converting a signed number `a' into its |
||
476 | * absolute value (stored back into `a') and its sign. The sign is |
||
477 | * stored in `sa'; 0 means `a' was positive or zero, and -1 means `a' |
||
478 | * was negative. (Similarly for `b' and `sb'). |
||
479 | * |
||
480 | * Unfortunately, it doesn't work (at least not portably). |
||
481 | * |
||
482 | * It makes the assumption that right-shift on a negative signed value |
||
483 | * fills the leftmost bits by copying the sign bit. This is wrong. |
||
484 | * According to K&R 2nd ed, section `A7.8 Shift Operators' on page 206, |
||
485 | * the result of right-shift of a negative signed value is |
||
486 | * implementation-defined. At least one implementation fills the |
||
487 | * leftmost bits with 0s (i.e., it is exactly the same as an unsigned |
||
488 | * right shift). This means that when `a' is negative, `sa' ends up |
||
489 | * with the value 1 rather than -1. After that, everything else goes |
||
490 | * wrong. |
||
491 | */ |
||
492 | sa = ( a >> ( sizeof ( a ) * 8 - 1 ) ); |
||
493 | a = ( a ^ sa ) - sa; |
||
494 | sb = ( b >> ( sizeof ( b ) * 8 - 1 ) ); |
||
495 | b = ( b ^ sb ) - sb; |
||
496 | |||
497 | ua = (FT_ULong)a; |
||
498 | ub = (FT_ULong)b; |
||
499 | |||
500 | if ( ua <= 2048 && ub <= 1048576L ) |
||
501 | ua = ( ua * ub + 0x8000U ) >> 16; |
||
502 | else |
||
503 | { |
||
504 | FT_ULong al = ua & 0xFFFFU; |
||
505 | |||
506 | |||
507 | ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + |
||
508 | ( ( al * ( ub & 0xFFFFU ) + 0x8000U ) >> 16 ); |
||
509 | } |
||
510 | |||
511 | sa ^= sb, |
||
512 | ua = (FT_ULong)(( ua ^ sa ) - sa); |
||
513 | |||
514 | return (FT_Long)ua; |
||
515 | |||
516 | #else /* 0 */ |
||
517 | |||
518 | FT_Long s; |
||
519 | FT_ULong ua, ub; |
||
520 | |||
521 | |||
522 | if ( a == 0 || b == 0x10000L ) |
||
523 | return a; |
||
524 | |||
525 | s = a; a = FT_ABS( a ); |
||
526 | s ^= b; b = FT_ABS( b ); |
||
527 | |||
528 | ua = (FT_ULong)a; |
||
529 | ub = (FT_ULong)b; |
||
530 | |||
531 | if ( ua <= 2048 && ub <= 1048576L ) |
||
532 | ua = ( ua * ub + 0x8000UL ) >> 16; |
||
533 | else |
||
534 | { |
||
535 | FT_ULong al = ua & 0xFFFFUL; |
||
536 | |||
537 | |||
538 | ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + |
||
539 | ( ( al * ( ub & 0xFFFFUL ) + 0x8000UL ) >> 16 ); |
||
540 | } |
||
541 | |||
542 | return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua ); |
||
543 | |||
544 | #endif /* 0 */ |
||
545 | |||
546 | } |
||
547 | |||
548 | |||
549 | /* documentation is in freetype.h */ |
||
550 | |||
551 | FT_EXPORT_DEF( FT_Long ) |
||
552 | FT_DivFix( FT_Long a, |
||
553 | FT_Long b ) |
||
554 | { |
||
555 | FT_Int32 s; |
||
556 | FT_UInt32 q; |
||
557 | |||
558 | |||
559 | /* XXX: this function does not allow 64-bit arguments */ |
||
560 | s = (FT_Int32)a; a = FT_ABS( a ); |
||
561 | s ^= (FT_Int32)b; b = FT_ABS( b ); |
||
562 | |||
563 | if ( (FT_UInt32)b == 0 ) |
||
564 | { |
||
565 | /* check for division by 0 */ |
||
566 | q = (FT_UInt32)0x7FFFFFFFL; |
||
567 | } |
||
568 | else if ( ( a >> 16 ) == 0 ) |
||
569 | { |
||
570 | /* compute result directly */ |
||
571 | q = (FT_UInt32)( ( (FT_ULong)a << 16 ) + ( b >> 1 ) ) / (FT_UInt32)b; |
||
572 | } |
||
573 | else |
||
574 | { |
||
575 | /* we need more bits; we have to do it by hand */ |
||
576 | FT_Int64 temp, temp2; |
||
577 | |||
578 | |||
579 | temp.hi = (FT_Int32)( a >> 16 ); |
||
580 | temp.lo = (FT_UInt32)a << 16; |
||
581 | temp2.hi = 0; |
||
582 | temp2.lo = (FT_UInt32)( b >> 1 ); |
||
583 | FT_Add64( &temp, &temp2, &temp ); |
||
584 | q = ft_div64by32( temp.hi, temp.lo, (FT_Int32)b ); |
||
585 | } |
||
586 | |||
587 | return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); |
||
588 | } |
||
589 | |||
590 | |||
591 | #if 0 |
||
592 | |||
593 | /* documentation is in ftcalc.h */ |
||
594 | |||
595 | FT_EXPORT_DEF( void ) |
||
596 | FT_MulTo64( FT_Int32 x, |
||
597 | FT_Int32 y, |
||
598 | FT_Int64 *z ) |
||
599 | { |
||
600 | FT_Int32 s; |
||
601 | |||
602 | |||
603 | s = x; x = FT_ABS( x ); |
||
604 | s ^= y; y = FT_ABS( y ); |
||
605 | |||
606 | ft_multo64( x, y, z ); |
||
607 | |||
608 | if ( s < 0 ) |
||
609 | { |
||
610 | z->lo = (FT_UInt32)-(FT_Int32)z->lo; |
||
611 | z->hi = ~z->hi + !( z->lo ); |
||
612 | } |
||
613 | } |
||
614 | |||
615 | |||
616 | /* apparently, the second version of this code is not compiled correctly */ |
||
617 | /* on Mac machines with the MPW C compiler.. tsk, tsk, tsk... */ |
||
618 | |||
619 | #if 1 |
||
620 | |||
621 | FT_EXPORT_DEF( FT_Int32 ) |
||
622 | FT_Div64by32( FT_Int64* x, |
||
623 | FT_Int32 y ) |
||
624 | { |
||
625 | FT_Int32 s; |
||
626 | FT_UInt32 q, r, i, lo; |
||
627 | |||
628 | |||
629 | s = x->hi; |
||
630 | if ( s < 0 ) |
||
631 | { |
||
632 | x->lo = (FT_UInt32)-(FT_Int32)x->lo; |
||
633 | x->hi = ~x->hi + !x->lo; |
||
634 | } |
||
635 | s ^= y; y = FT_ABS( y ); |
||
636 | |||
637 | /* Shortcut */ |
||
638 | if ( x->hi == 0 ) |
||
639 | { |
||
640 | if ( y > 0 ) |
||
641 | q = x->lo / y; |
||
642 | else |
||
643 | q = 0x7FFFFFFFL; |
||
644 | |||
645 | return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); |
||
646 | } |
||
647 | |||
648 | r = x->hi; |
||
649 | lo = x->lo; |
||
650 | |||
651 | if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */ |
||
652 | return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL ); |
||
653 | /* Return Max/Min Int32 if division overflow. */ |
||
654 | /* This includes division by zero! */ |
||
655 | q = 0; |
||
656 | for ( i = 0; i < 32; i++ ) |
||
657 | { |
||
658 | r <<= 1; |
||
659 | q <<= 1; |
||
660 | r |= lo >> 31; |
||
661 | |||
662 | if ( r >= (FT_UInt32)y ) |
||
663 | { |
||
664 | r -= y; |
||
665 | q |= 1; |
||
666 | } |
||
667 | lo <<= 1; |
||
668 | } |
||
669 | |||
670 | return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); |
||
671 | } |
||
672 | |||
673 | #else /* 0 */ |
||
674 | |||
675 | FT_EXPORT_DEF( FT_Int32 ) |
||
676 | FT_Div64by32( FT_Int64* x, |
||
677 | FT_Int32 y ) |
||
678 | { |
||
679 | FT_Int32 s; |
||
680 | FT_UInt32 q; |
||
681 | |||
682 | |||
683 | s = x->hi; |
||
684 | if ( s < 0 ) |
||
685 | { |
||
686 | x->lo = (FT_UInt32)-(FT_Int32)x->lo; |
||
687 | x->hi = ~x->hi + !x->lo; |
||
688 | } |
||
689 | s ^= y; y = FT_ABS( y ); |
||
690 | |||
691 | /* Shortcut */ |
||
692 | if ( x->hi == 0 ) |
||
693 | { |
||
694 | if ( y > 0 ) |
||
695 | q = ( x->lo + ( y >> 1 ) ) / y; |
||
696 | else |
||
697 | q = 0x7FFFFFFFL; |
||
698 | |||
699 | return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); |
||
700 | } |
||
701 | |||
702 | q = ft_div64by32( x->hi, x->lo, y ); |
||
703 | |||
704 | return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); |
||
705 | } |
||
706 | |||
707 | #endif /* 0 */ |
||
708 | |||
709 | #endif /* 0 */ |
||
710 | |||
711 | |||
712 | #endif /* FT_LONG64 */ |
||
713 | |||
714 | |||
715 | /* documentation is in ftglyph.h */ |
||
716 | |||
717 | FT_EXPORT_DEF( void ) |
||
718 | FT_Matrix_Multiply( const FT_Matrix* a, |
||
719 | FT_Matrix *b ) |
||
720 | { |
||
721 | FT_Fixed xx, xy, yx, yy; |
||
722 | |||
723 | |||
724 | if ( !a || !b ) |
||
725 | return; |
||
726 | |||
727 | xx = FT_MulFix( a->xx, b->xx ) + FT_MulFix( a->xy, b->yx ); |
||
728 | xy = FT_MulFix( a->xx, b->xy ) + FT_MulFix( a->xy, b->yy ); |
||
729 | yx = FT_MulFix( a->yx, b->xx ) + FT_MulFix( a->yy, b->yx ); |
||
730 | yy = FT_MulFix( a->yx, b->xy ) + FT_MulFix( a->yy, b->yy ); |
||
731 | |||
732 | b->xx = xx; b->xy = xy; |
||
733 | b->yx = yx; b->yy = yy; |
||
734 | } |
||
735 | |||
736 | |||
737 | /* documentation is in ftglyph.h */ |
||
738 | |||
739 | FT_EXPORT_DEF( FT_Error ) |
||
740 | FT_Matrix_Invert( FT_Matrix* matrix ) |
||
741 | { |
||
742 | FT_Pos delta, xx, yy; |
||
743 | |||
744 | |||
745 | if ( !matrix ) |
||
746 | return FT_THROW( Invalid_Argument ); |
||
747 | |||
748 | /* compute discriminant */ |
||
749 | delta = FT_MulFix( matrix->xx, matrix->yy ) - |
||
750 | FT_MulFix( matrix->xy, matrix->yx ); |
||
751 | |||
752 | if ( !delta ) |
||
753 | return FT_THROW( Invalid_Argument ); /* matrix can't be inverted */ |
||
754 | |||
755 | matrix->xy = - FT_DivFix( matrix->xy, delta ); |
||
756 | matrix->yx = - FT_DivFix( matrix->yx, delta ); |
||
757 | |||
758 | xx = matrix->xx; |
||
759 | yy = matrix->yy; |
||
760 | |||
761 | matrix->xx = FT_DivFix( yy, delta ); |
||
762 | matrix->yy = FT_DivFix( xx, delta ); |
||
763 | |||
764 | return FT_Err_Ok; |
||
765 | } |
||
766 | |||
767 | |||
768 | /* documentation is in ftcalc.h */ |
||
769 | |||
770 | FT_BASE_DEF( void ) |
||
771 | FT_Matrix_Multiply_Scaled( const FT_Matrix* a, |
||
772 | FT_Matrix *b, |
||
773 | FT_Long scaling ) |
||
774 | { |
||
775 | FT_Fixed xx, xy, yx, yy; |
||
776 | |||
777 | FT_Long val = 0x10000L * scaling; |
||
778 | |||
779 | |||
780 | if ( !a || !b ) |
||
781 | return; |
||
782 | |||
783 | xx = FT_MulDiv( a->xx, b->xx, val ) + FT_MulDiv( a->xy, b->yx, val ); |
||
784 | xy = FT_MulDiv( a->xx, b->xy, val ) + FT_MulDiv( a->xy, b->yy, val ); |
||
785 | yx = FT_MulDiv( a->yx, b->xx, val ) + FT_MulDiv( a->yy, b->yx, val ); |
||
786 | yy = FT_MulDiv( a->yx, b->xy, val ) + FT_MulDiv( a->yy, b->yy, val ); |
||
787 | |||
788 | b->xx = xx; b->xy = xy; |
||
789 | b->yx = yx; b->yy = yy; |
||
790 | } |
||
791 | |||
792 | |||
793 | /* documentation is in ftcalc.h */ |
||
794 | |||
795 | FT_BASE_DEF( void ) |
||
796 | FT_Vector_Transform_Scaled( FT_Vector* vector, |
||
797 | const FT_Matrix* matrix, |
||
798 | FT_Long scaling ) |
||
799 | { |
||
800 | FT_Pos xz, yz; |
||
801 | |||
802 | FT_Long val = 0x10000L * scaling; |
||
803 | |||
804 | |||
805 | if ( !vector || !matrix ) |
||
806 | return; |
||
807 | |||
808 | xz = FT_MulDiv( vector->x, matrix->xx, val ) + |
||
809 | FT_MulDiv( vector->y, matrix->xy, val ); |
||
810 | |||
811 | yz = FT_MulDiv( vector->x, matrix->yx, val ) + |
||
812 | FT_MulDiv( vector->y, matrix->yy, val ); |
||
813 | |||
814 | vector->x = xz; |
||
815 | vector->y = yz; |
||
816 | } |
||
817 | |||
818 | |||
819 | /* documentation is in ftcalc.h */ |
||
820 | |||
821 | FT_BASE_DEF( FT_Int32 ) |
||
822 | FT_SqrtFixed( FT_Int32 x ) |
||
823 | { |
||
824 | FT_UInt32 root, rem_hi, rem_lo, test_div; |
||
825 | FT_Int count; |
||
826 | |||
827 | |||
828 | root = 0; |
||
829 | |||
830 | if ( x > 0 ) |
||
831 | { |
||
832 | rem_hi = 0; |
||
833 | rem_lo = x; |
||
834 | count = 24; |
||
835 | do |
||
836 | { |
||
837 | rem_hi = ( rem_hi << 2 ) | ( rem_lo >> 30 ); |
||
838 | rem_lo <<= 2; |
||
839 | root <<= 1; |
||
840 | test_div = ( root << 1 ) + 1; |
||
841 | |||
842 | if ( rem_hi >= test_div ) |
||
843 | { |
||
844 | rem_hi -= test_div; |
||
845 | root += 1; |
||
846 | } |
||
847 | } while ( --count ); |
||
848 | } |
||
849 | |||
850 | return (FT_Int32)root; |
||
851 | } |
||
852 | |||
853 | |||
854 | /* documentation is in ftcalc.h */ |
||
855 | |||
856 | FT_BASE_DEF( FT_Int ) |
||
857 | ft_corner_orientation( FT_Pos in_x, |
||
858 | FT_Pos in_y, |
||
859 | FT_Pos out_x, |
||
860 | FT_Pos out_y ) |
||
861 | { |
||
862 | FT_Long result; /* avoid overflow on 16-bit system */ |
||
863 | |||
864 | |||
865 | /* deal with the trivial cases quickly */ |
||
866 | if ( in_y == 0 ) |
||
867 | { |
||
868 | if ( in_x >= 0 ) |
||
869 | result = out_y; |
||
870 | else |
||
871 | result = -out_y; |
||
872 | } |
||
873 | else if ( in_x == 0 ) |
||
874 | { |
||
875 | if ( in_y >= 0 ) |
||
876 | result = -out_x; |
||
877 | else |
||
878 | result = out_x; |
||
879 | } |
||
880 | else if ( out_y == 0 ) |
||
881 | { |
||
882 | if ( out_x >= 0 ) |
||
883 | result = in_y; |
||
884 | else |
||
885 | result = -in_y; |
||
886 | } |
||
887 | else if ( out_x == 0 ) |
||
888 | { |
||
889 | if ( out_y >= 0 ) |
||
890 | result = -in_x; |
||
891 | else |
||
892 | result = in_x; |
||
893 | } |
||
894 | else /* general case */ |
||
895 | { |
||
896 | #ifdef FT_LONG64 |
||
897 | |||
898 | FT_Int64 delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x; |
||
899 | |||
900 | |||
901 | if ( delta == 0 ) |
||
902 | result = 0; |
||
903 | else |
||
904 | result = 1 - 2 * ( delta < 0 ); |
||
905 | |||
906 | #else |
||
907 | |||
908 | FT_Int64 z1, z2; |
||
909 | |||
910 | |||
911 | /* XXX: this function does not allow 64-bit arguments */ |
||
912 | ft_multo64( (FT_Int32)in_x, (FT_Int32)out_y, &z1 ); |
||
913 | ft_multo64( (FT_Int32)in_y, (FT_Int32)out_x, &z2 ); |
||
914 | |||
915 | if ( z1.hi > z2.hi ) |
||
916 | result = +1; |
||
917 | else if ( z1.hi < z2.hi ) |
||
918 | result = -1; |
||
919 | else if ( z1.lo > z2.lo ) |
||
920 | result = +1; |
||
921 | else if ( z1.lo < z2.lo ) |
||
922 | result = -1; |
||
923 | else |
||
924 | result = 0; |
||
925 | |||
926 | #endif |
||
927 | } |
||
928 | |||
929 | /* XXX: only the sign of return value, +1/0/-1 must be used */ |
||
930 | return (FT_Int)result; |
||
931 | } |
||
932 | |||
933 | |||
934 | /* documentation is in ftcalc.h */ |
||
935 | |||
936 | FT_BASE_DEF( FT_Int ) |
||
937 | ft_corner_is_flat( FT_Pos in_x, |
||
938 | FT_Pos in_y, |
||
939 | FT_Pos out_x, |
||
940 | FT_Pos out_y ) |
||
941 | { |
||
942 | FT_Pos ax = in_x; |
||
943 | FT_Pos ay = in_y; |
||
944 | |||
945 | FT_Pos d_in, d_out, d_corner; |
||
946 | |||
947 | |||
948 | if ( ax < 0 ) |
||
949 | ax = -ax; |
||
950 | if ( ay < 0 ) |
||
951 | ay = -ay; |
||
952 | d_in = ax + ay; |
||
953 | |||
954 | ax = out_x; |
||
955 | if ( ax < 0 ) |
||
956 | ax = -ax; |
||
957 | ay = out_y; |
||
958 | if ( ay < 0 ) |
||
959 | ay = -ay; |
||
960 | d_out = ax + ay; |
||
961 | |||
962 | ax = out_x + in_x; |
||
963 | if ( ax < 0 ) |
||
964 | ax = -ax; |
||
965 | ay = out_y + in_y; |
||
966 | if ( ay < 0 ) |
||
967 | ay = -ay; |
||
968 | d_corner = ax + ay; |
||
969 | |||
970 | return ( d_in + d_out - d_corner ) < ( d_corner >> 4 ); |
||
971 | } |
||
972 | |||
973 | |||
974 | /* END */>>>>>>>>>>><>=><=>=><=>><>>>>>=><=>=><=>=><=>>>>>>>><>><>>=>=>=>=>>=>=>>=>=>=>=>>=>=>=>>=><=>=><=>=><=>>><>><>>>><>>>>>>>>>>>><>><>><>><>><> |