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