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