SeqAn3  3.0.1
The Modern C++ library for sequence analysis.
bit_manipulation.hpp
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------------------------------
2 // Copyright (c) 2006-2020, Knut Reinert & Freie Universität Berlin
3 // Copyright (c) 2016-2020, Knut Reinert & MPI für molekulare Genetik
4 // This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
5 // shipped with this file and also available at: https://github.com/seqan/seqan3/blob/master/LICENSE.md
6 // -----------------------------------------------------------------------------------------------------
7 
14 #pragma once
15 
16 #include <meta/meta.hpp>
17 
18 #include <sdsl/bits.hpp>
19 
20 #include <climits>
21 #include <utility>
22 
23 // Find correct header for byte-order conversion functions.
24 #if __has_include(<endian.h>) // unix GLIBC
25  #include <endian.h>
26 #elif __has_include(<sys/endian.h>) // *BSD
27  #include <sys/endian.h>
28 #endif // __has_include(endian.h)
29 
32 #include <seqan3/std/concepts>
33 
34 namespace seqan3::detail
35 {
36 
42 template <typename type_t>
43 constexpr auto sizeof_bits = min_viable_uint_v<CHAR_BIT * sizeof(type_t)>;
44 
54 constexpr bool is_power_of_two(size_t const n)
55 {
56  return n > 0 && (n & (n-1)) == 0;
57 }
58 
70 constexpr size_t next_power_of_two(size_t n)
71 {
72  if (n == 0)
73  return 1;
74 
75  --n;
76  for (size_t shift = 1; !is_power_of_two(n + 1); shift <<= 1)
77  n |= n >> shift;
78 
79  return n + 1;
80 }
81 
105 template <std::unsigned_integral unsigned_t>
106 constexpr uint8_t popcount(unsigned_t const n) noexcept
107 {
108 #if defined(__GNUC__)
109  if constexpr (sizeof(unsigned_t) == sizeof(unsigned long long))
110  return __builtin_popcountll(n);
111  else if constexpr (sizeof(unsigned_t) == sizeof(unsigned long))
112  return __builtin_popcountl(n);
113  else
114  return __builtin_popcount(n);
115 #else
116  return sdsl::bits::cnt(n);
117 #endif
118 }
119 
145 template <std::unsigned_integral unsigned_t>
146 constexpr uint8_t count_leading_zeros(unsigned_t const n) noexcept
147 {
148  assert(n > 0); // n == 0 might have undefined behaviour
149 #if defined(__GNUC__)
150  if constexpr (sizeof(unsigned_t) == sizeof(unsigned long long))
151  return __builtin_clzll(n);
152  else if constexpr (sizeof(unsigned_t) == sizeof(unsigned long))
153  return __builtin_clzl(n);
154  else
155  return __builtin_clz(n) + sizeof_bits<unsigned_t> - sizeof_bits<unsigned int>;
156 #else
157  return sizeof_bits<unsigned_t> - sdsl::bits::hi(n) - 1;
158 #endif
159 }
160 
186 template <std::unsigned_integral unsigned_t>
187 constexpr uint8_t count_trailing_zeros(unsigned_t const n) noexcept
188 {
189  assert(n > 0); // n == 0 might have undefined behaviour
190 #if defined(__GNUC__)
191  if constexpr (sizeof(unsigned_t) == sizeof(unsigned long long))
192  return __builtin_ctzll(n);
193  else if constexpr (sizeof(unsigned_t) == sizeof(unsigned long))
194  return __builtin_ctzl(n);
195  else
196  return __builtin_ctz(n);
197 #else
198  return sdsl::bits::lo(n);
199 #endif
200 }
201 
227 template <std::unsigned_integral unsigned_t>
228 constexpr uint8_t most_significant_bit_set(unsigned_t const n) noexcept
229 {
230  assert(n > 0); // n == 0 might have undefined behaviour
231 #if defined(__GNUC__)
232  return sizeof_bits<unsigned_t> - count_leading_zeros(n) - 1;
233 #else
234  return sdsl::bits::hi(n);
235 #endif
236 }
237 
250 template <std::integral type>
251 constexpr type to_little_endian(type const in) noexcept
252 {
253  if constexpr (endian::native == endian::little)
254  {
255  return in;
256  }
257  else if constexpr (endian::native == endian::big)
258  {
259  static_assert(sizeof(type) <= 8,
260  "Can only convert the byte encoding for integral numbers with a size of up to 8 bytes.");
261  static_assert(is_power_of_two(sizeof(type)),
262  "Can only convert the byte encoding for integral numbers whose byte size is a power of two.");
263 
264  if constexpr (sizeof(type) == 2)
265  return htole16(in);
266  else if constexpr (sizeof(type) == 4)
267  return htole32(in);
268  else if constexpr (sizeof(type) == 8)
269  return htole64(in);
270  else
271  return in; // single byte.
272  }
273  else
274  {
275  static_assert(endian::native == endian::little || endian::native == endian::big,
276  "Expected a little-endian or big-endian platform.");
277  }
278 }
279 
280 } // namespace seqan3::detail
utility
endian.hpp
Provides seqan3::detail::endian.
concepts
The Concepts library.
int_types.hpp
Provides metaprogramming utilities for integer types.
climits