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