1 /* Copyright (C) 2010 Wildfire Games.
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:
11 * The above copyright notice and this permission notice shall be included
12 * in all copies or substantial portions of the Software.
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.
31 * value of bit number \<n\>.
36 * - T should be an unsigned type
37 * - n must be in [0, CHAR_BIT*sizeof(T)), else the result is undefined!
40 inline T
Bit(size_t n
)
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.
51 #define BIT(n) (1u << (n))
54 inline bool IsBitSet(T value
, size_t index
)
56 const T bit
= Bit
<T
>(index
);
57 return (value
& bit
) != 0;
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
67 * a mask that includes the lowest N bits
69 * @param numBits Number of bits in mask.
72 inline T
bit_mask(size_t numBits
)
74 const T bitsInT
= sizeof(T
)*CHAR_BIT
;
75 const T allBits
= (T
)~T(0);
76 // (shifts of at least bitsInT are undefined)
77 if(numBits
>= bitsInT
)
79 // (note: the previous allBits >> (bitsInT-numBits) is not safe
80 // because right-shifts of negative numbers are undefined.)
81 const T mask
= (T
)((T(1) << numBits
)-1);
87 * extract the value of bits hi_idx:lo_idx within num
89 * example: bits(0x69, 2, 5) == 0x0A
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.
97 inline T
bits(T num
, size_t lo_idx
, size_t hi_idx
)
99 const size_t numBits
= (hi_idx
- lo_idx
)+1; // # bits to return
100 T result
= T(num
>> lo_idx
);
101 result
= T(result
& bit_mask
<T
>(numBits
));
106 * set the value of bits hi_idx:lo_idx
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
113 inline T
SetBitsTo(T num
, size_t lo_idx
, size_t hi_idx
, size_t value
)
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
));
125 * @return number of 1-bits in mask.
126 * execution time is proportional to number of 1-bits in mask.
129 inline size_t SparsePopulationCount(T mask
)
134 mask
&= mask
-1; // clear least significant 1-bit
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]
148 static inline size_t PopulationCount(T x
)
150 cassert(!std::numeric_limits
<T
>::is_signed
);
151 const T mask
= T(~T(0));
152 x
-= (x
>> 1) & (mask
/3); // count 2 bits
153 x
= (x
& (mask
/15*3)) + ((x
>> 2) & (mask
/15*3)); // count 4 bits
154 x
= (x
+ (x
>> 4)) & (mask
/255*15); // count 8 bits
155 return T(x
* (mask
/255)) >> ((sizeof(T
)-1)*CHAR_BIT
);
161 * @return whether the given number is a power of two.
164 inline bool is_pow2(T n
)
166 // 0 would pass the test below but isn't a POT.
169 return (n
& (n
-1)) == 0;
172 // as above; intended for use in static_assert
173 #define IS_POW2(n) (((n) != 0) && ((n) & ((n)-1)) == 0)
176 inline T
LeastSignificantBit(T x
)
178 const T negX
= T(~x
+ 1); // 2's complement (avoids 'negating unsigned type' warning)
183 inline T
ClearLeastSignificantBit(T x
)
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.
197 inline size_t ceil_log2(T x
)
201 while(bit
< x
&& bit
!= 0) // must detect overflow
210 // compile-time variant of the above
214 enum { value
= 1 + CeilLog2
<(N
+1)/2>::value
};
233 * fast, uses the FPU normalization hardware.
235 * @param x (float) input; MUST be > 0, else results are undefined.
236 * @return floor of the base-2 logarithm (i.e. rounded down).
238 extern int floor_log2(const float x
);
241 * round up to next larger power of two.
244 inline T
round_up_to_pow2(T x
)
246 return T(1) << ceil_log2(x
);
250 * round down to next larger power of two.
253 inline T
round_down_to_pow2(T x
)
255 return T(1) << floor_log2(x
);
259 * round number up/down to the next given multiple.
261 * @param n Number to round.
262 * @param multiple Must be a power of two.
265 inline T
round_up(T n
, T multiple
)
267 ASSERT(is_pow2(multiple
));
268 const T result
= (n
+ multiple
-1) & ~(multiple
-1);
269 ASSERT(n
<= result
&& result
< n
+multiple
);
274 inline T
round_down(T n
, T multiple
)
276 ASSERT(is_pow2(multiple
));
277 const T result
= n
& ~(multiple
-1);
278 ASSERT(result
<= n
&& n
< result
+multiple
);
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))
288 inline T
MaxPowerOfTwoDivisor(T value
)
290 ASSERT(value
!= T(0));
292 for(size_t log2
= 0; log2
< sizeof(T
)*CHAR_BIT
; log2
++)
294 if(IsBitSet(value
, log2
))
298 DEBUG_WARN_ERR(ERR::LOGIC
); // unreachable (!= 0 => there is a set bit)
302 #endif // #ifndef INCLUDED_BITS