michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #ifndef SkFloatUtils_DEFINED
michael@0: #define SkFloatUtils_DEFINED
michael@0: 
michael@0: #include "SkTypes.h"
michael@0: #include <limits.h>
michael@0: #include <float.h>
michael@0: 
michael@0: template <size_t size>
michael@0: class SkTypeWithSize {
michael@0: public:
michael@0:     // Prevents using SkTypeWithSize<N> with non-specialized N.
michael@0:     typedef void UInt;
michael@0: };
michael@0: 
michael@0: template <>
michael@0: class SkTypeWithSize<32> {
michael@0: public:
michael@0:     typedef uint32_t UInt;
michael@0: };
michael@0: 
michael@0: template <>
michael@0: class SkTypeWithSize<64> {
michael@0: public:
michael@0:     typedef uint64_t UInt;
michael@0: };
michael@0: 
michael@0: template <typename RawType>
michael@0: struct SkNumericLimits {
michael@0:     static const int digits = 0;
michael@0: };
michael@0: 
michael@0: template <>
michael@0: struct SkNumericLimits<double> {
michael@0:     static const int digits = DBL_MANT_DIG;
michael@0: };
michael@0: 
michael@0: template <>
michael@0: struct SkNumericLimits<float> {
michael@0:     static const int digits = FLT_MANT_DIG;
michael@0: };
michael@0: 
michael@0: //See
michael@0: //http://stackoverflow.com/questions/17333/most-effective-way-for-float-and-double-comparison/3423299#3423299
michael@0: //http://code.google.com/p/googletest/source/browse/trunk/include/gtest/internal/gtest-internal.h
michael@0: //http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
michael@0: 
michael@0: template <typename RawType, unsigned int ULPs>
michael@0: class SkFloatingPoint {
michael@0: public:
michael@0:     /** Bits is a unsigned integer the same size as the floating point number. */
michael@0:     typedef typename SkTypeWithSize<sizeof(RawType) * CHAR_BIT>::UInt Bits;
michael@0: 
michael@0:     /** # of bits in a number. */
michael@0:     static const size_t kBitCount = CHAR_BIT * sizeof(RawType);
michael@0: 
michael@0:     /** # of fraction bits in a number. */
michael@0:     static const size_t kFractionBitCount = SkNumericLimits<RawType>::digits - 1;
michael@0: 
michael@0:     /** # of exponent bits in a number. */
michael@0:     static const size_t kExponentBitCount = kBitCount - 1 - kFractionBitCount;
michael@0: 
michael@0:     /** The mask for the sign bit. */
michael@0:     static const Bits kSignBitMask = static_cast<Bits>(1) << (kBitCount - 1);
michael@0: 
michael@0:     /** The mask for the fraction bits. */
michael@0:     static const Bits kFractionBitMask =
michael@0:         ~static_cast<Bits>(0) >> (kExponentBitCount + 1);
michael@0: 
michael@0:     /** The mask for the exponent bits. */
michael@0:     static const Bits kExponentBitMask = ~(kSignBitMask | kFractionBitMask);
michael@0: 
michael@0:     /** How many ULP's (Units in the Last Place) to tolerate when comparing. */
michael@0:     static const size_t kMaxUlps = ULPs;
michael@0: 
michael@0:     /**
michael@0:      *  Constructs a FloatingPoint from a raw floating-point number.
michael@0:      *
michael@0:      *  On an Intel CPU, passing a non-normalized NAN (Not a Number)
michael@0:      *  around may change its bits, although the new value is guaranteed
michael@0:      *  to be also a NAN.  Therefore, don't expect this constructor to
michael@0:      *  preserve the bits in x when x is a NAN.
michael@0:      */
michael@0:     explicit SkFloatingPoint(const RawType& x) { fU.value = x; }
michael@0: 
michael@0:     /** Returns the exponent bits of this number. */
michael@0:     Bits exponent_bits() const { return kExponentBitMask & fU.bits; }
michael@0: 
michael@0:     /** Returns the fraction bits of this number. */
michael@0:     Bits fraction_bits() const { return kFractionBitMask & fU.bits; }
michael@0: 
michael@0:     /** Returns true iff this is NAN (not a number). */
michael@0:     bool is_nan() const {
michael@0:         // It's a NAN if both of the folloowing are true:
michael@0:         // * the exponent bits are all ones
michael@0:         // * the fraction bits are not all zero.
michael@0:         return (exponent_bits() == kExponentBitMask) && (fraction_bits() != 0);
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Returns true iff this number is at most kMaxUlps ULP's away from ths.
michael@0:      *  In particular, this function:
michael@0:      *   - returns false if either number is (or both are) NAN.
michael@0:      *   - treats really large numbers as almost equal to infinity.
michael@0:      *   - thinks +0.0 and -0.0 are 0 DLP's apart.
michael@0:      */
michael@0:     bool AlmostEquals(const SkFloatingPoint& rhs) const {
michael@0:         // Any comparison operation involving a NAN must return false.
michael@0:         if (is_nan() || rhs.is_nan()) return false;
michael@0: 
michael@0:         const Bits dist = DistanceBetweenSignAndMagnitudeNumbers(fU.bits,
michael@0:                                                                  rhs.fU.bits);
michael@0:         //SkDEBUGF(("(%f, %f, %d) ", u_.value_, rhs.u_.value_, dist));
michael@0:         return dist <= kMaxUlps;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     /** The data type used to store the actual floating-point number. */
michael@0:     union FloatingPointUnion {
michael@0:         /** The raw floating-point number. */
michael@0:         RawType value;
michael@0:         /** The bits that represent the number. */
michael@0:         Bits bits;
michael@0:     };
michael@0: 
michael@0:     /**
michael@0:      *  Converts an integer from the sign-and-magnitude representation to
michael@0:      *  the biased representation. More precisely, let N be 2 to the
michael@0:      *  power of (kBitCount - 1), an integer x is represented by the
michael@0:      *  unsigned number x + N.
michael@0:      *
michael@0:      *  For instance,
michael@0:      *
michael@0:      *    -N + 1 (the most negative number representable using
michael@0:      *           sign-and-magnitude) is represented by 1;
michael@0:      *    0      is represented by N; and
michael@0:      *    N - 1  (the biggest number representable using
michael@0:      *           sign-and-magnitude) is represented by 2N - 1.
michael@0:      *
michael@0:      *  Read http://en.wikipedia.org/wiki/Signed_number_representations
michael@0:      *  for more details on signed number representations.
michael@0:      */
michael@0:     static Bits SignAndMagnitudeToBiased(const Bits &sam) {
michael@0:         if (kSignBitMask & sam) {
michael@0:             // sam represents a negative number.
michael@0:             return ~sam + 1;
michael@0:         } else {
michael@0:             // sam represents a positive number.
michael@0:             return kSignBitMask | sam;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Given two numbers in the sign-and-magnitude representation,
michael@0:      *  returns the distance between them as an unsigned number.
michael@0:      */
michael@0:     static Bits DistanceBetweenSignAndMagnitudeNumbers(const Bits &sam1,
michael@0:                                                        const Bits &sam2) {
michael@0:         const Bits biased1 = SignAndMagnitudeToBiased(sam1);
michael@0:         const Bits biased2 = SignAndMagnitudeToBiased(sam2);
michael@0:         return (biased1 >= biased2) ? (biased1 - biased2) : (biased2 - biased1);
michael@0:     }
michael@0: 
michael@0:     FloatingPointUnion fU;
michael@0: };
michael@0: 
michael@0: #endif