• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

PeterCDMcLean / BitLib / 15229950309

24 May 2025 06:42PM UTC coverage: 52.356% (+2.5%) from 49.894%
15229950309

Pull #14

github

web-flow
Merge 6eabe9a4e into d45f839f0
Pull Request #14: Add support for signed word types.

8602 of 16014 branches covered (53.72%)

Branch coverage included in aggregate %.

212 of 260 new or added lines in 12 files covered. (81.54%)

4 existing lines in 1 file now uncovered.

5319 of 10575 relevant lines covered (50.3%)

5575305.01 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

60.21
/include/bitlib/bit-iterator/bit_details.hpp
1
// ============================== BIT DETAILS =============================== //
2
// Project:         The C++ Bit Library
3
// Name:            bit_details.hpp
4
// Description:     Provides common implementation details and helper classes
5
// Creator:         Vincent Reverdy
6
// Contributor(s):  Vincent Reverdy [2015-2017]
7
//                  Bryce Kille [2019]
8
// License:         BSD 3-Clause License
9
// ========================================================================== //
10
#ifndef _BIT_DETAILS_HPP_INCLUDED
11
#define _BIT_DETAILS_HPP_INCLUDED
12
// ========================================================================== //
13

14

15

16
// ================================ PREAMBLE ================================ //
17
// C++ standard library
18
#include <algorithm>
19
#include <cassert>
20
#include <concepts>
21
#include <cstddef>
22
#include <cstdint>
23
#include <iterator>
24
#include <limits>
25
#include <ranges>
26
#include <stdexcept>
27
#include <tuple>
28
#include <type_traits>
29
#include <utility>
30

31
#include "bitlib/bit-containers/bit_bitsof.hpp"
32
#include "bitlib/bit_concepts.hpp"
33

