bmalloc, WTF and JavaScriptCore parts of [Xcode] Update some build settings as recomm...
[WebKit-https.git] / Source / WTF / wtf / MathExtras.h
1 /*
2  * Copyright (C) 2006-2018 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(OPENBSD)
38 #include <sys/types.h>
39 #include <machine/ieee.h>
40 #endif
41
42 #ifndef M_PI
43 const double piDouble = 3.14159265358979323846;
44 const float piFloat = 3.14159265358979323846f;
45 #else
46 const double piDouble = M_PI;
47 const float piFloat = static_cast<float>(M_PI);
48 #endif
49
50 #ifndef M_PI_2
51 const double piOverTwoDouble = 1.57079632679489661923;
52 const float piOverTwoFloat = 1.57079632679489661923f;
53 #else
54 const double piOverTwoDouble = M_PI_2;
55 const float piOverTwoFloat = static_cast<float>(M_PI_2);
56 #endif
57
58 #ifndef M_PI_4
59 const double piOverFourDouble = 0.785398163397448309616;
60 const float piOverFourFloat = 0.785398163397448309616f;
61 #else
62 const double piOverFourDouble = M_PI_4;
63 const float piOverFourFloat = static_cast<float>(M_PI_4);
64 #endif
65
66 #ifndef M_SQRT2
67 const double sqrtOfTwoDouble = 1.41421356237309504880;
68 const float sqrtOfTwoFloat = 1.41421356237309504880f;
69 #else
70 const double sqrtOfTwoDouble = M_SQRT2;
71 const float sqrtOfTwoFloat = static_cast<float>(M_SQRT2);
72 #endif
73
74 #if COMPILER(MSVC)
75
76 // Work around a bug in Win, where atan2(+-infinity, +-infinity) yields NaN instead of specific values.
77 extern "C" inline double wtf_atan2(double x, double y)
78 {
79     double posInf = std::numeric_limits<double>::infinity();
80     double negInf = -std::numeric_limits<double>::infinity();
81     double nan = std::numeric_limits<double>::quiet_NaN();
82
83     double result = nan;
84
85     if (x == posInf && y == posInf)
86         result = piOverFourDouble;
87     else if (x == posInf && y == negInf)
88         result = 3 * piOverFourDouble;
89     else if (x == negInf && y == posInf)
90         result = -piOverFourDouble;
91     else if (x == negInf && y == negInf)
92         result = -3 * piOverFourDouble;
93     else
94         result = ::atan2(x, y);
95
96     return result;
97 }
98
99 #define atan2(x, y) wtf_atan2(x, y)
100
101 #endif // COMPILER(MSVC)
102
103 inline double deg2rad(double d)  { return d * piDouble / 180.0; }
104 inline double rad2deg(double r)  { return r * 180.0 / piDouble; }
105 inline double deg2grad(double d) { return d * 400.0 / 360.0; }
106 inline double grad2deg(double g) { return g * 360.0 / 400.0; }
107 inline double turn2deg(double t) { return t * 360.0; }
108 inline double deg2turn(double d) { return d / 360.0; }
109 inline double rad2grad(double r) { return r * 200.0 / piDouble; }
110 inline double grad2rad(double g) { return g * piDouble / 200.0; }
111
112 inline float deg2rad(float d)  { return d * piFloat / 180.0f; }
113 inline float rad2deg(float r)  { return r * 180.0f / piFloat; }
114 inline float deg2grad(float d) { return d * 400.0f / 360.0f; }
115 inline float grad2deg(float g) { return g * 360.0f / 400.0f; }
116 inline float turn2deg(float t) { return t * 360.0f; }
117 inline float deg2turn(float d) { return d / 360.0f; }
118 inline float rad2grad(float r) { return r * 200.0f / piFloat; }
119 inline float grad2rad(float g) { return g * piFloat / 200.0f; }
120
121 // std::numeric_limits<T>::min() returns the smallest positive value for floating point types
122 template<typename T> constexpr inline T defaultMinimumForClamp() { return std::numeric_limits<T>::min(); }
123 template<> constexpr inline float defaultMinimumForClamp() { return -std::numeric_limits<float>::max(); }
124 template<> constexpr inline double defaultMinimumForClamp() { return -std::numeric_limits<double>::max(); }
125 template<typename T> constexpr inline T defaultMaximumForClamp() { return std::numeric_limits<T>::max(); }
126
127 template<typename T> inline T clampTo(double value, T min = defaultMinimumForClamp<T>(), T max = defaultMaximumForClamp<T>())
128 {
129     if (value >= static_cast<double>(max))
130         return max;
131     if (value <= static_cast<double>(min))
132         return min;
133     return static_cast<T>(value);
134 }
135 template<> inline long long int clampTo(double, long long int, long long int); // clampTo does not support long long ints.
136
137 inline int clampToInteger(double value)
138 {
139     return clampTo<int>(value);
140 }
141
142 inline unsigned clampToUnsigned(double value)
143 {
144     return clampTo<unsigned>(value);
145 }
146
147 inline float clampToFloat(double value)
148 {
149     return clampTo<float>(value);
150 }
151
152 inline int clampToPositiveInteger(double value)
153 {
154     return clampTo<int>(value, 0);
155 }
156
157 inline int clampToInteger(float value)
158 {
159     return clampTo<int>(value);
160 }
161
162 template<typename T>
163 inline int clampToInteger(T x)
164 {
165     static_assert(std::numeric_limits<T>::is_integer, "T must be an integer.");
166
167     const T intMax = static_cast<unsigned>(std::numeric_limits<int>::max());
168
169     if (x >= intMax)
170         return std::numeric_limits<int>::max();
171     return static_cast<int>(x);
172 }
173
174 // Explicitly accept 64bit result when clamping double value.
175 // Keep in mind that double can only represent 53bit integer precisely.
176 template<typename T> constexpr inline T clampToAccepting64(double value, T min = defaultMinimumForClamp<T>(), T max = defaultMaximumForClamp<T>())
177 {
178     return (value >= static_cast<double>(max)) ? max : ((value <= static_cast<double>(min)) ? min : static_cast<T>(value));
179 }
180
181 inline bool isWithinIntRange(float x)
182 {
183     return x > static_cast<float>(std::numeric_limits<int>::min()) && x < static_cast<float>(std::numeric_limits<int>::max());
184 }
185
186 inline float normalizedFloat(float value)
187 {
188     if (value > 0 && value < std::numeric_limits<float>::min())
189         return std::numeric_limits<float>::min();
190     if (value < 0 && value > -std::numeric_limits<float>::min())
191         return -std::numeric_limits<float>::min();
192     return value;
193 }
194
195 template<typename T> constexpr bool hasOneBitSet(T value)
196 {
197     return !((value - 1) & value) && value;
198 }
199
200 template<typename T> constexpr bool hasZeroOrOneBitsSet(T value)
201 {
202     return !((value - 1) & value);
203 }
204
205 template<typename T> constexpr bool hasTwoOrMoreBitsSet(T value)
206 {
207     return !hasZeroOrOneBitsSet(value);
208 }
209
210 template <typename T> inline unsigned getLSBSet(T value)
211 {
212     typedef typename std::make_unsigned<T>::type UnsignedT;
213     unsigned result = 0;
214
215     UnsignedT unsignedValue = static_cast<UnsignedT>(value);
216     while (unsignedValue >>= 1)
217         ++result;
218
219     return result;
220 }
221
222 template<typename T> inline T divideRoundedUp(T a, T b)
223 {
224     return (a + b - 1) / b;
225 }
226
227 template<typename T> inline T timesThreePlusOneDividedByTwo(T value)
228 {
229     // Mathematically equivalent to:
230     //   (value * 3 + 1) / 2;
231     // or:
232     //   (unsigned)ceil(value * 1.5));
233     // This form is not prone to internal overflow.
234     return value + (value >> 1) + (value & 1);
235 }
236
237 template<typename T> inline bool isNotZeroAndOrdered(T value)
238 {
239     return value > 0.0 || value < 0.0;
240 }
241
242 template<typename T> inline bool isZeroOrUnordered(T value)
243 {
244     return !isNotZeroAndOrdered(value);
245 }
246
247 template<typename T> inline bool isGreaterThanNonZeroPowerOfTwo(T value, unsigned power)
248 {
249     // The crazy way of testing of index >= 2 ** power
250     // (where I use ** to denote pow()).
251     return !!((value >> 1) >> (power - 1));
252 }
253
254 template<typename T> constexpr inline bool isLessThan(const T& a, const T& b) { return a < b; }
255 template<typename T> constexpr inline bool isLessThanEqual(const T& a, const T& b) { return a <= b; }
256 template<typename T> constexpr inline bool isGreaterThan(const T& a, const T& b) { return a > b; }
257 template<typename T> constexpr inline bool isGreaterThanEqual(const T& a, const T& b) { return a >= b; }
258
259 #ifndef UINT64_C
260 #if COMPILER(MSVC)
261 #define UINT64_C(c) c ## ui64
262 #else
263 #define UINT64_C(c) c ## ull
264 #endif
265 #endif
266
267 #if COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC < 1)
268 inline double wtf_pow(double x, double y)
269 {
270     // MinGW-w64 has a custom implementation for pow.
271     // This handles certain special cases that are different.
272     if ((x == 0.0 || std::isinf(x)) && std::isfinite(y)) {
273         double f;
274         if (modf(y, &f) != 0.0)
275             return ((x == 0.0) ^ (y > 0.0)) ? std::numeric_limits<double>::infinity() : 0.0;
276     }
277
278     if (x == 2.0) {
279         int yInt = static_cast<int>(y);
280         if (y == yInt)
281             return ldexp(1.0, yInt);
282     }
283
284     return pow(x, y);
285 }
286 #define pow(x, y) wtf_pow(x, y)
287 #endif // COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC < 1)
288
289
290 // decompose 'number' to its sign, exponent, and mantissa components.
291 // The result is interpreted as:
292 //     (sign ? -1 : 1) * pow(2, exponent) * (mantissa / (1 << 52))
293 inline void decomposeDouble(double number, bool& sign, int32_t& exponent, uint64_t& mantissa)
294 {
295     ASSERT(std::isfinite(number));
296
297     sign = std::signbit(number);
298
299     uint64_t bits = WTF::bitwise_cast<uint64_t>(number);
300     exponent = (static_cast<int32_t>(bits >> 52) & 0x7ff) - 0x3ff;
301     mantissa = bits & 0xFFFFFFFFFFFFFull;
302
303     // Check for zero/denormal values; if so, adjust the exponent,
304     // if not insert the implicit, omitted leading 1 bit.
305     if (exponent == -0x3ff)
306         exponent = mantissa ? -0x3fe : 0;
307     else
308         mantissa |= 0x10000000000000ull;
309 }
310
311 // Calculate d % 2^{64}.
312 inline void doubleToInteger(double d, unsigned long long& value)
313 {
314     if (std::isnan(d) || std::isinf(d))
315         value = 0;
316     else {
317         // -2^{64} < fmodValue < 2^{64}.
318         double fmodValue = fmod(trunc(d), std::numeric_limits<unsigned long long>::max() + 1.0);
319         if (fmodValue >= 0) {
320             // 0 <= fmodValue < 2^{64}.
321             // 0 <= value < 2^{64}. This cast causes no loss.
322             value = static_cast<unsigned long long>(fmodValue);
323         } else {
324             // -2^{64} < fmodValue < 0.
325             // 0 < fmodValueInUnsignedLongLong < 2^{64}. This cast causes no loss.
326             unsigned long long fmodValueInUnsignedLongLong = static_cast<unsigned long long>(-fmodValue);
327             // -1 < (std::numeric_limits<unsigned long long>::max() - fmodValueInUnsignedLongLong) < 2^{64} - 1.
328             // 0 < value < 2^{64}.
329             value = std::numeric_limits<unsigned long long>::max() - fmodValueInUnsignedLongLong + 1;
330         }
331     }
332 }
333
334 namespace WTF {
335
336 // From http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
337 inline constexpr uint32_t roundUpToPowerOfTwo(uint32_t v)
338 {
339     v--;
340     v |= v >> 1;
341     v |= v >> 2;
342     v |= v >> 4;
343     v |= v >> 8;
344     v |= v >> 16;
345     v++;
346     return v;
347 }
348
349 inline constexpr unsigned maskForSize(unsigned size)
350 {
351     if (!size)
352         return 0;
353     return roundUpToPowerOfTwo(size) - 1;
354 }
355
356 inline unsigned fastLog2(unsigned i)
357 {
358     unsigned log2 = 0;
359     if (i & (i - 1))
360         log2 += 1;
361     if (i >> 16) {
362         log2 += 16;
363         i >>= 16;
364     }
365     if (i >> 8) {
366         log2 += 8;
367         i >>= 8;
368     }
369     if (i >> 4) {
370         log2 += 4;
371         i >>= 4;
372     }
373     if (i >> 2) {
374         log2 += 2;
375         i >>= 2;
376     }
377     if (i >> 1)
378         log2 += 1;
379     return log2;
380 }
381
382 inline unsigned fastLog2(uint64_t value)
383 {
384     unsigned high = static_cast<unsigned>(value >> 32);
385     if (high)
386         return fastLog2(high) + 32;
387     return fastLog2(static_cast<unsigned>(value));
388 }
389
390 template <typename T>
391 inline typename std::enable_if<std::is_floating_point<T>::value, T>::type safeFPDivision(T u, T v)
392 {
393     // Protect against overflow / underflow.
394     if (v < 1 && u > v * std::numeric_limits<T>::max())
395         return std::numeric_limits<T>::max();
396     if (v > 1 && u < v * std::numeric_limits<T>::min())
397         return 0;
398     return u / v;
399 }
400
401 // Floating point numbers comparison:
402 // u is "essentially equal" [1][2] to v if: | u - v | / |u| <= e and | u - v | / |v| <= e
403 //
404 // [1] Knuth, D. E. "Accuracy of Floating Point Arithmetic." The Art of Computer Programming. 3rd ed. Vol. 2.
405 //     Boston: Addison-Wesley, 1998. 229-45.
406 // [2] http://www.boost.org/doc/libs/1_34_0/libs/test/doc/components/test_tools/floating_point_comparison.html
407 template <typename T>
408 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())
409 {
410     if (u == v)
411         return true;
412
413     const T delta = std::abs(u - v);
414     return safeFPDivision(delta, std::abs(u)) <= epsilon && safeFPDivision(delta, std::abs(v)) <= epsilon;
415 }
416
417 // Match behavior of Math.min, where NaN is returned if either argument is NaN.
418 template <typename T>
419 inline typename std::enable_if<std::is_floating_point<T>::value, T>::type nanPropagatingMin(T a, T b)
420 {
421     return std::isnan(a) || std::isnan(b) ? std::numeric_limits<T>::quiet_NaN() : std::min(a, b);
422 }
423
424 // Match behavior of Math.max, 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 nanPropagatingMax(T a, T b)
427 {
428     return std::isnan(a) || std::isnan(b) ? std::numeric_limits<T>::quiet_NaN() : std::max(a, b);
429 }
430
431 inline bool isIntegral(float value)
432 {
433     return static_cast<int>(value) == value;
434 }
435
436 template<typename T>
437 inline void incrementWithSaturation(T& value)
438 {
439     if (value != std::numeric_limits<T>::max())
440         value++;
441 }
442
443 template<typename T>
444 inline T leftShiftWithSaturation(T value, unsigned shiftAmount, T max = std::numeric_limits<T>::max())
445 {
446     T result = value << shiftAmount;
447     // We will have saturated if shifting right doesn't recover the original value.
448     if (result >> shiftAmount != value)
449         return max;
450     if (result > max)
451         return max;
452     return result;
453 }
454
455 // Check if two ranges overlap assuming that neither range is empty.
456 template<typename T>
457 inline bool nonEmptyRangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
458 {
459     ASSERT(leftMin < leftMax);
460     ASSERT(rightMin < rightMax);
461
462     return leftMax > rightMin && rightMax > leftMin;
463 }
464
465 // Pass ranges with the min being inclusive and the max being exclusive. For example, this should
466 // return false:
467 //
468 //     rangesOverlap(0, 8, 8, 16)
469 template<typename T>
470 inline bool rangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
471 {
472     ASSERT(leftMin <= leftMax);
473     ASSERT(rightMin <= rightMax);
474     
475     // Empty ranges interfere with nothing.
476     if (leftMin == leftMax)
477         return false;
478     if (rightMin == rightMax)
479         return false;
480
481     return nonEmptyRangesOverlap(leftMin, leftMax, rightMin, rightMax);
482 }
483
484 // This mask is not necessarily the minimal mask, specifically if size is
485 // a power of 2. It has the advantage that it's fast to compute, however.
486 inline uint32_t computeIndexingMask(uint32_t size)
487 {
488     return static_cast<uint64_t>(static_cast<uint32_t>(-1)) >> std::clz(size);
489 }
490
491 constexpr unsigned preciseIndexMaskShiftForSize(unsigned size)
492 {
493     return size * 8 - 1;
494 }
495
496 template<typename T>
497 constexpr unsigned preciseIndexMaskShift()
498 {
499     return preciseIndexMaskShiftForSize(sizeof(T));
500 }
501
502 template<typename T>
503 T opaque(T pointer)
504 {
505 #if !OS(WINDOWS)
506     asm("" : "+r"(pointer));
507 #endif
508     return pointer;
509 }
510
511 // This masks the given pointer with 0xffffffffffffffff (ptrwidth) if `index <
512 // length`. Otherwise, it masks the pointer with 0. Similar to Linux kernel's array_ptr.
513 template<typename T>
514 inline T* preciseIndexMaskPtr(uintptr_t index, uintptr_t length, T* value)
515 {
516     uintptr_t result = bitwise_cast<uintptr_t>(value) & static_cast<uintptr_t>(
517         static_cast<intptr_t>(index - opaque(length)) >>
518         static_cast<intptr_t>(preciseIndexMaskShift<T*>()));
519     return bitwise_cast<T*>(result);
520 }
521
522 template<typename VectorType, typename RandomFunc>
523 void shuffleVector(VectorType& vector, size_t size, const RandomFunc& randomFunc)
524 {
525     for (size_t i = 0; i + 1 < size; ++i)
526         std::swap(vector[i], vector[i + randomFunc(size - i)]);
527 }
528
529 template<typename VectorType, typename RandomFunc>
530 void shuffleVector(VectorType& vector, const RandomFunc& randomFunc)
531 {
532     shuffleVector(vector, vector.size(), randomFunc);
533 }
534
535 inline unsigned clz32(uint32_t number)
536 {
537 #if COMPILER(GCC_COMPATIBLE)
538     if (number)
539         return __builtin_clz(number);
540     return 32;
541 #elif COMPILER(MSVC)
542     // Visual Studio 2008 or upper have __lzcnt, but we can't detect Intel AVX at compile time.
543     // So we use bit-scan-reverse operation to calculate clz.
544     unsigned long ret = 0;
545     if (_BitScanReverse(&ret, number))
546         return 31 - ret;
547     return 32;
548 #else
549     unsigned zeroCount = 0;
550     for (int i = 31; i >= 0; i--) {
551         if (!(number >> i))
552             zeroCount++;
553         else
554             break;
555     }
556     return zeroCount;
557 #endif
558 }
559
560 inline unsigned clz64(uint64_t number)
561 {
562 #if COMPILER(GCC_COMPATIBLE)
563     if (number)
564         return __builtin_clzll(number);
565     return 64;
566 #elif COMPILER(MSVC) && !CPU(X86)
567     // Visual Studio 2008 or upper have __lzcnt, but we can't detect Intel AVX at compile time.
568     // So we use bit-scan-reverse operation to calculate clz.
569     // _BitScanReverse64 is defined in X86_64 and ARM in MSVC supported environments.
570     unsigned long ret = 0;
571     if (_BitScanReverse64(&ret, number))
572         return 63 - ret;
573     return 64;
574 #else
575     unsigned zeroCount = 0;
576     for (int i = 63; i >= 0; i--) {
577         if (!(number >> i))
578             zeroCount++;
579         else
580             break;
581     }
582     return zeroCount;
583 #endif
584 }
585
586 inline unsigned ctz32(uint32_t number)
587 {
588 #if COMPILER(GCC_COMPATIBLE)
589     if (number)
590         return __builtin_ctz(number);
591     return 32;
592 #elif COMPILER(MSVC) && !CPU(X86)
593     unsigned long ret = 0;
594     if (_BitScanForward(&ret, number))
595         return ret;
596     return 32;
597 #else
598     unsigned zeroCount = 0;
599     for (unsigned i = 0; i < 32; i++) {
600         if (number & 1)
601             break;
602
603         zeroCount++;
604         number >>= 1;
605     }
606     return zeroCount;
607 #endif
608 }
609
610 } // namespace WTF
611
612 using WTF::opaque;
613 using WTF::preciseIndexMaskPtr;
614 using WTF::preciseIndexMaskShift;
615 using WTF::preciseIndexMaskShiftForSize;
616 using WTF::shuffleVector;
617 using WTF::clz32;
618 using WTF::clz64;
619 using WTF::ctz32;
620
621 #endif // #ifndef WTF_MathExtras_h