15696616722

Committed 17 Jun 2025 02:29AM UTC coverage: 54.11% (+0.6%) from 53.519%

Build # 15696616722

Build Type

Pull #17

github

Committed by

web-flow

Commit Message

Merge caf45e877 into 0f0b787a1

Pull Request Pull Request #17: Truncation policy

Run Details

10137 of 18710 branches covered (54.18%)

Branch coverage included in aggregate %.

212 of 251 new or added lines in 13 files covered. (84.46%)

214 existing lines in 11 files now uncovered.

6062 of 11227 relevant lines covered (53.99%)

7736453.1 hits per line

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

70.79

/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;
}

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,	303,043✔
33	bit_iterator<InputIt> last
34	)
35	{	311,052✔
36	_assert_range_viability(first, last);	614,095✔
37	using word_type = typename bit_iterator<InputIt>::word_type;	311,052✔
38	using size_type = typename bit_iterator<InputIt>::size_type;	311,052✔
39	constexpr size_type digits = binary_digits<word_type>::value;	614,095✔
40	return std::distance(first.base(), last.base())*digits	614,095✔
41	+ (last.position() - first.position());	917,138✔
42	}	311,052✔
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,855✔
47	{	1,054,081✔
48	first += n;	4,084,936✔
49	}	4,084,936✔
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,653✔
108	using native_word_type = typename bit_iterator<InputIt>::word_type;	1,114,217✔
109	constexpr T digits = binary_digits<native_word_type>::value;	4,190,653✔
110	assert(digits >= len);	4,190,653!
111	using non_const_T = std::remove_cvref_t<T>;	1,114,217✔
112	non_const_T offset = digits - first.position();	4,190,653✔
113	non_const_T ret_word = lsr(*first.base(), first.position());	4,190,653✔
114
115	// We've already assigned enough bits
116	if (len <= offset) {	4,190,653!
117	return ret_word;	177,835✔
118	}	91,951✔
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,217✔
144
145	template <class T, class InputIt>
146	T get_masked_word(const bit_iterator<InputIt>& first, size_t len = binary_digits<T>::value) {	6✔
147	return get_word<T>(first, len) & _mask<T>(len);	9✔
148	}	3✔
149
150	// Get next len bits beginning at start and store them in a word of type T
151	// If we reach `last` before we get len bits, break and return the current word
152	// bits_read will store the number of bits that we read.
153	//template <class T, class InputIt>
154	//T get_word(bit_iterator<InputIt> first, bit_iterator<InputIt> last,
155	//T& bits_read, T len=binary_digits<T>::value
156	//)
157	//{
158	//using native_word_type = typename bit_iterator<InputIt>::word_type;
159	//constexpr T native_digits = binary_digits<native_word_type>::value;
160	//constexpr T ret_digits = binary_digits<T>::value;
161	//assert(ret_digits >= len);
162	//bits_read = native_digits - first.position();
163	//T ret_word = *first.base() >> first.position();
164
165	//// TODO vincent mentioned that we should aim for only 1 return function
166	//// per function. However I'm not sure how that can be accomplished here
167	//// without suffering a minor performance loss
168
169	//// We have reached the last iterator
170	//if (first.base() == last.base()) {
171	//bits_read -= (native_digits - last.position());
172	//return ret_word;
173	//}
174	//// We've already assigned enough bits
175	//if (len <= bits_read) {
176	//return ret_word;
177	//}
178
179	//InputIt it = std::next(first.base());
180	//len -= bits_read;
181	//// Fill up ret_word starting at bit [bits_read] using it
182	//// TODO define a mask and use the _bitblend that takes in the extra mask
183	//while (len > native_digits && it != last.base()) {
184	//ret_word = _bitblend(
185	//ret_word,
186	//static_cast<T>(static_cast<T>(*it) << bits_read),
187	//bits_read,
188	//native_digits
189	//);
190	//++it;
191	//bits_read += native_digits;
192	//len -= native_digits;
193	//}
194
195	//// Assign remaining len bits of last word
196	//if (it == last.base()) {
197	//bits_read -= (native_digits - last.position());
198	//ret_word = _bitblend(
199	//ret_word,
200	//static_cast<T>(static_cast<T>(*it) << bits_read),
201	//bits_read,
202	//last.position()
203	//);
204	//} else {
205	//ret_word = _bitblend(
206	//ret_word,
207	//static_cast<T>(static_cast<T>(*it) << bits_read),
208	//bits_read,
209	//len
210	//);
211	//}
212	//return ret_word;
213	//}
214
215
216	// Writes len bits from src beginning at dstIt
217	template <class src_type, class OutputIt>
218	void write_word(src_type src, bit_iterator<OutputIt> dst_bit_it,	90,210✔
219	src_type len=binary_digits<src_type>::value
220	)
221	{	94,538✔
222	using dst_type = typename bit_iterator<OutputIt>::word_type;	94,538✔
223	constexpr dst_type dst_digits = binary_digits<dst_type>::value;	184,748✔
224	constexpr dst_type src_digits = binary_digits<src_type>::value;	184,748✔
225
226	if constexpr (dst_digits >= src_digits) {	94,538✔
227	if (dst_bit_it.position() == 0 && len == dst_digits) {	184,748!
228	*dst_bit_it.base() = src;	56✔
229	} else {	94,502✔
230	*dst_bit_it.base() = _bitblend<src_type>(	371,847✔
231	*dst_bit_it.base(),	273,575✔
232	static_cast<src_type>(src << dst_bit_it.position()),	274,882✔
233	dst_bit_it.position(),	141,176✔
234	std::min<src_type>(	252,518✔
235	dst_digits - dst_bit_it.position(),	234,194✔
236	len));	94,502✔
237	if (len > dst_digits - dst_bit_it.position()) {	184,692!
238	OutputIt overflow_dst = std::next(dst_bit_it.base());	15,995✔
239	*overflow_dst = _bitblend<src_type>(	22,321✔
240	*overflow_dst,	15,995✔
241	lsr(src, (dst_digits - dst_bit_it.position())),	15,995✔
242	0,	7,513✔
243	len - (dst_digits - dst_bit_it.position()));	15,995✔
244	}	7,513✔
245	}	94,502✔
246	} else {
247	OutputIt it = dst_bit_it.base();
248	if (dst_bit_it.position() != 0) {
249	*it = _bitblend(
250	*it,
251	static_cast<dst_type>(src),
252	static_cast<dst_type>(-1) << dst_bit_it.position());
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 = lsr(src, dst_digits - dst_bit_it.position());
258	++it;
259	}
260	while (len >= dst_digits) {
261	*it = static_cast<dst_type>(src);
262	src = lsr(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	_mask<dst_type>(len));
271	}
272	}
273	return;	274,958✔
274	}	94,538✔
275
276
277	// Shifts the range [first, last) to the left by n, filling the empty
278	// bits with 0
279	template <class RandomAccessIt>
280	RandomAccessIt word_shift_left(RandomAccessIt first,	1,032✔
281	RandomAccessIt last,
282	typename RandomAccessIt::difference_type n
283	)
284	{	1,032✔
285	if (n <= 0) return last;	2,064✔
286	if (n >= distance(first, last)) return first;	2,049✔
287	RandomAccessIt mid = first + n;	1,372✔
288	auto ret = std::move(mid, last, first);	1,372✔
289	return ret;	1,372✔
290	}	1,020✔
291
292
293	// Shifts the range [first, right) to the left by n, filling the empty
294	// bits with 0
295	// NOT OPTIMIZED. Will be replaced with std::shift eventually.
296	template <class RandomAccessIt>
297	RandomAccessIt word_shift_right(RandomAccessIt first,	1,032✔
298	RandomAccessIt last,
299	typename RandomAccessIt::difference_type n
300	)
301	{	1,032✔
302	auto d = distance(first, last);	2,064✔
303	if (n <= 0) return first;	2,064✔
304	if (n >= d) return last;	1,991✔
305	std::move_backward(first, last-n, last);	1,328✔
306	return std::next(first, n);	1,328✔
307	}	999✔
308
309	// returns a word consisting of all one bits
UNCOV 310	constexpr auto _all_ones() {
UNCOV 311	return -1;
UNCOV 312	}
313
314	// returns a word consisting of all zero bits
UNCOV 315	constexpr auto _all_zeros() {
UNCOV 316	return 0;
UNCOV 317	}
318
319	// checks that the passed iterator points to the first bit of a word
320	template <class It>
321	bool _is_aligned_lsb(bit_iterator<It> iter) {
322	return iter.position() == 0;
323	}
324
325	// checks that maybe_end is one position past the last bit of base
326	template <class ForwardIt>
327	bool _is_one_past_last_bit(bit_iterator<ForwardIt> maybe_end,
328	ForwardIt base) {
329	return maybe_end.position() == 0 && std::next(base) == maybe_end.base();
330	}
331
332	// checks that two bit iterators point to the same word
333	template <class It>
334	constexpr bool _in_same_word(bit_iterator<It> lhs, bit_iterator<It> rhs) {
335	return lhs.base() == rhs.base();
336	}
337
338	// simple alias for right shift
339	template <class WordType>
340	WordType _shift_towards_lsb(WordType word, std::size_t n) {
341	return word >> n;
342	}
343
344	// simple alias for left shift
345	template <class WordType>
346	WordType _shift_towards_msb(WordType word, std::size_t n) {
347	return word << n;
348	}
349
350	/* Used to read partial/full words and pad any missing digits. Will not
351	* read outside of the word pointed to by the first iterator (see case 4)
352	*
353	* Case 0: 01011101
354	* L F
355	* Case 1: 01011101 -> padded with 0s -> 00001101
356	* L F
357	* Case 2: 01011101 -> padded with 1s -> 01011111
358	* L F
359	* Case 3: 01011101 -> padded with 0s -> 00011100
360	* L F
361	* Case 4: 01011101 11111111 -> treated as 01011101
362	* F L L F
363	*
364	* Note: word is read from [first, last), meaning the element pointed
365	* to by last is not included in the read. if first == last, behavior
366	* is undefined
367	*/
368	template <class It>
369	[[deprecated("Unused")]]
370	typename bit_iterator<It>::word_type _padded_read(bit_iterator<It> first,
371	bit_iterator<It> last, const bit::bit_value bv) {
372	using word_type = typename bit_iterator<It>::word_type;
373
374	constexpr std::size_t num_digits = binary_digits<word_type>::value;
375	const std::size_t first_position = first.position();
376	const std::size_t last_position = last.position();
377	const word_type read = *(first.base());
378	constexpr word_type all_ones = _all_ones();
379
380	word_type mask;
381
382	if (_is_aligned_lsb(first)) {
383	if (_in_same_word(first, last)) {
384	// Case 1
385	if (bv == bit0) {
386	mask = _shift_towards_lsb(all_ones, num_digits - last_position);
387	return read & mask;
388	} else {
389	mask = _shift_towards_msb(all_ones, last_position);
390	return read \| mask;
391	}
392	} else {
393	// Case 0
394	return read;
395	}
396	} else {
397	if (!_in_same_word(first, last)) {
398	// Case 2
399	if (bv == bit0) {
400	mask = _shift_towards_msb(all_ones, first_position);
401	return read & mask;
402	} else {
403	mask = _shift_towards_lsb(all_ones, num_digits - first_position);
404	return read \| mask;
405	}
406	} else {
407	// Case 3
408	if (bv == bit0) {
409	mask = _shift_towards_msb(all_ones, first_position);
410	mask &= _shift_towards_lsb(all_ones, num_digits - last_position);
411	return read & mask;
412	} else {
413	mask = _shift_towards_lsb(all_ones, num_digits - first_position);
414	mask \|= _shift_towards_msb(all_ones, last_position);
415	return read \| mask;
416	}
417	}
418	}
419	}
420	// -------------------------------------------------------------------------- //
421
422
423
424	// ========================================================================== //
425	} // namespace bit
426	#endif // _BIT_ALGORITHM_DETAILS_HPP_INCLUDED
427	// ========================================================================== //

PeterCDMcLean / BitLib / 15696616722

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