projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
[FREETYPE]
[reactos.git] / reactos / lib / 3rdparty / freetype / src / base / ftcalc.c
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 <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 #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 #if 0
820
821 /* documentation is in ftcalc.h */
822
823 FT_BASE_DEF( FT_Int32 )
824 FT_SqrtFixed( FT_Int32 x )
825 {
826 FT_UInt32 root, rem_hi, rem_lo, test_div;
827 FT_Int count;
828
829
830 root = 0;
831
832 if ( x > 0 )
833 {
834 rem_hi = 0;
835 rem_lo = x;
836 count = 24;
837 do
838 {
839 rem_hi = ( rem_hi << 2 ) | ( rem_lo >> 30 );
840 rem_lo <<= 2;
841 root <<= 1;
842 test_div = ( root << 1 ) + 1;
843
844 if ( rem_hi >= test_div )
845 {
846 rem_hi -= test_div;
847 root += 1;
848 }
849 } while ( --count );
850 }
851
852 return (FT_Int32)root;
853 }
854
855 #endif /* 0 */
856
857
858 /* documentation is in ftcalc.h */
859
860 FT_BASE_DEF( FT_Int )
861 ft_corner_orientation( FT_Pos in_x,
862 FT_Pos in_y,
863 FT_Pos out_x,
864 FT_Pos out_y )
865 {
866 FT_Long result; /* avoid overflow on 16-bit system */
867
868
869 /* deal with the trivial cases quickly */
870 if ( in_y == 0 )
871 {
872 if ( in_x >= 0 )
873 result = out_y;
874 else
875 result = -out_y;
876 }
877 else if ( in_x == 0 )
878 {
879 if ( in_y >= 0 )
880 result = -out_x;
881 else
882 result = out_x;
883 }
884 else if ( out_y == 0 )
885 {
886 if ( out_x >= 0 )
887 result = in_y;
888 else
889 result = -in_y;
890 }
891 else if ( out_x == 0 )
892 {
893 if ( out_y >= 0 )
894 result = -in_x;
895 else
896 result = in_x;
897 }
898 else /* general case */
899 {
900 #ifdef FT_LONG64
901
902 FT_Int64 delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x;
903
904
905 if ( delta == 0 )
906 result = 0;
907 else
908 result = 1 - 2 * ( delta < 0 );
909
910 #else
911
912 FT_Int64 z1, z2;
913
914
915 /* XXX: this function does not allow 64-bit arguments */
916 ft_multo64( (FT_Int32)in_x, (FT_Int32)out_y, &z1 );
917 ft_multo64( (FT_Int32)in_y, (FT_Int32)out_x, &z2 );
918
919 if ( z1.hi > z2.hi )
920 result = +1;
921 else if ( z1.hi < z2.hi )
922 result = -1;
923 else if ( z1.lo > z2.lo )
924 result = +1;
925 else if ( z1.lo < z2.lo )
926 result = -1;
927 else
928 result = 0;
929
930 #endif
931 }
932
933 /* XXX: only the sign of return value, +1/0/-1 must be used */
934 return (FT_Int)result;
935 }
936
937
938 /* documentation is in ftcalc.h */
939
940 FT_BASE_DEF( FT_Int )
941 ft_corner_is_flat( FT_Pos in_x,
942 FT_Pos in_y,
943 FT_Pos out_x,
944 FT_Pos out_y )
945 {
946 FT_Pos ax = in_x;
947 FT_Pos ay = in_y;
948
949 FT_Pos d_in, d_out, d_corner;
950
951
952 /* We approximate the Euclidean metric (sqrt(x^2 + y^2)) with */
953 /* the Taxicab metric (|x| + |y|), which can be computed much */
954 /* faster. If one of the two vectors is much longer than the */
955 /* other one, the direction of the shorter vector doesn't */
956 /* influence the result any more. */
957 /* */
958 /* corner */
959 /* x---------------------------x */
960 /* \ / */
961 /* \ / */
962 /* in \ / out */
963 /* \ / */
964 /* o */
965 /* Point */
966 /* */
967
968 if ( ax < 0 )
969 ax = -ax;
970 if ( ay < 0 )
971 ay = -ay;
972 d_in = ax + ay; /* d_in = || in || */
973
974 ax = out_x;
975 if ( ax < 0 )
976 ax = -ax;
977 ay = out_y;
978 if ( ay < 0 )
979 ay = -ay;
980 d_out = ax + ay; /* d_out = || out || */
981
982 ax = out_x + in_x;
983 if ( ax < 0 )
984 ax = -ax;
985 ay = out_y + in_y;
986 if ( ay < 0 )
987 ay = -ay;
988 d_corner = ax + ay; /* d_corner = || in + out || */
989
990 /* now do a simple length comparison: */
991 /* */
992 /* d_in + d_out < 17/16 d_corner */
993
994 return ( d_in + d_out - d_corner ) < ( d_corner >> 4 );
995 }
996
997
998 /* END */
A free Windows-compatible Operating System