1 // Bit manipulation functions. These functions are not privileged.
6 #include <lowlevel/arch.h>
7 #include <lowlevel/types.h>
8 #include _LL_INC(bitops.h)
10 // Find First (least-significant) Set, counting from 0,
11 // undefined if no bits set
13 static inline int ll_ffs(unsigned long val)
15 return __builtin_ctzl(val);
18 // Find Last (most-significant) Set, counting from 0,
19 // undefined if no bits set
21 static inline int ll_fls(unsigned long val)
23 return (sizeof(unsigned long)*8 - 1) ^ __builtin_clzl(val);
26 // As above, except on 64-bit values regardless of sizeof(long).
27 static inline int ll_ffs64(uint64_t val)
29 return __builtin_ctzll(val);
32 // Find Last (most-significant) Set, counting from 0,
33 // undefined if no bits set
35 static inline int ll_fls64(unsigned long val)
37 return (sizeof(unsigned long long)*8 - 1) ^ __builtin_clzll(val);
40 static inline int ll_get_order_round_up(unsigned long val)
42 return val > 1 ? ll_fls(val - 1) + 1 : 0;
45 static inline int ll_get_order_round_down(unsigned long val)
50 // Note that the multiword bit scans are endian and word size dependent.
51 // They return -1 if no suitable bit was found. Start and end are
54 static inline int ll_multiword_ffs(unsigned long *bitmap, int start, int len)
56 static const int bits_per_long = sizeof(unsigned long) * 8;
57 int off = start / bits_per_long;
58 int shift_first = start % bits_per_long;
61 unsigned long shifted = *bitmap >> shift_first;
64 return ll_ffs(shifted) + start;
67 start = off * bits_per_long;
70 while (off < len / bits_per_long) {
75 start += bits_per_long;
78 if (start < len && bitmap[off]) {
79 int ret = start + ll_ffs(bitmap[off]);
88 static inline int ll_multiword_ffc(unsigned long *bitmap, int start, int len)
90 static const int bits_per_long = sizeof(unsigned long) * 8;
91 int off = start / bits_per_long;
92 int shift_first = start % bits_per_long;
95 unsigned long shifted = *bitmap >> shift_first;
98 return ll_ffs(~shifted) + start;
101 start = off * bits_per_long;
104 while (off < len / bits_per_long) {
109 start += bits_per_long;
112 if (start < len && ~bitmap[off]) {
113 int ret = start + ll_ffs(~bitmap[off]);