15231925347

Committed 24 May 2025 11:21PM UTC coverage: 52.363% (+2.5%) from 49.894%

Build # 15231925347

Build Type

push

github

Committed by

web-flow

Commit Message

Add support for signed word types. (#14)

* Add support for signed word types.
Use logical shift right and avoid signed multiplication.
Someone builtin_popcount is also sensitive to sign

* Use common mask function to avoid signed word underflows

* Allow _mask to optimize by default

Run Details

8602 of 16014 branches covered (53.72%)

Branch coverage included in aggregate %.

216 of 264 new or added lines in 12 files covered. (81.82%)

4 existing lines in 1 file now uncovered.

5323 of 10579 relevant lines covered (50.32%)

5579260.68 hits per line

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

85.4

/include/bitlib/bit-algorithms/rotate.hpp

// ================================= ROTATE ================================= //
// Project:         The Experimental Bit Algorithms Library
// Name:            rotate.hpp
// Description:     bit_iterator overloads for std::rotate
// Contributor(s):  Bryce Kille [2019]
// License:         BSD 3-Clause License
// ========================================================================== //
#ifndef _ROTATE_HPP_INCLUDED
#define _ROTATE_HPP_INCLUDED
// ========================================================================== //



// ============================== PREAMBLE ================================== //
// C++ standard library
#include <iostream>
// Project sources
#include "bit_algorithm.hpp"
// Third-party libraries
// Miscellaneous
namespace bit {
// ========================================================================== //

// Rotates a range by copying [first...n_first) to the stack, then shifting
// the range to the left and appending the copied section to the end.
//
// Note: distance(first, n_first) <= 3*digits
template <class ForwardIt, int BufferSize>
bit_iterator<ForwardIt> _rotate_via_copy_begin(
   bit_iterator<ForwardIt> first,
   bit_iterator<ForwardIt> n_first,
   bit_iterator<ForwardIt> last
) {
    // Types and constants
    using word_type = typename bit_iterator<ForwardIt>::word_type;
    using size_type = typename bit_iterator<ForwardIt>::size_type;
    constexpr size_type digits = binary_digits<word_type>::value;

    size_type k = distance(first, n_first);
    assert(k <= BufferSize*digits);
    word_type copy_arr[BufferSize];
    copy_arr[0] = *first.base();
    ForwardIt it = ++first.base();
    short unsigned int pos = 1;
    short int bits_left_to_copy = k - (digits - first.position());
    while (bits_left_to_copy > 0) {
        copy_arr[pos++] = *it++;
        bits_left_to_copy -= digits;
    }
    bit_iterator<ForwardIt> ret = shift_left(first, last, k);
    copy(
        bit_iterator<word_type*>(copy_arr, first.position()),
        bit_iterator<word_type*>(
                copy_arr,
                first.position()
        ) + k,
        ret
    );
    return ret;
}

// Rotates a range by copying [n_first, last) to the stack, then shifting
// the range to the right and prepending the copied section to the beginning.
//
// Note: distance(n_first, last) <= 3*digits
template <class ForwardIt, int BufferSize>
bit_iterator<ForwardIt> _rotate_via_copy_end(
   bit_iterator<ForwardIt> first,
   bit_iterator<ForwardIt> n_first,
   bit_iterator<ForwardIt> last
) {
    // Types and constants
    using word_type = typename bit_iterator<ForwardIt>::word_type;
    using size_type = typename bit_iterator<ForwardIt>::size_type;
    constexpr size_type digits = binary_digits<word_type>::value;

    size_type k = distance(n_first, last);
    assert(k <= BufferSize*digits);
    word_type copy_arr[BufferSize];
    copy_arr[0] = *n_first.base();
    ForwardIt it = ++n_first.base();
    short unsigned int pos = 1;
    short int bits_left_to_copy = k - (digits - n_first.position());
    while (bits_left_to_copy > 0) {
        copy_arr[pos++] = *it++;
        bits_left_to_copy -= digits;
    }
    bit_iterator<ForwardIt> ret = shift_right(first, last, k);
    copy(
        bit_iterator<word_type*>(copy_arr, n_first.position()),
        bit_iterator<word_type*>(
                copy_arr,
                n_first.position()
        ) + k,
        first
    );
    return ret;
}

// Rotates a range using random-access iterators. Algorithm logic from the GCC
// implementation
template <class RandomAccessIt>
bit_iterator<RandomAccessIt> _rotate_via_raw(
   bit_iterator<RandomAccessIt> first,
   bit_iterator<RandomAccessIt> n_first,
   bit_iterator<RandomAccessIt> last,
   std::random_access_iterator_tag
) {
    // Types and constants
    using word_type = typename bit_iterator<RandomAccessIt>::word_type;
    using size_type = typename bit_iterator<RandomAccessIt>::size_type;
    using difference_type =
        typename bit_iterator<RandomAccessIt>::difference_type;
    constexpr difference_type digits = binary_digits<word_type>::value;

    difference_type k = n_first - first;
    difference_type n = last - first;

    if (k == n - k) {
        swap_ranges(first, n_first, n_first);
        return n_first;
    }

    bit_iterator<RandomAccessIt> p = first;
    bit_iterator<RandomAccessIt> ret = first + (last - n_first);

    for (;;) {
        if (k < n - k) {
            if (k <= digits) {
                // BENCHMARK NOTE: may be better to do k <= 3*digits and use
                // the _rotate_via_copy method.
                word_type temp_word = get_word<word_type>(p, k);
                bit_iterator<RandomAccessIt> temp_it = shift_left(p, p + n, k);
                write_word<word_type>(temp_word, temp_it, k);
                return ret;
            }
            bit_iterator<RandomAccessIt> q = p + k;
            unsigned int full_swaps = (n - k) / k;
            size_type remainder = (n - k) - full_swaps*k;
            while (full_swaps > 0) {
                swap_ranges(p, q, q);
                p += k;
                q += k;
                --full_swaps;
            }
            swap_ranges(p, p + remainder, q);
            p += remainder;
            q += remainder;
            n %= k;
            if (n == 0)
                return ret;
            std::swap(n, k);
            k = n - k;
        } else {
            k = n - k;
            if (k <= digits) {
                word_type temp_word = get_word<word_type>(p + n - k, k);
                shift_right(p, p + n, k);
                write_word<word_type>(temp_word, p, k);
                return ret;
            }
            bit_iterator<RandomAccessIt> q = p + n;
            p = q - k;
            unsigned int full_swaps = (n - k) / k;
            size_type remainder = (n - k) - full_swaps*k;
            while (full_swaps > 0) {
                p -= k;
                q -= k;
                swap_ranges(p, q, q);
                --full_swaps;
            }
            p -= remainder;
            q -= remainder;
            swap_ranges(p, p + remainder, q);
            n %= k;
            if (n == 0)
                return ret;
            std::swap(n, k);
        }
    }
}

// Main function for implementing the bit overload of std::rotate.
template <class ForwardIt>
bit_iterator<ForwardIt> rotate(
   bit_iterator<ForwardIt> first,
   bit_iterator<ForwardIt> n_first,
   bit_iterator<ForwardIt> last
) {
    // Assertions
    _assert_range_viability(first, n_first);
    _assert_range_viability(n_first, last);
    _assert_range_viability(first, last);
    //if (first == n_first) return n_first;
    if (first == n_first) return last;

    // Types and constants
    using word_type = typename bit_iterator<ForwardIt>::word_type;
    using size_type = typename bit_iterator<ForwardIt>::size_type;
    using difference_type =
        typename bit_iterator<ForwardIt>::difference_type;
    constexpr difference_type digits = binary_digits<word_type>::value;

    // Initialization
    const bool is_first_aligned = first.position() == 0;
    const bool is_last_aligned = last.position() == 0;

    // Within the same word
    if (std::next(first.base(), is_last_aligned) == last.base()) {
        if (is_first_aligned && is_last_aligned) {
          *first.base() =
              (lsr(*first.base(), n_first.position())) |
              static_cast<word_type>(
                  *first.base() << (digits - n_first.position()));
          return std::next(first, digits - n_first.position());
        } else {
            size_type last_pos = is_last_aligned ? digits : last.position();
            size_type k = n_first.position() - first.position();
            size_type p = last_pos - n_first.position();
            size_type d = last_pos - first.position();

            word_type mask = _mask<word_type>(d) << first.position();
            word_type rotated = *first.base() & mask;
            rotated = static_cast<word_type>(lsr(rotated, k)) | static_cast<word_type>(rotated << p);
            *first.base() = _bitblend<word_type>(
                *first.base(),
                rotated,
                first.position(),
                d
            );
            return std::next(first, p);
        }
    }

    // Single word subcases
    if (is_within<digits>(first, n_first)) {
        size_type k = distance(first, n_first);
        word_type temp = get_word<word_type>(first, k);
        bit_iterator<ForwardIt> new_last = shift_left(first, last, k);
        write_word<word_type>(temp, new_last, static_cast<word_type>(k));
        return new_last;
    } else if (is_within<digits>(n_first, last)) {
        size_type p = distance(n_first, last);
        word_type temp = get_word<word_type>(n_first, p);
        auto new_last = shift_right(first, last, p);
        write_word(temp, first, static_cast<word_type>(p));
        return new_last;
    }
    return _rotate_via_raw(
            first,
            n_first,
            last,
            typename std::iterator_traits<ForwardIt>::iterator_category()
    );
}


// ========================================================================== //
} // namespace bit
#endif // _ROTATE_HPP_INCLUDED
// ========================================================================== //

1	// ================================= ROTATE ================================= //
2	// Project: The Experimental Bit Algorithms Library
3	// Name: rotate.hpp
4	// Description: bit_iterator overloads for std::rotate
5	// Contributor(s): Bryce Kille [2019]
6	// License: BSD 3-Clause License
7	// ========================================================================== //
8	#ifndef _ROTATE_HPP_INCLUDED
9	#define _ROTATE_HPP_INCLUDED
10	// ========================================================================== //
11
12
13
14	// ============================== PREAMBLE ================================== //
15	// C++ standard library
16	#include <iostream>
17	// Project sources
18	#include "bit_algorithm.hpp"
19	// Third-party libraries
20	// Miscellaneous
21	namespace bit {
22	// ========================================================================== //
23
24	// Rotates a range by copying [first...n_first) to the stack, then shifting
25	// the range to the left and appending the copied section to the end.
26	//
27	// Note: distance(first, n_first) <= 3*digits
28	template <class ForwardIt, int BufferSize>
29	bit_iterator<ForwardIt> _rotate_via_copy_begin(
30	bit_iterator<ForwardIt> first,
31	bit_iterator<ForwardIt> n_first,
32	bit_iterator<ForwardIt> last
33	) {
34	// Types and constants
35	using word_type = typename bit_iterator<ForwardIt>::word_type;
36	using size_type = typename bit_iterator<ForwardIt>::size_type;
37	constexpr size_type digits = binary_digits<word_type>::value;
38
39	size_type k = distance(first, n_first);
40	assert(k <= BufferSize*digits);
41	word_type copy_arr[BufferSize];
42	copy_arr[0] = *first.base();
43	ForwardIt it = ++first.base();
44	short unsigned int pos = 1;
45	short int bits_left_to_copy = k - (digits - first.position());
46	while (bits_left_to_copy > 0) {
47	copy_arr[pos++] = *it++;
48	bits_left_to_copy -= digits;
49	}
50	bit_iterator<ForwardIt> ret = shift_left(first, last, k);
51	copy(
52	bit_iterator<word_type*>(copy_arr, first.position()),
53	bit_iterator<word_type*>(
54	copy_arr,
55	first.position()
56	) + k,
57	ret
58	);
59	return ret;
60	}
61
62	// Rotates a range by copying [n_first, last) to the stack, then shifting
63	// the range to the right and prepending the copied section to the beginning.
64	//
65	// Note: distance(n_first, last) <= 3*digits
66	template <class ForwardIt, int BufferSize>
67	bit_iterator<ForwardIt> _rotate_via_copy_end(
68	bit_iterator<ForwardIt> first,
69	bit_iterator<ForwardIt> n_first,
70	bit_iterator<ForwardIt> last
71	) {
72	// Types and constants
73	using word_type = typename bit_iterator<ForwardIt>::word_type;
74	using size_type = typename bit_iterator<ForwardIt>::size_type;
75	constexpr size_type digits = binary_digits<word_type>::value;
76
77	size_type k = distance(n_first, last);
78	assert(k <= BufferSize*digits);
79	word_type copy_arr[BufferSize];
80	copy_arr[0] = *n_first.base();
81	ForwardIt it = ++n_first.base();
82	short unsigned int pos = 1;
83	short int bits_left_to_copy = k - (digits - n_first.position());
84	while (bits_left_to_copy > 0) {
85	copy_arr[pos++] = *it++;
86	bits_left_to_copy -= digits;
87	}
88	bit_iterator<ForwardIt> ret = shift_right(first, last, k);
89	copy(
90	bit_iterator<word_type*>(copy_arr, n_first.position()),
91	bit_iterator<word_type*>(
92	copy_arr,
93	n_first.position()
94	) + k,
95	first
96	);
97	return ret;
98	}
99
100	// Rotates a range using random-access iterators. Algorithm logic from the GCC
101	// implementation
102	template <class RandomAccessIt>
103	bit_iterator<RandomAccessIt> _rotate_via_raw(
104	bit_iterator<RandomAccessIt> first,
105	bit_iterator<RandomAccessIt> n_first,
106	bit_iterator<RandomAccessIt> last,
107	std::random_access_iterator_tag
108	) {	2,448✔
109	// Types and constants
110	using word_type = typename bit_iterator<RandomAccessIt>::word_type;	2,448✔
111	using size_type = typename bit_iterator<RandomAccessIt>::size_type;	2,448✔
112	using difference_type =	2,448✔
113	typename bit_iterator<RandomAccessIt>::difference_type;	2,448✔
114	constexpr difference_type digits = binary_digits<word_type>::value;	2,448✔
115
116	difference_type k = n_first - first;	2,448✔
117	difference_type n = last - first;	2,448✔
118
119	if (k == n - k) {	2,448!
120	swap_ranges(first, n_first, n_first);	16✔
121	return n_first;	16✔
122	}	16✔
123
124	bit_iterator<RandomAccessIt> p = first;	2,432✔
125	bit_iterator<RandomAccessIt> ret = first + (last - n_first);	2,432✔
126
127	for (;;) {	9,728✔
128	if (k < n - k) {	9,728✔
129	if (k <= digits) {	4,096✔
130	// BENCHMARK NOTE: may be better to do k <= 3*digits and use
131	// the _rotate_via_copy method.
132	word_type temp_word = get_word<word_type>(p, k);	1,328✔
133	bit_iterator<RandomAccessIt> temp_it = shift_left(p, p + n, k);	1,328✔
134	write_word<word_type>(temp_word, temp_it, k);	1,328✔
135	return ret;	1,328✔
136	}	1,328✔
137	bit_iterator<RandomAccessIt> q = p + k;	2,768✔
138	unsigned int full_swaps = (n - k) / k;	2,768✔
139	size_type remainder = (n - k) - full_swaps*k;	2,768✔
140	while (full_swaps > 0) {	15,712✔
141	swap_ranges(p, q, q);	12,944✔
142	p += k;	12,944✔
143	q += k;	12,944✔
144	--full_swaps;	12,944✔
145	}	12,944✔
146	swap_ranges(p, p + remainder, q);	2,768✔
147	p += remainder;	2,768✔
148	q += remainder;	2,768✔
149	n %= k;	2,768✔
150	if (n == 0)	2,768!
151	return ret;	×
152	std::swap(n, k);	2,768✔
153	k = n - k;	2,768✔
154	} else {	5,632✔
155	k = n - k;	5,632✔
156	if (k <= digits) {	5,632✔
157	word_type temp_word = get_word<word_type>(p + n - k, k);	1,040✔
158	shift_right(p, p + n, k);	1,040✔
159	write_word<word_type>(temp_word, p, k);	1,040✔
160	return ret;	1,040✔
161	}	1,040✔
162	bit_iterator<RandomAccessIt> q = p + n;	4,592✔
163	p = q - k;	4,592✔
164	unsigned int full_swaps = (n - k) / k;	4,592✔
165	size_type remainder = (n - k) - full_swaps*k;	4,592✔
166	while (full_swaps > 0) {	35,392✔
167	p -= k;	30,800✔
168	q -= k;	30,800✔
169	swap_ranges(p, q, q);	30,800✔
170	--full_swaps;	30,800✔
171	}	30,800✔
172	p -= remainder;	4,592✔
173	q -= remainder;	4,592✔
174	swap_ranges(p, p + remainder, q);	4,592✔
175	n %= k;	4,592✔
176	if (n == 0)	4,592!
177	return ret;	64✔
178	std::swap(n, k);	4,528✔
179	}	4,528✔
180	}	9,728✔
181	}	2,432✔
182
183	// Main function for implementing the bit overload of std::rotate.
184	template <class ForwardIt>
185	bit_iterator<ForwardIt> rotate(
186	bit_iterator<ForwardIt> first,
187	bit_iterator<ForwardIt> n_first,
188	bit_iterator<ForwardIt> last
189	) {	16,512✔
190	// Assertions
191	_assert_range_viability(first, n_first);	16,512✔
192	_assert_range_viability(n_first, last);	16,512✔
193	_assert_range_viability(first, last);	16,512✔
194	//if (first == n_first) return n_first;
195	if (first == n_first) return last;	16,512✔
196
197	// Types and constants
198	using word_type = typename bit_iterator<ForwardIt>::word_type;	15,392✔
199	using size_type = typename bit_iterator<ForwardIt>::size_type;	15,392✔
200	using difference_type =	15,392✔
201	typename bit_iterator<ForwardIt>::difference_type;	15,392✔
202	constexpr difference_type digits = binary_digits<word_type>::value;	15,392✔
203
204	// Initialization
205	const bool is_first_aligned = first.position() == 0;	15,392✔
206	const bool is_last_aligned = last.position() == 0;	15,392✔
207
208	// Within the same word
209	if (std::next(first.base(), is_last_aligned) == last.base()) {	15,392✔
210	if (is_first_aligned && is_last_aligned) {	2,960!
NEW 211	*first.base() =	×
NEW 212	(lsr(*first.base(), n_first.position())) \|	×
NEW 213	static_cast<word_type>(	×
NEW 214	*first.base() << (digits - n_first.position()));	×
NEW 215	return std::next(first, digits - n_first.position());	×
216	} else {	2,960✔
217	size_type last_pos = is_last_aligned ? digits : last.position();	2,960!
218	size_type k = n_first.position() - first.position();	2,960✔
219	size_type p = last_pos - n_first.position();	2,960✔
220	size_type d = last_pos - first.position();	2,960✔
221
222	word_type mask = _mask<word_type>(d) << first.position();	2,960✔
223	word_type rotated = *first.base() & mask;	2,960✔
224	rotated = static_cast<word_type>(lsr(rotated, k)) \| static_cast<word_type>(rotated << p);	2,960✔
225	*first.base() = _bitblend<word_type>(	2,960✔
226	*first.base(),	2,960✔
227	rotated,	2,960✔
228	first.position(),	2,960✔
229	d	2,960✔
230	);	2,960✔
231	return std::next(first, p);	2,960✔
232	}	2,960✔
233	}	2,960✔
234
235	// Single word subcases
236	if (is_within<digits>(first, n_first)) {	12,432!
237	size_type k = distance(first, n_first);	7,008✔
238	word_type temp = get_word<word_type>(first, k);	7,008✔
239	bit_iterator<ForwardIt> new_last = shift_left(first, last, k);	7,008✔
240	write_word<word_type>(temp, new_last, static_cast<word_type>(k));	7,008✔
241	return new_last;	7,008✔
242	} else if (is_within<digits>(n_first, last)) {	7,008!
243	size_type p = distance(n_first, last);	2,976✔
244	word_type temp = get_word<word_type>(n_first, p);	2,976✔
245	auto new_last = shift_right(first, last, p);	2,976✔
246	write_word(temp, first, static_cast<word_type>(p));	2,976✔
247	return new_last;	2,976✔
248	}	2,976✔
249	return _rotate_via_raw(	2,448✔
250	first,	2,448✔
251	n_first,	2,448✔
252	last,	2,448✔
253	typename std::iterator_traits<ForwardIt>::iterator_category()	2,448✔
254	);	2,448✔
255	}	12,432✔
256
257
258	// ========================================================================== //
259	} // namespace bit
260	#endif // _ROTATE_HPP_INCLUDED
261	// ========================================================================== //

PeterCDMcLean / BitLib / 15231925347

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