Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : /* Various predicates and operations on IEEE-754 floating point types. */
8 :
9 : #ifndef mozilla_FloatingPoint_h
10 : #define mozilla_FloatingPoint_h
11 :
12 : #include "mozilla/Assertions.h"
13 : #include "mozilla/Attributes.h"
14 : #include "mozilla/Casting.h"
15 : #include "mozilla/MathAlgorithms.h"
16 : #include "mozilla/Types.h"
17 :
18 : #include <stdint.h>
19 :
20 : namespace mozilla {
21 :
22 : /*
23 : * It's reasonable to ask why we have this header at all. Don't isnan,
24 : * copysign, the built-in comparison operators, and the like solve these
25 : * problems? Unfortunately, they don't. We've found that various compilers
26 : * (MSVC, MSVC when compiling with PGO, and GCC on OS X, at least) miscompile
27 : * the standard methods in various situations, so we can't use them. Some of
28 : * these compilers even have problems compiling seemingly reasonable bitwise
29 : * algorithms! But with some care we've found algorithms that seem to not
30 : * trigger those compiler bugs.
31 : *
32 : * For the aforementioned reasons, be very wary of making changes to any of
33 : * these algorithms. If you must make changes, keep a careful eye out for
34 : * compiler bustage, particularly PGO-specific bustage.
35 : */
36 :
37 : struct FloatTypeTraits
38 : {
39 : typedef uint32_t Bits;
40 :
41 : static const unsigned kExponentBias = 127;
42 : static const unsigned kExponentShift = 23;
43 :
44 : static const Bits kSignBit = 0x80000000UL;
45 : static const Bits kExponentBits = 0x7F800000UL;
46 : static const Bits kSignificandBits = 0x007FFFFFUL;
47 : };
48 :
49 : struct DoubleTypeTraits
50 : {
51 : typedef uint64_t Bits;
52 :
53 : static const unsigned kExponentBias = 1023;
54 : static const unsigned kExponentShift = 52;
55 :
56 : static const Bits kSignBit = 0x8000000000000000ULL;
57 : static const Bits kExponentBits = 0x7ff0000000000000ULL;
58 : static const Bits kSignificandBits = 0x000fffffffffffffULL;
59 : };
60 :
61 : template<typename T> struct SelectTrait;
62 : template<> struct SelectTrait<float> : public FloatTypeTraits {};
63 : template<> struct SelectTrait<double> : public DoubleTypeTraits {};
64 :
65 : /*
66 : * This struct contains details regarding the encoding of floating-point
67 : * numbers that can be useful for direct bit manipulation. As of now, the
68 : * template parameter has to be float or double.
69 : *
70 : * The nested typedef |Bits| is the unsigned integral type with the same size
71 : * as T: uint32_t for float and uint64_t for double (static assertions
72 : * double-check these assumptions).
73 : *
74 : * kExponentBias is the offset that is subtracted from the exponent when
75 : * computing the value, i.e. one plus the opposite of the mininum possible
76 : * exponent.
77 : * kExponentShift is the shift that one needs to apply to retrieve the
78 : * exponent component of the value.
79 : *
80 : * kSignBit contains a bits mask. Bit-and-ing with this mask will result in
81 : * obtaining the sign bit.
82 : * kExponentBits contains the mask needed for obtaining the exponent bits and
83 : * kSignificandBits contains the mask needed for obtaining the significand
84 : * bits.
85 : *
86 : * Full details of how floating point number formats are encoded are beyond
87 : * the scope of this comment. For more information, see
88 : * http://en.wikipedia.org/wiki/IEEE_floating_point
89 : * http://en.wikipedia.org/wiki/Floating_point#IEEE_754:_floating_point_in_modern_computers
90 : */
91 : template<typename T>
92 : struct FloatingPoint : public SelectTrait<T>
93 : {
94 : typedef SelectTrait<T> Base;
95 : typedef typename Base::Bits Bits;
96 :
97 : static_assert((Base::kSignBit & Base::kExponentBits) == 0,
98 : "sign bit shouldn't overlap exponent bits");
99 : static_assert((Base::kSignBit & Base::kSignificandBits) == 0,
100 : "sign bit shouldn't overlap significand bits");
101 : static_assert((Base::kExponentBits & Base::kSignificandBits) == 0,
102 : "exponent bits shouldn't overlap significand bits");
103 :
104 : static_assert((Base::kSignBit | Base::kExponentBits | Base::kSignificandBits) ==
105 : ~Bits(0),
106 : "all bits accounted for");
107 :
108 : /*
109 : * These implementations assume float/double are 32/64-bit single/double
110 : * format number types compatible with the IEEE-754 standard. C++ don't
111 : * require this to be the case. But we required this in implementations of
112 : * these algorithms that preceded this header, so we shouldn't break anything
113 : * if we keep doing so.
114 : */
115 : static_assert(sizeof(T) == sizeof(Bits), "Bits must be same size as T");
116 : };
117 :
118 : /** Determines whether a float/double is NaN. */
119 : template<typename T>
120 : static MOZ_ALWAYS_INLINE bool
121 52819 : IsNaN(T aValue)
122 : {
123 : /*
124 : * A float/double is NaN if all exponent bits are 1 and the significand
125 : * contains at least one non-zero bit.
126 : */
127 : typedef FloatingPoint<T> Traits;
128 : typedef typename Traits::Bits Bits;
129 53064 : return (BitwiseCast<Bits>(aValue) & Traits::kExponentBits) == Traits::kExponentBits &&
130 53064 : (BitwiseCast<Bits>(aValue) & Traits::kSignificandBits) != 0;
131 : }
132 :
133 : /** Determines whether a float/double is +Infinity or -Infinity. */
134 : template<typename T>
135 : static MOZ_ALWAYS_INLINE bool
136 839 : IsInfinite(T aValue)
137 : {
138 : /* Infinities have all exponent bits set to 1 and an all-0 significand. */
139 : typedef FloatingPoint<T> Traits;
140 : typedef typename Traits::Bits Bits;
141 839 : Bits bits = BitwiseCast<Bits>(aValue);
142 839 : return (bits & ~Traits::kSignBit) == Traits::kExponentBits;
143 : }
144 :
145 : /** Determines whether a float/double is not NaN or infinite. */
146 : template<typename T>
147 : static MOZ_ALWAYS_INLINE bool
148 5907 : IsFinite(T aValue)
149 : {
150 : /*
151 : * NaN and Infinities are the only non-finite floats/doubles, and both have
152 : * all exponent bits set to 1.
153 : */
154 : typedef FloatingPoint<T> Traits;
155 : typedef typename Traits::Bits Bits;
156 5907 : Bits bits = BitwiseCast<Bits>(aValue);
157 5907 : return (bits & Traits::kExponentBits) != Traits::kExponentBits;
158 : }
159 :
160 : /**
161 : * Determines whether a float/double is negative or -0. It is an error
162 : * to call this method on a float/double which is NaN.
163 : */
164 : template<typename T>
165 : static MOZ_ALWAYS_INLINE bool
166 611 : IsNegative(T aValue)
167 : {
168 611 : MOZ_ASSERT(!IsNaN(aValue), "NaN does not have a sign");
169 :
170 : /* The sign bit is set if the double is negative. */
171 : typedef FloatingPoint<T> Traits;
172 : typedef typename Traits::Bits Bits;
173 611 : Bits bits = BitwiseCast<Bits>(aValue);
174 611 : return (bits & Traits::kSignBit) != 0;
175 : }
176 :
177 : /** Determines whether a float/double represents -0. */
178 : template<typename T>
179 : static MOZ_ALWAYS_INLINE bool
180 30486 : IsNegativeZero(T aValue)
181 : {
182 : /* Only the sign bit is set if the value is -0. */
183 : typedef FloatingPoint<T> Traits;
184 : typedef typename Traits::Bits Bits;
185 30486 : Bits bits = BitwiseCast<Bits>(aValue);
186 30486 : return bits == Traits::kSignBit;
187 : }
188 :
189 : /** Determines wether a float/double represents +0. */
190 : template<typename T>
191 : static MOZ_ALWAYS_INLINE bool
192 0 : IsPositiveZero(T aValue)
193 : {
194 : /* All bits are zero if the value is +0. */
195 : typedef FloatingPoint<T> Traits;
196 : typedef typename Traits::Bits Bits;
197 0 : Bits bits = BitwiseCast<Bits>(aValue);
198 0 : return bits == 0;
199 : }
200 :
201 : /**
202 : * Returns 0 if a float/double is NaN or infinite;
203 : * otherwise, the float/double is returned.
204 : */
205 : template<typename T>
206 : static MOZ_ALWAYS_INLINE T
207 0 : ToZeroIfNonfinite(T aValue)
208 : {
209 0 : return IsFinite(aValue) ? aValue : 0;
210 : }
211 :
212 : /**
213 : * Returns the exponent portion of the float/double.
214 : *
215 : * Zero is not special-cased, so ExponentComponent(0.0) is
216 : * -int_fast16_t(Traits::kExponentBias).
217 : */
218 : template<typename T>
219 : static MOZ_ALWAYS_INLINE int_fast16_t
220 400 : ExponentComponent(T aValue)
221 : {
222 : /*
223 : * The exponent component of a float/double is an unsigned number, biased
224 : * from its actual value. Subtract the bias to retrieve the actual exponent.
225 : */
226 : typedef FloatingPoint<T> Traits;
227 : typedef typename Traits::Bits Bits;
228 400 : Bits bits = BitwiseCast<Bits>(aValue);
229 400 : return int_fast16_t((bits & Traits::kExponentBits) >> Traits::kExponentShift) -
230 400 : int_fast16_t(Traits::kExponentBias);
231 : }
232 :
233 : /** Returns +Infinity. */
234 : template<typename T>
235 : static MOZ_ALWAYS_INLINE T
236 7222 : PositiveInfinity()
237 : {
238 : /*
239 : * Positive infinity has all exponent bits set, sign bit set to 0, and no
240 : * significand.
241 : */
242 : typedef FloatingPoint<T> Traits;
243 7222 : return BitwiseCast<T>(Traits::kExponentBits);
244 : }
245 :
246 : /** Returns -Infinity. */
247 : template<typename T>
248 : static MOZ_ALWAYS_INLINE T
249 7214 : NegativeInfinity()
250 : {
251 : /*
252 : * Negative infinity has all exponent bits set, sign bit set to 1, and no
253 : * significand.
254 : */
255 : typedef FloatingPoint<T> Traits;
256 7214 : return BitwiseCast<T>(Traits::kSignBit | Traits::kExponentBits);
257 : }
258 :
259 : /**
260 : * Computes the bit pattern for a NaN with the specified sign bit and
261 : * significand bits.
262 : */
263 : template<typename T,
264 : int SignBit,
265 : typename FloatingPoint<T>::Bits Significand>
266 : struct SpecificNaNBits
267 : {
268 : using Traits = FloatingPoint<T>;
269 :
270 : static_assert(SignBit == 0 || SignBit == 1, "bad sign bit");
271 : static_assert((Significand & ~Traits::kSignificandBits) == 0,
272 : "significand must only have significand bits set");
273 : static_assert(Significand & Traits::kSignificandBits,
274 : "significand must be nonzero");
275 :
276 : static constexpr typename Traits::Bits value =
277 : (SignBit * Traits::kSignBit) | Traits::kExponentBits | Significand;
278 : };
279 :
280 : /**
281 : * Constructs a NaN value with the specified sign bit and significand bits.
282 : *
283 : * There is also a variant that returns the value directly. In most cases, the
284 : * two variants should be identical. However, in the specific case of x86
285 : * chips, the behavior differs: returning floating-point values directly is done
286 : * through the x87 stack, and x87 loads and stores turn signaling NaNs into
287 : * quiet NaNs... silently. Returning floating-point values via outparam,
288 : * however, is done entirely within the SSE registers when SSE2 floating-point
289 : * is enabled in the compiler, which has semantics-preserving behavior you would
290 : * expect.
291 : *
292 : * If preserving the distinction between signaling NaNs and quiet NaNs is
293 : * important to you, you should use the outparam version. In all other cases,
294 : * you should use the direct return version.
295 : */
296 : template<typename T>
297 : static MOZ_ALWAYS_INLINE void
298 232 : SpecificNaN(int signbit, typename FloatingPoint<T>::Bits significand, T* result)
299 : {
300 : typedef FloatingPoint<T> Traits;
301 232 : MOZ_ASSERT(signbit == 0 || signbit == 1);
302 232 : MOZ_ASSERT((significand & ~Traits::kSignificandBits) == 0);
303 232 : MOZ_ASSERT(significand & Traits::kSignificandBits);
304 :
305 232 : BitwiseCast<T>((signbit ? Traits::kSignBit : 0) |
306 : Traits::kExponentBits |
307 : significand,
308 : result);
309 232 : MOZ_ASSERT(IsNaN(*result));
310 232 : }
311 :
312 : template<typename T>
313 : static MOZ_ALWAYS_INLINE T
314 232 : SpecificNaN(int signbit, typename FloatingPoint<T>::Bits significand)
315 : {
316 : T t;
317 232 : SpecificNaN(signbit, significand, &t);
318 232 : return t;
319 : }
320 :
321 : /** Computes the smallest non-zero positive float/double value. */
322 : template<typename T>
323 : static MOZ_ALWAYS_INLINE T
324 3 : MinNumberValue()
325 : {
326 : typedef FloatingPoint<T> Traits;
327 : typedef typename Traits::Bits Bits;
328 3 : return BitwiseCast<T>(Bits(1));
329 : }
330 :
331 : /**
332 : * If aValue is equal to some int32_t value, set *aInt32 to that value and
333 : * return true; otherwise return false.
334 : *
335 : * Note that negative zero is "equal" to zero here. To test whether a value can
336 : * be losslessly converted to int32_t and back, use NumberIsInt32 instead.
337 : */
338 : template<typename T>
339 : static MOZ_ALWAYS_INLINE bool
340 30406 : NumberEqualsInt32(T aValue, int32_t* aInt32)
341 : {
342 : /*
343 : * XXX Casting a floating-point value that doesn't truncate to int32_t, to
344 : * int32_t, induces undefined behavior. We should definitely fix this
345 : * (bug 744965), but as apparently it "works" in practice, it's not a
346 : * pressing concern now.
347 : */
348 30406 : return aValue == (*aInt32 = int32_t(aValue));
349 : }
350 :
351 : /**
352 : * If d can be converted to int32_t and back to an identical double value,
353 : * set *aInt32 to that value and return true; otherwise return false.
354 : *
355 : * The difference between this and NumberEqualsInt32 is that this method returns
356 : * false for negative zero.
357 : */
358 : template<typename T>
359 : static MOZ_ALWAYS_INLINE bool
360 30405 : NumberIsInt32(T aValue, int32_t* aInt32)
361 : {
362 30405 : return !IsNegativeZero(aValue) && NumberEqualsInt32(aValue, aInt32);
363 : }
364 :
365 : /**
366 : * Computes a NaN value. Do not use this method if you depend upon a particular
367 : * NaN value being returned.
368 : */
369 : template<typename T>
370 : static MOZ_ALWAYS_INLINE T
371 19 : UnspecifiedNaN()
372 : {
373 : /*
374 : * If we can use any quiet NaN, we might as well use the all-ones NaN,
375 : * since it's cheap to materialize on common platforms (such as x64, where
376 : * this value can be represented in a 32-bit signed immediate field, allowing
377 : * it to be stored to memory in a single instruction).
378 : */
379 : typedef FloatingPoint<T> Traits;
380 19 : return SpecificNaN<T>(1, Traits::kSignificandBits);
381 : }
382 :
383 : /**
384 : * Compare two doubles for equality, *without* equating -0 to +0, and equating
385 : * any NaN value to any other NaN value. (The normal equality operators equate
386 : * -0 with +0, and they equate NaN to no other value.)
387 : */
388 : template<typename T>
389 : static inline bool
390 28 : NumbersAreIdentical(T aValue1, T aValue2)
391 : {
392 : typedef FloatingPoint<T> Traits;
393 : typedef typename Traits::Bits Bits;
394 28 : if (IsNaN(aValue1)) {
395 0 : return IsNaN(aValue2);
396 : }
397 28 : return BitwiseCast<Bits>(aValue1) == BitwiseCast<Bits>(aValue2);
398 : }
399 :
400 : namespace detail {
401 :
402 : template<typename T>
403 : struct FuzzyEqualsEpsilon;
404 :
405 : template<>
406 : struct FuzzyEqualsEpsilon<float>
407 : {
408 : // A number near 1e-5 that is exactly representable in a float.
409 166 : static float value() { return 1.0f / (1 << 17); }
410 : };
411 :
412 : template<>
413 : struct FuzzyEqualsEpsilon<double>
414 : {
415 : // A number near 1e-12 that is exactly representable in a double.
416 : static double value() { return 1.0 / (1LL << 40); }
417 : };
418 :
419 : } // namespace detail
420 :
421 : /**
422 : * Compare two floating point values for equality, modulo rounding error. That
423 : * is, the two values are considered equal if they are both not NaN and if they
424 : * are less than or equal to aEpsilon apart. The default value of aEpsilon is
425 : * near 1e-5.
426 : *
427 : * For most scenarios you will want to use FuzzyEqualsMultiplicative instead,
428 : * as it is more reasonable over the entire range of floating point numbers.
429 : * This additive version should only be used if you know the range of the
430 : * numbers you are dealing with is bounded and stays around the same order of
431 : * magnitude.
432 : */
433 : template<typename T>
434 : static MOZ_ALWAYS_INLINE bool
435 34 : FuzzyEqualsAdditive(T aValue1, T aValue2,
436 : T aEpsilon = detail::FuzzyEqualsEpsilon<T>::value())
437 : {
438 : static_assert(IsFloatingPoint<T>::value, "floating point type required");
439 34 : return Abs(aValue1 - aValue2) <= aEpsilon;
440 : }
441 :
442 : /**
443 : * Compare two floating point values for equality, allowing for rounding error
444 : * relative to the magnitude of the values. That is, the two values are
445 : * considered equal if they are both not NaN and they are less than or equal to
446 : * some aEpsilon apart, where the aEpsilon is scaled by the smaller of the two
447 : * argument values.
448 : *
449 : * In most cases you will want to use this rather than FuzzyEqualsAdditive, as
450 : * this function effectively masks out differences in the bottom few bits of
451 : * the floating point numbers being compared, regardless of what order of
452 : * magnitude those numbers are at.
453 : */
454 : template<typename T>
455 : static MOZ_ALWAYS_INLINE bool
456 136 : FuzzyEqualsMultiplicative(T aValue1, T aValue2,
457 : T aEpsilon = detail::FuzzyEqualsEpsilon<T>::value())
458 : {
459 : static_assert(IsFloatingPoint<T>::value, "floating point type required");
460 : // can't use std::min because of bug 965340
461 136 : T smaller = Abs(aValue1) < Abs(aValue2) ? Abs(aValue1) : Abs(aValue2);
462 136 : return Abs(aValue1 - aValue2) <= aEpsilon * smaller;
463 : }
464 :
465 : /**
466 : * Returns true if the given value can be losslessly represented as an IEEE-754
467 : * single format number, false otherwise. All NaN values are considered
468 : * representable (notwithstanding that the exact bit pattern of a double format
469 : * NaN value can't be exactly represented in single format).
470 : *
471 : * This function isn't inlined to avoid buggy optimizations by MSVC.
472 : */
473 : MOZ_MUST_USE
474 : extern MFBT_API bool
475 : IsFloat32Representable(double aFloat32);
476 :
477 : } /* namespace mozilla */
478 :
479 : #endif /* mozilla_FloatingPoint_h */
|
