blob: 76873ae5a52a84fb985c87c23ecb15af5a743163 [file] [log] [blame]
Jeff Thompson86b6d642013-10-17 15:01:56 -07001
2// Copyright 2005-2012 Daniel James.
3// Distributed under the Boost Software License, Version 1.0. (See accompanying
4// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5
6#if !defined(NDNBOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_HEADER)
7#define NDNBOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_HEADER
8
9#if defined(_MSC_VER) && (_MSC_VER >= 1020)
10# pragma once
11#endif
12
13#include <ndnboost/config.hpp>
14#include <ndnboost/functional/hash/detail/float_functions.hpp>
15#include <ndnboost/functional/hash/detail/limits.hpp>
16#include <ndnboost/utility/enable_if.hpp>
17#include <ndnboost/integer/static_log2.hpp>
18#include <ndnboost/cstdint.hpp>
19#include <ndnboost/assert.hpp>
20#include <ndnboost/limits.hpp>
21#include <cstring>
22
23#if defined(NDNBOOST_MSVC)
24#pragma warning(push)
25#if NDNBOOST_MSVC >= 1400
26#pragma warning(disable:6294) // Ill-defined for-loop: initial condition does
27 // not satisfy test. Loop body not executed
28#endif
29#endif
30
31// Can we use fpclassify?
32
33// STLport
34#if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION)
35#define NDNBOOST_HASH_USE_FPCLASSIFY 0
36
37// GNU libstdc++ 3
38#elif defined(__GLIBCPP__) || defined(__GLIBCXX__)
39# if (defined(__USE_ISOC99) || defined(_GLIBCXX_USE_C99_MATH)) && \
40 !(defined(macintosh) || defined(__APPLE__) || defined(__APPLE_CC__))
41# define NDNBOOST_HASH_USE_FPCLASSIFY 1
42# else
43# define NDNBOOST_HASH_USE_FPCLASSIFY 0
44# endif
45
46// Everything else
47#else
48# define NDNBOOST_HASH_USE_FPCLASSIFY 0
49#endif
50
51namespace ndnboost
52{
53 namespace hash_detail
54 {
55 inline void hash_float_combine(std::size_t& seed, std::size_t value)
56 {
57 seed ^= value + (seed<<6) + (seed>>2);
58 }
59
60 ////////////////////////////////////////////////////////////////////////
61 // Binary hash function
62 //
63 // Only used for floats with known iec559 floats, and certain values in
64 // numeric_limits
65
66 inline std::size_t hash_binary(char* ptr, std::size_t length)
67 {
68 std::size_t seed = 0;
69
70 if (length >= sizeof(std::size_t)) {
71 seed = *(std::size_t*) ptr;
72 length -= sizeof(std::size_t);
73 ptr += sizeof(std::size_t);
74
75 while(length >= sizeof(std::size_t)) {
76 std::size_t buffer = 0;
77 std::memcpy(&buffer, ptr, sizeof(std::size_t));
78 hash_float_combine(seed, buffer);
79 length -= sizeof(std::size_t);
80 ptr += sizeof(std::size_t);
81 }
82 }
83
84 if (length > 0) {
85 std::size_t buffer = 0;
86 std::memcpy(&buffer, ptr, length);
87 hash_float_combine(seed, buffer);
88 }
89
90 return seed;
91 }
92
93 template <typename Float>
94 inline std::size_t float_hash_impl(Float v,
95 NDNBOOST_DEDUCED_TYPENAME ndnboost::enable_if_c<
96 std::numeric_limits<Float>::is_iec559 &&
97 std::numeric_limits<Float>::digits == 24 &&
98 std::numeric_limits<Float>::radix == 2 &&
99 std::numeric_limits<Float>::max_exponent == 128,
100 int>::type
101 )
102 {
103 return hash_binary((char*) &v, 4);
104 }
105
106
107 template <typename Float>
108 inline std::size_t float_hash_impl(Float v,
109 NDNBOOST_DEDUCED_TYPENAME ndnboost::enable_if_c<
110 std::numeric_limits<Float>::is_iec559 &&
111 std::numeric_limits<Float>::digits == 53 &&
112 std::numeric_limits<Float>::radix == 2 &&
113 std::numeric_limits<Float>::max_exponent == 1024,
114 int>::type
115 )
116 {
117 return hash_binary((char*) &v, 8);
118 }
119
120 template <typename Float>
121 inline std::size_t float_hash_impl(Float v,
122 NDNBOOST_DEDUCED_TYPENAME ndnboost::enable_if_c<
123 std::numeric_limits<Float>::is_iec559 &&
124 std::numeric_limits<Float>::digits == 64 &&
125 std::numeric_limits<Float>::radix == 2 &&
126 std::numeric_limits<Float>::max_exponent == 16384,
127 int>::type
128 )
129 {
130 return hash_binary((char*) &v, 10);
131 }
132
133 template <typename Float>
134 inline std::size_t float_hash_impl(Float v,
135 NDNBOOST_DEDUCED_TYPENAME ndnboost::enable_if_c<
136 std::numeric_limits<Float>::is_iec559 &&
137 std::numeric_limits<Float>::digits == 113 &&
138 std::numeric_limits<Float>::radix == 2 &&
139 std::numeric_limits<Float>::max_exponent == 16384,
140 int>::type
141 )
142 {
143 return hash_binary((char*) &v, 16);
144 }
145
146 ////////////////////////////////////////////////////////////////////////
147 // Portable hash function
148 //
149 // Used as a fallback when the binary hash function isn't supported.
150
151 template <class T>
152 inline std::size_t float_hash_impl2(T v)
153 {
154 ndnboost::hash_detail::call_frexp<T> frexp;
155 ndnboost::hash_detail::call_ldexp<T> ldexp;
156
157 int exp = 0;
158
159 v = frexp(v, &exp);
160
161 // A postive value is easier to hash, so combine the
162 // sign with the exponent and use the absolute value.
163 if(v < 0) {
164 v = -v;
165 exp += limits<T>::max_exponent -
166 limits<T>::min_exponent;
167 }
168
169 v = ldexp(v, limits<std::size_t>::digits);
170 std::size_t seed = static_cast<std::size_t>(v);
171 v -= static_cast<T>(seed);
172
173 // ceiling(digits(T) * log2(radix(T))/ digits(size_t)) - 1;
174 std::size_t const length
175 = (limits<T>::digits *
176 ndnboost::static_log2<limits<T>::radix>::value
177 + limits<std::size_t>::digits - 1)
178 / limits<std::size_t>::digits;
179
180 for(std::size_t i = 0; i != length; ++i)
181 {
182 v = ldexp(v, limits<std::size_t>::digits);
183 std::size_t part = static_cast<std::size_t>(v);
184 v -= static_cast<T>(part);
185 hash_float_combine(seed, part);
186 }
187
188 hash_float_combine(seed, exp);
189
190 return seed;
191 }
192
193#if !defined(NDNBOOST_HASH_DETAIL_TEST_WITHOUT_GENERIC)
194 template <class T>
195 inline std::size_t float_hash_impl(T v, ...)
196 {
197 typedef NDNBOOST_DEDUCED_TYPENAME select_hash_type<T>::type type;
198 return float_hash_impl2(static_cast<type>(v));
199 }
200#endif
201 }
202}
203
204#if NDNBOOST_HASH_USE_FPCLASSIFY
205
206#include <ndnboost/config/no_tr1/cmath.hpp>
207
208namespace ndnboost
209{
210 namespace hash_detail
211 {
212 template <class T>
213 inline std::size_t float_hash_value(T v)
214 {
215#if defined(fpclassify)
216 switch (fpclassify(v))
217#elif NDNBOOST_HASH_CONFORMANT_FLOATS
218 switch (std::fpclassify(v))
219#else
220 using namespace std;
221 switch (fpclassify(v))
222#endif
223 {
224 case FP_ZERO:
225 return 0;
226 case FP_INFINITE:
227 return (std::size_t)(v > 0 ? -1 : -2);
228 case FP_NAN:
229 return (std::size_t)(-3);
230 case FP_NORMAL:
231 case FP_SUBNORMAL:
232 return float_hash_impl(v, 0);
233 default:
234 NDNBOOST_ASSERT(0);
235 return 0;
236 }
237 }
238 }
239}
240
241#else // !NDNBOOST_HASH_USE_FPCLASSIFY
242
243namespace ndnboost
244{
245 namespace hash_detail
246 {
247 template <class T>
248 inline bool is_zero(T v)
249 {
250#if !defined(__GNUC__)
251 return v == 0;
252#else
253 // GCC's '-Wfloat-equal' will complain about comparing
254 // v to 0, but because it disables warnings for system
255 // headers it won't complain if you use std::equal_to to
256 // compare with 0. Resulting in this silliness:
257 return std::equal_to<T>()(v, 0);
258#endif
259 }
260
261 template <class T>
262 inline std::size_t float_hash_value(T v)
263 {
264 return ndnboost::hash_detail::is_zero(v) ? 0 : float_hash_impl(v, 0);
265 }
266 }
267}
268
269#endif // NDNBOOST_HASH_USE_FPCLASSIFY
270
271#undef NDNBOOST_HASH_USE_FPCLASSIFY
272
273#if defined(NDNBOOST_MSVC)
274#pragma warning(pop)
275#endif
276
277#endif