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 static inline uint64_t 230 u_bit_consecutive64(unsigned start, unsigned count) 231 { 232 assert(start + count <= 64); 233 if (count == 64) 234 return ~(uint64_t)0; 235 return (((uint64_t)1 << count) - 1) << start; 236 } 237 238 239 #ifdef __cplusplus 240 } 241 #endif 242 243 #endif /* BITSCAN_H */ 244
