15658468082

Committed 15 Jun 2025 02:19AM UTC coverage: 54.19% (+0.7%) from 53.519%

Build # 15658468082

Build Type

Pull #17

github

Committed by

web-flow

Commit Message

Merge 9f7c4d06e into 0f0b787a1

Pull Request Pull Request #17: Truncation policy

Run Details

10212 of 18780 branches covered (54.38%)

Branch coverage included in aggregate %.

179 of 225 new or added lines in 12 files covered. (79.56%)

214 existing lines in 11 files now uncovered.

6037 of 11205 relevant lines covered (53.88%)

7751643.37 hits per line

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

70.61

/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 size_type = typename bit_iterator<InputIt>::size_type;
    constexpr size_type digits = binary_digits<word_type>::value;
    return std::distance(first.base(), last.base())*digits
           + (last.position() - first.position());
}

// Increments the iterator n times. (If n is negative, the iterator is decremented n times)
template <class InputIt, class Distance>
void advance(bit_iterator<InputIt>& first, Distance n)
{
    first += 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(*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;
}

// 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,	302,998✔
33	bit_iterator<InputIt> last
34	)
35	{	311,007✔
36	_assert_range_viability(first, last);	614,005✔
37	using word_type = typename bit_iterator<InputIt>::word_type;	311,007✔
38	using size_type = typename bit_iterator<InputIt>::size_type;	311,007✔
39	constexpr size_type digits = binary_digits<word_type>::value;	614,005✔
40	return std::distance(first.base(), last.base())*digits	614,005✔
41	+ (last.position() - first.position());	917,003✔
42	}	311,007✔
43
44	// Increments the iterator n times. (If n is negative, the iterator is decremented n times)
45	template <class InputIt, class Distance>
46	void advance(bit_iterator<InputIt>& first, Distance n)	3,030,833✔
47	{	1,054,059✔
48	first += n;	4,084,892✔
49	}	4,084,892✔
50
51	template<class ForwardIt>
52	bit_iterator<ForwardIt> next(
53	bit_iterator<ForwardIt> bit_it,
54	typename bit_iterator<ForwardIt>::difference_type n = 1
55	) {
56	return bit_it + n;
57	}
58
59	// -------------------------------------------------------------------------- //
60
61
62
63	// --------------------------- Utility Functions ---------------------------- //
64
65	// Returns distance(first, last) <= n
66	template <class InputIt>
67	bool is_within(
68	bit_iterator<InputIt> first,
69	bit_iterator<InputIt> last,
70	typename InputIt::difference_type n
71	) {
72	//using word_type = typename bit_iterator<InputIt>::word_type;
73	//using size_type = typename bit_iterator<InputIt>::size_type;
74	//constexpr size_type digits = binary_digits<word_type>::value;
75
76	return distance(first, last) <= n;
77	}
78
79	template <int N, class InputIt>
80	constexpr bool is_within(	33,358✔
81	bit_iterator<InputIt> first,
82	bit_iterator<InputIt> last
83	) {	29,614✔
84	using word_type = typename bit_iterator<InputIt>::word_type;	29,614✔
85	//using size_type = typename bit_iterator<InputIt>::size_type;
86	constexpr int digits = binary_digits<word_type>::value;	62,972✔
87	constexpr int full_words = N / digits;	62,972✔
88	constexpr int remainder_bits = N % digits;	62,972✔
89
90	if constexpr (full_words > 0) {	29,614✔
91	return (first.base() == last.base())	82,516✔
92	\|\| (std::next(first.base()) == last.base() && first.position() >= last.position())	71,690✔
93	\|\| is_within<N-digits>(first + digits, last)	118,659!
94	;	20,182✔
95	} else if (remainder_bits >= 0) {	20,182✔
96	return (first.base() == last.base()	47,172✔
97	&& first.position() + remainder_bits >= last.position()	15,688!
98	) \|\| (std::next(first.base()) == last.base()	69,196✔
99	&& (static_cast<int>(first.position()) + remainder_bits - digits >= static_cast<int>(last.position()))	12,620!
100	)	34,592✔
101	;	9,432✔
102	}	9,432✔
103	}	29,614✔
104
105	// Get next len bits beginning at start and store them in a word of type T
106	template <class T, class InputIt>
107	T get_word(const bit_iterator<InputIt>& first, size_t len = binary_digits<T>::value) {	4,190,571✔
108	using native_word_type = typename bit_iterator<InputIt>::word_type;	1,114,176✔
109	constexpr T digits = binary_digits<native_word_type>::value;	4,190,571✔
110	assert(digits >= len);	4,190,571!
111	using non_const_T = std::remove_cvref_t<T>;	1,114,176✔
112	non_const_T offset = digits - first.position();	4,190,571✔
113	non_const_T ret_word = lsr(*first.base(), first.position());	4,190,571✔
114
115	// We've already assigned enough bits
116	if (len <= offset) {	4,190,571!
117	return ret_word;	177,753✔
118	}	91,910✔
119
120	InputIt it = std::next(first.base());	4,012,818✔
121	len -= offset;	4,012,818✔
122	// Fill up ret_word starting at bit [offset] using it
123	// TODO define a mask and use the _bitblend that takes in the extra mask
124	while (len > digits) {	4,012,818!
125	ret_word = _bitblend<T>(	×
UNCOV 126	ret_word,
127	static_cast<T>(static_cast<T>(*it) << offset),	×
UNCOV 128	offset,
UNCOV 129	digits
UNCOV 130	);
131	++it;	×
132	offset += digits;	×
133	len -= digits;	×
UNCOV 134	}
135	// Assign remaining len bits of last word
136	ret_word = _bitblend<T>(	9,875,202✔
137	ret_word,	1,022,266✔
138	static_cast<T>(static_cast<T>(*it) << offset),	5,049,242✔
139	offset,	1,022,266✔
140	len	1,022,266✔
141	);	1,022,266✔
142	return ret_word;	4,012,818✔
143	}	1,114,176✔
144
145	// Get next len bits beginning at start and store them in a word of type T
146	// If we reach `last` before we get len bits, break and return the current word
147	// bits_read will store the number of bits that we read.
148	//template <class T, class InputIt>
149	//T get_word(bit_iterator<InputIt> first, bit_iterator<InputIt> last,
150	//T& bits_read, T len=binary_digits<T>::value
151	//)
152	//{
153	//using native_word_type = typename bit_iterator<InputIt>::word_type;
154	//constexpr T native_digits = binary_digits<native_word_type>::value;
155	//constexpr T ret_digits = binary_digits<T>::value;
156	//assert(ret_digits >= len);
157	//bits_read = native_digits - first.position();
158	//T ret_word = *first.base() >> first.position();
159
160	//// TODO vincent mentioned that we should aim for only 1 return function
161	//// per function. However I'm not sure how that can be accomplished here
162	//// without suffering a minor performance loss
163
164	//// We have reached the last iterator
165	//if (first.base() == last.base()) {
166	//bits_read -= (native_digits - last.position());
167	//return ret_word;
168	//}
169	//// We've already assigned enough bits
170	//if (len <= bits_read) {
171	//return ret_word;
172	//}
173
174	//InputIt it = std::next(first.base());
175	//len -= bits_read;
176	//// Fill up ret_word starting at bit [bits_read] using it
177	//// TODO define a mask and use the _bitblend that takes in the extra mask
178	//while (len > native_digits && it != last.base()) {
179	//ret_word = _bitblend(
180	//ret_word,
181	//static_cast<T>(static_cast<T>(*it) << bits_read),
182	//bits_read,
183	//native_digits
184	//);
185	//++it;
186	//bits_read += native_digits;
187	//len -= native_digits;
188	//}
189
190	//// Assign remaining len bits of last word
191	//if (it == last.base()) {
192	//bits_read -= (native_digits - last.position());
193	//ret_word = _bitblend(
194	//ret_word,
195	//static_cast<T>(static_cast<T>(*it) << bits_read),
196	//bits_read,
197	//last.position()
198	//);
199	//} else {
200	//ret_word = _bitblend(
201	//ret_word,
202	//static_cast<T>(static_cast<T>(*it) << bits_read),
203	//bits_read,
204	//len
205	//);
206	//}
207	//return ret_word;
208	//}
209
210
211	// Writes len bits from src beginning at dstIt
212	template <class src_type, class OutputIt>
213	void write_word(src_type src, bit_iterator<OutputIt> dst_bit_it,	90,210✔
214	src_type len=binary_digits<src_type>::value
215	)
216	{	94,538✔
217	using dst_type = typename bit_iterator<OutputIt>::word_type;	94,538✔
218	constexpr dst_type dst_digits = binary_digits<dst_type>::value;	184,748✔
219	constexpr dst_type src_digits = binary_digits<src_type>::value;	184,748✔
220
221	if constexpr (dst_digits >= src_digits) {	94,538✔
222	if (dst_bit_it.position() == 0 && len == dst_digits) {	184,748!
223	*dst_bit_it.base() = src;	56✔
224	} else {	94,502✔
225	*dst_bit_it.base() = _bitblend<src_type>(	371,847✔
226	*dst_bit_it.base(),	273,575✔
227	static_cast<src_type>(src << dst_bit_it.position()),	274,882✔
228	dst_bit_it.position(),	141,176✔
229	std::min<src_type>(	252,518✔
230	dst_digits - dst_bit_it.position(),	234,194✔
231	len));	94,502✔
232	if (len > dst_digits - dst_bit_it.position()) {	184,692!
233	OutputIt overflow_dst = std::next(dst_bit_it.base());	15,995✔
234	*overflow_dst = _bitblend<src_type>(	22,321✔
235	*overflow_dst,	15,995✔
236	lsr(src, (dst_digits - dst_bit_it.position())),	15,995✔
237	0,	7,513✔
238	len - (dst_digits - dst_bit_it.position()));	15,995✔
239	}	7,513✔
240	}	94,502✔
241	} else {
242	OutputIt it = dst_bit_it.base();
243	if (dst_bit_it.position() != 0) {
244	*it = _bitblend(
245	*it,
246	static_cast<dst_type>(src),
247	static_cast<dst_type>(-1) << dst_bit_it.position());
248	len -= dst_digits - dst_bit_it.position();
249	// TODO would it be faster to jsut shift src every time it is
250	// passed as an argument and keep track of how much we need to
251	// shift?
252	src = lsr(src, dst_digits - dst_bit_it.position());
253	++it;
254	}
255	while (len >= dst_digits) {
256	*it = static_cast<dst_type>(src);
257	src = lsr(src, dst_digits);
258	len -= dst_digits;
259	++it;
260	}
261	if (len > 0) {
262	*it = _bitblend(
263	*it,
264	static_cast<dst_type>(src),
265	_mask<dst_type>(len));
266	}
267	}
268	return;	274,958✔
269	}	94,538✔
270
271
272	// Shifts the range [first, last) to the left by n, filling the empty
273	// bits with 0
274	template <class RandomAccessIt>
275	RandomAccessIt word_shift_left(RandomAccessIt first,	1,032✔
276	RandomAccessIt last,
277	typename RandomAccessIt::difference_type n
278	)
279	{	1,032✔
280	if (n <= 0) return last;	2,064✔
281	if (n >= distance(first, last)) return first;	2,049✔
282	RandomAccessIt mid = first + n;	1,372✔
283	auto ret = std::move(mid, last, first);	1,372✔
284	return ret;	1,372✔
285	}	1,020✔
286
287
288	// Shifts the range [first, right) to the left by n, filling the empty
289	// bits with 0
290	// NOT OPTIMIZED. Will be replaced with std::shift eventually.
291	template <class RandomAccessIt>
292	RandomAccessIt word_shift_right(RandomAccessIt first,	1,032✔
293	RandomAccessIt last,
294	typename RandomAccessIt::difference_type n
295	)
296	{	1,032✔
297	auto d = distance(first, last);	2,064✔
298	if (n <= 0) return first;	2,064✔
299	if (n >= d) return last;	1,991✔
300	std::move_backward(first, last-n, last);	1,328✔
301	return std::next(first, n);	1,328✔
302	}	999✔
303
304	// returns a word consisting of all one bits
UNCOV 305	constexpr auto _all_ones() {
UNCOV 306	return -1;
UNCOV 307	}
308
309	// returns a word consisting of all zero bits
UNCOV 310	constexpr auto _all_zeros() {
UNCOV 311	return 0;
UNCOV 312	}
313
314	// checks that the passed iterator points to the first bit of a word
315	template <class It>
316	bool _is_aligned_lsb(bit_iterator<It> iter) {
317	return iter.position() == 0;
318	}
319
320	// checks that maybe_end is one position past the last bit of base
321	template <class ForwardIt>
322	bool _is_one_past_last_bit(bit_iterator<ForwardIt> maybe_end,
323	ForwardIt base) {
324	return maybe_end.position() == 0 && std::next(base) == maybe_end.base();
325	}
326
327	// checks that two bit iterators point to the same word
328	template <class It>
329	constexpr bool _in_same_word(bit_iterator<It> lhs, bit_iterator<It> rhs) {
330	return lhs.base() == rhs.base();
331	}
332
333	// simple alias for right shift
334	template <class WordType>
335	WordType _shift_towards_lsb(WordType word, std::size_t n) {
336	return word >> n;
337	}
338
339	// simple alias for left shift
340	template <class WordType>
341	WordType _shift_towards_msb(WordType word, std::size_t n) {
342	return word << n;
343	}
344
345	/* Used to read partial/full words and pad any missing digits. Will not
346	* read outside of the word pointed to by the first iterator (see case 4)
347	*
348	* Case 0: 01011101
349	* L F
350	* Case 1: 01011101 -> padded with 0s -> 00001101
351	* L F
352	* Case 2: 01011101 -> padded with 1s -> 01011111
353	* L F
354	* Case 3: 01011101 -> padded with 0s -> 00011100
355	* L F
356	* Case 4: 01011101 11111111 -> treated as 01011101
357	* F L L F
358	*
359	* Note: word is read from [first, last), meaning the element pointed
360	* to by last is not included in the read. if first == last, behavior
361	* is undefined
362	*/
363	template <class It>
364	[[deprecated("Unused")]]
365	typename bit_iterator<It>::word_type _padded_read(bit_iterator<It> first,
366	bit_iterator<It> last, const bit::bit_value bv) {
367	using word_type = typename bit_iterator<It>::word_type;
368
369	constexpr std::size_t num_digits = binary_digits<word_type>::value;
370	const std::size_t first_position = first.position();
371	const std::size_t last_position = last.position();
372	const word_type read = *(first.base());
373	constexpr word_type all_ones = _all_ones();
374
375	word_type mask;
376
377	if (_is_aligned_lsb(first)) {
378	if (_in_same_word(first, last)) {
379	// Case 1
380	if (bv == bit0) {
381	mask = _shift_towards_lsb(all_ones, num_digits - last_position);
382	return read & mask;
383	} else {
384	mask = _shift_towards_msb(all_ones, last_position);
385	return read \| mask;
386	}
387	} else {
388	// Case 0
389	return read;
390	}
391	} else {
392	if (!_in_same_word(first, last)) {
393	// Case 2
394	if (bv == bit0) {
395	mask = _shift_towards_msb(all_ones, first_position);
396	return read & mask;
397	} else {
398	mask = _shift_towards_lsb(all_ones, num_digits - first_position);
399	return read \| mask;
400	}
401	} else {
402	// Case 3
403	if (bv == bit0) {
404	mask = _shift_towards_msb(all_ones, first_position);
405	mask &= _shift_towards_lsb(all_ones, num_digits - last_position);
406	return read & mask;
407	} else {
408	mask = _shift_towards_lsb(all_ones, num_digits - first_position);
409	mask \|= _shift_towards_msb(all_ones, last_position);
410	return read \| mask;
411	}
412	}
413	}
414	}
415	// -------------------------------------------------------------------------- //
416
417
418
419	// ========================================================================== //
420	} // namespace bit
421	#endif // _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
422	// ========================================================================== //

PeterCDMcLean / BitLib / 15658468082

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