--- /dev/null
+/***************************************************************************/
+/* */
+/* ftcalc.c */
+/* */
+/* Arithmetic computations (body). */
+/* */
+/* Copyright 1996-2001, 2002 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 <ft2build.h>
+#include FT_INTERNAL_CALC_H
+#include FT_INTERNAL_DEBUG_H
+#include FT_INTERNAL_OBJECTS_H
+
+
+/* we need to define a 64-bits data type here */
+
+#ifdef FT_LONG64
+
+ typedef FT_INT64 FT_Int64;
+
+#else
+
+ typedef struct FT_Int64_
+ {
+ FT_UInt32 lo;
+ FT_UInt32 hi;
+
+ } FT_Int64;
+
+#endif /* FT_LONG64 */
+
+
+ /*************************************************************************/
+ /* */
+ /* 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 trace_calc
+
+
+ /* The following three functions are available regardless of whether */
+ /* FT_LONG64 is defined. */
+
+ /* documentation is in freetype.h */
+
+ FT_EXPORT_DEF( FT_Fixed )
+ FT_RoundFix( FT_Fixed a )
+ {
+ return ( a >= 0 ) ? ( a + 0x8000L ) & -0x10000L
+ : -((-a + 0x8000L ) & -0x10000L );
+ }
+
+
+ /* documentation is in freetype.h */
+
+ FT_EXPORT_DEF( FT_Fixed )
+ FT_CeilFix( FT_Fixed a )
+ {
+ return ( a >= 0 ) ? ( a + 0xFFFFL ) & -0x10000L
+ : -((-a + 0xFFFFL ) & -0x10000L );
+ }
+
+
+ /* documentation is in freetype.h */
+
+ FT_EXPORT_DEF( FT_Fixed )
+ FT_FloorFix( FT_Fixed a )
+ {
+ return ( a >= 0 ) ? a & -0x10000L
+ : -((-a) & -0x10000L );
+ }
+
+
+ /* documentation is in ftcalc.h */
+
+ FT_EXPORT_DEF( FT_Int32 )
+ FT_Sqrt32( FT_Int32 x )
+ {
+ FT_ULong val, root, newroot, mask;
+
+
+ root = 0;
+ mask = 0x40000000L;
+ val = (FT_ULong)x;
+
+ do
+ {
+ newroot = root + mask;
+ if ( newroot <= val )
+ {
+ val -= newroot;
+ root = newroot + mask;
+ }
+
+ root >>= 1;
+ mask >>= 2;
+
+ } while ( mask != 0 );
+
+ return root;
+ }
+
+
+#ifdef FT_LONG64
+
+
+ /* documentation is in freetype.h */
+
+ FT_EXPORT_DEF( FT_Long )
+ FT_MulDiv( FT_Long a,
+ FT_Long b,
+ FT_Long c )
+ {
+ FT_Int s;
+ 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; }
+
+ d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c
+ : 0x7FFFFFFFL );
+
+ return ( s > 0 ) ? d : -d;
+ }
+
+
+ /* documentation is in freetype.h */
+
+ FT_EXPORT_DEF( FT_Long )
+ FT_MulFix( FT_Long a,
+ FT_Long b )
+ {
+ FT_Int s = 1;
+ FT_Long c;
+
+
+ if ( a < 0 ) { a = -a; s = -1; }
+ if ( b < 0 ) { b = -b; s = -s; }
+
+ c = (FT_Long)( ( (FT_Int64)a * b + 0x8000 ) >> 16 );
+ return ( s > 0 ) ? c : -c ;
+ }
+
+
+ /* documentation is in freetype.h */
+
+ FT_EXPORT_DEF( FT_Long )
+ FT_DivFix( FT_Long a,
+ FT_Long b )
+ {
+ FT_Int32 s;
+ FT_UInt32 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 );
+
+ return ( s < 0 ? -(FT_Long)q : (FT_Long)q );
+ }
+
+
+#else /* FT_LONG64 */
+
+
+ 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;
+
+
+ q = 0;
+ r = hi;
+
+ if ( r >= y )
+ return (FT_UInt32)0x7FFFFFFFL;
+
+ i = 32;
+ do
+ {
+ r <<= 1;
+ q <<= 1;
+ r |= lo >> 31;
+
+ if ( r >= (FT_UInt32)y )
+ {
+ r -= y;
+ q |= 1;
+ }
+ lo <<= 1;
+ } while ( --i );
+
+ return q;
+ }
+
+
+ /* documentation is in ftcalc.h */
+
+ FT_EXPORT_DEF( void )
+ FT_Add64( FT_Int64* x,
+ FT_Int64* y,
+ FT_Int64 *z )
+ {
+ register FT_UInt32 lo, hi, max;
+
+
+ max = x->lo > y->lo ? x->lo : y->lo;
+ lo = x->lo + y->lo;
+ hi = x->hi + y->hi + ( lo < max );
+
+ z->lo = lo;
+ z->hi = hi;
+ }
+
+
+ /* documentation is in freetype.h */
+
+ FT_EXPORT_DEF( FT_Long )
+ FT_MulDiv( FT_Long a,
+ FT_Long b,
+ FT_Long c )
+ {
+ long s;
+
+
+ if ( a == 0 || b == c )
+ return a;
+
+ s = a; a = ABS( a );
+ s ^= b; b = ABS( b );
+ s ^= c; c = ABS( c );
+
+ if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 )
+ {
+ a = ( a * b + ( c >> 1 ) ) / c;
+ }
+ else if ( c > 0 )
+ {
+ FT_Int64 temp, temp2;
+
+
+ ft_multo64( a, b, &temp );
+
+ temp2.hi = 0;
+ temp2.lo = (FT_UInt32)(c >> 1);
+ FT_Add64( &temp, &temp2, &temp );
+ a = ft_div64by32( temp.hi, temp.lo, c );
+ }
+ else
+ a = 0x7FFFFFFFL;
+
+ return ( s < 0 ? -a : a );
+ }
+
+
+ /* documentation is in freetype.h */
+
+ FT_EXPORT_DEF( FT_Long )
+ FT_MulFix( FT_Long a,
+ FT_Long b )
+ {
+ FT_Long s;
+ FT_ULong ua, ub;
+
+
+ if ( a == 0 || b == 0x10000L )
+ return a;
+
+ s = a; a = ABS(a);
+ s ^= b; b = ABS(b);
+
+ ua = (FT_ULong)a;
+ ub = (FT_ULong)b;
+
+ if ( ua <= 2048 && ub <= 1048576L )
+ {
+ ua = ( ua * ub + 0x8000 ) >> 16;
+ }
+ else
+ {
+ FT_ULong al = ua & 0xFFFF;
+
+
+ ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) +
+ ( ( al * ( ub & 0xFFFF ) + 0x8000 ) >> 16 );
+ }
+
+ return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua );
+ }
+
+
+ /* documentation is in freetype.h */
+
+ FT_EXPORT_DEF( FT_Long )
+ FT_DivFix( FT_Long a,
+ FT_Long b )
+ {
+ FT_Int32 s;
+ FT_UInt32 q;
+
+
+ s = a; a = ABS(a);
+ s ^= b; b = ABS(b);
+
+ if ( b == 0 )
+ {
+ /* check for division by 0 */
+ q = 0x7FFFFFFFL;
+ }
+ else if ( ( a >> 16 ) == 0 )
+ {
+ /* compute result directly */
+ q = (FT_UInt32)( (a << 16) + (b >> 1) ) / (FT_UInt32)b;
+ }
+ else
+ {
+ /* we need more bits; we have to do it by hand */
+ FT_Int64 temp, temp2;
+
+ temp.hi = (FT_Int32) (a >> 16);
+ temp.lo = (FT_UInt32)(a << 16);
+ temp2.hi = 0;
+ temp2.lo = (FT_UInt32)( b >> 1 );
+ FT_Add64( &temp, &temp2, &temp );
+ q = ft_div64by32( temp.hi, temp.lo, b );
+ }
+
+ return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
+ }
+
+
+ /* 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 = ABS( x );
+ s ^= y; y = ABS( y );
+
+ ft_multo64( x, y, z );
+
+ if ( s < 0 )
+ {
+ z->lo = (FT_UInt32)-(FT_Int32)z->lo;
+ z->hi = ~z->hi + !( z->lo );
+ }
+ }
+
+
+ /* documentation is in ftcalc.h */
+
+ /* apparently, the second version of this code is not compiled correctly */
+ /* on Mac machines with the MPW C compiler.. tsss, tsss, tss... */
+
+#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 = 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 = 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 );
+ }
+
+ q = ft_div64by32( x->hi, x->lo, y );
+
+ return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
+ }
+
+#endif /* 0 */
+
+
+#endif /* FT_LONG64 */
+
+
+ /* a not-so-fast but working 16.16 fixed point square root function */
+
+ FT_EXPORT_DEF( FT_Int32 )
+ FT_SqrtFixed( FT_Int32 x )
+ {
+ FT_UInt32 root, rem_hi, rem_lo, test_div;
+ FT_Int count;
+
+
+ root = 0;
+
+ if ( x > 0 )
+ {
+ rem_hi = 0;
+ rem_lo = x;
+ count = 24;
+ do
+ {
+ rem_hi = ( rem_hi << 2 ) | ( rem_lo >> 30 );
+ rem_lo <<= 2;
+ root <<= 1;
+ test_div = ( root << 1 ) + 1;
+
+ if ( rem_hi >= test_div )
+ {
+ rem_hi -= test_div;
+ root += 1;
+ }
+ } while ( --count );
+ }
+
+ return (FT_Int32)root;
+ }
+
+
+/* END */
git://git.jankratochvil.net / reactos.git / blobdiff