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