ReactOS 0.4.15-dev-8135-g1bc6c90
ftcalc.c
Go to the documentation of this file.
1/***************************************************************************/
2/* */
3/* ftcalc.c */
4/* */
5/* Arithmetic computations (body). */
6/* */
7/* Copyright 1996-2018 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 <ft2build.h>
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
43#ifdef FT_MULFIX_ASSEMBLER
44#undef FT_MulFix
45#endif
46
47/* we need to emulate a 64-bit data type if a real one isn't available */
48
49#ifndef FT_LONG64
50
51 typedef struct FT_Int64_
52 {
53 FT_UInt32 lo;
54 FT_UInt32 hi;
55
57
58#endif /* !FT_LONG64 */
59
60
61 /*************************************************************************/
62 /* */
63 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
64 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
65 /* messages during execution. */
66 /* */
67#undef FT_COMPONENT
68#define FT_COMPONENT trace_calc
69
70
71 /* transfer sign, leaving a positive number; */
72 /* we need an unsigned value to safely negate INT_MIN (or LONG_MIN) */
73#define FT_MOVE_SIGN( x, x_unsigned, s ) \
74 FT_BEGIN_STMNT \
75 if ( x < 0 ) \
76 { \
77 x_unsigned = 0U - (x_unsigned); \
78 s = -s; \
79 } \
80 FT_END_STMNT
81
82 /* The following three functions are available regardless of whether */
83 /* FT_LONG64 is defined. */
84
85 /* documentation is in freetype.h */
86
89 {
90 return ( ADD_LONG( a, 0x8000L - ( a < 0 ) ) ) & ~0xFFFFL;
91 }
92
93
94 /* documentation is in freetype.h */
95
98 {
99 return ( ADD_LONG( a, 0xFFFFL ) ) & ~0xFFFFL;
100 }
101
102
103 /* documentation is in freetype.h */
104
107 {
108 return a & ~0xFFFFL;
109 }
110
111#ifndef FT_MSB
112
114 FT_MSB( FT_UInt32 z )
115 {
116 FT_Int shift = 0;
117
118
119 /* determine msb bit index in `shift' */
120 if ( z & 0xFFFF0000UL )
121 {
122 z >>= 16;
123 shift += 16;
124 }
125 if ( z & 0x0000FF00UL )
126 {
127 z >>= 8;
128 shift += 8;
129 }
130 if ( z & 0x000000F0UL )
131 {
132 z >>= 4;
133 shift += 4;
134 }
135 if ( z & 0x0000000CUL )
136 {
137 z >>= 2;
138 shift += 2;
139 }
140 if ( z & 0x00000002UL )
141 {
142 /* z >>= 1; */
143 shift += 1;
144 }
145
146 return shift;
147 }
148
149#endif /* !FT_MSB */
150
151
152 /* documentation is in ftcalc.h */
153
156 FT_Fixed y )
157 {
158 FT_Vector v;
159
160
161 v.x = x;
162 v.y = y;
163
164 return FT_Vector_Length( &v );
165 }
166
167
168#ifdef FT_LONG64
169
170
171 /* documentation is in freetype.h */
172
174 FT_MulDiv( FT_Long a_,
175 FT_Long b_,
176 FT_Long c_ )
177 {
178 FT_Int s = 1;
179 FT_UInt64 a, b, c, d;
180 FT_Long d_;
181
182
183 a = (FT_UInt64)a_;
184 b = (FT_UInt64)b_;
185 c = (FT_UInt64)c_;
186
187 FT_MOVE_SIGN( a_, a, s );
188 FT_MOVE_SIGN( b_, b, s );
189 FT_MOVE_SIGN( c_, c, s );
190
191 d = c > 0 ? ( a * b + ( c >> 1 ) ) / c
192 : 0x7FFFFFFFUL;
193
194 d_ = (FT_Long)d;
195
196 return s < 0 ? NEG_LONG( d_ ) : d_;
197 }
198
199
200 /* documentation is in ftcalc.h */
201
204 FT_Long b_,
205 FT_Long c_ )
206 {
207 FT_Int s = 1;
208 FT_UInt64 a, b, c, d;
209 FT_Long d_;
210
211
212 a = (FT_UInt64)a_;
213 b = (FT_UInt64)b_;
214 c = (FT_UInt64)c_;
215
216 FT_MOVE_SIGN( a_, a, s );
217 FT_MOVE_SIGN( b_, b, s );
218 FT_MOVE_SIGN( c_, c, s );
219
220 d = c > 0 ? a * b / c
221 : 0x7FFFFFFFUL;
222
223 d_ = (FT_Long)d;
224
225 return s < 0 ? NEG_LONG( d_ ) : d_;
226 }
227
228
229 /* documentation is in freetype.h */
230
232 FT_MulFix( FT_Long a_,
233 FT_Long b_ )
234 {
235#ifdef FT_MULFIX_ASSEMBLER
236
237 return FT_MULFIX_ASSEMBLER( (FT_Int32)a_, (FT_Int32)b_ );
238
239#else
240
241 FT_Int64 ab = (FT_Int64)a_ * (FT_Int64)b_;
242
243 /* this requires arithmetic right shift of signed numbers */
244 return (FT_Long)( ( ab + 0x8000L - ( ab < 0 ) ) >> 16 );
245
246#endif /* FT_MULFIX_ASSEMBLER */
247 }
248
249
250 /* documentation is in freetype.h */
251
253 FT_DivFix( FT_Long a_,
254 FT_Long b_ )
255 {
256 FT_Int s = 1;
257 FT_UInt64 a, b, q;
258 FT_Long q_;
259
260
261 a = (FT_UInt64)a_;
262 b = (FT_UInt64)b_;
263
264 FT_MOVE_SIGN( a_, a, s );
265 FT_MOVE_SIGN( b_, b, s );
266
267 q = b > 0 ? ( ( a << 16 ) + ( b >> 1 ) ) / b
268 : 0x7FFFFFFFUL;
269
270 q_ = (FT_Long)q;
271
272 return s < 0 ? NEG_LONG( q_ ) : q_;
273 }
274
275
276#else /* !FT_LONG64 */
277
278
279 static void
280 ft_multo64( FT_UInt32 x,
281 FT_UInt32 y,
282 FT_Int64 *z )
283 {
284 FT_UInt32 lo1, hi1, lo2, hi2, lo, hi, i1, i2;
285
286
287 lo1 = x & 0x0000FFFFU; hi1 = x >> 16;
288 lo2 = y & 0x0000FFFFU; hi2 = y >> 16;
289
290 lo = lo1 * lo2;
291 i1 = lo1 * hi2;
292 i2 = lo2 * hi1;
293 hi = hi1 * hi2;
294
295 /* Check carry overflow of i1 + i2 */
296 i1 += i2;
297 hi += (FT_UInt32)( i1 < i2 ) << 16;
298
299 hi += i1 >> 16;
300 i1 = i1 << 16;
301
302 /* Check carry overflow of i1 + lo */
303 lo += i1;
304 hi += ( lo < i1 );
305
306 z->lo = lo;
307 z->hi = hi;
308 }
309
310
311 static FT_UInt32
312 ft_div64by32( FT_UInt32 hi,
313 FT_UInt32 lo,
314 FT_UInt32 y )
315 {
316 FT_UInt32 r, q;
317 FT_Int i;
318
319
320 if ( hi >= y )
321 return (FT_UInt32)0x7FFFFFFFL;
322
323 /* We shift as many bits as we can into the high register, perform */
324 /* 32-bit division with modulo there, then work through the remaining */
325 /* bits with long division. This optimization is especially noticeable */
326 /* for smaller dividends that barely use the high register. */
327
328 i = 31 - FT_MSB( hi );
329 r = ( hi << i ) | ( lo >> ( 32 - i ) ); lo <<= i; /* left 64-bit shift */
330 q = r / y;
331 r -= q * y; /* remainder */
332
333 i = 32 - i; /* bits remaining in low register */
334 do
335 {
336 q <<= 1;
337 r = ( r << 1 ) | ( lo >> 31 ); lo <<= 1;
338
339 if ( r >= y )
340 {
341 r -= y;
342 q |= 1;
343 }
344 } while ( --i );
345
346 return q;
347 }
348
349
350 static void
352 FT_Int64* y,
353 FT_Int64 *z )
354 {
355 FT_UInt32 lo, hi;
356
357
358 lo = x->lo + y->lo;
359 hi = x->hi + y->hi + ( lo < x->lo );
360
361 z->lo = lo;
362 z->hi = hi;
363 }
364
365
366 /* The FT_MulDiv function has been optimized thanks to ideas from */
367 /* Graham Asher and Alexei Podtelezhnikov. The trick is to optimize */
368 /* a rather common case when everything fits within 32-bits. */
369 /* */
370 /* We compute 'a*b+c/2', then divide it by 'c' (all positive values). */
371 /* */
372 /* The product of two positive numbers never exceeds the square of */
373 /* its mean values. Therefore, we always avoid the overflow by */
374 /* imposing */
375 /* */
376 /* (a + b) / 2 <= sqrt(X - c/2) , */
377 /* */
378 /* where X = 2^32 - 1, the maximum unsigned 32-bit value, and using */
379 /* unsigned arithmetic. Now we replace `sqrt' with a linear function */
380 /* that is smaller or equal for all values of c in the interval */
381 /* [0;X/2]; it should be equal to sqrt(X) and sqrt(3X/4) at the */
382 /* endpoints. Substituting the linear solution and explicit numbers */
383 /* we get */
384 /* */
385 /* a + b <= 131071.99 - c / 122291.84 . */
386 /* */
387 /* In practice, we should use a faster and even stronger inequality */
388 /* */
389 /* a + b <= 131071 - (c >> 16) */
390 /* */
391 /* or, alternatively, */
392 /* */
393 /* a + b <= 129894 - (c >> 17) . */
394 /* */
395 /* FT_MulFix, on the other hand, is optimized for a small value of */
396 /* the first argument, when the second argument can be much larger. */
397 /* This can be achieved by scaling the second argument and the limit */
398 /* in the above inequalities. For example, */
399 /* */
400 /* a + (b >> 8) <= (131071 >> 4) */
401 /* */
402 /* covers the practical range of use. The actual test below is a bit */
403 /* tighter to avoid the border case overflows. */
404 /* */
405 /* In the case of FT_DivFix, the exact overflow check */
406 /* */
407 /* a << 16 <= X - c/2 */
408 /* */
409 /* is scaled down by 2^16 and we use */
410 /* */
411 /* a <= 65535 - (c >> 17) . */
412
413 /* documentation is in freetype.h */
414
417 FT_Long b_,
418 FT_Long c_ )
419 {
420 FT_Int s = 1;
421 FT_UInt32 a, b, c;
422
423
424 /* XXX: this function does not allow 64-bit arguments */
425
426 a = (FT_UInt32)a_;
427 b = (FT_UInt32)b_;
428 c = (FT_UInt32)c_;
429
430 FT_MOVE_SIGN( a_, a, s );
431 FT_MOVE_SIGN( b_, b, s );
432 FT_MOVE_SIGN( c_, c, s );
433
434 if ( c == 0 )
435 a = 0x7FFFFFFFUL;
436
437 else if ( a + b <= 129894UL - ( c >> 17 ) )
438 a = ( a * b + ( c >> 1 ) ) / c;
439
440 else
441 {
442 FT_Int64 temp, temp2;
443
444
445 ft_multo64( a, b, &temp );
446
447 temp2.hi = 0;
448 temp2.lo = c >> 1;
449
450 FT_Add64( &temp, &temp2, &temp );
451
452 /* last attempt to ditch long division */
453 a = ( temp.hi == 0 ) ? temp.lo / c
454 : ft_div64by32( temp.hi, temp.lo, c );
455 }
456
457 a_ = (FT_Long)a;
458
459 return s < 0 ? NEG_LONG( a_ ) : a_;
460 }
461
462
465 FT_Long b_,
466 FT_Long c_ )
467 {
468 FT_Int s = 1;
469 FT_UInt32 a, b, c;
470
471
472 /* XXX: this function does not allow 64-bit arguments */
473
474 a = (FT_UInt32)a_;
475 b = (FT_UInt32)b_;
476 c = (FT_UInt32)c_;
477
478 FT_MOVE_SIGN( a_, a, s );
479 FT_MOVE_SIGN( b_, b, s );
480 FT_MOVE_SIGN( c_, c, s );
481
482 if ( c == 0 )
483 a = 0x7FFFFFFFUL;
484
485 else if ( a + b <= 131071UL )
486 a = a * b / c;
487
488 else
489 {
491
492
493 ft_multo64( a, b, &temp );
494
495 /* last attempt to ditch long division */
496 a = ( temp.hi == 0 ) ? temp.lo / c
497 : ft_div64by32( temp.hi, temp.lo, c );
498 }
499
500 a_ = (FT_Long)a;
501
502 return s < 0 ? NEG_LONG( a_ ) : a_;
503 }
504
505
506 /* documentation is in freetype.h */
507
510 FT_Long b_ )
511 {
512#ifdef FT_MULFIX_ASSEMBLER
513
514 return FT_MULFIX_ASSEMBLER( a_, b_ );
515
516#elif 0
517
518 /*
519 * This code is nonportable. See comment below.
520 *
521 * However, on a platform where right-shift of a signed quantity fills
522 * the leftmost bits by copying the sign bit, it might be faster.
523 */
524
525 FT_Long sa, sb;
526 FT_UInt32 a, b;
527
528
529 /*
530 * This is a clever way of converting a signed number `a' into its
531 * absolute value (stored back into `a') and its sign. The sign is
532 * stored in `sa'; 0 means `a' was positive or zero, and -1 means `a'
533 * was negative. (Similarly for `b' and `sb').
534 *
535 * Unfortunately, it doesn't work (at least not portably).
536 *
537 * It makes the assumption that right-shift on a negative signed value
538 * fills the leftmost bits by copying the sign bit. This is wrong.
539 * According to K&R 2nd ed, section `A7.8 Shift Operators' on page 206,
540 * the result of right-shift of a negative signed value is
541 * implementation-defined. At least one implementation fills the
542 * leftmost bits with 0s (i.e., it is exactly the same as an unsigned
543 * right shift). This means that when `a' is negative, `sa' ends up
544 * with the value 1 rather than -1. After that, everything else goes
545 * wrong.
546 */
547 sa = ( a_ >> ( sizeof ( a_ ) * 8 - 1 ) );
548 a = ( a_ ^ sa ) - sa;
549 sb = ( b_ >> ( sizeof ( b_ ) * 8 - 1 ) );
550 b = ( b_ ^ sb ) - sb;
551
552 a = (FT_UInt32)a_;
553 b = (FT_UInt32)b_;
554
555 if ( a + ( b >> 8 ) <= 8190UL )
556 a = ( a * b + 0x8000U ) >> 16;
557 else
558 {
559 FT_UInt32 al = a & 0xFFFFUL;
560
561
562 a = ( a >> 16 ) * b + al * ( b >> 16 ) +
563 ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 );
564 }
565
566 sa ^= sb;
567 a = ( a ^ sa ) - sa;
568
569 return (FT_Long)a;
570
571#else /* 0 */
572
573 FT_Int s = 1;
574 FT_UInt32 a, b;
575
576
577 /* XXX: this function does not allow 64-bit arguments */
578
579 a = (FT_UInt32)a_;
580 b = (FT_UInt32)b_;
581
582 FT_MOVE_SIGN( a_, a, s );
583 FT_MOVE_SIGN( b_, b, s );
584
585 if ( a + ( b >> 8 ) <= 8190UL )
586 a = ( a * b + 0x8000UL ) >> 16;
587 else
588 {
589 FT_UInt32 al = a & 0xFFFFUL;
590
591
592 a = ( a >> 16 ) * b + al * ( b >> 16 ) +
593 ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 );
594 }
595
596 a_ = (FT_Long)a;
597
598 return s < 0 ? NEG_LONG( a_ ) : a_;
599
600#endif /* 0 */
601
602 }
603
604
605 /* documentation is in freetype.h */
606
609 FT_Long b_ )
610 {
611 FT_Int s = 1;
612 FT_UInt32 a, b, q;
613 FT_Long q_;
614
615
616 /* XXX: this function does not allow 64-bit arguments */
617
618 a = (FT_UInt32)a_;
619 b = (FT_UInt32)b_;
620
621 FT_MOVE_SIGN( a_, a, s );
622 FT_MOVE_SIGN( b_, b, s );
623
624 if ( b == 0 )
625 {
626 /* check for division by 0 */
627 q = 0x7FFFFFFFUL;
628 }
629 else if ( a <= 65535UL - ( b >> 17 ) )
630 {
631 /* compute result directly */
632 q = ( ( a << 16 ) + ( b >> 1 ) ) / b;
633 }
634 else
635 {
636 /* we need more bits; we have to do it by hand */
637 FT_Int64 temp, temp2;
638
639
640 temp.hi = a >> 16;
641 temp.lo = a << 16;
642 temp2.hi = 0;
643 temp2.lo = b >> 1;
644
645 FT_Add64( &temp, &temp2, &temp );
646 q = ft_div64by32( temp.hi, temp.lo, b );
647 }
648
649 q_ = (FT_Long)q;
650
651 return s < 0 ? NEG_LONG( q_ ) : q_;
652 }
653
654
655#endif /* !FT_LONG64 */
656
657
658 /* documentation is in ftglyph.h */
659
660 FT_EXPORT_DEF( void )
662 FT_Matrix *b )
663 {
664 FT_Fixed xx, xy, yx, yy;
665
666
667 if ( !a || !b )
668 return;
669
670 xx = ADD_LONG( FT_MulFix( a->xx, b->xx ),
671 FT_MulFix( a->xy, b->yx ) );
672 xy = ADD_LONG( FT_MulFix( a->xx, b->xy ),
673 FT_MulFix( a->xy, b->yy ) );
674 yx = ADD_LONG( FT_MulFix( a->yx, b->xx ),
675 FT_MulFix( a->yy, b->yx ) );
676 yy = ADD_LONG( FT_MulFix( a->yx, b->xy ),
677 FT_MulFix( a->yy, b->yy ) );
678
679 b->xx = xx;
680 b->xy = xy;
681 b->yx = yx;
682 b->yy = yy;
683 }
684
685
686 /* documentation is in ftglyph.h */
687
690 {
691 FT_Pos delta, xx, yy;
692
693
694 if ( !matrix )
695 return FT_THROW( Invalid_Argument );
696
697 /* compute discriminant */
698 delta = FT_MulFix( matrix->xx, matrix->yy ) -
699 FT_MulFix( matrix->xy, matrix->yx );
700
701 if ( !delta )
702 return FT_THROW( Invalid_Argument ); /* matrix can't be inverted */
703
704 matrix->xy = - FT_DivFix( matrix->xy, delta );
705 matrix->yx = - FT_DivFix( matrix->yx, delta );
706
707 xx = matrix->xx;
708 yy = matrix->yy;
709
710 matrix->xx = FT_DivFix( yy, delta );
711 matrix->yy = FT_DivFix( xx, delta );
712
713 return FT_Err_Ok;
714 }
715
716
717 /* documentation is in ftcalc.h */
718
719 FT_BASE_DEF( void )
721 FT_Matrix *b,
722 FT_Long scaling )
723 {
724 FT_Fixed xx, xy, yx, yy;
725
726 FT_Long val = 0x10000L * scaling;
727
728
729 if ( !a || !b )
730 return;
731
732 xx = ADD_LONG( FT_MulDiv( a->xx, b->xx, val ),
733 FT_MulDiv( a->xy, b->yx, val ) );
734 xy = ADD_LONG( FT_MulDiv( a->xx, b->xy, val ),
735 FT_MulDiv( a->xy, b->yy, val ) );
736 yx = ADD_LONG( FT_MulDiv( a->yx, b->xx, val ),
737 FT_MulDiv( a->yy, b->yx, val ) );
738 yy = ADD_LONG( FT_MulDiv( a->yx, b->xy, val ),
739 FT_MulDiv( a->yy, b->yy, val ) );
740
741 b->xx = xx;
742 b->xy = xy;
743 b->yx = yx;
744 b->yy = yy;
745 }
746
747
748 /* documentation is in ftcalc.h */
749
750 FT_BASE_DEF( void )
753 FT_Long scaling )
754 {
755 FT_Pos xz, yz;
756
757 FT_Long val = 0x10000L * scaling;
758
759
760 if ( !vector || !matrix )
761 return;
762
763 xz = ADD_LONG( FT_MulDiv( vector->x, matrix->xx, val ),
764 FT_MulDiv( vector->y, matrix->xy, val ) );
765 yz = ADD_LONG( FT_MulDiv( vector->x, matrix->yx, val ),
766 FT_MulDiv( vector->y, matrix->yy, val ) );
767
768 vector->x = xz;
769 vector->y = yz;
770 }
771
772
773 /* documentation is in ftcalc.h */
774
775 FT_BASE_DEF( FT_UInt32 )
777 {
778 FT_Int32 x_ = vector->x;
779 FT_Int32 y_ = vector->y;
780 FT_Int32 b, z;
781 FT_UInt32 x, y, u, v, l;
782 FT_Int sx = 1, sy = 1, shift;
783
784
785 x = (FT_UInt32)x_;
786 y = (FT_UInt32)y_;
787
788 FT_MOVE_SIGN( x_, x, sx );
789 FT_MOVE_SIGN( y_, y, sy );
790
791 /* trivial cases */
792 if ( x == 0 )
793 {
794 if ( y > 0 )
795 vector->y = sy * 0x10000;
796 return y;
797 }
798 else if ( y == 0 )
799 {
800 if ( x > 0 )
801 vector->x = sx * 0x10000;
802 return x;
803 }
804
805 /* Estimate length and prenormalize by shifting so that */
806 /* the new approximate length is between 2/3 and 4/3. */
807 /* The magic constant 0xAAAAAAAAUL (2/3 of 2^32) helps */
808 /* achieve this in 16.16 fixed-point representation. */
809 l = x > y ? x + ( y >> 1 )
810 : y + ( x >> 1 );
811
812 shift = 31 - FT_MSB( l );
813 shift -= 15 + ( l >= ( 0xAAAAAAAAUL >> shift ) );
814
815 if ( shift > 0 )
816 {
817 x <<= shift;
818 y <<= shift;
819
820 /* re-estimate length for tiny vectors */
821 l = x > y ? x + ( y >> 1 )
822 : y + ( x >> 1 );
823 }
824 else
825 {
826 x >>= -shift;
827 y >>= -shift;
828 l >>= -shift;
829 }
830
831 /* lower linear approximation for reciprocal length minus one */
832 b = 0x10000 - (FT_Int32)l;
833
834 x_ = (FT_Int32)x;
835 y_ = (FT_Int32)y;
836
837 /* Newton's iterations */
838 do
839 {
840 u = (FT_UInt32)( x_ + ( x_ * b >> 16 ) );
841 v = (FT_UInt32)( y_ + ( y_ * b >> 16 ) );
842
843 /* Normalized squared length in the parentheses approaches 2^32. */
844 /* On two's complement systems, converting to signed gives the */
845 /* difference with 2^32 even if the expression wraps around. */
846 z = -(FT_Int32)( u * u + v * v ) / 0x200;
847 z = z * ( ( 0x10000 + b ) >> 8 ) / 0x10000;
848
849 b += z;
850
851 } while ( z > 0 );
852
853 vector->x = sx < 0 ? -(FT_Pos)u : (FT_Pos)u;
854 vector->y = sy < 0 ? -(FT_Pos)v : (FT_Pos)v;
855
856 /* Conversion to signed helps to recover from likely wrap around */
857 /* in calculating the prenormalized length, because it gives the */
858 /* correct difference with 2^32 on two's complement systems. */
859 l = (FT_UInt32)( 0x10000 + (FT_Int32)( u * x + v * y ) / 0x10000 );
860 if ( shift > 0 )
861 l = ( l + ( 1 << ( shift - 1 ) ) ) >> shift;
862 else
863 l <<= -shift;
864
865 return l;
866 }
867
868
869#if 0
870
871 /* documentation is in ftcalc.h */
872
873 FT_BASE_DEF( FT_Int32 )
874 FT_SqrtFixed( FT_Int32 x )
875 {
876 FT_UInt32 root, rem_hi, rem_lo, test_div;
878
879
880 root = 0;
881
882 if ( x > 0 )
883 {
884 rem_hi = 0;
885 rem_lo = (FT_UInt32)x;
886 count = 24;
887 do
888 {
889 rem_hi = ( rem_hi << 2 ) | ( rem_lo >> 30 );
890 rem_lo <<= 2;
891 root <<= 1;
892 test_div = ( root << 1 ) + 1;
893
894 if ( rem_hi >= test_div )
895 {
896 rem_hi -= test_div;
897 root += 1;
898 }
899 } while ( --count );
900 }
901
902 return (FT_Int32)root;
903 }
904
905#endif /* 0 */
906
907
908 /* documentation is in ftcalc.h */
909
912 FT_Pos in_y,
913 FT_Pos out_x,
914 FT_Pos out_y )
915 {
916#ifdef FT_LONG64
917
918 FT_Int64 delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x;
919
920
921 return ( delta > 0 ) - ( delta < 0 );
922
923#else
924
926
927
928 /* we silently ignore overflow errors, since such large values */
929 /* lead to even more (harmless) rendering errors later on */
930 if ( ADD_LONG( FT_ABS( in_x ), FT_ABS( out_y ) ) <= 131071L &&
931 ADD_LONG( FT_ABS( in_y ), FT_ABS( out_x ) ) <= 131071L )
932 {
933 FT_Long z1 = MUL_LONG( in_x, out_y );
934 FT_Long z2 = MUL_LONG( in_y, out_x );
935
936
937 if ( z1 > z2 )
938 result = +1;
939 else if ( z1 < z2 )
940 result = -1;
941 else
942 result = 0;
943 }
944 else /* products might overflow 32 bits */
945 {
946 FT_Int64 z1, z2;
947
948
949 /* XXX: this function does not allow 64-bit arguments */
950 ft_multo64( (FT_UInt32)in_x, (FT_UInt32)out_y, &z1 );
951 ft_multo64( (FT_UInt32)in_y, (FT_UInt32)out_x, &z2 );
952
953 if ( z1.hi > z2.hi )
954 result = +1;
955 else if ( z1.hi < z2.hi )
956 result = -1;
957 else if ( z1.lo > z2.lo )
958 result = +1;
959 else if ( z1.lo < z2.lo )
960 result = -1;
961 else
962 result = 0;
963 }
964
965 /* XXX: only the sign of return value, +1/0/-1 must be used */
966 return result;
967
968#endif
969 }
970
971
972 /* documentation is in ftcalc.h */
973
976 FT_Pos in_y,
977 FT_Pos out_x,
978 FT_Pos out_y )
979 {
980 FT_Pos ax = in_x + out_x;
981 FT_Pos ay = in_y + out_y;
982
983 FT_Pos d_in, d_out, d_hypot;
984
985
986 /* The idea of this function is to compare the length of the */
987 /* hypotenuse with the `in' and `out' length. The `corner' */
988 /* represented by `in' and `out' is flat if the hypotenuse's */
989 /* length isn't too large. */
990 /* */
991 /* This approach has the advantage that the angle between */
992 /* `in' and `out' is not checked. In case one of the two */
993 /* vectors is `dominant', this is, much larger than the */
994 /* other vector, we thus always have a flat corner. */
995 /* */
996 /* hypotenuse */
997 /* x---------------------------x */
998 /* \ / */
999 /* \ / */
1000 /* in \ / out */
1001 /* \ / */
1002 /* o */
1003 /* Point */
1004
1005 d_in = FT_HYPOT( in_x, in_y );
1006 d_out = FT_HYPOT( out_x, out_y );
1007 d_hypot = FT_HYPOT( ax, ay );
1008
1009 /* now do a simple length comparison: */
1010 /* */
1011 /* d_in + d_out < 17/16 d_hypot */
1012
1013 return ( d_in + d_out - d_hypot ) < ( d_hypot >> 4 );
1014 }
1015
1016
1017/* END */
static struct sockaddr_in sa
Definition: adnsresfilter.c:69
struct _root root
r l[0]
Definition: byte_order.h:168
superblock * sb
Definition: btrfs.c:4261
return FT_Err_Ok
Definition: ftbbox.c:511
ft_corner_is_flat(FT_Pos in_x, FT_Pos in_y, FT_Pos out_x, FT_Pos out_y)
Definition: ftcalc.c:975
FT_MSB(FT_UInt32 z)
Definition: ftcalc.c:114
FT_RoundFix(FT_Fixed a)
Definition: ftcalc.c:88
static void ft_multo64(FT_UInt32 x, FT_UInt32 y, FT_Int64 *z)
Definition: ftcalc.c:280
static void FT_Add64(FT_Int64 *x, FT_Int64 *y, FT_Int64 *z)
Definition: ftcalc.c:351
FT_MulFix(FT_Long a_, FT_Long b_)
Definition: ftcalc.c:509
FT_MulDiv(FT_Long a_, FT_Long b_, FT_Long c_)
Definition: ftcalc.c:416
FT_Vector_NormLen(FT_Vector *vector)
Definition: ftcalc.c:776
struct FT_Int64_ FT_Int64
FT_Vector_Transform_Scaled(FT_Vector *vector, const FT_Matrix *matrix, FT_Long scaling)
Definition: ftcalc.c:751
FT_CeilFix(FT_Fixed a)
Definition: ftcalc.c:97
FT_FloorFix(FT_Fixed a)
Definition: ftcalc.c:106
FT_MulDiv_No_Round(FT_Long a_, FT_Long b_, FT_Long c_)
Definition: ftcalc.c:464
FT_Matrix_Invert(FT_Matrix *matrix)
Definition: ftcalc.c:689
FT_DivFix(FT_Long a_, FT_Long b_)
Definition: ftcalc.c:608
#define FT_MOVE_SIGN(x, x_unsigned, s)
Definition: ftcalc.c:73
FT_Matrix_Multiply_Scaled(const FT_Matrix *a, FT_Matrix *b, FT_Long scaling)
Definition: ftcalc.c:720
FT_Hypot(FT_Fixed x, FT_Fixed y)
Definition: ftcalc.c:155
FT_Matrix_Multiply(const FT_Matrix *a, FT_Matrix *b)
Definition: ftcalc.c:661
static FT_UInt32 ft_div64by32(FT_UInt32 hi, FT_UInt32 lo, FT_UInt32 y)
Definition: ftcalc.c:312
ft_corner_orientation(FT_Pos in_x, FT_Pos in_y, FT_Pos out_x, FT_Pos out_y)
Definition: ftcalc.c:911
#define NEG_LONG(a)
Definition: ftcalc.h:426
#define MUL_LONG(a, b)
Definition: ftcalc.h:424
#define ADD_LONG(a, b)
Definition: ftcalc.h:420
#define FT_EXPORT_DEF(x)
Definition: ftconfig.h:483
#define FT_BASE_DEF(x)
Definition: ftconfig.h:419
#define FT_THROW(e)
Definition: ftdebug.h:213
FT_BEGIN_HEADER typedef signed long FT_Pos
Definition: ftimage.h:58
#define FT_ABS(a)
Definition: ftobjs.h:74
#define FT_HYPOT(x, y)
Definition: ftobjs.h:81
FT_Vector_Length(FT_Vector *vec)
Definition: fttrigon.c:426
signed long FT_Fixed
Definition: fttypes.h:288
int FT_Error
Definition: fttypes.h:300
signed long FT_Long
Definition: fttypes.h:242
signed int FT_Int
Definition: fttypes.h:220
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
const GLdouble * v
Definition: gl.h:2040
GLdouble s
Definition: gl.h:2039
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLuint GLuint GLsizei count
Definition: gl.h:1545
GLdouble GLdouble GLdouble r
Definition: gl.h:2055
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
const GLubyte * c
Definition: glext.h:8905
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLuint GLenum matrix
Definition: glext.h:9407
GLuint GLfloat * val
Definition: glext.h:7180
GLboolean GLboolean GLboolean GLboolean a
Definition: glext.h:6204
GLuint64EXT * result
Definition: glext.h:11304
GLdouble GLdouble z
Definition: glext.h:5874
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble * u
Definition: glfuncs.h:240
#define d
Definition: ke_i.h:81
#define a
Definition: ke_i.h:78
#define c
Definition: ke_i.h:80
#define b
Definition: ke_i.h:79
UCHAR ab[sizeof("Hello World!") -1]
Definition: fdi.c:106
#define shift
Definition: input.c:1755
int xx
Definition: npserver.c:29
static calc_node_t temp
Definition: rpn_ieee.c:38
FT_UInt32 lo
Definition: ftcalc.c:53
FT_UInt32 hi
Definition: ftcalc.c:54
ecx edi movl ebx edx edi decl ecx esi eax jecxz decl eax andl eax esi movl edx movl TEMP incl eax andl eax ecx incl ebx testl eax jnz xchgl ecx incl TEMP esp ecx subl ebx pushl ecx ecx edx ecx shrl ecx mm0 mm4 mm0 mm4 mm1 mm5 mm1 mm5 mm2 mm6 mm2 mm6 mm3 mm7 mm3 mm7 paddd mm0 paddd mm4 paddd mm0 paddd mm4 paddd mm0 paddd mm4 movq mm1 movq mm5 psrlq mm1 psrlq mm5 paddd mm0 paddd mm4 psrad mm0 psrad mm4 packssdw mm0 packssdw mm4 mm1 punpckldq mm0 pand mm1 pand mm0 por mm1 movq edi esi edx edi decl ecx jnz popl ecx andl ecx jecxz mm0 mm0 mm1 mm1 mm2 mm2 mm3 mm3 paddd mm0 paddd mm0 paddd mm0 movq mm1 psrlq mm1 paddd mm0 psrad mm0 packssdw mm0 movd eax movw ax
Definition: synth_sse3d.h:180
#define const
Definition: zconf.h:233