1 // Copyright 2016 The Fuchsia Authors
2 // Copyright (c) 2008 Travis Geiselbrecht
3 //
4 // Use of this source code is governed by a MIT-style
5 // license that can be found in the LICENSE file or at
6 // https://opensource.org/licenses/MIT
7
8 #pragma once
9
10 #include <zircon/compiler.h>
11 #include <arch/ops.h>
12
13 __BEGIN_CDECLS
14
15 #define clz(x) __builtin_clz(x)
16 #define ctz(x) __builtin_ctz(x)
17
18 /* Trick to get a 1 of the right size */
19 #define _ONE(x) (1 + ((x) - (x)))
20
21 #define BIT(x, bit) ((x) & (_ONE(x) << (bit)))
22 #define BIT_SHIFT(x, bit) (((x) >> (bit)) & 1)
23 #define BITS(x, high, low) ((x) & (((_ONE(x)<<((high)+1))-1) & ~((_ONE(x)<<(low))-1)))
24 #define BITS_SHIFT(x, high, low) (((x) >> (low)) & ((_ONE(x)<<((high)-(low)+1))-1))
25 #define BIT_SET(x, bit) (((x) & (_ONE(x) << (bit))) ? 1 : 0)
26
27 #define BITMAP_BITS_PER_WORD ((int)(sizeof(unsigned long) * 8))
28 #define BITMAP_NUM_WORDS(x) (((x) + BITMAP_BITS_PER_WORD - 1) / BITMAP_BITS_PER_WORD)
29 #define BITMAP_WORD(x) ((x) / BITMAP_BITS_PER_WORD)
30 #define BITMAP_BIT_IN_WORD(x) ((x) & (BITMAP_BITS_PER_WORD - 1))
31
32 #define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITMAP_BITS_PER_WORD))
33 #define BITMAP_LAST_WORD_MASK(nbits) (((nbits) % BITMAP_BITS_PER_WORD) ? (1UL<<((nbits) % BITMAP_BITS_PER_WORD))-1 : ~0UL)
34
35 #define BITMAP_BITS_PER_INT (sizeof(unsigned int) * 8)
36 #define BITMAP_BIT_IN_INT(x) ((x) & (BITMAP_BITS_PER_INT - 1))
37 #define BITMAP_INT(x) ((x) / BITMAP_BITS_PER_INT)
38
39 #define BIT_MASK(x) (((x) >= sizeof(unsigned long) * 8) ? (0UL-1) : ((1UL << (x)) - 1))
40
bitmap_set(unsigned long * bitmap,int start,int nr)41 static inline void bitmap_set(unsigned long *bitmap, int start, int nr)
42 {
43 unsigned long *p = bitmap + BITMAP_WORD(start);
44 const long size = start + nr;
45 int bits_to_set = BITMAP_BITS_PER_WORD - (start % BITMAP_BITS_PER_WORD);
46 unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
47
48 while (nr - bits_to_set >= 0) {
49 *p |= mask_to_set;
50 nr -= bits_to_set;
51 bits_to_set = BITMAP_BITS_PER_WORD;
52 mask_to_set = ~0UL;
53 p++;
54 }
55 if (nr) {
56 mask_to_set &= BITMAP_LAST_WORD_MASK(size);
57 *p |= mask_to_set;
58 }
59 }
60
bitmap_clear(unsigned long * bitmap,int start,int nr)61 static inline void bitmap_clear(unsigned long *bitmap, int start, int nr)
62 {
63 unsigned long *p = bitmap + BITMAP_WORD(start);
64 const long size = start + nr;
65 int bits_to_clear = BITMAP_BITS_PER_WORD - (start % BITMAP_BITS_PER_WORD);
66 unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
67
68 while (nr - bits_to_clear >= 0) {
69 *p &= ~mask_to_clear;
70 nr -= bits_to_clear;
71 bits_to_clear = BITMAP_BITS_PER_WORD;
72 mask_to_clear = ~0UL;
73 p++;
74 }
75 if (nr) {
76 mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
77 *p &= ~mask_to_clear;
78 }
79 }
80
bitmap_test(unsigned long * bitmap,int bit)81 static inline int bitmap_test(unsigned long *bitmap, int bit)
82 {
83 return BIT_SET(bitmap[BITMAP_WORD(bit)], BITMAP_BIT_IN_WORD(bit));
84 }
85
86 /* find first zero bit starting from LSB */
_ffz(unsigned long x)87 static inline unsigned long _ffz(unsigned long x)
88 {
89 return __builtin_ffsl(~x) - 1;
90 }
91
bitmap_ffz(unsigned long * bitmap,int numbits)92 static inline int bitmap_ffz(unsigned long *bitmap, int numbits)
93 {
94 int bit;
95
96 for (int i = 0; i < BITMAP_NUM_WORDS(numbits); i++) {
97 if (bitmap[i] == ~0UL)
98 continue;
99 bit = i * BITMAP_BITS_PER_WORD + (int)_ffz(bitmap[i]);
100 if (bit < numbits)
101 return bit;
102 return -1;
103 }
104 return -1;
105 }
106
107 __END_CDECLS
108