14987388202

Committed 13 May 2025 03:18AM UTC coverage: 49.868% (-46.5%) from 96.333%

Build # 14987388202

Build Type

Pull #7

github

Committed by

web-flow

Commit Message

Merge ec5f59a7f into 09dd4e61e

Pull Request Pull Request #7: Add github workflow targets for warnings

Run Details

5155 of 10638 branches covered (48.46%)

Branch coverage included in aggregate %.

39 of 70 new or added lines in 1 file covered. (55.71%)

128 existing lines in 10 files now uncovered.

5402 of 10532 relevant lines covered (51.29%)

5332091.8 hits per line

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

76.49

/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]
// 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(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_cv_t<T>;
    non_const_T offset = digits - first.position();
    non_const_T ret_word = *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(),
                   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,
                        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 >>= dst_digits - dst_bit_it.position();
            ++it;
        }
        while (len >= dst_digits) {
            *it = static_cast<dst_type>(src);
            src >>= dst_digits;
            len -= dst_digits;
            ++it;
        }
        if (len > 0 ) {
            *it = _bitblend(
                    *it,
                    static_cast<dst_type>(src),
                    (1 << len) - 1
            );
        }
    }
    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>
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	// License: BSD 3-Clause License
8	// ========================================================================== //
9	#ifndef _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
10	#define _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
11	// ========================================================================== //
12
13
14
15	// ============================== PREAMBLE ================================== //
16	// C++ standard library
17	// Project sources
18	#include "bitlib/bit-iterator/bit.hpp"
19	// Third-party libraries
20	// Miscellaneous
21	namespace bit {
22	// ========================================================================== //
23
24
25
26	// -------------------------- Iterator Algorithms --------------------------- //
27	// Returns the number of increments needed to get to last from first.
28	// May be negative if last comes before first (Only when input is RAI)
29	template <class InputIt>
30	typename bit_iterator<InputIt>::difference_type
31	distance(bit_iterator<InputIt> first,	138,034✔
32	bit_iterator<InputIt> last
33	)
34	{	147,133✔
35	_assert_range_viability(first, last);	285,167✔
36	using word_type = typename bit_iterator<InputIt>::word_type;	147,133✔
37	using size_type = typename bit_iterator<InputIt>::size_type;	147,133✔
38	constexpr size_type digits = binary_digits<word_type>::value;	285,167✔
39	return std::distance(first.base(), last.base())*digits	285,167✔
40	+ (last.position() - first.position());	423,201✔
41	}	147,133✔
42
43	// Increments the iterator n times. (If n is negative, the iterator is decremented n times)
44	template <class InputIt, class Distance>
45	void advance(bit_iterator<InputIt>& first, Distance n)	485,940✔
46	{	419,308✔
47	first += n;	905,248✔
48	}	905,248✔
49
50	template<class ForwardIt>
51	bit_iterator<ForwardIt> next(
52	bit_iterator<ForwardIt> bit_it,
53	typename bit_iterator<ForwardIt>::difference_type n = 1
54	) {
55	return bit_it + n;
56	}
57
58	// -------------------------------------------------------------------------- //
59
60
61
62	// --------------------------- Utility Functions ---------------------------- //
63
64	// Returns distance(first, last) <= n
65	template <class InputIt>
66	bool is_within(
67	bit_iterator<InputIt> first,
68	bit_iterator<InputIt> last,
69	typename InputIt::difference_type n
70	) {
71	//using word_type = typename bit_iterator<InputIt>::word_type;
72	//using size_type = typename bit_iterator<InputIt>::size_type;
73	//constexpr size_type digits = binary_digits<word_type>::value;
74
75	return distance(first, last) <= n;
76	}
77
78	template <int N, class InputIt>
79	constexpr bool is_within(	18,108✔
80	bit_iterator<InputIt> first,
81	bit_iterator<InputIt> last
82	) {	17,566✔
83	using word_type = typename bit_iterator<InputIt>::word_type;	17,566✔
84	//using size_type = typename bit_iterator<InputIt>::size_type;
85	constexpr int digits = binary_digits<word_type>::value;	35,674✔
86	constexpr int full_words = N / digits;	35,674✔
87	constexpr int remainder_bits = N % digits;	35,674✔
88
89	if constexpr (full_words > 0) {	17,566✔
90	return (first.base() == last.base())	43,830!
91	\|\| (std::next(first.base()) == last.base() && first.position() >= last.position())	38,936!
92	\|\| is_within<N-digits>(first + digits, last)	63,175!
93	;	11,142✔
94	} else if (remainder_bits >= 0) {	11,142✔
95	return (first.base() == last.base()	28,060!
96	&& first.position() + remainder_bits >= last.position()	10,128!
97	) \|\| (std::next(first.base()) == last.base()	40,877!
98	&& (static_cast<int>(first.position()) + remainder_bits - digits >= static_cast<int>(last.position()))	8,325!
99	)	20,848✔
100	;	6,424✔
101	}	6,424✔
102	}	17,566✔
103
104	// Get next len bits beginning at start and store them in a word of type T
105	template <class T, class InputIt>
106	T get_word(bit_iterator<InputIt> first, size_t len=binary_digits<T>::value)	510,450✔
107	{	448,711✔
108	using native_word_type = typename bit_iterator<InputIt>::word_type;	448,711✔
109	constexpr T digits = binary_digits<native_word_type>::value;	959,161✔
110	assert(digits >= len);	959,161!
111	using non_const_T = std::remove_cv_t<T>;	448,711✔
112	non_const_T offset = digits - first.position();	959,161✔
113	non_const_T ret_word = *first.base() >> first.position();	959,161✔
114
115	// We've already assigned enough bits
116	if (len <= offset) {	959,161!
117	return ret_word;	67,667✔
118	}	35,480✔
119
120	InputIt it = std::next(first.base());	891,494✔
121	len -= offset;	891,494✔
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) {	891,494!
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>(	1,159,748✔
137	ret_word,	413,231✔
138	static_cast<T>(static_cast<T>(*it) << offset),	1,235,630✔
139	offset,	413,231✔
140	len	413,231✔
141	);	413,231✔
142	return ret_word;	891,494✔
143	}	448,711✔
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,	43,535✔
214	src_type len=binary_digits<src_type>::value
215	)
216	{	47,418✔
217	using dst_type = typename bit_iterator<OutputIt>::word_type;	47,418✔
218	constexpr dst_type dst_digits = binary_digits<dst_type>::value;	90,953✔
219	constexpr dst_type src_digits = binary_digits<src_type>::value;	90,953✔
220
221	if constexpr (dst_digits >= src_digits) {	47,418✔
222	if (dst_bit_it.position() == 0 && len == dst_digits) {	90,953!
223	*dst_bit_it.base() = src;	38✔
224	}	19✔
225	else {	47,399✔
226	*dst_bit_it.base() = _bitblend<src_type>(	181,368✔
227	*dst_bit_it.base(),	133,669✔
228	src << dst_bit_it.position(),	134,431✔
229	dst_bit_it.position(),	67,134✔
230	std::min<src_type>(	123,543✔
231	dst_digits - dst_bit_it.position(),	114,696✔
232	len	47,399✔
233	)	47,399✔
234	);	47,399✔
235	if (len > dst_digits - dst_bit_it.position()) {	90,915!
236	OutputIt overflow_dst = std::next(dst_bit_it.base());	7,384✔
237	*overflow_dst = _bitblend<src_type>(	7,384✔
238	*overflow_dst,	7,384✔
239	src >> (dst_digits - dst_bit_it.position()),	7,384✔
240	0,	2,673✔
241	len - (dst_digits - dst_bit_it.position())	7,384✔
242	);	2,673✔
243	}	2,673✔
244	}	47,399✔
245	} else {
246	OutputIt it = dst_bit_it.base();
247	if (dst_bit_it.position() != 0) {
248	*it = _bitblend(
249	*it,
250	static_cast<dst_type>(src),
251	static_cast<dst_type>(-1) << dst_bit_it.position()
252	);
253	len -= dst_digits - dst_bit_it.position();
254	// TODO would it be faster to jsut shift src every time it is
255	// passed as an argument and keep track of how much we need to
256	// shift?
257	src >>= dst_digits - dst_bit_it.position();
258	++it;
259	}
260	while (len >= dst_digits) {
261	*it = static_cast<dst_type>(src);
262	src >>= dst_digits;
263	len -= dst_digits;
264	++it;
265	}
266	if (len > 0 ) {
267	*it = _bitblend(
268	*it,
269	static_cast<dst_type>(src),
270	(1 << len) - 1
271	);
272	}
273	}
274	return;	134,488✔
275	}	47,418✔
276
277
278	// Shifts the range [first, last) to the left by n, filling the empty
279	// bits with 0
280	template <class RandomAccessIt>
281	RandomAccessIt word_shift_left(RandomAccessIt first,	516✔
282	RandomAccessIt last,
283	typename RandomAccessIt::difference_type n
284	)
285	{	516✔
286	if (n <= 0) return last;	1,032✔
287	if (n >= distance(first, last)) return first;	1,025✔
288	RandomAccessIt mid = first + n;	755✔
289	auto ret = std::move(mid, last, first);	755✔
290	return ret;	755✔
291	}	512✔
292
293
294	// Shifts the range [first, right) to the left by n, filling the empty
295	// bits with 0
296	// NOT OPTIMIZED. Will be replaced with std::shift eventually.
297	template <class RandomAccessIt>
298	RandomAccessIt word_shift_right(RandomAccessIt first,	516✔
299	RandomAccessIt last,
300	typename RandomAccessIt::difference_type n
301	)
302	{	516✔
303	auto d = distance(first, last);	1,032✔
304	if (n <= 0) return first;	1,032✔
305	if (n >= d) return last;	989✔
306	std::move_backward(first, last-n, last);	815✔
307	return std::next(first, n);	815✔
308	}	502✔
309
310	// returns a word consisting of all one bits
UNCOV 311	constexpr auto _all_ones() {
UNCOV 312	return -1;
UNCOV 313	}
314
315	// returns a word consisting of all zero bits
UNCOV 316	constexpr auto _all_zeros() {
UNCOV 317	return 0;
UNCOV 318	}
319
320	// checks that the passed iterator points to the first bit of a word
321	template <class It>
322	bool _is_aligned_lsb(bit_iterator<It> iter) {
323	return iter.position() == 0;
324	}
325
326	// checks that maybe_end is one position past the last bit of base
327	template <class ForwardIt>
328	bool _is_one_past_last_bit(bit_iterator<ForwardIt> maybe_end,
329	ForwardIt base) {
330	return maybe_end.position() == 0 && std::next(base) == maybe_end.base();
331	}
332
333	// checks that two bit iterators point to the same word
334	template <class It>
335	constexpr bool _in_same_word(bit_iterator<It> lhs, bit_iterator<It> rhs) {
336	return lhs.base() == rhs.base();
337	}
338
339	// simple alias for right shift
340	template <class WordType>
341	WordType _shift_towards_lsb(WordType word, std::size_t n) {
342	return word >> n;
343	}
344
345	// simple alias for left shift
346	template <class WordType>
347	WordType _shift_towards_msb(WordType word, std::size_t n) {
348	return word << n;
349	}
350
351	/* Used to read partial/full words and pad any missing digits. Will not
352	* read outside of the word pointed to by the first iterator (see case 4)
353	*
354	* Case 0: 01011101
355	* L F
356	* Case 1: 01011101 -> padded with 0s -> 00001101
357	* L F
358	* Case 2: 01011101 -> padded with 1s -> 01011111
359	* L F
360	* Case 3: 01011101 -> padded with 0s -> 00011100
361	* L F
362	* Case 4: 01011101 11111111 -> treated as 01011101
363	* F L L F
364	*
365	* Note: word is read from [first, last), meaning the element pointed
366	* to by last is not included in the read. if first == last, behavior
367	* is undefined
368	*/
369	template <class It>
370	typename bit_iterator<It>::word_type _padded_read(bit_iterator<It> first,
371	bit_iterator<It> last, const bit::bit_value bv) {
372
373	using word_type = typename bit_iterator<It>::word_type;
374
375	constexpr std::size_t num_digits = binary_digits<word_type>::value;
376	const std::size_t first_position = first.position();
377	const std::size_t last_position = last.position();
378	const word_type read = *(first.base());
379	constexpr word_type all_ones = _all_ones();
380
381	word_type mask;
382
383	if (_is_aligned_lsb(first)) {
384	if (_in_same_word(first, last)) {
385	// Case 1
386	if (bv == bit0) {
387	mask = _shift_towards_lsb(all_ones, num_digits - last_position);
388	return read & mask;
389	} else {
390	mask = _shift_towards_msb(all_ones, last_position);
391	return read \| mask;
392	}
393	} else {
394	// Case 0
395	return read;
396	}
397	} else {
398	if (!_in_same_word(first, last)) {
399	// Case 2
400	if (bv == bit0) {
401	mask = _shift_towards_msb(all_ones, first_position);
402	return read & mask;
403	} else {
404	mask = _shift_towards_lsb(all_ones, num_digits - first_position);
405	return read \| mask;
406	}
407	} else {
408	// Case 3
409	if (bv == bit0) {
410	mask = _shift_towards_msb(all_ones, first_position);
411	mask &= _shift_towards_lsb(all_ones, num_digits - last_position);
412	return read & mask;
413	} else {
414	mask = _shift_towards_lsb(all_ones, num_digits - first_position);
415	mask \|= _shift_towards_msb(all_ones, last_position);
416	return read \| mask;
417	}
418	}
419	}
420	}
421	// -------------------------------------------------------------------------- //
422
423
424
425	// ========================================================================== //
426	} // namespace bit
427	#endif // _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
428	// ========================================================================== //

PeterCDMcLean / BitLib / 14987388202

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