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