34
// Project sources
35
// Third-party libraries
36
// Miscellaneous
37
namespace bit {
38
class bit_value;
39
template <class WordType>
40
class bit_reference;
41
template <class Iterator> class bit_iterator;
42
template <class WordType>
43
using bit_pointer = bit_iterator<WordType*>;
44

45
// ========================================================================== //
46

47
/* ***************************** BINARY DIGITS ****************************** */
48
// Binary digits structure definition
49
// Implementation template: only instantiates static_asserts for non-byte types.
50
template <typename T, bool = std::is_same<T, std::byte>::value>
51
struct binary_digits_impl : std::integral_constant<std::size_t, std::numeric_limits<std::make_unsigned_t<T>>::digits> {
52
  static_assert(std::is_integral<T>::value, "Type must be integral");
53
  //static_assert(std::is_unsigned<T>::value, "Type must be unsigned");
54
  static_assert(!std::is_same<T, bool>::value, "Type must not be bool");
55
  static_assert(!std::is_same<T, char>::value, "Type must not be char");
56
};
57

58
// Specialization for std::byte.
59
template <>
60
struct binary_digits_impl<std::byte, true> : std::integral_constant<std::size_t, std::numeric_limits<unsigned char>::digits> {};
61

62
// Public interface that removes cv-qualifiers.
63
template <typename UIntType>
64
struct binary_digits : binary_digits_impl<std::remove_cv_t<UIntType>> {};
65

66
// Binary digits value
67
template <class T>
68
constexpr std::size_t binary_digits_v = binary_digits<T>::value;
69
/* ************************************************************************** */
70

71
#if 0
72
template <typename T>
73
using smallest_integral = std::conditional_t<
74
    (sizeof(T) <= sizeof(std::uint8_t)),
75
    std::uint8_t,
76
    std::conditional_t<
77
        (sizeof(T) <= sizeof(std::uint16_t)),
78
        std::uint16_t,
79
        std::conditional_t<
80
            (sizeof(T) <= sizeof(std::uint32_t)),
81
            std::uint32_t,
82
            std::conditional_t<
83
                (sizeof(T) <= sizeof(std::uint64_t)),
84
                std::uint64_t,
85
                T>>>>;
86
#endif
87

88
/* *************** IMPLEMENTATION DETAILS: CV ITERATOR TRAITS *************** */
89
// Cv iterator traits structure definition
90
template <class Iterator>
91
struct _cv_iterator_traits
92
{
93
    // Assertions
94
    private:
95
    using _traits_t = std::iterator_traits<Iterator>;
96
    using _difference_t = typename _traits_t::difference_type;
97
    using _value_t = typename _traits_t::value_type;
98
    using _pointer_t = typename _traits_t::pointer;
99
    using _reference_t = typename _traits_t::reference;
100
    using _category_t =  typename _traits_t::iterator_category;
101
    using _no_pointer_t = typename std::remove_pointer<_pointer_t>::type;
102
    using _no_reference_t = typename std::remove_reference<_reference_t>::type;
103
    using _raw_value_t = typename std::remove_cv<_value_t>::type;
104
    using _raw_pointer_t = typename std::remove_cv<_no_pointer_t>::type;
105
    using _raw_reference_t = typename std::remove_cv<_no_reference_t>::type;
106
    using _cv_value_t = _no_reference_t;
107
    static_assert(std::is_same<_raw_pointer_t, _raw_value_t>::value, "");
108
    static_assert(std::is_same<_raw_reference_t, _raw_value_t>::value, "");
109

110
    // Types
111
    public:
112
    using difference_type = _difference_t;
113
    using value_type = _cv_value_t;
114
    using pointer = _pointer_t;
115
    using reference = _reference_t;
116
    using iterator_category = _category_t;
117
};
118
/* ************************************************************************** */
119

120

121

122
/* *********** IMPLEMENTATION DETAILS: NARROWEST AND WIDEST TYPES *********** */
123
// Narrowest type structure declaration
124
template <class... T>
125
struct _narrowest_type;
126

127
// Narrowest type structure specialization: selects the only passed type
128
template <class T>
129
struct _narrowest_type<T>
130
: std::common_type<T>
131
{
132
    static_assert(binary_digits<T>::value, "");
133
};
134

135
// Narrowest type structure specialization: selects the type with less bits
136
template <class T, class U>
137
struct _narrowest_type<T, U>
138
: _narrowest_type<
139
    typename std::conditional<
140
        (binary_digits<T>::value < binary_digits<U>::value),
141
        T,
142
        typename std::conditional<
143
            (binary_digits<T>::value > binary_digits<U>::value),
144
            U,
145
            typename std::common_type<T, U>::type
146
        >::type
147
    >::type
148
>
149
{
150
};
151

152
// Narrowest type structure specialization: recursively selects the right type
153
template <class T, class... U>
154
struct _narrowest_type<T, U...>
155
: _narrowest_type<T, typename _narrowest_type<U...>::type>
156
{
157
};
158

159
// Narrowest type alias
160
template <class... T>
161
using _narrowest_type_t = typename _narrowest_type<T...>::type;
162

163
// Widest type structure declaration
164
template <class... X>
165
struct _widest_type;
166

167
// Widest type structure specialization: selects the only passed type
168
template <class T>
169
struct _widest_type<T>
170
: std::common_type<T>
171
{
172
    static_assert(binary_digits<T>::value, "");
173
};
174

175
// Widest type structure specialization: selects the type with more bits
176
template <class T, class U>
177
struct _widest_type<T, U>
178
: _widest_type<
179
    typename std::conditional<
180
        (binary_digits<T>::value > binary_digits<U>::value),
181
        T,
182
        typename std::conditional<
183
            (binary_digits<T>::value < binary_digits<U>::value),
184
            U,
185
            typename std::common_type<T, U>::type
186
        >::type
187
    >::type
188
>
189
{
190
};
191

192
// Widest type structure specialization: recursively selects the right type
193
template <class T, class... X>
194
struct _widest_type<T, X...>
195
: _widest_type<T, typename _widest_type<X...>::type>
196
{
197
};
198

199
// Widest type alias
200
template <class... T>
201
using _widest_type_t = typename _widest_type<T...>::type;
202
/* ************************************************************************** */
203

204

205

206
/* ************ IMPLEMENTATION DETAILS: NARROWER AND WIDER TYPES ************ */
207
// Narrower type structure definition
208
template <class T, int I = 0>
209
struct _narrower_type
210
{
211
    using tuple = std::tuple<
212
        unsigned long long int,
213
        unsigned long int,
214
        unsigned int,
215
        unsigned short int,
216
        unsigned char
217
    >;
218
    using lhs_bits = binary_digits<T>;
219
    using rhs_bits = binary_digits<typename std::tuple_element<I, tuple>::type>;
220
    using type = typename std::conditional<
221
        (lhs_bits::value > rhs_bits::value),
222
        typename std::tuple_element<I, tuple>::type,
223
        typename std::conditional<
224
            (I + 1 < std::tuple_size<tuple>::value),
225
            typename _narrower_type<
226
                T,
227
                (I + 1 < std::tuple_size<tuple>::value ? I + 1 : -1)
228
            >::type,
229
            typename std::tuple_element<I, tuple>::type
230
        >::type
231
    >::type;
232
};
233

234
// Narrower type structure specialization: not found
235
template <class T>
236
struct _narrower_type<T, -1>
237
{
238
    using type = T;
239
};
240

241
// Narrower type alias
242
template <class T>
243
using _narrower_type_t = typename _narrower_type<T>::type;
244

245
// Wider type structure definition
246
template <class T, int I = 0>
247
struct _wider_type
248
{
249
    using tuple = std::tuple<
250
        unsigned char,
251
        unsigned short int,
252
        unsigned int,
253
        unsigned long int,
254
        unsigned long long int
255
    >;
256
    using lhs_bits = binary_digits<T>;
257
    using rhs_bits = binary_digits<typename std::tuple_element<I, tuple>::type>;
258
    using type = typename std::conditional<
259
        (lhs_bits::value < rhs_bits::value),
260
        typename std::tuple_element<I, tuple>::type,
261
        typename std::conditional<
262
            (I + 1 < std::tuple_size<tuple>::value),
263
            typename _narrower_type<
264
                T,
265
                (I + 1 < std::tuple_size<tuple>::value ? I + 1 : -1)
266
            >::type,
267
            typename std::tuple_element<I, tuple>::type
268
        >::type
269
    >::type;
270
};
271

272
// Wider type structure specialization: not found
273
template <class T>
274
struct _wider_type<T, -1>
275
{
276
    using type = T;
277
};
278

279
// Wider type alias
280
template <class T>
281
using _wider_type_t = typename _wider_type<T>::type;
282
/* ************************************************************************** */
283

284

285

286
/* ******************* IMPLEMENTATION DETAILS: UTILITIES ******************** */
287
// Assertions
288
template <class Iterator>
289
constexpr bool _assert_range_viability(Iterator first, Iterator last);
290
/* ************************************************************************** */
291

292

293

294
/* ****************** IMPLEMENTATION DETAILS: INSTRUCTIONS ****************** */
295
// Population count
296
template <class T, class = decltype(__builtin_popcountll(T()))>
297
constexpr T _popcnt(T src) noexcept;
298
template <class T, class... X>
299
constexpr T _popcnt(T src, X...) noexcept;
300

301
// Leading zeros count
302
template <class T, class = decltype(__builtin_clzll(T()))>
303
constexpr T _lzcnt(T src) noexcept;
304
template <class T, class... X>
305
constexpr T _lzcnt(T src, X...) noexcept;
306

307
// Trailing zeros count
308
template <class T, class = decltype(__builtin_ctzll(T()))>
309
constexpr T _tzcnt(T src) noexcept;
310
template <class T, class... X>
311
constexpr T _tzcnt(T src, X...) noexcept;
312

313
// Bit field extraction
314
template <class T, class = decltype(__builtin_ia32_bextr_u64(T(), T(), T()))>
315
constexpr T _bextr(T src, T start, T len) noexcept;
316
template <class T, class... X>
317
constexpr T _bextr(T src, T start, T len, X...) noexcept;
318

319
// Parallel bits deposit
320
template <class T, class = decltype(_pdep_u64(T()))>
321
constexpr T _pdep(T src, T msk) noexcept;
322
template <class T, class... X>
323
constexpr T _pdep(T src, T msk, X...) noexcept;
324

325
// Parallel bits extract
326
template <class T, class = decltype(_pext_u64(T()))>
327
constexpr T _pext(T src, T msk) noexcept;
328
template <class T, class... X>
329
constexpr T _pext(T src, T msk, X...) noexcept;
330

331
// Byte swap
332
template <class T, class T128 = decltype(__uint128_t(__builtin_bswap64(T())))>
333
constexpr T _byteswap(T src) noexcept;
334
template <class T, class... X>
335
constexpr T _byteswap(T src, X...) noexcept;
336

337
// Bit swap
338
template <class T>
339
constexpr T _bitswap(T src) noexcept;
340
template <class T, std::size_t N>
341
constexpr T _bitswap(T src) noexcept;
342
template <class T, std::size_t N>
343
constexpr T _bitswap() noexcept;
344

345
// Bit blend
346
template <class T>
347
constexpr T _bitblend(T src0, T src1, T msk) noexcept;
348
template <class T>
349
constexpr T _bitblend(T src0, T src1, T start, T len) noexcept;
350

351
// Bit exchange
352
template <class T>
353
constexpr void _bitexch(T& src0, T& src1, T msk) noexcept;
354
template <class T, class S>
355
constexpr void _bitexch(T& src0, T& src1, S start, S len) noexcept;
356
template <class T, class S>
357
constexpr void _bitexch(T& src0, T& src1, S start0, S start1, S len) noexcept;
358

359
// Bit compare
360
template <class T>
361
constexpr T _bitcmp(T src0, T src1, T start0, T start1, T len) noexcept;
362

363
// Double precision shift left
364
template <class T>
365
constexpr T _shld(T dst, T src, T cnt) noexcept;
366

367
// Double precision shift right
368
template <class T>
369
constexpr T _shrd(T dst, T src, T cnt) noexcept;
370

371
// Add carry
372
template <class... T>
373
using _supports_adc = decltype(__builtin_ia32_addcarryx_u64(T()...));
374
template <class C, class T, class = _supports_adc<C, T, T, std::nullptr_t>>
375
constexpr C _addcarry(C carry, T src0, T src1, T* dst) noexcept;
376
template <class C, class T, class... X>
377
constexpr C _addcarry(C carry, T src0, T src1, T* dst, X...) noexcept;
378

379
// Sub borrow
380
template <class... T>
381
using _supports_sbb = decltype(__builtin_ia32_sbb_u64(T()...));
382
template <class... T>
383
using _supports_sbb_alt = decltype(__builtin_ia32_subborrow_u64(T()...));
384
template <class B, class T, class = _supports_sbb<B, T, T, std::nullptr_t>>
385
constexpr B _subborrow(B borrow, T src0, T src1, T* dst) noexcept;
386
template <class B, class T, class = _supports_sbb_alt<B, T, T, std::nullptr_t>>
387
constexpr B _subborrow(const B& borrow, T src0, T src1, T* dst) noexcept;
388
template <class B, class T, class... X>
389
constexpr B _subborrow(B borrow, T src0, T src1, T* dst, X...) noexcept;
390

391
// Multiword multiply
392
template <class T, class T128 = decltype(__uint128_t(T()))>
393
constexpr T _mulx(T src0, T src1, T* hi) noexcept;
394
template <class T, class... X>
395
constexpr T _mulx(T src0, T src1, T* hi, X...) noexcept;
396
/* ************************************************************************** */
397

398
/*
399
Logical shift right
400
*/
401
template <std::integral T, typename size_type = size_t>
402
constexpr T lsr(const T& val, const size_type shift) {
85,662,609✔
403
  return static_cast<T>(static_cast<std::make_unsigned_t<T>>(val) >> shift);
85,662,609✔
404
}
85,662,609✔
405

406
template <std::integral T, typename size_type = size_t>
407
constexpr T _mask(const size_type len) {
21,404,909✔
408
  constexpr std::make_unsigned_t<T> one = std::make_unsigned_t<T>(1);
21,404,909✔
409
  // The digits_mask is solely here to prevent Undefined Sanitizer
410
  // complaining about shift of len >= digits
411
  // Note: on -O1 the (len & digits_mask) is optimized to simply (len)
412
  constexpr std::make_unsigned_t<T> digits_mask = bitsof<T>() - one;
21,404,909✔
413
  return static_cast<T>((one << (len & digits_mask)) * (len < bitsof<T>()) - one);
21,404,909✔
414
}
21,404,909✔
415

416
// ------------- IMPLEMENTATION DETAILS: UTILITIES: ASSERTIONS -------------- //
417
// If the range allows multipass iteration, checks if last - first >= 0
418
template <class Iterator>
419
constexpr bool _assert_range_viability(Iterator first, Iterator last) {
473,587✔
420
  using traits_t = std::iterator_traits<Iterator>;
473,587✔
421
  using category_t = typename traits_t::iterator_category;
473,587✔
422
  using multi_t = std::forward_iterator_tag;
473,587✔
423
  constexpr bool is_multipass = std::is_base_of<multi_t, category_t>::value;
473,587✔
424
  const bool is_viable = !is_multipass || std::distance(first, last) >= 0;
473,587!
425
  assert(is_viable);
473,587!
426
  return is_viable;
473,587✔
427
}
473,587✔
428
// -------------------------------------------------------------------------- //
429

430
// --------- IMPLEMENTATION DETAILS: INSTRUCTIONS: POPULATION COUNT --------- //
431
// Counts the number of bits set to 1 with compiler intrinsics
432
template <class T, class>
433
constexpr T _popcnt(T src) noexcept {
52,544✔
434
  static_assert(binary_digits<T>::value, "");
52,544✔
435
  constexpr T digits = binary_digits<T>::value;
52,544✔
436
  if (digits <= std::numeric_limits<unsigned int>::digits) {
52,544✔
437
    src = __builtin_popcount(static_cast<std::make_unsigned_t<T>>(src));
24,128✔
438
  } else if (digits <= std::numeric_limits<unsigned long int>::digits) {
28,416✔
439
    src = __builtin_popcountl(static_cast<std::make_unsigned_t<T>>(src));
28,416✔
440
  } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
28,416✔
NEW
441
    src = __builtin_popcountll(static_cast<std::make_unsigned_t<T>>(src));
×
NEW
442
  } else {
×
NEW
443
    src = _popcnt(src, std::ignore);
×
NEW
444
  }
×
445
  return src;
52,544✔
446
}
52,544✔
447

