bitops.h

   1 #ifndef _PERF_LINUX_BITOPS_H_
   2 #define _PERF_LINUX_BITOPS_H_
   3
   4 #include <linux/kernel.h>
   5
   6 #define BITS_PER_BYTE           8
   7 #define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
   8 #define BITS_TO_U64(nr)         DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u64))
   9 #define BITS_TO_U32(nr)         DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(u32))
  10
  11 #define for_each_set_bit(bit, addr, size) \
  12         for ((bit) = find_first_bit((addr), (size));            \
  13              (bit) < (size);                                    \
  14              (bit) = find_next_bit((addr), (size), (bit) + 1))
  15
  16 /* same as for_each_set_bit() but use bit as value to start with */
  17 #define for_each_set_bit_from(bit, addr, size) \
  18         for ((bit) = find_next_bit((addr), (size), (bit));      \
  19              (bit) < (size);                                    \
  20              (bit) = find_next_bit((addr), (size), (bit) + 1))
  21
  22 static inline void set_bit(int nr, unsigned long *addr)
  23 {
  24         addr[nr / BITS_PER_LONG] |= 1UL << (nr % BITS_PER_LONG);
  25 }
  26
  27 static inline void clear_bit(int nr, unsigned long *addr)
  28 {
  29         addr[nr / BITS_PER_LONG] &= ~(1UL << (nr % BITS_PER_LONG));
  30 }
  31
  32 /**
  33  * hweightN - returns the hamming weight of a N-bit word
  34  * @x: the word to weigh
  35  *
  36  * The Hamming Weight of a number is the total number of bits set in it.
  37  */
  38
  39 static inline unsigned int hweight32(unsigned int w)
  40 {
  41         unsigned int res = w - ((w >> 1) & 0x55555555);
  42         res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
  43         res = (res + (res >> 4)) & 0x0F0F0F0F;
  44         res = res + (res >> 8);
  45         return (res + (res >> 16)) & 0x000000FF;
  46 }
  47
  48 static inline unsigned long hweight64(__u64 w)
  49 {
  50 #if BITS_PER_LONG == 32
  51         return hweight32((unsigned int)(w >> 32)) + hweight32((unsigned int)w);
  52 #elif BITS_PER_LONG == 64
  53         __u64 res = w - ((w >> 1) & 0x5555555555555555ul);
  54         res = (res & 0x3333333333333333ul) + ((res >> 2) & 0x3333333333333333ul);
  55         res = (res + (res >> 4)) & 0x0F0F0F0F0F0F0F0Ful;
  56         res = res + (res >> 8);
  57         res = res + (res >> 16);
  58         return (res + (res >> 32)) & 0x00000000000000FFul;
  59 #endif
  60 }
  61
  62 static inline unsigned long hweight_long(unsigned long w)
  63 {
  64         return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
  65 }
  66
  67 #define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
  68
  69 /**
  70  * __ffs - find first bit in word.
  71  * @word: The word to search
  72  *
  73  * Undefined if no bit exists, so code should check against 0 first.
  74  */
  75 static __always_inline unsigned long __ffs(unsigned long word)
  76 {
  77         int num = 0;
  78
  79 #if BITS_PER_LONG == 64
  80         if ((word & 0xffffffff) == 0) {
  81                 num += 32;
  82                 word >>= 32;
  83         }
  84 #endif
  85         if ((word & 0xffff) == 0) {
  86                 num += 16;
  87                 word >>= 16;
  88         }
  89         if ((word & 0xff) == 0) {
  90                 num += 8;
  91                 word >>= 8;
  92         }
  93         if ((word & 0xf) == 0) {
  94                 num += 4;
  95                 word >>= 4;
  96         }
  97         if ((word & 0x3) == 0) {
  98                 num += 2;
  99                 word >>= 2;
 100         }
 101         if ((word & 0x1) == 0)
 102                 num += 1;
 103         return num;
 104 }
 105
 106 #define ffz(x) __ffs(~(x))
 107
 108 /*
 109  * Find the first set bit in a memory region.
 110  */
 111 static inline unsigned long
 112 find_first_bit(const unsigned long *addr, unsigned long size)
 113 {
 114         const unsigned long *p = addr;
 115         unsigned long result = 0;
 116         unsigned long tmp;
 117
 118         while (size & ~(BITS_PER_LONG-1)) {
 119                 if ((tmp = *(p++)))
 120                         goto found;
 121                 result += BITS_PER_LONG;
 122                 size -= BITS_PER_LONG;
 123         }
 124         if (!size)
 125                 return result;
 126
 127         tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
 128         if (tmp == 0UL)         /* Are any bits set? */
 129                 return result + size;   /* Nope. */
 130 found:
 131         return result + __ffs(tmp);
 132 }
 133
 134 /*
 135  * Find the next set bit in a memory region.
 136  */
 137 static inline unsigned long
 138 find_next_bit(const unsigned long *addr, unsigned long size,
 139               unsigned long offset)
 140 {
 141         const unsigned long *p = addr + BITOP_WORD(offset);
 142         unsigned long result = offset & ~(BITS_PER_LONG-1);
 143         unsigned long tmp;
 144
 145         if (offset >= size)
 146                 return size;
 147         size -= result;
 148         offset %= BITS_PER_LONG;
 149         if (offset) {
 150                 tmp = *(p++);
 151                 tmp &= (~0UL << offset);
 152                 if (size < BITS_PER_LONG)
 153                         goto found_first;
 154                 if (tmp)
 155                         goto found_middle;
 156                 size -= BITS_PER_LONG;
 157                 result += BITS_PER_LONG;
 158         }
 159         while (size & ~(BITS_PER_LONG-1)) {
 160                 if ((tmp = *(p++)))
 161                         goto found_middle;
 162                 result += BITS_PER_LONG;
 163                 size -= BITS_PER_LONG;
 164         }
 165         if (!size)
 166                 return result;
 167         tmp = *p;
 168
 169 found_first:
 170         tmp &= (~0UL >> (BITS_PER_LONG - size));
 171         if (tmp == 0UL)         /* Are any bits set? */
 172                 return result + size;   /* Nope. */
 173 found_middle:
 174         return result + __ffs(tmp);
 175 }
 176
 177 /*
 178  * This implementation of find_{first,next}_zero_bit was stolen from
 179  * Linus' asm-alpha/bitops.h.
 180  */
 181 static inline unsigned long
 182 find_next_zero_bit(const unsigned long *addr, unsigned long size,
 183                    unsigned long offset)
 184 {
 185         const unsigned long *p = addr + BITOP_WORD(offset);
 186         unsigned long result = offset & ~(BITS_PER_LONG-1);
 187         unsigned long tmp;
 188
 189         if (offset >= size)
 190                 return size;
 191         size -= result;
 192         offset %= BITS_PER_LONG;
 193         if (offset) {
 194                 tmp = *(p++);
 195                 tmp |= ~0UL >> (BITS_PER_LONG - offset);
 196                 if (size < BITS_PER_LONG)
 197                         goto found_first;
 198                 if (~tmp)
 199                         goto found_middle;
 200                 size -= BITS_PER_LONG;
 201                 result += BITS_PER_LONG;
 202         }
 203         while (size & ~(BITS_PER_LONG-1)) {
 204                 if (~(tmp = *(p++)))
 205                         goto found_middle;
 206                 result += BITS_PER_LONG;
 207                 size -= BITS_PER_LONG;
 208         }
 209         if (!size)
 210                 return result;
 211         tmp = *p;
 212
 213 found_first:
 214         tmp |= ~0UL << size;
 215         if (tmp == ~0UL)        /* Are any bits zero? */
 216                 return result + size;   /* Nope. */
 217 found_middle:
 218         return result + ffz(tmp);
 219 }
 220 #endif