OLD | NEW |
| (Empty) |
1 /* | |
2 * Copyright (C) 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved. | |
3 * | |
4 * Redistribution and use in source and binary forms, with or without | |
5 * modification, are permitted provided that the following conditions | |
6 * are met: | |
7 * 1. Redistributions of source code must retain the above copyright | |
8 * notice, this list of conditions and the following disclaimer. | |
9 * 2. Redistributions in binary form must reproduce the above copyright | |
10 * notice, this list of conditions and the following disclaimer in the | |
11 * documentation and/or other materials provided with the distribution. | |
12 * | |
13 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY | |
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR | |
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | |
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | |
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | |
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | |
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
24 */ | |
25 | |
26 #ifndef WTF_MathExtras_h | |
27 #define WTF_MathExtras_h | |
28 | |
29 #include <algorithm> | |
30 #include <cmath> | |
31 #include <float.h> | |
32 #include <limits> | |
33 #include <stdint.h> | |
34 #include <stdlib.h> | |
35 #include <wtf/StdLibExtras.h> | |
36 | |
37 #if OS(SOLARIS) | |
38 #include <ieeefp.h> | |
39 #endif | |
40 | |
41 #if OS(OPENBSD) | |
42 #include <sys/types.h> | |
43 #include <machine/ieee.h> | |
44 #endif | |
45 | |
46 #if OS(QNX) | |
47 // FIXME: Look into a way to have cmath import its functions into both the stand
ard and global | |
48 // namespace. For now, we include math.h since the QNX cmath header only imports
its functions | |
49 // into the standard namespace. | |
50 #include <math.h> | |
51 #endif | |
52 | |
53 #ifndef M_PI | |
54 const double piDouble = 3.14159265358979323846; | |
55 const float piFloat = 3.14159265358979323846f; | |
56 #else | |
57 const double piDouble = M_PI; | |
58 const float piFloat = static_cast<float>(M_PI); | |
59 #endif | |
60 | |
61 #ifndef M_PI_2 | |
62 const double piOverTwoDouble = 1.57079632679489661923; | |
63 const float piOverTwoFloat = 1.57079632679489661923f; | |
64 #else | |
65 const double piOverTwoDouble = M_PI_2; | |
66 const float piOverTwoFloat = static_cast<float>(M_PI_2); | |
67 #endif | |
68 | |
69 #ifndef M_PI_4 | |
70 const double piOverFourDouble = 0.785398163397448309616; | |
71 const float piOverFourFloat = 0.785398163397448309616f; | |
72 #else | |
73 const double piOverFourDouble = M_PI_4; | |
74 const float piOverFourFloat = static_cast<float>(M_PI_4); | |
75 #endif | |
76 | |
77 #if OS(DARWIN) | |
78 | |
79 // Work around a bug in the Mac OS X libc where ceil(-0.1) return +0. | |
80 inline double wtf_ceil(double x) { return copysign(ceil(x), x); } | |
81 | |
82 #define ceil(x) wtf_ceil(x) | |
83 | |
84 #endif | |
85 | |
86 #if OS(SOLARIS) | |
87 | |
88 namespace std { | |
89 | |
90 #ifndef isfinite | |
91 inline bool isfinite(double x) { return finite(x) && !isnand(x); } | |
92 #endif | |
93 #ifndef signbit | |
94 inline bool signbit(double x) { return copysign(1.0, x) < 0; } | |
95 #endif | |
96 #ifndef isinf | |
97 inline bool isinf(double x) { return !finite(x) && !isnand(x); } | |
98 #endif | |
99 | |
100 } // namespace std | |
101 | |
102 #endif | |
103 | |
104 #if OS(OPENBSD) | |
105 | |
106 namespace std { | |
107 | |
108 #ifndef isfinite | |
109 inline bool isfinite(double x) { return finite(x); } | |
110 #endif | |
111 #ifndef signbit | |
112 inline bool signbit(double x) { struct ieee_double *p = (struct ieee_double *)&x
; return p->dbl_sign; } | |
113 #endif | |
114 | |
115 } // namespace std | |
116 | |
117 #endif | |
118 | |
119 #if COMPILER(MSVC) | |
120 | |
121 // We must not do 'num + 0.5' or 'num - 0.5' because they can cause precision lo
ss. | |
122 static double round(double num) | |
123 { | |
124 double integer = ceil(num); | |
125 if (num > 0) | |
126 return integer - num > 0.5 ? integer - 1.0 : integer; | |
127 return integer - num >= 0.5 ? integer - 1.0 : integer; | |
128 } | |
129 static float roundf(float num) | |
130 { | |
131 float integer = ceilf(num); | |
132 if (num > 0) | |
133 return integer - num > 0.5f ? integer - 1.0f : integer; | |
134 return integer - num >= 0.5f ? integer - 1.0f : integer; | |
135 } | |
136 inline long long llround(double num) { return static_cast<long long>(round(num))
; } | |
137 inline long long llroundf(float num) { return static_cast<long long>(roundf(num)
); } | |
138 inline long lround(double num) { return static_cast<long>(round(num)); } | |
139 inline long lroundf(float num) { return static_cast<long>(roundf(num)); } | |
140 inline double trunc(double num) { return num > 0 ? floor(num) : ceil(num); } | |
141 | |
142 #endif | |
143 | |
144 #if COMPILER(GCC) && OS(QNX) | |
145 // The stdlib on QNX doesn't contain long abs(long). See PR #104666. | |
146 inline long long abs(long num) { return labs(num); } | |
147 #endif | |
148 | |
149 #if OS(ANDROID) || COMPILER(MSVC) | |
150 // ANDROID and MSVC's math.h does not currently supply log2 or log2f. | |
151 inline double log2(double num) | |
152 { | |
153 // This constant is roughly M_LN2, which is not provided by default on Windo
ws and Android. | |
154 return log(num) / 0.693147180559945309417232121458176568; | |
155 } | |
156 | |
157 inline float log2f(float num) | |
158 { | |
159 // This constant is roughly M_LN2, which is not provided by default on Windo
ws and Android. | |
160 return logf(num) / 0.693147180559945309417232121458176568f; | |
161 } | |
162 #endif | |
163 | |
164 #if COMPILER(MSVC) | |
165 // The 64bit version of abs() is already defined in stdlib.h which comes with VC
10 | |
166 #if COMPILER(MSVC9_OR_LOWER) | |
167 inline long long abs(long long num) { return _abs64(num); } | |
168 #endif | |
169 | |
170 namespace std { | |
171 | |
172 inline bool isinf(double num) { return !_finite(num) && !_isnan(num); } | |
173 inline bool isnan(double num) { return !!_isnan(num); } | |
174 inline bool isfinite(double x) { return _finite(x); } | |
175 inline bool signbit(double num) { return _copysign(1.0, num) < 0; } | |
176 | |
177 } // namespace std | |
178 | |
179 inline double nextafter(double x, double y) { return _nextafter(x, y); } | |
180 inline float nextafterf(float x, float y) { return x > y ? x - FLT_EPSILON : x +
FLT_EPSILON; } | |
181 | |
182 inline double copysign(double x, double y) { return _copysign(x, y); } | |
183 | |
184 // Work around a bug in Win, where atan2(+-infinity, +-infinity) yields NaN inst
ead of specific values. | |
185 inline double wtf_atan2(double x, double y) | |
186 { | |
187 double posInf = std::numeric_limits<double>::infinity(); | |
188 double negInf = -std::numeric_limits<double>::infinity(); | |
189 double nan = std::numeric_limits<double>::quiet_NaN(); | |
190 | |
191 double result = nan; | |
192 | |
193 if (x == posInf && y == posInf) | |
194 result = piOverFourDouble; | |
195 else if (x == posInf && y == negInf) | |
196 result = 3 * piOverFourDouble; | |
197 else if (x == negInf && y == posInf) | |
198 result = -piOverFourDouble; | |
199 else if (x == negInf && y == negInf) | |
200 result = -3 * piOverFourDouble; | |
201 else | |
202 result = ::atan2(x, y); | |
203 | |
204 return result; | |
205 } | |
206 | |
207 // Work around a bug in the Microsoft CRT, where fmod(x, +-infinity) yields NaN
instead of x. | |
208 inline double wtf_fmod(double x, double y) { return (!std::isinf(x) && std::isin
f(y)) ? x : fmod(x, y); } | |
209 | |
210 // Work around a bug in the Microsoft CRT, where pow(NaN, 0) yields NaN instead
of 1. | |
211 inline double wtf_pow(double x, double y) { return y == 0 ? 1 : pow(x, y); } | |
212 | |
213 #define atan2(x, y) wtf_atan2(x, y) | |
214 #define fmod(x, y) wtf_fmod(x, y) | |
215 #define pow(x, y) wtf_pow(x, y) | |
216 | |
217 // MSVC's math functions do not bring lrint. | |
218 inline long int lrint(double flt) | |
219 { | |
220 int64_t intgr; | |
221 #if CPU(X86) | |
222 __asm { | |
223 fld flt | |
224 fistp intgr | |
225 }; | |
226 #else | |
227 ASSERT(std::isfinite(flt)); | |
228 double rounded = round(flt); | |
229 intgr = static_cast<int64_t>(rounded); | |
230 // If the fractional part is exactly 0.5, we need to check whether | |
231 // the rounded result is even. If it is not we need to add 1 to | |
232 // negative values and subtract one from positive values. | |
233 if ((fabs(intgr - flt) == 0.5) & intgr) | |
234 intgr -= ((intgr >> 62) | 1); // 1 with the sign of result, i.e. -1 or 1
. | |
235 #endif | |
236 return static_cast<long int>(intgr); | |
237 } | |
238 | |
239 #endif // COMPILER(MSVC) | |
240 | |
241 inline double deg2rad(double d) { return d * piDouble / 180.0; } | |
242 inline double rad2deg(double r) { return r * 180.0 / piDouble; } | |
243 inline double deg2grad(double d) { return d * 400.0 / 360.0; } | |
244 inline double grad2deg(double g) { return g * 360.0 / 400.0; } | |
245 inline double turn2deg(double t) { return t * 360.0; } | |
246 inline double deg2turn(double d) { return d / 360.0; } | |
247 inline double rad2grad(double r) { return r * 200.0 / piDouble; } | |
248 inline double grad2rad(double g) { return g * piDouble / 200.0; } | |
249 | |
250 inline float deg2rad(float d) { return d * piFloat / 180.0f; } | |
251 inline float rad2deg(float r) { return r * 180.0f / piFloat; } | |
252 inline float deg2grad(float d) { return d * 400.0f / 360.0f; } | |
253 inline float grad2deg(float g) { return g * 360.0f / 400.0f; } | |
254 inline float turn2deg(float t) { return t * 360.0f; } | |
255 inline float deg2turn(float d) { return d / 360.0f; } | |
256 inline float rad2grad(float r) { return r * 200.0f / piFloat; } | |
257 inline float grad2rad(float g) { return g * piFloat / 200.0f; } | |
258 | |
259 // std::numeric_limits<T>::min() returns the smallest positive value for floatin
g point types | |
260 template<typename T> inline T defaultMinimumForClamp() { return std::numeric_lim
its<T>::min(); } | |
261 template<> inline float defaultMinimumForClamp() { return -std::numeric_limits<f
loat>::max(); } | |
262 template<> inline double defaultMinimumForClamp() { return -std::numeric_limits<
double>::max(); } | |
263 template<typename T> inline T defaultMaximumForClamp() { return std::numeric_lim
its<T>::max(); } | |
264 | |
265 template<typename T> inline T clampTo(double value, T min = defaultMinimumForCla
mp<T>(), T max = defaultMaximumForClamp<T>()) | |
266 { | |
267 if (value >= static_cast<double>(max)) | |
268 return max; | |
269 if (value <= static_cast<double>(min)) | |
270 return min; | |
271 return static_cast<T>(value); | |
272 } | |
273 template<> inline long long int clampTo(double, long long int, long long int); /
/ clampTo does not support long long ints. | |
274 | |
275 inline int clampToInteger(double value) | |
276 { | |
277 return clampTo<int>(value); | |
278 } | |
279 | |
280 inline float clampToFloat(double value) | |
281 { | |
282 return clampTo<float>(value); | |
283 } | |
284 | |
285 inline int clampToPositiveInteger(double value) | |
286 { | |
287 return clampTo<int>(value, 0); | |
288 } | |
289 | |
290 inline int clampToInteger(float value) | |
291 { | |
292 return clampTo<int>(value); | |
293 } | |
294 | |
295 inline int clampToInteger(unsigned x) | |
296 { | |
297 const unsigned intMax = static_cast<unsigned>(std::numeric_limits<int>::max(
)); | |
298 | |
299 if (x >= intMax) | |
300 return std::numeric_limits<int>::max(); | |
301 return static_cast<int>(x); | |
302 } | |
303 | |
304 inline bool isWithinIntRange(float x) | |
305 { | |
306 return x > static_cast<float>(std::numeric_limits<int>::min()) && x < static
_cast<float>(std::numeric_limits<int>::max()); | |
307 } | |
308 | |
309 template<typename T> inline bool hasOneBitSet(T value) | |
310 { | |
311 return !((value - 1) & value) && value; | |
312 } | |
313 | |
314 template<typename T> inline bool hasZeroOrOneBitsSet(T value) | |
315 { | |
316 return !((value - 1) & value); | |
317 } | |
318 | |
319 template<typename T> inline bool hasTwoOrMoreBitsSet(T value) | |
320 { | |
321 return !hasZeroOrOneBitsSet(value); | |
322 } | |
323 | |
324 template <typename T> inline unsigned getLSBSet(T value) | |
325 { | |
326 unsigned result = 0; | |
327 | |
328 while (value >>= 1) | |
329 ++result; | |
330 | |
331 return result; | |
332 } | |
333 | |
334 template<typename T> inline T timesThreePlusOneDividedByTwo(T value) | |
335 { | |
336 // Mathematically equivalent to: | |
337 // (value * 3 + 1) / 2; | |
338 // or: | |
339 // (unsigned)ceil(value * 1.5)); | |
340 // This form is not prone to internal overflow. | |
341 return value + (value >> 1) + (value & 1); | |
342 } | |
343 | |
344 #ifndef UINT64_C | |
345 #if COMPILER(MSVC) | |
346 #define UINT64_C(c) c ## ui64 | |
347 #else | |
348 #define UINT64_C(c) c ## ull | |
349 #endif | |
350 #endif | |
351 | |
352 #if COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC
< 1) | |
353 inline double wtf_pow(double x, double y) | |
354 { | |
355 // MinGW-w64 has a custom implementation for pow. | |
356 // This handles certain special cases that are different. | |
357 if ((x == 0.0 || std::isinf(x)) && std::isfinite(y)) { | |
358 double f; | |
359 if (modf(y, &f) != 0.0) | |
360 return ((x == 0.0) ^ (y > 0.0)) ? std::numeric_limits<double>::infin
ity() : 0.0; | |
361 } | |
362 | |
363 if (x == 2.0) { | |
364 int yInt = static_cast<int>(y); | |
365 if (y == yInt) | |
366 return ldexp(1.0, yInt); | |
367 } | |
368 | |
369 return pow(x, y); | |
370 } | |
371 #define pow(x, y) wtf_pow(x, y) | |
372 #endif // COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERS
ION_RC < 1) | |
373 | |
374 | |
375 // decompose 'number' to its sign, exponent, and mantissa components. | |
376 // The result is interpreted as: | |
377 // (sign ? -1 : 1) * pow(2, exponent) * (mantissa / (1 << 52)) | |
378 inline void decomposeDouble(double number, bool& sign, int32_t& exponent, uint64
_t& mantissa) | |
379 { | |
380 ASSERT(std::isfinite(number)); | |
381 | |
382 sign = std::signbit(number); | |
383 | |
384 uint64_t bits = WTF::bitwise_cast<uint64_t>(number); | |
385 exponent = (static_cast<int32_t>(bits >> 52) & 0x7ff) - 0x3ff; | |
386 mantissa = bits & 0xFFFFFFFFFFFFFull; | |
387 | |
388 // Check for zero/denormal values; if so, adjust the exponent, | |
389 // if not insert the implicit, omitted leading 1 bit. | |
390 if (exponent == -0x3ff) | |
391 exponent = mantissa ? -0x3fe : 0; | |
392 else | |
393 mantissa |= 0x10000000000000ull; | |
394 } | |
395 | |
396 // Calculate d % 2^{64}. | |
397 inline void doubleToInteger(double d, unsigned long long& value) | |
398 { | |
399 if (std::isnan(d) || std::isinf(d)) | |
400 value = 0; | |
401 else { | |
402 // -2^{64} < fmodValue < 2^{64}. | |
403 double fmodValue = fmod(trunc(d), std::numeric_limits<unsigned long long
>::max() + 1.0); | |
404 if (fmodValue >= 0) { | |
405 // 0 <= fmodValue < 2^{64}. | |
406 // 0 <= value < 2^{64}. This cast causes no loss. | |
407 value = static_cast<unsigned long long>(fmodValue); | |
408 } else { | |
409 // -2^{64} < fmodValue < 0. | |
410 // 0 < fmodValueInUnsignedLongLong < 2^{64}. This cast causes no los
s. | |
411 unsigned long long fmodValueInUnsignedLongLong = static_cast<unsigne
d long long>(-fmodValue); | |
412 // -1 < (std::numeric_limits<unsigned long long>::max() - fmodValueI
nUnsignedLongLong) < 2^{64} - 1. | |
413 // 0 < value < 2^{64}. | |
414 value = std::numeric_limits<unsigned long long>::max() - fmodValueIn
UnsignedLongLong + 1; | |
415 } | |
416 } | |
417 } | |
418 | |
419 namespace WTF { | |
420 | |
421 // From http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2 | |
422 inline uint32_t roundUpToPowerOfTwo(uint32_t v) | |
423 { | |
424 v--; | |
425 v |= v >> 1; | |
426 v |= v >> 2; | |
427 v |= v >> 4; | |
428 v |= v >> 8; | |
429 v |= v >> 16; | |
430 v++; | |
431 return v; | |
432 } | |
433 | |
434 inline unsigned fastLog2(unsigned i) | |
435 { | |
436 unsigned log2 = 0; | |
437 if (i & (i - 1)) | |
438 log2 += 1; | |
439 if (i >> 16) | |
440 log2 += 16, i >>= 16; | |
441 if (i >> 8) | |
442 log2 += 8, i >>= 8; | |
443 if (i >> 4) | |
444 log2 += 4, i >>= 4; | |
445 if (i >> 2) | |
446 log2 += 2, i >>= 2; | |
447 if (i >> 1) | |
448 log2 += 1; | |
449 return log2; | |
450 } | |
451 | |
452 } // namespace WTF | |
453 | |
454 #endif // #ifndef WTF_MathExtras_h | |
OLD | NEW |