448
// Counts the number of bits set to 1 without compiler intrinsics
449
template <class T, class... X>
NEW
450
constexpr T _popcnt(T src, X...) noexcept {
×
NEW
451
  static_assert(binary_digits<T>::value, "");
×
NEW
452
  T dst = T();
×
NEW
453
  for (dst = T(); src; src = lsr(src, 1)) {
×
NEW
454
    dst += src & 1;
×
NEW
455
  }
×
NEW
456
  return dst;
×
UNCOV
457
}
×
458
// -------------------------------------------------------------------------- //
459

460
// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: LEADING ZEROS COUNT -------- //
461
// Counts the number of leading zeros with compiler intrinsics
462
template <class T, class>
463
constexpr T _lzcnt(T src) noexcept {
464
  static_assert(binary_digits<T>::value, "");
465
  constexpr T digits = binary_digits<T>::value;
466
  T dst = T();
467
  if (digits < std::numeric_limits<unsigned int>::digits) {
468
    dst = src ? __builtin_clz(src) - (std::numeric_limits<unsigned int>::digits - digits)
469
              : digits;
470
  } else if (digits == std::numeric_limits<unsigned int>::digits) {
471
    dst = src ? __builtin_clz(src) : digits;
472
  } else if (digits < std::numeric_limits<unsigned long int>::digits) {
473
    dst = src ? __builtin_clzl(src) - (std::numeric_limits<unsigned long int>::digits - digits)
474
              : digits;
475
  } else if (digits == std::numeric_limits<unsigned long int>::digits) {
476
    dst = src ? __builtin_clzl(src) : digits;
477
  } else if (digits < std::numeric_limits<unsigned long long int>::digits) {
478
    dst = src ? __builtin_clzll(src) - (std::numeric_limits<unsigned long long int>::digits - digits)
479
              : digits;
480
  } else if (digits == std::numeric_limits<unsigned long long int>::digits) {
481
    dst = src ? __builtin_clzll(src) : digits;
482
  } else {
483
    dst = _lzcnt(src, std::ignore);
484
  }
485
  return dst;
486
}
487

