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 }
int get_highest_on_bit(unsigned short x)
Returns the index of the highest 1 bit in the word.
Definition: pbitops.I:259
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
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
int count_bits_in_word(unsigned short x)
Returns the number of 1 bits in the indicated word.
Definition: pbitops.I:18
int get_lowest_on_bit(unsigned short x)
Returns the index of the lowest 1 bit in the word.
Definition: pbitops.I:175
int get_next_higher_bit(unsigned short x)
Returns the smallest power of 2 greater than x.
Definition: pbitops.I:328