src/base/bitfield.hh

   1 /*
   2  * Copyright (c) 2017, 2019 ARM Limited
   3  * All rights reserved
   4  *
   5  * The license below extends only to copyright in the software and shall
   6  * not be construed as granting a license to any other intellectual
   7  * property including but not limited to intellectual property relating
   8  * to a hardware implementation of the functionality of the software
   9  * licensed hereunder.  You may use the software subject to the license
  10  * terms below provided that you ensure that this notice is replicated
  11  * unmodified and in its entirety in all distributions of the software,
  12  * modified or unmodified, in source code or in binary form.
  13  *
  14  * Copyright (c) 2003-2005 The Regents of The University of Michigan
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions are
  19  * met: redistributions of source code must retain the above copyright
  20  * notice, this list of conditions and the following disclaimer;
  21  * redistributions in binary form must reproduce the above copyright
  22  * notice, this list of conditions and the following disclaimer in the
  23  * documentation and/or other materials provided with the distribution;
  24  * neither the name of the copyright holders nor the names of its
  25  * contributors may be used to endorse or promote products derived from
  26  * this software without specific prior written permission.
  27  *
  28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  31  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  32  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  33  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  34  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  35  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  36  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  37  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  38  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  39  */
  40
  41 #ifndef __BASE_BITFIELD_HH__
  42 #define __BASE_BITFIELD_HH__
  43
  44 #include <inttypes.h>
  45 #include <cassert>
  46 #include <cstddef>
  47 #include <type_traits>
  48
  49 /** Lookup table used for High Speed bit reversing */
  50 extern const uint8_t reverseLookUpTable[];
  51
  52 /**
  53  * Generate a 64-bit mask of 'nbits' 1s, right justified. If a number of bits
  54  * greater than 64 is given, it is truncated to 64.
  55  *
  56  * @param nbits The number of bits set in the mask.
  57  *
  58  * @ingroup api_bitfield
  59  */
  60 inline uint64_t
  61 mask(int nbits)
  62 {
  63     return (nbits >= 64) ? (uint64_t)-1LL : (1ULL << nbits) - 1;
  64 }
  65
  66 /**
  67  * Extract the bitfield from position 'first' to 'last' (inclusive)
  68  * from 'val' and right justify it.  MSB is numbered 63, LSB is 0.
  69  *
  70  * @ingroup api_bitfield
  71  */
  72 template <class T>
  73 inline
  74 T
  75 bits(T val, int first, int last)
  76 {
  77     int nbits = first - last + 1;
  78     assert((first - last) >= 0);
  79     return (val >> last) & mask(nbits);
  80 }
  81
  82 /**
  83  * Extract the bit from this position from 'val' and right justify it.
  84  *
  85  * @ingroup api_bitfield
  86  */
  87 template <class T>
  88 inline
  89 T
  90 bits(T val, int bit)
  91 {
  92     return bits(val, bit, bit);
  93 }
  94
  95 /**
  96  * Mask off the given bits in place like bits() but without shifting.
  97  * msb = 63, lsb = 0
  98  *
  99  * @ingroup api_bitfield
 100  */
 101 template <class T>
 102 inline
 103 T
 104 mbits(T val, int first, int last)
 105 {
 106     return val & (mask(first+1) & ~mask(last));
 107 }
 108
 109 /**
 110  * @ingroup api_bitfield
 111  */
 112 inline uint64_t
 113 mask(int first, int last)
 114 {
 115     return mbits((uint64_t)-1LL, first, last);
 116 }
 117
 118 /**
 119  * Sign-extend an N-bit value to 64 bits.
 120  *
 121  * @ingroup api_bitfield
 122  */
 123 template <int N>
 124 inline
 125 uint64_t
 126 sext(uint64_t val)
 127 {
 128     int sign_bit = bits(val, N-1, N-1);
 129     return sign_bit ? (val | ~mask(N)) : val;
 130 }
 131
 132 /**
 133  * Returns val with bits first to last set to the LSBs of bit_val
 134  *
 135  * E.g.:
 136  * first: 7
 137  * last:  4
 138  * val:      0xFFFF
 139  * bit_val:  0x0000
 140  * returned: 0xFF0F
 141  *
 142  * @ingroup api_bitfield
 143  */
 144 template <class T, class B>
 145 inline
 146 T
 147 insertBits(T val, int first, int last, B bit_val)
 148 {
 149     T t_bit_val = bit_val;
 150     assert((first - last) >= 0);
 151     T bmask = mask(first - last + 1) << last;
 152     return ((t_bit_val << last) & bmask) | (val & ~bmask);
 153 }
 154
 155 /**
 156  * Overloaded for access to only one bit in value
 157  *
 158  * @ingroup api_bitfield
 159  */
 160 template <class T, class B>
 161 inline
 162 T
 163 insertBits(T val, int bit, B bit_val)
 164 {
 165     return insertBits(val, bit, bit, bit_val);
 166 }
 167
 168 /**
 169  * A convenience function to replace bits first to last of val with bit_val
 170  * in place. It is functionally equivalent to insertBits.
 171  *
 172  * \note "first" is the MSB and "last" is the LSB. "first" >= "last"
 173  *
 174  * @ingroup api_bitfield
 175  */
 176 template <class T, class B>
 177 inline
 178 void
 179 replaceBits(T& val, int first, int last, B bit_val)
 180 {
 181     val = insertBits(val, first, last, bit_val);
 182 }
 183
 184 /**
 185  * Overloaded function to allow to access only 1 bit
 186  *
 187  * @ingroup api_bitfield
 188  */
 189 template <class T, class B>
 190 inline
 191 void
 192 replaceBits(T& val, int bit, B bit_val)
 193 {
 194     val = insertBits(val, bit, bit, bit_val);
 195 }
 196
 197 /**
 198  * Takes a variable lenght word and returns the mirrored version
 199  * (Bit by bit, LSB=>MSB).
 200  *
 201  * algorithm from
 202  * http://graphics.stanford.edu/~seander/bithacks.html
 203  * #ReverseBitsByLookupTable
 204  *
 205  * @param val: variable lenght word
 206  * @param size: number of bytes to mirror
 207  * @return mirrored word
 208  *
 209  * @ingroup api_bitfield
 210  */
 211 template <class T>
 212 T
 213 reverseBits(T val, std::size_t size = sizeof(T))
 214 {
 215     static_assert(std::is_integral<T>::value, "Expecting an integer type");
 216
 217     assert(size <= sizeof(T));
 218
 219     T output = 0;
 220     for (auto byte = 0; byte < size; byte++, val = static_cast<T>(val >> 8)) {
 221         output = (output << 8) | reverseLookUpTable[val & 0xFF];
 222     }
 223
 224     return output;
 225 }
 226
 227 /**
 228  * Returns the bit position of the MSB that is set in the input
 229  *
 230  * @ingroup api_bitfield
 231  */
 232 inline
 233 int
 234 findMsbSet(uint64_t val) {
 235     int msb = 0;
 236     if (!val)
 237         return 0;
 238     if (bits(val, 63,32)) { msb += 32; val >>= 32; }
 239     if (bits(val, 31,16)) { msb += 16; val >>= 16; }
 240     if (bits(val, 15,8))  { msb += 8;  val >>= 8;  }
 241     if (bits(val, 7,4))   { msb += 4;  val >>= 4;  }
 242     if (bits(val, 3,2))   { msb += 2;  val >>= 2;  }
 243     if (bits(val, 1,1))   { msb += 1; }
 244     return msb;
 245 }
 246
 247 /**
 248  * Returns the bit position of the LSB that is set in the input
 249  *
 250  * @ingroup api_bitfield
 251  */
 252 inline int
 253 findLsbSet(uint64_t val) {
 254     int lsb = 0;
 255     if (!val)
 256         return sizeof(val) * 8;
 257     if (!bits(val, 31,0)) { lsb += 32; val >>= 32; }
 258     if (!bits(val, 15,0)) { lsb += 16; val >>= 16; }
 259     if (!bits(val, 7,0))  { lsb += 8;  val >>= 8;  }
 260     if (!bits(val, 3,0))  { lsb += 4;  val >>= 4;  }
 261     if (!bits(val, 1,0))  { lsb += 2;  val >>= 2;  }
 262     if (!bits(val, 0,0))  { lsb += 1; }
 263     return lsb;
 264 }
 265
 266 /**
 267  * Checks if a number is a power of two, or zero.
 268  *
 269  * @ingroup api_bitfield
 270  */
 271 template <class T>
 272 inline bool
 273 isPow2(T v) {
 274    return (v & (v - 1)) == (T)0;
 275 }
 276
 277 /**
 278  * Returns the number of set ones in the provided value.
 279  * PD algorithm from
 280  * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
 281  *
 282  * @ingroup api_bitfield
 283  */
 284 inline int
 285 popCount(uint64_t val) {
 286 #ifndef __has_builtin
 287     #define __has_builtin(foo) 0
 288 #endif
 289 #if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl))
 290     return __builtin_popcountl(val);
 291 #else
 292     const uint64_t m1 = 0x5555555555555555;  // ..010101b
 293     const uint64_t m2 = 0x3333333333333333;  // ..110011b
 294     const uint64_t m4 = 0x0f0f0f0f0f0f0f0f;  // ..001111b
 295     const uint64_t sum = 0x0101010101010101;
 296
 297     val -= (val >> 1) & m1;               // 2 bits count -> 2 bits
 298     val = (val & m2) + ((val >> 2) & m2); // 4 bits count -> 4 bits
 299     val = (val + (val >> 4)) & m4;        // 8 bits count -> 8 bits
 300     return (val * sum) >> 56;             // horizontal sum
 301 #endif // defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl))
 302 }
 303
 304 /**
 305  * Align to the next highest power of two.
 306  *
 307  * The number passed in is aligned to the next highest power of two,
 308  * if it is not already a power of two. Please note that if 0 is
 309  * passed in, 0 is returned.
 310  *
 311  * This code has been modified from the following:
 312  * http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
 313  *
 314  * @ingroup api_bitfield
 315  */
 316 inline uint64_t alignToPowerOfTwo(uint64_t val)
 317 {
 318     val--;
 319     val |= val >> 1;
 320     val |= val >> 2;
 321     val |= val >> 4;
 322     val |= val >> 8;
 323     val |= val >> 16;
 324     val |= val >> 32;
 325     val++;
 326
 327     return val;
 328 };
 329
 330 /**
 331  * Count trailing zeros in a 32-bit value.
 332  *
 333  * @param An input value
 334  * @return The number of trailing zeros or 32 if the value is zero.
 335  *
 336  * @ingroup api_bitfield
 337  */
 338 inline int ctz32(uint32_t value)
 339 {
 340     return value ? __builtin_ctzl(value) : 32;
 341 }
 342
 343 /**
 344  * Count trailing zeros in a 64-bit value.
 345  *
 346  * @param An input value
 347  * @return The number of trailing zeros or 64 if the value is zero.
 348  *
 349  * @ingroup api_bitfield
 350  */
 351 inline int ctz64(uint64_t value)
 352 {
 353     return value ? __builtin_ctzll(value) : 64;
 354 }
 355
 356 #endif // __BASE_BITFIELD_HH__