1 #ifndef _LINUX_BITOPS_H
2 #define _LINUX_BITOPS_H
5 #include <linux/types.h>
8 #define BIT(nr) (1 << (nr))
9 #define BIT_MASK(nr) (1 << ((nr) % BITS_PER_LONG))
10 #define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
11 #define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_LONG)
12 #define BITS_PER_BYTE 8
16 * Include this here because some architectures need generic_ffs/fls in
21 * find_first_zero_bit - find the first zero bit in a memory region
22 * @addr: The address to start the search at
23 * @size: The maximum size to search
25 * Returns the bit number of the first zero bit, not the number of the byte
28 #define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0)
31 * find_next_zero_bit - find the first zero bit in a memory region
32 * @addr: The address to base the search on
33 * @offset: The bit number to start searching at
34 * @size: The maximum size to search
36 int find_next_zero_bit(const unsigned long *addr
, int size
, int offset
);
39 * __ffs - find first bit in word.
40 * @word: The word to search
42 * Undefined if no bit exists, so code should check against 0 first.
44 static inline unsigned long __ffs(unsigned long word
)
48 #if BITS_PER_LONG == 64
49 if ((word
& 0xffffffff) == 0) {
54 if ((word
& 0xffff) == 0) {
58 if ((word
& 0xff) == 0) {
62 if ((word
& 0xf) == 0) {
66 if ((word
& 0x3) == 0) {
70 if ((word
& 0x1) == 0)
76 * find_first_bit - find the first set bit in a memory region
77 * @addr: The address to start the search at
78 * @size: The maximum size to search
80 * Returns the bit number of the first set bit, not the number of the byte
83 static inline unsigned find_first_bit(const unsigned long *addr
, unsigned size
)
88 unsigned long val
= *addr
++;
90 return __ffs(val
) + x
;
91 x
+= (sizeof(*addr
)<<3);
97 * find_next_bit - find the next set bit in a memory region
98 * @addr: The address to base the search on
99 * @offset: The bitnumber to start searching at
100 * @size: The maximum size to search
104 * ffz - find first zero in word.
105 * @word: The word to search
107 * Undefined if no zero exists, so code should check against ~0UL first.
109 #define ffz(x) __ffs(~(x))
113 * ffs - find first bit set
114 * @x: the word to search
116 * This is defined the same way as
117 * the libc and compiler builtin ffs routines, therefore
118 * differs in spirit from the above ffz (man ffs).
120 static inline int ffs(int x
)
150 * fls - find last (most-significant) bit set
151 * @x: the word to search
153 * This is defined the same way as ffs.
154 * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.
157 static inline int fls(int x
)
163 if (!(x
& 0xffff0000u
)) {
167 if (!(x
& 0xff000000u
)) {
171 if (!(x
& 0xf0000000u
)) {
175 if (!(x
& 0xc0000000u
)) {
179 if (!(x
& 0x80000000u
)) {
186 static inline int fls64(__u64 x
)
188 __u32 h
= (__u32
) (x
>> 32);
194 #define for_each_bit(bit, addr, size) \
195 for ((bit) = find_first_bit((addr), (size)); \
197 (bit) = find_next_bit((addr), (size), (bit) + 1))
200 static __inline
int get_bitmask_order(unsigned int count
)
205 return order
; /* We could be slightly more clever with -1 here... */
208 static __inline
int get_count_order(unsigned int count
)
212 order
= fls(count
) - 1;
213 if (count
& (count
- 1))
220 * rol32 - rotate a 32-bit value left
221 * @word: value to rotate
222 * @shift: bits to roll
224 static inline __u32
rol32(__u32 word
, unsigned int shift
)
226 return (word
<< shift
) | (word
>> (32 - shift
));
230 * ror32 - rotate a 32-bit value right
231 * @word: value to rotate
232 * @shift: bits to roll
234 static inline __u32
ror32(__u32 word
, unsigned int shift
)
236 return (word
>> shift
) | (word
<< (32 - shift
));
239 static inline unsigned fls_long(unsigned long l
)
247 * hweightN: returns the hamming weight (i.e. the number
248 * of bits set) of a N-bit word
251 static inline unsigned long hweight32(unsigned long w
)
253 unsigned int res
= (w
& 0x55555555) + ((w
>> 1) & 0x55555555);
254 res
= (res
& 0x33333333) + ((res
>> 2) & 0x33333333);
255 res
= (res
& 0x0F0F0F0F) + ((res
>> 4) & 0x0F0F0F0F);
256 res
= (res
& 0x00FF00FF) + ((res
>> 8) & 0x00FF00FF);
257 return (res
& 0x0000FFFF) + ((res
>> 16) & 0x0000FFFF);
260 static inline unsigned long hweight64(__u64 w
)
262 #if BITS_PER_LONG < 64
263 return hweight32((unsigned int)(w
>> 32)) + hweight32((unsigned int)w
);
266 res
= (w
& 0x5555555555555555U
) + ((w
>> 1) & 0x5555555555555555U
);
267 res
= (res
& 0x3333333333333333U
) + ((res
>> 2) & 0x3333333333333333U
);
268 res
= (res
& 0x0F0F0F0F0F0F0F0FU
) + ((res
>> 4) & 0x0F0F0F0F0F0F0F0FU
);
269 res
= (res
& 0x00FF00FF00FF00FFU
) + ((res
>> 8) & 0x00FF00FF00FF00FFU
);
270 res
= (res
& 0x0000FFFF0000FFFFU
) + ((res
>> 16) & 0x0000FFFF0000FFFFU
);
271 return (res
& 0x00000000FFFFFFFFU
) + ((res
>> 32) & 0x00000000FFFFFFFFU
);
275 static inline unsigned long hweight_long(unsigned long w
)
277 return sizeof(w
) == 4 ? hweight32(w
) : hweight64(w
);