1 /***************************************************************************/ 2 /* */ 3 /* ftcalc.c */ 4 /* */ 5 /* Arithmetic computations (body). */ 6 /* */ 7 /* Copyright 1996-2001, 2002 by */ 8 /* David Turner, Robert Wilhelm, and Werner Lemberg. */ 9 /* */ 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. */ 15 /* */ 16 /***************************************************************************/ 17 18 /*************************************************************************/ 19 /* */ 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. */ 22 /* */ 23 /*************************************************************************/ 24 25 /*************************************************************************/ 26 /* */ 27 /* Implementing basic computation routines. */ 28 /* */ 29 /* FT_MulDiv(), FT_MulFix(), FT_DivFix(), FT_RoundFix(), FT_CeilFix(), */ 30 /* and FT_FloorFix() are declared in freetype.h. */ 31 /* */ 32 /*************************************************************************/ 33 34 35 #include <ft2build.h> 36 #include FT_INTERNAL_CALC_H 37 #include FT_INTERNAL_DEBUG_H 38 #include FT_INTERNAL_OBJECTS_H 39 40 41 /* we need to define a 64-bits data type here */ 42 43 #ifdef FT_LONG64 44 45 typedef FT_INT64 FT_Int64; 46 47 #else 48 49 typedef struct FT_Int64_ 50 { 51 FT_UInt32 lo; 52 FT_UInt32 hi; 53 54 } FT_Int64; 55 56 #endif /* FT_LONG64 */ 57 58 59 /*************************************************************************/ 60 /* */ 61 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */ 62 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */ 63 /* messages during execution. */ 64 /* */ 65 #undef FT_COMPONENT 66 #define FT_COMPONENT trace_calc 67 68 69 /* The following three functions are available regardless of whether */ 70 /* FT_LONG64 is defined. */ 71 72 /* documentation is in freetype.h */ 73 74 FT_EXPORT_DEF( FT_Fixed ) FT_RoundFix(FT_Fixed a)75 FT_RoundFix( FT_Fixed a ) 76 { 77 return ( a >= 0 ) ? ( a + 0x8000L ) & -0x10000L 78 : -((-a + 0x8000L ) & -0x10000L ); 79 } 80 81 82 /* documentation is in freetype.h */ 83 84 FT_EXPORT_DEF( FT_Fixed ) FT_CeilFix(FT_Fixed a)85 FT_CeilFix( FT_Fixed a ) 86 { 87 return ( a >= 0 ) ? ( a + 0xFFFFL ) & -0x10000L 88 : -((-a + 0xFFFFL ) & -0x10000L ); 89 } 90 91 92 /* documentation is in freetype.h */ 93 94 FT_EXPORT_DEF( FT_Fixed ) FT_FloorFix(FT_Fixed a)95 FT_FloorFix( FT_Fixed a ) 96 { 97 return ( a >= 0 ) ? a & -0x10000L 98 : -((-a) & -0x10000L ); 99 } 100 101 102 /* documentation is in ftcalc.h */ 103 104 FT_EXPORT_DEF( FT_Int32 ) FT_Sqrt32(FT_Int32 x)105 FT_Sqrt32( FT_Int32 x ) 106 { 107 FT_ULong val, root, newroot, mask; 108 109 110 root = 0; 111 mask = 0x40000000L; 112 val = (FT_ULong)x; 113 114 do 115 { 116 newroot = root + mask; 117 if ( newroot <= val ) 118 { 119 val -= newroot; 120 root = newroot + mask; 121 } 122 123 root >>= 1; 124 mask >>= 2; 125 126 } while ( mask != 0 ); 127 128 return root; 129 } 130 131 132 #ifdef FT_LONG64 133 134 135 /* documentation is in freetype.h */ 136 137 FT_EXPORT_DEF( FT_Long ) FT_MulDiv(FT_Long a,FT_Long b,FT_Long c)138 FT_MulDiv( FT_Long a, 139 FT_Long b, 140 FT_Long c ) 141 { 142 FT_Int s; 143 FT_Long d; 144 145 146 s = 1; 147 if ( a < 0 ) { a = -a; s = -1; } 148 if ( b < 0 ) { b = -b; s = -s; } 149 if ( c < 0 ) { c = -c; s = -s; } 150 151 d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c 152 : 0x7FFFFFFFL ); 153 154 return ( s > 0 ) ? d : -d; 155 } 156 157 158 /* documentation is in freetype.h */ 159 160 FT_EXPORT_DEF( FT_Long ) FT_MulFix(FT_Long a,FT_Long b)161 FT_MulFix( FT_Long a, 162 FT_Long b ) 163 { 164 FT_Int s = 1; 165 FT_Long c; 166 167 168 if ( a < 0 ) { a = -a; s = -1; } 169 if ( b < 0 ) { b = -b; s = -s; } 170 171 c = (FT_Long)( ( (FT_Int64)a * b + 0x8000 ) >> 16 ); 172 return ( s > 0 ) ? c : -c ; 173 } 174 175 176 /* documentation is in freetype.h */ 177 178 FT_EXPORT_DEF( FT_Long ) FT_DivFix(FT_Long a,FT_Long b)179 FT_DivFix( FT_Long a, 180 FT_Long b ) 181 { 182 FT_Int32 s; 183 FT_UInt32 q; 184 185 s = 1; 186 if ( a < 0 ) { a = -a; s = -1; } 187 if ( b < 0 ) { b = -b; s = -s; } 188 189 if ( b == 0 ) 190 /* check for division by 0 */ 191 q = 0x7FFFFFFFL; 192 else 193 /* compute result directly */ 194 q = (FT_UInt32)( ( ( (FT_Int64)a << 16 ) + ( b >> 1 ) ) / b ); 195 196 return ( s < 0 ? -(FT_Long)q : (FT_Long)q ); 197 } 198 199 200 #else /* FT_LONG64 */ 201 202 203 static void ft_multo64(FT_UInt32 x,FT_UInt32 y,FT_Int64 * z)204 ft_multo64( FT_UInt32 x, 205 FT_UInt32 y, 206 FT_Int64 *z ) 207 { 208 FT_UInt32 lo1, hi1, lo2, hi2, lo, hi, i1, i2; 209 210 211 lo1 = x & 0x0000FFFFU; hi1 = x >> 16; 212 lo2 = y & 0x0000FFFFU; hi2 = y >> 16; 213 214 lo = lo1 * lo2; 215 i1 = lo1 * hi2; 216 i2 = lo2 * hi1; 217 hi = hi1 * hi2; 218 219 /* Check carry overflow of i1 + i2 */ 220 i1 += i2; 221 hi += (FT_UInt32)( i1 < i2 ) << 16; 222 223 hi += i1 >> 16; 224 i1 = i1 << 16; 225 226 /* Check carry overflow of i1 + lo */ 227 lo += i1; 228 hi += ( lo < i1 ); 229 230 z->lo = lo; 231 z->hi = hi; 232 } 233 234 235 static FT_UInt32 ft_div64by32(FT_UInt32 hi,FT_UInt32 lo,FT_UInt32 y)236 ft_div64by32( FT_UInt32 hi, 237 FT_UInt32 lo, 238 FT_UInt32 y ) 239 { 240 FT_UInt32 r, q; 241 FT_Int i; 242 243 244 q = 0; 245 r = hi; 246 247 if ( r >= y ) 248 return (FT_UInt32)0x7FFFFFFFL; 249 250 i = 32; 251 do 252 { 253 r <<= 1; 254 q <<= 1; 255 r |= lo >> 31; 256 257 if ( r >= (FT_UInt32)y ) 258 { 259 r -= y; 260 q |= 1; 261 } 262 lo <<= 1; 263 } while ( --i ); 264 265 return q; 266 } 267 268 269 /* documentation is in ftcalc.h */ 270 271 FT_EXPORT_DEF( void ) FT_Add64(FT_Int64 * x,FT_Int64 * y,FT_Int64 * z)272 FT_Add64( FT_Int64* x, 273 FT_Int64* y, 274 FT_Int64 *z ) 275 { 276 register FT_UInt32 lo, hi, max; 277 278 279 max = x->lo > y->lo ? x->lo : y->lo; 280 lo = x->lo + y->lo; 281 hi = x->hi + y->hi + ( lo < max ); 282 283 z->lo = lo; 284 z->hi = hi; 285 } 286 287 288 /* documentation is in freetype.h */ 289 290 FT_EXPORT_DEF( FT_Long ) FT_MulDiv(FT_Long a,FT_Long b,FT_Long c)291 FT_MulDiv( FT_Long a, 292 FT_Long b, 293 FT_Long c ) 294 { 295 long s; 296 297 298 if ( a == 0 || b == c ) 299 return a; 300 301 s = a; a = ABS( a ); 302 s ^= b; b = ABS( b ); 303 s ^= c; c = ABS( c ); 304 305 if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 ) 306 { 307 a = ( a * b + ( c >> 1 ) ) / c; 308 } 309 else if ( c > 0 ) 310 { 311 FT_Int64 temp, temp2; 312 313 314 ft_multo64( a, b, &temp ); 315 316 temp2.hi = 0; 317 temp2.lo = (FT_UInt32)(c >> 1); 318 FT_Add64( &temp, &temp2, &temp ); 319 a = ft_div64by32( temp.hi, temp.lo, c ); 320 } 321 else 322 a = 0x7FFFFFFFL; 323 324 return ( s < 0 ? -a : a ); 325 } 326 327 328 /* documentation is in freetype.h */ 329 330 FT_EXPORT_DEF( FT_Long ) FT_MulFix(FT_Long a,FT_Long b)331 FT_MulFix( FT_Long a, 332 FT_Long b ) 333 { 334 FT_Long s; 335 FT_ULong ua, ub; 336 337 338 if ( a == 0 || b == 0x10000L ) 339 return a; 340 341 s = a; a = ABS(a); 342 s ^= b; b = ABS(b); 343 344 ua = (FT_ULong)a; 345 ub = (FT_ULong)b; 346 347 if ( ua <= 2048 && ub <= 1048576L ) 348 { 349 ua = ( ua * ub + 0x8000 ) >> 16; 350 } 351 else 352 { 353 FT_ULong al = ua & 0xFFFF; 354 355 356 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + 357 ( ( al * ( ub & 0xFFFF ) + 0x8000 ) >> 16 ); 358 } 359 360 return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua ); 361 } 362 363 364 /* documentation is in freetype.h */ 365 366 FT_EXPORT_DEF( FT_Long ) FT_DivFix(FT_Long a,FT_Long b)367 FT_DivFix( FT_Long a, 368 FT_Long b ) 369 { 370 FT_Int32 s; 371 FT_UInt32 q; 372 373 374 s = a; a = ABS(a); 375 s ^= b; b = ABS(b); 376 377 if ( b == 0 ) 378 { 379 /* check for division by 0 */ 380 q = 0x7FFFFFFFL; 381 } 382 else if ( ( a >> 16 ) == 0 ) 383 { 384 /* compute result directly */ 385 q = (FT_UInt32)( (a << 16) + (b >> 1) ) / (FT_UInt32)b; 386 } 387 else 388 { 389 /* we need more bits; we have to do it by hand */ 390 FT_Int64 temp, temp2; 391 392 temp.hi = (FT_Int32) (a >> 16); 393 temp.lo = (FT_UInt32)(a << 16); 394 temp2.hi = 0; 395 temp2.lo = (FT_UInt32)( b >> 1 ); 396 FT_Add64( &temp, &temp2, &temp ); 397 q = ft_div64by32( temp.hi, temp.lo, b ); 398 } 399 400 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 401 } 402 403 404 /* documentation is in ftcalc.h */ 405 406 FT_EXPORT_DEF( void ) FT_MulTo64(FT_Int32 x,FT_Int32 y,FT_Int64 * z)407 FT_MulTo64( FT_Int32 x, 408 FT_Int32 y, 409 FT_Int64 *z ) 410 { 411 FT_Int32 s; 412 413 414 s = x; x = ABS( x ); 415 s ^= y; y = ABS( y ); 416 417 ft_multo64( x, y, z ); 418 419 if ( s < 0 ) 420 { 421 z->lo = (FT_UInt32)-(FT_Int32)z->lo; 422 z->hi = ~z->hi + !( z->lo ); 423 } 424 } 425 426 427 /* documentation is in ftcalc.h */ 428 429 /* apparently, the second version of this code is not compiled correctly */ 430 /* on Mac machines with the MPW C compiler.. tsss, tsss, tss... */ 431 432 #if 1 433 434 FT_EXPORT_DEF( FT_Int32 ) FT_Div64by32(FT_Int64 * x,FT_Int32 y)435 FT_Div64by32( FT_Int64* x, 436 FT_Int32 y ) 437 { 438 FT_Int32 s; 439 FT_UInt32 q, r, i, lo; 440 441 442 s = x->hi; 443 if ( s < 0 ) 444 { 445 x->lo = (FT_UInt32)-(FT_Int32)x->lo; 446 x->hi = ~x->hi + !x->lo; 447 } 448 s ^= y; y = ABS( y ); 449 450 /* Shortcut */ 451 if ( x->hi == 0 ) 452 { 453 if ( y > 0 ) 454 q = x->lo / y; 455 else 456 q = 0x7FFFFFFFL; 457 458 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 459 } 460 461 r = x->hi; 462 lo = x->lo; 463 464 if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */ 465 return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL ); 466 /* Return Max/Min Int32 if division overflow. */ 467 /* This includes division by zero! */ 468 q = 0; 469 for ( i = 0; i < 32; i++ ) 470 { 471 r <<= 1; 472 q <<= 1; 473 r |= lo >> 31; 474 475 if ( r >= (FT_UInt32)y ) 476 { 477 r -= y; 478 q |= 1; 479 } 480 lo <<= 1; 481 } 482 483 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 484 } 485 486 #else /* 0 */ 487 488 FT_EXPORT_DEF( FT_Int32 ) FT_Div64by32(FT_Int64 * x,FT_Int32 y)489 FT_Div64by32( FT_Int64* x, 490 FT_Int32 y ) 491 { 492 FT_Int32 s; 493 FT_UInt32 q; 494 495 496 s = x->hi; 497 if ( s < 0 ) 498 { 499 x->lo = (FT_UInt32)-(FT_Int32)x->lo; 500 x->hi = ~x->hi + !x->lo; 501 } 502 s ^= y; y = ABS( y ); 503 504 /* Shortcut */ 505 if ( x->hi == 0 ) 506 { 507 if ( y > 0 ) 508 q = ( x->lo + ( y >> 1 ) ) / y; 509 else 510 q = 0x7FFFFFFFL; 511 512 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 513 } 514 515 q = ft_div64by32( x->hi, x->lo, y ); 516 517 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 518 } 519 520 #endif /* 0 */ 521 522 523 #endif /* FT_LONG64 */ 524 525 526 /* a not-so-fast but working 16.16 fixed point square root function */ 527 528 FT_EXPORT_DEF( FT_Int32 ) FT_SqrtFixed(FT_Int32 x)529 FT_SqrtFixed( FT_Int32 x ) 530 { 531 FT_UInt32 root, rem_hi, rem_lo, test_div; 532 FT_Int count; 533 534 535 root = 0; 536 537 if ( x > 0 ) 538 { 539 rem_hi = 0; 540 rem_lo = x; 541 count = 24; 542 do 543 { 544 rem_hi = ( rem_hi << 2 ) | ( rem_lo >> 30 ); 545 rem_lo <<= 2; 546 root <<= 1; 547 test_div = ( root << 1 ) + 1; 548 549 if ( rem_hi >= test_div ) 550 { 551 rem_hi -= test_div; 552 root += 1; 553 } 554 } while ( --count ); 555 } 556 557 return (FT_Int32)root; 558 } 559 560 561 /* END */ 562