bitops.h

   1 /*
   2  * Bitops Module
   3  *
   4  * Copyright (C) 2010 Corentin Chary <corentin.chary@gmail.com>
   5  *
   6  * Mostly inspired by (stolen from) linux/bitmap.h and linux/bitops.h
   7  *
   8  * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
   9  * See the COPYING.LIB file in the top-level directory.
  10  */
  11
  12 #ifndef BITOPS_H
  13 #define BITOPS_H
  14
  15 #include "qemu-common.h"
  16
  17 #define BITS_PER_BYTE           CHAR_BIT
  18 #define BITS_PER_LONG           (sizeof (unsigned long) * BITS_PER_BYTE)
  19
  20 #define BIT(nr)                 (1UL << (nr))
  21 #define BIT_MASK(nr)            (1UL << ((nr) % BITS_PER_LONG))
  22 #define BIT_WORD(nr)            ((nr) / BITS_PER_LONG)
  23 #define BITS_TO_LONGS(nr)       DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
  24
  25 /**
  26  * bitops_ffs - find first bit in word.
  27  * @word: The word to search
  28  *
  29  * Undefined if no bit exists, so code should check against 0 first.
  30  */
  31 static unsigned long bitops_ffsl(unsigned long word)
  32 {
  33         int num = 0;
  34
  35 #if LONG_MAX > 0x7FFFFFFF
  36         if ((word & 0xffffffff) == 0) {
  37                 num += 32;
  38                 word >>= 32;
  39         }
  40 #endif
  41         if ((word & 0xffff) == 0) {
  42                 num += 16;
  43                 word >>= 16;
  44         }
  45         if ((word & 0xff) == 0) {
  46                 num += 8;
  47                 word >>= 8;
  48         }
  49         if ((word & 0xf) == 0) {
  50                 num += 4;
  51                 word >>= 4;
  52         }
  53         if ((word & 0x3) == 0) {
  54                 num += 2;
  55                 word >>= 2;
  56         }
  57         if ((word & 0x1) == 0) {
  58                 num += 1;
  59         }
  60         return num;
  61 }
  62
  63 /**
  64  * bitops_fls - find last (most-significant) set bit in a long word
  65  * @word: the word to search
  66  *
  67  * Undefined if no set bit exists, so code should check against 0 first.
  68  */
  69 static inline unsigned long bitops_flsl(unsigned long word)
  70 {
  71         int num = BITS_PER_LONG - 1;
  72
  73 #if LONG_MAX > 0x7FFFFFFF
  74         if (!(word & (~0ul << 32))) {
  75                 num -= 32;
  76                 word <<= 32;
  77         }
  78 #endif
  79         if (!(word & (~0ul << (BITS_PER_LONG-16)))) {
  80                 num -= 16;
  81                 word <<= 16;
  82         }
  83         if (!(word & (~0ul << (BITS_PER_LONG-8)))) {
  84                 num -= 8;
  85                 word <<= 8;
  86         }
  87         if (!(word & (~0ul << (BITS_PER_LONG-4)))) {
  88                 num -= 4;
  89                 word <<= 4;
  90         }
  91         if (!(word & (~0ul << (BITS_PER_LONG-2)))) {
  92                 num -= 2;
  93
  94                 word <<= 2;
  95         }
  96         if (!(word & (~0ul << (BITS_PER_LONG-1))))
  97                 num -= 1;
  98         return num;
  99 }
 100
 101 /**
 102  * ffz - find first zero in word.
 103  * @word: The word to search
 104  *
 105  * Undefined if no zero exists, so code should check against ~0UL first.
 106  */
 107 static inline unsigned long ffz(unsigned long word)
 108 {
 109     return bitops_ffsl(~word);
 110 }
 111
 112 /**
 113  * set_bit - Set a bit in memory
 114  * @nr: the bit to set
 115  * @addr: the address to start counting from
 116  */
 117 static inline void set_bit(int nr, unsigned long *addr)
 118 {
 119         unsigned long mask = BIT_MASK(nr);
 120         unsigned long *p = addr + BIT_WORD(nr);
 121
 122         *p  |= mask;
 123 }
 124
 125 /**
 126  * clear_bit - Clears a bit in memory
 127  * @nr: Bit to clear
 128  * @addr: Address to start counting from
 129  */
 130 static inline void clear_bit(int nr, unsigned long *addr)
 131 {
 132         unsigned long mask = BIT_MASK(nr);
 133         unsigned long *p = addr + BIT_WORD(nr);
 134
 135         *p &= ~mask;
 136 }
 137
 138 /**
 139  * change_bit - Toggle a bit in memory
 140  * @nr: Bit to change
 141  * @addr: Address to start counting from
 142  */
 143 static inline void change_bit(int nr, unsigned long *addr)
 144 {
 145         unsigned long mask = BIT_MASK(nr);
 146         unsigned long *p = addr + BIT_WORD(nr);
 147
 148         *p ^= mask;
 149 }
 150
 151 /**
 152  * test_and_set_bit - Set a bit and return its old value
 153  * @nr: Bit to set
 154  * @addr: Address to count from
 155  */
 156 static inline int test_and_set_bit(int nr, unsigned long *addr)
 157 {
 158         unsigned long mask = BIT_MASK(nr);
 159         unsigned long *p = addr + BIT_WORD(nr);
 160         unsigned long old = *p;
 161
 162         *p = old | mask;
 163         return (old & mask) != 0;
 164 }
 165
 166 /**
 167  * test_and_clear_bit - Clear a bit and return its old value
 168  * @nr: Bit to clear
 169  * @addr: Address to count from
 170  */
 171 static inline int test_and_clear_bit(int nr, unsigned long *addr)
 172 {
 173         unsigned long mask = BIT_MASK(nr);
 174         unsigned long *p = addr + BIT_WORD(nr);
 175         unsigned long old = *p;
 176
 177         *p = old & ~mask;
 178         return (old & mask) != 0;
 179 }
 180
 181 /**
 182  * test_and_change_bit - Change a bit and return its old value
 183  * @nr: Bit to change
 184  * @addr: Address to count from
 185  */
 186 static inline int test_and_change_bit(int nr, unsigned long *addr)
 187 {
 188         unsigned long mask = BIT_MASK(nr);
 189         unsigned long *p = addr + BIT_WORD(nr);
 190         unsigned long old = *p;
 191
 192         *p = old ^ mask;
 193         return (old & mask) != 0;
 194 }
 195
 196 /**
 197  * test_bit - Determine whether a bit is set
 198  * @nr: bit number to test
 199  * @addr: Address to start counting from
 200  */
 201 static inline int test_bit(int nr, const unsigned long *addr)
 202 {
 203         return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
 204 }
 205
 206 /**
 207  * find_last_bit - find the last set bit in a memory region
 208  * @addr: The address to start the search at
 209  * @size: The maximum size to search
 210  *
 211  * Returns the bit number of the first set bit, or size.
 212  */
 213 unsigned long find_last_bit(const unsigned long *addr,
 214                             unsigned long size);
 215
 216 /**
 217  * find_next_bit - find the next set bit in a memory region
 218  * @addr: The address to base the search on
 219  * @offset: The bitnumber to start searching at
 220  * @size: The bitmap size in bits
 221  */
 222 unsigned long find_next_bit(const unsigned long *addr,
 223                                    unsigned long size, unsigned long offset);
 224
 225 /**
 226  * find_next_zero_bit - find the next cleared bit in a memory region
 227  * @addr: The address to base the search on
 228  * @offset: The bitnumber to start searching at
 229  * @size: The bitmap size in bits
 230  */
 231
 232 unsigned long find_next_zero_bit(const unsigned long *addr,
 233                                  unsigned long size,
 234                                  unsigned long offset);
 235
 236 /**
 237  * find_first_bit - find the first set bit in a memory region
 238  * @addr: The address to start the search at
 239  * @size: The maximum size to search
 240  *
 241  * Returns the bit number of the first set bit.
 242  */
 243 static inline unsigned long find_first_bit(const unsigned long *addr,
 244                                            unsigned long size)
 245 {
 246     return find_next_bit(addr, size, 0);
 247 }
 248
 249 /**
 250  * find_first_zero_bit - find the first cleared bit in a memory region
 251  * @addr: The address to start the search at
 252  * @size: The maximum size to search
 253  *
 254  * Returns the bit number of the first cleared bit.
 255  */
 256 static inline unsigned long find_first_zero_bit(const unsigned long *addr,
 257                                                 unsigned long size)
 258 {
 259     return find_next_zero_bit(addr, size, 0);
 260 }
 261
 262 static inline unsigned long hweight_long(unsigned long w)
 263 {
 264     unsigned long count;
 265
 266     for (count = 0; w; w >>= 1) {
 267         count += w & 1;
 268     }
 269     return count;
 270 }
 271
 272 /**
 273  * extract32:
 274  * @value: the value to extract the bit field from
 275  * @start: the lowest bit in the bit field (numbered from 0)
 276  * @length: the length of the bit field
 277  *
 278  * Extract from the 32 bit input @value the bit field specified by the
 279  * @start and @length parameters, and return it. The bit field must
 280  * lie entirely within the 32 bit word. It is valid to request that
 281  * all 32 bits are returned (ie @length 32 and @start 0).
 282  *
 283  * Returns: the value of the bit field extracted from the input value.
 284  */
 285 static inline uint32_t extract32(uint32_t value, int start, int length)
 286 {
 287     assert(start >= 0 && length > 0 && length <= 32 - start);
 288     return (value >> start) & (~0U >> (32 - length));
 289 }
 290
 291 /**
 292  * extract64:
 293  * @value: the value to extract the bit field from
 294  * @start: the lowest bit in the bit field (numbered from 0)
 295  * @length: the length of the bit field
 296  *
 297  * Extract from the 64 bit input @value the bit field specified by the
 298  * @start and @length parameters, and return it. The bit field must
 299  * lie entirely within the 64 bit word. It is valid to request that
 300  * all 64 bits are returned (ie @length 64 and @start 0).
 301  *
 302  * Returns: the value of the bit field extracted from the input value.
 303  */
 304 static inline uint64_t extract64(uint64_t value, int start, int length)
 305 {
 306     assert(start >= 0 && length > 0 && length <= 64 - start);
 307     return (value >> start) & (~0ULL >> (64 - length));
 308 }
 309
 310 /**
 311  * deposit32:
 312  * @value: initial value to insert bit field into
 313  * @start: the lowest bit in the bit field (numbered from 0)
 314  * @length: the length of the bit field
 315  * @fieldval: the value to insert into the bit field
 316  *
 317  * Deposit @fieldval into the 32 bit @value at the bit field specified
 318  * by the @start and @length parameters, and return the modified
 319  * @value. Bits of @value outside the bit field are not modified.
 320  * Bits of @fieldval above the least significant @length bits are
 321  * ignored. The bit field must lie entirely within the 32 bit word.
 322  * It is valid to request that all 32 bits are modified (ie @length
 323  * 32 and @start 0).
 324  *
 325  * Returns: the modified @value.
 326  */
 327 static inline uint32_t deposit32(uint32_t value, int start, int length,
 328                                  uint32_t fieldval)
 329 {
 330     uint32_t mask;
 331     assert(start >= 0 && length > 0 && length <= 32 - start);
 332     mask = (~0U >> (32 - length)) << start;
 333     return (value & ~mask) | ((fieldval << start) & mask);
 334 }
 335
 336 /**
 337  * deposit64:
 338  * @value: initial value to insert bit field into
 339  * @start: the lowest bit in the bit field (numbered from 0)
 340  * @length: the length of the bit field
 341  * @fieldval: the value to insert into the bit field
 342  *
 343  * Deposit @fieldval into the 64 bit @value at the bit field specified
 344  * by the @start and @length parameters, and return the modified
 345  * @value. Bits of @value outside the bit field are not modified.
 346  * Bits of @fieldval above the least significant @length bits are
 347  * ignored. The bit field must lie entirely within the 64 bit word.
 348  * It is valid to request that all 64 bits are modified (ie @length
 349  * 64 and @start 0).
 350  *
 351  * Returns: the modified @value.
 352  */
 353 static inline uint64_t deposit64(uint64_t value, int start, int length,
 354                                  uint64_t fieldval)
 355 {
 356     uint64_t mask;
 357     assert(start >= 0 && length > 0 && length <= 64 - start);
 358     mask = (~0ULL >> (64 - length)) << start;
 359     return (value & ~mask) | ((fieldval << start) & mask);
 360 }
 361
 362 #endif