15658406666

Committed 15 Jun 2025 02:12AM UTC coverage: 96.002% (+42.5%) from 53.519%

Build # 15658406666

Build Type

Pull #17

github

Committed by

web-flow

Commit Message

Merge 5e911f3b7 into 0f0b787a1

Pull Request Pull Request #17: Truncation policy

Run Details

122 of 148 new or added lines in 9 files covered. (82.43%)

4 existing lines in 3 files now uncovered.

1561 of 1626 relevant lines covered (96.0%)

20765048.89 hits per line

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

86.67

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

// ================================= COUNT ================================== //
// Project: The Experimental Bit Algorithms Library
// Description: bit_iterator overloads for std::count, std::count_if
// License: BSD 3-Clause License
// ========================================================================== //
#ifndef _COUNT_HPP_INCLUDED
#define _COUNT_HPP_INCLUDED
// ========================================================================== //

// ============================== PREAMBLE ================================== //
// C++ standard library
#include <iterator>
#include <numeric>
// Project sources
#include "bitlib/bit-algorithms/accumulate.hpp"
#include "bitlib/bit-algorithms/libpopcnt.h"
#include "bitlib/bit-iterator/bit.hpp"
// Third-party libraries
#ifdef BITLIB_HWY
#include "hwy/highway.h"
HWY_BEFORE_NAMESPACE();
#endif
// Miscellaneous

#define is_aligned(POINTER, BYTE_COUNT) \
    (((uintptr_t)(const void *)(POINTER)) % (BYTE_COUNT) == 0)

namespace bit {

#ifdef BITLIB_HWY
namespace hn = hwy::HWY_NAMESPACE;
#endif
// ========================================================================== //

template<class RandomAccessIt>
constexpr typename bit_iterator<RandomAccessIt>::difference_type
count(
    bit_iterator <RandomAccessIt> first,
    bit_iterator <RandomAccessIt> last,
    bit_value value
) {
    // Assertions
    _assert_range_viability(first, last);

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

    // Initialization
    difference_type result = 0;

    // Computation when bits belong to several underlying words
    if (first.base() != last.base()) {
      iterator_type it = first.base();

      if (first.position() != 0) {
        word_type first_value = lsr(*first.base(), first.position());
        result = _popcnt(first_value);
        ++it;
      }
// The SIMD implementation here is actually slower than the standard
//#ifdef BITLIB_HWY
        //// ReduceSum not implemented for unsigned char
        //if constexpr (digits > 8)
        //{
            //// Align to boundary
            //for (; it != last.base() && !is_aligned(&(*it), 64); ++it) {
                //result += _popcnt(*it);
            //}

            //// SIMD
            //hn::ScalableTag<word_type> d;
            //for (; std::distance(it, last.base()) >= hn::Lanes(d); it += hn::Lanes(d))
            //{
                //const auto popcntV = hn::PopulationCount(hn::Load(d, &*it));
                //result += hn::ReduceSum(d, popcntV);
            //}

            //// Remaining
            //for (; it != last.base(); ++it) {
                //result += _popcnt(*it);
            //}
        //} else
//#endif
        {
            // std:: version
            //result += std::transform_reduce(
                    //it,
                    //last.base(),
                    //0,
                    //std::plus{},
                    //[](word_type word) {return _popcnt(word); }
            //);

            // libpopcnt
            result += popcnt(&*it, (digits / 8) * std::distance(it, last.base()));
        }
        if (last.position() != 0) {
            word_type last_value = *last.base() << (digits - last.position());
            result += _popcnt(last_value);
        }
    // Computation when bits belong to the same underlying word
    } else {
        result = _popcnt(
            _bextr<word_type>(*first.base(), first.position(), last.position()
              - first.position())
        );
    }

    // Negates when the number of zero bits is requested
    if (!static_cast<bool>(value)) {
        result = std::distance(first, last) - result;
    }

    // Finalization
    return result;
}

template <class RandomAccessIt>
constexpr int count_msb(
    bit_iterator<RandomAccessIt> first,
    bit_iterator<RandomAccessIt> last,
    bit_value value) {
  if (value) {
    return bit::accumulate_backward_while(
        first, last, 0,
        [](int acc, auto word) { return std::make_pair((word == 0), acc + std::countl_one(word)); },
        [](int acc, auto word, auto bits) { return std::make_pair((word == 0), acc + std::countl_one(word) - (bit::bitsof(word) - bits)); });
  } else {
    return bit::accumulate_backward_while(
        first, last, 0,
        [](int acc, auto word) { return std::make_pair((word == 0), acc + std::countl_zero(word)); },
        [](int acc, auto word, auto bits) { return std::make_pair((word == 0), acc + std::countl_zero(word) - (bit::bitsof(word) - bits)); });
  }
}

} // namespace bit
#ifdef BITLIB_HWY
HWY_AFTER_NAMESPACE();
#endif

// ========================================================================== //
#endif // _COUNT_HPP_INCLUDED
// ========================================================================== //

