source/lib/bits.h

   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 inline T Bit(size_t n)
  41 {
  42         const T one = T(1);
  43         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 inline bool IsBitSet(T value, size_t index)
  55 {
  56         const T bit = Bit<T>(index);
  57         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 inline T bit_mask(size_t numBits)
  73 {
  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)
  78                 return allBits;
  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);
  82         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 inline T bits(T num, size_t lo_idx, size_t hi_idx)
  98 {
  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));
 102         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 static inline size_t PopulationCount(T x)
 149 {
 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);
 156 }
 157
 158
 159
 160 /**
 161  * @return whether the given number is a power of two.
 162  **/
 163 template<typename T>
 164 inline bool is_pow2(T n)
 165 {
 166         // 0 would pass the test below but isn't a POT.
 167         if(n == 0)
 168                 return false;
 169         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 inline size_t ceil_log2(T x)
 198 {
 199         T bit = 1;
 200         size_t log = 0;
 201         while(bit < x && bit != 0)      // must detect overflow
 202         {
 203                 log++;
 204                 bit *= 2;
 205         }
 206
 207         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 inline T round_up_to_pow2(T x)
 245 {
 246         return T(1) << ceil_log2(x);
 247 }
 248
 249 /**
 250  * round down to next larger power of two.
 251  **/
 252 template<typename T>
 253 inline T round_down_to_pow2(T x)
 254 {
 255         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 inline T round_up(T n, T multiple)
 266 {
 267         ASSERT(is_pow2(multiple));
 268         const T result = (n + multiple-1) & ~(multiple-1);
 269         ASSERT(n <= result && result < n+multiple);
 270         return result;
 271 }
 272
 273 template<typename T>
 274 inline T round_down(T n, T multiple)
 275 {
 276         ASSERT(is_pow2(multiple));
 277         const T result = n & ~(multiple-1);
 278         ASSERT(result <= n && n < result+multiple);
 279         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