1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef SkFloatUtils_DEFINED
9#define SkFloatUtils_DEFINED
10
11#include "SkTypes.h"
12#include <limits.h>
13#include <float.h>
14
15template <size_t size>
16class SkTypeWithSize {
17public:
18    // Prevents using SkTypeWithSize<N> with non-specialized N.
19    typedef void UInt;
20};
21
22template <>
23class SkTypeWithSize<32> {
24public:
25    typedef uint32_t UInt;
26};
27
28template <>
29class SkTypeWithSize<64> {
30public:
31    typedef uint64_t UInt;
32};
33
34template <typename RawType>
35struct SkNumericLimits {
36    static const int digits = 0;
37};
38
39template <>
40struct SkNumericLimits<double> {
41    static const int digits = DBL_MANT_DIG;
42};
43
44template <>
45struct SkNumericLimits<float> {
46    static const int digits = FLT_MANT_DIG;
47};
48
49//See
50//http://stackoverflow.com/questions/17333/most-effective-way-for-float-and-double-comparison/3423299#3423299
51//http://code.google.com/p/googletest/source/browse/trunk/include/gtest/internal/gtest-internal.h
52//http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
53
54template <typename RawType, unsigned int ULPs>
55class SkFloatingPoint {
56public:
57    /** Bits is a unsigned integer the same size as the floating point number. */
58    typedef typename SkTypeWithSize<sizeof(RawType) * CHAR_BIT>::UInt Bits;
59
60    /** # of bits in a number. */
61    static const size_t kBitCount = CHAR_BIT * sizeof(RawType);
62
63    /** # of fraction bits in a number. */
64    static const size_t kFractionBitCount = SkNumericLimits<RawType>::digits - 1;
65
66    /** # of exponent bits in a number. */
67    static const size_t kExponentBitCount = kBitCount - 1 - kFractionBitCount;
68
69    /** The mask for the sign bit. */
70    static const Bits kSignBitMask = static_cast<Bits>(1) << (kBitCount - 1);
71
72    /** The mask for the fraction bits. */
73    static const Bits kFractionBitMask =
74        ~static_cast<Bits>(0) >> (kExponentBitCount + 1);
75
76    /** The mask for the exponent bits. */
77    static const Bits kExponentBitMask = ~(kSignBitMask | kFractionBitMask);
78
79    /** How many ULP's (Units in the Last Place) to tolerate when comparing. */
80    static const size_t kMaxUlps = ULPs;
81
82    /**
83     *  Constructs a FloatingPoint from a raw floating-point number.
84     *
85     *  On an Intel CPU, passing a non-normalized NAN (Not a Number)
86     *  around may change its bits, although the new value is guaranteed
87     *  to be also a NAN.  Therefore, don't expect this constructor to
88     *  preserve the bits in x when x is a NAN.
89     */
90    explicit SkFloatingPoint(const RawType& x) { fU.value = x; }
91
92    /** Returns the exponent bits of this number. */
93    Bits exponent_bits() const { return kExponentBitMask & fU.bits; }
94
95    /** Returns the fraction bits of this number. */
96    Bits fraction_bits() const { return kFractionBitMask & fU.bits; }
97
98    /** Returns true iff this is NAN (not a number). */
99    bool is_nan() const {
100        // It's a NAN if both of the folloowing are true:
101        // * the exponent bits are all ones
102        // * the fraction bits are not all zero.
103        return (exponent_bits() == kExponentBitMask) && (fraction_bits() != 0);
104    }
105
106    /**
107     *  Returns true iff this number is at most kMaxUlps ULP's away from ths.
108     *  In particular, this function:
109     *   - returns false if either number is (or both are) NAN.
110     *   - treats really large numbers as almost equal to infinity.
111     *   - thinks +0.0 and -0.0 are 0 DLP's apart.
112     */
113    bool AlmostEquals(const SkFloatingPoint& rhs) const {
114        // Any comparison operation involving a NAN must return false.
115        if (is_nan() || rhs.is_nan()) return false;
116
117        const Bits dist = DistanceBetweenSignAndMagnitudeNumbers(fU.bits,
118                                                                 rhs.fU.bits);
119        //SkDEBUGF(("(%f, %f, %d) ", u_.value_, rhs.u_.value_, dist));
120        return dist <= kMaxUlps;
121    }
122
123private:
124    /** The data type used to store the actual floating-point number. */
125    union FloatingPointUnion {
126        /** The raw floating-point number. */
127        RawType value;
128        /** The bits that represent the number. */
129        Bits bits;
130    };
131
132    /**
133     *  Converts an integer from the sign-and-magnitude representation to
134     *  the biased representation. More precisely, let N be 2 to the
135     *  power of (kBitCount - 1), an integer x is represented by the
136     *  unsigned number x + N.
137     *
138     *  For instance,
139     *
140     *    -N + 1 (the most negative number representable using
141     *           sign-and-magnitude) is represented by 1;
142     *    0      is represented by N; and
143     *    N - 1  (the biggest number representable using
144     *           sign-and-magnitude) is represented by 2N - 1.
145     *
146     *  Read http://en.wikipedia.org/wiki/Signed_number_representations
147     *  for more details on signed number representations.
148     */
149    static Bits SignAndMagnitudeToBiased(const Bits &sam) {
150        if (kSignBitMask & sam) {
151            // sam represents a negative number.
152            return ~sam + 1;
153        } else {
154            // sam represents a positive number.
155            return kSignBitMask | sam;
156        }
157    }
158
159    /**
160     *  Given two numbers in the sign-and-magnitude representation,
161     *  returns the distance between them as an unsigned number.
162     */
163    static Bits DistanceBetweenSignAndMagnitudeNumbers(const Bits &sam1,
164                                                       const Bits &sam2) {
165        const Bits biased1 = SignAndMagnitudeToBiased(sam1);
166        const Bits biased2 = SignAndMagnitudeToBiased(sam2);
167        return (biased1 >= biased2) ? (biased1 - biased2) : (biased2 - biased1);
168    }
169
170    FloatingPointUnion fU;
171};
172
173#endif
174