1 /* Copyright (C) 2003 Aladdin Enterprises. All rights reserved. 2 3 This software is provided AS-IS with no warranty, either express or 4 implied. 5 6 This software is distributed under license and may not be copied, 7 modified or distributed except as expressly authorized under the terms 8 of the license contained in the file LICENSE in this distribution. 9 10 For more information about licensing, please refer to 11 http://www.ghostscript.com/licensing/. For information on 12 commercial licensing, go to http://www.artifex.com/licensing/ or 13 contact Artifex Software, Inc., 101 Lucas Valley Road #110, 14 San Rafael, CA 94903, U.S.A., +1(415)492-9861. 15 */ 16 17 /* $Id: ttcalc.c,v 1.1 2003/10/01 13:44:56 igor Exp $ */ 18 19 /* Changes after FreeType: cut out the TrueType instruction interpreter. */ 20 21 /******************************************************************* 22 * 23 * ttcalc.c 24 * 25 * Arithmetic Computations (body). 26 * 27 * Copyright 1996-1998 by 28 * David Turner, Robert Wilhelm, and Werner Lemberg. 29 * 30 * This file is part of the FreeType project, and may only be used 31 * modified and distributed under the terms of the FreeType project 32 * license, LICENSE.TXT. By continuing to use, modify, or distribute 33 * this file you indicate that you have read the license and 34 * understand and accept it fully. 35 * 36 ******************************************************************/ 37 38 #include "ttmisc.h" 39 40 #include "ttcalc.h" 41 42 /* support for 1-complement arithmetic has been totally dropped in this */ 43 /* release. You can still write your own code if you need it.. */ 44 45 static const long Roots[63] = 46 { 47 1, 1, 2, 3, 4, 5, 8, 11, 48 16, 22, 32, 45, 64, 90, 128, 181, 49 256, 362, 512, 724, 1024, 1448, 2048, 2896, 50 4096, 5892, 8192, 11585, 16384, 23170, 32768, 46340, 51 52 65536, 92681, 131072, 185363, 262144, 370727, 53 524288, 741455, 1048576, 1482910, 2097152, 2965820, 54 4194304, 5931641, 8388608, 11863283, 16777216, 23726566, 55 56 33554432, 47453132, 67108864, 94906265, 57 134217728, 189812531, 268435456, 379625062, 58 536870912, 759250125, 1073741824, 1518500250, 59 2147483647 60 }; 61 62 63 #ifdef LONG64 64 MulDiv(Int32 a,Int32 b,Int32 c)65 Int32 MulDiv( Int32 a, Int32 b, Int32 c ) 66 { 67 Int32 s; 68 69 s = a; a = ABS(a); 70 s ^= b; b = ABS(b); 71 s ^= c; c = ABS(c); 72 73 a = (Int64)a * b / c; 74 return ((s < 0) ? -a : a); 75 } 76 77 MulDiv_Round(Int32 a,Int32 b,Int32 c)78 Int32 MulDiv_Round( Int32 a, Int32 b, Int32 c ) 79 { 80 int s; 81 82 s = a; a = ABS(a); 83 s ^= b; b = ABS(b); 84 s ^= c; c = ABS(c); 85 86 a = ((Int64)a * b + c/2) / c; 87 return ((s < 0) ? -a : a); 88 } 89 90 Order64(Int64 z)91 Int Order64( Int64 z ) 92 { 93 int j = 0; 94 while ( z ) 95 { 96 z = (unsigned INT64)z >> 1; 97 j++; 98 } 99 return j - 1; 100 } 101 102 Sqrt64(Int64 l)103 Int32 Sqrt64( Int64 l ) 104 { 105 Int64 r, s; 106 107 if ( l <= 0 ) return 0; 108 if ( l == 1 ) return 1; 109 110 r = Roots[Order64( l )]; 111 112 do 113 { 114 s = r; 115 r = ( r + l/r ) >> 1; 116 } 117 while ( r > s || r*r > l ); 118 119 return r; 120 } 121 122 #else /* LONG64 */ 123 MulDiv(Int32 a,Int32 b,Int32 c)124 Int32 MulDiv( Int32 a, Int32 b, Int32 c ) 125 { 126 Int64 temp; 127 Int32 s; 128 129 s = a; a = ABS(a); 130 s ^= b; b = ABS(b); 131 s ^= c; c = ABS(c); 132 133 MulTo64( a, b, &temp ); 134 a = Div64by32( &temp, c ); 135 136 return ((s < 0) ? -a : a); 137 } 138 139 MulDiv_Round(Int32 a,Int32 b,Int32 c)140 Int32 MulDiv_Round( Int32 a, Int32 b, Int32 c ) 141 { 142 Int64 temp, temp2; 143 Int32 s; 144 145 s = a; a = ABS(a); 146 s ^= b; b = ABS(b); 147 s ^= c; c = ABS(c); 148 149 MulTo64( a, b, &temp ); 150 temp2.hi = (Int32)(c >> 31); 151 temp2.lo = (Word32)(c / 2); 152 Add64( &temp, &temp2, &temp ); 153 a = Div64by32( &temp, c ); 154 155 return ((s < 0) ? -a : a); 156 } 157 158 Neg64__(Int64 * x)159 static void Neg64__( Int64* x ) 160 { 161 /* Remember that -(0x80000000) == 0x80000000 with 2-complement! */ 162 /* We take care of that here. */ 163 164 x->hi ^= 0xFFFFFFFF; 165 x->lo ^= 0xFFFFFFFF; 166 x->lo++; 167 168 if ( !x->lo ) 169 { 170 x->hi++; 171 if ( (Int32)x->hi == 0x80000000 ) /* Check -MaxInt32 - 1 */ 172 { 173 x->lo--; 174 x->hi--; /* We return 0x7FFFFFFF! */ 175 } 176 } 177 } 178 179 Add64(Int64 * x,Int64 * y,Int64 * z)180 void Add64( Int64* x, Int64* y, Int64* z ) 181 { 182 register Word32 lo, hi; 183 184 hi = x->hi + y->hi; 185 lo = x->lo + y->lo; 186 187 if ( y->lo ) 188 if ( (Word32)x->lo >= (Word32)(-y->lo) ) hi++; 189 190 z->lo = lo; 191 z->hi = hi; 192 } 193 194 Sub64(Int64 * x,Int64 * y,Int64 * z)195 void Sub64( Int64* x, Int64* y, Int64* z ) 196 { 197 register Word32 lo, hi; 198 199 hi = x->hi - y->hi; 200 lo = x->lo - y->lo; 201 202 if ( x->lo < y->lo ) hi--; 203 204 z->lo = lo; 205 z->hi = hi; 206 } 207 208 MulTo64(Int32 x,Int32 y,Int64 * z)209 void MulTo64( Int32 x, Int32 y, Int64* z ) 210 { 211 Int32 s; 212 Word32 lo1, hi1, lo2, hi2, lo, hi, i1, i2; 213 214 s = x; x = ABS(x); 215 s ^= y; y = ABS(y); 216 217 lo1 = x & 0x0000FFFF; hi1 = x >> 16; 218 lo2 = y & 0x0000FFFF; hi2 = y >> 16; 219 220 lo = lo1*lo2; 221 i1 = lo1*hi2; 222 i2 = lo2*hi1; 223 hi = hi1*hi2; 224 225 /* Check carry overflow of i1 + i2 */ 226 227 if ( i2 ) 228 { 229 if ( i1 >= (Word32)-i2 ) hi += 1 << 16; 230 i1 += i2; 231 } 232 233 i2 = i1 >> 16; 234 i1 = i1 << 16; 235 236 /* Check carry overflow of i1 + lo */ 237 if ( i1 ) 238 { 239 if ( lo >= (Word32)-i1 ) hi++; 240 lo += i1; 241 } 242 243 hi += i2; 244 245 z->lo = lo; 246 z->hi = hi; 247 248 if (s < 0) Neg64__( z ); 249 } 250 251 Div64by32(Int64 * x,Int32 y)252 Int32 Div64by32( Int64* x, Int32 y ) 253 { 254 Int32 s; 255 Word32 q, r, i, lo; 256 257 s = x->hi; if (s<0) Neg64__(x); 258 s ^= y; y = ABS(y); 259 260 /* Shortcut */ 261 if ( x->hi == 0 ) 262 { 263 q = x->lo / y; 264 return ((s<0) ? -q : q); 265 } 266 267 r = x->hi; 268 lo = x->lo; 269 270 if ( r >= (Word32)y ) /* we know y is to be treated as unsigned here */ 271 return ( (s<0) ? 0x80000001 : 0x7FFFFFFF ); 272 /* Return Max/Min Int32 if divide overflow */ 273 /* This includes division by zero! */ 274 q = 0; 275 for ( i = 0; i < 32; i++ ) 276 { 277 r <<= 1; 278 q <<= 1; 279 r |= lo >> 31; 280 281 if ( r >= (Word32)y ) 282 { 283 r -= y; 284 q |= 1; 285 } 286 lo <<= 1; 287 } 288 289 return ( (s<0) ? -q : q ); 290 } 291 292 Order64(Int64 * z)293 Int Order64( Int64* z ) 294 { 295 Word32 i; 296 int j; 297 298 if ( z->hi ) 299 { 300 i = z->hi; 301 j = 32; 302 } 303 else 304 { 305 i = z->lo; 306 j = 0; 307 } 308 309 while ( i > 0 ) 310 { 311 i >>= 1; 312 j++; 313 } 314 return j-1; 315 } 316 317 Sqrt64(Int64 * l)318 Int32 Sqrt64( Int64* l ) 319 { 320 Int64 l2; 321 Int32 r, s; 322 323 if ( (Int32)l->hi < 0 || 324 (l->hi == 0 && l->lo == 0) ) return 0; 325 326 s = Order64( l ); 327 if ( s == 0 ) return 1; 328 329 r = Roots[s]; 330 do 331 { 332 s = r; 333 r = ( r + Div64by32(l,r) ) >> 1; 334 MulTo64( r, r, &l2 ); 335 Sub64 ( l, &l2, &l2 ); 336 } 337 while ( r > s || (Int32)l2.hi < 0 ); 338 339 return r; 340 } 341 342 #endif /* LONG64 */ 343 344 #if 0 /* unused by the rest of the library */ 345 346 Int Order32( Int32 z ) 347 { 348 int j; 349 350 j = 0; 351 while ( z ) 352 { 353 z = (Word32)z >> 1; 354 j++; 355 } 356 return j - 1; 357 } 358 359 360 Int32 Sqrt32( Int32 l ) 361 { 362 Int32 r, s; 363 364 if ( l <= 0 ) return 0; 365 if ( l == 1 ) return 1; 366 367 r = Roots[Order32( l )]; 368 do 369 { 370 s = r; 371 r = ( r + l/r ) >> 1; 372 } 373 while ( r > s || r*r > l ); 374 return r; 375 } 376 377 #endif 378 379 /* END */ 380