Panda3D

pbitops.I
Go to the documentation of this file.
1 /**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file pbitops.I
10 * @author drose
11 * @date 2008-05-10
12 */
13
14 /**
15 * Returns the number of 1 bits in the indicated word.
16 */
17 INLINE int
18 count_bits_in_word(unsigned short x) {
19 return (int)num_bits_on[x];
20 }
21
22 /**
23 * Returns the number of 1 bits in the indicated word.
24 */
25 INLINE int
26 count_bits_in_word(unsigned int x) {
27 #if defined(__GNUC__) && defined(__POPCNT__)
28 return __builtin_popcount(x);
29 #else
30 return (int)num_bits_on[x & 0xffff] + (int)num_bits_on[(x >> 16) & 0xffff];
31 #endif
32 }
33
34 /**
35 * Returns the number of 1 bits in the indicated word.
36 */
37 INLINE int
38 count_bits_in_word(unsigned long x) {
39 #if defined(__GNUC__) && defined(__POPCNT__)
40 return __builtin_popcountl(x);
41 #elif defined(_LP64)
42 return count_bits_in_word((unsigned int)x) + count_bits_in_word((unsigned int)(x >> 32));
43 #else
44 return count_bits_in_word((unsigned int)x);
45 #endif
46 }
47
48 /**
49 * Returns the number of 1 bits in the indicated word.
50 */
51 INLINE int
52 count_bits_in_word(unsigned long long x) {
53 #if defined(__GNUC__) && defined(__POPCNT__)
54 return __builtin_popcountll(x);
55 #else
56 return count_bits_in_word((unsigned int)x) + count_bits_in_word((unsigned int)(x >> 32));
57 #endif
58 }
59
60 /**
61 * Returns a value such that every bit at or below the highest bit in x is 1.
62 */
63 INLINE unsigned short
64 flood_bits_down(unsigned short x) {
65 x |= (x >> 1);
66 x |= (x >> 2);
67 x |= (x >> 4);
68 x |= (x >> 8);
69 return x;
70 }
71
72 /**
73 * Returns a value such that every bit at or below the highest bit in x is 1.
74 */
75 INLINE unsigned int
76 flood_bits_down(unsigned int x) {
77 x |= (x >> 1);
78 x |= (x >> 2);
79 x |= (x >> 4);
80 x |= (x >> 8);
81 x |= (x >> 16);
82 return x;
83 }
84
85 /**
86 * Returns a value such that every bit at or below the highest bit in x is 1.
87 */
88 INLINE unsigned long
89 flood_bits_down(unsigned long x) {
90 x |= (x >> 1);
91 x |= (x >> 2);
92 x |= (x >> 4);
93 x |= (x >> 8);
94 x |= (x >> 16);
95 #if defined(_LP64) || defined(__LP64__)
96 x |= (x >> 32);
97 #endif
98 return x;
99 }
100
101 /**
102 * Returns a value such that every bit at or below the highest bit in x is 1.
103 */
104 INLINE unsigned long long
105 flood_bits_down(unsigned long long x) {
106 x |= (x >> 1);
107 x |= (x >> 2);
108 x |= (x >> 4);
109 x |= (x >> 8);
110 x |= (x >> 16);
111 x |= (x >> 32);
112 return x;
113 }
114
115 /**
116 * Returns a value such that every bit at or above the highest bit in x is 1.
117 */
118 INLINE unsigned short
119 flood_bits_up(unsigned short x) {
120 x |= (x << 1);
121 x |= (x << 2);
122 x |= (x << 4);
123 x |= (x << 8);
124 return x;
125 }
126
127 /**
128 * Returns a value such that every bit at or above the highest bit in x is 1.
129 */
130 INLINE unsigned int
131 flood_bits_up(unsigned int x) {
132 x |= (x << 1);
133 x |= (x << 2);
134 x |= (x << 4);
135 x |= (x << 8);
136 x |= (x << 16);
137 return x;
138 }
139
140 /**
141 * Returns a value such that every bit at or above the highest bit in x is 1.
142 */
143 INLINE unsigned long
144 flood_bits_up(unsigned long x) {
145 x |= (x << 1);
146 x |= (x << 2);
147 x |= (x << 4);
148 x |= (x << 8);
149 x |= (x << 16);
150 #if defined(_LP64) || defined(__LP64__)
151 x |= (x << 32);
152 #endif
153 return x;
154 }
155
156 /**
157 * Returns a value such that every bit at or above the highest bit in x is 1.
158 */
159 INLINE unsigned long long
160 flood_bits_up(unsigned long long x) {
161 x |= (x << 1);
162 x |= (x << 2);
163 x |= (x << 4);
164 x |= (x << 8);
165 x |= (x << 16);
166 x |= (x << 32);
167 return x;
168 }
169
170 /**
171 * Returns the index of the lowest 1 bit in the word. Returns -1 if there are
172 * no 1 bits.
173 */
174 INLINE int
175 get_lowest_on_bit(unsigned short x) {
176 #if defined(_MSC_VER)
177 unsigned long result;
178 return (_BitScanForward(&result, (unsigned long) x) == 0) ? -1 : result;
179 #elif defined(__GNUC__)
180 return __builtin_ffs((int) x) - 1;
181 #else
182 if (x == 0) {
183 return -1;
184 }
185
186 unsigned short w = (x & (~x + 1));
187 return (int)num_bits_on[w - 1];
188 #endif
189 }
190
191 /**
192 * Returns the index of the lowest 1 bit in the word. Returns -1 if there are
193 * no 1 bits.
194 */
195 INLINE int
196 get_lowest_on_bit(unsigned int x) {
197 #if defined(_MSC_VER)
198 unsigned long result;
199 return (_BitScanForward(&result, (unsigned long) x) == 0) ? -1 : result;
200 #elif defined(__GNUC__)
201 return __builtin_ffs((int) x) - 1;
202 #else
203 if (x == 0) {
204 return -1;
205 }
206
207 unsigned int w = (x & (~x + 1));
208 return count_bits_in_word(w - 1);
209 #endif
210 }
211
212 /**
213 * Returns the index of the lowest 1 bit in the word. Returns -1 if there are
214 * no 1 bits.
215 */
216 INLINE int
217 get_lowest_on_bit(unsigned long x) {
218 #if defined(_MSC_VER) && defined(_M_X64)
219 unsigned long result;
220 return (_BitScanForward(&result, x) == 0) ? -1 : result;
221 #elif defined(__GNUC__)
222 return __builtin_ffsl((long) x) - 1;
223 #else
224 if (x == 0) {
225 return -1;
226 }
227
228 unsigned long w = (x & (~x + 1));
229 return count_bits_in_word(w - 1);
230 #endif
231 }
232
233 /**
234 * Returns the index of the lowest 1 bit in the word. Returns -1 if there are
235 * no 1 bits.
236 */
237 INLINE int
238 get_lowest_on_bit(unsigned long long x) {
239 #if defined(_MSC_VER) && defined(_M_X64)
240 unsigned long result;
241 return (_BitScanForward64(&result, (unsigned __int64) x) == 0) ? -1 : result;
242 #elif defined(__GNUC__)
243 return __builtin_ffsll((long long) x) - 1;
244 #else
245 if (x == 0) {
246 return -1;
247 }
248
249 unsigned long long w = (x & (~x + 1));
250 return count_bits_in_word(w - 1);
251 #endif
252 }
253
254 /**
255 * Returns the index of the highest 1 bit in the word. Returns -1 if there
256 * are no 1 bits.
257 */
258 INLINE int
259 get_highest_on_bit(unsigned short x) {
260 #if defined(_MSC_VER)
261 unsigned long result;
262 return (_BitScanReverse(&result, (unsigned long) x) == 0) ? -1 : result;
263 #elif defined(__GNUC__)
264 return (x == 0) ? -1 : 31 - __builtin_clz((unsigned int) x);
265 #else
266 unsigned short w = flood_bits_down(x);
267 return count_bits_in_word(w) - 1;
268 #endif
269 }
270
271 /**
272 * Returns the index of the highest 1 bit in the word. Returns -1 if there
273 * are no 1 bits.
274 */
275 INLINE int
276 get_highest_on_bit(unsigned int x) {
277 #if defined(_MSC_VER)
278 unsigned long result;
279 return (_BitScanReverse(&result, (unsigned long) x) == 0) ? -1 : result;
280 #elif defined(__GNUC__)
281 return (x == 0) ? -1 : 31 - __builtin_clz(x);
282 #else
283 unsigned int w = flood_bits_down(x);
284 return count_bits_in_word(w) - 1;
285 #endif
286 }
287
288 /**
289 * Returns the index of the highest 1 bit in the word. Returns -1 if there
290 * are no 1 bits.
291 */
292 INLINE int
293 get_highest_on_bit(unsigned long x) {
294 #if defined(_MSC_VER) && defined(_M_X64)
295 unsigned long result;
296 return (_BitScanReverse(&result, (unsigned long) x) == 0) ? -1 : result;
297 #elif defined(__GNUC__)
298 return (x == 0) ? -1 : 63 - __builtin_clzl(x);
299 #else
300 unsigned long long w = flood_bits_down(x);
301 return count_bits_in_word(w) - 1;
302 #endif
303 }
304
305 /**
306 * Returns the index of the highest 1 bit in the word. Returns -1 if there
307 * are no 1 bits.
308 */
309 INLINE int
310 get_highest_on_bit(unsigned long long x) {
311 #if defined(_MSC_VER) && defined(_M_X64)
312 unsigned long result;
313 return (_BitScanReverse64(&result, (unsigned __int64) x) == 0) ? -1 : result;
314 #elif defined(__GNUC__)
315 return (x == 0) ? -1 : 63 - __builtin_clzll(x);
316 #else
317 unsigned long long w = flood_bits_down(x);
318 return count_bits_in_word(w) - 1;
319 #endif
320 }
321
322 /**
323 * Returns the smallest power of 2 greater than x.
324 *
325 * Returns the smallest number n such that (1 << n) is larger than x.
326 */
327 INLINE int
328 get_next_higher_bit(unsigned short x) {
329 return get_highest_on_bit(x) + 1;
330 }
331
332 /**
333 * Returns the smallest power of 2 greater than x.
334 *
335 * Returns the smallest number n such that (1 << n) is larger than x.
336 */
337 INLINE int
338 get_next_higher_bit(unsigned int x) {
339 return get_highest_on_bit(x) + 1;
340 }
341
342 /**
343 * Returns the smallest power of 2 greater than x.
344 *
345 * Returns the smallest number n such that (1 << n) is larger than x.
346 */
347 INLINE int
348 get_next_higher_bit(unsigned long x) {
349 return get_highest_on_bit(x) + 1;
350 }
351
352 /**
353 * Returns the smallest power of 2 greater than x.
354 *
355 * Returns the smallest number n such that (1 << n) is larger than x.
356 */
357 INLINE int
358 get_next_higher_bit(unsigned long long x) {
359 return get_highest_on_bit(x) + 1;
360 }
get_highest_on_bit
int get_highest_on_bit(unsigned short x)
Returns the index of the highest 1 bit in the word.
Definition: pbitops.I:259
flood_bits_down
unsigned short flood_bits_down(unsigned short x)
Returns a value such that every bit at or below the highest bit in x is 1.
Definition: pbitops.I:64
flood_bits_up
unsigned short flood_bits_up(unsigned short x)
Returns a value such that every bit at or above the highest bit in x is 1.
Definition: pbitops.I:119
count_bits_in_word
int count_bits_in_word(unsigned short x)
Returns the number of 1 bits in the indicated word.
Definition: pbitops.I:18
get_lowest_on_bit
int get_lowest_on_bit(unsigned short x)
Returns the index of the lowest 1 bit in the word.
Definition: pbitops.I:175
get_next_higher_bit
int get_next_higher_bit(unsigned short x)
Returns the smallest power of 2 greater than x.
Definition: pbitops.I:328