1 // Copyright 2020 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef LIB_STDCOMPAT_INTERNAL_BIT_H_
6 #define LIB_STDCOMPAT_INTERNAL_BIT_H_
7
8 #include <limits>
9 #include <type_traits>
10
11 #include "../type_traits.h"
12
13 namespace cpp20 {
14 namespace internal {
15
16 // Helper for exclusing specific char types when char is considered unsigned by the compiler.
17 template <typename T>
18 struct is_bit_type
19 : std::integral_constant<
20 bool, std::is_unsigned<T>::value && !std::is_same<bool, T>::value &&
21 !std::is_same<T, char>::value && !std::is_same<T, char16_t>::value &&
22 !std::is_same<T, char32_t>::value && !std::is_same<T, wchar_t>::value> {};
23
24 // Rotation implementation.
25 // Only internal for usage in implementation of certain methods.
26 template <class T>
rotl(T x,int s)27 [[gnu::warn_unused_result]] constexpr std::enable_if_t<is_bit_type<T>::value, T> rotl(
28 T x, int s) noexcept {
29 const auto digits = std::numeric_limits<T>::digits;
30 const auto rotate_by = s % digits;
31
32 if (rotate_by > 0) {
33 return static_cast<T>((x << rotate_by) | (x >> (digits - rotate_by)));
34 }
35
36 if (rotate_by < 0) {
37 return static_cast<T>((x >> -rotate_by) | (x << (digits + rotate_by)));
38 }
39
40 return x;
41 }
42
43 template <class T>
rotr(T x,int s)44 [[gnu::warn_unused_result]] constexpr std::enable_if_t<is_bit_type<T>::value, T> rotr(
45 T x, int s) noexcept {
46 int digits = std::numeric_limits<T>::digits;
47 int rotate_by = s % digits;
48
49 if (rotate_by > 0) {
50 return static_cast<T>((x >> rotate_by) | (x << (digits - rotate_by)));
51 }
52
53 if (rotate_by < 0) {
54 return rotl(x, -rotate_by);
55 }
56
57 return x;
58 }
59
60 // Overloads for intrinsics.
61 // Precondition: |value| != 0.
62 template <typename T>
63 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(T) <= sizeof(unsigned), int>
count_zeros_from_right(T value)64 count_zeros_from_right(T value) noexcept {
65 return __builtin_ctz(static_cast<unsigned>(value));
66 }
67
68 template <typename T>
69 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(unsigned) < sizeof(T) &&
70 sizeof(T) <= sizeof(unsigned long),
71 int>
72 count_zeros_from_right(T value) noexcept {
73 return __builtin_ctzl(static_cast<unsigned long>(value));
74 }
75
76 template <typename T>
77 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(unsigned long) < sizeof(T) &&
78 sizeof(T) <= sizeof(unsigned long long),
79 int>
80 count_zeros_from_right(T value) noexcept {
81 return __builtin_ctzll(static_cast<unsigned long long>(value));
82 }
83
84 template <typename T>
85 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(unsigned long long) < sizeof(T), int>
86 count_zeros_from_right(T value) noexcept {
87 int count = 0;
88 int iter_count = 0;
89 const unsigned long long max_digits = std::numeric_limits<unsigned long long>::digits;
90
91 for (int slot = 0; slot * max_digits < std::numeric_limits<T>::digits; ++slot) {
92 const unsigned long long chunk =
93 static_cast<unsigned long long>(internal::rotr(value, (slot)*max_digits));
94 iter_count = (chunk == 0) ? static_cast<int>(max_digits) : count_zeros_from_right(chunk);
95 count += iter_count;
96 if (iter_count != max_digits) {
97 break;
98 }
99 }
100 return count - static_cast<int>(std::numeric_limits<T>::digits % max_digits);
101 }
102
103 template <typename T, typename U,
104 typename std::enable_if<sizeof(T) >= sizeof(U), bool>::type = true>
105 struct digit_diff
106 : std::integral_constant<T, std::numeric_limits<T>::digits - std::numeric_limits<U>::digits> {};
107
108 template <typename T>
109 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(T) <= sizeof(unsigned), int>
count_zeros_from_left(T value)110 count_zeros_from_left(T value) noexcept {
111 return __builtin_clz(static_cast<unsigned>(value)) -
112 static_cast<int>(digit_diff<unsigned, T>::value);
113 }
114
115 template <typename T>
116 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(unsigned) < sizeof(T) &&
117 sizeof(T) <= sizeof(unsigned long),
118 int>
119 count_zeros_from_left(T value) noexcept {
120 return __builtin_clzl(static_cast<unsigned long>(value)) -
121 static_cast<int>(digit_diff<unsigned long, T>::value);
122 }
123
124 template <typename T>
125 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(unsigned long) < sizeof(T) &&
126 sizeof(T) <= sizeof(unsigned long long),
127 int>
128 count_zeros_from_left(T value) noexcept {
129 return __builtin_clzll(static_cast<unsigned long long>(value)) -
130 static_cast<int>(digit_diff<unsigned long long, T>::value);
131 }
132
133 template <typename T>
134 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(unsigned long long) < sizeof(T), int>
135 count_zeros_from_left(T value) noexcept {
136 int count = 0;
137 int iter_count = 0;
138 const unsigned int max_digits = std::numeric_limits<unsigned long long>::digits;
139
140 for (int slot = 0; slot * max_digits < std::numeric_limits<T>::digits; ++slot) {
141 const unsigned long long chunk =
142 static_cast<unsigned long long>(internal::rotl(value, (slot + 1) * max_digits));
143 iter_count = (chunk == 0) ? static_cast<int>(max_digits) : count_zeros_from_left(chunk);
144 count += iter_count;
145 if (iter_count != max_digits) {
146 break;
147 }
148 }
149 return count - static_cast<int>(std::numeric_limits<T>::digits % max_digits);
150 }
151
152 template <typename T>
popcount(T value)153 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(T) <= sizeof(unsigned), int> popcount(
154 T value) noexcept {
155 return __builtin_popcount(static_cast<unsigned>(value));
156 }
157
158 template <typename T>
159 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(unsigned) < sizeof(T) &&
160 sizeof(T) <= sizeof(unsigned long),
161 int>
162 popcount(T value) noexcept {
163 return __builtin_popcountl(static_cast<unsigned long>(value));
164 }
165
166 template <typename T>
167 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(unsigned long) < sizeof(T) &&
168 sizeof(T) <= sizeof(unsigned long long),
169 int>
170 popcount(T value) noexcept {
171 return __builtin_popcountll(static_cast<unsigned long long>(value));
172 }
173
174 template <typename T>
175 constexpr std::enable_if_t<is_bit_type<T>::value && sizeof(unsigned long long) < sizeof(T), int>
176 popcount(T value) noexcept {
177 int accumulated_count = 0;
178 while (value != 0) {
179 accumulated_count += popcount(static_cast<unsigned long long>(value));
180 value >>= std::numeric_limits<unsigned long long>::digits;
181 }
182 return accumulated_count;
183 }
184
185 template <typename T>
bit_width(T value)186 constexpr std::enable_if_t<is_bit_type<T>::value, int> bit_width(T value) {
187 const int zeros_left = (value == 0) ? std::numeric_limits<T>::digits
188 : static_cast<int>(count_zeros_from_left(value));
189 return std::numeric_limits<T>::digits - zeros_left;
190 }
191
192 template <typename T>
193 constexpr std::enable_if_t<is_bit_type<T>::value && !std::is_same<T, decltype(+T())>::value, T>
bit_ceil(T value)194 bit_ceil(T value) {
195 unsigned ub_offset = std::numeric_limits<unsigned>::digits - std::numeric_limits<T>::digits;
196 return static_cast<T>(1 << (bit_width(static_cast<T>(value - 1)) + ub_offset) >> ub_offset);
197 }
198
199 // When there is no integer promotion.
200 template <typename T>
201 constexpr std::enable_if_t<is_bit_type<T>::value && std::is_same<T, decltype(+T())>::value, T>
bit_ceil(T value)202 bit_ceil(T value) {
203 auto width = bit_width(value - 1);
204 if (!cpp20::is_constant_evaluated() && width == std::numeric_limits<T>::digits) {
205 __builtin_abort();
206 }
207 return static_cast<T>(1) << width;
208 }
209
210 template <typename T>
bit_floor(T value)211 constexpr std::enable_if_t<is_bit_type<T>::value, T> bit_floor(T value) {
212 return value == 0 ? 0 : static_cast<T>(T(1) << (static_cast<T>(bit_width(value)) - T(1)));
213 }
214
215 template <unsigned little, unsigned big>
native_endianess()216 constexpr unsigned native_endianess() {
217 auto curr = __BYTE_ORDER__;
218 if (curr == __ORDER_LITTLE_ENDIAN__) {
219 return little;
220 }
221 if (curr == __ORDER_BIG_ENDIAN__) {
222 return big;
223 }
224 return 0x404;
225 }
226
227 } // namespace internal
228 } // namespace cpp20
229
230 #endif // LIB_STDCOMPAT_INTERNAL_BIT_H_
231