Home | History | Annotate | Download | only in base 
      1 /*
      2  * Copyright (C) 2015 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #ifndef ART_LIBARTBASE_BASE_BIT_UTILS_H_
     18 #define ART_LIBARTBASE_BASE_BIT_UTILS_H_
     19 
     20 #include <limits>
     21 #include <type_traits>
     22 
     23 #include <android-base/logging.h>
     24 
     25 #include "base/stl_util_identity.h"
     26 
     27 namespace art {
     28 
     29 // Like sizeof, but count how many bits a type takes. Pass type explicitly.
     30 template <typename T>
     31 constexpr size_t BitSizeOf() {
     32   static_assert(std::is_integral<T>::value, "T must be integral");
     33   using unsigned_type = typename std::make_unsigned<T>::type;
     34   static_assert(sizeof(T) == sizeof(unsigned_type), "Unexpected type size mismatch!");
     35   static_assert(std::numeric_limits<unsigned_type>::radix == 2, "Unexpected radix!");
     36   return std::numeric_limits<unsigned_type>::digits;
     37 }
     38 
     39 // Like sizeof, but count how many bits a type takes. Infers type from parameter.
     40 template <typename T>
     41 constexpr size_t BitSizeOf(T /*x*/) {
     42   return BitSizeOf<T>();
     43 }
     44 
     45 template<typename T>
     46 constexpr int CLZ(T x) {
     47   static_assert(std::is_integral<T>::value, "T must be integral");
     48   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
     49   static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!");
     50   static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t),
     51                 "Unsupported sizeof(T)");
     52   DCHECK_NE(x, 0u);
     53   constexpr bool is_64_bit = (sizeof(T) == sizeof(uint64_t));
     54   constexpr size_t adjustment =
     55       is_64_bit ? 0u : std::numeric_limits<uint32_t>::digits - std::numeric_limits<T>::digits;
     56   return is_64_bit ? __builtin_clzll(x) : __builtin_clz(x) - adjustment;
     57 }
     58 
     59 // Similar to CLZ except that on zero input it returns bitwidth and supports signed integers.
     60 template<typename T>
     61 constexpr int JAVASTYLE_CLZ(T x) {
     62   static_assert(std::is_integral<T>::value, "T must be integral");
     63   using unsigned_type = typename std::make_unsigned<T>::type;
     64   return (x == 0) ? BitSizeOf<T>() : CLZ(static_cast<unsigned_type>(x));
     65 }
     66 
     67 template<typename T>
     68 constexpr int CTZ(T x) {
     69   static_assert(std::is_integral<T>::value, "T must be integral");
     70   // It is not unreasonable to ask for trailing zeros in a negative number. As such, do not check
     71   // that T is an unsigned type.
     72   static_assert(sizeof(T) == sizeof(uint64_t) || sizeof(T) <= sizeof(uint32_t),
     73                 "Unsupported sizeof(T)");
     74   DCHECK_NE(x, static_cast<T>(0));
     75   return (sizeof(T) == sizeof(uint64_t)) ? __builtin_ctzll(x) : __builtin_ctz(x);
     76 }
     77 
     78 // Similar to CTZ except that on zero input it returns bitwidth and supports signed integers.
     79 template<typename T>
     80 constexpr int JAVASTYLE_CTZ(T x) {
     81   static_assert(std::is_integral<T>::value, "T must be integral");
     82   using unsigned_type = typename std::make_unsigned<T>::type;
     83   return (x == 0) ? BitSizeOf<T>() : CTZ(static_cast<unsigned_type>(x));
     84 }
     85 
     86 // Return the number of 1-bits in `x`.
     87 template<typename T>
     88 constexpr int POPCOUNT(T x) {
     89   return (sizeof(T) == sizeof(uint32_t)) ? __builtin_popcount(x) : __builtin_popcountll(x);
     90 }
     91 
     92 // Swap bytes.
     93 template<typename T>
     94 constexpr T BSWAP(T x) {
     95   if (sizeof(T) == sizeof(uint16_t)) {
     96     return __builtin_bswap16(x);
     97   } else if (sizeof(T) == sizeof(uint32_t)) {
     98     return __builtin_bswap32(x);
     99   } else {
    100     return __builtin_bswap64(x);
    101   }
    102 }
    103 
    104 // Find the bit position of the most significant bit (0-based), or -1 if there were no bits set.
    105 template <typename T>
    106 constexpr ssize_t MostSignificantBit(T value) {
    107   static_assert(std::is_integral<T>::value, "T must be integral");
    108   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
    109   static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!");
    110   return (value == 0) ? -1 : std::numeric_limits<T>::digits - 1 - CLZ(value);
    111 }
    112 
    113 // Find the bit position of the least significant bit (0-based), or -1 if there were no bits set.
    114 template <typename T>
    115 constexpr ssize_t LeastSignificantBit(T value) {
    116   static_assert(std::is_integral<T>::value, "T must be integral");
    117   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
    118   return (value == 0) ? -1 : CTZ(value);
    119 }
    120 
    121 // How many bits (minimally) does it take to store the constant 'value'? i.e. 1 for 1, 3 for 5, etc.
    122 template <typename T>
    123 constexpr size_t MinimumBitsToStore(T value) {
    124   return static_cast<size_t>(MostSignificantBit(value) + 1);
    125 }
    126 
    127 template <typename T>
    128 constexpr T RoundUpToPowerOfTwo(T x) {
    129   static_assert(std::is_integral<T>::value, "T must be integral");
    130   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
    131   // NOTE: Undefined if x > (1 << (std::numeric_limits<T>::digits - 1)).
    132   return (x < 2u) ? x : static_cast<T>(1u) << (std::numeric_limits<T>::digits - CLZ(x - 1u));
    133 }
    134 
    135 // Return highest possible N - a power of two - such that val >= N.
    136 template <typename T>
    137 constexpr T TruncToPowerOfTwo(T val) {
    138   static_assert(std::is_integral<T>::value, "T must be integral");
    139   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
    140   return (val != 0) ? static_cast<T>(1u) << (BitSizeOf<T>() - CLZ(val) - 1u) : 0;
    141 }
    142 
    143 template<typename T>
    144 constexpr bool IsPowerOfTwo(T x) {
    145   static_assert(std::is_integral<T>::value, "T must be integral");
    146   // TODO: assert unsigned. There is currently many uses with signed values.
    147   return (x & (x - 1)) == 0;
    148 }
    149 
    150 template<typename T>
    151 constexpr int WhichPowerOf2(T x) {
    152   static_assert(std::is_integral<T>::value, "T must be integral");
    153   // TODO: assert unsigned. There is currently many uses with signed values.
    154   DCHECK((x != 0) && IsPowerOfTwo(x));
    155   return CTZ(x);
    156 }
    157 
    158 // For rounding integers.
    159 // Note: Omit the `n` from T type deduction, deduce only from the `x` argument.
    160 template<typename T>
    161 constexpr T RoundDown(T x, typename Identity<T>::type n) WARN_UNUSED;
    162 
    163 template<typename T>
    164 constexpr T RoundDown(T x, typename Identity<T>::type n) {
    165   DCHECK(IsPowerOfTwo(n));
    166   return (x & -n);
    167 }
    168 
    169 template<typename T>
    170 constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) WARN_UNUSED;
    171 
    172 template<typename T>
    173 constexpr T RoundUp(T x, typename std::remove_reference<T>::type n) {
    174   return RoundDown(x + n - 1, n);
    175 }
    176 
    177 // For aligning pointers.
    178 template<typename T>
    179 inline T* AlignDown(T* x, uintptr_t n) WARN_UNUSED;
    180 
    181 template<typename T>
    182 inline T* AlignDown(T* x, uintptr_t n) {
    183   return reinterpret_cast<T*>(RoundDown(reinterpret_cast<uintptr_t>(x), n));
    184 }
    185 
    186 template<typename T>
    187 inline T* AlignUp(T* x, uintptr_t n) WARN_UNUSED;
    188 
    189 template<typename T>
    190 inline T* AlignUp(T* x, uintptr_t n) {
    191   return reinterpret_cast<T*>(RoundUp(reinterpret_cast<uintptr_t>(x), n));
    192 }
    193 
    194 template<int n, typename T>
    195 constexpr bool IsAligned(T x) {
    196   static_assert((n & (n - 1)) == 0, "n is not a power of two");
    197   return (x & (n - 1)) == 0;
    198 }
    199 
    200 template<int n, typename T>
    201 inline bool IsAligned(T* x) {
    202   return IsAligned<n>(reinterpret_cast<const uintptr_t>(x));
    203 }
    204 
    205 template<typename T>
    206 inline bool IsAlignedParam(T x, int n) {
    207   return (x & (n - 1)) == 0;
    208 }
    209 
    210 template<typename T>
    211 inline bool IsAlignedParam(T* x, int n) {
    212   return IsAlignedParam(reinterpret_cast<const uintptr_t>(x), n);
    213 }
    214 
    215 #define CHECK_ALIGNED(value, alignment) \
    216   CHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value)
    217 
    218 #define DCHECK_ALIGNED(value, alignment) \
    219   DCHECK(::art::IsAligned<alignment>(value)) << reinterpret_cast<const void*>(value)
    220 
    221 #define CHECK_ALIGNED_PARAM(value, alignment) \
    222   CHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value)
    223 
    224 #define DCHECK_ALIGNED_PARAM(value, alignment) \
    225   DCHECK(::art::IsAlignedParam(value, alignment)) << reinterpret_cast<const void*>(value)
    226 
    227 inline uint16_t Low16Bits(uint32_t value) {
    228   return static_cast<uint16_t>(value);
    229 }
    230 
    231 inline uint16_t High16Bits(uint32_t value) {
    232   return static_cast<uint16_t>(value >> 16);
    233 }
    234 
    235 inline uint32_t Low32Bits(uint64_t value) {
    236   return static_cast<uint32_t>(value);
    237 }
    238 
    239 inline uint32_t High32Bits(uint64_t value) {
    240   return static_cast<uint32_t>(value >> 32);
    241 }
    242 
    243 // Check whether an N-bit two's-complement representation can hold value.
    244 template <typename T>
    245 inline bool IsInt(size_t N, T value) {
    246   if (N == BitSizeOf<T>()) {
    247     return true;
    248   } else {
    249     CHECK_LT(0u, N);
    250     CHECK_LT(N, BitSizeOf<T>());
    251     T limit = static_cast<T>(1) << (N - 1u);
    252     return (-limit <= value) && (value < limit);
    253   }
    254 }
    255 
    256 template <typename T>
    257 constexpr T GetIntLimit(size_t bits) {
    258   DCHECK_NE(bits, 0u);
    259   DCHECK_LT(bits, BitSizeOf<T>());
    260   return static_cast<T>(1) << (bits - 1);
    261 }
    262 
    263 template <size_t kBits, typename T>
    264 constexpr bool IsInt(T value) {
    265   static_assert(kBits > 0, "kBits cannot be zero.");
    266   static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
    267   static_assert(std::is_signed<T>::value, "Needs a signed type.");
    268   // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is
    269   // trivially true.
    270   return (kBits == BitSizeOf<T>()) ?
    271       true :
    272       (-GetIntLimit<T>(kBits) <= value) && (value < GetIntLimit<T>(kBits));
    273 }
    274 
    275 template <size_t kBits, typename T>
    276 constexpr bool IsUint(T value) {
    277   static_assert(kBits > 0, "kBits cannot be zero.");
    278   static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
    279   static_assert(std::is_integral<T>::value, "Needs an integral type.");
    280   // Corner case for "use all bits." Can't use the limits, as they would overflow, but it is
    281   // trivially true.
    282   // NOTE: To avoid triggering assertion in GetIntLimit(kBits+1) if kBits+1==BitSizeOf<T>(),
    283   // use GetIntLimit(kBits)*2u. The unsigned arithmetic works well for us if it overflows.
    284   using unsigned_type = typename std::make_unsigned<T>::type;
    285   return (0 <= value) &&
    286       (kBits == BitSizeOf<T>() ||
    287           (static_cast<unsigned_type>(value) <= GetIntLimit<unsigned_type>(kBits) * 2u - 1u));
    288 }
    289 
    290 template <size_t kBits, typename T>
    291 constexpr bool IsAbsoluteUint(T value) {
    292   static_assert(kBits <= BitSizeOf<T>(), "kBits must be <= max.");
    293   static_assert(std::is_integral<T>::value, "Needs an integral type.");
    294   using unsigned_type = typename std::make_unsigned<T>::type;
    295   return (kBits == BitSizeOf<T>())
    296       ? true
    297       : IsUint<kBits>(value < 0
    298                       ? static_cast<unsigned_type>(-1 - value) + 1u  // Avoid overflow.
    299                       : static_cast<unsigned_type>(value));
    300 }
    301 
    302 // Generate maximum/minimum values for signed/unsigned n-bit integers
    303 template <typename T>
    304 constexpr T MaxInt(size_t bits) {
    305   DCHECK(std::is_unsigned<T>::value || bits > 0u) << "bits cannot be zero for signed.";
    306   DCHECK_LE(bits, BitSizeOf<T>());
    307   using unsigned_type = typename std::make_unsigned<T>::type;
    308   return bits == BitSizeOf<T>()
    309       ? std::numeric_limits<T>::max()
    310       : std::is_signed<T>::value
    311           ? ((bits == 1u) ? 0 : static_cast<T>(MaxInt<unsigned_type>(bits - 1)))
    312           : static_cast<T>(UINT64_C(1) << bits) - static_cast<T>(1);
    313 }
    314 
    315 template <typename T>
    316 constexpr T MinInt(size_t bits) {
    317   DCHECK(std::is_unsigned<T>::value || bits > 0) << "bits cannot be zero for signed.";
    318   DCHECK_LE(bits, BitSizeOf<T>());
    319   return bits == BitSizeOf<T>()
    320       ? std::numeric_limits<T>::min()
    321       : std::is_signed<T>::value
    322           ? ((bits == 1u) ? -1 : static_cast<T>(-1) - MaxInt<T>(bits))
    323           : static_cast<T>(0);
    324 }
    325 
    326 // Returns value with bit set in lowest one-bit position or 0 if 0.  (java.lang.X.lowestOneBit).
    327 template <typename kind>
    328 inline static kind LowestOneBitValue(kind opnd) {
    329   // Hacker's Delight, Section 2-1
    330   return opnd & -opnd;
    331 }
    332 
    333 // Returns value with bit set in hightest one-bit position or 0 if 0.  (java.lang.X.highestOneBit).
    334 template <typename T>
    335 inline static T HighestOneBitValue(T opnd) {
    336   using unsigned_type = typename std::make_unsigned<T>::type;
    337   T res;
    338   if (opnd == 0) {
    339     res = 0;
    340   } else {
    341     int bit_position = BitSizeOf<T>() - (CLZ(static_cast<unsigned_type>(opnd)) + 1);
    342     res = static_cast<T>(UINT64_C(1) << bit_position);
    343   }
    344   return res;
    345 }
    346 
    347 // Rotate bits.
    348 template <typename T, bool left>
    349 inline static T Rot(T opnd, int distance) {
    350   int mask = BitSizeOf<T>() - 1;
    351   int unsigned_right_shift = left ? (-distance & mask) : (distance & mask);
    352   int signed_left_shift = left ? (distance & mask) : (-distance & mask);
    353   using unsigned_type = typename std::make_unsigned<T>::type;
    354   return (static_cast<unsigned_type>(opnd) >> unsigned_right_shift) | (opnd << signed_left_shift);
    355 }
    356 
    357 // TUNING: use rbit for arm/arm64
    358 inline static uint32_t ReverseBits32(uint32_t opnd) {
    359   // Hacker's Delight 7-1
    360   opnd = ((opnd >>  1) & 0x55555555) | ((opnd & 0x55555555) <<  1);
    361   opnd = ((opnd >>  2) & 0x33333333) | ((opnd & 0x33333333) <<  2);
    362   opnd = ((opnd >>  4) & 0x0F0F0F0F) | ((opnd & 0x0F0F0F0F) <<  4);
    363   opnd = ((opnd >>  8) & 0x00FF00FF) | ((opnd & 0x00FF00FF) <<  8);
    364   opnd = ((opnd >> 16)) | ((opnd) << 16);
    365   return opnd;
    366 }
    367 
    368 // TUNING: use rbit for arm/arm64
    369 inline static uint64_t ReverseBits64(uint64_t opnd) {
    370   // Hacker's Delight 7-1
    371   opnd = (opnd & 0x5555555555555555L) << 1 | ((opnd >> 1) & 0x5555555555555555L);
    372   opnd = (opnd & 0x3333333333333333L) << 2 | ((opnd >> 2) & 0x3333333333333333L);
    373   opnd = (opnd & 0x0f0f0f0f0f0f0f0fL) << 4 | ((opnd >> 4) & 0x0f0f0f0f0f0f0f0fL);
    374   opnd = (opnd & 0x00ff00ff00ff00ffL) << 8 | ((opnd >> 8) & 0x00ff00ff00ff00ffL);
    375   opnd = (opnd << 48) | ((opnd & 0xffff0000L) << 16) | ((opnd >> 16) & 0xffff0000L) | (opnd >> 48);
    376   return opnd;
    377 }
    378 
    379 // Create a mask for the least significant "bits"
    380 // The returned value is always unsigned to prevent undefined behavior for bitwise ops.
    381 //
    382 // Given 'bits',
    383 // Returns:
    384 //                   <--- bits --->
    385 // +-----------------+------------+
    386 // | 0 ............0 |   1.....1  |
    387 // +-----------------+------------+
    388 // msb                           lsb
    389 template <typename T = size_t>
    390 inline static constexpr std::make_unsigned_t<T> MaskLeastSignificant(size_t bits) {
    391   DCHECK_GE(BitSizeOf<T>(), bits) << "Bits out of range for type T";
    392   using unsigned_T = std::make_unsigned_t<T>;
    393   if (bits >= BitSizeOf<T>()) {
    394     return std::numeric_limits<unsigned_T>::max();
    395   } else {
    396     auto kOne = static_cast<unsigned_T>(1);  // Do not truncate for T>size_t.
    397     return static_cast<unsigned_T>((kOne << bits) - kOne);
    398   }
    399 }
    400 
    401 // Clears the bitfield starting at the least significant bit "lsb" with a bitwidth of 'width'.
    402 // (Equivalent of ARM BFC instruction).
    403 //
    404 // Given:
    405 //           <-- width  -->
    406 // +--------+------------+--------+
    407 // | ABC... |  bitfield  | XYZ... +
    408 // +--------+------------+--------+
    409 //                       lsb      0
    410 // Returns:
    411 //           <-- width  -->
    412 // +--------+------------+--------+
    413 // | ABC... | 0........0 | XYZ... +
    414 // +--------+------------+--------+
    415 //                       lsb      0
    416 template <typename T>
    417 inline static constexpr T BitFieldClear(T value, size_t lsb, size_t width) {
    418   DCHECK_GE(BitSizeOf(value), lsb + width) << "Bit field out of range for value";
    419   const auto val = static_cast<std::make_unsigned_t<T>>(value);
    420   const auto mask = MaskLeastSignificant<T>(width);
    421 
    422   return static_cast<T>(val & ~(mask << lsb));
    423 }
    424 
    425 // Inserts the contents of 'data' into bitfield of 'value'  starting
    426 // at the least significant bit "lsb" with a bitwidth of 'width'.
    427 // Note: data must be within range of [MinInt(width), MaxInt(width)].
    428 // (Equivalent of ARM BFI instruction).
    429 //
    430 // Given (data):
    431 //           <-- width  -->
    432 // +--------+------------+--------+
    433 // | ABC... |  bitfield  | XYZ... +
    434 // +--------+------------+--------+
    435 //                       lsb      0
    436 // Returns:
    437 //           <-- width  -->
    438 // +--------+------------+--------+
    439 // | ABC... | 0...data   | XYZ... +
    440 // +--------+------------+--------+
    441 //                       lsb      0
    442 
    443 template <typename T, typename T2>
    444 inline static constexpr T BitFieldInsert(T value, T2 data, size_t lsb, size_t width) {
    445   DCHECK_GE(BitSizeOf(value), lsb + width) << "Bit field out of range for value";
    446   if (width != 0u) {
    447     DCHECK_GE(MaxInt<T2>(width), data) << "Data out of range [too large] for bitwidth";
    448     DCHECK_LE(MinInt<T2>(width), data) << "Data out of range [too small] for bitwidth";
    449   } else {
    450     DCHECK_EQ(static_cast<T2>(0), data) << "Data out of range [nonzero] for bitwidth 0";
    451   }
    452   const auto data_mask = MaskLeastSignificant<T2>(width);
    453   const auto value_cleared = BitFieldClear(value, lsb, width);
    454 
    455   return static_cast<T>(value_cleared | ((data & data_mask) << lsb));
    456 }
    457 
    458 // Extracts the bitfield starting at the least significant bit "lsb" with a bitwidth of 'width'.
    459 // Signed types are sign-extended during extraction. (Equivalent of ARM UBFX/SBFX instruction).
    460 //
    461 // Given:
    462 //           <-- width   -->
    463 // +--------+-------------+-------+
    464 // |        |   bitfield  |       +
    465 // +--------+-------------+-------+
    466 //                       lsb      0
    467 // (Unsigned) Returns:
    468 //                  <-- width   -->
    469 // +----------------+-------------+
    470 // | 0...        0  |   bitfield  |
    471 // +----------------+-------------+
    472 //                                0
    473 // (Signed) Returns:
    474 //                  <-- width   -->
    475 // +----------------+-------------+
    476 // | S...        S  |   bitfield  |
    477 // +----------------+-------------+
    478 //                                0
    479 // where S is the highest bit in 'bitfield'.
    480 template <typename T>
    481 inline static constexpr T BitFieldExtract(T value, size_t lsb, size_t width) {
    482   DCHECK_GE(BitSizeOf(value), lsb + width) << "Bit field out of range for value";
    483   const auto val = static_cast<std::make_unsigned_t<T>>(value);
    484 
    485   const T bitfield_unsigned =
    486       static_cast<T>((val >> lsb) & MaskLeastSignificant<T>(width));
    487   if (std::is_signed<T>::value) {
    488     // Perform sign extension
    489     if (width == 0) {  // Avoid underflow.
    490       return static_cast<T>(0);
    491     } else if (bitfield_unsigned & (1 << (width - 1))) {  // Detect if sign bit was set.
    492       // MSB        <width> LSB
    493       // 0b11111...100...000000
    494       const auto ones_negmask = ~MaskLeastSignificant<T>(width);
    495       return static_cast<T>(bitfield_unsigned | ones_negmask);
    496     }
    497   }
    498   // Skip sign extension.
    499   return bitfield_unsigned;
    500 }
    501 
    502 }  // namespace art
    503 
    504 #endif  // ART_LIBARTBASE_BASE_BIT_UTILS_H_
    505