488
// Counts the number of leading zeros without compiler intrinsics
489
template <class T, class... X>
490
constexpr T _lzcnt(T src, X...) noexcept {
491
  static_assert(binary_digits<T>::value, "");
492
  constexpr T digits = binary_digits<T>::value;
493
  T dst = src != T();
494
  while ((src = lsr(src, 1))) {
495
    ++dst;
496
  }
497
  return digits - dst;
498
}
499
// -------------------------------------------------------------------------- //
500

501
// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: TRAILING ZEROS COUNT ------- //
502
// Counts the number of trailing zeros with compiler intrinsics
503
template <class T, class>
504
constexpr T _tzcnt(T src) noexcept {
33,230✔
505
  static_assert(binary_digits<T>::value, "");
33,230✔
506
  constexpr T digits = binary_digits<T>::value;
33,230✔
507
  T dst = T();
33,230✔
508
  if (digits <= std::numeric_limits<unsigned int>::digits) {
33,230✔
509
    dst = src ? __builtin_ctz(src) : digits;
16,206!
510
  } else if (digits <= std::numeric_limits<unsigned long int>::digits) {
17,024✔
511
    dst = src ? __builtin_ctzl(src) : digits;
17,024!
512
  } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
17,024✔
NEW
513
    dst = src ? __builtin_ctzll(src) : digits;
×
NEW
514
  } else {
×
NEW
515
    dst = _tzcnt(src, std::ignore);
×
NEW
516
  }
×
517
  return dst;
33,230✔
518
}
33,230✔
519

520
// Counts the number of trailing zeros without compiler intrinsics
521
template <class T, class... X>
NEW
522
constexpr T _tzcnt(T src, X...) noexcept {
×
NEW
523
  static_assert(binary_digits<T>::value, "");
×
NEW
524
  constexpr T digits = binary_digits<T>::value;
×
NEW
525
  T dst = digits;
×
NEW
526
  if (src) {
×
NEW
527
    src = lsr((src ^ (src - 1)), 1);
×
NEW
528
    for (dst = T(); src; dst++) {
×
NEW
529
      src = lsr(src, 1);
×
530
    }
×
NEW
531
  }
×
NEW
532
  return dst;
×
UNCOV
533
}
×
534
// -------------------------------------------------------------------------- //
535

536
// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: BIT FIELD EXTRACTION ------- //
537
// Extacts to lsbs a field of contiguous bits with compiler intrinsics
538
template <class T, class>
539
constexpr T _bextr(T src, T start, T len) noexcept {
540
  static_assert(binary_digits<T>::value, "");
541
  constexpr T digits = binary_digits<T>::value;
542
  T dst = T();
543
  if (digits <= std::numeric_limits<unsigned int>::digits) {
544
    dst = __builtin_ia32_bextr_u32(src, start, len);
545
  } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
546
    dst = __builtin_ia32_bextr_u64(src, start, len);
547
  } else {
548
    dst = _bextr(src, start, len, std::ignore);
549
  }
550
  return dst;
551
}
552

553
// Extacts to lsbs a field of contiguous bits without compiler intrinsics
554
template <class T, class... X>
555
constexpr T _bextr(T src, T start, T len, X...) noexcept {
7,616✔
556
  static_assert(binary_digits<T>::value, "");
7,616✔
557
  constexpr T digits = binary_digits<T>::value;
7,616✔
558
  constexpr T one = 1;
7,616✔
559
  const T msk = (one << len) * (len < digits) - one;
7,616✔
560
  return (lsr(src, start)) & msk * (start < digits);
7,616✔
561
}
7,616✔
562
// -------------------------------------------------------------------------- //
563

