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 #if defined(__POPCNT__)
  42 #include <popcntintrin.h>
  43 #endif
  44
  45 #include "c99_compat.h"
  46
  47 #ifdef __cplusplus
  48 extern "C" {
  49 #endif
  50
  51
  52 /**
  53  * Find first bit set in word.  Least significant bit is 1.
  54  * Return 0 if no bits set.
  55  */
  56 #ifdef HAVE___BUILTIN_FFS
  57 #define ffs __builtin_ffs
  58 #elif defined(_MSC_VER) && (_M_IX86 || _M_ARM || _M_AMD64 || _M_IA64)
  59 static inline
  60 int ffs(int i)
  61 {
  62    unsigned long index;
  63    if (_BitScanForward(&index, i))
  64       return index + 1;
  65    else
  66       return 0;
  67 }
  68 #else
  69 extern
  70 int ffs(int i);
  71 #endif
  72
  73 #ifdef HAVE___BUILTIN_FFSLL
  74 #define ffsll __builtin_ffsll
  75 #elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM || _M_IA64)
  76 static inline int
  77 ffsll(long long int i)
  78 {
  79    unsigned long index;
  80    if (_BitScanForward64(&index, i))
  81       return index + 1;
  82    else
  83       return 0;
  84 }
  85 #else
  86 extern int
  87 ffsll(long long int val);
  88 #endif
  89
  90
  91 /* Destructively loop over all of the bits in a mask as in:
  92  *
  93  * while (mymask) {
  94  *   int i = u_bit_scan(&mymask);
  95  *   ... process element i
  96  * }
  97  *
  98  */
  99 static inline int
 100 u_bit_scan(unsigned *mask)
 101 {
 102    const int i = ffs(*mask) - 1;
 103    *mask ^= (1u << i);
 104    return i;
 105 }
 106
 107 static inline int
 108 u_bit_scan64(uint64_t *mask)
 109 {
 110    const int i = ffsll(*mask) - 1;
 111    *mask ^= (((uint64_t)1) << i);
 112    return i;
 113 }
 114
 115 /* Determine if an unsigned value is a power of two.
 116  *
 117  * \note
 118  * Zero is treated as a power of two.
 119  */
 120 static inline bool
 121 util_is_power_of_two_or_zero(unsigned v)
 122 {
 123    return (v & (v - 1)) == 0;
 124 }
 125
 126 /* Determine if an unsigned value is a power of two.
 127  *
 128  * \note
 129  * Zero is \b not treated as a power of two.
 130  */
 131 static inline bool
 132 util_is_power_of_two_nonzero(unsigned v)
 133 {
 134    /* __POPCNT__ is different from HAVE___BUILTIN_POPCOUNT.  The latter
 135     * indicates the existence of the __builtin_popcount function.  The former
 136     * indicates that _mm_popcnt_u32 exists and is a native instruction.
 137     *
 138     * The other alternative is to use SSE 4.2 compile-time flags.  This has
 139     * two drawbacks.  First, there is currently no build infrastructure for
 140     * SSE 4.2 (only 4.1), so that would have to be added.  Second, some AMD
 141     * CPUs support POPCNT but not SSE 4.2 (e.g., Barcelona).
 142     */
 143 #ifdef __POPCNT__
 144    return _mm_popcnt_u32(v) == 1;
 145 #else
 146    return v != 0 && (v & (v - 1)) == 0;
 147 #endif
 148 }
 149
 150 /* For looping over a bitmask when you want to loop over consecutive bits
 151  * manually, for example:
 152  *
 153  * while (mask) {
 154  *    int start, count, i;
 155  *
 156  *    u_bit_scan_consecutive_range(&mask, &start, &count);
 157  *
 158  *    for (i = 0; i < count; i++)
 159  *       ... process element (start+i)
 160  * }
 161  */
 162 static inline void
 163 u_bit_scan_consecutive_range(unsigned *mask, int *start, int *count)
 164 {
 165    if (*mask == 0xffffffff) {
 166       *start = 0;
 167       *count = 32;
 168       *mask = 0;
 169       return;
 170    }
 171    *start = ffs(*mask) - 1;
 172    *count = ffs(~(*mask >> *start)) - 1;
 173    *mask &= ~(((1u << *count) - 1) << *start);
 174 }
 175
 176 static inline void
 177 u_bit_scan_consecutive_range64(uint64_t *mask, int *start, int *count)
 178 {
 179    if (*mask == ~0ull) {
 180       *start = 0;
 181       *count = 64;
 182       *mask = 0;
 183       return;
 184    }
 185    *start = ffsll(*mask) - 1;
 186    *count = ffsll(~(*mask >> *start)) - 1;
 187    *mask &= ~(((((uint64_t)1) << *count) - 1) << *start);
 188 }
 189
 190
 191 /**
 192  * Find last bit set in a word.  The least significant bit is 1.
 193  * Return 0 if no bits are set.
 194  * Essentially ffs() in the reverse direction.
 195  */
 196 static inline unsigned
 197 util_last_bit(unsigned u)
 198 {
 199 #if defined(HAVE___BUILTIN_CLZ)
 200    return u == 0 ? 0 : 32 - __builtin_clz(u);
 201 #elif defined(_MSC_VER) && (_M_IX86 || _M_ARM || _M_AMD64 || _M_IA64)
 202    unsigned long index;
 203    if (_BitScanReverse(&index, u))
 204       return index + 1;
 205    else
 206       return 0;
 207 #else
 208    unsigned r = 0;
 209    while (u) {
 210       r++;
 211       u >>= 1;
 212    }
 213    return r;
 214 #endif
 215 }
 216
 217 /**
 218  * Find last bit set in a word.  The least significant bit is 1.
 219  * Return 0 if no bits are set.
 220  * Essentially ffsll() in the reverse direction.
 221  */
 222 static inline unsigned
 223 util_last_bit64(uint64_t u)
 224 {
 225 #if defined(HAVE___BUILTIN_CLZLL)
 226    return u == 0 ? 0 : 64 - __builtin_clzll(u);
 227 #elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM || _M_IA64)
 228    unsigned long index;
 229    if (_BitScanReverse64(&index, u))
 230       return index + 1;
 231    else
 232       return 0;
 233 #else
 234    unsigned r = 0;
 235    while (u) {
 236       r++;
 237       u >>= 1;
 238    }
 239    return r;
 240 #endif
 241 }
 242
 243 /**
 244  * Find last bit in a word that does not match the sign bit. The least
 245  * significant bit is 1.
 246  * Return 0 if no bits are set.
 247  */
 248 static inline unsigned
 249 util_last_bit_signed(int i)
 250 {
 251    if (i >= 0)
 252       return util_last_bit(i);
 253    else
 254       return util_last_bit(~(unsigned)i);
 255 }
 256
 257 /* Returns a bitfield in which the first count bits starting at start are
 258  * set.
 259  */
 260 static inline unsigned
 261 u_bit_consecutive(unsigned start, unsigned count)
 262 {
 263    assert(start + count <= 32);
 264    if (count == 32)
 265       return ~0;
 266    return ((1u << count) - 1) << start;
 267 }
 268
 269 static inline uint64_t
 270 u_bit_consecutive64(unsigned start, unsigned count)
 271 {
 272    assert(start + count <= 64);
 273    if (count == 64)
 274       return ~(uint64_t)0;
 275    return (((uint64_t)1 << count) - 1) << start;
 276 }
 277
 278
 279 #ifdef __cplusplus
 280 }
 281 #endif
 282
 283 #endif /* BITSCAN_H */