| 285 | BitBlockCount NextOrNotWord() { return NextWord<detail::BitBlockOrNot>(); } |
| 286 | |
| 287 | private: |
| 288 | template <class Op> |
| 289 | BitBlockCount NextWord() { |
| 290 | using detail::LoadWord; |
| 291 | using detail::ShiftWord; |
| 292 | |
| 293 | if (!bits_remaining_) { |
| 294 | return {0, 0}; |
| 295 | } |
| 296 | // When the offset is > 0, we need there to be a word beyond the last aligned |
| 297 | // word in the bitmap for the bit shifting logic. |
| 298 | constexpr int64_t kWordBits = BitBlockCounter::kWordBits; |
| 299 | const int64_t bits_required_to_use_words = |
| 300 | std::max(left_offset_ == 0 ? 64 : 64 + (64 - left_offset_), |
| 301 | right_offset_ == 0 ? 64 : 64 + (64 - right_offset_)); |
| 302 | if (bits_remaining_ < bits_required_to_use_words) { |
| 303 | const int16_t run_length = |
| 304 | static_cast<int16_t>(std::min(bits_remaining_, kWordBits)); |
| 305 | int16_t popcount = 0; |
| 306 | for (int64_t i = 0; i < run_length; ++i) { |
| 307 | if (Op::Call(bit_util::GetBit(left_bitmap_, left_offset_ + i), |
| 308 | bit_util::GetBit(right_bitmap_, right_offset_ + i))) { |
| 309 | ++popcount; |
| 310 | } |
| 311 | } |
| 312 | // This code path should trigger _at most_ 2 times. In the "two times" |
| 313 | // case, the first time the run length will be a multiple of 8. |
| 314 | left_bitmap_ += run_length / 8; |
| 315 | right_bitmap_ += run_length / 8; |
| 316 | bits_remaining_ -= run_length; |
| 317 | return {run_length, popcount}; |
| 318 | } |
| 319 | |
| 320 | int64_t popcount = 0; |
| 321 | if (left_offset_ == 0 && right_offset_ == 0) { |
| 322 | popcount = std::popcount(Op::Call(LoadWord(left_bitmap_), LoadWord(right_bitmap_))); |
| 323 | } else { |
| 324 | auto left_word = |
| 325 | ShiftWord(LoadWord(left_bitmap_), LoadWord(left_bitmap_ + 8), left_offset_); |
| 326 | auto right_word = |
| 327 | ShiftWord(LoadWord(right_bitmap_), LoadWord(right_bitmap_ + 8), right_offset_); |
| 328 | popcount = std::popcount(Op::Call(left_word, right_word)); |
| 329 | } |
| 330 | left_bitmap_ += kWordBits / 8; |
| 331 | right_bitmap_ += kWordBits / 8; |
| 332 | bits_remaining_ -= kWordBits; |
| 333 | return {64, static_cast<int16_t>(popcount)}; |
| 334 | } |
| 335 | |
| 336 | const uint8_t* left_bitmap_; |
| 337 | int64_t left_offset_; |