1 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(BOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_HEADER) 7 #define BOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_HEADER 8 9 #include <boost/config.hpp> 10 #if defined(BOOST_HAS_PRAGMA_ONCE) 11 #pragma once 12 #endif 13 14 #include <boost/container_hash/detail/float_functions.hpp> 15 #include <boost/container_hash/detail/limits.hpp> 16 #include <boost/core/enable_if.hpp> 17 #include <boost/integer/static_log2.hpp> 18 #include <boost/cstdint.hpp> 19 #include <boost/assert.hpp> 20 #include <boost/limits.hpp> 21 #include <cstring> 22 23 #if defined(BOOST_MSVC) 24 #pragma warning(push) 25 #if BOOST_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 BOOST_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 BOOST_HASH_USE_FPCLASSIFY 1 42 # else 43 # define BOOST_HASH_USE_FPCLASSIFY 0 44 # endif 45 46 // Everything else 47 #else 48 # define BOOST_HASH_USE_FPCLASSIFY 0 49 #endif 50 51 namespace boost 52 { 53 namespace hash_detail 54 { hash_float_combine(std::size_t & seed,std::size_t value)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 hash_binary(char * ptr,std::size_t length)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 std::memcpy(&seed, ptr, sizeof(std::size_t)); 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, unsigned digits, unsigned max_exponent> 94 struct enable_binary_hash 95 { 96 BOOST_STATIC_CONSTANT(bool, value = 97 std::numeric_limits<Float>::is_iec559 && 98 std::numeric_limits<Float>::digits == digits && 99 std::numeric_limits<Float>::radix == 2 && 100 std::numeric_limits<Float>::max_exponent == max_exponent); 101 }; 102 103 template <typename Float> float_hash_impl(Float v,BOOST_DEDUCED_TYPENAME boost::enable_if_c<enable_binary_hash<Float,24,128>::value,std::size_t>::type)104 inline std::size_t float_hash_impl(Float v, 105 BOOST_DEDUCED_TYPENAME boost::enable_if_c< 106 enable_binary_hash<Float, 24, 128>::value, 107 std::size_t>::type) 108 { 109 return hash_binary((char*) &v, 4); 110 } 111 112 113 template <typename Float> float_hash_impl(Float v,BOOST_DEDUCED_TYPENAME boost::enable_if_c<enable_binary_hash<Float,53,1024>::value,std::size_t>::type)114 inline std::size_t float_hash_impl(Float v, 115 BOOST_DEDUCED_TYPENAME boost::enable_if_c< 116 enable_binary_hash<Float, 53, 1024>::value, 117 std::size_t>::type) 118 { 119 return hash_binary((char*) &v, 8); 120 } 121 122 template <typename Float> float_hash_impl(Float v,BOOST_DEDUCED_TYPENAME boost::enable_if_c<enable_binary_hash<Float,64,16384>::value,std::size_t>::type)123 inline std::size_t float_hash_impl(Float v, 124 BOOST_DEDUCED_TYPENAME boost::enable_if_c< 125 enable_binary_hash<Float, 64, 16384>::value, 126 std::size_t>::type) 127 { 128 return hash_binary((char*) &v, 10); 129 } 130 131 template <typename Float> float_hash_impl(Float v,BOOST_DEDUCED_TYPENAME boost::enable_if_c<enable_binary_hash<Float,113,16384>::value,std::size_t>::type)132 inline std::size_t float_hash_impl(Float v, 133 BOOST_DEDUCED_TYPENAME boost::enable_if_c< 134 enable_binary_hash<Float, 113, 16384>::value, 135 std::size_t>::type) 136 { 137 return hash_binary((char*) &v, 16); 138 } 139 140 //////////////////////////////////////////////////////////////////////// 141 // Portable hash function 142 // 143 // Used as a fallback when the binary hash function isn't supported. 144 145 template <class T> float_hash_impl2(T v)146 inline std::size_t float_hash_impl2(T v) 147 { 148 boost::hash_detail::call_frexp<T> frexp; 149 boost::hash_detail::call_ldexp<T> ldexp; 150 151 int exp = 0; 152 153 v = frexp(v, &exp); 154 155 // A postive value is easier to hash, so combine the 156 // sign with the exponent and use the absolute value. 157 if(v < 0) { 158 v = -v; 159 exp += limits<T>::max_exponent - 160 limits<T>::min_exponent; 161 } 162 163 v = ldexp(v, limits<std::size_t>::digits); 164 std::size_t seed = static_cast<std::size_t>(v); 165 v -= static_cast<T>(seed); 166 167 // ceiling(digits(T) * log2(radix(T))/ digits(size_t)) - 1; 168 std::size_t const length 169 = (limits<T>::digits * 170 boost::static_log2<limits<T>::radix>::value 171 + limits<std::size_t>::digits - 1) 172 / limits<std::size_t>::digits; 173 174 for(std::size_t i = 0; i != length; ++i) 175 { 176 v = ldexp(v, limits<std::size_t>::digits); 177 std::size_t part = static_cast<std::size_t>(v); 178 v -= static_cast<T>(part); 179 hash_float_combine(seed, part); 180 } 181 182 hash_float_combine(seed, static_cast<std::size_t>(exp)); 183 184 return seed; 185 } 186 187 #if !defined(BOOST_HASH_DETAIL_TEST_WITHOUT_GENERIC) 188 template <class T> float_hash_impl(T v,...)189 inline std::size_t float_hash_impl(T v, ...) 190 { 191 typedef BOOST_DEDUCED_TYPENAME select_hash_type<T>::type type; 192 return float_hash_impl2(static_cast<type>(v)); 193 } 194 #endif 195 } 196 } 197 198 #if BOOST_HASH_USE_FPCLASSIFY 199 200 #include <boost/config/no_tr1/cmath.hpp> 201 202 namespace boost 203 { 204 namespace hash_detail 205 { 206 template <class T> float_hash_value(T v)207 inline std::size_t float_hash_value(T v) 208 { 209 #if defined(fpclassify) 210 switch (fpclassify(v)) 211 #elif BOOST_HASH_CONFORMANT_FLOATS 212 switch (std::fpclassify(v)) 213 #else 214 using namespace std; 215 switch (fpclassify(v)) 216 #endif 217 { 218 case FP_ZERO: 219 return 0; 220 case FP_INFINITE: 221 return (std::size_t)(v > 0 ? -1 : -2); 222 case FP_NAN: 223 return (std::size_t)(-3); 224 case FP_NORMAL: 225 case FP_SUBNORMAL: 226 return float_hash_impl(v, 0); 227 default: 228 BOOST_ASSERT(0); 229 return 0; 230 } 231 } 232 } 233 } 234 235 #else // !BOOST_HASH_USE_FPCLASSIFY 236 237 namespace boost 238 { 239 namespace hash_detail 240 { 241 template <class T> is_zero(T v)242 inline bool is_zero(T v) 243 { 244 #if !defined(__GNUC__) && !defined(__clang__) 245 return v == 0; 246 #else 247 // GCC's '-Wfloat-equal' will complain about comparing 248 // v to 0, but because it disables warnings for system 249 // headers it won't complain if you use std::equal_to to 250 // compare with 0. Resulting in this silliness: 251 return std::equal_to<T>()(v, 0); 252 #endif 253 } 254 255 template <class T> float_hash_value(T v)256 inline std::size_t float_hash_value(T v) 257 { 258 return boost::hash_detail::is_zero(v) ? 0 : float_hash_impl(v, 0); 259 } 260 } 261 } 262 263 #endif // BOOST_HASH_USE_FPCLASSIFY 264 265 #undef BOOST_HASH_USE_FPCLASSIFY 266 267 #if defined(BOOST_MSVC) 268 #pragma warning(pop) 269 #endif 270 271 #endif 272