| // Copyright 2016 The Fuchsia Authors |
| // Copyright (c) 2008 Travis Geiselbrecht |
| // |
| // Use of this source code is governed by a MIT-style |
| // license that can be found in the LICENSE file or at |
| // https://opensource.org/licenses/MIT |
| |
| #ifndef ZIRCON_KERNEL_INCLUDE_BITS_H_ |
| #define ZIRCON_KERNEL_INCLUDE_BITS_H_ |
| |
| #include <zircon/compiler.h> |
| |
| #include <arch/ops.h> |
| #include <pow2.h> |
| |
| |
| #define clz(x) __builtin_clz(x) |
| #define ctz(x) __builtin_ctz(x) |
| |
| /* Trick to get a 1 of the right size */ |
| #define _ONE(x) (1 + ((x) - (x))) |
| |
| #define BIT(x, bit) ((x) & (_ONE(x) << (bit))) |
| #define BIT_SHIFT(x, bit) (((x) >> (bit)) & 1) |
| #define BITS(x, high, low) ((x) & (((_ONE(x) << ((high) + 1)) - 1) & ~((_ONE(x) << (low)) - 1))) |
| #define BITS_SHIFT(x, high, low) (((x) >> (low)) & ((_ONE(x) << ((high) - (low) + 1)) - 1)) |
| #define BIT_SET(x, bit) (((x) & (_ONE(x) << (bit))) ? 1 : 0) |
| |
| #define BITMAP_BITS_PER_WORD ((int)(sizeof(unsigned long) * 8)) |
| #define BITMAP_NUM_WORDS(x) (((x) + BITMAP_BITS_PER_WORD - 1) / BITMAP_BITS_PER_WORD) |
| #define BITMAP_WORD(x) ((x) / BITMAP_BITS_PER_WORD) |
| #define BITMAP_BIT_IN_WORD(x) ((x) & (BITMAP_BITS_PER_WORD - 1)) |
| |
| #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITMAP_BITS_PER_WORD)) |
| #define BITMAP_LAST_WORD_MASK(nbits) \ |
| (((nbits) % BITMAP_BITS_PER_WORD) ? (1UL << ((nbits) % BITMAP_BITS_PER_WORD)) - 1 : ~0UL) |
| |
| #define BITMAP_BITS_PER_INT (sizeof(unsigned int) * 8) |
| #define BITMAP_BIT_IN_INT(x) ((x) & (BITMAP_BITS_PER_INT - 1)) |
| #define BITMAP_INT(x) ((x) / BITMAP_BITS_PER_INT) |
| |
| #define BIT_MASK(x) (((x) >= sizeof(unsigned long) * 8) ? (0UL - 1) : ((1UL << (x)) - 1)) |
| |
| static inline void bitmap_set(unsigned long *bitmap, int start, int nr) { |
| unsigned long *p = bitmap + BITMAP_WORD(start); |
| const long size = start + nr; |
| int bits_to_set = BITMAP_BITS_PER_WORD - (start % BITMAP_BITS_PER_WORD); |
| unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); |
| |
| while (nr - bits_to_set >= 0) { |
| *p |= mask_to_set; |
| nr -= bits_to_set; |
| bits_to_set = BITMAP_BITS_PER_WORD; |
| mask_to_set = ~0UL; |
| p++; |
| } |
| if (nr) { |
| mask_to_set &= BITMAP_LAST_WORD_MASK(size); |
| *p |= mask_to_set; |
| } |
| } |
| |
| static inline void bitmap_clear(unsigned long *bitmap, int start, int nr) { |
| unsigned long *p = bitmap + BITMAP_WORD(start); |
| const long size = start + nr; |
| int bits_to_clear = BITMAP_BITS_PER_WORD - (start % BITMAP_BITS_PER_WORD); |
| unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); |
| |
| while (nr - bits_to_clear >= 0) { |
| *p &= ~mask_to_clear; |
| nr -= bits_to_clear; |
| bits_to_clear = BITMAP_BITS_PER_WORD; |
| mask_to_clear = ~0UL; |
| p++; |
| } |
| if (nr) { |
| mask_to_clear &= BITMAP_LAST_WORD_MASK(size); |
| *p &= ~mask_to_clear; |
| } |
| } |
| |
| static inline int bitmap_test(unsigned long *bitmap, int bit) { |
| return BIT_SET(bitmap[BITMAP_WORD(bit)], BITMAP_BIT_IN_WORD(bit)); |
| } |
| |
| /* find first zero bit starting from LSB */ |
| static inline unsigned long _ffz(unsigned long x) { return __builtin_ffsl(~x) - 1; } |
| |
| static inline int bitmap_ffz(unsigned long *bitmap, int numbits) { |
| int bit; |
| |
| for (int i = 0; i < BITMAP_NUM_WORDS(numbits); i++) { |
| if (bitmap[i] == ~0UL) |
| continue; |
| bit = i * BITMAP_BITS_PER_WORD + (int)_ffz(bitmap[i]); |
| if (bit < numbits) |
| return bit; |
| return -1; |
| } |
| return -1; |
| } |
| |
| // Extracts the bit range from [lower_bound, upper_bound] (inclusive) from input |
| // and returns it as a type ReturnType. |
| template <size_t upper_bound, size_t lower_bound, typename ReturnType, typename SourceType> |
| constexpr inline ReturnType ExtractBits(SourceType input) { |
| // Add one to upper bound because it is inclusive. |
| constexpr auto bit_count = upper_bound + 1 - lower_bound; |
| |
| static_assert(upper_bound > lower_bound, "Upper bound must be higher than lower bound."); |
| static_assert(upper_bound < (sizeof(SourceType) * 8), "Source value ends before upper bound"); |
| static_assert(bit_count <= (sizeof(ReturnType) * 8), |
| "Return Type is not large enough to hold requested bits."); |
| |
| return static_cast<ReturnType>((input >> lower_bound) & (valpow2(bit_count) - 1)); |
| } |
| |
| #endif // ZIRCON_KERNEL_INCLUDE_BITS_H_ |