Add fls_long() to bitops
[akaros.git] / kern / include / bitops.h
1 #ifndef ROS_KERN_BITOPS_H
2 #define ROS_KERN_BITOPS_H
3
4 #define BIT(nr)                 (1UL << (nr))
5 #define BIT_MASK(nr)            (1UL << ((nr) % BITS_PER_LONG))
6 #define BIT_WORD(nr)            ((nr) / BITS_PER_LONG)
7 #define BITS_PER_BYTE           8
8 #define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
9
10 extern unsigned int __sw_hweight8(unsigned int w);
11 extern unsigned int __sw_hweight16(unsigned int w);
12 extern unsigned int __sw_hweight32(unsigned int w);
13 extern unsigned long __sw_hweight64(uint64_t w);
14
15 /* not clear where we want these defined. */
16 unsigned long find_last_bit(const unsigned long *addr, unsigned long size);
17 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
18                             unsigned long offset);
19 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
20                                  unsigned long offset);
21 unsigned long find_first_bit(const unsigned long *addr, unsigned long size);
22 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size);
23
24 #include <arch/bitops.h>
25
26 #define for_each_set_bit(bit, addr, size) \
27         for ((bit) = find_first_bit((addr), (size));            \
28              (bit) < (size);                                    \
29              (bit) = find_next_bit((addr), (size), (bit) + 1))
30
31 /* same as for_each_set_bit() but use bit as value to start with */
32 #define for_each_set_bit_from(bit, addr, size) \
33         for ((bit) = find_next_bit((addr), (size), (bit));      \
34              (bit) < (size);                                    \
35              (bit) = find_next_bit((addr), (size), (bit) + 1))
36
37 #define for_each_clear_bit(bit, addr, size) \
38         for ((bit) = find_first_zero_bit((addr), (size));       \
39              (bit) < (size);                                    \
40              (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
41
42 /* same as for_each_clear_bit() but use bit as value to start with */
43 #define for_each_clear_bit_from(bit, addr, size) \
44         for ((bit) = find_next_zero_bit((addr), (size), (bit)); \
45              (bit) < (size);                                    \
46              (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
47
48 static __inline__ int get_bitmask_order(unsigned int count)
49 {
50         int order;
51
52         order = fls(count);
53         return order;   /* We could be slightly more clever with -1 here... */
54 }
55
56 static __inline__ int get_count_order(unsigned int count)
57 {
58         int order;
59
60         order = fls(count) - 1;
61         if (count & (count - 1))
62                 order++;
63         return order;
64 }
65
66 static inline unsigned long hweight_long(unsigned long w)
67 {
68         return __builtin_popcount(w);
69         //return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
70 }
71
72 static inline unsigned fls_long(unsigned long l)
73 {
74         if (sizeof(l) == 4)
75                 return fls(l);
76         return fls64(l);
77 }
78
79 // not used yet and I have other things I'm trying to do
80 #if 0
81 static inline bool BITMASK_IS_SET_IN_RANGE(uint8_t* m, size_t beg, size_t end)
82 {
83         for(size_t i=beg; i<end; i++) {
84                 if(!GET_BITMASK_BIT(m, i))
85                         return FALSE;
86         }
87         return TRUE;
88 }
89
90 static inline bool BITMASK_IS_CLR_IN_RANGE(uint8_t* m, size_t beg, size_t end)
91 {
92         for(size_t i=beg; i<end; i++) {
93                 if(GET_BITMASK_BIT(m, i))
94                         return FALSE;
95         }
96         return TRUE;
97 }
98
99 static inline void SET_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
100 {
101         for(size_t i=beg; i<end; i++) {
102                 SET_BITMASK_BIT(m, i);
103         }
104 }
105
106 static inline void CLR_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
107 {
108         for(size_t i=beg; i<end; i++) {
109                 CLR_BITMASK_BIT(m, i);
110         }
111 }
112
113
114 /* Runs *work on every bit in the bitmask, passing *work the value of the bit
115  * that is set.  Optionally clears the bit from the bitmask. 
116  *
117  * We need this to be a macro, so that the calling code doesn't need the
118  * address for work_fn.  This matters for code that has nested functions that
119  * use local variables, since taking the address of work_fn will force the
120  * compiler to put the function on the stack and incur icache coherency
121  * overheads. */
122 #define BITMASK_FOREACH_SET(name, size, work_fn, clear)                        \
123 {                                                                              \
124         for (int i = 0; i < (size); i++) {                                         \
125                 bool present = GET_BITMASK_BIT((name), i);                             \
126                 if (present && (clear))                                                \
127                         CLR_BITMASK_BIT_ATOMIC((name), i);                                 \
128                 if (present)                                                           \
129                         (work_fn)(i);                                                      \
130         }                                                                          \
131 }                                                                              
132 #endif
133 #endif /* ROS_KERN_BITOPS_H */