boost/unordered/detail/prime_fmod.hpp
// Copyright (C) 2022 Joaquin M Lopez Munoz. // Copyright (C) 2022-2023 Christian Mazakas // // Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) #ifndef BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP #define BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP #include <boost/unordered/detail/narrow_cast.hpp> #include <boost/config.hpp> #include <boost/cstdint.hpp> #include <climits> #include <cstddef> #if defined(SIZE_MAX) #if ((((SIZE_MAX >> 16) >> 16) >> 16) >> 15) != 0 #define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T #endif #elif defined(UINTPTR_MAX) /* used as proxy for std::size_t */ #if ((((UINTPTR_MAX >> 16) >> 16) >> 16) >> 15) != 0 #define BOOST_UNORDERED_FCA_HAS_64B_SIZE_T #endif #endif #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) && defined(_MSC_VER) #include <intrin.h> #endif namespace boost { namespace unordered { namespace detail { template <class = void> struct prime_fmod_size { constexpr static std::size_t const sizes[] = {13ul, 29ul, 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, #if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) 4294967291ul #else 6442450939ull, 12884901893ull, 25769803751ull, 51539607551ull, 103079215111ull, 206158430209ull, 412316860441ull, 824633720831ull, 1649267441651ull #endif }; constexpr static std::size_t const sizes_len = sizeof(sizes) / sizeof(sizes[0]); #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) constexpr static boost::uint64_t const inv_sizes32[] = { 1418980313362273202ull, 636094623231363849ull, 348051774975651918ull, 190172619316593316ull, 95578984837873325ull, 47420935922132524ull, 23987963684927896ull, 11955116055547344ull, 5991147799191151ull, 2998982941588287ull, 1501077717772769ull, 750081082979285ull, 375261795343686ull, 187625172388393ull, 93822606204624ull, 46909513691883ull, 23456218233098ull, 11728086747027ull, 5864041509391ull, 2932024948977ull, 1466014921160ull, 733007198436ull, 366503839517ull, 183251896093ull, 91625960335ull, 45812983922ull, 22906489714ull, 11453246088ull, 5726623060ull}; constexpr static std::size_t const inv_sizes32_len = sizeof(inv_sizes32) / sizeof(inv_sizes32[0]); #endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */ template <std::size_t SizeIndex, std::size_t Size = sizes[SizeIndex]> static std::size_t position(std::size_t hash) { return hash % Size; } constexpr static std::size_t (*positions[])(std::size_t) = { #if !defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) position<0, sizes[0]>, position<1, sizes[1]>, position<2, sizes[2]>, position<3, sizes[3]>, position<4, sizes[4]>, position<5, sizes[5]>, position<6, sizes[6]>, position<7, sizes[7]>, position<8, sizes[8]>, position<9, sizes[9]>, position<10, sizes[10]>, position<11, sizes[11]>, position<12, sizes[12]>, position<13, sizes[13]>, position<14, sizes[14]>, position<15, sizes[15]>, position<16, sizes[16]>, position<17, sizes[17]>, position<18, sizes[18]>, position<19, sizes[19]>, position<20, sizes[20]>, position<21, sizes[21]>, position<22, sizes[22]>, position<23, sizes[23]>, position<24, sizes[24]>, position<25, sizes[25]>, position<26, sizes[26]>, position<27, sizes[27]>, position<28, sizes[28]>, position<29, sizes[29]>, #else position<29, sizes[29]>, position<30, sizes[30]>, position<31, sizes[31]>, position<32, sizes[32]>, position<33, sizes[33]>, position<34, sizes[34]>, position<35, sizes[35]>, position<36, sizes[36]>, position<37, sizes[37]>, #endif }; static inline std::size_t size_index(std::size_t n) { std::size_t i = 0; for (; i < (sizes_len - 1); ++i) { if (sizes[i] >= n) { break; } } return i; } static inline std::size_t size(std::size_t size_index) { return sizes[size_index]; } #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) // We emulate the techniques taken from: // Faster Remainder by Direct Computation: Applications to Compilers and // Software Libraries // https://arxiv.org/abs/1902.01961 // // In essence, use fancy math to directly calculate the remainder (aka // modulo) exploiting how compilers transform division // static inline boost::uint64_t get_remainder( boost::uint64_t fractional, boost::uint32_t d) { #if defined(_MSC_VER) // use MSVC intrinsics when available to avoid promotion to 128 bits return __umulh(fractional, d); #elif defined(BOOST_HAS_INT128) return static_cast<boost::uint64_t>( ((boost::uint128_type)fractional * d) >> 64); #else // portable implementation in the absence of boost::uint128_type on 64 // bits, which happens at least in GCC 4.5 and prior boost::uint64_t r1 = (fractional & UINT32_MAX) * d; boost::uint64_t r2 = (fractional >> 32) * d; r2 += r1 >> 32; return r2 >> 32; #endif /* defined(_MSC_VER) */ } static inline boost::uint32_t fast_modulo( boost::uint32_t a, boost::uint64_t M, boost::uint32_t d) { boost::uint64_t fractional = M * a; return (boost::uint32_t)(get_remainder(fractional, d)); } #endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */ static inline std::size_t position( std::size_t hash, std::size_t size_index) { #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) std::size_t sizes_under_32bit = inv_sizes32_len; if (BOOST_LIKELY(size_index < sizes_under_32bit)) { return fast_modulo(narrow_cast<boost::uint32_t>(hash) + narrow_cast<boost::uint32_t>(hash >> 32), inv_sizes32[size_index], boost::uint32_t(sizes[size_index])); } else { return positions[size_index - sizes_under_32bit](hash); } #else return positions[size_index](hash); #endif /* defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) */ } }; // prime_fmod_size #if defined(BOOST_NO_CXX17_INLINE_VARIABLES) // https://en.cppreference.com/w/cpp/language/static#Constant_static_members // If a const non-inline (since C++17) static data member or a constexpr // static data member (since C++11)(until C++17) is odr-used, a definition // at namespace scope is still required, but it cannot have an // initializer. template <class T> constexpr std::size_t prime_fmod_size<T>::sizes[]; #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T) template <class T> constexpr boost::uint64_t prime_fmod_size<T>::inv_sizes32[]; #endif template <class T> constexpr std::size_t (*prime_fmod_size<T>::positions[])(std::size_t); #endif } // namespace detail } // namespace unordered } // namespace boost #endif // BOOST_UNORDERED_DETAIL_PRIME_FMOD_HPP