564
// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: PARALLEL BIT DEPOSIT ------- //
565
// Deposits bits according to a mask with compiler instrinsics
566
template <class T, class>
567
constexpr T _pdep(T src, T msk) noexcept {
568
  static_assert(binary_digits<T>::value, "");
569
  constexpr T digits = binary_digits<T>::value;
570
  T dst = T();
571
  if (digits <= std::numeric_limits<unsigned int>::digits) {
572
    dst = _pdep_u32(src, msk);
573
  } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
574
    dst = _pdep_u64(src, msk);
575
  } else {
576
    dst = _pdep(src, msk, std::ignore);
577
  }
578
  return dst;
579
}
580

581
// Deposits bits according to a mask without compiler instrinsics
582
template <class T, class... X>
583
constexpr T _pdep(T src, T msk, X...) noexcept {
584
  static_assert(binary_digits<T>::value, "");
585
  constexpr T digits = binary_digits<T>::value;
586
  T dst = T();
587
  T cnt = T();
588
  while (msk) {
589
    dst = lsr(dst, 1);
590
    if (msk & 1) {
591
      dst |= src << (digits - 1);
592
      src = lsr(src, 1);
593
    }
594
    msk = lsr(msk, 1);
595
    ++cnt;
596
  }
597
  dst = lsr(dst, (digits - cnt) * (cnt > 0));
598
  return dst;
599
}
600
// -------------------------------------------------------------------------- //
601

602
// ------- IMPLEMENTATION DETAILS: INSTRUCTIONS: PARALLEL BIT EXTRACT ------- //
603
// Extracts bits according to a mask with compiler instrinsics
604
template <class T, class>
605
constexpr T _pext(T src, T msk) noexcept {
606
  static_assert(binary_digits<T>::value, "");
607
  constexpr T digits = binary_digits<T>::value;
608
  T dst = T();
609
  if (digits <= std::numeric_limits<unsigned int>::digits) {
610
    dst = _pext_u32(src, msk);
611
  } else if (digits <= std::numeric_limits<unsigned long long int>::digits) {
612
    dst = _pext_u64(src, msk);
613
  } else {
614
    dst = _pext(src, msk, std::ignore);
615
  }
616
  return dst;
617
}
618

619
// Extracts bits according to a mask without compiler instrinsics
620
template <class T, class... X>
621
constexpr T _pext(T src, T msk, X...) noexcept {
622
  static_assert(binary_digits<T>::value, "");
623
  constexpr T digits = binary_digits<T>::value;
624
  T dst = T();
625
  T cnt = T();
626
  while (msk) {
627
    if (msk & 1) {
628
      dst = lsr(dst, 1);
629
      dst |= src << (digits - 1);
630
      ++cnt;
631
    }
632
    src = lsr(src, 1);
633
    msk = lsr(msk, 1);
634
  }
635
  dst = lsr(dst, (digits - cnt) * (cnt > 0));
636
  return dst;
637
}
638
// -------------------------------------------------------------------------- //
639

640
// ------------ IMPLEMENTATION DETAILS: INSTRUCTIONS: BYTE SWAP ------------- //
641
// Reverses the order of the underlying bytes with compiler intrinsics
642
template <class T, class T128>
643
constexpr T _byteswap(T src) noexcept {
644
  static_assert(binary_digits<T>::value, "");
645
  using byte_t = unsigned char;
646
  constexpr T digits = sizeof(T) * std::numeric_limits<byte_t>::digits;
647
  std::uint64_t tmp64 = 0;
648
  std::uint64_t* ptr64 = nullptr;
649
  if (std::is_same<T, T128>::value) {
650
    ptr64 = reinterpret_cast<std::uint64_t*>(&src);
651
    tmp64 = __builtin_bswap64(*ptr64);
652
    *ptr64 = __builtin_bswap64(*(ptr64 + 1));
653
    *(ptr64 + 1) = tmp64;
654
  } else if (digits == std::numeric_limits<std::uint16_t>::digits) {
655
    src = __builtin_bswap16(src);
656
  } else if (digits == std::numeric_limits<std::uint32_t>::digits) {
657
    src = __builtin_bswap32(src);
658
  } else if (digits == std::numeric_limits<std::uint64_t>::digits) {
659
    src = __builtin_bswap64(src);
660
  } else if (digits > std::numeric_limits<byte_t>::digits) {
661
    src = _byteswap(src, std::ignore);
662
  }
663
  return src;
664
}
665

666
// Reverses the order of the underlying bytes without compiler intrinsics
667
template <class T, class... X>
668
constexpr T _byteswap(T src, X...) noexcept {
669
  static_assert(binary_digits<T>::value, "");
670
  using byte_t = unsigned char;
671
  constexpr T half = sizeof(T) / 2;
672
  constexpr T end = sizeof(T) - 1;
673
  unsigned char* bytes = reinterpret_cast<byte_t*>(&src);
674
  unsigned char byte = 0;
675
  for (T i = T(); i < half; ++i) {
676
    byte = bytes[i];
677
    bytes[i] = bytes[end - i];
678
    bytes[end - i] = byte;
679
  }
680
  return src;
681
}
682
// -------------------------------------------------------------------------- //
683

