projects / reactos.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
- Remove svn:needs-lock, svn:eol-type, and svn:eol-tyle properties.
[reactos.git] / reactos / lib / 3rdparty / freetype / src / base / ftcalc.c
1 /***************************************************************************/
2 /* */
3 /* ftcalc.c */
4 /* */
5 /* Arithmetic computations (body). */
6 /* */
7 /* Copyright 1996-2001, 2002, 2003, 2004, 2005, 2006 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_INTERNAL_CALC_H
37 #include FT_INTERNAL_DEBUG_H
38 #include FT_INTERNAL_OBJECTS_H
39
40
41 /* we need to define a 64-bits data type here */
42
43 #ifdef FT_LONG64
44
45 typedef FT_INT64 FT_Int64;
46
47 #else
48
49 typedef struct FT_Int64_
50 {
51 FT_UInt32 lo;
52 FT_UInt32 hi;
53
54 } FT_Int64;
55
56 #endif /* FT_LONG64 */
57
58
59 /*************************************************************************/
60 /* */
61 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
62 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
63 /* messages during execution. */
64 /* */
65 #undef FT_COMPONENT
66 #define FT_COMPONENT trace_calc
67
68
69 /* The following three functions are available regardless of whether */
70 /* FT_LONG64 is defined. */
71
72 /* documentation is in freetype.h */
73
74 FT_EXPORT_DEF( FT_Fixed )
75 FT_RoundFix( FT_Fixed a )
76 {
77 return ( a >= 0 ) ? ( a + 0x8000L ) & ~0xFFFFL
78 : -((-a + 0x8000L ) & ~0xFFFFL );
79 }
80
81
82 /* documentation is in freetype.h */
83
84 FT_EXPORT_DEF( FT_Fixed )
85 FT_CeilFix( FT_Fixed a )
86 {
87 return ( a >= 0 ) ? ( a + 0xFFFFL ) & ~0xFFFFL
88 : -((-a + 0xFFFFL ) & ~0xFFFFL );
89 }
90
91
92 /* documentation is in freetype.h */
93
94 FT_EXPORT_DEF( FT_Fixed )
95 FT_FloorFix( FT_Fixed a )
96 {
97 return ( a >= 0 ) ? a & ~0xFFFFL
98 : -((-a) & ~0xFFFFL );
99 }
100
101
102 #ifdef FT_CONFIG_OPTION_OLD_INTERNALS
103
104 /* documentation is in ftcalc.h */
105
106 FT_EXPORT_DEF( FT_Int32 )
107 FT_Sqrt32( FT_Int32 x )
108 {
109 FT_ULong val, root, newroot, mask;
110
111
112 root = 0;
113 mask = 0x40000000L;
114 val = (FT_ULong)x;
115
116 do
117 {
118 newroot = root + mask;
119 if ( newroot <= val )
120 {
121 val -= newroot;
122 root = newroot + mask;
123 }
124
125 root >>= 1;
126 mask >>= 2;
127
128 } while ( mask != 0 );
129
130 return root;
131 }
132
133 #endif /* FT_CONFIG_OPTION_OLD_INTERNALS */
134
135
136 #ifdef FT_LONG64
137
138
139 /* documentation is in freetype.h */
140
141 FT_EXPORT_DEF( FT_Long )
142 FT_MulDiv( FT_Long a,
143 FT_Long b,
144 FT_Long c )
145 {
146 FT_Int s;
147 FT_Long d;
148
149
150 s = 1;
151 if ( a < 0 ) { a = -a; s = -1; }
152 if ( b < 0 ) { b = -b; s = -s; }
153 if ( c < 0 ) { c = -c; s = -s; }
154
155 d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c
156 : 0x7FFFFFFFL );
157
158 return ( s > 0 ) ? d : -d;
159 }
160
161
162 #ifdef TT_USE_BYTECODE_INTERPRETER
163
164 /* documentation is in ftcalc.h */
165
166 FT_BASE_DEF( FT_Long )
167 FT_MulDiv_No_Round( FT_Long a,
168 FT_Long b,
169 FT_Long c )
170 {
171 FT_Int s;
172 FT_Long d;
173
174
175 s = 1;
176 if ( a < 0 ) { a = -a; s = -1; }
177 if ( b < 0 ) { b = -b; s = -s; }
178 if ( c < 0 ) { c = -c; s = -s; }
179
180 d = (FT_Long)( c > 0 ? (FT_Int64)a * b / c
181 : 0x7FFFFFFFL );
182
183 return ( s > 0 ) ? d : -d;
184 }
185
186 #endif /* TT_USE_BYTECODE_INTERPRETER */
187
188
189 /* documentation is in freetype.h */
190
191 FT_EXPORT_DEF( FT_Long )
192 FT_MulFix( FT_Long a,
193 FT_Long b )
194 {
195 FT_Int s = 1;
196 FT_Long c;
197
198
199 if ( a < 0 ) { a = -a; s = -1; }
200 if ( b < 0 ) { b = -b; s = -s; }
201
202 c = (FT_Long)( ( (FT_Int64)a * b + 0x8000L ) >> 16 );
203 return ( s > 0 ) ? c : -c ;
204 }
205
206
207 /* documentation is in freetype.h */
208
209 FT_EXPORT_DEF( FT_Long )
210 FT_DivFix( FT_Long a,
211 FT_Long b )
212 {
213 FT_Int32 s;
214 FT_UInt32 q;
215
216 s = 1;
217 if ( a < 0 ) { a = -a; s = -1; }
218 if ( b < 0 ) { b = -b; s = -s; }
219
220 if ( b == 0 )
221 /* check for division by 0 */
222 q = 0x7FFFFFFFL;
223 else
224 /* compute result directly */
225 q = (FT_UInt32)( ( ( (FT_Int64)a << 16 ) + ( b >> 1 ) ) / b );
226
227 return ( s < 0 ? -(FT_Long)q : (FT_Long)q );
228 }
229
230
231 #else /* !FT_LONG64 */
232
233
234 static void
235 ft_multo64( FT_UInt32 x,
236 FT_UInt32 y,
237 FT_Int64 *z )
238 {
239 FT_UInt32 lo1, hi1, lo2, hi2, lo, hi, i1, i2;
240
241
242 lo1 = x & 0x0000FFFFU; hi1 = x >> 16;
243 lo2 = y & 0x0000FFFFU; hi2 = y >> 16;
244
245 lo = lo1 * lo2;
246 i1 = lo1 * hi2;
247 i2 = lo2 * hi1;
248 hi = hi1 * hi2;
249
250 /* Check carry overflow of i1 + i2 */
251 i1 += i2;
252 hi += (FT_UInt32)( i1 < i2 ) << 16;
253
254 hi += i1 >> 16;
255 i1 = i1 << 16;
256
257 /* Check carry overflow of i1 + lo */
258 lo += i1;
259 hi += ( lo < i1 );
260
261 z->lo = lo;
262 z->hi = hi;
263 }
264
265
266 static FT_UInt32
267 ft_div64by32( FT_UInt32 hi,
268 FT_UInt32 lo,
269 FT_UInt32 y )
270 {
271 FT_UInt32 r, q;
272 FT_Int i;
273
274
275 q = 0;
276 r = hi;
277
278 if ( r >= y )
279 return (FT_UInt32)0x7FFFFFFFL;
280
281 i = 32;
282 do
283 {
284 r <<= 1;
285 q <<= 1;
286 r |= lo >> 31;
287
288 if ( r >= (FT_UInt32)y )
289 {
290 r -= y;
291 q |= 1;
292 }
293 lo <<= 1;
294 } while ( --i );
295
296 return q;
297 }
298
299
300 static void
301 FT_Add64( FT_Int64* x,
302 FT_Int64* y,
303 FT_Int64 *z )
304 {
305 register FT_UInt32 lo, hi;
306
307
308 lo = x->lo + y->lo;
309 hi = x->hi + y->hi + ( lo < x->lo );
310
311 z->lo = lo;
312 z->hi = hi;
313 }
314
315
316 /* documentation is in freetype.h */
317
318 /* The FT_MulDiv function has been optimized thanks to ideas from */
319 /* Graham Asher. The trick is to optimize computation when everything */
320 /* fits within 32-bits (a rather common case). */
321 /* */
322 /* we compute 'a*b+c/2', then divide it by 'c'. (positive values) */
323 /* */
324 /* 46340 is FLOOR(SQRT(2^31-1)). */
325 /* */
326 /* if ( a <= 46340 && b <= 46340 ) then ( a*b <= 0x7FFEA810 ) */
327 /* */
328 /* 0x7FFFFFFF - 0x7FFEA810 = 0x157F0 */
329 /* */
330 /* if ( c < 0x157F0*2 ) then ( a*b+c/2 <= 0x7FFFFFFF ) */
331 /* */
332 /* and 2*0x157F0 = 176096 */
333 /* */
334
335 FT_EXPORT_DEF( FT_Long )
336 FT_MulDiv( FT_Long a,
337 FT_Long b,
338 FT_Long c )
339 {
340 long s;
341
342
343 if ( a == 0 || b == c )
344 return a;
345
346 s = a; a = FT_ABS( a );
347 s ^= b; b = FT_ABS( b );
348 s ^= c; c = FT_ABS( c );
349
350 if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 )
351 a = ( a * b + ( c >> 1 ) ) / c;
352
353 else if ( c > 0 )
354 {
355 FT_Int64 temp, temp2;
356
357
358 ft_multo64( a, b, &temp );
359
360 temp2.hi = 0;
361 temp2.lo = (FT_UInt32)(c >> 1);
362 FT_Add64( &temp, &temp2, &temp );
363 a = ft_div64by32( temp.hi, temp.lo, c );
364 }
365 else
366 a = 0x7FFFFFFFL;
367
368 return ( s < 0 ? -a : a );
369 }
370
371
372 #ifdef TT_USE_BYTECODE_INTERPRETER
373
374 FT_BASE_DEF( FT_Long )
375 FT_MulDiv_No_Round( FT_Long a,
376 FT_Long b,
377 FT_Long c )
378 {
379 long s;
380
381
382 if ( a == 0 || b == c )
383 return a;
384
385 s = a; a = FT_ABS( a );
386 s ^= b; b = FT_ABS( b );
387 s ^= c; c = FT_ABS( c );
388
389 if ( a <= 46340L && b <= 46340L && c > 0 )
390 a = a * b / c;
391
392 else if ( c > 0 )
393 {
394 FT_Int64 temp;
395
396
397 ft_multo64( a, b, &temp );
398 a = ft_div64by32( temp.hi, temp.lo, c );
399 }
400 else
401 a = 0x7FFFFFFFL;
402
403 return ( s < 0 ? -a : a );
404 }
405
406 #endif /* TT_USE_BYTECODE_INTERPRETER */
407
408
409 /* documentation is in freetype.h */
410
411 FT_EXPORT_DEF( FT_Long )
412 FT_MulFix( FT_Long a,
413 FT_Long b )
414 {
415 /* use inline assembly to speed up things a bit */
416
417 #if defined( __GNUC__ ) && defined( i386 )
418
419 FT_Long result;
420
421
422 __asm__ __volatile__ (
423 "imul %%edx\n"
424 "movl %%edx, %%ecx\n"
425 "sarl $31, %%ecx\n"
426 "addl $0x8000, %%ecx\n"
427 "addl %%ecx, %%eax\n"
428 "adcl $0, %%edx\n"
429 "shrl $16, %%eax\n"
430 "shll $16, %%edx\n"
431 "addl %%edx, %%eax\n"
432 "mov %%eax, %0\n"
433 : "=r"(result)
434 : "a"(a), "d"(b)
435 : "%ecx"
436 );
437 return result;
438
439 #elif 1
440
441 FT_Long sa, sb;
442 FT_ULong ua, ub;
443
444
445 if ( a == 0 || b == 0x10000L )
446 return a;
447
448 sa = ( a >> ( sizeof ( a ) * 8 - 1 ) );
449 a = ( a ^ sa ) - sa;
450 sb = ( b >> ( sizeof ( b ) * 8 - 1 ) );
451 b = ( b ^ sb ) - sb;
452
453 ua = (FT_ULong)a;
454 ub = (FT_ULong)b;
455
456 if ( ua <= 2048 && ub <= 1048576L )
457 ua = ( ua * ub + 0x8000U ) >> 16;
458 else
459 {
460 FT_ULong al = ua & 0xFFFFU;
461
462
463 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) +
464 ( ( al * ( ub & 0xFFFFU ) + 0x8000U ) >> 16 );
465 }
466
467 sa ^= sb,
468 ua = (FT_ULong)(( ua ^ sa ) - sa);
469
470 return (FT_Long)ua;
471
472 #else /* 0 */
473
474 FT_Long s;
475 FT_ULong ua, ub;
476
477
478 if ( a == 0 || b == 0x10000L )
479 return a;
480
481 s = a; a = FT_ABS( a );
482 s ^= b; b = FT_ABS( b );
483
484 ua = (FT_ULong)a;
485 ub = (FT_ULong)b;
486
487 if ( ua <= 2048 && ub <= 1048576L )
488 ua = ( ua * ub + 0x8000UL ) >> 16;
489 else
490 {
491 FT_ULong al = ua & 0xFFFFUL;
492
493
494 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) +
495 ( ( al * ( ub & 0xFFFFUL ) + 0x8000UL ) >> 16 );
496 }
497
498 return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua );
499
500 #endif /* 0 */
501
502 }
503
504
505 /* documentation is in freetype.h */
506
507 FT_EXPORT_DEF( FT_Long )
508 FT_DivFix( FT_Long a,
509 FT_Long b )
510 {
511 FT_Int32 s;
512 FT_UInt32 q;
513
514
515 s = a; a = FT_ABS(a);
516 s ^= b; b = FT_ABS(b);
517
518 if ( b == 0 )
519 {
520 /* check for division by 0 */
521 q = 0x7FFFFFFFL;
522 }
523 else if ( ( a >> 16 ) == 0 )
524 {
525 /* compute result directly */
526 q = (FT_UInt32)( (a << 16) + (b >> 1) ) / (FT_UInt32)b;
527 }
528 else
529 {
530 /* we need more bits; we have to do it by hand */
531 FT_Int64 temp, temp2;
532
533 temp.hi = (FT_Int32) (a >> 16);
534 temp.lo = (FT_UInt32)(a << 16);
535 temp2.hi = 0;
536 temp2.lo = (FT_UInt32)( b >> 1 );
537 FT_Add64( &temp, &temp2, &temp );
538 q = ft_div64by32( temp.hi, temp.lo, b );
539 }
540
541 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
542 }
543
544
545 #if 0
546
547 /* documentation is in ftcalc.h */
548
549 FT_EXPORT_DEF( void )
550 FT_MulTo64( FT_Int32 x,
551 FT_Int32 y,
552 FT_Int64 *z )
553 {
554 FT_Int32 s;
555
556
557 s = x; x = FT_ABS( x );
558 s ^= y; y = FT_ABS( y );
559
560 ft_multo64( x, y, z );
561
562 if ( s < 0 )
563 {
564 z->lo = (FT_UInt32)-(FT_Int32)z->lo;
565 z->hi = ~z->hi + !( z->lo );
566 }
567 }
568
569
570 /* apparently, the second version of this code is not compiled correctly */
571 /* on Mac machines with the MPW C compiler.. tsk, tsk, tsk... */
572
573 #if 1
574
575 FT_EXPORT_DEF( FT_Int32 )
576 FT_Div64by32( FT_Int64* x,
577 FT_Int32 y )
578 {
579 FT_Int32 s;
580 FT_UInt32 q, r, i, lo;
581
582
583 s = x->hi;
584 if ( s < 0 )
585 {
586 x->lo = (FT_UInt32)-(FT_Int32)x->lo;
587 x->hi = ~x->hi + !x->lo;
588 }
589 s ^= y; y = FT_ABS( y );
590
591 /* Shortcut */
592 if ( x->hi == 0 )
593 {
594 if ( y > 0 )
595 q = x->lo / y;
596 else
597 q = 0x7FFFFFFFL;
598
599 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
600 }
601
602 r = x->hi;
603 lo = x->lo;
604
605 if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */
606 return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL );
607 /* Return Max/Min Int32 if division overflow. */
608 /* This includes division by zero! */
609 q = 0;
610 for ( i = 0; i < 32; i++ )
611 {
612 r <<= 1;
613 q <<= 1;
614 r |= lo >> 31;
615
616 if ( r >= (FT_UInt32)y )
617 {
618 r -= y;
619 q |= 1;
620 }
621 lo <<= 1;
622 }
623
624 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
625 }
626
627 #else /* 0 */
628
629 FT_EXPORT_DEF( FT_Int32 )
630 FT_Div64by32( FT_Int64* x,
631 FT_Int32 y )
632 {
633 FT_Int32 s;
634 FT_UInt32 q;
635
636
637 s = x->hi;
638 if ( s < 0 )
639 {
640 x->lo = (FT_UInt32)-(FT_Int32)x->lo;
641 x->hi = ~x->hi + !x->lo;
642 }
643 s ^= y; y = FT_ABS( y );
644
645 /* Shortcut */
646 if ( x->hi == 0 )
647 {
648 if ( y > 0 )
649 q = ( x->lo + ( y >> 1 ) ) / y;
650 else
651 q = 0x7FFFFFFFL;
652
653 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
654 }
655
656 q = ft_div64by32( x->hi, x->lo, y );
657
658 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
659 }
660
661 #endif /* 0 */
662
663 #endif /* 0 */
664
665
666 #endif /* FT_LONG64 */
667
668
669 /* documentation is in ftcalc.h */
670
671 FT_BASE_DEF( FT_Int32 )
672 FT_SqrtFixed( FT_Int32 x )
673 {
674 FT_UInt32 root, rem_hi, rem_lo, test_div;
675 FT_Int count;
676
677
678 root = 0;
679
680 if ( x > 0 )
681 {
682 rem_hi = 0;
683 rem_lo = x;
684 count = 24;
685 do
686 {
687 rem_hi = ( rem_hi << 2 ) | ( rem_lo >> 30 );
688 rem_lo <<= 2;
689 root <<= 1;
690 test_div = ( root << 1 ) + 1;
691
692 if ( rem_hi >= test_div )
693 {
694 rem_hi -= test_div;
695 root += 1;
696 }
697 } while ( --count );
698 }
699
700 return (FT_Int32)root;
701 }
702
703
704 /* documentation is in ftcalc.h */
705
706 FT_BASE_DEF( FT_Int )
707 ft_corner_orientation( FT_Pos in_x,
708 FT_Pos in_y,
709 FT_Pos out_x,
710 FT_Pos out_y )
711 {
712 FT_Int result;
713
714
715 /* deal with the trivial cases quickly */
716 if ( in_y == 0 )
717 {
718 if ( in_x >= 0 )
719 result = out_y;
720 else
721 result = -out_y;
722 }
723 else if ( in_x == 0 )
724 {
725 if ( in_y >= 0 )
726 result = -out_x;
727 else
728 result = out_x;
729 }
730 else if ( out_y == 0 )
731 {
732 if ( out_x >= 0 )
733 result = in_y;
734 else
735 result = -in_y;
736 }
737 else if ( out_x == 0 )
738 {
739 if ( out_y >= 0 )
740 result = -in_x;
741 else
742 result = in_x;
743 }
744 else /* general case */
745 {
746 #ifdef FT_LONG64
747
748 FT_Int64 delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x;
749
750
751 if ( delta == 0 )
752 result = 0;
753 else
754 result = 1 - 2 * ( delta < 0 );
755
756 #else
757
758 FT_Int64 z1, z2;
759
760
761 ft_multo64( in_x, out_y, &z1 );
762 ft_multo64( in_y, out_x, &z2 );
763
764 if ( z1.hi > z2.hi )
765 result = +1;
766 else if ( z1.hi < z2.hi )
767 result = -1;
768 else if ( z1.lo > z2.lo )
769 result = +1;
770 else if ( z1.lo < z2.lo )
771 result = -1;
772 else
773 result = 0;
774
775 #endif
776 }
777
778 return result;
779 }
780
781
782 /* documentation is in ftcalc.h */
783
784 FT_BASE_DEF( FT_Int )
785 ft_corner_is_flat( FT_Pos in_x,
786 FT_Pos in_y,
787 FT_Pos out_x,
788 FT_Pos out_y )
789 {
790 FT_Pos ax = in_x;
791 FT_Pos ay = in_y;
792
793 FT_Pos d_in, d_out, d_corner;
794
795
796 if ( ax < 0 )
797 ax = -ax;
798 if ( ay < 0 )
799 ay = -ay;
800 d_in = ax + ay;
801
802 ax = out_x;
803 if ( ax < 0 )
804 ax = -ax;
805 ay = out_y;
806 if ( ay < 0 )
807 ay = -ay;
808 d_out = ax + ay;
809
810 ax = out_x + in_x;
811 if ( ax < 0 )
812 ax = -ax;
813 ay = out_y + in_y;
814 if ( ay < 0 )
815 ay = -ay;
816 d_corner = ax + ay;
817
818 return ( d_in + d_out - d_corner ) < ( d_corner >> 4 );
819 }
820
821
822 /* END */
A free Windows-compatible Operating System