Line data Source code
1 : /* Copyright (C) 2010 Wildfire Games.
2 : *
3 : * Permission is hereby granted, free of charge, to any person obtaining
4 : * a copy of this software and associated documentation files (the
5 : * "Software"), to deal in the Software without restriction, including
6 : * without limitation the rights to use, copy, modify, merge, publish,
7 : * distribute, sublicense, and/or sell copies of the Software, and to
8 : * permit persons to whom the Software is furnished to do so, subject to
9 : * the following conditions:
10 : *
11 : * The above copyright notice and this permission notice shall be included
12 : * in all copies or substantial portions of the Software.
13 : *
14 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 : * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 : * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17 : * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18 : * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19 : * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20 : * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 : */
22 :
23 : /*
24 : * bit-twiddling.
25 : */
26 :
27 : #ifndef INCLUDED_BITS
28 : #define INCLUDED_BITS
29 :
30 : /**
31 : * value of bit number \<n\>.
32 : *
33 : * @param n bit index.
34 : *
35 : * requirements:
36 : * - T should be an unsigned type
37 : * - n must be in [0, CHAR_BIT*sizeof(T)), else the result is undefined!
38 : **/
39 : template<typename T>
40 36 : inline T Bit(size_t n)
41 : {
42 36 : const T one = T(1);
43 36 : return (T)(one << n);
44 : }
45 :
46 : /**
47 : * pretty much the same as Bit\<unsigned\>.
48 : * this is intended for the initialization of enum values, where a
49 : * compile-time constant is required.
50 : **/
51 : #define BIT(n) (1u << (n))
52 :
53 : template<typename T>
54 24 : inline bool IsBitSet(T value, size_t index)
55 : {
56 24 : const T bit = Bit<T>(index);
57 24 : return (value & bit) != 0;
58 : }
59 :
60 :
61 : // these are declared in the header and inlined to aid compiler optimizations
62 : // (they can easily end up being time-critical).
63 : // note: GCC can't inline extern functions, while VC's "Whole Program
64 : // Optimization" can.
65 :
66 : /**
67 : * a mask that includes the lowest N bits
68 : *
69 : * @param numBits Number of bits in mask.
70 : **/
71 : template<typename T>
72 15589 : inline T bit_mask(size_t numBits)
73 : {
74 15589 : const T bitsInT = sizeof(T)*CHAR_BIT;
75 15589 : const T allBits = (T)~T(0);
76 : // (shifts of at least bitsInT are undefined)
77 15589 : if(numBits >= bitsInT)
78 8 : return allBits;
79 : // (note: the previous allBits >> (bitsInT-numBits) is not safe
80 : // because right-shifts of negative numbers are undefined.)
81 15581 : const T mask = (T)((T(1) << numBits)-1);
82 15581 : return mask;
83 : }
84 :
85 :
86 : /**
87 : * extract the value of bits hi_idx:lo_idx within num
88 : *
89 : * example: bits(0x69, 2, 5) == 0x0A
90 : *
91 : * @param num number whose bits are to be extracted
92 : * @param lo_idx bit index of lowest bit to include
93 : * @param hi_idx bit index of highest bit to include
94 : * @return value of extracted bits.
95 : **/
96 : template<typename T>
97 3147 : inline T bits(T num, size_t lo_idx, size_t hi_idx)
98 : {
99 3147 : const size_t numBits = (hi_idx - lo_idx)+1; // # bits to return
100 3147 : T result = T(num >> lo_idx);
101 3147 : result = T(result & bit_mask<T>(numBits));
102 3147 : return result;
103 : }
104 :
105 : /**
106 : * set the value of bits hi_idx:lo_idx
107 : *
108 : * @param lo_idx bit index of lowest bit to include
109 : * @param hi_idx bit index of highest bit to include
110 : * @param value new value to be assigned to these bits
111 : **/
112 : template<typename T>
113 : inline T SetBitsTo(T num, size_t lo_idx, size_t hi_idx, size_t value)
114 : {
115 : const size_t numBits = (hi_idx - lo_idx)+1;
116 : ASSERT(value < (T(1) << numBits));
117 : const T mask = bit_mask<T>(numBits) << lo_idx;
118 : T result = num & ~mask;
119 : result = T(result | (value << lo_idx));
120 : return result;
121 : }
122 :
123 :
124 : /**
125 : * @return number of 1-bits in mask.
126 : * execution time is proportional to number of 1-bits in mask.
127 : **/
128 : template<typename T>
129 : inline size_t SparsePopulationCount(T mask)
130 : {
131 : size_t num1Bits = 0;
132 : while(mask)
133 : {
134 : mask &= mask-1; // clear least significant 1-bit
135 : num1Bits++;
136 : }
137 :
138 : return num1Bits;
139 : }
140 :
141 : /**
142 : * @return number of 1-bits in mask.
143 : * execution time is logarithmic in the total number of bits.
144 : * supports up to 128-bit integers (if their arithmetic operators are defined).
145 : * [http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel]
146 : **/
147 : template<typename T>
148 14 : static inline size_t PopulationCount(T x)
149 : {
150 : cassert(!std::numeric_limits<T>::is_signed);
151 14 : const T mask = T(~T(0));
152 14 : x -= (x >> 1) & (mask/3); // count 2 bits
153 14 : x = (x & (mask/15*3)) + ((x >> 2) & (mask/15*3)); // count 4 bits
154 14 : x = (x + (x >> 4)) & (mask/255*15); // count 8 bits
155 14 : return T(x * (mask/255)) >> ((sizeof(T)-1)*CHAR_BIT);
156 : }
157 :
158 :
159 :
160 : /**
161 : * @return whether the given number is a power of two.
162 : **/
163 : template<typename T>
164 6416 : inline bool is_pow2(T n)
165 : {
166 : // 0 would pass the test below but isn't a POT.
167 6416 : if(n == 0)
168 1 : return false;
169 6415 : return (n & (n-1)) == 0;
170 : }
171 :
172 : // as above; intended for use in static_assert
173 : #define IS_POW2(n) (((n) != 0) && ((n) & ((n)-1)) == 0)
174 :
175 : template<typename T>
176 : inline T LeastSignificantBit(T x)
177 : {
178 : const T negX = T(~x + 1); // 2's complement (avoids 'negating unsigned type' warning)
179 : return x & negX;
180 : }
181 :
182 : template<typename T>
183 : inline T ClearLeastSignificantBit(T x)
184 : {
185 : return x & (x-1);
186 : }
187 :
188 :
189 : /**
190 : * ceil(log2(x))
191 : *
192 : * @param x (unsigned integer)
193 : * @return ceiling of the base-2 logarithm (i.e. rounded up) or
194 : * zero if the input is zero.
195 : **/
196 : template<typename T>
197 31 : inline size_t ceil_log2(T x)
198 : {
199 31 : T bit = 1;
200 31 : size_t log = 0;
201 379 : while(bit < x && bit != 0) // must detect overflow
202 : {
203 174 : log++;
204 174 : bit *= 2;
205 : }
206 :
207 31 : return log;
208 : }
209 :
210 : // compile-time variant of the above
211 : template<size_t N>
212 : struct CeilLog2
213 : {
214 : enum { value = 1 + CeilLog2<(N+1)/2>::value };
215 : };
216 :
217 : template<>
218 : struct CeilLog2<1>
219 : {
220 : enum { value = 0 };
221 : };
222 :
223 : template<>
224 : struct CeilLog2<0>
225 : {
226 : enum { value = 0 };
227 : };
228 :
229 :
230 :
231 : /**
232 : * floor(log2(f))
233 : * fast, uses the FPU normalization hardware.
234 : *
235 : * @param x (float) input; MUST be > 0, else results are undefined.
236 : * @return floor of the base-2 logarithm (i.e. rounded down).
237 : **/
238 : extern int floor_log2(const float x);
239 :
240 : /**
241 : * round up to next larger power of two.
242 : **/
243 : template<typename T>
244 5 : inline T round_up_to_pow2(T x)
245 : {
246 5 : return T(1) << ceil_log2(x);
247 : }
248 :
249 : /**
250 : * round down to next larger power of two.
251 : **/
252 : template<typename T>
253 33 : inline T round_down_to_pow2(T x)
254 : {
255 33 : return T(1) << floor_log2(x);
256 : }
257 :
258 : /**
259 : * round number up/down to the next given multiple.
260 : *
261 : * @param n Number to round.
262 : * @param multiple Must be a power of two.
263 : **/
264 : template<typename T>
265 3440 : inline T round_up(T n, T multiple)
266 : {
267 3440 : ASSERT(is_pow2(multiple));
268 3440 : const T result = (n + multiple-1) & ~(multiple-1);
269 3440 : ASSERT(n <= result && result < n+multiple);
270 3440 : return result;
271 : }
272 :
273 : template<typename T>
274 7 : inline T round_down(T n, T multiple)
275 : {
276 7 : ASSERT(is_pow2(multiple));
277 7 : const T result = n & ~(multiple-1);
278 7 : ASSERT(result <= n && n < result+multiple);
279 7 : return result;
280 : }
281 :
282 : // evaluates to an expression suitable as an initializer
283 : // for constant static data members.
284 : #define ROUND_UP(n, multiple) (((n) + (multiple)-1) & ~((multiple)-1))
285 :
286 :
287 : template<typename T>
288 : inline T MaxPowerOfTwoDivisor(T value)
289 : {
290 : ASSERT(value != T(0));
291 :
292 : for(size_t log2 = 0; log2 < sizeof(T)*CHAR_BIT; log2++)
293 : {
294 : if(IsBitSet(value, log2))
295 : return T(1) << log2;
296 : }
297 :
298 : DEBUG_WARN_ERR(ERR::LOGIC); // unreachable (!= 0 => there is a set bit)
299 : return 0;
300 : }
301 :
302 : #endif // #ifndef INCLUDED_BITS
|
