1/*
2 * Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013, 2016 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 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 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#ifndef M_PI
47const double piDouble = 3.14159265358979323846;
48const float piFloat = 3.14159265358979323846f;
49#else
50const double piDouble = M_PI;
51const float piFloat = static_cast<float>(M_PI);
52#endif
53
54#ifndef M_PI_2
55const double piOverTwoDouble = 1.57079632679489661923;
56const float piOverTwoFloat = 1.57079632679489661923f;
57#else
58const double piOverTwoDouble = M_PI_2;
59const float piOverTwoFloat = static_cast<float>(M_PI_2);
60#endif
61
62#ifndef M_PI_4
63const double piOverFourDouble = 0.785398163397448309616;
64const float piOverFourFloat = 0.785398163397448309616f;
65#else
66const double piOverFourDouble = M_PI_4;
67const float piOverFourFloat = static_cast<float>(M_PI_4);
68#endif
69
70#ifndef M_SQRT2
71const double sqrtOfTwoDouble = 1.41421356237309504880;
72const float sqrtOfTwoFloat = 1.41421356237309504880f;
73#else
74const double sqrtOfTwoDouble = M_SQRT2;
75const float sqrtOfTwoFloat = static_cast<float>(M_SQRT2);
76#endif
77
78#if OS(SOLARIS)
79
80namespace std {
81
82#ifndef isfinite
83inline bool isfinite(double x) { return finite(x) && !isnand(x); }
84#endif
85#ifndef signbit
86inline bool signbit(double x) { return copysign(1.0, x) < 0; }
87#endif
88#ifndef isinf
89inline bool isinf(double x) { return !finite(x) && !isnand(x); }
90#endif
91
92} // namespace std
93
94#endif
95
96#if COMPILER(MSVC)
97
98// Work around a bug in Win, where atan2(+-infinity, +-infinity) yields NaN instead of specific values.
99extern "C" inline double wtf_atan2(double x, double y)
100{
101 double posInf = std::numeric_limits<double>::infinity();
102 double negInf = -std::numeric_limits<double>::infinity();
103 double nan = std::numeric_limits<double>::quiet_NaN();
104
105 double result = nan;
106
107 if (x == posInf && y == posInf)
108 result = piOverFourDouble;
109 else if (x == posInf && y == negInf)
110 result = 3 * piOverFourDouble;
111 else if (x == negInf && y == posInf)
112 result = -piOverFourDouble;
113 else if (x == negInf && y == negInf)
114 result = -3 * piOverFourDouble;
115 else
116 result = ::atan2(x, y);
117
118 return result;
119}
120
121#define atan2(x, y) wtf_atan2(x, y)
122
123#endif // COMPILER(MSVC)
124
125inline double deg2rad(double d) { return d * piDouble / 180.0; }
126inline double rad2deg(double r) { return r * 180.0 / piDouble; }
127inline double deg2grad(double d) { return d * 400.0 / 360.0; }
128inline double grad2deg(double g) { return g * 360.0 / 400.0; }
129inline double turn2deg(double t) { return t * 360.0; }
130inline double deg2turn(double d) { return d / 360.0; }
131inline double rad2grad(double r) { return r * 200.0 / piDouble; }
132inline double grad2rad(double g) { return g * piDouble / 200.0; }
133
134inline float deg2rad(float d) { return d * piFloat / 180.0f; }
135inline float rad2deg(float r) { return r * 180.0f / piFloat; }
136inline float deg2grad(float d) { return d * 400.0f / 360.0f; }
137inline float grad2deg(float g) { return g * 360.0f / 400.0f; }
138inline float turn2deg(float t) { return t * 360.0f; }
139inline float deg2turn(float d) { return d / 360.0f; }
140inline float rad2grad(float r) { return r * 200.0f / piFloat; }
141inline float grad2rad(float g) { return g * piFloat / 200.0f; }
142
143// std::numeric_limits<T>::min() returns the smallest positive value for floating point types
144template<typename T> inline T defaultMinimumForClamp() { return std::numeric_limits<T>::min(); }
145template<> inline float defaultMinimumForClamp() { return -std::numeric_limits<float>::max(); }
146template<> inline double defaultMinimumForClamp() { return -std::numeric_limits<double>::max(); }
147template<typename T> inline T defaultMaximumForClamp() { return std::numeric_limits<T>::max(); }
148
149template<typename T> inline T clampTo(double value, T min = defaultMinimumForClamp<T>(), T max = defaultMaximumForClamp<T>())
150{
151 if (value >= static_cast<double>(max))
152 return max;
153 if (value <= static_cast<double>(min))
154 return min;
155 return static_cast<T>(value);
156}
157template<> inline long long int clampTo(double, long long int, long long int); // clampTo does not support long long ints.
158
159inline int clampToInteger(double value)
160{
161 return clampTo<int>(value);
162}
163
164inline unsigned clampToUnsigned(double value)
165{
166 return clampTo<unsigned>(value);
167}
168
169inline float clampToFloat(double value)
170{
171 return clampTo<float>(value);
172}
173
174inline int clampToPositiveInteger(double value)
175{
176 return clampTo<int>(value, 0);
177}
178
179inline int clampToInteger(float value)
180{
181 return clampTo<int>(value);
182}
183
184inline int clampToInteger(unsigned x)
185{
186 const unsigned intMax = static_cast<unsigned>(std::numeric_limits<int>::max());
187
188 if (x >= intMax)
189 return std::numeric_limits<int>::max();
190 return static_cast<int>(x);
191}
192
193inline bool isWithinIntRange(float x)
194{
195 return x > static_cast<float>(std::numeric_limits<int>::min()) && x < static_cast<float>(std::numeric_limits<int>::max());
196}
197
198template<typename T> inline bool hasOneBitSet(T value)
199{
200 return !((value - 1) & value) && value;
201}
202
203template<typename T> inline bool hasZeroOrOneBitsSet(T value)
204{
205 return !((value - 1) & value);
206}
207
208template<typename T> inline bool hasTwoOrMoreBitsSet(T value)
209{
210 return !hasZeroOrOneBitsSet(value);
211}
212
213template <typename T> inline unsigned getLSBSet(T value)
214{
215 unsigned result = 0;
216
217 while (value >>= 1)
218 ++result;
219
220 return result;
221}
222
223template<typename T> inline T divideRoundedUp(T a, T b)
224{
225 return (a + b - 1) / b;
226}
227
228template<typename T> inline T timesThreePlusOneDividedByTwo(T value)
229{
230 // Mathematically equivalent to:
231 // (value * 3 + 1) / 2;
232 // or:
233 // (unsigned)ceil(value * 1.5));
234 // This form is not prone to internal overflow.
235 return value + (value >> 1) + (value & 1);
236}
237
238template<typename T> inline bool isNotZeroAndOrdered(T value)
239{
240 return value > 0.0 || value < 0.0;
241}
242
243template<typename T> inline bool isZeroOrUnordered(T value)
244{
245 return !isNotZeroAndOrdered(value);
246}
247
248template<typename T> inline bool isGreaterThanNonZeroPowerOfTwo(T value, unsigned power)
249{
250 // The crazy way of testing of index >= 2 ** power
251 // (where I use ** to denote pow()).
252 return !!((value >> 1) >> (power - 1));
253}
254
255#ifndef UINT64_C
256#if COMPILER(MSVC)
257#define UINT64_C(c) c ## ui64
258#else
259#define UINT64_C(c) c ## ull
260#endif
261#endif
262
263#if COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC < 1)
264inline double wtf_pow(double x, double y)
265{
266 // MinGW-w64 has a custom implementation for pow.
267 // This handles certain special cases that are different.
268 if ((x == 0.0 || std::isinf(x)) && std::isfinite(y)) {
269 double f;
270 if (modf(y, &f) != 0.0)
271 return ((x == 0.0) ^ (y > 0.0)) ? std::numeric_limits<double>::infinity() : 0.0;
272 }
273
274 if (x == 2.0) {
275 int yInt = static_cast<int>(y);
276 if (y == yInt)
277 return ldexp(1.0, yInt);
278 }
279
280 return pow(x, y);
281}
282#define pow(x, y) wtf_pow(x, y)
283#endif // COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC < 1)
284
285
286// decompose 'number' to its sign, exponent, and mantissa components.
287// The result is interpreted as:
288// (sign ? -1 : 1) * pow(2, exponent) * (mantissa / (1 << 52))
289inline void decomposeDouble(double number, bool& sign, int32_t& exponent, uint64_t& mantissa)
290{
291 ASSERT(std::isfinite(number));
292
293 sign = std::signbit(number);
294
295 uint64_t bits = WTF::bitwise_cast<uint64_t>(number);
296 exponent = (static_cast<int32_t>(bits >> 52) & 0x7ff) - 0x3ff;
297 mantissa = bits & 0xFFFFFFFFFFFFFull;
298
299 // Check for zero/denormal values; if so, adjust the exponent,
300 // if not insert the implicit, omitted leading 1 bit.
301 if (exponent == -0x3ff)
302 exponent = mantissa ? -0x3fe : 0;
303 else
304 mantissa |= 0x10000000000000ull;
305}
306
307// Calculate d % 2^{64}.
308inline void doubleToInteger(double d, unsigned long long& value)
309{
310 if (std::isnan(d) || std::isinf(d))
311 value = 0;
312 else {
313 // -2^{64} < fmodValue < 2^{64}.
314 double fmodValue = fmod(trunc(d), std::numeric_limits<unsigned long long>::max() + 1.0);
315 if (fmodValue >= 0) {
316 // 0 <= fmodValue < 2^{64}.
317 // 0 <= value < 2^{64}. This cast causes no loss.
318 value = static_cast<unsigned long long>(fmodValue);
319 } else {
320 // -2^{64} < fmodValue < 0.
321 // 0 < fmodValueInUnsignedLongLong < 2^{64}. This cast causes no loss.
322 unsigned long long fmodValueInUnsignedLongLong = static_cast<unsigned long long>(-fmodValue);
323 // -1 < (std::numeric_limits<unsigned long long>::max() - fmodValueInUnsignedLongLong) < 2^{64} - 1.
324 // 0 < value < 2^{64}.
325 value = std::numeric_limits<unsigned long long>::max() - fmodValueInUnsignedLongLong + 1;
326 }
327 }
328}
329
330namespace WTF {
331
332// From http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
333inline uint32_t roundUpToPowerOfTwo(uint32_t v)
334{
335 v--;
336 v |= v >> 1;
337 v |= v >> 2;
338 v |= v >> 4;
339 v |= v >> 8;
340 v |= v >> 16;
341 v++;
342 return v;
343}
344
345inline unsigned fastLog2(unsigned i)
346{
347 unsigned log2 = 0;
348 if (i & (i - 1))
349 log2 += 1;
350 if (i >> 16)
351 log2 += 16, i >>= 16;
352 if (i >> 8)
353 log2 += 8, i >>= 8;
354 if (i >> 4)
355 log2 += 4, i >>= 4;
356 if (i >> 2)
357 log2 += 2, i >>= 2;
358 if (i >> 1)
359 log2 += 1;
360 return log2;
361}
362
363inline unsigned fastLog2(uint64_t value)
364{
365 unsigned high = static_cast<unsigned>(value >> 32);
366 if (high)
367 return fastLog2(high) + 32;
368 return fastLog2(static_cast<unsigned>(value));
369}
370
371template <typename T>
372inline typename std::enable_if<std::is_floating_point<T>::value, T>::type safeFPDivision(T u, T v)
373{
374 // Protect against overflow / underflow.
375 if (v < 1 && u > v * std::numeric_limits<T>::max())
376 return std::numeric_limits<T>::max();
377 if (v > 1 && u < v * std::numeric_limits<T>::min())
378 return 0;
379 return u / v;
380}
381
382// Floating point numbers comparison:
383// u is "essentially equal" [1][2] to v if: | u - v | / |u| <= e and | u - v | / |v| <= e
384//
385// [1] Knuth, D. E. "Accuracy of Floating Point Arithmetic." The Art of Computer Programming. 3rd ed. Vol. 2.
386// Boston: Addison-Wesley, 1998. 229-45.
387// [2] http://www.boost.org/doc/libs/1_34_0/libs/test/doc/components/test_tools/floating_point_comparison.html
388template <typename T>
389inline typename std::enable_if<std::is_floating_point<T>::value, bool>::type areEssentiallyEqual(T u, T v, T epsilon = std::numeric_limits<T>::epsilon())
390{
391 if (u == v)
392 return true;
393
394 const T delta = std::abs(u - v);
395 return safeFPDivision(delta, std::abs(u)) <= epsilon && safeFPDivision(delta, std::abs(v)) <= epsilon;
396}
397
398inline bool isIntegral(float value)
399{
400 return static_cast<int>(value) == value;
401}
402
403template<typename T>
404inline void incrementWithSaturation(T& value)
405{
406 if (value != std::numeric_limits<T>::max())
407 value++;
408}
409
410template<typename T>
411inline T leftShiftWithSaturation(T value, unsigned shiftAmount, T max = std::numeric_limits<T>::max())
412{
413 T result = value << shiftAmount;
414 // We will have saturated if shifting right doesn't recover the original value.
415 if (result >> shiftAmount != value)
416 return max;
417 if (result > max)
418 return max;
419 return result;
420}
421
422// Check if two ranges overlap assuming that neither range is empty.
423template<typename T>
424inline bool nonEmptyRangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
425{
426 ASSERT(leftMin < leftMax);
427 ASSERT(rightMin < rightMax);
428
429 if (leftMin <= rightMin && leftMax > rightMin)
430 return true;
431 if (rightMin <= leftMin && rightMax > leftMin)
432 return true;
433 return false;
434}
435
436// Pass ranges with the min being inclusive and the max being exclusive. For example, this should
437// return false:
438//
439// rangesOverlap(0, 8, 8, 16)
440template<typename T>
441inline bool rangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
442{
443 ASSERT(leftMin <= leftMax);
444 ASSERT(rightMin <= rightMax);
445
446 // Empty ranges interfere with nothing.
447 if (leftMin == leftMax)
448 return false;
449 if (rightMin == rightMax)
450 return false;
451
452 return nonEmptyRangesOverlap(leftMin, leftMax, rightMin, rightMax);
453}
454
455} // namespace WTF
456
457#endif // #ifndef WTF_MathExtras_h
458