/src/mcl/include/cybozu/bit_operation.hpp
Line | Count | Source (jump to first uncovered line) |
1 | | #pragma once |
2 | | /** |
3 | | @file |
4 | | @brief bit operation |
5 | | */ |
6 | | #include <assert.h> |
7 | | #include <cybozu/inttype.hpp> |
8 | | |
9 | | #if defined(_WIN32) |
10 | | #include <intrin.h> |
11 | | #endif |
12 | | |
13 | | namespace cybozu { |
14 | | |
15 | | namespace bit_op_local { |
16 | | |
17 | | template<bool equalTo8> |
18 | | struct Tag {}; |
19 | | |
20 | | // sizeof(T) < 8 |
21 | | template<> |
22 | | struct Tag<false> { |
23 | | template<class T> |
24 | | static inline int bsf(T x) |
25 | | { |
26 | | #if defined(_MSC_VER) |
27 | | unsigned long out; |
28 | | _BitScanForward(&out, x); |
29 | | #pragma warning(suppress: 6102) |
30 | | return out; |
31 | | #else |
32 | | return __builtin_ctz(x); |
33 | | #endif |
34 | | } |
35 | | template<class T> |
36 | | static inline int bsr(T x) |
37 | 0 | { |
38 | 0 | #if defined(_MSC_VER) |
39 | 0 | unsigned long out; |
40 | 0 | _BitScanReverse(&out, x); |
41 | 0 | #pragma warning(suppress: 6102) |
42 | 0 | return out; |
43 | 0 | #else |
44 | 0 | return __builtin_clz(x) ^ 0x1f; |
45 | 0 | #endif |
46 | 0 | } Unexecuted instantiation: int cybozu::bit_op_local::Tag<false>::bsr<unsigned char>(unsigned char) Unexecuted instantiation: int cybozu::bit_op_local::Tag<false>::bsr<unsigned short>(unsigned short) Unexecuted instantiation: int cybozu::bit_op_local::Tag<false>::bsr<unsigned int>(unsigned int) |
47 | | }; |
48 | | |
49 | | // sizeof(T) == 8 |
50 | | template<> |
51 | | struct Tag<true> { |
52 | | template<class T> |
53 | | static inline int bsf(T x) |
54 | 2.20M | { |
55 | | #if defined(_MSC_VER) && defined(_WIN64) |
56 | | unsigned long out; |
57 | | _BitScanForward64(&out, x); |
58 | | #pragma warning(suppress: 6102) |
59 | | return out; |
60 | | #elif defined(__x86_64__) |
61 | 2.20M | return __builtin_ctzll(x); |
62 | | #else |
63 | | const uint32_t L = uint32_t(x); |
64 | | if (L) return Tag<false>::bsf(L); |
65 | | const uint32_t H = uint32_t(x >> 32); |
66 | | return Tag<false>::bsf(H) + 32; |
67 | | #endif |
68 | 2.20M | } |
69 | | template<class T> |
70 | | static inline int bsr(T x) |
71 | 75.8k | { |
72 | | #if defined(_MSC_VER) && defined(_WIN64) |
73 | | unsigned long out; |
74 | | _BitScanReverse64(&out, x); |
75 | | #pragma warning(suppress: 6102) |
76 | | return out; |
77 | | #elif defined(__x86_64__) |
78 | 75.8k | return __builtin_clzll(x) ^ 0x3f; |
79 | | #else |
80 | | const uint32_t H = uint32_t(x >> 32); |
81 | | if (H) return Tag<false>::bsr(H) + 32; |
82 | | const uint32_t L = uint32_t(x); |
83 | | return Tag<false>::bsr(L); |
84 | | #endif |
85 | 75.8k | } int cybozu::bit_op_local::Tag<true>::bsr<unsigned long>(unsigned long) Line | Count | Source | 71 | 75.8k | { | 72 | | #if defined(_MSC_VER) && defined(_WIN64) | 73 | | unsigned long out; | 74 | | _BitScanReverse64(&out, x); | 75 | | #pragma warning(suppress: 6102) | 76 | | return out; | 77 | | #elif defined(__x86_64__) | 78 | 75.8k | return __builtin_clzll(x) ^ 0x3f; | 79 | | #else | 80 | | const uint32_t H = uint32_t(x >> 32); | 81 | | if (H) return Tag<false>::bsr(H) + 32; | 82 | | const uint32_t L = uint32_t(x); | 83 | | return Tag<false>::bsr(L); | 84 | | #endif | 85 | 75.8k | } |
Unexecuted instantiation: int cybozu::bit_op_local::Tag<true>::bsr<unsigned long long>(unsigned long long) |
86 | | }; |
87 | | |
88 | | } // bit_op_local |
89 | | |
90 | | template<class T> |
91 | | int bsf(T x) |
92 | 2.20M | { |
93 | 2.20M | return bit_op_local::Tag<sizeof(T) == 8>::bsf(x); |
94 | 2.20M | } |
95 | | template<class T> |
96 | | int bsr(T x) |
97 | 75.8k | { |
98 | 75.8k | return bit_op_local::Tag<sizeof(T) == 8>::bsr(x); |
99 | 75.8k | } int cybozu::bsr<unsigned long>(unsigned long) Line | Count | Source | 97 | 75.8k | { | 98 | 75.8k | return bit_op_local::Tag<sizeof(T) == 8>::bsr(x); | 99 | 75.8k | } |
Unexecuted instantiation: int cybozu::bsr<unsigned char>(unsigned char) Unexecuted instantiation: int cybozu::bsr<unsigned short>(unsigned short) Unexecuted instantiation: int cybozu::bsr<unsigned int>(unsigned int) Unexecuted instantiation: int cybozu::bsr<unsigned long long>(unsigned long long) |
100 | | |
101 | | template<class T> |
102 | | uint64_t makeBitMask64(T x) |
103 | | { |
104 | | assert(x < 64); |
105 | | return (uint64_t(1) << x) - 1; |
106 | | } |
107 | | |
108 | | template<class T> |
109 | | uint32_t popcnt(T x); |
110 | | |
111 | | template<> |
112 | | inline uint32_t popcnt<uint32_t>(uint32_t x) |
113 | 0 | { |
114 | 0 | #if defined(_M_ARM64) |
115 | 0 | return static_cast<uint32_t>(_CountOneBits(x)); |
116 | 0 | #elif defined(_MSC_VER) && !defined(__clang__) |
117 | 0 | return static_cast<uint32_t>(_mm_popcnt_u32(x)); |
118 | 0 | #else |
119 | 0 | return static_cast<uint32_t>(__builtin_popcount(x)); |
120 | 0 | #endif |
121 | 0 | } |
122 | | |
123 | | template<> |
124 | | inline uint32_t popcnt<uint64_t>(uint64_t x) |
125 | 0 | { |
126 | 0 | #if defined(_M_ARM64) |
127 | 0 | return static_cast<uint32_t>(_CountOneBits64(x)); |
128 | 0 | #elif defined(__x86_64__) |
129 | 0 | return static_cast<uint32_t>(__builtin_popcountll(x)); |
130 | 0 | #elif defined(_WIN64) |
131 | 0 | return static_cast<uint32_t>(_mm_popcnt_u64(x)); |
132 | 0 | #else |
133 | 0 | return popcnt<uint32_t>(static_cast<uint32_t>(x)) + popcnt<uint32_t>(static_cast<uint32_t>(x >> 32)); |
134 | 0 | #endif |
135 | 0 | } |
136 | | |
137 | | } // cybozu |