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 // not used yet and I have other things I'm trying to do
  73 #if 0
  74 static inline bool BITMASK_IS_SET_IN_RANGE(uint8_t* m, size_t beg, size_t end)
  75 {
  76         for(size_t i=beg; i<end; i++) {
  77                 if(!GET_BITMASK_BIT(m, i))
  78                         return FALSE;
  79         }
  80         return TRUE;
  81 }
  82
  83 static inline bool BITMASK_IS_CLR_IN_RANGE(uint8_t* m, size_t beg, size_t end)
  84 {
  85         for(size_t i=beg; i<end; i++) {
  86                 if(GET_BITMASK_BIT(m, i))
  87                         return FALSE;
  88         }
  89         return TRUE;
  90 }
  91
  92 static inline void SET_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
  93 {
  94         for(size_t i=beg; i<end; i++) {
  95                 SET_BITMASK_BIT(m, i);
  96         }
  97 }
  98
  99 static inline void CLR_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
 100 {
 101         for(size_t i=beg; i<end; i++) {
 102                 CLR_BITMASK_BIT(m, i);
 103         }
 104 }
 105
 106
 107 /* Runs *work on every bit in the bitmask, passing *work the value of the bit
 108  * that is set.  Optionally clears the bit from the bitmask.
 109  *
 110  * We need this to be a macro, so that the calling code doesn't need the
 111  * address for work_fn.  This matters for code that has nested functions that
 112  * use local variables, since taking the address of work_fn will force the
 113  * compiler to put the function on the stack and incur icache coherency
 114  * overheads. */
 115 #define BITMASK_FOREACH_SET(name, size, work_fn, clear)                        \
 116 {                                                                              \
 117         for (int i = 0; i < (size); i++) {                                         \
 118                 bool present = GET_BITMASK_BIT((name), i);                             \
 119                 if (present && (clear))                                                \
 120                         CLR_BITMASK_BIT_ATOMIC((name), i);                                 \
 121                 if (present)                                                           \
 122                         (work_fn)(i);                                                      \
 123         }                                                                          \
 124 }
 125 #endif
 126 #endif /* ROS_KERN_BITOPS_H */