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
  35 #if defined(_MSC_VER)
  36 #include <intrin.h>
  37 #endif
  38
  39 #include "c99_compat.h"
  40
  41 #ifdef __cplusplus
  42 extern "C" {
  43 #endif
  44
  45
  46 /**
  47  * Find first bit set in word.  Least significant bit is 1.
  48  * Return 0 if no bits set.
  49  */
  50 #ifdef HAVE___BUILTIN_FFS
  51 #define ffs __builtin_ffs
  52 #elif defined(_MSC_VER) && (_M_IX86 || _M_ARM || _M_AMD64 || _M_IA64)
  53 static inline
  54 int ffs(unsigned i)
  55 {
  56    unsigned long index;
  57    if (_BitScanForward(&index, i))
  58       return index + 1;
  59    else
  60       return 0;
  61 }
  62 #else
  63 extern
  64 int ffs(unsigned i);
  65 #endif
  66
  67 #ifdef HAVE___BUILTIN_FFSLL
  68 #define ffsll __builtin_ffsll
  69 #elif defined(_MSC_VER) && (_M_AMD64 || _M_ARM || _M_IA64)
  70 static inline int
  71 ffsll(uint64_t i)
  72 {
  73    unsigned long index;
  74    if (_BitScanForward64(&index, i))
  75       return index + 1;
  76    else
  77       return 0;
  78 }
  79 #else
  80 extern int
  81 ffsll(uint64_t val);
  82 #endif
  83
  84
  85 /* Destructively loop over all of the bits in a mask as in:
  86  *
  87  * while (mymask) {
  88  *   int i = u_bit_scan(&mymask);
  89  *   ... process element i
  90  * }
  91  *
  92  */
  93 static inline int
  94 u_bit_scan(unsigned *mask)
  95 {
  96    const int i = ffs(*mask) - 1;
  97    *mask ^= (1u << i);
  98    return i;
  99 }
 100
 101 static inline int
 102 u_bit_scan64(uint64_t *mask)
 103 {
 104    const int i = ffsll(*mask) - 1;
 105    *mask ^= (((uint64_t)1) << i);
 106    return i;
 107 }
 108
 109 /* For looping over a bitmask when you want to loop over consecutive bits
 110  * manually, for example:
 111  *
 112  * while (mask) {
 113  *    int start, count, i;
 114  *
 115  *    u_bit_scan_consecutive_range(&mask, &start, &count);
 116  *
 117  *    for (i = 0; i < count; i++)
 118  *       ... process element (start+i)
 119  * }
 120  */
 121 static inline void
 122 u_bit_scan_consecutive_range(unsigned *mask, int *start, int *count)
 123 {
 124    if (*mask == 0xffffffff) {
 125       *start = 0;
 126       *count = 32;
 127       *mask = 0;
 128       return;
 129    }
 130    *start = ffs(*mask) - 1;
 131    *count = ffs(~(*mask >> *start)) - 1;
 132    *mask &= ~(((1u << *count) - 1) << *start);
 133 }
 134
 135 static inline void
 136 u_bit_scan_consecutive_range64(uint64_t *mask, int *start, int *count)
 137 {
 138    if (*mask == ~0llu) {
 139       *start = 0;
 140       *count = 64;
 141       *mask = 0;
 142       return;
 143    }
 144    *start = ffsll(*mask) - 1;
 145    *count = ffsll(~(*mask >> *start)) - 1;
 146    *mask &= ~(((((uint64_t)1) << *count) - 1) << *start);
 147 }
 148
 149
 150 /**
 151  * Find last bit set in a word.  The least significant bit is 1.
 152  * Return 0 if no bits are set.
 153  * Essentially ffs() in the reverse direction.
 154  */
 155 static inline unsigned
 156 util_last_bit(unsigned u)
 157 {
 158 #if defined(HAVE___BUILTIN_CLZ)
 159    return u == 0 ? 0 : 32 - __builtin_clz(u);
 160 #else
 161    unsigned r = 0;
 162    while (u) {
 163       r++;
 164       u >>= 1;
 165    }
 166    return r;
 167 #endif
 168 }
 169
 170 /**
 171  * Find last bit set in a word.  The least significant bit is 1.
 172  * Return 0 if no bits are set.
 173  * Essentially ffsll() in the reverse direction.
 174  */
 175 static inline unsigned
 176 util_last_bit64(uint64_t u)
 177 {
 178 #if defined(HAVE___BUILTIN_CLZLL)
 179    return u == 0 ? 0 : 64 - __builtin_clzll(u);
 180 #else
 181    unsigned r = 0;
 182    while (u) {
 183       r++;
 184       u >>= 1;
 185    }
 186    return r;
 187 #endif
 188 }
 189
 190 /**
 191  * Find last bit in a word that does not match the sign bit. The least
 192  * significant bit is 1.
 193  * Return 0 if no bits are set.
 194  */
 195 static inline unsigned
 196 util_last_bit_signed(int i)
 197 {
 198    if (i >= 0)
 199       return util_last_bit(i);
 200    else
 201       return util_last_bit(~(unsigned)i);
 202 }
 203
 204 /* Returns a bitfield in which the first count bits starting at start are
 205  * set.
 206  */
 207 static inline unsigned
 208 u_bit_consecutive(unsigned start, unsigned count)
 209 {
 210    assert(start + count <= 32);
 211    if (count == 32)
 212       return ~0;
 213    return ((1u << count) - 1) << start;
 214 }
 215
 216
 217 #ifdef __cplusplus
 218 }
 219 #endif
 220
 221 #endif /* BITSCAN_H */