/**************************************************************************** * * ftcalc.c * * Arithmetic computations (body). * * Copyright (C) 1996-2024 by * David Turner, Robert Wilhelm, and Werner Lemberg. * * This file is part of the FreeType project, and may only be used, * modified, and distributed under the terms of the FreeType project * license, LICENSE.TXT. By continuing to use, modify, or distribute * this file you indicate that you have read the license and * understand and accept it fully. * */ /************************************************************************** * * Support for 1-complement arithmetic has been totally dropped in this * release. You can still write your own code if you need it. * */ /************************************************************************** * * Implementing basic computation routines. * * FT_MulDiv(), FT_MulFix(), FT_DivFix(), FT_RoundFix(), FT_CeilFix(), * and FT_FloorFix() are declared in freetype.h. * */ #include <freetype/ftglyph.h> #include <freetype/fttrigon.h> #include <freetype/internal/ftcalc.h> #include <freetype/internal/ftdebug.h> #include <freetype/internal/ftobjs.h> #ifdef FT_MULFIX_ASSEMBLER #undef FT_MulFix #endif /* we need to emulate a 64-bit data type if a real one isn't available */ #ifndef FT_INT64 typedef struct FT_Int64_ { FT_UInt32 lo; FT_UInt32 hi; } FT_Int64; #endif /* !FT_INT64 */ /************************************************************************** * * The macro FT_COMPONENT is used in trace mode. It is an implicit * parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log * messages during execution. */ #undef FT_COMPONENT #define FT_COMPONENT … /* transfer sign, leaving a positive number; */ /* we need an unsigned value to safely negate INT_MIN (or LONG_MIN) */ #define FT_MOVE_SIGN( utype, x, x_unsigned, s ) … /* The following three functions are available regardless of whether */ /* FT_INT64 is defined. */ /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Fixed ) FT_RoundFix( FT_Fixed a ) { … } /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Fixed ) FT_CeilFix( FT_Fixed a ) { … } /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Fixed ) FT_FloorFix( FT_Fixed a ) { … } #ifndef FT_MSB FT_BASE_DEF( FT_Int ) FT_MSB( FT_UInt32 z ) { FT_Int shift = 0; /* 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; } #endif /* !FT_MSB */ /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_Fixed ) FT_Hypot( FT_Fixed x, FT_Fixed y ) { … } #ifdef FT_INT64 /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) FT_MulDiv( FT_Long a_, FT_Long b_, FT_Long c_ ) { … } /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_Long ) FT_MulDiv_No_Round( FT_Long a_, FT_Long b_, FT_Long c_ ) { … } /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) FT_MulFix( FT_Long a_, FT_Long b_ ) { … } /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) FT_DivFix( FT_Long a_, FT_Long b_ ) { … } #else /* !FT_INT64 */ static void ft_multo64( FT_UInt32 x, FT_UInt32 y, FT_Int64 *z ) { FT_UInt32 lo1, hi1, lo2, hi2, lo, hi, i1, i2; lo1 = x & 0x0000FFFFU; hi1 = x >> 16; lo2 = y & 0x0000FFFFU; hi2 = y >> 16; lo = lo1 * lo2; i1 = lo1 * hi2; i2 = lo2 * hi1; hi = hi1 * hi2; /* Check carry overflow of i1 + i2 */ i1 += i2; hi += (FT_UInt32)( i1 < i2 ) << 16; hi += i1 >> 16; i1 = i1 << 16; /* Check carry overflow of i1 + lo */ lo += i1; hi += ( lo < i1 ); z->lo = lo; z->hi = hi; } static FT_UInt32 ft_div64by32( FT_UInt32 hi, FT_UInt32 lo, FT_UInt32 y ) { FT_UInt32 r, q; FT_Int i; if ( hi >= y ) return (FT_UInt32)0x7FFFFFFFL; /* 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 { q <<= 1; r = ( r << 1 ) | ( lo >> 31 ); lo <<= 1; if ( r >= y ) { r -= y; q |= 1; } } while ( --i ); return q; } static void FT_Add64( FT_Int64* x, FT_Int64* y, FT_Int64 *z ) { FT_UInt32 lo, hi; lo = x->lo + y->lo; hi = x->hi + y->hi + ( lo < x->lo ); z->lo = lo; z->hi = hi; } /* 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) , */ /* */ /* 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 */ /* */ /* a + b <= 131071.99 - c / 122291.84 . */ /* */ /* In practice, we should use a faster and even stronger inequality */ /* */ /* a + b <= 131071 - (c >> 16) */ /* */ /* or, alternatively, */ /* */ /* 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_ ) { FT_Int s = 1; FT_UInt32 a, b, c; /* XXX: this function does not allow 64-bit arguments */ FT_MOVE_SIGN( FT_UInt32, a_, a, s ); FT_MOVE_SIGN( FT_UInt32, b_, b, s ); FT_MOVE_SIGN( FT_UInt32, c_, c, s ); if ( c == 0 ) a = 0x7FFFFFFFUL; else if ( a + b <= 129894UL - ( c >> 17 ) ) a = ( a * b + ( c >> 1 ) ) / c; else { FT_Int64 temp, temp2; ft_multo64( a, b, &temp ); temp2.hi = 0; temp2.lo = c >> 1; FT_Add64( &temp, &temp2, &temp ); /* last attempt to ditch long division */ a = ( temp.hi == 0 ) ? temp.lo / c : ft_div64by32( temp.hi, temp.lo, c ); } a_ = (FT_Long)a; return s < 0 ? NEG_LONG( a_ ) : a_; } FT_BASE_DEF( FT_Long ) FT_MulDiv_No_Round( FT_Long a_, FT_Long b_, FT_Long c_ ) { FT_Int s = 1; FT_UInt32 a, b, c; /* XXX: this function does not allow 64-bit arguments */ FT_MOVE_SIGN( FT_UInt32, a_, a, s ); FT_MOVE_SIGN( FT_UInt32, b_, b, s ); FT_MOVE_SIGN( FT_UInt32, c_, c, s ); if ( c == 0 ) a = 0x7FFFFFFFUL; else if ( a + b <= 131071UL ) a = a * b / c; else { FT_Int64 temp; 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 ); } a_ = (FT_Long)a; return s < 0 ? NEG_LONG( a_ ) : a_; } /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) FT_MulFix( FT_Long a_, FT_Long b_ ) { #ifdef FT_MULFIX_ASSEMBLER return FT_MULFIX_ASSEMBLER( a_, b_ ); #elif 0 /* * This code is nonportable. See comment below. * * However, on a platform where right-shift of a signed quantity fills * the leftmost bits by copying the sign bit, it might be faster. */ FT_Long sa, sb; FT_UInt32 a, b; /* * This is a clever way of converting a signed number `a' into its * absolute value (stored back into `a') and its sign. The sign is * stored in `sa'; 0 means `a' was positive or zero, and -1 means `a' * was negative. (Similarly for `b' and `sb'). * * Unfortunately, it doesn't work (at least not portably). * * It makes the assumption that right-shift on a negative signed value * fills the leftmost bits by copying the sign bit. This is wrong. * According to K&R 2nd ed, section `A7.8 Shift Operators' on page 206, * the result of right-shift of a negative signed value is * implementation-defined. At least one implementation fills the * leftmost bits with 0s (i.e., it is exactly the same as an unsigned * right shift). This means that when `a' is negative, `sa' ends up * 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; a = (FT_UInt32)a_; b = (FT_UInt32)b_; if ( a + ( b >> 8 ) <= 8190UL ) a = ( a * b + 0x8000U ) >> 16; else { FT_UInt32 al = a & 0xFFFFUL; a = ( a >> 16 ) * b + al * ( b >> 16 ) + ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 ); } sa ^= sb; a = ( a ^ sa ) - sa; return (FT_Long)a; #else /* 0 */ FT_Int s = 1; FT_UInt32 a, b; /* XXX: this function does not allow 64-bit arguments */ FT_MOVE_SIGN( FT_UInt32, a_, a, s ); FT_MOVE_SIGN( FT_UInt32, b_, b, s ); if ( a + ( b >> 8 ) <= 8190UL ) a = ( a * b + 0x8000UL ) >> 16; else { FT_UInt32 al = a & 0xFFFFUL; a = ( a >> 16 ) * b + al * ( b >> 16 ) + ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 ); } a_ = (FT_Long)a; return s < 0 ? NEG_LONG( a_ ) : a_; #endif /* 0 */ } /* documentation is in freetype.h */ FT_EXPORT_DEF( FT_Long ) FT_DivFix( FT_Long a_, FT_Long b_ ) { FT_Int s = 1; FT_UInt32 a, b, q; FT_Long q_; /* XXX: this function does not allow 64-bit arguments */ FT_MOVE_SIGN( FT_UInt32, a_, a, s ); FT_MOVE_SIGN( FT_UInt32, b_, b, s ); if ( b == 0 ) { /* check for division by 0 */ q = 0x7FFFFFFFUL; } else if ( a <= 65535UL - ( b >> 17 ) ) { /* compute result directly */ q = ( ( a << 16 ) + ( b >> 1 ) ) / b; } else { /* we need more bits; we have to do it by hand */ FT_Int64 temp, temp2; temp.hi = a >> 16; temp.lo = a << 16; temp2.hi = 0; temp2.lo = b >> 1; FT_Add64( &temp, &temp2, &temp ); q = ft_div64by32( temp.hi, temp.lo, b ); } q_ = (FT_Long)q; return s < 0 ? NEG_LONG( q_ ) : q_; } #endif /* !FT_INT64 */ /* documentation is in ftglyph.h */ FT_EXPORT_DEF( void ) FT_Matrix_Multiply( const FT_Matrix* a, FT_Matrix *b ) { … } /* documentation is in ftglyph.h */ FT_EXPORT_DEF( FT_Error ) FT_Matrix_Invert( FT_Matrix* matrix ) { … } /* documentation is in ftcalc.h */ FT_BASE_DEF( void ) FT_Matrix_Multiply_Scaled( const FT_Matrix* a, FT_Matrix *b, FT_Long scaling ) { … } /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_Bool ) FT_Matrix_Check( const FT_Matrix* matrix ) { … } /* documentation is in ftcalc.h */ FT_BASE_DEF( void ) FT_Vector_Transform_Scaled( FT_Vector* vector, const FT_Matrix* matrix, FT_Long scaling ) { … } /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_UInt32 ) FT_Vector_NormLen( FT_Vector* vector ) { … } /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_UInt32 ) FT_SqrtFixed( FT_UInt32 v ) { … } /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_Int ) ft_corner_orientation( FT_Pos in_x, FT_Pos in_y, FT_Pos out_x, FT_Pos out_y ) { … } /* documentation is in ftcalc.h */ FT_BASE_DEF( FT_Int ) ft_corner_is_flat( FT_Pos in_x, FT_Pos in_y, FT_Pos out_x, FT_Pos out_y ) { … } FT_BASE_DEF( FT_Int32 ) FT_MulAddFix( FT_Fixed* s, FT_Int32* f, FT_UInt count ) { … } /* END */
Codebase Browser
chromium