StdAir Logo  1.00.3
C++ Standard Airline IT Object Library
float_utils_google.hpp
Go to the documentation of this file.
1 #ifndef __STDAIR_BAS_FLOAT_UTILS_GOOGLE_HPP
2 #define __STDAIR_BAS_FLOAT_UTILS_GOOGLE_HPP
3 
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 // * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 //
30 // Authors: wan@google.com (Zhanyong Wan), eefacm@gmail.com (Sean Mcafee)
31 //
32 // The Google C++ Testing Framework (Google Test)
33 
34 
35 // This template class serves as a compile-time function from size to
36 // type. It maps a size in bytes to a primitive type with that
37 // size. e.g.
38 //
39 // TypeWithSize<4>::UInt
40 //
41 // is typedef-ed to be unsigned int (unsigned integer made up of 4
42 // bytes).
43 //
44 // Such functionality should belong to STL, but I cannot find it
45 // there.
46 //
47 // Google Test uses this class in the implementation of floating-point
48 // comparison.
49 //
50 // For now it only handles UInt (unsigned int) as that's all Google Test
51 // needs. Other types can be easily added in the future if need
52 // arises.
53 template <size_t size>
54 class TypeWithSize {
55  public:
56  // This prevents the user from using TypeWithSize<N> with incorrect
57  // values of N.
58  typedef void UInt;
59 };
60 
61 // The specialization for size 4.
62 template <>
63 class TypeWithSize<4> {
64  public:
65  // unsigned int has size 4 in both gcc and MSVC.
66  //
67  // As base/basictypes.h doesn't compile on Windows, we cannot use
68  // uint32, uint64, and etc here.
69  typedef int Int;
70  typedef unsigned int UInt;
71 };
72 
73 // The specialization for size 8.
74 template <>
75 class TypeWithSize<8> {
76  public:
77 #if GTEST_OS_WINDOWS
78  typedef __int64 Int;
79  typedef unsigned __int64 UInt;
80 #else
81  typedef long long Int; // NOLINT
82  typedef unsigned long long UInt; // NOLINT
83 #endif // GTEST_OS_WINDOWS
84 };
85 
86 
87 // This template class represents an IEEE floating-point number
88 // (either single-precision or double-precision, depending on the
89 // template parameters).
90 //
91 // The purpose of this class is to do more sophisticated number
92 // comparison. (Due to round-off error, etc, it's very unlikely that
93 // two floating-points will be equal exactly. Hence a naive
94 // comparison by the == operation often doesn't work.)
95 //
96 // Format of IEEE floating-point:
97 //
98 // The most-significant bit being the leftmost, an IEEE
99 // floating-point looks like
100 //
101 // sign_bit exponent_bits fraction_bits
102 //
103 // Here, sign_bit is a single bit that designates the sign of the
104 // number.
105 //
106 // For float, there are 8 exponent bits and 23 fraction bits.
107 //
108 // For double, there are 11 exponent bits and 52 fraction bits.
109 //
110 // More details can be found at
111 // http://en.wikipedia.org/wiki/IEEE_floating-point_standard.
112 //
113 // Template parameter:
114 //
115 // RawType: the raw floating-point type (either float or double)
116 template <typename RawType>
118  public:
119  // Defines the unsigned integer type that has the same size as the
120  // floating point number.
122 
123  // Constants.
124 
125  // # of bits in a number.
126  static const size_t kBitCount = 8*sizeof(RawType);
127 
128  // # of fraction bits in a number.
129  static const size_t kFractionBitCount =
130  std::numeric_limits<RawType>::digits - 1;
131 
132  // # of exponent bits in a number.
133  static const size_t kExponentBitCount = kBitCount - 1 - kFractionBitCount;
134 
135  // The mask for the sign bit.
136  static const Bits kSignBitMask = static_cast<Bits>(1) << (kBitCount - 1);
137 
138  // The mask for the fraction bits.
139  static const Bits kFractionBitMask =
140  ~static_cast<Bits>(0) >> (kExponentBitCount + 1);
141 
142  // The mask for the exponent bits.
143  static const Bits kExponentBitMask = ~(kSignBitMask | kFractionBitMask);
144 
145  // How many ULP's (Units in the Last Place) we want to tolerate when
146  // comparing two numbers. The larger the value, the more error we
147  // allow. A 0 value means that two numbers must be exactly the same
148  // to be considered equal.
149  //
150  // The maximum error of a single floating-point operation is 0.5
151  // units in the last place. On Intel CPU's, all floating-point
152  // calculations are done with 80-bit precision, while double has 64
153  // bits. Therefore, 4 should be enough for ordinary use.
154  //
155  // See the following article for more details on ULP:
156  // http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm.
157  static const size_t kMaxUlps = 4;
158 
159  // Constructs a FloatingPoint from a raw floating-point number.
160  //
161  // On an Intel CPU, passing a non-normalized NAN (Not a Number)
162  // around may change its bits, although the new value is guaranteed
163  // to be also a NAN. Therefore, don't expect this constructor to
164  // preserve the bits in x when x is a NAN.
165  explicit FloatingPoint(const RawType& x) { u_.value_ = x; }
166 
167  // Static methods
168 
169  // Reinterprets a bit pattern as a floating-point number.
170  //
171  // This function is needed to test the AlmostEquals() method.
172  static RawType ReinterpretBits(const Bits bits) {
173  FloatingPoint fp(0);
174  fp.u_.bits_ = bits;
175  return fp.u_.value_;
176  }
177 
178  // Returns the floating-point number that represent positive infinity.
179  static RawType Infinity() {
180  return ReinterpretBits(kExponentBitMask);
181  }
182 
183  // Non-static methods
184 
185  // Returns the bits that represents this number.
186  const Bits &bits() const { return u_.bits_; }
187 
188  // Returns the exponent bits of this number.
189  Bits exponent_bits() const { return kExponentBitMask & u_.bits_; }
190 
191  // Returns the fraction bits of this number.
192  Bits fraction_bits() const { return kFractionBitMask & u_.bits_; }
193 
194  // Returns the sign bit of this number.
195  Bits sign_bit() const { return kSignBitMask & u_.bits_; }
196 
197  // Returns true iff this is NAN (not a number).
198  bool is_nan() const {
199  // It's a NAN if the exponent bits are all ones and the fraction
200  // bits are not entirely zeros.
201  return (exponent_bits() == kExponentBitMask) && (fraction_bits() != 0);
202  }
203 
204  // Returns true iff this number is at most kMaxUlps ULP's away from
205  // rhs. In particular, this function:
206  //
207  // - returns false if either number is (or both are) NAN.
208  // - treats really large numbers as almost equal to infinity.
209  // - thinks +0.0 and -0.0 are 0 DLP's apart.
210  bool AlmostEquals(const FloatingPoint& rhs) const {
211  // The IEEE standard says that any comparison operation involving
212  // a NAN must return false.
213  if (is_nan() || rhs.is_nan()) return false;
214 
215  return DistanceBetweenSignAndMagnitudeNumbers(u_.bits_, rhs.u_.bits_)
216  <= kMaxUlps;
217  }
218 
219  private:
220  // The data type used to store the actual floating-point number.
221  union FloatingPointUnion {
222  RawType value_; // The raw floating-point number.
223  Bits bits_; // The bits that represent the number.
224  };
225 
226  // Converts an integer from the sign-and-magnitude representation to
227  // the biased representation. More precisely, let N be 2 to the
228  // power of (kBitCount - 1), an integer x is represented by the
229  // unsigned number x + N.
230  //
231  // For instance,
232  //
233  // -N + 1 (the most negative number representable using
234  // sign-and-magnitude) is represented by 1;
235  // 0 is represented by N; and
236  // N - 1 (the biggest number representable using
237  // sign-and-magnitude) is represented by 2N - 1.
238  //
239  // Read http://en.wikipedia.org/wiki/Signed_number_representations
240  // for more details on signed number representations.
241  static Bits SignAndMagnitudeToBiased(const Bits &sam) {
242  if (kSignBitMask & sam) {
243  // sam represents a negative number.
244  return ~sam + 1;
245  } else {
246  // sam represents a positive number.
247  return kSignBitMask | sam;
248  }
249  }
250 
251  // Given two numbers in the sign-and-magnitude representation,
252  // returns the distance between them as an unsigned number.
253  static Bits DistanceBetweenSignAndMagnitudeNumbers(const Bits &sam1,
254  const Bits &sam2) {
255  const Bits biased1 = SignAndMagnitudeToBiased(sam1);
256  const Bits biased2 = SignAndMagnitudeToBiased(sam2);
257  return (biased1 >= biased2) ? (biased1 - biased2) : (biased2 - biased1);
258  }
259 
260  FloatingPointUnion u_;
261 };
262 
263 #endif // __STDAIR_BAS_FLOAT_UTILS_GOOGLE_HPP
static const size_t kBitCount
Bits fraction_bits() const
static RawType ReinterpretBits(const Bits bits)
static const Bits kExponentBitMask
static const size_t kExponentBitCount
static const Bits kSignBitMask
TypeWithSize< sizeof(RawType)>::UInt Bits
Bits exponent_bits() const
static const size_t kMaxUlps
static const size_t kFractionBitCount
bool is_nan() const
static const Bits kFractionBitMask
Bits sign_bit() const
unsigned long long UInt
static RawType Infinity()
bool AlmostEquals(const FloatingPoint &rhs) const
const Bits & bits() const
FloatingPoint(const RawType &x)