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
17namespace immer {
18namespace detail {
19namespace hamts {
20
21using size_t = std::size_t;
22using hash_t = std::size_t;
23using bits_t = std::uint32_t;
24using count_t = std::uint32_t;
25using shift_t = std::uint32_t;
26
27template <bits_t B>
28struct get_bitmap_type
29{
30 static_assert(B < 6u, "B > 6 is not supported.");
31
32 using type = std::uint32_t;
33};
34
35template <>
36struct get_bitmap_type<6u>
37{
38 using type = std::uint64_t;
39};
40
41template <bits_t B, typename T=count_t>
42constexpr T branches = T{1u} << B;
43
44template <bits_t B, typename T=size_t>
45constexpr T mask = branches<B, T> - 1u;
46
47template <bits_t B, typename T=count_t>
48constexpr T max_depth = (sizeof(hash_t) * 8u + B - 1u) / B;
49
50template <bits_t B, typename T=count_t>
51constexpr T max_shift = max_depth<B, count_t> * B;
52
53#define IMMER_HAS_BUILTIN_POPCOUNT 1
54
55inline 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
66inline 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
73inline 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
86inline 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