8080533dd792f0f437b66e347c2d11beb3944e95
[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 #pragma once
27
28 #include <algorithm>
29 #include <climits>
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 T defaultMinimumForClamp() { return std::numeric_limits<T>::min(); }
123 template<> constexpr float defaultMinimumForClamp() { return -std::numeric_limits<float>::max(); }
124 template<> constexpr double defaultMinimumForClamp() { return -std::numeric_limits<double>::max(); }
125 template<typename T> constexpr T defaultMaximumForClamp() { return std::numeric_limits<T>::max(); }
126
127 // Same type in and out.
128 template<typename TargetType, typename SourceType>
129 typename std::enable_if<std::is_same<TargetType, SourceType>::value, TargetType>::type
130 clampTo(SourceType value, TargetType min = defaultMinimumForClamp<TargetType>(), TargetType max = defaultMaximumForClamp<TargetType>())
131 {
132     if (value >= max)
133         return max;
134     if (value <= min)
135         return min;
136     return value;
137 }
138
139 // Floating point source.
140 template<typename TargetType, typename SourceType>
141 typename std::enable_if<!std::is_same<TargetType, SourceType>::value
142     && std::is_floating_point<SourceType>::value
143     && !(std::is_floating_point<TargetType>::value && sizeof(TargetType) > sizeof(SourceType)), TargetType>::type
144 clampTo(SourceType value, TargetType min = defaultMinimumForClamp<TargetType>(), TargetType max = defaultMaximumForClamp<TargetType>())
145 {
146     if (value >= static_cast<SourceType>(max))
147         return max;
148     if (value <= static_cast<SourceType>(min))
149         return min;
150     return static_cast<TargetType>(value);
151 }
152
153 template<typename TargetType, typename SourceType>
154 typename std::enable_if<!std::is_same<TargetType, SourceType>::value
155     && std::is_floating_point<SourceType>::value
156     && std::is_floating_point<TargetType>::value
157     && (sizeof(TargetType) > sizeof(SourceType)), TargetType>::type
158 clampTo(SourceType value, TargetType min = defaultMinimumForClamp<TargetType>(), TargetType max = defaultMaximumForClamp<TargetType>())
159 {
160     TargetType convertedValue = static_cast<TargetType>(value);
161     if (convertedValue >= max)
162         return max;
163     if (convertedValue <= min)
164         return min;
165     return convertedValue;
166 }
167
168 // Source and Target have the same sign and Source is larger or equal to Target
169 template<typename TargetType, typename SourceType>
170 typename std::enable_if<!std::is_same<TargetType, SourceType>::value
171     && std::numeric_limits<SourceType>::is_integer
172     && std::numeric_limits<TargetType>::is_integer
173     && std::numeric_limits<TargetType>::is_signed == std::numeric_limits<SourceType>::is_signed
174     && sizeof(SourceType) >= sizeof(TargetType), TargetType>::type
175 clampTo(SourceType value, TargetType min = defaultMinimumForClamp<TargetType>(), TargetType max = defaultMaximumForClamp<TargetType>())
176 {
177     if (value >= static_cast<SourceType>(max))
178         return max;
179     if (value <= static_cast<SourceType>(min))
180         return min;
181     return static_cast<TargetType>(value);
182 }
183
184 // Clamping a unsigned integer to the max signed value.
185 template<typename TargetType, typename SourceType>
186 typename std::enable_if<!std::is_same<TargetType, SourceType>::value
187     && std::numeric_limits<SourceType>::is_integer
188     && std::numeric_limits<TargetType>::is_integer
189     && std::numeric_limits<TargetType>::is_signed
190     && !std::numeric_limits<SourceType>::is_signed
191     && sizeof(SourceType) >= sizeof(TargetType), TargetType>::type
192 clampTo(SourceType value)
193 {
194     TargetType max = std::numeric_limits<TargetType>::max();
195     if (value >= static_cast<SourceType>(max))
196         return max;
197     return static_cast<TargetType>(value);
198 }
199
200 // Clamping a signed integer into a valid unsigned integer.
201 template<typename TargetType, typename SourceType>
202 typename std::enable_if<!std::is_same<TargetType, SourceType>::value
203     && std::numeric_limits<SourceType>::is_integer
204     && std::numeric_limits<TargetType>::is_integer
205     && !std::numeric_limits<TargetType>::is_signed
206     && std::numeric_limits<SourceType>::is_signed
207     && sizeof(SourceType) == sizeof(TargetType), TargetType>::type
208 clampTo(SourceType value)
209 {
210     if (value < 0)
211         return 0;
212     return static_cast<TargetType>(value);
213 }
214
215 template<typename TargetType, typename SourceType>
216 typename std::enable_if<!std::is_same<TargetType, SourceType>::value
217     && std::numeric_limits<SourceType>::is_integer
218     && std::numeric_limits<TargetType>::is_integer
219     && !std::numeric_limits<TargetType>::is_signed
220     && std::numeric_limits<SourceType>::is_signed
221     && (sizeof(SourceType) > sizeof(TargetType)), TargetType>::type
222 clampTo(SourceType value)
223 {
224     if (value < 0)
225         return 0;
226     TargetType max = std::numeric_limits<TargetType>::max();
227     if (value >= static_cast<SourceType>(max))
228         return max;
229     return static_cast<TargetType>(value);
230 }
231
232 inline int clampToInteger(double value)
233 {
234     return clampTo<int>(value);
235 }
236
237 inline unsigned clampToUnsigned(double value)
238 {
239     return clampTo<unsigned>(value);
240 }
241
242 inline float clampToFloat(double value)
243 {
244     return clampTo<float>(value);
245 }
246
247 inline int clampToPositiveInteger(double value)
248 {
249     return clampTo<int>(value, 0);
250 }
251
252 inline int clampToInteger(float value)
253 {
254     return clampTo<int>(value);
255 }
256
257 template<typename T>
258 inline int clampToInteger(T x)
259 {
260     static_assert(std::numeric_limits<T>::is_integer, "T must be an integer.");
261
262     const T intMax = static_cast<unsigned>(std::numeric_limits<int>::max());
263
264     if (x >= intMax)
265         return std::numeric_limits<int>::max();
266     return static_cast<int>(x);
267 }
268
269 // Explicitly accept 64bit result when clamping double value.
270 // Keep in mind that double can only represent 53bit integer precisely.
271 template<typename T> constexpr T clampToAccepting64(double value, T min = defaultMinimumForClamp<T>(), T max = defaultMaximumForClamp<T>())
272 {
273     return (value >= static_cast<double>(max)) ? max : ((value <= static_cast<double>(min)) ? min : static_cast<T>(value));
274 }
275
276 inline bool isWithinIntRange(float x)
277 {
278     return x > static_cast<float>(std::numeric_limits<int>::min()) && x < static_cast<float>(std::numeric_limits<int>::max());
279 }
280
281 inline float normalizedFloat(float value)
282 {
283     if (value > 0 && value < std::numeric_limits<float>::min())
284         return std::numeric_limits<float>::min();
285     if (value < 0 && value > -std::numeric_limits<float>::min())
286         return -std::numeric_limits<float>::min();
287     return value;
288 }
289
290 template<typename T> constexpr bool hasOneBitSet(T value)
291 {
292     return !((value - 1) & value) && value;
293 }
294
295 template<typename T> constexpr bool hasZeroOrOneBitsSet(T value)
296 {
297     return !((value - 1) & value);
298 }
299
300 template<typename T> constexpr bool hasTwoOrMoreBitsSet(T value)
301 {
302     return !hasZeroOrOneBitsSet(value);
303 }
304
305 template<typename T> inline T divideRoundedUp(T a, T b)
306 {
307     return (a + b - 1) / b;
308 }
309
310 template<typename T> inline T timesThreePlusOneDividedByTwo(T value)
311 {
312     // Mathematically equivalent to:
313     //   (value * 3 + 1) / 2;
314     // or:
315     //   (unsigned)ceil(value * 1.5));
316     // This form is not prone to internal overflow.
317     return value + (value >> 1) + (value & 1);
318 }
319
320 template<typename T> inline bool isNotZeroAndOrdered(T value)
321 {
322     return value > 0.0 || value < 0.0;
323 }
324
325 template<typename T> inline bool isZeroOrUnordered(T value)
326 {
327     return !isNotZeroAndOrdered(value);
328 }
329
330 template<typename T> inline bool isGreaterThanNonZeroPowerOfTwo(T value, unsigned power)
331 {
332     // The crazy way of testing of index >= 2 ** power
333     // (where I use ** to denote pow()).
334     return !!((value >> 1) >> (power - 1));
335 }
336
337 template<typename T> constexpr bool isLessThan(const T& a, const T& b) { return a < b; }
338 template<typename T> constexpr bool isLessThanEqual(const T& a, const T& b) { return a <= b; }
339 template<typename T> constexpr bool isGreaterThan(const T& a, const T& b) { return a > b; }
340 template<typename T> constexpr bool isGreaterThanEqual(const T& a, const T& b) { return a >= b; }
341
342 #ifndef UINT64_C
343 #if COMPILER(MSVC)
344 #define UINT64_C(c) c ## ui64
345 #else
346 #define UINT64_C(c) c ## ull
347 #endif
348 #endif
349
350 #if COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC < 1)
351 inline double wtf_pow(double x, double y)
352 {
353     // MinGW-w64 has a custom implementation for pow.
354     // This handles certain special cases that are different.
355     if ((x == 0.0 || std::isinf(x)) && std::isfinite(y)) {
356         double f;
357         if (modf(y, &f) != 0.0)
358             return ((x == 0.0) ^ (y > 0.0)) ? std::numeric_limits<double>::infinity() : 0.0;
359     }
360
361     if (x == 2.0) {
362         int yInt = static_cast<int>(y);
363         if (y == yInt)
364             return ldexp(1.0, yInt);
365     }
366
367     return pow(x, y);
368 }
369 #define pow(x, y) wtf_pow(x, y)
370 #endif // COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC < 1)
371
372
373 // decompose 'number' to its sign, exponent, and mantissa components.
374 // The result is interpreted as:
375 //     (sign ? -1 : 1) * pow(2, exponent) * (mantissa / (1 << 52))
376 inline void decomposeDouble(double number, bool& sign, int32_t& exponent, uint64_t& mantissa)
377 {
378     ASSERT(std::isfinite(number));
379
380     sign = std::signbit(number);
381
382     uint64_t bits = WTF::bitwise_cast<uint64_t>(number);
383     exponent = (static_cast<int32_t>(bits >> 52) & 0x7ff) - 0x3ff;
384     mantissa = bits & 0xFFFFFFFFFFFFFull;
385
386     // Check for zero/denormal values; if so, adjust the exponent,
387     // if not insert the implicit, omitted leading 1 bit.
388     if (exponent == -0x3ff)
389         exponent = mantissa ? -0x3fe : 0;
390     else
391         mantissa |= 0x10000000000000ull;
392 }
393
394 // Calculate d % 2^{64}.
395 inline void doubleToInteger(double d, unsigned long long& value)
396 {
397     if (std::isnan(d) || std::isinf(d))
398         value = 0;
399     else {
400         // -2^{64} < fmodValue < 2^{64}.
401         double fmodValue = fmod(trunc(d), std::numeric_limits<unsigned long long>::max() + 1.0);
402         if (fmodValue >= 0) {
403             // 0 <= fmodValue < 2^{64}.
404             // 0 <= value < 2^{64}. This cast causes no loss.
405             value = static_cast<unsigned long long>(fmodValue);
406         } else {
407             // -2^{64} < fmodValue < 0.
408             // 0 < fmodValueInUnsignedLongLong < 2^{64}. This cast causes no loss.
409             unsigned long long fmodValueInUnsignedLongLong = static_cast<unsigned long long>(-fmodValue);
410             // -1 < (std::numeric_limits<unsigned long long>::max() - fmodValueInUnsignedLongLong) < 2^{64} - 1.
411             // 0 < value < 2^{64}.
412             value = std::numeric_limits<unsigned long long>::max() - fmodValueInUnsignedLongLong + 1;
413         }
414     }
415 }
416
417 namespace WTF {
418
419 // From http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
420 constexpr uint32_t roundUpToPowerOfTwo(uint32_t v)
421 {
422     v--;
423     v |= v >> 1;
424     v |= v >> 2;
425     v |= v >> 4;
426     v |= v >> 8;
427     v |= v >> 16;
428     v++;
429     return v;
430 }
431
432 constexpr unsigned maskForSize(unsigned size)
433 {
434     if (!size)
435         return 0;
436     return roundUpToPowerOfTwo(size) - 1;
437 }
438
439 inline unsigned fastLog2(unsigned i)
440 {
441     unsigned log2 = 0;
442     if (i & (i - 1))
443         log2 += 1;
444     if (i >> 16) {
445         log2 += 16;
446         i >>= 16;
447     }
448     if (i >> 8) {
449         log2 += 8;
450         i >>= 8;
451     }
452     if (i >> 4) {
453         log2 += 4;
454         i >>= 4;
455     }
456     if (i >> 2) {
457         log2 += 2;
458         i >>= 2;
459     }
460     if (i >> 1)
461         log2 += 1;
462     return log2;
463 }
464
465 inline unsigned fastLog2(uint64_t value)
466 {
467     unsigned high = static_cast<unsigned>(value >> 32);
468     if (high)
469         return fastLog2(high) + 32;
470     return fastLog2(static_cast<unsigned>(value));
471 }
472
473 template <typename T>
474 inline typename std::enable_if<std::is_floating_point<T>::value, T>::type safeFPDivision(T u, T v)
475 {
476     // Protect against overflow / underflow.
477     if (v < 1 && u > v * std::numeric_limits<T>::max())
478         return std::numeric_limits<T>::max();
479     if (v > 1 && u < v * std::numeric_limits<T>::min())
480         return 0;
481     return u / v;
482 }
483
484 // Floating point numbers comparison:
485 // u is "essentially equal" [1][2] to v if: | u - v | / |u| <= e and | u - v | / |v| <= e
486 //
487 // [1] Knuth, D. E. "Accuracy of Floating Point Arithmetic." The Art of Computer Programming. 3rd ed. Vol. 2.
488 //     Boston: Addison-Wesley, 1998. 229-45.
489 // [2] http://www.boost.org/doc/libs/1_34_0/libs/test/doc/components/test_tools/floating_point_comparison.html
490 template <typename T>
491 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())
492 {
493     if (u == v)
494         return true;
495
496     const T delta = std::abs(u - v);
497     return safeFPDivision(delta, std::abs(u)) <= epsilon && safeFPDivision(delta, std::abs(v)) <= epsilon;
498 }
499
500 // Match behavior of Math.min, where NaN is returned if either argument is NaN.
501 template <typename T>
502 inline typename std::enable_if<std::is_floating_point<T>::value, T>::type nanPropagatingMin(T a, T b)
503 {
504     return std::isnan(a) || std::isnan(b) ? std::numeric_limits<T>::quiet_NaN() : std::min(a, b);
505 }
506
507 // Match behavior of Math.max, where NaN is returned if either argument is NaN.
508 template <typename T>
509 inline typename std::enable_if<std::is_floating_point<T>::value, T>::type nanPropagatingMax(T a, T b)
510 {
511     return std::isnan(a) || std::isnan(b) ? std::numeric_limits<T>::quiet_NaN() : std::max(a, b);
512 }
513
514 inline bool isIntegral(float value)
515 {
516     return static_cast<int>(value) == value;
517 }
518
519 template<typename T>
520 inline void incrementWithSaturation(T& value)
521 {
522     if (value != std::numeric_limits<T>::max())
523         value++;
524 }
525
526 template<typename T>
527 inline T leftShiftWithSaturation(T value, unsigned shiftAmount, T max = std::numeric_limits<T>::max())
528 {
529     T result = value << shiftAmount;
530     // We will have saturated if shifting right doesn't recover the original value.
531     if (result >> shiftAmount != value)
532         return max;
533     if (result > max)
534         return max;
535     return result;
536 }
537
538 // Check if two ranges overlap assuming that neither range is empty.
539 template<typename T>
540 inline bool nonEmptyRangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
541 {
542     ASSERT(leftMin < leftMax);
543     ASSERT(rightMin < rightMax);
544
545     return leftMax > rightMin && rightMax > leftMin;
546 }
547
548 // Pass ranges with the min being inclusive and the max being exclusive. For example, this should
549 // return false:
550 //
551 //     rangesOverlap(0, 8, 8, 16)
552 template<typename T>
553 inline bool rangesOverlap(T leftMin, T leftMax, T rightMin, T rightMax)
554 {
555     ASSERT(leftMin <= leftMax);
556     ASSERT(rightMin <= rightMax);
557     
558     // Empty ranges interfere with nothing.
559     if (leftMin == leftMax)
560         return false;
561     if (rightMin == rightMax)
562         return false;
563
564     return nonEmptyRangesOverlap(leftMin, leftMax, rightMin, rightMax);
565 }
566
567 // This mask is not necessarily the minimal mask, specifically if size is
568 // a power of 2. It has the advantage that it's fast to compute, however.
569 inline uint32_t computeIndexingMask(uint32_t size)
570 {
571     return static_cast<uint64_t>(static_cast<uint32_t>(-1)) >> std::clz(size);
572 }
573
574 constexpr unsigned preciseIndexMaskShiftForSize(unsigned size)
575 {
576     return size * 8 - 1;
577 }
578
579 template<typename T>
580 constexpr unsigned preciseIndexMaskShift()
581 {
582     return preciseIndexMaskShiftForSize(sizeof(T));
583 }
584
585 template<typename T>
586 T opaque(T pointer)
587 {
588 #if !OS(WINDOWS)
589     asm("" : "+r"(pointer));
590 #endif
591     return pointer;
592 }
593
594 // This masks the given pointer with 0xffffffffffffffff (ptrwidth) if `index <
595 // length`. Otherwise, it masks the pointer with 0. Similar to Linux kernel's array_ptr.
596 template<typename T>
597 inline T* preciseIndexMaskPtr(uintptr_t index, uintptr_t length, T* value)
598 {
599     uintptr_t result = bitwise_cast<uintptr_t>(value) & static_cast<uintptr_t>(
600         static_cast<intptr_t>(index - opaque(length)) >>
601         static_cast<intptr_t>(preciseIndexMaskShift<T*>()));
602     return bitwise_cast<T*>(result);
603 }
604
605 template<typename VectorType, typename RandomFunc>
606 void shuffleVector(VectorType& vector, size_t size, const RandomFunc& randomFunc)
607 {
608     for (size_t i = 0; i + 1 < size; ++i)
609         std::swap(vector[i], vector[i + randomFunc(size - i)]);
610 }
611
612 template<typename VectorType, typename RandomFunc>
613 void shuffleVector(VectorType& vector, const RandomFunc& randomFunc)
614 {
615     shuffleVector(vector, vector.size(), randomFunc);
616 }
617
618 template<typename T>
619 inline unsigned clz(T value)
620 {
621     constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
622
623     using UT = typename std::make_unsigned<T>::type;
624     UT uValue = value;
625
626 #if COMPILER(GCC_COMPATIBLE)
627     constexpr unsigned bitSize64 = sizeof(uint64_t) * CHAR_BIT;
628     if (uValue)
629         return __builtin_clzll(uValue) - (bitSize64 - bitSize);
630     return bitSize;
631 #elif COMPILER(MSVC) && !CPU(X86)
632     // Visual Studio 2008 or upper have __lzcnt, but we can't detect Intel AVX at compile time.
633     // So we use bit-scan-reverse operation to calculate clz.
634     // _BitScanReverse64 is defined in X86_64 and ARM in MSVC supported environments.
635     unsigned long ret = 0;
636     if (_BitScanReverse64(&ret, uValue))
637         return bitSize - 1 - ret;
638     return bitSize;
639 #else
640     unsigned zeroCount = 0;
641     for (int i = bitSize - 1; i >= 0; i--) {
642         if (uValue >> i)
643             break;
644         zeroCount++;
645     }
646     return zeroCount;
647 #endif
648 }
649
650 template<typename T>
651 inline unsigned ctz(T value)
652 {
653     constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
654
655     using UT = typename std::make_unsigned<T>::type;
656     UT uValue = value;
657
658 #if COMPILER(GCC_COMPATIBLE)
659     if (uValue)
660         return __builtin_ctzll(uValue);
661     return bitSize;
662 #elif COMPILER(MSVC) && !CPU(X86)
663     unsigned long ret = 0;
664     if (_BitScanForward64(&ret, uValue))
665         return ret;
666     return bitSize;
667 #else
668     unsigned zeroCount = 0;
669     for (unsigned i = 0; i < bitSize; i++) {
670         if (uValue & 1)
671             break;
672
673         zeroCount++;
674         uValue >>= 1;
675     }
676     return zeroCount;
677 #endif
678 }
679
680 template<typename T>
681 inline unsigned getLSBSet(T t)
682 {
683     ASSERT(t);
684     return ctz(t);
685 }
686
687 template<typename T>
688 inline unsigned getMSBSet(T t)
689 {
690     constexpr unsigned bitSize = sizeof(T) * CHAR_BIT;
691     ASSERT(t);
692     return bitSize - 1 - clz(t);
693 }
694
695 } // namespace WTF
696
697 using WTF::opaque;
698 using WTF::preciseIndexMaskPtr;
699 using WTF::preciseIndexMaskShift;
700 using WTF::preciseIndexMaskShiftForSize;
701 using WTF::shuffleVector;
702 using WTF::clz;
703 using WTF::ctz;
704 using WTF::getLSBSet;
705 using WTF::getMSBSet;