684
// ------------- IMPLEMENTATION DETAILS: INSTRUCTIONS: BIT SWAP ------------- //
685
// Reverses the order of the bits with or without of compiler intrinsics
686
template <class T>
687
constexpr T _bitswap(T src) noexcept {
10,521,728✔
688
  static_assert(binary_digits<T>::value, "");
10,521,728✔
689
  using byte_t = unsigned char;
10,521,728✔
690
  constexpr auto ignore = nullptr;
10,521,728✔
691
  constexpr T digits = binary_digits<T>::value;
10,521,728✔
692
  constexpr unsigned long long int first = 0x80200802ULL;
10,521,728✔
693
  constexpr unsigned long long int second = 0x0884422110ULL;
10,521,728✔
694
  constexpr unsigned long long int third = 0x0101010101ULL;
10,521,728✔
695
  constexpr unsigned long long int fourth = 32;
10,521,728✔
696
  constexpr bool is_size1 = sizeof(T) == 1;
10,521,728✔
697
  constexpr bool is_byte = digits == std::numeric_limits<byte_t>::digits;
10,521,728✔
698
  constexpr bool is_octet = std::numeric_limits<byte_t>::digits == 8;
10,521,728✔
699
  constexpr bool is_pow2 = _popcnt(digits, ignore) == 1;
10,521,728✔
700
  T dst = src;
10,521,728✔
701
  T i = digits - 1;
10,521,728✔
702
  if (is_size1 && is_byte && is_octet) {
10,521,728✔
703
    dst = static_cast<T>(lsr(((static_cast<std::make_unsigned_t<T>>(src) * first) & second) * third, fourth));
2,622,432✔
704
  } else if (is_pow2) {
7,899,296✔
705
    dst = _bitswap<T, digits>(src);
7,899,296✔
706
  } else {
7,899,296✔
NEW
707
    for (src = lsr(src, 1); src; src = lsr(src, 1)) {
×
NEW
708
      dst <<= 1;
×
NEW
709
      dst |= src & 1;
×
NEW
710
      i--;
×
UNCOV
711
    }
×
NEW
712
    dst <<= i;
×
NEW
713
  }
×
714
  return dst;
10,521,728✔
715
}
10,521,728✔
716

717
// Reverses the order of the bits: recursive metafunction
718
template <class T, std::size_t N>
719
constexpr T _bitswap(T src) noexcept {
39,511,840✔
720
  static_assert(binary_digits<T>::value, "");
39,511,840✔
721
  constexpr T cnt = N >> 1;
39,511,840✔
722
  constexpr T msk = _bitswap<T, cnt>();
39,511,840✔
723
  src = ((lsr(src, cnt)) & msk) | ((src << cnt) & ~msk);
39,511,840✔
724
  return cnt > 1 ? _bitswap<T, cnt>(src) : src;
39,511,840✔
725
}
39,511,840✔
726

727
// Reverses the order of the bits: mask for the recursive metafunction
728
template <class T, std::size_t N>
NEW
729
constexpr T _bitswap() noexcept {
×
NEW
730
  static_assert(binary_digits<T>::value, "");
×
NEW
731
  constexpr T digits = binary_digits<T>::value;
×
NEW
732
  T cnt = digits;
×
NEW
733
  T msk = ~T();
×
NEW
734
  while (cnt != N) {
×
NEW
735
    cnt = lsr(cnt, 1);
×
NEW
736
    msk ^= (msk << cnt);
×
NEW
737
  }
×
NEW
738
  return msk;
×
UNCOV
739
}
×
740
// -------------------------------------------------------------------------- //
741

742
// ------------ IMPLEMENTATION DETAILS: INSTRUCTIONS: BIT BLEND ------------- //
743
// Replaces bits of src0 by the ones of src1 where the mask is true
744
template <class T>
745
constexpr T _bitblend(T src0, T src1, T msk) noexcept {
5,016✔
746
  static_assert(binary_digits<T>::value, "");
5,016✔
747
  return src0 ^ ((src0 ^ src1) & msk);
5,016✔
748
}
5,016✔
749

750
// Replaces len bits of src0 by the ones of src1 starting at start
751
template <class T>
752
constexpr T _bitblend(T src0, T src1, T start, T len) noexcept {
796,999✔
753
  static_assert(binary_digits<T>::value, "");
796,999✔
754
  constexpr T digits = binary_digits<T>::value;
796,999✔
755
  const T msk = _mask<T>(len) << start;
796,999✔
756
  return src0 ^ ((src0 ^ src1) & msk * (start < digits));
796,999✔
757
}
796,999✔
758
// -------------------------------------------------------------------------- //
759

760
// ---------- IMPLEMENTATION DETAILS: INSTRUCTIONS: BIT EXCHANGE ------------ //
761
// Exchanges/swaps bits of src0 by the ones of src1 where the mask is true
762
template <class T>
763
constexpr void _bitexch(T& src0, T& src1, T msk) noexcept {
764
  src0 = src0 ^ static_cast<T>(src1 & msk);
765
  src1 = src1 ^ static_cast<T>(src0 & msk);
766
  src0 = src0 ^ static_cast<T>(src1 & msk);
767
  return;
768
}
769

770
// Replaces len bits of src0 by the ones of src1 starting at start
771
template <class T, class S>
772
constexpr void _bitexch(T& src0, T& src1, S start, S len) noexcept {
2,371✔
773
  static_assert(binary_digits<T>::value, "");
2,371✔
774
  constexpr auto digits = binary_digits<T>::value;
2,371✔
775
  const T msk = (len < digits)
2,371!
776
                    ? _mask<T>(len) << start
2,371✔
777
                    : -1;  // TODO: What if start > 0 here?
2,371✔
778
  src0 = src0 ^ static_cast<T>(src1 & msk);
2,371✔
779
  src1 = src1 ^ static_cast<T>(src0 & msk);
2,371✔
780
  src0 = src0 ^ static_cast<T>(src1 & msk);
2,371✔
781
  return;
2,371✔
782
}
2,371✔
783

