| // Copyright 2022 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "third_party/iwlwifi/platform/compiler.h" |
| |
| #define BITARR_TYPE_NUM_BITS (sizeof(uint64_t) * 8) |
| |
| // Find the first asserted LSB(assume the input is little-endian). |
| // |
| // Returns: |
| // [0, num_bits): found. The index of first asserted bit (the least significant one). |
| // num_bits: No asserted bit found in num_bits. |
| // |
| size_t find_first_bit(unsigned int* bits, const size_t num_bits) { |
| const size_t num_of_ints = DIV_ROUND_UP(num_bits, BITS_PER_INT); |
| size_t ret = num_bits; |
| |
| for (size_t i = 0; i < num_of_ints; ++i) { |
| if (bits[i] == 0) { |
| continue; |
| } |
| ret = (i * BITS_PER_INT) + __builtin_ctz(bits[i]); |
| break; |
| } |
| |
| return MIN(num_bits, ret); |
| } |
| |
| // Find the last asserted MSB(assume the input is little-endian). |
| // |
| // Returns: |
| // [0, num_bits): found. The index of last asserted bit (the most significant one). |
| // num_bits: No asserted bit found in num_bits. |
| // |
| size_t find_last_bit(unsigned int* bits, const size_t num_bits) { |
| const size_t num_of_ints = DIV_ROUND_UP(num_bits, BITS_PER_INT); |
| const size_t size_inside_int = (num_bits - 1) % BITS_PER_INT + 1; |
| unsigned int mask = |
| size_inside_int == BITS_PER_INT ? ~0U : (unsigned int)(1 << size_inside_int) - 1; |
| |
| size_t ret = num_bits; |
| for (int64_t i = (int64_t)(num_of_ints - 1); i >= 0; --i) { |
| if (bits[i] == 0) { |
| continue; |
| } |
| unsigned int val = mask & bits[i]; |
| |
| if (val == 0) { |
| continue; |
| } |
| ret = (i * BITS_PER_INT) + (BITS_PER_INT - 1 - __builtin_clz(val)); |
| break; |
| } |
| |
| return MIN(num_bits, ret); |
| } |
| |
| // Find next bit which is set in an unsigned integer. |
| // |
| // Returns: |
| // [0, num_bits): found. The index of next bit which is set to 1 starts from bit_offset. |
| // num_bits: No asserted bit found in num_bits. |
| // |
| size_t find_next_bit(unsigned int* bitarr, size_t num_bits, size_t bit_offset) { |
| if (bit_offset >= num_bits) { |
| return num_bits; |
| } |
| |
| size_t word_offset = bit_offset / BITARR_TYPE_NUM_BITS; |
| size_t offset_within_word = bit_offset % BITARR_TYPE_NUM_BITS; |
| |
| size_t rest = bitarr[word_offset] & (~0ULL << offset_within_word); |
| if (rest != 0) { |
| int bit = __builtin_ffsll(rest) - 1; |
| return MIN(word_offset * BITARR_TYPE_NUM_BITS + bit, num_bits); |
| } |
| |
| size_t skipped_bits = (word_offset + 1) * BITARR_TYPE_NUM_BITS; |
| if (skipped_bits >= num_bits) { |
| return num_bits; |
| } |
| |
| return skipped_bits + find_first_bit(bitarr + word_offset + 1, num_bits - skipped_bits); |
| } |