1 #ifndef _PERF_LINUX_BITOPS_H_
2 #define _PERF_LINUX_BITOPS_H_
4 #include <linux/kernel.h>
6 #define BITS_PER_BYTE 8
7 #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
8 #define BITS_TO_U64(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u64))
9 #define BITS_TO_U32(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u32))
11 #define for_each_set_bit(bit, addr, size) \
12 for ((bit) = find_first_bit((addr), (size)); \
14 (bit) = find_next_bit((addr), (size), (bit) + 1))
16 /* same as for_each_set_bit() but use bit as value to start with */
17 #define for_each_set_bit_from(bit, addr, size) \
18 for ((bit) = find_next_bit((addr), (size), (bit)); \
20 (bit) = find_next_bit((addr), (size), (bit) + 1))
22 static inline void set_bit(int nr
, unsigned long *addr
)
24 addr
[nr
/ BITS_PER_LONG
] |= 1UL << (nr
% BITS_PER_LONG
);
27 static inline void clear_bit(int nr
, unsigned long *addr
)
29 addr
[nr
/ BITS_PER_LONG
] &= ~(1UL << (nr
% BITS_PER_LONG
));
33 * hweightN - returns the hamming weight of a N-bit word
34 * @x: the word to weigh
36 * The Hamming Weight of a number is the total number of bits set in it.
39 static inline unsigned int hweight32(unsigned int w
)
41 unsigned int res
= w
- ((w
>> 1) & 0x55555555);
42 res
= (res
& 0x33333333) + ((res
>> 2) & 0x33333333);
43 res
= (res
+ (res
>> 4)) & 0x0F0F0F0F;
44 res
= res
+ (res
>> 8);
45 return (res
+ (res
>> 16)) & 0x000000FF;
48 static inline unsigned long hweight64(__u64 w
)
50 #if BITS_PER_LONG == 32
51 return hweight32((unsigned int)(w
>> 32)) + hweight32((unsigned int)w
);
52 #elif BITS_PER_LONG == 64
53 __u64 res
= w
- ((w
>> 1) & 0x5555555555555555ul
);
54 res
= (res
& 0x3333333333333333ul
) + ((res
>> 2) & 0x3333333333333333ul
);
55 res
= (res
+ (res
>> 4)) & 0x0F0F0F0F0F0F0F0Ful
;
56 res
= res
+ (res
>> 8);
57 res
= res
+ (res
>> 16);
58 return (res
+ (res
>> 32)) & 0x00000000000000FFul
;
62 static inline unsigned long hweight_long(unsigned long w
)
64 return sizeof(w
) == 4 ? hweight32(w
) : hweight64(w
);
67 #define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
70 * __ffs - find first bit in word.
71 * @word: The word to search
73 * Undefined if no bit exists, so code should check against 0 first.
75 static __always_inline
unsigned long __ffs(unsigned long word
)
79 #if BITS_PER_LONG == 64
80 if ((word
& 0xffffffff) == 0) {
85 if ((word
& 0xffff) == 0) {
89 if ((word
& 0xff) == 0) {
93 if ((word
& 0xf) == 0) {
97 if ((word
& 0x3) == 0) {
101 if ((word
& 0x1) == 0)
106 #define ffz(x) __ffs(~(x))
109 * Find the first set bit in a memory region.
111 static inline unsigned long
112 find_first_bit(const unsigned long *addr
, unsigned long size
)
114 const unsigned long *p
= addr
;
115 unsigned long result
= 0;
118 while (size
& ~(BITS_PER_LONG
-1)) {
121 result
+= BITS_PER_LONG
;
122 size
-= BITS_PER_LONG
;
127 tmp
= (*p
) & (~0UL >> (BITS_PER_LONG
- size
));
128 if (tmp
== 0UL) /* Are any bits set? */
129 return result
+ size
; /* Nope. */
131 return result
+ __ffs(tmp
);
135 * Find the next set bit in a memory region.
137 static inline unsigned long
138 find_next_bit(const unsigned long *addr
, unsigned long size
,
139 unsigned long offset
)
141 const unsigned long *p
= addr
+ BITOP_WORD(offset
);
142 unsigned long result
= offset
& ~(BITS_PER_LONG
-1);
148 offset
%= BITS_PER_LONG
;
151 tmp
&= (~0UL << offset
);
152 if (size
< BITS_PER_LONG
)
156 size
-= BITS_PER_LONG
;
157 result
+= BITS_PER_LONG
;
159 while (size
& ~(BITS_PER_LONG
-1)) {
162 result
+= BITS_PER_LONG
;
163 size
-= BITS_PER_LONG
;
170 tmp
&= (~0UL >> (BITS_PER_LONG
- size
));
171 if (tmp
== 0UL) /* Are any bits set? */
172 return result
+ size
; /* Nope. */
174 return result
+ __ffs(tmp
);
178 * This implementation of find_{first,next}_zero_bit was stolen from
179 * Linus' asm-alpha/bitops.h.
181 static inline unsigned long
182 find_next_zero_bit(const unsigned long *addr
, unsigned long size
,
183 unsigned long offset
)
185 const unsigned long *p
= addr
+ BITOP_WORD(offset
);
186 unsigned long result
= offset
& ~(BITS_PER_LONG
-1);
192 offset
%= BITS_PER_LONG
;
195 tmp
|= ~0UL >> (BITS_PER_LONG
- offset
);
196 if (size
< BITS_PER_LONG
)
200 size
-= BITS_PER_LONG
;
201 result
+= BITS_PER_LONG
;
203 while (size
& ~(BITS_PER_LONG
-1)) {
206 result
+= BITS_PER_LONG
;
207 size
-= BITS_PER_LONG
;
215 if (tmp
== ~0UL) /* Are any bits zero? */
216 return result
+ size
; /* Nope. */
218 return result
+ ffz(tmp
);