OpenTREP Logo  0.07.11
C++ Open Travel Request Parsing Library
float_utils_google.hpp
Go to the documentation of this file.
1 #ifndef __OPENTREP_BAS_FLOAT_UTILS_GOOGLE_HPP
2 #define __OPENTREP_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 // License: MIT
32 //
33 // The Google C++ Testing Framework (Google Test)
34 
35 // //////////////////////////////////////////////////////////////////////
36 // Import section
37 // //////////////////////////////////////////////////////////////////////
38 // STL
39 #include <limits>
40 
41 
42 // This template class serves as a compile-time function from size to
43 // type. It maps a size in bytes to a primitive type with that
44 // size. e.g.
45 //
46 // TypeWithSize<4>::UInt
47 //
48 // is typedef-ed to be unsigned int (unsigned integer made up of 4
49 // bytes).
50 //
51 // Such functionality should belong to STL, but I cannot find it
52 // there.
53 //
54 // Google Test uses this class in the implementation of floating-point
55 // comparison.
56 //
57 // For now it only handles UInt (unsigned int) as that's all Google Test
58 // needs. Other types can be easily added in the future if need
59 // arises.
60 template <size_t size>
61 class TypeWithSize {
62  public:
63  // This prevents the user from using TypeWithSize<N> with incorrect
64  // values of N.
65  typedef void UInt;
66 };
67 
68 // The specialization for size 4.
69 template <>
70 class TypeWithSize<4> {
71  public:
72  // unsigned int has size 4 in both gcc and MSVC.
73  //
74  // As base/basictypes.h doesn't compile on Windows, we cannot use
75  // uint32, uint64, and etc here.
76  typedef int Int;
77  typedef unsigned int UInt;
78 };
79 
80 // The specialization for size 8.
81 template <>
82 class TypeWithSize<8> {
83  public:
84 #if GTEST_OS_WINDOWS
85  typedef __int64 Int;
86  typedef unsigned __int64 UInt;
87 #else
88  typedef long long Int; // NOLINT
89  typedef unsigned long long UInt; // NOLINT
90 #endif // GTEST_OS_WINDOWS
91 };
92 
93 
94 // This template class represents an IEEE floating-point number
95 // (either single-precision or double-precision, depending on the
96 // template parameters).
97 //
98 // The purpose of this class is to do more sophisticated number
99 // comparison. (Due to round-off error, etc, it's very unlikely that
100 // two floating-points will be equal exactly. Hence a naive
101 // comparison by the == operation often doesn't work.)
102 //
103 // Format of IEEE floating-point:
104 //
105 // The most-significant bit being the leftmost, an IEEE
106 // floating-point looks like
107 //
108 // sign_bit exponent_bits fraction_bits
109 //
110 // Here, sign_bit is a single bit that designates the sign of the
111 // number.
112 //
113 // For float, there are 8 exponent bits and 23 fraction bits.
114 //
115 // For double, there are 11 exponent bits and 52 fraction bits.
116 //
117 // More details can be found at
118 // http://en.wikipedia.org/wiki/IEEE_floating-point_standard.
119 //
120 // Template parameter:
121 //
122 // RawType: the raw floating-point type (either float or double)
123 template <typename RawType>
125  public:
126  // Defines the unsigned integer type that has the same size as the
127  // floating point number.
128  typedef typename TypeWithSize<sizeof(RawType)>::UInt Bits;
129 
130  // Constants.
131 
132  // # of bits in a number.
133  static const size_t kBitCount = 8*sizeof(RawType);
134 
135  // # of fraction bits in a number.
136  static const size_t kFractionBitCount =
137  std::numeric_limits<RawType>::digits - 1;
138 
139  // # of exponent bits in a number.
140  static const size_t kExponentBitCount = kBitCount - 1 - kFractionBitCount;
141 
142  // The mask for the sign bit.
143  static const Bits kSignBitMask = static_cast<Bits>(1) << (kBitCount - 1);
144 
145  // The mask for the fraction bits.
146  static const Bits kFractionBitMask =
147  ~static_cast<Bits>(0) >> (kExponentBitCount + 1);
148 
149  // The mask for the exponent bits.
151 
152  // How many ULP's (Units in the Last Place) we want to tolerate when
153  // comparing two numbers. The larger the value, the more error we
154  // allow. A 0 value means that two numbers must be exactly the same
155  // to be considered equal.
156  //
157  // The maximum error of a single floating-point operation is 0.5
158  // units in the last place. On Intel CPU's, all floating-point
159  // calculations are done with 80-bit precision, while double has 64
160  // bits. Therefore, 4 should be enough for ordinary use.
161  //
162  // See the following article for more details on ULP:
163  // http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm.
164  static const size_t kMaxUlps = 4;
165 
166  // Constructs a FloatingPoint from a raw floating-point number.
167  //
168  // On an Intel CPU, passing a non-normalized NAN (Not a Number)
169  // around may change its bits, although the new value is guaranteed
170  // to be also a NAN. Therefore, don't expect this constructor to
171  // preserve the bits in x when x is a NAN.
172  explicit FloatingPoint (const RawType& x) { u_.value_ = x; }
173 
174  // Static methods
175 
176  // Reinterprets a bit pattern as a floating-point number.
177  //
178  // This function is needed to test the AlmostEquals() method.
179  static RawType ReinterpretBits(const Bits bits) {
180  FloatingPoint fp(0);
181  fp.u_.bits_ = bits;
182  return fp.u_.value_;
183  }
184 
185  // Returns the floating-point number that represent positive infinity.
186  static RawType Infinity() {
188  }
189 
190  // Non-static methods
191 
192  // Returns the bits that represents this number.
193  const Bits &bits() const { return u_.bits_; }
194 
195  // Returns the exponent bits of this number.
196  Bits exponent_bits() const { return kExponentBitMask & u_.bits_; }
197 
198  // Returns the fraction bits of this number.
199  Bits fraction_bits() const { return kFractionBitMask & u_.bits_; }
200 
201  // Returns the sign bit of this number.
202  Bits sign_bit() const { return kSignBitMask & u_.bits_; }
203 
204  // Returns true iff this is NAN (not a number).
205  bool is_nan() const {
206  // It's a NAN if the exponent bits are all ones and the fraction
207  // bits are not entirely zeros.
208  return (exponent_bits() == kExponentBitMask) && (fraction_bits() != 0);
209  }
210 
211  // Returns true iff this number is at most kMaxUlps ULP's away from
212  // rhs. In particular, this function:
213  //
214  // - returns false if either number is (or both are) NAN.
215  // - treats really large numbers as almost equal to infinity.
216  // - thinks +0.0 and -0.0 are 0 DLP's apart.
217  bool AlmostEquals(const FloatingPoint& rhs) const {
218  // The IEEE standard says that any comparison operation involving
219  // a NAN must return false.
220  if (is_nan() || rhs.is_nan()) return false;
221 
222  return DistanceBetweenSignAndMagnitudeNumbers(u_.bits_, rhs.u_.bits_)
223  <= kMaxUlps;
224  }
225 
226  private:
227  // The data type used to store the actual floating-point number.
228  union FloatingPointUnion {
229  RawType value_; // The raw floating-point number.
230  Bits bits_; // The bits that represent the number.
231  };
232 
233  // Converts an integer from the sign-and-magnitude representation to
234  // the biased representation. More precisely, let N be 2 to the
235  // power of (kBitCount - 1), an integer x is represented by the
236  // unsigned number x + N.
237  //
238  // For instance,
239  //
240  // -N + 1 (the most negative number representable using
241  // sign-and-magnitude) is represented by 1;
242  // 0 is represented by N; and
243  // N - 1 (the biggest number representable using
244  // sign-and-magnitude) is represented by 2N - 1.
245  //
246  // Read http://en.wikipedia.org/wiki/Signed_number_representations
247  // for more details on signed number representations.
248  static Bits SignAndMagnitudeToBiased(const Bits &sam) {
249  if (kSignBitMask & sam) {
250  // sam represents a negative number.
251  return ~sam + 1;
252  } else {
253  // sam represents a positive number.
254  return kSignBitMask | sam;
255  }
256  }
257 
258  // Given two numbers in the sign-and-magnitude representation,
259  // returns the distance between them as an unsigned number.
260  static Bits DistanceBetweenSignAndMagnitudeNumbers(const Bits &sam1,
261  const Bits &sam2) {
262  const Bits biased1 = SignAndMagnitudeToBiased(sam1);
263  const Bits biased2 = SignAndMagnitudeToBiased(sam2);
264  return (biased1 >= biased2) ? (biased1 - biased2) : (biased2 - biased1);
265  }
266 
267  FloatingPointUnion u_;
268 };
269 
270 #endif // __OPENTREP_BAS_FLOAT_UTILS_GOOGLE_HPP
static const size_t kExponentBitCount
static const Bits kSignBitMask
FloatingPoint(const RawType &x)
bool AlmostEquals(const FloatingPoint &rhs) const
const Bits & bits() const
static const Bits kFractionBitMask
Bits fraction_bits() const
static const Bits kExponentBitMask
static RawType ReinterpretBits(const Bits bits)
TypeWithSize< sizeof(RawType)>::UInt Bits
static RawType Infinity()
Bits exponent_bits() const
static const size_t kMaxUlps
static const size_t kBitCount
Bits sign_bit() const
static const size_t kFractionBitCount
unsigned long long UInt