diff options
Diffstat (limited to 'third_party/freetype/src/base/ftcalc.c')
-rw-r--r-- | third_party/freetype/src/base/ftcalc.c | 455 |
1 files changed, 280 insertions, 175 deletions
diff --git a/third_party/freetype/src/base/ftcalc.c b/third_party/freetype/src/base/ftcalc.c index f3ef8c537b..619a08b3a0 100644 --- a/third_party/freetype/src/base/ftcalc.c +++ b/third_party/freetype/src/base/ftcalc.c @@ -4,7 +4,7 @@ /* */ /* Arithmetic computations (body). */ /* */ -/* Copyright 1996-2006, 2008, 2012-2014 by */ +/* Copyright 1996-2015 by */ /* David Turner, Robert Wilhelm, and Werner Lemberg. */ /* */ /* This file is part of the FreeType project, and may only be used, */ @@ -86,8 +86,7 @@ FT_EXPORT_DEF( FT_Fixed ) FT_RoundFix( FT_Fixed a ) { - return ( a >= 0 ) ? ( a + 0x8000L ) & ~0xFFFFL - : -((-a + 0x8000L ) & ~0xFFFFL ); + return ( a + 0x8000L - ( a < 0 ) ) & ~0xFFFFL; } @@ -96,8 +95,7 @@ FT_EXPORT_DEF( FT_Fixed ) FT_CeilFix( FT_Fixed a ) { - return ( a >= 0 ) ? ( a + 0xFFFFL ) & ~0xFFFFL - : -((-a + 0xFFFFL ) & ~0xFFFFL ); + return ( a + 0xFFFFL ) & ~0xFFFFL; } @@ -106,8 +104,7 @@ FT_EXPORT_DEF( FT_Fixed ) FT_FloorFix( FT_Fixed a ) { - return ( a >= 0 ) ? a & ~0xFFFFL - : -((-a) & ~0xFFFFL ); + return a & ~0xFFFFL; } #ifndef FT_MSB @@ -115,30 +112,31 @@ FT_BASE_DEF ( FT_Int ) FT_MSB( FT_UInt32 z ) { - FT_Int shift = 0; + FT_Int shift = 0; + /* determine msb bit index in `shift' */ - if ( z & 0xFFFF0000U ) + if ( z & 0xFFFF0000UL ) { z >>= 16; shift += 16; } - if ( z & 0x0000FF00U ) + if ( z & 0x0000FF00UL ) { z >>= 8; shift += 8; } - if ( z & 0x000000F0U ) + if ( z & 0x000000F0UL ) { z >>= 4; shift += 4; } - if ( z & 0x0000000CU ) + if ( z & 0x0000000CUL ) { z >>= 2; shift += 2; } - if ( z & 0x00000002U ) + if ( z & 0x00000002UL ) { /* z >>= 1; */ shift += 1; @@ -172,69 +170,77 @@ /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) - FT_MulDiv( FT_Long a, - FT_Long b, - FT_Long c ) + FT_MulDiv( FT_Long a_, + FT_Long b_, + FT_Long c_ ) { - FT_Int s = 1; - FT_Long d; + FT_Int s = 1; + FT_UInt64 a, b, c, d; + FT_Long d_; + + + FT_MOVE_SIGN( a_, s ); + FT_MOVE_SIGN( b_, s ); + FT_MOVE_SIGN( c_, s ); + a = (FT_UInt64)a_; + b = (FT_UInt64)b_; + c = (FT_UInt64)c_; - FT_MOVE_SIGN( a, s ); - FT_MOVE_SIGN( b, s ); - FT_MOVE_SIGN( c, s ); + d = c > 0 ? ( a * b + ( c >> 1 ) ) / c + : 0x7FFFFFFFUL; - d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c - : 0x7FFFFFFFL ); + d_ = (FT_Long)d; - return ( s > 0 ) ? d : -d; + return s < 0 ? -d_ : d_; } /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_Long ) - FT_MulDiv_No_Round( FT_Long a, - FT_Long b, - FT_Long c ) + FT_MulDiv_No_Round( FT_Long a_, + FT_Long b_, + FT_Long c_ ) { - FT_Int s = 1; - FT_Long d; + FT_Int s = 1; + FT_UInt64 a, b, c, d; + FT_Long d_; - FT_MOVE_SIGN( a, s ); - FT_MOVE_SIGN( b, s ); - FT_MOVE_SIGN( c, s ); + FT_MOVE_SIGN( a_, s ); + FT_MOVE_SIGN( b_, s ); + FT_MOVE_SIGN( c_, s ); - d = (FT_Long)( c > 0 ? (FT_Int64)a * b / c - : 0x7FFFFFFFL ); + a = (FT_UInt64)a_; + b = (FT_UInt64)b_; + c = (FT_UInt64)c_; - return ( s > 0 ) ? d : -d; + d = c > 0 ? a * b / c + : 0x7FFFFFFFUL; + + d_ = (FT_Long)d; + + return s < 0 ? -d_ : d_; } /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) - FT_MulFix( FT_Long a, - FT_Long b ) + FT_MulFix( FT_Long a_, + FT_Long b_ ) { #ifdef FT_MULFIX_ASSEMBLER - return FT_MULFIX_ASSEMBLER( a, b ); + return FT_MULFIX_ASSEMBLER( a_, b_ ); #else - FT_Int s = 1; - FT_Long c; - + FT_Int64 ab = (FT_Int64)a_ * (FT_Int64)b_; - FT_MOVE_SIGN( a, s ); - FT_MOVE_SIGN( b, s ); - - c = (FT_Long)( ( (FT_Int64)a * b + 0x8000L ) >> 16 ); - - return ( s > 0 ) ? c : -c; + /* this requires arithmetic right shift of signed numbers */ + return (FT_Long)( ( ab + 0x8000L - ( ab < 0 ) ) >> 16 ); #endif /* FT_MULFIX_ASSEMBLER */ } @@ -243,20 +249,26 @@ /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) - FT_DivFix( FT_Long a, - FT_Long b ) + FT_DivFix( FT_Long a_, + FT_Long b_ ) { - FT_Int s = 1; - FT_Long q; + FT_Int s = 1; + FT_UInt64 a, b, q; + FT_Long q_; + + FT_MOVE_SIGN( a_, s ); + FT_MOVE_SIGN( b_, s ); - FT_MOVE_SIGN( a, s ); - FT_MOVE_SIGN( b, s ); + a = (FT_UInt64)a_; + b = (FT_UInt64)b_; - q = (FT_Long)( b > 0 ? ( ( (FT_UInt64)a << 16 ) + ( b >> 1 ) ) / b - : 0x7FFFFFFFL ); + q = b > 0 ? ( ( a << 16 ) + ( b >> 1 ) ) / b + : 0x7FFFFFFFUL; - return ( s < 0 ? -q : q ); + q_ = (FT_Long)q; + + return s < 0 ? -q_ : q_; } @@ -400,26 +412,29 @@ /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) - FT_MulDiv( FT_Long a, - FT_Long b, - FT_Long c ) + FT_MulDiv( FT_Long a_, + FT_Long b_, + FT_Long c_ ) { - FT_Int s = 1; + FT_Int s = 1; + FT_UInt32 a, b, c; /* XXX: this function does not allow 64-bit arguments */ - if ( a == 0 || b == c ) - return a; - FT_MOVE_SIGN( a, s ); - FT_MOVE_SIGN( b, s ); - FT_MOVE_SIGN( c, s ); + FT_MOVE_SIGN( a_, s ); + FT_MOVE_SIGN( b_, s ); + FT_MOVE_SIGN( c_, s ); + + a = (FT_UInt32)a_; + b = (FT_UInt32)b_; + c = (FT_UInt32)c_; if ( c == 0 ) - a = 0x7FFFFFFFL; + a = 0x7FFFFFFFUL; - else if ( (FT_ULong)a + b <= 129894UL - ( c >> 17 ) ) - a = ( (FT_ULong)a * b + ( c >> 1 ) ) / c; + else if ( a + b <= 129894UL - ( c >> 17 ) ) + a = ( a * b + ( c >> 1 ) ) / c; else { @@ -438,30 +453,36 @@ : ft_div64by32( temp.hi, temp.lo, c ); } - return ( s < 0 ? -a : a ); + a_ = (FT_Long)a; + + return s < 0 ? -a_ : a_; } FT_BASE_DEF( FT_Long ) - FT_MulDiv_No_Round( FT_Long a, - FT_Long b, - FT_Long c ) + FT_MulDiv_No_Round( FT_Long a_, + FT_Long b_, + FT_Long c_ ) { - FT_Int s = 1; + FT_Int s = 1; + FT_UInt32 a, b, c; + + /* XXX: this function does not allow 64-bit arguments */ - if ( a == 0 || b == c ) - return a; + FT_MOVE_SIGN( a_, s ); + FT_MOVE_SIGN( b_, s ); + FT_MOVE_SIGN( c_, s ); - FT_MOVE_SIGN( a, s ); - FT_MOVE_SIGN( b, s ); - FT_MOVE_SIGN( c, s ); + a = (FT_UInt32)a_; + b = (FT_UInt32)b_; + c = (FT_UInt32)c_; if ( c == 0 ) - a = 0x7FFFFFFFL; + a = 0x7FFFFFFFUL; - else if ( (FT_ULong)a + b <= 131071UL ) - a = (FT_ULong)a * b / c; + else if ( a + b <= 131071UL ) + a = a * b / c; else { @@ -475,19 +496,21 @@ : ft_div64by32( temp.hi, temp.lo, c ); } - return ( s < 0 ? -a : a ); + a_ = (FT_Long)a; + + return s < 0 ? -a_ : a_; } /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) - FT_MulFix( FT_Long a, - FT_Long b ) + FT_MulFix( FT_Long a_, + FT_Long b_ ) { #ifdef FT_MULFIX_ASSEMBLER - return FT_MULFIX_ASSEMBLER( a, b ); + return FT_MULFIX_ASSEMBLER( a_, b_ ); #elif 0 @@ -498,12 +521,9 @@ * the leftmost bits by copying the sign bit, it might be faster. */ - FT_Long sa, sb; - FT_ULong ua, ub; - + FT_Long sa, sb; + FT_UInt32 a, b; - if ( a == 0 || b == 0x10000L ) - return a; /* * This is a clever way of converting a signed number `a' into its @@ -523,57 +543,58 @@ * with the value 1 rather than -1. After that, everything else goes * wrong. */ - sa = ( a >> ( sizeof ( a ) * 8 - 1 ) ); - a = ( a ^ sa ) - sa; - sb = ( b >> ( sizeof ( b ) * 8 - 1 ) ); - b = ( b ^ sb ) - sb; + sa = ( a_ >> ( sizeof ( a_ ) * 8 - 1 ) ); + a = ( a_ ^ sa ) - sa; + sb = ( b_ >> ( sizeof ( b_ ) * 8 - 1 ) ); + b = ( b_ ^ sb ) - sb; - ua = (FT_ULong)a; - ub = (FT_ULong)b; + a = (FT_UInt32)a_; + b = (FT_UInt32)b_; - if ( ua + ( ub >> 8 ) <= 8190UL ) - ua = ( ua * ub + 0x8000U ) >> 16; + if ( a + ( b >> 8 ) <= 8190UL ) + a = ( a * b + 0x8000U ) >> 16; else { - FT_ULong al = ua & 0xFFFFU; + FT_UInt32 al = a & 0xFFFFUL; - ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + - ( ( al * ( ub & 0xFFFFU ) + 0x8000U ) >> 16 ); + a = ( a >> 16 ) * b + al * ( b >> 16 ) + + ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 ); } - sa ^= sb, - ua = (FT_ULong)(( ua ^ sa ) - sa); + sa ^= sb; + a = ( a ^ sa ) - sa; - return (FT_Long)ua; + return (FT_Long)a; #else /* 0 */ - FT_Int s = 1; - FT_ULong ua, ub; + FT_Int s = 1; + FT_UInt32 a, b; - if ( a == 0 || b == 0x10000L ) - return a; + /* XXX: this function does not allow 64-bit arguments */ - FT_MOVE_SIGN( a, s ); - FT_MOVE_SIGN( b, s ); + FT_MOVE_SIGN( a_, s ); + FT_MOVE_SIGN( b_, s ); - ua = (FT_ULong)a; - ub = (FT_ULong)b; + a = (FT_UInt32)a_; + b = (FT_UInt32)b_; - if ( ua + ( ub >> 8 ) <= 8190UL ) - ua = ( ua * ub + 0x8000UL ) >> 16; + if ( a + ( b >> 8 ) <= 8190UL ) + a = ( a * b + 0x8000UL ) >> 16; else { - FT_ULong al = ua & 0xFFFFUL; + FT_UInt32 al = a & 0xFFFFUL; - ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + - ( ( al * ( ub & 0xFFFFUL ) + 0x8000UL ) >> 16 ); + a = ( a >> 16 ) * b + al * ( b >> 16 ) + + ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 ); } - return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua ); + a_ = (FT_Long)a; + + return s < 0 ? -a_ : a_; #endif /* 0 */ @@ -583,27 +604,31 @@ /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) - FT_DivFix( FT_Long a, - FT_Long b ) + FT_DivFix( FT_Long a_, + FT_Long b_ ) { - FT_Int s = 1; - FT_Long q; + FT_Int s = 1; + FT_UInt32 a, b, q; + FT_Long q_; /* XXX: this function does not allow 64-bit arguments */ - FT_MOVE_SIGN( a, s ); - FT_MOVE_SIGN( b, s ); + FT_MOVE_SIGN( a_, s ); + FT_MOVE_SIGN( b_, s ); + + a = (FT_UInt32)a_; + b = (FT_UInt32)b_; if ( b == 0 ) { /* check for division by 0 */ - q = 0x7FFFFFFFL; + q = 0x7FFFFFFFUL; } - else if ( a <= 65535L - ( b >> 17 ) ) + else if ( a <= 65535UL - ( b >> 17 ) ) { /* compute result directly */ - q = (FT_Long)( ( ( (FT_ULong)a << 16 ) + ( b >> 1 ) ) / b ); + q = ( ( a << 16 ) + ( b >> 1 ) ) / b; } else { @@ -617,14 +642,16 @@ temp2.lo = b >> 1; FT_Add64( &temp, &temp2, &temp ); - q = (FT_Long)ft_div64by32( temp.hi, temp.lo, b ); + q = ft_div64by32( temp.hi, temp.lo, b ); } - return ( s < 0 ? -q : q ); + q_ = (FT_Long)q; + + return s < 0 ? -q_ : q_; } -#endif /* FT_LONG64 */ +#endif /* !FT_LONG64 */ /* documentation is in ftglyph.h */ @@ -731,6 +758,102 @@ } + /* documentation is in ftcalc.h */ + + FT_BASE_DEF( FT_UInt32 ) + FT_Vector_NormLen( FT_Vector* vector ) + { + FT_Int32 x_ = vector->x; + FT_Int32 y_ = vector->y; + FT_Int32 b, z; + FT_UInt32 x, y, u, v, l; + FT_Int sx = 1, sy = 1, shift; + + + FT_MOVE_SIGN( x_, sx ); + FT_MOVE_SIGN( y_, sy ); + + x = (FT_UInt32)x_; + y = (FT_UInt32)y_; + + /* trivial cases */ + if ( x == 0 ) + { + if ( y > 0 ) + vector->y = sy * 0x10000; + return y; + } + else if ( y == 0 ) + { + if ( x > 0 ) + vector->x = sx * 0x10000; + return x; + } + + /* Estimate length and prenormalize by shifting so that */ + /* the new approximate length is between 2/3 and 4/3. */ + /* The magic constant 0xAAAAAAAAUL (2/3 of 2^32) helps */ + /* achieve this in 16.16 fixed-point representation. */ + l = x > y ? x + ( y >> 1 ) + : y + ( x >> 1 ); + + shift = 31 - FT_MSB( l ); + shift -= 15 + ( l >= ( 0xAAAAAAAAUL >> shift ) ); + + if ( shift > 0 ) + { + x <<= shift; + y <<= shift; + + /* re-estimate length for tiny vectors */ + l = x > y ? x + ( y >> 1 ) + : y + ( x >> 1 ); + } + else + { + x >>= -shift; + y >>= -shift; + l >>= -shift; + } + + /* lower linear approximation for reciprocal length minus one */ + b = 0x10000 - (FT_Int32)l; + + x_ = (FT_Int32)x; + y_ = (FT_Int32)y; + + /* Newton's iterations */ + do + { + u = (FT_UInt32)( x_ + ( x_ * b >> 16 ) ); + v = (FT_UInt32)( y_ + ( y_ * b >> 16 ) ); + + /* Normalized squared length in the parentheses approaches 2^32. */ + /* On two's complement systems, converting to signed gives the */ + /* difference with 2^32 even if the expression wraps around. */ + z = -(FT_Int32)( u * u + v * v ) / 0x200; + z = z * ( ( 0x10000 + b ) >> 8 ) / 0x10000; + + b += z; + + } while ( z > 0 ); + + vector->x = sx < 0 ? -(FT_Pos)u : (FT_Pos)u; + vector->y = sy < 0 ? -(FT_Pos)v : (FT_Pos)v; + + /* Conversion to signed helps to recover from likely wrap around */ + /* in calculating the prenormalized length, because it gives the */ + /* correct difference with 2^32 on two's complement systems. */ + l = (FT_UInt32)( 0x10000 + (FT_Int32)( u * x + v * y ) / 0x10000 ); + if ( shift > 0 ) + l = ( l + ( 1 << ( shift - 1 ) ) ) >> shift; + else + l <<= -shift; + + return l; + } + + #if 0 /* documentation is in ftcalc.h */ @@ -747,7 +870,7 @@ if ( x > 0 ) { rem_hi = 0; - rem_lo = x; + rem_lo = (FT_UInt32)x; count = 24; do { @@ -778,58 +901,40 @@ FT_Pos out_x, FT_Pos out_y ) { - FT_Long result; /* avoid overflow on 16-bit system */ - - - /* deal with the trivial cases quickly */ - if ( in_y == 0 ) - { - if ( in_x >= 0 ) - result = out_y; - else - result = -out_y; - } - else if ( in_x == 0 ) - { - if ( in_y >= 0 ) - result = -out_x; - else - result = out_x; - } - else if ( out_y == 0 ) - { - if ( out_x >= 0 ) - result = in_y; - else - result = -in_y; - } - else if ( out_x == 0 ) - { - if ( out_y >= 0 ) - result = -in_x; - else - result = in_x; - } - else /* general case */ - { #ifdef FT_LONG64 - FT_Int64 delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x; + FT_Int64 delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x; - if ( delta == 0 ) - result = 0; - else - result = 1 - 2 * ( delta < 0 ); + return ( delta > 0 ) - ( delta < 0 ); #else + FT_Int result; + + + if ( (FT_ULong)FT_ABS( in_x ) + (FT_ULong)FT_ABS( out_y ) <= 131071UL && + (FT_ULong)FT_ABS( in_y ) + (FT_ULong)FT_ABS( out_x ) <= 131071UL ) + { + FT_Long z1 = in_x * out_y; + FT_Long z2 = in_y * out_x; + + + if ( z1 > z2 ) + result = +1; + else if ( z1 < z2 ) + result = -1; + else + result = 0; + } + else /* products might overflow 32 bits */ + { FT_Int64 z1, z2; /* XXX: this function does not allow 64-bit arguments */ - ft_multo64( (FT_Int32)in_x, (FT_Int32)out_y, &z1 ); - ft_multo64( (FT_Int32)in_y, (FT_Int32)out_x, &z2 ); + ft_multo64( (FT_UInt32)in_x, (FT_UInt32)out_y, &z1 ); + ft_multo64( (FT_UInt32)in_y, (FT_UInt32)out_x, &z2 ); if ( z1.hi > z2.hi ) result = +1; @@ -841,12 +946,12 @@ result = -1; else result = 0; - -#endif } /* XXX: only the sign of return value, +1/0/-1 must be used */ - return (FT_Int)result; + return result; + +#endif } |