1	// ================================= COUNT ================================== //
2	// Project: The Experimental Bit Algorithms Library
3	// Description: bit_iterator overloads for std::count, std::count_if
4	// License: BSD 3-Clause License
5	// ========================================================================== //
6	#ifndef _COUNT_HPP_INCLUDED
7	#define _COUNT_HPP_INCLUDED
8	// ========================================================================== //
9
10	// ============================== PREAMBLE ================================== //
11	// C++ standard library
12	#include <iterator>
13	#include <numeric>
14	// Project sources
15	#include "bitlib/bit-algorithms/accumulate.hpp"
16	#include "bitlib/bit-algorithms/libpopcnt.h"
17	#include "bitlib/bit-iterator/bit.hpp"
18	// Third-party libraries
19	#ifdef BITLIB_HWY
20	#include "hwy/highway.h"
21	HWY_BEFORE_NAMESPACE();
22	#endif
23	// Miscellaneous
24
25	#define is_aligned(POINTER, BYTE_COUNT) \
26	(((uintptr_t)(const void *)(POINTER)) % (BYTE_COUNT) == 0)
27
28	namespace bit {
29
30	#ifdef BITLIB_HWY
31	namespace hn = hwy::HWY_NAMESPACE;
32	#endif
33	// ========================================================================== //
34
35	template<class RandomAccessIt>
36	constexpr typename bit_iterator<RandomAccessIt>::difference_type
37	count(	30,464✔
38	bit_iterator <RandomAccessIt> first,
39	bit_iterator <RandomAccessIt> last,
40	bit_value value
41	) {
42	// Assertions
43	_assert_range_viability(first, last);	30,464✔
44
45	// Types and constants
46	using word_type = typename bit_iterator<RandomAccessIt>::word_type;
47	using difference_type = typename bit_iterator<RandomAccessIt>::difference_type;
48	using iterator_type = typename bit_iterator<RandomAccessIt>::iterator_type;
49	constexpr difference_type digits = binary_digits<word_type>::value;	30,464✔
50
51	// Initialization
52	difference_type result = 0;	30,464✔
53
54	// Computation when bits belong to several underlying words
55	if (first.base() != last.base()) {	30,464✔
56	iterator_type it = first.base();	22,976✔
57
58	if (first.position() != 0) {	22,976✔
59	word_type first_value = lsr(*first.base(), first.position());	22,976✔
60	result = _popcnt(first_value);	22,976✔
61	++it;	22,976✔
62	}
63	// The SIMD implementation here is actually slower than the standard
64	//#ifdef BITLIB_HWY
65	//// ReduceSum not implemented for unsigned char
66	//if constexpr (digits > 8)
67	//{
68	//// Align to boundary
69	//for (; it != last.base() && !is_aligned(&(*it), 64); ++it) {
70	//result += _popcnt(*it);
71	//}
72
73	//// SIMD
74	//hn::ScalableTag<word_type> d;
75	//for (; std::distance(it, last.base()) >= hn::Lanes(d); it += hn::Lanes(d))
76	//{
77	//const auto popcntV = hn::PopulationCount(hn::Load(d, &*it));
78	//result += hn::ReduceSum(d, popcntV);
79	//}
80
81	//// Remaining
82	//for (; it != last.base(); ++it) {
83	//result += _popcnt(*it);
84	//}
85	//} else
86	//#endif
87	{
88	// std:: version
89	//result += std::transform_reduce(
90	//it,
91	//last.base(),
92	//0,
93	//std::plus{},
94	//[](word_type word) {return _popcnt(word); }
95	//);
96
97	// libpopcnt
98	result += popcnt(&it, (digits / 8) std::distance(it, last.base()));	45,952✔
99	}
100	if (last.position() != 0) {	22,976✔
101	word_type last_value = *last.base() << (digits - last.position());	22,208✔
102	result += _popcnt(last_value);	22,208✔
103	}
104	// Computation when bits belong to the same underlying word
105	} else {
106	result = _popcnt(	9,504✔
107	_bextr<word_type>(*first.base(), first.position(), last.position()	22,464✔
108	- first.position())	7,488✔
109	);
110	}
111
112	// Negates when the number of zero bits is requested
113	if (!static_cast<bool>(value)) {	30,464✔
114	result = std::distance(first, last) - result;	30,464✔
115	}
116
117	// Finalization
118	return result;	60,928✔
119	}
120
121	template <class RandomAccessIt>
122	constexpr int count_msb(	4✔
123	bit_iterator<RandomAccessIt> first,
124	bit_iterator<RandomAccessIt> last,
125	bit_value value) {
126	if (value) {	4✔
NEW 127	return bit::accumulate_backward_while(	×
NEW 128	first, last, 0,	×
NEW 129	[](int acc, auto word) { return std::make_pair((word == 0), acc + std::countl_one(word)); },	×
NEW 130	[](int acc, auto word, auto bits) { return std::make_pair((word == 0), acc + std::countl_one(word) - (bit::bitsof(word) - bits)); });	×
131	} else {
132	return bit::accumulate_backward_while(	4✔
133	first, last, 0,	8✔
134	[](int acc, auto word) { return std::make_pair((word == 0), acc + std::countl_zero(word)); },	8✔
135	[](int acc, auto word, auto bits) { return std::make_pair((word == 0), acc + std::countl_zero(word) - (bit::bitsof(word) - bits)); });	6✔
136	}
137	}
138
139	} // namespace bit
140	#ifdef BITLIB_HWY
141	HWY_AFTER_NAMESPACE();
142	#endif
143
144	// ========================================================================== //
145	#endif // _COUNT_HPP_INCLUDED
146	// ========================================================================== //

PeterCDMcLean / BitLib / 15658406666

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