1 /***************************************************************************/
5 /* Arithmetic computations (body). */
7 /* Copyright 1996-2001 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 /*************************************************************************/
36 #include FT_INTERNAL_CALC_H
37 #include FT_INTERNAL_DEBUG_H
38 #include FT_INTERNAL_OBJECTS_H
41 /* we need to define a 64-bits data type here */
42 #ifndef FT_CONFIG_OPTION_OLD_CALCS
46 typedef FT_INT64 FT_Int64;
50 typedef struct FT_Int64_
57 #endif /* FT_LONG64 */
59 #endif /* !FT_CONFIG_OPTION_OLD_CALCS */
62 /*************************************************************************/
64 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */
65 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */
66 /* messages during execution. */
69 #define FT_COMPONENT trace_calc
72 /* The following three functions are available regardless of whether */
73 /* FT_LONG64 or FT_CONFIG_OPTION_OLD_CALCS is defined. */
75 /* documentation is in freetype.h */
77 FT_EXPORT_DEF( FT_Fixed )
78 FT_RoundFix( FT_Fixed a )
80 return ( a >= 0 ) ? ( a + 0x8000L ) & -0x10000L
81 : -((-a + 0x8000L ) & -0x10000L );
85 /* documentation is in freetype.h */
87 FT_EXPORT_DEF( FT_Fixed )
88 FT_CeilFix( FT_Fixed a )
90 return ( a >= 0 ) ? ( a + 0xFFFFL ) & -0x10000L
91 : -((-a + 0xFFFFL ) & -0x10000L );
95 /* documentation is in freetype.h */
97 FT_EXPORT_DEF( FT_Fixed )
98 FT_FloorFix( FT_Fixed a )
100 return ( a >= 0 ) ? a & -0x10000L
101 : -((-a) & -0x10000L );
105 #ifdef FT_CONFIG_OPTION_OLD_CALCS
107 static const FT_Long ft_square_roots[63] =
109 1L, 1L, 2L, 3L, 4L, 5L, 8L, 11L,
110 16L, 22L, 32L, 45L, 64L, 90L, 128L, 181L,
111 256L, 362L, 512L, 724L, 1024L, 1448L, 2048L, 2896L,
112 4096L, 5892L, 8192L, 11585L, 16384L, 23170L, 32768L, 46340L,
114 65536L, 92681L, 131072L, 185363L, 262144L, 370727L,
115 524288L, 741455L, 1048576L, 1482910L, 2097152L, 2965820L,
116 4194304L, 5931641L, 8388608L, 11863283L, 16777216L, 23726566L,
118 33554432L, 47453132L, 67108864L, 94906265L,
119 134217728L, 189812531L, 268435456L, 379625062L,
120 536870912L, 759250125L, 1073741824L, 1518500250L,
126 /* documentation is in ftcalc.h */
128 FT_EXPORT_DEF( FT_Int32 )
129 FT_Sqrt32( FT_Int32 x )
131 FT_ULong val, root, newroot, mask;
140 newroot = root + mask;
141 if ( newroot <= val )
144 root = newroot + mask;
150 } while ( mask != 0 );
155 #endif /* FT_CONFIG_OPTION_OLD_CALCS */
160 /* documentation is in freetype.h */
162 FT_EXPORT_DEF( FT_Long )
163 FT_MulDiv( FT_Long a,
172 if ( a < 0 ) { a = -a; s = -1; }
173 if ( b < 0 ) { b = -b; s = -s; }
174 if ( c < 0 ) { c = -c; s = -s; }
176 d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c
179 return ( s > 0 ) ? d : -d;
183 /* documentation is in freetype.h */
185 FT_EXPORT_DEF( FT_Long )
186 FT_MulFix( FT_Long a,
193 if ( a < 0 ) { a = -a; s = -1; }
194 if ( b < 0 ) { b = -b; s = -s; }
196 c = (FT_Long)( ( (FT_Int64)a * b + 0x8000 ) >> 16 );
197 return ( s > 0 ) ? c : -c ;
201 /* documentation is in freetype.h */
203 FT_EXPORT_DEF( FT_Long )
204 FT_DivFix( FT_Long a,
211 if ( a < 0 ) { a = -a; s = -1; }
212 if ( b < 0 ) { b = -b; s = -s; }
215 /* check for division by 0 */
218 /* compute result directly */
219 q = (FT_UInt32)( ( ( (FT_Int64)a << 16 ) + ( b >> 1 ) ) / b );
221 return ( s < 0 ? -(FT_Long)q : (FT_Long)q );
225 #ifdef FT_CONFIG_OPTION_OLD_CALCS
227 /* a helper function for FT_Sqrt64() */
230 ft_order64( FT_Int64 z )
237 z = (unsigned FT_INT64)z >> 1;
244 /* documentation is in ftcalc.h */
246 FT_EXPORT_DEF( FT_Int32 )
247 FT_Sqrt64( FT_Int64 l )
252 if ( l <= 0 ) return 0;
253 if ( l == 1 ) return 1;
255 r = ft_square_roots[ft_order64( l )];
260 r = ( r + l / r ) >> 1;
262 } while ( r > s || r * r > l );
267 #endif /* FT_CONFIG_OPTION_OLD_CALCS */
270 #else /* FT_LONG64 */
274 ft_multo64( FT_UInt32 x,
278 FT_UInt32 lo1, hi1, lo2, hi2, lo, hi, i1, i2;
281 lo1 = x & 0x0000FFFFU; hi1 = x >> 16;
282 lo2 = y & 0x0000FFFFU; hi2 = y >> 16;
289 /* Check carry overflow of i1 + i2 */
291 hi += (FT_UInt32)( i1 < i2 ) << 16;
296 /* Check carry overflow of i1 + lo */
306 ft_div64by32( FT_UInt32 hi,
318 return (FT_UInt32)0x7FFFFFFFL;
327 if ( r >= (FT_UInt32)y )
339 /* documentation is in ftcalc.h */
341 FT_EXPORT_DEF( void )
342 FT_Add64( FT_Int64* x,
346 register FT_UInt32 lo, hi, max;
349 max = x->lo > y->lo ? x->lo : y->lo;
351 hi = x->hi + y->hi + ( lo < max );
358 /* documentation is in freetype.h */
360 FT_EXPORT_DEF( FT_Long )
361 FT_MulDiv( FT_Long a,
368 if ( a == 0 || b == c )
372 s ^= b; b = ABS( b );
373 s ^= c; c = ABS( c );
375 if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 )
377 a = ( a * b + ( c >> 1 ) ) / c;
381 FT_Int64 temp, temp2;
384 ft_multo64( a, b, &temp );
387 temp2.lo = (FT_UInt32)(c >> 1);
388 FT_Add64( &temp, &temp2, &temp );
389 a = ft_div64by32( temp.hi, temp.lo, c );
394 return ( s < 0 ? -a : a );
398 /* documentation is in freetype.h */
400 FT_EXPORT_DEF( FT_Long )
401 FT_MulFix( FT_Long a,
408 if ( a == 0 || b == 0x10000L )
417 if ( ua <= 2048 && ub <= 1048576L )
419 ua = ( ua * ub + 0x8000 ) >> 16;
423 FT_ULong al = ua & 0xFFFF;
426 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) +
427 ( ( al * ( ub & 0xFFFF ) + 0x8000 ) >> 16 );
430 return ( s < 0 ? -(FT_Long)ua : ua );
434 /* documentation is in freetype.h */
436 FT_EXPORT_DEF( FT_Long )
437 FT_DivFix( FT_Long a,
449 /* check for division by 0 */
452 else if ( ( a >> 16 ) == 0 )
454 /* compute result directly */
455 q = (FT_UInt32)( (a << 16) + (b >> 1) ) / (FT_UInt32)b;
459 /* we need more bits; we have to do it by hand */
460 FT_Int64 temp, temp2;
462 temp.hi = (FT_Int32) (a >> 16);
463 temp.lo = (FT_UInt32)(a << 16);
465 temp2.lo = (FT_UInt32)( b >> 1 );
466 FT_Add64( &temp, &temp2, &temp );
467 q = ft_div64by32( temp.hi, temp.lo, b );
470 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
474 /* documentation is in ftcalc.h */
476 FT_EXPORT_DEF( void )
477 FT_MulTo64( FT_Int32 x,
485 s ^= y; y = ABS( y );
487 ft_multo64( x, y, z );
491 z->lo = (FT_UInt32)-(FT_Int32)z->lo;
492 z->hi = ~z->hi + !( z->lo );
497 /* documentation is in ftcalc.h */
499 FT_EXPORT_DEF( FT_Int32 )
500 FT_Div64by32( FT_Int64* x,
510 x->lo = (FT_UInt32)-(FT_Int32)x->lo;
511 x->hi = ~x->hi + !( x->lo );
513 s ^= y; y = ABS( y );
519 q = ( x->lo + ( y >> 1 ) ) / y;
523 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
526 q = ft_div64by32( x->hi, x->lo, y );
528 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
532 #ifdef FT_CONFIG_OPTION_OLD_CALCS
535 /* two helper functions for FT_Sqrt64() */
538 FT_Sub64( FT_Int64* x,
542 register FT_UInt32 lo, hi;
546 hi = x->hi - y->hi - ( (FT_Int32)lo < 0 );
554 ft_order64( FT_Int64* z )
577 /* documentation is in ftcalc.h */
579 FT_EXPORT_DEF( FT_Int32 )
580 FT_Sqrt64( FT_Int64* l )
586 if ( (FT_Int32)l->hi < 0 ||
587 ( l->hi == 0 && l->lo == 0 ) )
594 r = ft_square_roots[s];
598 r = ( r + FT_Div64by32( l, r ) ) >> 1;
599 FT_MulTo64( r, r, &l2 );
600 FT_Sub64 ( l, &l2, &l2 );
602 } while ( r > s || (FT_Int32)l2.hi < 0 );
608 #endif /* FT_CONFIG_OPTION_OLD_CALCS */
611 #endif /* FT_LONG64 */
614 /* a not-so-fast but working 16.16 fixed point square root function */
616 FT_EXPORT_DEF( FT_Int32 )
617 FT_SqrtFixed( FT_Int32 x )
619 FT_UInt32 root, rem_hi, rem_lo, test_div;
632 rem_hi = ( rem_hi << 2 ) | ( rem_lo >> 30 );
635 test_div = ( root << 1 ) + 1;
637 if ( rem_hi >= test_div )
645 return (FT_Int32)root;