1 /***************************************************************************/
5 /* Arithmetic computations (body). */
7 /* Copyright 1996-2006, 2008, 2012-2013 by */
8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */
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. */
16 /***************************************************************************/
18 /*************************************************************************/
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. */
23 /*************************************************************************/
25 /*************************************************************************/
27 /* Implementing basic computation routines. */
29 /* FT_MulDiv(), FT_MulFix(), FT_DivFix(), FT_RoundFix(), FT_CeilFix(), */
30 /* and FT_FloorFix() are declared in freetype.h. */
32 /*************************************************************************/
37 #include FT_TRIGONOMETRY_H
38 #include FT_INTERNAL_CALC_H
39 #include FT_INTERNAL_DEBUG_H
40 #include FT_INTERNAL_OBJECTS_H
42 #ifdef FT_MULFIX_INLINED
46 /* we need to emulate a 64-bit data type if a real one isn't available */
50 typedef struct FT_Int64_
57 #endif /* !FT_LONG64 */
60 /*************************************************************************/
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. */
67 #define FT_COMPONENT trace_calc
70 /* The following three functions are available regardless of whether */
71 /* FT_LONG64 is defined. */
73 /* documentation is in freetype.h */
75 FT_EXPORT_DEF( FT_Fixed
)
76 FT_RoundFix( FT_Fixed a
)
78 return ( a
>= 0 ) ? ( a
+ 0x8000L
) & ~0xFFFFL
79 : -((-a
+ 0x8000L
) & ~0xFFFFL
);
83 /* documentation is in freetype.h */
85 FT_EXPORT_DEF( FT_Fixed
)
86 FT_CeilFix( FT_Fixed a
)
88 return ( a
>= 0 ) ? ( a
+ 0xFFFFL
) & ~0xFFFFL
89 : -((-a
+ 0xFFFFL
) & ~0xFFFFL
);
93 /* documentation is in freetype.h */
95 FT_EXPORT_DEF( FT_Fixed
)
96 FT_FloorFix( FT_Fixed a
)
98 return ( a
>= 0 ) ? a
& ~0xFFFFL
99 : -((-a
) & ~0xFFFFL
);
103 FT_BASE_DEF ( FT_Int
)
104 FT_MSB( FT_UInt32 z
)
108 /* determine msb bit index in `shift' */
109 if ( z
>= ( 1L << 16 ) )
114 if ( z
>= ( 1L << 8 ) )
119 if ( z
>= ( 1L << 4 ) )
124 if ( z
>= ( 1L << 2 ) )
129 if ( z
>= ( 1L << 1 ) )
139 /* documentation is in ftcalc.h */
141 FT_BASE_DEF( FT_Fixed
)
142 FT_Hypot( FT_Fixed x
,
151 return FT_Vector_Length( &v
);
158 /* documentation is in freetype.h */
160 FT_EXPORT_DEF( FT_Long
)
161 FT_MulDiv( FT_Long a
,
170 if ( a
< 0 ) { a
= -a
; s
= -1; }
171 if ( b
< 0 ) { b
= -b
; s
= -s
; }
172 if ( c
< 0 ) { c
= -c
; s
= -s
; }
174 d
= (FT_Long
)( c
> 0 ? ( (FT_Int64
)a
* b
+ ( c
>> 1 ) ) / c
177 return ( s
> 0 ) ? d
: -d
;
181 /* documentation is in ftcalc.h */
183 FT_BASE_DEF( FT_Long
)
184 FT_MulDiv_No_Round( FT_Long a
,
193 if ( a
< 0 ) { a
= -a
; s
= -1; }
194 if ( b
< 0 ) { b
= -b
; s
= -s
; }
195 if ( c
< 0 ) { c
= -c
; s
= -s
; }
197 d
= (FT_Long
)( c
> 0 ? (FT_Int64
)a
* b
/ c
200 return ( s
> 0 ) ? d
: -d
;
204 /* documentation is in freetype.h */
206 FT_EXPORT_DEF( FT_Long
)
207 FT_MulFix( FT_Long a
,
210 #ifdef FT_MULFIX_ASSEMBLER
212 return FT_MULFIX_ASSEMBLER( a
, b
);
232 c
= (FT_Long
)( ( (FT_Int64
)a
* b
+ 0x8000L
) >> 16 );
234 return ( s
> 0 ) ? c
: -c
;
236 #endif /* FT_MULFIX_ASSEMBLER */
240 /* documentation is in freetype.h */
242 FT_EXPORT_DEF( FT_Long
)
243 FT_DivFix( FT_Long a
,
263 /* check for division by 0 */
266 /* compute result directly */
267 q
= (FT_UInt32
)( ( ( (FT_UInt64
)a
<< 16 ) + ( b
>> 1 ) ) / b
);
269 return ( s
< 0 ? -(FT_Long
)q
: (FT_Long
)q
);
273 #else /* !FT_LONG64 */
277 ft_multo64( FT_UInt32 x
,
281 FT_UInt32 lo1
, hi1
, lo2
, hi2
, lo
, hi
, i1
, i2
;
284 lo1
= x
& 0x0000FFFFU
; hi1
= x
>> 16;
285 lo2
= y
& 0x0000FFFFU
; hi2
= y
>> 16;
292 /* Check carry overflow of i1 + i2 */
294 hi
+= (FT_UInt32
)( i1
< i2
) << 16;
299 /* Check carry overflow of i1 + lo */
309 ft_div64by32( FT_UInt32 hi
,
321 return (FT_UInt32
)0x7FFFFFFFL
;
343 FT_Add64( FT_Int64
* x
,
347 register FT_UInt32 lo
, hi
;
351 hi
= x
->hi
+ y
->hi
+ ( lo
< x
->lo
);
358 /* documentation is in freetype.h */
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). */
364 /* we compute 'a*b+c/2', then divide it by 'c'. (positive values) */
366 /* 46340 is FLOOR(SQRT(2^31-1)). */
368 /* if ( a <= 46340 && b <= 46340 ) then ( a*b <= 0x7FFEA810 ) */
370 /* 0x7FFFFFFF - 0x7FFEA810 = 0x157F0 */
372 /* if ( c < 0x157F0*2 ) then ( a*b+c/2 <= 0x7FFFFFFF ) */
374 /* and 2*0x157F0 = 176096 */
377 FT_EXPORT_DEF( FT_Long
)
378 FT_MulDiv( FT_Long a
,
385 /* XXX: this function does not allow 64-bit arguments */
386 if ( a
== 0 || b
== c
)
389 s
= a
; a
= FT_ABS( a
);
390 s
^= b
; b
= FT_ABS( b
);
391 s
^= c
; c
= FT_ABS( c
);
393 if ( a
<= 46340L && b
<= 46340L && c
<= 176095L && c
> 0 )
394 a
= ( a
* b
+ ( c
>> 1 ) ) / c
;
396 else if ( (FT_Int32
)c
> 0 )
398 FT_Int64 temp
, temp2
;
401 ft_multo64( (FT_Int32
)a
, (FT_Int32
)b
, &temp
);
404 temp2
.lo
= (FT_UInt32
)(c
>> 1);
405 FT_Add64( &temp
, &temp2
, &temp
);
406 a
= ft_div64by32( temp
.hi
, temp
.lo
, (FT_Int32
)c
);
411 return ( s
< 0 ? -a
: a
);
415 FT_BASE_DEF( FT_Long
)
416 FT_MulDiv_No_Round( FT_Long a
,
423 if ( a
== 0 || b
== c
)
426 s
= a
; a
= FT_ABS( a
);
427 s
^= b
; b
= FT_ABS( b
);
428 s
^= c
; c
= FT_ABS( c
);
430 if ( a
<= 46340L && b
<= 46340L && c
> 0 )
433 else if ( (FT_Int32
)c
> 0 )
438 ft_multo64( (FT_Int32
)a
, (FT_Int32
)b
, &temp
);
439 a
= ft_div64by32( temp
.hi
, temp
.lo
, (FT_Int32
)c
);
444 return ( s
< 0 ? -a
: a
);
448 /* documentation is in freetype.h */
450 FT_EXPORT_DEF( FT_Long
)
451 FT_MulFix( FT_Long a
,
454 #ifdef FT_MULFIX_ASSEMBLER
456 return FT_MULFIX_ASSEMBLER( a
, b
);
461 * This code is nonportable. See comment below.
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.
471 if ( a
== 0 || b
== 0x10000L
)
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').
480 * Unfortunately, it doesn't work (at least not portably).
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
492 sa
= ( a
>> ( sizeof ( a
) * 8 - 1 ) );
494 sb
= ( b
>> ( sizeof ( b
) * 8 - 1 ) );
500 if ( ua
<= 2048 && ub
<= 1048576L )
501 ua
= ( ua
* ub
+ 0x8000U
) >> 16;
504 FT_ULong al
= ua
& 0xFFFFU
;
507 ua
= ( ua
>> 16 ) * ub
+ al
* ( ub
>> 16 ) +
508 ( ( al
* ( ub
& 0xFFFFU
) + 0x8000U
) >> 16 );
512 ua
= (FT_ULong
)(( ua
^ sa
) - sa
);
522 if ( a
== 0 || b
== 0x10000L
)
525 s
= a
; a
= FT_ABS( a
);
526 s
^= b
; b
= FT_ABS( b
);
531 if ( ua
<= 2048 && ub
<= 1048576L )
532 ua
= ( ua
* ub
+ 0x8000UL
) >> 16;
535 FT_ULong al
= ua
& 0xFFFFUL
;
538 ua
= ( ua
>> 16 ) * ub
+ al
* ( ub
>> 16 ) +
539 ( ( al
* ( ub
& 0xFFFFUL
) + 0x8000UL
) >> 16 );
542 return ( s
< 0 ? -(FT_Long
)ua
: (FT_Long
)ua
);
549 /* documentation is in freetype.h */
551 FT_EXPORT_DEF( FT_Long
)
552 FT_DivFix( FT_Long a
,
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
);
563 if ( (FT_UInt32
)b
== 0 )
565 /* check for division by 0 */
566 q
= (FT_UInt32
)0x7FFFFFFFL
;
568 else if ( ( a
>> 16 ) == 0 )
570 /* compute result directly */
571 q
= (FT_UInt32
)( ( (FT_ULong
)a
<< 16 ) + ( b
>> 1 ) ) / (FT_UInt32
)b
;
575 /* we need more bits; we have to do it by hand */
576 FT_Int64 temp
, temp2
;
579 temp
.hi
= (FT_Int32
)( a
>> 16 );
580 temp
.lo
= (FT_UInt32
)a
<< 16;
582 temp2
.lo
= (FT_UInt32
)( b
>> 1 );
583 FT_Add64( &temp
, &temp2
, &temp
);
584 q
= ft_div64by32( temp
.hi
, temp
.lo
, (FT_Int32
)b
);
587 return ( s
< 0 ? -(FT_Int32
)q
: (FT_Int32
)q
);
593 /* documentation is in ftcalc.h */
595 FT_EXPORT_DEF( void )
596 FT_MulTo64( FT_Int32 x
,
603 s
= x
; x
= FT_ABS( x
);
604 s
^= y
; y
= FT_ABS( y
);
606 ft_multo64( x
, y
, z
);
610 z
->lo
= (FT_UInt32
)-(FT_Int32
)z
->lo
;
611 z
->hi
= ~z
->hi
+ !( z
->lo
);
616 /* apparently, the second version of this code is not compiled correctly */
617 /* on Mac machines with the MPW C compiler.. tsk, tsk, tsk... */
621 FT_EXPORT_DEF( FT_Int32
)
622 FT_Div64by32( FT_Int64
* x
,
626 FT_UInt32 q
, r
, i
, lo
;
632 x
->lo
= (FT_UInt32
)-(FT_Int32
)x
->lo
;
633 x
->hi
= ~x
->hi
+ !x
->lo
;
635 s
^= y
; y
= FT_ABS( y
);
645 return ( s
< 0 ? -(FT_Int32
)q
: (FT_Int32
)q
);
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! */
656 for ( i
= 0; i
< 32; i
++ )
662 if ( r
>= (FT_UInt32
)y
)
670 return ( s
< 0 ? -(FT_Int32
)q
: (FT_Int32
)q
);
675 FT_EXPORT_DEF( FT_Int32
)
676 FT_Div64by32( FT_Int64
* x
,
686 x
->lo
= (FT_UInt32
)-(FT_Int32
)x
->lo
;
687 x
->hi
= ~x
->hi
+ !x
->lo
;
689 s
^= y
; y
= FT_ABS( y
);
695 q
= ( x
->lo
+ ( y
>> 1 ) ) / y
;
699 return ( s
< 0 ? -(FT_Int32
)q
: (FT_Int32
)q
);
702 q
= ft_div64by32( x
->hi
, x
->lo
, y
);
704 return ( s
< 0 ? -(FT_Int32
)q
: (FT_Int32
)q
);
712 #endif /* FT_LONG64 */
715 /* documentation is in ftglyph.h */
717 FT_EXPORT_DEF( void )
718 FT_Matrix_Multiply( const FT_Matrix
* a
,
721 FT_Fixed xx
, xy
, yx
, yy
;
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
);
732 b
->xx
= xx
; b
->xy
= xy
;
733 b
->yx
= yx
; b
->yy
= yy
;
737 /* documentation is in ftglyph.h */
739 FT_EXPORT_DEF( FT_Error
)
740 FT_Matrix_Invert( FT_Matrix
* matrix
)
742 FT_Pos delta
, xx
, yy
;
746 return FT_THROW( Invalid_Argument
);
748 /* compute discriminant */
749 delta
= FT_MulFix( matrix
->xx
, matrix
->yy
) -
750 FT_MulFix( matrix
->xy
, matrix
->yx
);
753 return FT_THROW( Invalid_Argument
); /* matrix can't be inverted */
755 matrix
->xy
= - FT_DivFix( matrix
->xy
, delta
);
756 matrix
->yx
= - FT_DivFix( matrix
->yx
, delta
);
761 matrix
->xx
= FT_DivFix( yy
, delta
);
762 matrix
->yy
= FT_DivFix( xx
, delta
);
768 /* documentation is in ftcalc.h */
771 FT_Matrix_Multiply_Scaled( const FT_Matrix
* a
,
775 FT_Fixed xx
, xy
, yx
, yy
;
777 FT_Long val
= 0x10000L
* scaling
;
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
);
788 b
->xx
= xx
; b
->xy
= xy
;
789 b
->yx
= yx
; b
->yy
= yy
;
793 /* documentation is in ftcalc.h */
796 FT_Vector_Transform_Scaled( FT_Vector
* vector
,
797 const FT_Matrix
* matrix
,
802 FT_Long val
= 0x10000L
* scaling
;
805 if ( !vector
|| !matrix
)
808 xz
= FT_MulDiv( vector
->x
, matrix
->xx
, val
) +
809 FT_MulDiv( vector
->y
, matrix
->xy
, val
);
811 yz
= FT_MulDiv( vector
->x
, matrix
->yx
, val
) +
812 FT_MulDiv( vector
->y
, matrix
->yy
, val
);
819 /* documentation is in ftcalc.h */
821 FT_BASE_DEF( FT_Int32
)
822 FT_SqrtFixed( FT_Int32 x
)
824 FT_UInt32 root
, rem_hi
, rem_lo
, test_div
;
837 rem_hi
= ( rem_hi
<< 2 ) | ( rem_lo
>> 30 );
840 test_div
= ( root
<< 1 ) + 1;
842 if ( rem_hi
>= test_div
)
850 return (FT_Int32
)root
;
854 /* documentation is in ftcalc.h */
856 FT_BASE_DEF( FT_Int
)
857 ft_corner_orientation( FT_Pos in_x
,
862 FT_Long result
; /* avoid overflow on 16-bit system */
865 /* deal with the trivial cases quickly */
873 else if ( in_x
== 0 )
880 else if ( out_y
== 0 )
887 else if ( out_x
== 0 )
894 else /* general case */
898 FT_Int64 delta
= (FT_Int64
)in_x
* out_y
- (FT_Int64
)in_y
* out_x
;
904 result
= 1 - 2 * ( delta
< 0 );
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
);
917 else if ( z1
.hi
< z2
.hi
)
919 else if ( z1
.lo
> z2
.lo
)
921 else if ( z1
.lo
< z2
.lo
)
929 /* XXX: only the sign of return value, +1/0/-1 must be used */
930 return (FT_Int
)result
;
934 /* documentation is in ftcalc.h */
936 FT_BASE_DEF( FT_Int
)
937 ft_corner_is_flat( FT_Pos in_x
,
945 FT_Pos d_in
, d_out
, d_corner
;
970 return ( d_in
+ d_out
- d_corner
) < ( d_corner
>> 4 );