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

PeterCDMcLean / BitLib / 16829837342

08 Aug 2025 11:58AM UTC coverage: 73.556% (-3.2%) from 76.797%
16829837342

Pull #29

github

web-flow
Merge 795bf174b into 4adca69e9
Pull Request #29: Explicitly cast inside _mask

3353 of 5056 branches covered (66.32%)

Branch coverage included in aggregate %.

188 of 196 new or added lines in 16 files covered. (95.92%)

56 existing lines in 5 files now uncovered.

2455 of 2840 relevant lines covered (86.44%)

15641929.23 hits per line

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

62.67
/include/bitlib/bit-algorithms/bit_algorithm_details.hpp
1
// ========================= BIT ALGORITHM DETAILS  ========================= //
2
// Project: The Experimental Bit Algorithms Library
3
// Name: bit_algorithm_details.hpp
4
// Description: A set of utilities to assist in writing algorithms
5
// Contributor(s): Vincent Reverdy [2019]
6
//                 Bryce Kille [2019]
7
//                 Peter McLean [2025]
8
// License: BSD 3-Clause License
9
// ========================================================================== //
10
#ifndef _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
11
#define _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
12
// ========================================================================== //
13

14

15

16
// ============================== PREAMBLE ================================== //
17
// C++ standard library
18
// Project sources
19
#include "bitlib/bit-iterator/bit.hpp"
20
// Third-party libraries
21
// Miscellaneous
22
namespace bit {
23
// ========================================================================== //
24

25

26

27
// -------------------------- Iterator Algorithms --------------------------- //
28
// Returns the number of increments needed to get to last from first.
29
// May be negative if last comes before first (Only when input is RAI)
30
template <class InputIt>
31
typename bit_iterator<InputIt>::difference_type
32
distance(bit_iterator<InputIt> first,
33
         bit_iterator<InputIt> last) {
1,611,827✔
34
  _assert_range_viability(first, last);
1,611,827✔
35
  using word_type = typename bit_iterator<InputIt>::word_type;
1,611,827✔
36
  using difference_type = typename bit_iterator<InputIt>::difference_type;
1,611,827✔
37
  constexpr difference_type digits = binary_digits<word_type>::value;
1,611,827✔
38
  return std::distance(first.base(), last.base()) * digits +
1,611,827✔
39
         static_cast<difference_type>(last.position()) -
1,611,827✔
40
         static_cast<difference_type>(first.position());
1,611,827✔
41
}
1,611,827✔
42

43
// Increments the iterator n times. (If n is negative, the iterator is decremented n times)
44
template <class InputIt>
45
void advance(bit_iterator<InputIt>& first, typename bit_iterator<InputIt>::difference_type n) {
888,967✔
46
  first += n;
888,967✔
47
}
888,967✔
48

49
template <typename InputIt, std::integral T>
50
void reverse(InputIt& it, const T& n) {
395,439✔
51
  ::std::advance(it, -static_cast<std::make_signed_t<T>>(n));
395,439✔
52
}
395,439✔
53

54
template <class ForwardIt>
55
bit_iterator<ForwardIt> next(
56
    bit_iterator<ForwardIt> bit_it,
57
    typename bit_iterator<ForwardIt>::difference_type n = 1) {
58
  return bit_it + n;
59
}
60

61
// -------------------------------------------------------------------------- //
62

63

64

65
// --------------------------- Utility Functions ---------------------------- //
66

67
// Returns distance(first, last) <= n
68
template <class InputIt>
69
bool is_within(
70
        bit_iterator<InputIt> first,
71
        bit_iterator<InputIt> last,
72
        typename InputIt::difference_type n
73
) {
74
    //using word_type = typename bit_iterator<InputIt>::word_type;
75
    //using size_type = typename bit_iterator<InputIt>::size_type;
76
    //constexpr size_type digits = binary_digits<word_type>::value;
77

78
    return distance(first, last) <= n;
79
}
80

81
template <int N, class InputIt>
82
constexpr bool is_within(
83
        bit_iterator<InputIt> first,
84
        bit_iterator<InputIt> last
85
) {
29,621✔
86
    using word_type = typename bit_iterator<InputIt>::word_type;
29,621✔
87
    //using size_type = typename bit_iterator<InputIt>::size_type;
88
    constexpr int digits = binary_digits<word_type>::value;
29,621✔
89
    constexpr int full_words = N / digits;
29,621✔
90
    constexpr int remainder_bits = N % digits;
29,621✔
91

92
    if constexpr (full_words > 0) {
29,621✔
93
        return (first.base() == last.base())
20,189!
94
            || (std::next(first.base()) == last.base() && first.position() >= last.position())
20,189!
95
            || is_within<N-digits>(first + digits, last)
20,189!
96
        ;
20,189✔
97
    } else if (remainder_bits >= 0) {
20,189✔
98
        return (first.base() == last.base()
9,432!
99
                && first.position() + remainder_bits >= last.position()
9,432!
100
               ) || (std::next(first.base()) == last.base()
9,432!
101
                   && (static_cast<int>(first.position()) + remainder_bits - digits >= static_cast<int>(last.position()))
9,432!
102
               )
9,432✔
103
        ;
9,432✔
104
    }
9,432✔
105
}
29,621✔
106

107
// Get next len bits beginning at start and store them in a word of type T
108
template <class T, class InputIt>
109
T get_word(const bit_iterator<InputIt>& first, size_t len = binary_digits<T>::value) {
2,901,381✔
110
  using native_word_type = typename bit_iterator<InputIt>::word_type;
2,901,381✔
111
  constexpr T digits = binary_digits<native_word_type>::value;
2,901,381✔
112
  assert(digits >= len);
2,901,381!
113
  using non_const_T = std::remove_cvref_t<T>;
2,901,381✔
114
  non_const_T offset = digits - first.position();
2,901,381✔
115
  non_const_T ret_word = lsr<T>(*first.base(), first.position());
2,901,381✔
116

117
  // We've already assigned enough bits
118
  if (len <= offset) {
2,901,381!
119
    return ret_word;
1,637,191✔
120
  }
1,637,191✔
121

122
    InputIt it = std::next(first.base());
1,264,190✔
123
    len -= offset;
1,264,190✔
124
    // Fill up ret_word starting at bit [offset] using it
125
    // TODO define a mask and use the _bitblend that takes in the extra mask
126
    while (len > digits) {
1,264,190!
127
        ret_word = _bitblend<T>(
×
128
                ret_word,
×
129
                static_cast<T>(static_cast<T>(*it) << offset),
×
130
                offset,
×
131
                digits
×
132
        );
×
UNCOV
133
        ++it;
×
UNCOV
134
        offset += digits;
×
UNCOV
135
        len -= digits;
×
UNCOV
136
    }
×
137
    // Assign remaining len bits of last word
138
    ret_word = _bitblend<T>(
1,264,190✔
139
            ret_word,
1,264,190✔
140
            static_cast<T>(static_cast<T>(*it) << offset),
1,264,190✔
141
            offset,
1,264,190✔
142
            len
1,264,190✔
143
    );
1,264,190✔
144
    return ret_word;
1,264,190✔
145
}
2,901,381✔
146

147
template <class T, class InputIt>
148
T get_masked_word(const bit_iterator<InputIt>& first, size_t len = binary_digits<T>::value) {
4,838✔
149
  return get_word<T>(first, len) & _mask<T>(len);
4,838✔
150
}
4,838✔
151

152
// Get next len bits beginning at start and store them in a word of type T
153
// If we reach `last` before we get len bits, break and return the current word
154
// bits_read will store the number of bits that we read.
155
//template <class T, class InputIt>
156
//T get_word(bit_iterator<InputIt> first, bit_iterator<InputIt> last,
157
        //T& bits_read, T len=binary_digits<T>::value
158
        //)
159
//{
160
    //using native_word_type = typename bit_iterator<InputIt>::word_type;
161
    //constexpr T native_digits = binary_digits<native_word_type>::value;
162
    //constexpr T ret_digits = binary_digits<T>::value;
163
    //assert(ret_digits >= len);
164
    //bits_read = native_digits - first.position();
165
    //T ret_word = *first.base() >> first.position();
166

167
    //// TODO vincent mentioned that we should aim for only 1 return function
168
    //// per function. However I'm not sure how that can be accomplished here
169
    //// without suffering a minor performance loss
170

171
    //// We have reached the last iterator
172
    //if (first.base() == last.base()) {
173
        //bits_read -= (native_digits - last.position());
174
        //return ret_word;
175
    //}
176
    //// We've already assigned enough bits
177
    //if (len <= bits_read) {
178
        //return ret_word;
179
    //}
180

181
    //InputIt it = std::next(first.base());
182
    //len -= bits_read;
183
    //// Fill up ret_word starting at bit [bits_read] using it
184
    //// TODO define a mask and use the _bitblend that takes in the extra mask
185
    //while (len > native_digits && it != last.base()) {
186
        //ret_word = _bitblend(
187
                //ret_word,
188
                //static_cast<T>(static_cast<T>(*it) << bits_read),
189
                //bits_read,
190
                //native_digits
191
        //);
192
        //++it;
193
        //bits_read += native_digits;
194
        //len -= native_digits;
195
    //}
196

197
    //// Assign remaining len bits of last word
198
    //if (it == last.base()) {
199
        //bits_read -= (native_digits - last.position());
200
        //ret_word = _bitblend(
201
                //ret_word,
202
                //static_cast<T>(static_cast<T>(*it) << bits_read),
203
                //bits_read,
204
                //last.position()
205
        //);
206
    //} else {
207
        //ret_word = _bitblend(
208
                //ret_word,
209
                //static_cast<T>(static_cast<T>(*it) << bits_read),
210
                //bits_read,
211
                //len
212
        //);
213
    //}
214
    //return ret_word;
215
//}
216

217

218
// Writes len bits from src beginning at dstIt
219
template <class src_type, class OutputIt>
220
void write_word(src_type src, bit_iterator<OutputIt> dst_bit_it,
221
        src_type len=binary_digits<src_type>::value
222
        )
223
{
94,545✔
224
  using dst_type = typename bit_iterator<OutputIt>::word_type;
94,545✔
225
  constexpr dst_type dst_digits = binary_digits<dst_type>::value;
94,545✔
226
  constexpr dst_type src_digits = binary_digits<src_type>::value;
94,545✔
227

228
  if constexpr (dst_digits >= src_digits) {
94,545✔
229
    if (dst_bit_it.position() == 0 && len == dst_digits) {
94,545!
230
      *dst_bit_it.base() = src;
37✔
231
    } else {
94,508✔
232
      *dst_bit_it.base() = _bitblend<src_type>(
94,508✔
233
          *dst_bit_it.base(),
94,508✔
234
          static_cast<src_type>(src << dst_bit_it.position()),
94,508✔
235
          dst_bit_it.position(),
94,508✔
236
          std::min<src_type>(
94,508✔
237
              dst_digits - dst_bit_it.position(),
94,508✔
238
              len));
94,508✔
239
      if (len > dst_digits - dst_bit_it.position()) {
94,508!
240
        OutputIt overflow_dst = std::next(dst_bit_it.base());
7,513✔
241
        *overflow_dst = _bitblend<src_type>(
7,513✔
242
            *overflow_dst,
7,513✔
243
            lsr(src, (dst_digits - dst_bit_it.position())),
7,513✔
244
            0,
7,513✔
245
            len - (dst_digits - dst_bit_it.position()));
7,513✔
246
      }
7,513✔
247
    }
94,508✔
248
  } else {
249
    OutputIt it = dst_bit_it.base();
250
    if (dst_bit_it.position() != 0) {
251
      *it = _bitblend(
252
          *it,
253
          static_cast<dst_type>(src),
254
          static_cast<dst_type>(-1) << dst_bit_it.position());
255
      len -= dst_digits - dst_bit_it.position();
256
      // TODO would it be faster to jsut shift src every time it is
257
      // passed as an argument and keep track of how much we need to
258
      // shift?
259
      src = lsr(src, dst_digits - dst_bit_it.position());
260
      ++it;
261
    }
262
    while (len >= dst_digits) {
263
      *it = static_cast<dst_type>(src);
264
      src = lsr(src, dst_digits);
265
      len -= dst_digits;
266
      ++it;
267
    }
268
    if (len > 0) {
269
      *it = _bitblend(
270
          *it,
271
          static_cast<dst_type>(src),
272
          _mask<dst_type>(len));
273
    }
274
  }
275
    return;
94,545✔
276
}
94,545✔
277

278

279
// Shifts the range [first, last) to the left by n, filling the empty
280
// bits with 0
281
template <class RandomAccessIt>
282
RandomAccessIt word_shift_left(RandomAccessIt first,
283
                          RandomAccessIt last,
284
                          typename RandomAccessIt::difference_type n
285
)
286
{
1,032✔
287
    if (n <= 0) return last;
1,032✔
288
    if (n >= distance(first, last)) return first;
1,020✔
289
    RandomAccessIt mid = first + n;
719✔
290
    auto ret = std::move(mid, last, first);
719✔
291
    return ret;
719✔
292
}
1,020✔
293

294

295
// Shifts the range [first, right) to the left by n, filling the empty
296
// bits with 0
297
// NOT OPTIMIZED. Will be replaced with std::shift eventually.
298
template <class RandomAccessIt>
299
RandomAccessIt word_shift_right(RandomAccessIt first,
300
                          RandomAccessIt last,
301
                          typename RandomAccessIt::difference_type n
302
)
303
{
1,032✔
304
    auto d = distance(first, last);
1,032✔
305
    if (n <= 0) return first;
1,032✔
306
    if (n >= d) return last;
999✔
307
    std::move_backward(first, last-n, last);
611✔
308
    return std::next(first, n);
611✔
309
}
999✔
310

311
// returns a word consisting of all one bits
UNCOV
312
constexpr auto _all_ones() {
×
UNCOV
313
    return -1;
×
UNCOV
314
}
×
315

316
// returns a word consisting of all zero bits
UNCOV
317
constexpr auto _all_zeros() {
×
UNCOV
318
    return 0;
×
UNCOV
319
}
×
320

321
// checks that the passed iterator points to the first bit of a word
322
template <class It>
323
bool _is_aligned_lsb(bit_iterator<It> iter) {
324
    return iter.position() == 0;
325
}
326

327
// checks that maybe_end is one position past the last bit of base
328
template <class ForwardIt>
329
bool _is_one_past_last_bit(bit_iterator<ForwardIt> maybe_end,
330
    ForwardIt base) {
331
    return maybe_end.position() == 0 && std::next(base) == maybe_end.base();
332
}
333

334
// checks that two bit iterators point to the same word
335
template <class It>
336
constexpr bool _in_same_word(bit_iterator<It> lhs, bit_iterator<It> rhs) {
337
    return lhs.base() == rhs.base();
338
}
339

340
// simple alias for right shift
341
template <class WordType>
342
WordType _shift_towards_lsb(WordType word, std::size_t n) {
343
    return word >> n;
344
}
345

346
// simple alias for left shift
347
template <class WordType>
348
WordType _shift_towards_msb(WordType word, std::size_t n) {
349
    return word << n;
350
}
351

352
/* Used to read partial/full words and pad any missing digits. Will not
353
 * read outside of the word pointed to by the first iterator (see case 4)
354
 *
355
 * Case 0: 01011101
356
 *        L       F
357
 * Case 1: 01011101 -> padded with 0s -> 00001101
358
 *            L   F
359
 * Case 2: 01011101 -> padded with 1s -> 01011111
360
 *        L    F
361
 * Case 3: 01011101 -> padded with 0s -> 00011100
362
 *           L  F
363
 * Case 4: 01011101 11111111 -> treated as 01011101
364
 *           F           L                L  F
365
 *
366
 * Note: word is read from [first, last), meaning the element pointed
367
 * to by last is not included in the read. if first == last, behavior
368
 * is undefined
369
 */
370
template <class It>
371
[[deprecated("Unused")]]
372
typename bit_iterator<It>::word_type _padded_read(bit_iterator<It> first,
373
                                                  bit_iterator<It> last, const bit::bit_value bv) {
374
  using word_type = typename bit_iterator<It>::word_type;
375

376
  constexpr std::size_t num_digits = binary_digits<word_type>::value;
377
  const std::size_t first_position = first.position();
378
  const std::size_t last_position = last.position();
379
  const word_type read = *(first.base());
380
  constexpr word_type all_ones = _all_ones();
381

382
  word_type mask;
383

384
  if (_is_aligned_lsb(first)) {
385
    if (_in_same_word(first, last)) {
386
      // Case 1
387
      if (bv == bit0) {
388
        mask = _shift_towards_lsb(all_ones, num_digits - last_position);
389
        return read & mask;
390
      } else {
391
        mask = _shift_towards_msb(all_ones, last_position);
392
        return read | mask;
393
      }
394
    } else {
395
      // Case 0
396
      return read;
397
    }
398
  } else {
399
    if (!_in_same_word(first, last)) {
400
      // Case 2
401
      if (bv == bit0) {
402
        mask = _shift_towards_msb(all_ones, first_position);
403
        return read & mask;
404
      } else {
405
        mask = _shift_towards_lsb(all_ones, num_digits - first_position);
406
        return read | mask;
407
      }
408
    } else {
409
      // Case 3
410
      if (bv == bit0) {
411
        mask = _shift_towards_msb(all_ones, first_position);
412
        mask &= _shift_towards_lsb(all_ones, num_digits - last_position);
413
        return read & mask;
414
      } else {
415
        mask = _shift_towards_lsb(all_ones, num_digits - first_position);
416
        mask |= _shift_towards_msb(all_ones, last_position);
417
        return read | mask;
418
      }
419
    }
420
  }
421
}
422
// -------------------------------------------------------------------------- //
423

424

425

426
// ========================================================================== //
427
} // namespace bit
428
#endif // _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
429
// ========================================================================== //
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

© 2025 Coveralls, Inc