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