X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=src%2Fbase%2Fftcalc.c;h=57f796803df97f0fde16cff40c0a4581fd1decab;hb=afcae9b7a0a6009d33581fac78416fc9623a8a18;hp=2aeea0459bc83d93c5f30de7dc1ffb913b12f981;hpb=46ec2c26b7d34b4a37c96ed6049ce3fd0702dc78;p=framework%2Fgraphics%2Ffreetype.git diff --git a/src/base/ftcalc.c b/src/base/ftcalc.c index 2aeea04..57f7968 100644 --- a/src/base/ftcalc.c +++ b/src/base/ftcalc.c @@ -4,7 +4,7 @@ /* */ /* Arithmetic computations (body). */ /* */ -/* Copyright 1996-2006, 2008, 2012 by */ +/* Copyright 1996-2006, 2008, 2012-2014 by */ /* David Turner, Robert Wilhelm, and Werner Lemberg. */ /* */ /* This file is part of the FreeType project, and may only be used, */ @@ -34,21 +34,19 @@ #include #include FT_GLYPH_H +#include FT_TRIGONOMETRY_H #include FT_INTERNAL_CALC_H #include FT_INTERNAL_DEBUG_H #include FT_INTERNAL_OBJECTS_H -#ifdef FT_MULFIX_INLINED + +#ifdef FT_MULFIX_ASSEMBLER #undef FT_MulFix #endif -/* we need to define a 64-bits data type here */ - -#ifdef FT_LONG64 - - typedef FT_INT64 FT_Int64; +/* we need to emulate a 64-bit data type if a real one isn't available */ -#else +#ifndef FT_LONG64 typedef struct FT_Int64_ { @@ -57,7 +55,7 @@ } FT_Int64; -#endif /* FT_LONG64 */ +#endif /* !FT_LONG64 */ /*************************************************************************/ @@ -70,6 +68,16 @@ #define FT_COMPONENT trace_calc + /* transfer sign leaving a positive number */ +#define FT_MOVE_SIGN( x, s ) \ + FT_BEGIN_STMNT \ + if ( x < 0 ) \ + { \ + x = -x; \ + s = -s; \ + } \ + FT_END_STMNT + /* The following three functions are available regardless of whether */ /* FT_LONG64 is defined. */ @@ -78,8 +86,8 @@ FT_EXPORT_DEF( FT_Fixed ) FT_RoundFix( FT_Fixed a ) { - return ( a >= 0 ) ? ( a + 0x8000L ) & ~0xFFFFL - : -((-a + 0x8000L ) & ~0xFFFFL ); + return a >= 0 ? ( a + 0x8000L ) & ~0xFFFFL + : -((-a + 0x8000L ) & ~0xFFFFL ); } @@ -88,8 +96,8 @@ FT_EXPORT_DEF( FT_Fixed ) FT_CeilFix( FT_Fixed a ) { - return ( a >= 0 ) ? ( a + 0xFFFFL ) & ~0xFFFFL - : -((-a + 0xFFFFL ) & ~0xFFFFL ); + return a >= 0 ? ( a + 0xFFFFL ) & ~0xFFFFL + : -((-a + 0xFFFFL ) & ~0xFFFFL ); } @@ -98,43 +106,65 @@ FT_EXPORT_DEF( FT_Fixed ) FT_FloorFix( FT_Fixed a ) { - return ( a >= 0 ) ? a & ~0xFFFFL - : -((-a) & ~0xFFFFL ); + return a >= 0 ? a & ~0xFFFFL + : -((-a) & ~0xFFFFL ); } +#ifndef FT_MSB -#ifdef FT_CONFIG_OPTION_OLD_INTERNALS + FT_BASE_DEF ( FT_Int ) + FT_MSB( FT_UInt32 z ) + { + FT_Int shift = 0; - /* documentation is in ftcalc.h */ - FT_EXPORT_DEF( FT_Int32 ) - FT_Sqrt32( FT_Int32 x ) - { - FT_UInt32 val, root, newroot, mask; + /* determine msb bit index in `shift' */ + if ( z & 0xFFFF0000UL ) + { + z >>= 16; + shift += 16; + } + if ( z & 0x0000FF00UL ) + { + z >>= 8; + shift += 8; + } + if ( z & 0x000000F0UL ) + { + z >>= 4; + shift += 4; + } + if ( z & 0x0000000CUL ) + { + z >>= 2; + shift += 2; + } + if ( z & 0x00000002UL ) + { + /* z >>= 1; */ + shift += 1; + } + return shift; + } - root = 0; - mask = (FT_UInt32)0x40000000UL; - val = (FT_UInt32)x; +#endif /* !FT_MSB */ - do - { - newroot = root + mask; - if ( newroot <= val ) - { - val -= newroot; - root = newroot + mask; - } - root >>= 1; - mask >>= 2; + /* documentation is in ftcalc.h */ - } while ( mask != 0 ); + FT_BASE_DEF( FT_Fixed ) + FT_Hypot( FT_Fixed x, + FT_Fixed y ) + { + FT_Vector v; - return root; - } -#endif /* FT_CONFIG_OPTION_OLD_INTERNALS */ + v.x = x; + v.y = y; + + return FT_Vector_Length( &v ); + } #ifdef FT_LONG64 @@ -147,24 +177,21 @@ FT_Long b, FT_Long c ) { - FT_Int s; + FT_Int s = 1; FT_Long d; - s = 1; - if ( a < 0 ) { a = -a; s = -1; } - if ( b < 0 ) { b = -b; s = -s; } - if ( c < 0 ) { c = -c; s = -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 >> 1 ) ) / c : 0x7FFFFFFFL ); - return ( s > 0 ) ? d : -d; + return s < 0 ? -d : d; } -#ifdef TT_USE_BYTECODE_INTERPRETER - /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_Long ) @@ -172,23 +199,20 @@ FT_Long b, FT_Long c ) { - FT_Int s; + FT_Int s = 1; FT_Long d; - s = 1; - if ( a < 0 ) { a = -a; s = -1; } - if ( b < 0 ) { b = -b; s = -s; } - if ( c < 0 ) { c = -c; s = -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 ); - return ( s > 0 ) ? d : -d; + return s < 0 ? -d : d; } -#endif /* TT_USE_BYTECODE_INTERPRETER */ - /* documentation is in freetype.h */ @@ -206,21 +230,12 @@ FT_Long c; - if ( a < 0 ) - { - a = -a; - s = -1; - } - - if ( b < 0 ) - { - b = -b; - s = -s; - } + FT_MOVE_SIGN( a, s ); + FT_MOVE_SIGN( b, s ); c = (FT_Long)( ( (FT_Int64)a * b + 0x8000L ) >> 16 ); - return ( s > 0 ) ? c : -c; + return s < 0 ? -c : c; #endif /* FT_MULFIX_ASSEMBLER */ } @@ -232,21 +247,17 @@ FT_DivFix( FT_Long a, FT_Long b ) { - FT_Int32 s; - FT_UInt32 q; + FT_Int s = 1; + FT_Long q; - s = 1; - if ( a < 0 ) { a = -a; s = -1; } - if ( b < 0 ) { b = -b; s = -s; } - if ( b == 0 ) - /* check for division by 0 */ - q = 0x7FFFFFFFL; - else - /* compute result directly */ - q = (FT_UInt32)( ( ( (FT_Int64)a << 16 ) + ( b >> 1 ) ) / b ); + FT_MOVE_SIGN( a, s ); + FT_MOVE_SIGN( b, s ); - return ( s < 0 ? -(FT_Long)q : (FT_Long)q ); + q = (FT_Long)( b > 0 ? ( ( (FT_UInt64)a << 16 ) + ( b >> 1 ) ) / b + : 0x7FFFFFFFL ); + + return s < 0 ? -q : q; } @@ -294,25 +305,30 @@ FT_Int i; - q = 0; - r = hi; - - if ( r >= y ) + if ( hi >= y ) return (FT_UInt32)0x7FFFFFFFL; - i = 32; + /* We shift as many bits as we can into the high register, perform */ + /* 32-bit division with modulo there, then work through the remaining */ + /* bits with long division. This optimization is especially noticeable */ + /* for smaller dividends that barely use the high register. */ + + i = 31 - FT_MSB( hi ); + r = ( hi << i ) | ( lo >> ( 32 - i ) ); lo <<= i; /* left 64-bit shift */ + q = r / y; + r -= q * y; /* remainder */ + + i = 32 - i; /* bits remaining in low register */ do { - r <<= 1; q <<= 1; - r |= lo >> 31; + r = ( r << 1 ) | ( lo >> 31 ); lo <<= 1; if ( r >= y ) { r -= y; q |= 1; } - lo <<= 1; } while ( --i ); return q; @@ -324,7 +340,7 @@ FT_Int64* y, FT_Int64 *z ) { - register FT_UInt32 lo, hi; + FT_UInt32 lo, hi; lo = x->lo + y->lo; @@ -335,99 +351,134 @@ } - /* documentation is in freetype.h */ - - /* The FT_MulDiv function has been optimized thanks to ideas from */ - /* Graham Asher. The trick is to optimize computation when everything */ - /* fits within 32-bits (a rather common case). */ + /* The FT_MulDiv function has been optimized thanks to ideas from */ + /* Graham Asher and Alexei Podtelezhnikov. The trick is to optimize */ + /* a rather common case when everything fits within 32-bits. */ + /* */ + /* We compute 'a*b+c/2', then divide it by 'c' (all positive values). */ + /* */ + /* The product of two positive numbers never exceeds the square of */ + /* its mean values. Therefore, we always avoid the overflow by */ + /* imposing */ + /* */ + /* (a + b) / 2 <= sqrt(X - c/2) , */ /* */ - /* we compute 'a*b+c/2', then divide it by 'c'. (positive values) */ + /* where X = 2^32 - 1, the maximum unsigned 32-bit value, and using */ + /* unsigned arithmetic. Now we replace `sqrt' with a linear function */ + /* that is smaller or equal for all values of c in the interval */ + /* [0;X/2]; it should be equal to sqrt(X) and sqrt(3X/4) at the */ + /* endpoints. Substituting the linear solution and explicit numbers */ + /* we get */ /* */ - /* 46340 is FLOOR(SQRT(2^31-1)). */ + /* a + b <= 131071.99 - c / 122291.84 . */ /* */ - /* if ( a <= 46340 && b <= 46340 ) then ( a*b <= 0x7FFEA810 ) */ + /* In practice, we should use a faster and even stronger inequality */ /* */ - /* 0x7FFFFFFF - 0x7FFEA810 = 0x157F0 */ + /* a + b <= 131071 - (c >> 16) */ /* */ - /* if ( c < 0x157F0*2 ) then ( a*b+c/2 <= 0x7FFFFFFF ) */ + /* or, alternatively, */ /* */ - /* and 2*0x157F0 = 176096 */ + /* a + b <= 129894 - (c >> 17) . */ /* */ + /* FT_MulFix, on the other hand, is optimized for a small value of */ + /* the first argument, when the second argument can be much larger. */ + /* This can be achieved by scaling the second argument and the limit */ + /* in the above inequalities. For example, */ + /* */ + /* a + (b >> 8) <= (131071 >> 4) */ + /* */ + /* covers the practical range of use. The actual test below is a bit */ + /* tighter to avoid the border case overflows. */ + /* */ + /* In the case of FT_DivFix, the exact overflow check */ + /* */ + /* a << 16 <= X - c/2 */ + /* */ + /* is scaled down by 2^16 and we use */ + /* */ + /* a <= 65535 - (c >> 17) . */ + + /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) FT_MulDiv( FT_Long a, FT_Long b, FT_Long c ) { - long s; + FT_Int s = 1; /* XXX: this function does not allow 64-bit arguments */ if ( a == 0 || b == c ) return a; - s = a; a = FT_ABS( a ); - s ^= b; b = FT_ABS( b ); - s ^= c; c = FT_ABS( c ); + FT_MOVE_SIGN( a, s ); + FT_MOVE_SIGN( b, s ); + FT_MOVE_SIGN( c, s ); + + if ( c == 0 ) + a = 0x7FFFFFFFL; - if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 ) - a = ( a * b + ( c >> 1 ) ) / c; + else if ( (FT_ULong)a + b <= 129894UL - ( c >> 17 ) ) + a = ( (FT_ULong)a * b + ( c >> 1 ) ) / c; - else if ( (FT_Int32)c > 0 ) + else { FT_Int64 temp, temp2; - ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp ); + ft_multo64( a, b, &temp ); temp2.hi = 0; - temp2.lo = (FT_UInt32)(c >> 1); + temp2.lo = c >> 1; + FT_Add64( &temp, &temp2, &temp ); - a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c ); + + /* last attempt to ditch long division */ + a = temp.hi == 0 ? temp.lo / c + : ft_div64by32( temp.hi, temp.lo, c ); } - else - a = 0x7FFFFFFFL; - return ( s < 0 ? -a : a ); + return s < 0 ? -a : a; } -#ifdef TT_USE_BYTECODE_INTERPRETER - FT_BASE_DEF( FT_Long ) FT_MulDiv_No_Round( FT_Long a, FT_Long b, FT_Long c ) { - long s; + FT_Int s = 1; if ( a == 0 || b == c ) return a; - s = a; a = FT_ABS( a ); - s ^= b; b = FT_ABS( b ); - s ^= c; c = FT_ABS( c ); + FT_MOVE_SIGN( a, s ); + FT_MOVE_SIGN( b, s ); + FT_MOVE_SIGN( c, s ); + + if ( c == 0 ) + a = 0x7FFFFFFFL; - if ( a <= 46340L && b <= 46340L && c > 0 ) - a = a * b / c; + else if ( (FT_ULong)a + b <= 131071UL ) + a = (FT_ULong)a * b / c; - else if ( (FT_Int32)c > 0 ) + else { FT_Int64 temp; - ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp ); - a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c ); + ft_multo64( a, b, &temp ); + + /* last attempt to ditch long division */ + a = temp.hi == 0 ? temp.lo / c + : ft_div64by32( temp.hi, temp.lo, c ); } - else - a = 0x7FFFFFFFL; - return ( s < 0 ? -a : a ); + return s < 0 ? -a : a; } -#endif /* TT_USE_BYTECODE_INTERPRETER */ - /* documentation is in freetype.h */ @@ -481,7 +532,7 @@ ua = (FT_ULong)a; ub = (FT_ULong)b; - if ( ua <= 2048 && ub <= 1048576L ) + if ( ua + ( ub >> 8 ) <= 8190UL ) ua = ( ua * ub + 0x8000U ) >> 16; else { @@ -499,20 +550,20 @@ #else /* 0 */ - FT_Long s; + FT_Int s = 1; FT_ULong ua, ub; if ( a == 0 || b == 0x10000L ) return a; - s = a; a = FT_ABS( a ); - s ^= b; b = FT_ABS( b ); + FT_MOVE_SIGN( a, s ); + FT_MOVE_SIGN( b, s ); ua = (FT_ULong)a; ub = (FT_ULong)b; - if ( ua <= 2048 && ub <= 1048576L ) + if ( ua + ( ub >> 8 ) <= 8190UL ) ua = ( ua * ub + 0x8000UL ) >> 16; else { @@ -523,7 +574,7 @@ ( ( al * ( ub & 0xFFFFUL ) + 0x8000UL ) >> 16 ); } - return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua ); + return s < 0 ? -(FT_Long)ua : (FT_Long)ua; #endif /* 0 */ @@ -536,23 +587,24 @@ FT_DivFix( FT_Long a, FT_Long b ) { - FT_Int32 s; - FT_UInt32 q; + FT_Int s = 1; + FT_Long q; /* XXX: this function does not allow 64-bit arguments */ - s = (FT_Int32)a; a = FT_ABS( a ); - s ^= (FT_Int32)b; b = FT_ABS( b ); - if ( (FT_UInt32)b == 0 ) + FT_MOVE_SIGN( a, s ); + FT_MOVE_SIGN( b, s ); + + if ( b == 0 ) { /* check for division by 0 */ - q = (FT_UInt32)0x7FFFFFFFL; + q = 0x7FFFFFFFL; } - else if ( ( a >> 16 ) == 0 ) + else if ( a <= 65535L - ( b >> 17 ) ) { /* compute result directly */ - q = (FT_UInt32)( ( a << 16 ) + ( b >> 1 ) ) / (FT_UInt32)b; + q = (FT_Long)( ( ( (FT_ULong)a << 16 ) + ( b >> 1 ) ) / b ); } else { @@ -560,138 +612,18 @@ FT_Int64 temp, temp2; - temp.hi = (FT_Int32) ( a >> 16 ); - temp.lo = (FT_UInt32)( a << 16 ); + temp.hi = a >> 16; + temp.lo = a << 16; temp2.hi = 0; - temp2.lo = (FT_UInt32)( b >> 1 ); - FT_Add64( &temp, &temp2, &temp ); - q = ft_div64by32( temp.hi, temp.lo, (FT_Int32)b ); - } - - return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); - } - - -#if 0 - - /* documentation is in ftcalc.h */ - - FT_EXPORT_DEF( void ) - FT_MulTo64( FT_Int32 x, - FT_Int32 y, - FT_Int64 *z ) - { - FT_Int32 s; - - - s = x; x = FT_ABS( x ); - s ^= y; y = FT_ABS( y ); - - ft_multo64( x, y, z ); - - if ( s < 0 ) - { - z->lo = (FT_UInt32)-(FT_Int32)z->lo; - z->hi = ~z->hi + !( z->lo ); - } - } - + temp2.lo = b >> 1; - /* apparently, the second version of this code is not compiled correctly */ - /* on Mac machines with the MPW C compiler.. tsk, tsk, tsk... */ - -#if 1 - - FT_EXPORT_DEF( FT_Int32 ) - FT_Div64by32( FT_Int64* x, - FT_Int32 y ) - { - FT_Int32 s; - FT_UInt32 q, r, i, lo; - - - s = x->hi; - if ( s < 0 ) - { - x->lo = (FT_UInt32)-(FT_Int32)x->lo; - x->hi = ~x->hi + !x->lo; - } - s ^= y; y = FT_ABS( y ); - - /* Shortcut */ - if ( x->hi == 0 ) - { - if ( y > 0 ) - q = x->lo / y; - else - q = 0x7FFFFFFFL; - - return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); - } - - r = x->hi; - lo = x->lo; - - if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */ - return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL ); - /* Return Max/Min Int32 if division overflow. */ - /* This includes division by zero! */ - q = 0; - for ( i = 0; i < 32; i++ ) - { - r <<= 1; - q <<= 1; - r |= lo >> 31; - - if ( r >= (FT_UInt32)y ) - { - r -= y; - q |= 1; - } - lo <<= 1; - } - - return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); - } - -#else /* 0 */ - - FT_EXPORT_DEF( FT_Int32 ) - FT_Div64by32( FT_Int64* x, - FT_Int32 y ) - { - FT_Int32 s; - FT_UInt32 q; - - - s = x->hi; - if ( s < 0 ) - { - x->lo = (FT_UInt32)-(FT_Int32)x->lo; - x->hi = ~x->hi + !x->lo; - } - s ^= y; y = FT_ABS( y ); - - /* Shortcut */ - if ( x->hi == 0 ) - { - if ( y > 0 ) - q = ( x->lo + ( y >> 1 ) ) / y; - else - q = 0x7FFFFFFFL; - - return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); + FT_Add64( &temp, &temp2, &temp ); + q = (FT_Long)ft_div64by32( temp.hi, temp.lo, b ); } - q = ft_div64by32( x->hi, x->lo, y ); - - return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); + return s < 0 ? -q : q; } -#endif /* 0 */ - -#endif /* 0 */ - #endif /* FT_LONG64 */ @@ -727,14 +659,14 @@ if ( !matrix ) - return FT_Err_Invalid_Argument; + return FT_THROW( Invalid_Argument ); /* compute discriminant */ delta = FT_MulFix( matrix->xx, matrix->yy ) - FT_MulFix( matrix->xy, matrix->yx ); if ( !delta ) - return FT_Err_Invalid_Argument; /* matrix can't be inverted */ + return FT_THROW( Invalid_Argument ); /* matrix can't be inverted */ matrix->xy = - FT_DivFix( matrix->xy, delta ); matrix->yx = - FT_DivFix( matrix->yx, delta ); @@ -800,6 +732,8 @@ } +#if 0 + /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_Int32 ) @@ -834,6 +768,8 @@ return (FT_Int32)root; } +#endif /* 0 */ + /* documentation is in ftcalc.h */ @@ -923,35 +859,40 @@ FT_Pos out_x, FT_Pos out_y ) { - FT_Pos ax = in_x; - FT_Pos ay = in_y; - - FT_Pos d_in, d_out, d_corner; - - - if ( ax < 0 ) - ax = -ax; - if ( ay < 0 ) - ay = -ay; - d_in = ax + ay; - - ax = out_x; - if ( ax < 0 ) - ax = -ax; - ay = out_y; - if ( ay < 0 ) - ay = -ay; - d_out = ax + ay; - - ax = out_x + in_x; - if ( ax < 0 ) - ax = -ax; - ay = out_y + in_y; - if ( ay < 0 ) - ay = -ay; - d_corner = ax + ay; - - return ( d_in + d_out - d_corner ) < ( d_corner >> 4 ); + FT_Pos ax = in_x + out_x; + FT_Pos ay = in_y + out_y; + + FT_Pos d_in, d_out, d_hypot; + + + /* The idea of this function is to compare the length of the */ + /* hypotenuse with the `in' and `out' length. The `corner' */ + /* represented by `in' and `out' is flat if the hypotenuse's */ + /* length isn't too large. */ + /* */ + /* This approach has the advantage that the angle between */ + /* `in' and `out' is not checked. In case one of the two */ + /* vectors is `dominant', this is, much larger than the */ + /* other vector, we thus always have a flat corner. */ + /* */ + /* hypotenuse */ + /* x---------------------------x */ + /* \ / */ + /* \ / */ + /* in \ / out */ + /* \ / */ + /* o */ + /* Point */ + + d_in = FT_HYPOT( in_x, in_y ); + d_out = FT_HYPOT( out_x, out_y ); + d_hypot = FT_HYPOT( ax, ay ); + + /* now do a simple length comparison: */ + /* */ + /* d_in + d_out < 17/16 d_hypot */ + + return ( d_in + d_out - d_hypot ) < ( d_hypot >> 4 ); }