1/*
2 * Copyright (C) 2006, 2007, 2008, 2009, 2010, 2013 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#if OS(DARWIN)
71
72// Work around a bug in the Mac OS X libc where ceil(-0.1) return +0.
73inline double wtf_ceil(double x) { return copysign(ceil(x), x); }
74
75#define ceil(x) wtf_ceil(x)
76
77#endif
78
79#if OS(SOLARIS)
80
81namespace std {
82
83#ifndef isfinite
84inline bool isfinite(double x) { return finite(x) && !isnand(x); }
85#endif
86#ifndef signbit
87inline bool signbit(double x) { return copysign(1.0, x) < 0; }
88#endif
89#ifndef isinf
90inline bool isinf(double x) { return !finite(x) && !isnand(x); }
91#endif
92
93} // namespace std
94
95#endif
96
97#if OS(OPENBSD)
98
99namespace std {
100
101#ifndef isfinite
102inline bool isfinite(double x) { return finite(x); }
103#endif
104#ifndef signbit
105inline bool signbit(double x) { struct ieee_double *p = (struct ieee_double *)&x; return p->dbl_sign; }
106#endif
107
108} // namespace std
109
110#endif
111
112#if COMPILER(MSVC)
113
114// Work around a bug in Win, where atan2(+-infinity, +-infinity) yields NaN instead of specific values.
115extern "C" inline double wtf_atan2(double x, double y)
116{
117    double posInf = std::numeric_limits<double>::infinity();
118    double negInf = -std::numeric_limits<double>::infinity();
119    double nan = std::numeric_limits<double>::quiet_NaN();
120
121    double result = nan;
122
123    if (x == posInf && y == posInf)
124        result = piOverFourDouble;
125    else if (x == posInf && y == negInf)
126        result = 3 * piOverFourDouble;
127    else if (x == negInf && y == posInf)
128        result = -piOverFourDouble;
129    else if (x == negInf && y == negInf)
130        result = -3 * piOverFourDouble;
131    else
132        result = ::atan2(x, y);
133
134    return result;
135}
136
137// Work around a bug in the Microsoft CRT, where fmod(x, +-infinity) yields NaN instead of x.
138extern "C" inline double wtf_fmod(double x, double y) { return (!std::isinf(x) && std::isinf(y)) ? x : fmod(x, y); }
139
140// Work around a bug in the Microsoft CRT, where pow(NaN, 0) yields NaN instead of 1.
141extern "C" inline double wtf_pow(double x, double y) { return y == 0 ? 1 : pow(x, y); }
142
143#define atan2(x, y) wtf_atan2(x, y)
144#define fmod(x, y) wtf_fmod(x, y)
145#define pow(x, y) wtf_pow(x, y)
146
147#endif // COMPILER(MSVC)
148
149inline double deg2rad(double d)  { return d * piDouble / 180.0; }
150inline double rad2deg(double r)  { return r * 180.0 / piDouble; }
151inline double deg2grad(double d) { return d * 400.0 / 360.0; }
152inline double grad2deg(double g) { return g * 360.0 / 400.0; }
153inline double turn2deg(double t) { return t * 360.0; }
154inline double deg2turn(double d) { return d / 360.0; }
155inline double rad2grad(double r) { return r * 200.0 / piDouble; }
156inline double grad2rad(double g) { return g * piDouble / 200.0; }
157
158inline float deg2rad(float d)  { return d * piFloat / 180.0f; }
159inline float rad2deg(float r)  { return r * 180.0f / piFloat; }
160inline float deg2grad(float d) { return d * 400.0f / 360.0f; }
161inline float grad2deg(float g) { return g * 360.0f / 400.0f; }
162inline float turn2deg(float t) { return t * 360.0f; }
163inline float deg2turn(float d) { return d / 360.0f; }
164inline float rad2grad(float r) { return r * 200.0f / piFloat; }
165inline float grad2rad(float g) { return g * piFloat / 200.0f; }
166
167// std::numeric_limits<T>::min() returns the smallest positive value for floating point types
168template<typename T> inline T defaultMinimumForClamp() { return std::numeric_limits<T>::min(); }
169template<> inline float defaultMinimumForClamp() { return -std::numeric_limits<float>::max(); }
170template<> inline double defaultMinimumForClamp() { return -std::numeric_limits<double>::max(); }
171template<typename T> inline T defaultMaximumForClamp() { return std::numeric_limits<T>::max(); }
172
173template<typename T> inline T clampTo(double value, T min = defaultMinimumForClamp<T>(), T max = defaultMaximumForClamp<T>())
174{
175    if (value >= static_cast<double>(max))
176        return max;
177    if (value <= static_cast<double>(min))
178        return min;
179    return static_cast<T>(value);
180}
181template<> inline long long int clampTo(double, long long int, long long int); // clampTo does not support long long ints.
182
183inline int clampToInteger(double value)
184{
185    return clampTo<int>(value);
186}
187
188inline unsigned clampToUnsigned(double value)
189{
190    return clampTo<unsigned>(value);
191}
192
193inline float clampToFloat(double value)
194{
195    return clampTo<float>(value);
196}
197
198inline int clampToPositiveInteger(double value)
199{
200    return clampTo<int>(value, 0);
201}
202
203inline int clampToInteger(float value)
204{
205    return clampTo<int>(value);
206}
207
208inline int clampToInteger(unsigned x)
209{
210    const unsigned intMax = static_cast<unsigned>(std::numeric_limits<int>::max());
211
212    if (x >= intMax)
213        return std::numeric_limits<int>::max();
214    return static_cast<int>(x);
215}
216
217inline bool isWithinIntRange(float x)
218{
219    return x > static_cast<float>(std::numeric_limits<int>::min()) && x < static_cast<float>(std::numeric_limits<int>::max());
220}
221
222template<typename T> inline bool hasOneBitSet(T value)
223{
224    return !((value - 1) & value) && value;
225}
226
227template<typename T> inline bool hasZeroOrOneBitsSet(T value)
228{
229    return !((value - 1) & value);
230}
231
232template<typename T> inline bool hasTwoOrMoreBitsSet(T value)
233{
234    return !hasZeroOrOneBitsSet(value);
235}
236
237template <typename T> inline unsigned getLSBSet(T value)
238{
239    unsigned result = 0;
240
241    while (value >>= 1)
242        ++result;
243
244    return result;
245}
246
247template<typename T> inline T divideRoundedUp(T a, T b)
248{
249    return (a + b - 1) / b;
250}
251
252template<typename T> inline T timesThreePlusOneDividedByTwo(T value)
253{
254    // Mathematically equivalent to:
255    //   (value * 3 + 1) / 2;
256    // or:
257    //   (unsigned)ceil(value * 1.5));
258    // This form is not prone to internal overflow.
259    return value + (value >> 1) + (value & 1);
260}
261
262template<typename T> inline bool isNotZeroAndOrdered(T value)
263{
264    return value > 0.0 || value < 0.0;
265}
266
267template<typename T> inline bool isZeroOrUnordered(T value)
268{
269    return !isNotZeroAndOrdered(value);
270}
271
272template<typename T> inline bool isGreaterThanNonZeroPowerOfTwo(T value, unsigned power)
273{
274    // The crazy way of testing of index >= 2 ** power
275    // (where I use ** to denote pow()).
276    return !!((value >> 1) >> (power - 1));
277}
278
279#ifndef UINT64_C
280#if COMPILER(MSVC)
281#define UINT64_C(c) c ## ui64
282#else
283#define UINT64_C(c) c ## ull
284#endif
285#endif
286
287#if COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC < 1)
288inline double wtf_pow(double x, double y)
289{
290    // MinGW-w64 has a custom implementation for pow.
291    // This handles certain special cases that are different.
292    if ((x == 0.0 || std::isinf(x)) && std::isfinite(y)) {
293        double f;
294        if (modf(y, &f) != 0.0)
295            return ((x == 0.0) ^ (y > 0.0)) ? std::numeric_limits<double>::infinity() : 0.0;
296    }
297
298    if (x == 2.0) {
299        int yInt = static_cast<int>(y);
300        if (y == yInt)
301            return ldexp(1.0, yInt);
302    }
303
304    return pow(x, y);
305}
306#define pow(x, y) wtf_pow(x, y)
307#endif // COMPILER(MINGW64) && (!defined(__MINGW64_VERSION_RC) || __MINGW64_VERSION_RC < 1)
308
309
310// decompose 'number' to its sign, exponent, and mantissa components.
311// The result is interpreted as:
312//     (sign ? -1 : 1) * pow(2, exponent) * (mantissa / (1 << 52))
313inline void decomposeDouble(double number, bool& sign, int32_t& exponent, uint64_t& mantissa)
314{
315    ASSERT(std::isfinite(number));
316
317    sign = std::signbit(number);
318
319    uint64_t bits = WTF::bitwise_cast<uint64_t>(number);
320    exponent = (static_cast<int32_t>(bits >> 52) & 0x7ff) - 0x3ff;
321    mantissa = bits & 0xFFFFFFFFFFFFFull;
322
323    // Check for zero/denormal values; if so, adjust the exponent,
324    // if not insert the implicit, omitted leading 1 bit.
325    if (exponent == -0x3ff)
326        exponent = mantissa ? -0x3fe : 0;
327    else
328        mantissa |= 0x10000000000000ull;
329}
330
331// Calculate d % 2^{64}.
332inline void doubleToInteger(double d, unsigned long long& value)
333{
334    if (std::isnan(d) || std::isinf(d))
335        value = 0;
336    else {
337        // -2^{64} < fmodValue < 2^{64}.
338        double fmodValue = fmod(trunc(d), std::numeric_limits<unsigned long long>::max() + 1.0);
339        if (fmodValue >= 0) {
340            // 0 <= fmodValue < 2^{64}.
341            // 0 <= value < 2^{64}. This cast causes no loss.
342            value = static_cast<unsigned long long>(fmodValue);
343        } else {
344            // -2^{64} < fmodValue < 0.
345            // 0 < fmodValueInUnsignedLongLong < 2^{64}. This cast causes no loss.
346            unsigned long long fmodValueInUnsignedLongLong = static_cast<unsigned long long>(-fmodValue);
347            // -1 < (std::numeric_limits<unsigned long long>::max() - fmodValueInUnsignedLongLong) < 2^{64} - 1.
348            // 0 < value < 2^{64}.
349            value = std::numeric_limits<unsigned long long>::max() - fmodValueInUnsignedLongLong + 1;
350        }
351    }
352}
353
354namespace WTF {
355
356// From http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
357inline uint32_t roundUpToPowerOfTwo(uint32_t v)
358{
359    v--;
360    v |= v >> 1;
361    v |= v >> 2;
362    v |= v >> 4;
363    v |= v >> 8;
364    v |= v >> 16;
365    v++;
366    return v;
367}
368
369inline unsigned fastLog2(unsigned i)
370{
371    unsigned log2 = 0;
372    if (i & (i - 1))
373        log2 += 1;
374    if (i >> 16)
375        log2 += 16, i >>= 16;
376    if (i >> 8)
377        log2 += 8, i >>= 8;
378    if (i >> 4)
379        log2 += 4, i >>= 4;
380    if (i >> 2)
381        log2 += 2, i >>= 2;
382    if (i >> 1)
383        log2 += 1;
384    return log2;
385}
386
387} // namespace WTF
388
389#endif // #ifndef WTF_MathExtras_h
390