• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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(int 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(int 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(long long int 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(long long int 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
u_bit_scan(unsigned * mask)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
u_bit_scan64(uint64_t * mask)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
u_bit_scan_consecutive_range(unsigned * mask,int * start,int * count)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
u_bit_scan_consecutive_range64(uint64_t * mask,int * start,int * count)137 u_bit_scan_consecutive_range64(uint64_t *mask, int *start, int *count)
138 {
139    if (*mask == ~0ull) {
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
util_last_bit(unsigned u)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
util_last_bit64(uint64_t u)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
util_last_bit_signed(int i)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
u_bit_consecutive(unsigned start,unsigned count)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
u_bit_consecutive64(unsigned start,unsigned count)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