1 | // |
2 | // immer: immutable data structures for C++ |
3 | // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente |
4 | // |
5 | // This software is distributed under the Boost Software License, Version 1.0. |
6 | // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt |
7 | // |
8 | |
9 | #pragma once |
10 | |
11 | #include <cstdint> |
12 | |
13 | #if defined(_MSC_VER) |
14 | #include <intrin.h> // __popcnt |
15 | #endif |
16 | |
17 | namespace immer { |
18 | namespace detail { |
19 | namespace hamts { |
20 | |
21 | using size_t = std::size_t; |
22 | using hash_t = std::size_t; |
23 | using bits_t = std::uint32_t; |
24 | using count_t = std::uint32_t; |
25 | using shift_t = std::uint32_t; |
26 | |
27 | template <bits_t B> |
28 | struct get_bitmap_type |
29 | { |
30 | static_assert(B < 6u, "B > 6 is not supported." ); |
31 | |
32 | using type = std::uint32_t; |
33 | }; |
34 | |
35 | template <> |
36 | struct get_bitmap_type<6u> |
37 | { |
38 | using type = std::uint64_t; |
39 | }; |
40 | |
41 | template <bits_t B, typename T=count_t> |
42 | constexpr T branches = T{1u} << B; |
43 | |
44 | template <bits_t B, typename T=size_t> |
45 | constexpr T mask = branches<B, T> - 1u; |
46 | |
47 | template <bits_t B, typename T=count_t> |
48 | constexpr T max_depth = (sizeof(hash_t) * 8u + B - 1u) / B; |
49 | |
50 | template <bits_t B, typename T=count_t> |
51 | constexpr T max_shift = max_depth<B, count_t> * B; |
52 | |
53 | #define IMMER_HAS_BUILTIN_POPCOUNT 1 |
54 | |
55 | inline auto popcount_fallback(std::uint32_t x) |
56 | { |
57 | // More alternatives: |
58 | // https://en.wikipedia.org/wiki/Hamming_weight |
59 | // http://wm.ite.pl/articles/sse-popcount.html |
60 | // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel |
61 | x = x - ((x >> 1) & 0x55555555u); |
62 | x = (x & 0x33333333u) + ((x >> 2) & 0x33333333u); |
63 | return (((x + (x >> 4u)) & 0xF0F0F0Fu) * 0x1010101u) >> 24u; |
64 | } |
65 | |
66 | inline auto popcount_fallback(std::uint64_t x) |
67 | { |
68 | x = x - ((x >> 1) & 0x5555555555555555u); |
69 | x = (x & 0x3333333333333333u) + ((x >> 2u) & 0x3333333333333333u); |
70 | return (((x + (x >> 4)) & 0x0F0F0F0F0F0F0F0Fu) * 0x0101010101010101u) >> 56u; |
71 | } |
72 | |
73 | inline count_t popcount(std::uint32_t x) |
74 | { |
75 | #if IMMER_HAS_BUILTIN_POPCOUNT |
76 | # if defined(_MSC_VER) |
77 | return __popcnt(x); |
78 | # else |
79 | return __builtin_popcount(x); |
80 | # endif |
81 | #else |
82 | return popcount_fallback(x); |
83 | #endif |
84 | } |
85 | |
86 | inline count_t popcount(std::uint64_t x) |
87 | { |
88 | #if IMMER_HAS_BUILTIN_POPCOUNT |
89 | # if defined(_MSC_VER) |
90 | # if defined(_WIN64) |
91 | return __popcnt64(x); |
92 | # else |
93 | // TODO: benchmark against popcount_fallback(std::uint64_t x) |
94 | return popcount(static_cast<std::uint32_t>(x >> 32)) |
95 | + popcount(static_cast<std::uint32_t>(x)); |
96 | # endif |
97 | # else |
98 | return __builtin_popcountll(x); |
99 | # endif |
100 | #else |
101 | return popcount_fallback(x); |
102 | #endif |
103 | } |
104 | |
105 | } // namespace hamts |
106 | } // namespace detail |
107 | } // namespace immer |
108 | |