784
// Replaces len bits of src0 by the ones of src1 starting at start0
785
// in src0 and start1 in src1.
786
// len <= digits-max(start0, start1)
787
// clang-format off
788
template <class T, class S>
789
constexpr void _bitexch(T& src0, T& src1, S start0, S start1, S len) noexcept
790
{
20,594,586✔
791
    static_assert(binary_digits<T>::value, "");
20,594,586✔
792
    constexpr auto digits = binary_digits<T>::value;
20,594,586✔
793
    const T msk = _mask<T>(len);
20,594,586✔
794
    if (start0 >= start1) {
20,594,586✔
795
        src0 = src0 ^ (
10,298,778✔
796
                static_cast<T>(src1 << (start0 - start1))
10,298,778✔
797
                &
10,298,778✔
798
                static_cast<T>(msk << start0)
10,298,778✔
799
        );
10,298,778✔
800
        src1 = src1 ^ (
10,298,778✔
801
                static_cast<T>(lsr(src0, (start0 - start1)))
10,298,778✔
802
                &
10,298,778✔
803
                static_cast<T>(msk << start1)
10,298,778✔
804
        );
10,298,778✔
805
        src0 = src0 ^ (
10,298,778✔
806
                static_cast<T>(src1 << (start0 - start1))
10,298,778✔
807
                &
10,298,778✔
808
                static_cast<T>(msk << start0)
10,298,778✔
809
        );
10,298,778✔
810
    } else {
10,298,778✔
811
        src0 = src0 ^ (
10,295,808✔
812
                static_cast<T>(lsr(src1, (start1 - start0)))
10,295,808✔
813
                &
10,295,808✔
814
                static_cast<T>(msk << start0)
10,295,808✔
815
        );
10,295,808✔
816
        src1 = src1 ^ (
10,295,808✔
817
                static_cast<T>(src0 << (start1 - start0))
10,295,808✔
818
                &
10,295,808✔
819
                static_cast<T>(msk << start1)
10,295,808✔
820
        );
10,295,808✔
821
        src0 = src0 ^ (
10,295,808✔
822
                static_cast<T>(lsr(src1, (start1 - start0)))
10,295,808✔
823
                &
10,295,808✔
824
                static_cast<T>(msk << start0)
10,295,808✔
825
        );
10,295,808✔
826
    }
10,295,808✔
827
    return;
20,594,586✔
828
}
20,594,586✔
829
// clang-format on
830
// -------------------------------------------------------------------------- //
831

832
// ----------- IMPLEMENTATION DETAILS: INSTRUCTIONS: BIT COMPARE ------------ //
833
// Compares a subsequence of bits within src0 and src1 and returns 0 if equal
834
template <class T>
835
constexpr T _bitcmp(T src0, T src1, T start0, T start1, T len) noexcept {
836
  static_assert(binary_digits<T>::value, "");
837
  return _bextr(src0, start0, len) == _bextr(src1, start1, len);
838
}
839
// -------------------------------------------------------------------------- //
840

841
// --- IMPLEMENTATION DETAILS: INSTRUCTIONS: DOUBLE PRECISION SHIFT LEFT ---- //
842
// Left shifts dst by cnt bits, filling the lsbs of dst by the msbs of src
843
template <class T>
844
constexpr T _shld(T dst, T src, T cnt) noexcept {
845
  static_assert(binary_digits<T>::value, "");
846
  constexpr T digits = binary_digits<T>::value;
847
  if (cnt < digits) {
848
    dst = (dst << cnt) | (lsr(src, (digits - cnt)));
849
  } else {
850
    dst = (src << (cnt - digits)) * (cnt < digits + digits);
851
  }
852
  return dst;
853
}
854
// -------------------------------------------------------------------------- //
855

856
// --- IMPLEMENTATION DETAILS: INSTRUCTIONS: DOUBLE PRECISION SHIFT RIGHT --- //
857
// Right shifts dst by cnt bits, filling the msbs of dst by the lsbs of src
858
template <class T>
859
constexpr T _shrd(T dst, T src, T cnt) noexcept {
11,838,264✔
860
  static_assert(binary_digits<T>::value, "");
11,838,264✔
861
  constexpr T digits = binary_digits<T>::value;
11,838,264✔
862
  if (cnt < digits) {
11,838,264!
863
    dst = (lsr(dst, cnt)) | (src << (digits - cnt));
11,838,264✔
864
  } else {
11,838,264✔
NEW
865
    dst = (lsr(src, (cnt - digits))) * (cnt < digits + digits);
×
NEW
866
  }
×
867
  return dst;
11,838,264✔
868
}
11,838,264✔
869
// -------------------------------------------------------------------------- //
870

871
// ------------ IMPLEMENTATION DETAILS: INSTRUCTIONS: ADD CARRY ------------- //
872
// Adds src0 and src1 and returns the new carry bit with intrinsics
873
template <class C, class T, class>
874
constexpr C _addcarry(C carry, T src0, T src1, T* dst) noexcept {
875
  static_assert(binary_digits<T>::value, "");
876
  using wider_t = typename _wider_type<T>::type;
877
  constexpr T digits = binary_digits<T>::value;
878
  wider_t tmp = 0;
879
  unsigned int udst = 0;
880
  unsigned long long int ulldst = 0;
881
  if (digits == std::numeric_limits<unsigned int>::digits) {
882
    carry = __builtin_ia32_addcarryx_u32(carry, src0, src1, &udst);
883
    *dst = udst;
884
  } else if (digits == std::numeric_limits<unsigned long long int>::digits) {
885
    carry = __builtin_ia32_addcarryx_u64(carry, src0, src1, &ulldst);
886
    *dst = ulldst;
887
  } else if (digits < binary_digits<wider_t>::value) {
888
    tmp = static_cast<wider_t>(src0) + static_cast<wider_t>(src1);
889
    tmp += static_cast<wider_t>(static_cast<bool>(carry));
890
    *dst = tmp;
891
    carry = static_cast<bool>(tmp >> digits);
892
  } else {
893
    carry = _addcarry(carry, src0, src1, dst, std::ignore);
894
  }
895
  return carry;
896
}
897

898
// Adds src0 and src1 and returns the new carry bit without intrinsics
899
template <class C, class T, class... X>
900
constexpr C _addcarry(C carry, T src0, T src1, T* dst, X...) noexcept {
901
  static_assert(binary_digits<T>::value, "");
902
  *dst = src0 + src1 + static_cast<T>(static_cast<bool>(carry));
903
  return carry ? *dst <= src0 || *dst <= src1 : *dst < src0 || *dst < src1;
904
}
905
// -------------------------------------------------------------------------- //
906

