src/util/bitscan.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2008 VMware, Inc.
   4  * All Rights Reserved.
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining a
   7  * copy of this software and associated documentation files (the
   8  * "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sub license, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the
  15  * next paragraph) shall be included in all copies or substantial portions
  16  * of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT.
  21  * IN NO EVENT SHALL VMWARE AND/OR ITS SUPPLIERS BE LIABLE FOR
  22  * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  **************************************************************************/
  27
  28
  29 #ifndef BITSCAN_H
  30 #define BITSCAN_H
  31
  32 #include <assert.h>
  33 #include <stdint.h>
  34 #include <stdbool.h>
  35 #include <string.h>
  36
  37 #if defined(_MSC_VER)
  38 #include <intrin.h>
  39 #endif
  40
  41 #include "c99_compat.h"
  42
  43 #ifdef __cplusplus
  44 extern "C" {
  45 #endif
  46
  47
  48 /**
  49  * Find first bit set in word.  Least significant bit is 1.
  50  * Return 0 if no bits set.
  51  */
  52 #ifdef HAVE___BUILTIN_FFS
  53 #define ffs __builtin_ffs
  54 #elif defined(_MSC_VER) && (_M_IX86 || _M_ARM || _M_AMD64 || _M_IA64)
  55 static inline
  56 int ffs(int i)
  57 {
  58    unsigned long index;
  59    if (_BitScanForward(&index, i))
  60       return index + 1;
  61    else
  62       return 0;
  63 }
  64 #else
  65 extern
  66 int ffs(int i);
  67 #endif
  68
  69 #ifdef HAVE___BUILTIN_FFSLL
  70 #define ffsll __builtin_ffsll
  71 #elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM || _M_IA64)
  72 static inline int
  73 ffsll(long long int i)
  74 {
  75    unsigned long index;
  76    if (_BitScanForward64(&index, i))
  77       return index + 1;
  78    else
  79       return 0;
  80 }
  81 #else
  82 extern int
  83 ffsll(long long int val);
  84 #endif
  85
  86
  87 /* Destructively loop over all of the bits in a mask as in:
  88  *
  89  * while (mymask) {
  90  *   int i = u_bit_scan(&mymask);
  91  *   ... process element i
  92  * }
  93  *
  94  */
  95 static inline int
  96 u_bit_scan(unsigned *mask)
  97 {
  98    const int i = ffs(*mask) - 1;
  99    *mask ^= (1u << i);
 100    return i;
 101 }
 102
 103 static inline int
 104 u_bit_scan64(uint64_t *mask)
 105 {
 106    const int i = ffsll(*mask) - 1;
 107    *mask ^= (((uint64_t)1) << i);
 108    return i;
 109 }
 110
 111 /* Determine if an unsigned value is a power of two.
 112  *
 113  * \note
 114  * Zero is treated as a power of two.
 115  */
 116 static inline bool
 117 util_is_power_of_two_or_zero(unsigned v)
 118 {
 119    return (v & (v - 1)) == 0;
 120 }
 121
 122 /* Determine if an unsigned value is a power of two.
 123  *
 124  * \note
 125  * Zero is \b not treated as a power of two.
 126  */
 127 static inline bool
 128 util_is_power_of_two_nonzero(unsigned v)
 129 {
 130    return v != 0 && (v & (v - 1)) == 0;
 131 }
 132
 133 /* For looping over a bitmask when you want to loop over consecutive bits
 134  * manually, for example:
 135  *
 136  * while (mask) {
 137  *    int start, count, i;
 138  *
 139  *    u_bit_scan_consecutive_range(&mask, &start, &count);
 140  *
 141  *    for (i = 0; i < count; i++)
 142  *       ... process element (start+i)
 143  * }
 144  */
 145 static inline void
 146 u_bit_scan_consecutive_range(unsigned *mask, int *start, int *count)
 147 {
 148    if (*mask == 0xffffffff) {
 149       *start = 0;
 150       *count = 32;
 151       *mask = 0;
 152       return;
 153    }
 154    *start = ffs(*mask) - 1;
 155    *count = ffs(~(*mask >> *start)) - 1;
 156    *mask &= ~(((1u << *count) - 1) << *start);
 157 }
 158
 159 static inline void
 160 u_bit_scan_consecutive_range64(uint64_t *mask, int *start, int *count)
 161 {
 162    if (*mask == ~0ull) {
 163       *start = 0;
 164       *count = 64;
 165       *mask = 0;
 166       return;
 167    }
 168    *start = ffsll(*mask) - 1;
 169    *count = ffsll(~(*mask >> *start)) - 1;
 170    *mask &= ~(((((uint64_t)1) << *count) - 1) << *start);
 171 }
 172
 173
 174 /**
 175  * Find last bit set in a word.  The least significant bit is 1.
 176  * Return 0 if no bits are set.
 177  * Essentially ffs() in the reverse direction.
 178  */
 179 static inline unsigned
 180 util_last_bit(unsigned u)
 181 {
 182 #if defined(HAVE___BUILTIN_CLZ)
 183    return u == 0 ? 0 : 32 - __builtin_clz(u);
 184 #elif defined(_MSC_VER) && (_M_IX86 || _M_ARM || _M_AMD64 || _M_IA64)
 185    unsigned long index;
 186    if (_BitScanReverse(&index, u))
 187       return index + 1;
 188    else
 189       return 0;
 190 #else
 191    unsigned r = 0;
 192    while (u) {
 193       r++;
 194       u >>= 1;
 195    }
 196    return r;
 197 #endif
 198 }
 199
 200 /**
 201  * Find last bit set in a word.  The least significant bit is 1.
 202  * Return 0 if no bits are set.
 203  * Essentially ffsll() in the reverse direction.
 204  */
 205 static inline unsigned
 206 util_last_bit64(uint64_t u)
 207 {
 208 #if defined(HAVE___BUILTIN_CLZLL)
 209    return u == 0 ? 0 : 64 - __builtin_clzll(u);
 210 #elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM || _M_IA64)
 211    unsigned long index;
 212    if (_BitScanReverse64(&index, u))
 213       return index + 1;
 214    else
 215       return 0;
 216 #else
 217    unsigned r = 0;
 218    while (u) {
 219       r++;
 220       u >>= 1;
 221    }
 222    return r;
 223 #endif
 224 }
 225
 226 /**
 227  * Find last bit in a word that does not match the sign bit. The least
 228  * significant bit is 1.
 229  * Return 0 if no bits are set.
 230  */
 231 static inline unsigned
 232 util_last_bit_signed(int i)
 233 {
 234    if (i >= 0)
 235       return util_last_bit(i);
 236    else
 237       return util_last_bit(~(unsigned)i);
 238 }
 239
 240 /* Returns a bitfield in which the first count bits starting at start are
 241  * set.
 242  */
 243 static inline unsigned
 244 u_bit_consecutive(unsigned start, unsigned count)
 245 {
 246    assert(start + count <= 32);
 247    if (count == 32)
 248       return ~0;
 249    return ((1u << count) - 1) << start;
 250 }
 251
 252 static inline uint64_t
 253 u_bit_consecutive64(unsigned start, unsigned count)
 254 {
 255    assert(start + count <= 64);
 256    if (count == 64)
 257       return ~(uint64_t)0;
 258    return (((uint64_t)1 << count) - 1) << start;
 259 }
 260
 261
 262 #ifdef __cplusplus
 263 }
 264 #endif
 265
 266 #endif /* BITSCAN_H */