src/base/bitfield.hh

   1 /*
   2  * Copyright (c) 2017 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  * Authors: Steve Reinhardt
  41  *          Nathan Binkert
  42  *          Giacomo Travaglini
  43  */
  44
  45 #ifndef __BASE_BITFIELD_HH__
  46 #define __BASE_BITFIELD_HH__
  47
  48 #include <inttypes.h>
  49 #include <cassert>
  50 #include <cstddef>
  51 #include <type_traits>
  52
  53 /** Lookup table used for High Speed bit reversing */
  54 extern const uint8_t reverseLookUpTable[];
  55
  56 /**
  57  * Generate a 64-bit mask of 'nbits' 1s, right justified.
  58  */
  59 inline uint64_t
  60 mask(int nbits)
  61 {
  62     return (nbits == 64) ? (uint64_t)-1LL : (1ULL << nbits) - 1;
  63 }
  64
  65 /**
  66  * Extract the bitfield from position 'first' to 'last' (inclusive)
  67  * from 'val' and right justify it.  MSB is numbered 63, LSB is 0.
  68  */
  69 template <class T>
  70 inline
  71 T
  72 bits(T val, int first, int last)
  73 {
  74     int nbits = first - last + 1;
  75     return (val >> last) & mask(nbits);
  76 }
  77
  78 /**
  79  * Extract the bit from this position from 'val' and right justify it.
  80  */
  81 template <class T>
  82 inline
  83 T
  84 bits(T val, int bit)
  85 {
  86     return bits(val, bit, bit);
  87 }
  88
  89 /**
  90  * Mask off the given bits in place like bits() but without shifting.
  91  * msb = 63, lsb = 0
  92  */
  93 template <class T>
  94 inline
  95 T
  96 mbits(T val, int first, int last)
  97 {
  98     return val & (mask(first+1) & ~mask(last));
  99 }
 100
 101 inline uint64_t
 102 mask(int first, int last)
 103 {
 104     return mbits((uint64_t)-1LL, first, last);
 105 }
 106
 107 /**
 108  * Sign-extend an N-bit value to 64 bits.
 109  */
 110 template <int N>
 111 inline
 112 uint64_t
 113 sext(uint64_t val)
 114 {
 115     int sign_bit = bits(val, N-1, N-1);
 116     return sign_bit ? (val | ~mask(N)) : val;
 117 }
 118
 119 /**
 120  * Return val with bits first to last set to bit_val
 121  */
 122 template <class T, class B>
 123 inline
 124 T
 125 insertBits(T val, int first, int last, B bit_val)
 126 {
 127     T t_bit_val = bit_val;
 128     T bmask = mask(first - last + 1) << last;
 129     return ((t_bit_val << last) & bmask) | (val & ~bmask);
 130 }
 131
 132 /**
 133  * Overloaded for access to only one bit in value
 134  */
 135 template <class T, class B>
 136 inline
 137 T
 138 insertBits(T val, int bit, B bit_val)
 139 {
 140     return insertBits(val, bit, bit, bit_val);
 141 }
 142
 143 /**
 144  * A convenience function to replace bits first to last of val with bit_val
 145  * in place.
 146  */
 147 template <class T, class B>
 148 inline
 149 void
 150 replaceBits(T& val, int first, int last, B bit_val)
 151 {
 152     val = insertBits(val, first, last, bit_val);
 153 }
 154
 155 /** Overloaded function to allow to access only 1 bit*/
 156 template <class T, class B>
 157 inline
 158 void
 159 replaceBits(T& val, int bit, B bit_val)
 160 {
 161     val = insertBits(val, bit, bit, bit_val);
 162 }
 163
 164 /**
 165  * Takes a variable lenght word and returns the mirrored version
 166  * (Bit by bit, LSB=>MSB).
 167  *
 168  * algorithm from
 169  * http://graphics.stanford.edu/~seander/bithacks.html
 170  * #ReverseBitsByLookupTable
 171  *
 172  * @param val: variable lenght word
 173  * @param size: number of bytes to mirror
 174  * @return mirrored word
 175  */
 176 template <class T>
 177 T
 178 reverseBits(T val, std::size_t size = sizeof(T))
 179 {
 180     static_assert(std::is_integral<T>::value, "Expecting an integer type");
 181
 182     assert(size <= sizeof(T));
 183
 184     T output = 0;
 185     for (auto byte = 0; byte < size; byte++, val >>= 8) {
 186         output = (output << 8) | reverseLookUpTable[val & 0xFF];
 187     }
 188
 189     return output;
 190 }
 191
 192 /**
 193  * Returns the bit position of the MSB that is set in the input
 194  */
 195 inline
 196 int
 197 findMsbSet(uint64_t val) {
 198     int msb = 0;
 199     if (!val)
 200         return 0;
 201     if (bits(val, 63,32)) { msb += 32; val >>= 32; }
 202     if (bits(val, 31,16)) { msb += 16; val >>= 16; }
 203     if (bits(val, 15,8))  { msb += 8;  val >>= 8;  }
 204     if (bits(val, 7,4))   { msb += 4;  val >>= 4;  }
 205     if (bits(val, 3,2))   { msb += 2;  val >>= 2;  }
 206     if (bits(val, 1,1))   { msb += 1; }
 207     return msb;
 208 }
 209
 210 /**
 211  * Returns the bit position of the LSB that is set in the input
 212  */
 213 inline int
 214 findLsbSet(uint64_t val) {
 215     int lsb = 0;
 216     if (!val)
 217         return sizeof(val) * 8;
 218     if (!bits(val, 31,0)) { lsb += 32; val >>= 32; }
 219     if (!bits(val, 15,0)) { lsb += 16; val >>= 16; }
 220     if (!bits(val, 7,0))  { lsb += 8;  val >>= 8;  }
 221     if (!bits(val, 3,0))  { lsb += 4;  val >>= 4;  }
 222     if (!bits(val, 1,0))  { lsb += 2;  val >>= 2;  }
 223     if (!bits(val, 0,0))  { lsb += 1; }
 224     return lsb;
 225 }
 226
 227 /**
 228  * Checks if a number is a power of two, or zero.
 229  */
 230 template <class T>
 231 inline bool
 232 isPow2(T v) {
 233    return (v & (v - 1)) == (T)0;
 234 }
 235
 236 /**
 237  * Returns the number of set ones in the provided value.
 238  * PD algorithm from
 239  * http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
 240  */
 241 inline int
 242 popCount(uint64_t val) {
 243 #ifndef __has_builtin
 244     #define __has_builtin(foo) 0
 245 #endif
 246 #if defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl))
 247     return __builtin_popcountl(val);
 248 #else
 249     const uint64_t m1 = 0x5555555555555555;  // ..010101b
 250     const uint64_t m2 = 0x3333333333333333;  // ..110011b
 251     const uint64_t m4 = 0x0f0f0f0f0f0f0f0f;  // ..001111b
 252     const uint64_t sum = 0x0101010101010101;
 253
 254     val -= (val >> 1) & m1;               // 2 bits count -> 2 bits
 255     val = (val & m2) + ((val >> 2) & m2); // 4 bits count -> 4 bits
 256     val = (val + (val >> 4)) & m4;        // 8 bits count -> 8 bits
 257     return (val * sum) >> 56;             // horizontal sum
 258 #endif // defined(__GNUC__) || (defined(__clang__) && __has_builtin(__builtin_popcountl))
 259 }
 260
 261 /**
 262  * Align to the next highest power of two.
 263  *
 264  * The number passed in is aligned to the next highest power of two,
 265  * if it is not already a power of two. Please note that if 0 is
 266  * passed in, 0 is returned.
 267  *
 268  * This code has been modified from the following:
 269  * http://graphics.stanford.edu/~seander/bithacks.html#RoundUpPowerOf2
 270  */
 271 inline uint64_t alignToPowerOfTwo(uint64_t val)
 272 {
 273     val--;
 274     val |= val >> 1;
 275     val |= val >> 2;
 276     val |= val >> 4;
 277     val |= val >> 8;
 278     val |= val >> 16;
 279     val |= val >> 32;
 280     val++;
 281
 282     return val;
 283 };
 284
 285 /**
 286  * Count trailing zeros in a 32-bit value.
 287  *
 288  * Returns 32 if the value is zero. Note that the GCC builtin is
 289  * undefined if the value is zero.
 290  */
 291 inline int ctz32(uint32_t value)
 292 {
 293     return value ? __builtin_ctz(value) : 32;
 294 }
 295
 296 #endif // __BASE_BITFIELD_HH__