907
// ------------ IMPLEMENTATION DETAILS: INSTRUCTIONS: SUB BORROW ------------ //
908
// Subtracts src1 to src0 and returns the new borrow bit with intrinsics
909
template <class B, class T, class>
910
constexpr B _subborrow(B borrow, T src0, T src1, T* dst) noexcept {
911
  static_assert(binary_digits<T>::value, "");
912
  using wider_t = typename _wider_type<T>::type;
913
  constexpr T digits = binary_digits<T>::value;
914
  wider_t tmp = 0;
915
  unsigned int udst = 0;
916
  unsigned long long int ulldst = 0;
917
  if (digits == std::numeric_limits<unsigned int>::digits) {
918
    borrow = __builtin_ia32_sbb_u32(borrow, src0, src1, &udst);
919
    *dst = udst;
920
  } else if (digits == std::numeric_limits<unsigned long long int>::digits) {
921
    borrow = __builtin_ia32_sbb_u64(borrow, src0, src1, &ulldst);
922
    *dst = ulldst;
923
  } else if (digits < binary_digits<wider_t>::value) {
924
    tmp = static_cast<wider_t>(src1);
925
    tmp += static_cast<wider_t>(static_cast<bool>(borrow));
926
    borrow = tmp > static_cast<wider_t>(src0);
927
    *dst = static_cast<wider_t>(src0) - tmp;
928
  } else {
929
    borrow = _subborrow(borrow, src0, src1, dst, std::ignore);
930
  }
931
  return borrow;
932
}
933

934
// Subtracts src1 to src0 and returns the new borrow bit with other intrinsics
935
template <class B, class T, class>
936
constexpr B _subborrow(const B& borrow, T src0, T src1, T* dst) noexcept {
937
  static_assert(binary_digits<T>::value, "");
938
  using wider_t = typename _wider_type<T>::type;
939
  constexpr T digits = binary_digits<T>::value;
940
  wider_t tmp = 0;
941
  unsigned int udst = 0;
942
  unsigned long long int ulldst = 0;
943
  B flag = borrow;
944
  if (digits == std::numeric_limits<unsigned int>::digits) {
945
    flag = __builtin_ia32_subborrow_u32(borrow, src0, src1, &udst);
946
    *dst = udst;
947
  } else if (digits == std::numeric_limits<unsigned long long int>::digits) {
948
    flag = __builtin_ia32_subborrow_u64(borrow, src0, src1, &ulldst);
949
    *dst = ulldst;
950
  } else if (digits < binary_digits<wider_t>::value) {
951
    tmp = static_cast<wider_t>(src1);
952
    tmp += static_cast<wider_t>(static_cast<bool>(borrow));
953
    flag = tmp > static_cast<wider_t>(src0);
954
    *dst = static_cast<wider_t>(src0) - tmp;
955
  } else {
956
    flag = _subborrow(borrow, src0, src1, dst, std::ignore);
957
  }
958
  return flag;
959
}
960

961
// Subtracts src1 to src0 and returns the new borrow bit without intrinsics
962
template <class B, class T, class... X>
963
constexpr B _subborrow(B borrow, T src0, T src1, T* dst, X...) noexcept {
964
  static_assert(binary_digits<T>::value, "");
965
  *dst = src0 - (src1 + static_cast<T>(static_cast<bool>(borrow)));
966
  return borrow ? src1 >= src0 : src1 > src0;
967
}
968
// -------------------------------------------------------------------------- //
969

970
// -------- IMPLEMENTATION DETAILS: INSTRUCTIONS: MULTIWORD MULTIPLY -------- //
971
// Multiplies src0 and src1 and gets the full result with compiler intrinsics
972
template <class T, class T128>
973
constexpr T _mulx(T src0, T src1, T* hi) noexcept
974
{
975
    static_assert(binary_digits<T>::value, "");
976
    using wider_t = typename _wider_type<T>::type;
977
    constexpr T digits = binary_digits<T>::value;
978
    wider_t tmp = 0;
979
    T128 tmp128 = 0;
980
    T lo = 0;
981
    if (digits == std::numeric_limits<std::uint64_t>::digits) {
982
        tmp128 = static_cast<T128>(src0) * static_cast<T128>(src1);
983
        *hi = tmp128 >> digits;
984
        lo = tmp128;
985
    } else if (digits + digits == binary_digits<wider_t>::value) {
986
        tmp = static_cast<wider_t>(src0) * static_cast<wider_t>(src1);
987
        *hi = tmp >> digits;
988
        lo = tmp;
989
    } else {
990
        lo = _mulx(src0, src1, hi, std::ignore);
991
    }
992
    return lo;
993
}
994

995
// Multiplies src0 and src1 and gets the full result without compiler intrinsics
996
template <class T, class... X>
997
constexpr T _mulx(T src0, T src1, T* hi, X...) noexcept
998
{
999
    static_assert(binary_digits<T>::value, "");
1000
    constexpr T digits = binary_digits<T>::value;
1001
    constexpr T offset = digits / 2;
1002
    constexpr T ones = ~static_cast<T>(0);
1003
    const T lsbs0 = src0 & static_cast<T>(lsr(ones, (digits - offset)));
1004
    const T msbs0 = lsr(src0, offset);
1005
    const T lsbs1 = src1 & static_cast<T>(lsr(ones, (digits - offset)));
1006
    const T msbs1 = lsr(src1, offset);
1007
    const T llsbs = lsbs0 * lsbs1;
1008
    const T mlsbs = msbs0 * lsbs1;
1009
    const T lmsbs = lsbs0 * msbs1;
1010
    const T mi = mlsbs + lmsbs;
1011
    const T lo = llsbs + static_cast<T>(mi << offset);
1012
    const T lcarry = lo < llsbs || lo < static_cast<T>(mi << offset);
1013
    const T mcarry = static_cast<T>(mi < mlsbs || mi < lmsbs) << offset;
1014
    *hi = static_cast<T>(lsr(mi, offset)) + msbs0 * msbs1 + mcarry + lcarry;
1015
    return lo;
1016
}
1017
// -------------------------------------------------------------------------- //
1018

1019

1020

1021
// ========================================================================== //
1022
} // namespace bit
1023
#endif // _BIT_DETAILS_HPP_INCLUDED
1024
// ========================================================================== //
1025

STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc