| 36 | namespace internal { |
| 37 | |
| 38 | int64_t CountSetBits(const uint8_t* data, int64_t bit_offset, int64_t length) { |
| 39 | constexpr int64_t pop_len = sizeof(uint64_t) * 8; |
| 40 | DCHECK_GE(bit_offset, 0); |
| 41 | int64_t count = 0; |
| 42 | |
| 43 | const auto p = BitmapWordAlign<pop_len / 8>(data, bit_offset, length); |
| 44 | for (int64_t i = bit_offset; i < bit_offset + p.leading_bits; ++i) { |
| 45 | if (bit_util::GetBit(data, i)) { |
| 46 | ++count; |
| 47 | } |
| 48 | } |
| 49 | |
| 50 | if (p.aligned_words > 0) { |
| 51 | // popcount as much as possible with the widest possible count |
| 52 | const uint64_t* u64_data = reinterpret_cast<const uint64_t*>(p.aligned_start); |
| 53 | DCHECK_EQ(reinterpret_cast<size_t>(u64_data) & 7, 0); |
| 54 | const uint64_t* end = u64_data + p.aligned_words; |
| 55 | |
| 56 | constexpr int64_t kCountUnrollFactor = 4; |
| 57 | const int64_t words_rounded = |
| 58 | bit_util::RoundDown(p.aligned_words, kCountUnrollFactor); |
| 59 | std::array<int64_t, kCountUnrollFactor> count_unroll{}; |
| 60 | |
| 61 | // Unroll the loop for better performance |
| 62 | for (int64_t i = 0; i < words_rounded; i += kCountUnrollFactor) { |
| 63 | // (hand-unrolled as some gcc versions would unnest a nested `for` loop) |
| 64 | count_unroll[0] += std::popcount(u64_data[0]); |
| 65 | count_unroll[1] += std::popcount(u64_data[1]); |
| 66 | count_unroll[2] += std::popcount(u64_data[2]); |
| 67 | count_unroll[3] += std::popcount(u64_data[3]); |
| 68 | u64_data += kCountUnrollFactor; |
| 69 | } |
| 70 | for (int64_t k = 0; k < kCountUnrollFactor; k++) { |
| 71 | count += count_unroll[k]; |
| 72 | } |
| 73 | |
| 74 | // The trailing part |
| 75 | for (; u64_data < end; ++u64_data) { |
| 76 | count += std::popcount(*u64_data); |
| 77 | } |
| 78 | } |
| 79 | |
| 80 | // Account for left over bits (in theory we could fall back to smaller |
| 81 | // versions of popcount but the code complexity is likely not worth it) |
| 82 | for (int64_t i = p.trailing_bit_offset; i < bit_offset + length; ++i) { |
| 83 | if (bit_util::GetBit(data, i)) { |
| 84 | ++count; |
| 85 | } |
| 86 | } |
| 87 | |
| 88 | return count; |
| 89 | } |
| 90 | |
| 91 | int64_t CountAndSetBits(const uint8_t* left_bitmap, int64_t left_offset, |
| 92 | const uint8_t* right_bitmap, int64_t right_offset, |