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