LCOV - code coverage report
Current view: top level - source/lib - bits.h (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 25 26 96.2 %
Date: 2022-03-08 13:03:03 Functions: 0 0 -

          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             : inline T Bit(size_t n)
      41             : {
      42           8 :     const T one = T(1);
      43           7 :     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           3 :     const T bit = Bit<T>(index);
      57           1 :     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       15457 :     const T bitsInT = sizeof(T)*CHAR_BIT;
      75       15437 :     const T allBits = (T)~T(0);
      76             :     // (shifts of at least bitsInT are undefined)
      77           0 :     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       12347 :     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        3111 :     const size_t numBits = (hi_idx - lo_idx)+1; // # bits to return
     100        3111 :     T result = T(num >> lo_idx);
     101        3099 :     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          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           1 :     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        2874 :     if(n == 0)
     168             :         return false;
     169        2874 :     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          10 :     T bit = 1;
     200           4 :     size_t log = 0;
     201         112 :     while(bit < x && bit != 0)   // must detect overflow
     202             :     {
     203         102 :         log++;
     204         102 :         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           4 :     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          30 :     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         143 :     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           1 :     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

Generated by: LCOV version 1.13