primecount 0.2.1

Rust wrapper for https://github.com/kimwalisch/primecount
Documentation 
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

///
/// @file  popcnt.hpp
/// @brief Functions to count the number of 1 bits inside
///        an array or a 64-bit word.
///
/// Copyright (C) 2021 Kim Walisch, <kim.walisch@gmail.com>
///
/// This file is distributed under the BSD License. See the COPYING
/// file in the top level directory.
///

#ifndef POPCNT_HPP
#define POPCNT_HPP

#include <stdint.h>

#if defined(__has_include)
  #define HAS_INCLUDE(header) __has_include(header)
#else
  // If the __has_include() macro does not exist
  // we assume that the header file exists.
  #define HAS_INCLUDE(header) 1
#endif

#if !defined(__has_builtin)
  #define __has_builtin(x) 0
#endif

// GCC & Clang
#if defined(__GNUC__) || \
    __has_builtin(__builtin_popcountl)

namespace {

inline uint64_t popcnt64(uint64_t x)
{
#if __cplusplus >= 201703L
  if constexpr(sizeof(int) >= sizeof(uint64_t))
    return (uint64_t) __builtin_popcount(x);
  else if constexpr(sizeof(long) >= sizeof(uint64_t))
    return (uint64_t) __builtin_popcountl(x);
  else if constexpr(sizeof(long long) >= sizeof(uint64_t))
    return (uint64_t) __builtin_popcountll(x);
#else
    return (uint64_t) __builtin_popcountll(x);
#endif
}

} // namespace

#elif defined(_MSC_VER) && \
      !defined(DISABLE_POPCNT) && \
      defined(_M_X64) && \
      HAS_INCLUDE(<intrin.h>)

#include <intrin.h>

namespace {

inline uint64_t popcnt64(uint64_t x)
{
  return __popcnt64(x);
}

} // namespace

#elif defined(_MSC_VER) && \
      !defined(DISABLE_POPCNT) && \
      defined(_M_IX86) && \
      HAS_INCLUDE(<intrin.h>)

#include <intrin.h>

namespace {

inline uint64_t popcnt64(uint64_t x)
{
  return __popcnt((uint32_t) x) +
         __popcnt((uint32_t)(x >> 32));
}

} // namespace

#elif __cplusplus >= 202002L

#include <bit>

namespace {

/// Ideally we would like to std::popcount instead of the
/// intrinsics above. However std::popcount is from C++20 and
/// not yet widely supported. Also the assembly generated by
/// std::popcount is not as good as __builtin_popcountll on
/// x64 with the Clang compiler. This will likely be fixed in
/// a few years. 
///
inline uint64_t popcnt64(uint64_t x)
{
  return std::popcount(x);
}

} // namespace

#elif defined(DISABLE_POPCNT)

namespace {

/// This uses fewer arithmetic operations than any other known
/// implementation on machines with fast multiplication.
/// It uses 12 arithmetic operations, one of which is a multiply.
/// https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation
///
inline uint64_t popcnt64(uint64_t x)
{
  uint64_t m1 = 0x5555555555555555ull;
  uint64_t m2 = 0x3333333333333333ull;
  uint64_t m4 = 0x0F0F0F0F0F0F0F0Full;
  uint64_t h01 = 0x0101010101010101ull;

  x -= (x >> 1) & m1;
  x = (x & m2) + ((x >> 2) & m2);
  x = (x + (x >> 4)) & m4;

  return (x * h01) >> 56;
}

} // namespace

#endif

#endif // POPCNT_HPP