#ifndef __BITS_H__
#define __BITS_H__
+#ifdef KERNEL
+#include <kern/assert.h>
#include <kern/kalloc.h>
+#else
+#include <assert.h>
+#include <stdlib.h>
+#define kalloc(x) malloc(x)
+#define kfree(x, y) free(x)
+#endif
#include <stdbool.h>
#include <stdint.h>
+#include <stdatomic.h>
+
+typedef unsigned int uint;
+
+#define BIT(b) (1ULL << (b))
-typedef unsigned int uint;
+#define mask(width) (width >= 64 ? -1ULL : (BIT(width) - 1))
+#define extract(x, shift, width) ((((uint64_t)(x)) >> (shift)) & mask(width))
+#define bits(x, hi, lo) extract((x), (lo), (hi) - (lo) + 1)
-#define BIT(b) (1ULL << (b))
+#define bit_set(x, b) ((x) |= BIT(b))
+#define bit_clear(x, b) ((x) &= ~BIT(b))
+#define bit_test(x, b) ((bool)((x) & BIT(b)))
-#define mask(width) (BIT(width) - 1)
-#define extract(x, shift, width) ((((uint64_t)(x)) >> (shift)) & mask(width))
-#define bits(x, hi, lo) extract((x), (lo), (hi) - (lo) + 1)
+inline static uint64_t
+bit_ror64(uint64_t bitmap, uint n)
+{
+#if defined(__arm64__)
+ uint64_t result;
+ uint64_t _n = (uint64_t)n;
+ asm volatile ("ror %0, %1, %2" : "=r" (result) : "r" (bitmap), "r" (_n));
+ return result;
+#else
+ n = n & 63;
+ return (bitmap >> n) | (bitmap << (64 - n));
+#endif
+}
-#define bit_set(x, b) ((x) |= BIT(b))
-#define bit_clear(x, b) ((x) &= ~BIT(b))
-#define bit_test(x, b) ((bool)((x) & BIT(b)))
+inline static uint64_t
+bit_rol64(uint64_t bitmap, uint n)
+{
+#if defined(__arm64__)
+ return bit_ror64(bitmap, 64U - n);
+#else
+ n = n & 63;
+ return (bitmap << n) | (bitmap >> (64 - n));
+#endif
+}
/* Non-atomically clear the bit and returns whether the bit value was changed */
inline static bool
bit_clear_if_set(uint64_t bitmap, int bit)
{
- bool bit_is_set = bit_test(bitmap, bit);
- bit_clear(bitmap, bit);
- return bit_is_set;
+ bool bit_is_set = bit_test(bitmap, bit);
+ bit_clear(bitmap, bit);
+ return bit_is_set;
}
/* Non-atomically set the bit and returns whether the bit value was changed */
inline static bool
bit_set_if_clear(uint64_t bitmap, int bit)
{
- bool bit_is_set = bit_test(bitmap, bit);
- bit_set(bitmap, bit);
- return !bit_is_set;
+ bool bit_is_set = bit_test(bitmap, bit);
+ bit_set(bitmap, bit);
+ return !bit_is_set;
}
/* Returns the most significant '1' bit, or -1 if all zeros */
{
#if defined(__arm64__)
int64_t result;
- asm volatile("clz %0, %1" : "=r" (result) : "r" (bitmap));
+ asm volatile ("clz %0, %1" : "=r" (result) : "r" (bitmap));
return 63 - (int)result;
#else
return (bitmap == 0) ? -1 : 63 - __builtin_clzll(bitmap);
inline static int
lsb_first(uint64_t bitmap)
{
- return __builtin_ffsll(bitmap) - 1;
+ return __builtin_ffsll((long long)bitmap) - 1;
}
/* Returns the least significant '1' bit that is more significant than previous_bit,
}
/* If n is a power of 2, bit_log2(n) == bit_floor(n) == bit_ceiling(n) */
-#define bit_log2(n) bit_floor((uint64_t)(n))
+#define bit_log2(n) bit_floor((uint64_t)(n))
-typedef _Atomic uint64_t bitmap_t;
+typedef uint64_t bitmap_t;
inline static bool
-atomic_bit_set(bitmap_t *map, int n, int mem_order)
+atomic_bit_set(_Atomic bitmap_t *map, int n, int mem_order)
{
bitmap_t prev;
prev = __c11_atomic_fetch_or(map, BIT(n), mem_order);
}
inline static bool
-atomic_bit_clear(bitmap_t *map, int n, int mem_order)
+atomic_bit_clear(_Atomic bitmap_t *map, int n, int mem_order)
{
bitmap_t prev;
prev = __c11_atomic_fetch_and(map, ~BIT(n), mem_order);
}
-#define BITMAP_LEN(n) (((uint)(n) + 63) >> 6) /* Round to 64bit bitmap_t */
-#define BITMAP_SIZE(n) (size_t)(BITMAP_LEN(n) << 3) /* Round to 64bit bitmap_t, then convert to bytes */
-#define bitmap_bit(n) bits(n, 5, 0)
-#define bitmap_index(n) bits(n, 63, 6)
+#define BITMAP_LEN(n) (((uint)(n) + 63) >> 6) /* Round to 64bit bitmap_t */
+#define BITMAP_SIZE(n) (size_t)(BITMAP_LEN(n) << 3) /* Round to 64bit bitmap_t, then convert to bytes */
+#define bitmap_bit(n) bits(n, 5, 0)
+#define bitmap_index(n) bits(n, 63, 6)
inline static bitmap_t *
bitmap_zero(bitmap_t *map, uint nbits)
inline static bitmap_t *
bitmap_full(bitmap_t *map, uint nbits)
{
- return (bitmap_t *)memset((void *)map, ~0, BITMAP_SIZE(nbits));
+ uint i;
+
+ for (i = 0; i < bitmap_index(nbits - 1); i++) {
+ map[i] = ~((uint64_t)0);
+ }
+
+ uint nbits_filled = i * 64;
+
+ if (nbits > nbits_filled) {
+ map[i] = mask(nbits - nbits_filled);
+ }
+
+ return map;
+}
+
+inline static bool
+bitmap_is_full(bitmap_t *map, uint nbits)
+{
+ uint i;
+
+ for (i = 0; i < bitmap_index(nbits - 1); i++) {
+ if (map[i] != ~((uint64_t)0)) {
+ return false;
+ }
+ }
+
+ uint nbits_filled = i * 64;
+
+ if (nbits > nbits_filled) {
+ return map[i] == mask(nbits - nbits_filled);
+ }
+
+ return true;
}
inline static bitmap_t *
}
inline static bool
-atomic_bitmap_set(bitmap_t *map, uint n, int mem_order)
+atomic_bitmap_set(_Atomic bitmap_t *map, uint n, int mem_order)
{
return atomic_bit_set(&map[bitmap_index(n)], bitmap_bit(n), mem_order);
}
inline static bool
-atomic_bitmap_clear(bitmap_t *map, uint n, int mem_order)
+atomic_bitmap_clear(_Atomic bitmap_t *map, uint n, int mem_order)
{
return atomic_bit_clear(&map[bitmap_index(n)], bitmap_bit(n), mem_order);
}
inline static bool
-bitmap_test(bitmap_t *map, uint n)
+bitmap_test(const bitmap_t *map, uint n)
{
return bit_test(map[bitmap_index(n)], bitmap_bit(n));
}
return -1;
}
+inline static void
+bitmap_not(bitmap_t *out, const bitmap_t *in, uint nbits)
+{
+ uint i;
+
+ for (i = 0; i < bitmap_index(nbits - 1); i++) {
+ out[i] = ~in[i];
+ }
+
+ uint nbits_complete = i * 64;
+
+ if (nbits > nbits_complete) {
+ out[i] = ~in[i] & mask(nbits - nbits_complete);
+ }
+}
+
+inline static void
+bitmap_and(bitmap_t *out, const bitmap_t *in1, const bitmap_t *in2, uint nbits)
+{
+ for (uint i = 0; i <= bitmap_index(nbits - 1); i++) {
+ out[i] = in1[i] & in2[i];
+ }
+}
+
+inline static void
+bitmap_and_not(bitmap_t *out, const bitmap_t *in1, const bitmap_t *in2, uint nbits)
+{
+ uint i;
+
+ for (i = 0; i < bitmap_index(nbits - 1); i++) {
+ out[i] = in1[i] & ~in2[i];
+ }
+
+ uint nbits_complete = i * 64;
+
+ if (nbits > nbits_complete) {
+ out[i] = (in1[i] & ~in2[i]) & mask(nbits - nbits_complete);
+ }
+}
+
+inline static bool
+bitmap_equal(const bitmap_t *in1, const bitmap_t *in2, uint nbits)
+{
+ for (uint i = 0; i <= bitmap_index(nbits - 1); i++) {
+ if (in1[i] != in2[i]) {
+ return false;
+ }
+ }
+
+ return true;
+}
+
inline static int
bitmap_and_not_mask_first(bitmap_t *map, bitmap_t *mask, uint nbits)
{
}
inline static int
-bitmap_lsb_first(bitmap_t *map, uint nbits)
+bitmap_lsb_first(const bitmap_t *map, uint nbits)
{
for (uint i = 0; i <= bitmap_index(nbits - 1); i++) {
if (map[i] == 0) {
}
inline static int
-bitmap_next(bitmap_t *map, uint prev)
+bitmap_next(const bitmap_t *map, uint prev)
{
if (prev == 0) {
return -1;
}
inline static int
-bitmap_lsb_next(bitmap_t *map, uint nbits, uint prev)
+bitmap_lsb_next(const bitmap_t *map, uint nbits, uint prev)
{
if ((prev + 1) >= nbits) {
return -1;
projects / apple / xnu.git / blobdiff