16829837342

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

Build # 16829837342

Build Type

Pull #29

github

Committed by

web-flow

Commit Message

Merge 795bf174b into 4adca69e9

Pull Request Pull Request #29: Explicitly cast inside _mask

Run Details

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

// ========================= BIT ALGORITHM DETAILS  ========================= //
// Project: The Experimental Bit Algorithms Library
// Name: bit_algorithm_details.hpp
// Description: A set of utilities to assist in writing algorithms
// Contributor(s): Vincent Reverdy [2019]
//                 Bryce Kille [2019]
//                 Peter McLean [2025]
// License: BSD 3-Clause License
// ========================================================================== //
#ifndef _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
#define _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
// ========================================================================== //



// ============================== PREAMBLE ================================== //
// C++ standard library
// Project sources
#include "bitlib/bit-iterator/bit.hpp"
// Third-party libraries
// Miscellaneous
namespace bit {
// ========================================================================== //



// -------------------------- Iterator Algorithms --------------------------- //
// Returns the number of increments needed to get to last from first.
// May be negative if last comes before first (Only when input is RAI)
template <class InputIt>
typename bit_iterator<InputIt>::difference_type
distance(bit_iterator<InputIt> first,
         bit_iterator<InputIt> last) {
  _assert_range_viability(first, last);
  using word_type = typename bit_iterator<InputIt>::word_type;
  using difference_type = typename bit_iterator<InputIt>::difference_type;
  constexpr difference_type digits = binary_digits<word_type>::value;
  return std::distance(first.base(), last.base()) * digits +
         static_cast<difference_type>(last.position()) -
         static_cast<difference_type>(first.position());
}

// Increments the iterator n times. (If n is negative, the iterator is decremented n times)
template <class InputIt>
void advance(bit_iterator<InputIt>& first, typename bit_iterator<InputIt>::difference_type n) {
  first += n;
}

template <typename InputIt, std::integral T>
void reverse(InputIt& it, const T& n) {
  ::std::advance(it, -static_cast<std::make_signed_t<T>>(n));
}

template <class ForwardIt>
bit_iterator<ForwardIt> next(
    bit_iterator<ForwardIt> bit_it,
    typename bit_iterator<ForwardIt>::difference_type n = 1) {
  return bit_it + n;
}

// -------------------------------------------------------------------------- //



// --------------------------- Utility Functions ---------------------------- //

// Returns distance(first, last) <= n
template <class InputIt>
bool is_within(
        bit_iterator<InputIt> first,
        bit_iterator<InputIt> last,
        typename InputIt::difference_type n
) {
    //using word_type = typename bit_iterator<InputIt>::word_type;
    //using size_type = typename bit_iterator<InputIt>::size_type;
    //constexpr size_type digits = binary_digits<word_type>::value;

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

template <int N, class InputIt>
constexpr bool is_within(
        bit_iterator<InputIt> first,
        bit_iterator<InputIt> last
) {
    using word_type = typename bit_iterator<InputIt>::word_type;
    //using size_type = typename bit_iterator<InputIt>::size_type;
    constexpr int digits = binary_digits<word_type>::value;
    constexpr int full_words = N / digits;
    constexpr int remainder_bits = N % digits;

    if constexpr (full_words > 0) {
        return (first.base() == last.base())
            || (std::next(first.base()) == last.base() && first.position() >= last.position())
            || is_within<N-digits>(first + digits, last)
        ;
    } else if (remainder_bits >= 0) {
        return (first.base() == last.base()
                && first.position() + remainder_bits >= last.position()
               ) || (std::next(first.base()) == last.base()
                   && (static_cast<int>(first.position()) + remainder_bits - digits >= static_cast<int>(last.position()))
               )
        ;
    }
}

// Get next len bits beginning at start and store them in a word of type T
template <class T, class InputIt>
T get_word(const bit_iterator<InputIt>& first, size_t len = binary_digits<T>::value) {
  using native_word_type = typename bit_iterator<InputIt>::word_type;
  constexpr T digits = binary_digits<native_word_type>::value;
  assert(digits >= len);
  using non_const_T = std::remove_cvref_t<T>;
  non_const_T offset = digits - first.position();
  non_const_T ret_word = lsr<T>(*first.base(), first.position());

  // We've already assigned enough bits
  if (len <= offset) {
    return ret_word;
  }

    InputIt it = std::next(first.base());
    len -= offset;
    // Fill up ret_word starting at bit [offset] using it
    // TODO define a mask and use the _bitblend that takes in the extra mask
    while (len > digits) {
        ret_word = _bitblend<T>(
                ret_word,
                static_cast<T>(static_cast<T>(*it) << offset),
                offset,
                digits
        );
        ++it;
        offset += digits;
        len -= digits;
    }
    // Assign remaining len bits of last word
    ret_word = _bitblend<T>(
            ret_word,
            static_cast<T>(static_cast<T>(*it) << offset),
            offset,
            len
    );
    return ret_word;
}

template <class T, class InputIt>
T get_masked_word(const bit_iterator<InputIt>& first, size_t len = binary_digits<T>::value) {
  return get_word<T>(first, len) & _mask<T>(len);
}

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

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

    //// We have reached the last iterator
    //if (first.base() == last.base()) {
        //bits_read -= (native_digits - last.position());
        //return ret_word;
    //}
    //// We've already assigned enough bits
    //if (len <= bits_read) {
        //return ret_word;
    //}

    //InputIt it = std::next(first.base());
    //len -= bits_read;
    //// Fill up ret_word starting at bit [bits_read] using it
    //// TODO define a mask and use the _bitblend that takes in the extra mask
    //while (len > native_digits && it != last.base()) {
        //ret_word = _bitblend(
                //ret_word,
                //static_cast<T>(static_cast<T>(*it) << bits_read),
                //bits_read,
                //native_digits
        //);
        //++it;
        //bits_read += native_digits;
        //len -= native_digits;
    //}

    //// Assign remaining len bits of last word
    //if (it == last.base()) {
        //bits_read -= (native_digits - last.position());
        //ret_word = _bitblend(
                //ret_word,
                //static_cast<T>(static_cast<T>(*it) << bits_read),
                //bits_read,
                //last.position()
        //);
    //} else {
        //ret_word = _bitblend(
                //ret_word,
                //static_cast<T>(static_cast<T>(*it) << bits_read),
                //bits_read,
                //len
        //);
    //}
    //return ret_word;
//}


// Writes len bits from src beginning at dstIt
template <class src_type, class OutputIt>
void write_word(src_type src, bit_iterator<OutputIt> dst_bit_it,
        src_type len=binary_digits<src_type>::value
        )
{
  using dst_type = typename bit_iterator<OutputIt>::word_type;
  constexpr dst_type dst_digits = binary_digits<dst_type>::value;
  constexpr dst_type src_digits = binary_digits<src_type>::value;

  if constexpr (dst_digits >= src_digits) {
    if (dst_bit_it.position() == 0 && len == dst_digits) {
      *dst_bit_it.base() = src;
    } else {
      *dst_bit_it.base() = _bitblend<src_type>(
          *dst_bit_it.base(),
          static_cast<src_type>(src << dst_bit_it.position()),
          dst_bit_it.position(),
          std::min<src_type>(
              dst_digits - dst_bit_it.position(),
              len));
      if (len > dst_digits - dst_bit_it.position()) {
        OutputIt overflow_dst = std::next(dst_bit_it.base());
        *overflow_dst = _bitblend<src_type>(
            *overflow_dst,
            lsr(src, (dst_digits - dst_bit_it.position())),
            0,
            len - (dst_digits - dst_bit_it.position()));
      }
    }
  } else {
    OutputIt it = dst_bit_it.base();
    if (dst_bit_it.position() != 0) {
      *it = _bitblend(
          *it,
          static_cast<dst_type>(src),
          static_cast<dst_type>(-1) << dst_bit_it.position());
      len -= dst_digits - dst_bit_it.position();
      // TODO would it be faster to jsut shift src every time it is
      // passed as an argument and keep track of how much we need to
      // shift?
      src = lsr(src, dst_digits - dst_bit_it.position());
      ++it;
    }
    while (len >= dst_digits) {
      *it = static_cast<dst_type>(src);
      src = lsr(src, dst_digits);
      len -= dst_digits;
      ++it;
    }
    if (len > 0) {
      *it = _bitblend(
          *it,
          static_cast<dst_type>(src),
          _mask<dst_type>(len));
    }
  }
    return;
}


// Shifts the range [first, last) to the left by n, filling the empty
// bits with 0
template <class RandomAccessIt>
RandomAccessIt word_shift_left(RandomAccessIt first,
                          RandomAccessIt last,
                          typename RandomAccessIt::difference_type n
)
{
    if (n <= 0) return last;
    if (n >= distance(first, last)) return first;
    RandomAccessIt mid = first + n;
    auto ret = std::move(mid, last, first);
    return ret;
}


// Shifts the range [first, right) to the left by n, filling the empty
// bits with 0
// NOT OPTIMIZED. Will be replaced with std::shift eventually.
template <class RandomAccessIt>
RandomAccessIt word_shift_right(RandomAccessIt first,
                          RandomAccessIt last,
                          typename RandomAccessIt::difference_type n
)
{
    auto d = distance(first, last);
    if (n <= 0) return first;
    if (n >= d) return last;
    std::move_backward(first, last-n, last);
    return std::next(first, n);
}

// returns a word consisting of all one bits
constexpr auto _all_ones() {
    return -1;
}

// returns a word consisting of all zero bits
constexpr auto _all_zeros() {
    return 0;
}

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

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

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

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

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

/* Used to read partial/full words and pad any missing digits. Will not
 * read outside of the word pointed to by the first iterator (see case 4)
 *
 * Case 0: 01011101
 *        L       F
 * Case 1: 01011101 -> padded with 0s -> 00001101
 *            L   F
 * Case 2: 01011101 -> padded with 1s -> 01011111
 *        L    F
 * Case 3: 01011101 -> padded with 0s -> 00011100
 *           L  F
 * Case 4: 01011101 11111111 -> treated as 01011101
 *           F           L                L  F
 *
 * Note: word is read from [first, last), meaning the element pointed
 * to by last is not included in the read. if first == last, behavior
 * is undefined
 */
template <class It>
[[deprecated("Unused")]]
typename bit_iterator<It>::word_type _padded_read(bit_iterator<It> first,
                                                  bit_iterator<It> last, const bit::bit_value bv) {
  using word_type = typename bit_iterator<It>::word_type;

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

  word_type mask;

  if (_is_aligned_lsb(first)) {
    if (_in_same_word(first, last)) {
      // Case 1
      if (bv == bit0) {
        mask = _shift_towards_lsb(all_ones, num_digits - last_position);
        return read & mask;
      } else {
        mask = _shift_towards_msb(all_ones, last_position);
        return read | mask;
      }
    } else {
      // Case 0
      return read;
    }
  } else {
    if (!_in_same_word(first, last)) {
      // Case 2
      if (bv == bit0) {
        mask = _shift_towards_msb(all_ones, first_position);
        return read & mask;
      } else {
        mask = _shift_towards_lsb(all_ones, num_digits - first_position);
        return read | mask;
      }
    } else {
      // Case 3
      if (bv == bit0) {
        mask = _shift_towards_msb(all_ones, first_position);
        mask &= _shift_towards_lsb(all_ones, num_digits - last_position);
        return read & mask;
      } else {
        mask = _shift_towards_lsb(all_ones, num_digits - first_position);
        mask |= _shift_towards_msb(all_ones, last_position);
        return read | mask;
      }
    }
  }
}
// -------------------------------------------------------------------------- //



// ========================================================================== //
} // namespace bit
#endif // _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
// ========================================================================== //

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	// ========================================================================== //

PeterCDMcLean / BitLib / 16829837342

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

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