OpenTREP Logo  0.07.18
C++ Open Travel Request Parsing Library
Loading...
Searching...
No Matches
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.
60template <size_t size>
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.
69template <>
70class 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.
81template <>
82class 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)
123template <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
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
const Bits & bits() const
static const size_t kBitCount
static const size_t kFractionBitCount
unsigned long long UInt