llvm/ADT/Bitfields.h

0001 //===-- llvm/ADT/Bitfield.h - Get and Set bits in an integer ---*- C++ -*--===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 /// This file implements methods to test, set and extract typed bits from packed
0011 /// unsigned integers.
0012 ///
0013 /// Why not C++ bitfields?
0014 /// ----------------------
0015 /// C++ bitfields do not offer control over the bit layout nor consistent
0016 /// behavior when it comes to out of range values.
0017 /// For instance, the layout is implementation defined and adjacent bits may be
0018 /// packed together but are not required to. This is problematic when storage is
0019 /// sparse and data must be stored in a particular integer type.
0020 ///
0021 /// The methods provided in this file ensure precise control over the
0022 /// layout/storage as well as protection against out of range values.
0023 ///
0024 /// Usage example
0025 /// -------------
0026 /// \code{.cpp}
0027 ///  uint8_t Storage = 0;
0028 ///
0029 ///  // Store and retrieve a single bit as bool.
0030 ///  using Bool = Bitfield::Element<bool, 0, 1>;
0031 ///  Bitfield::set<Bool>(Storage, true);
0032 ///  EXPECT_EQ(Storage, 0b00000001);
0033 ///  //                          ^
0034 ///  EXPECT_EQ(Bitfield::get<Bool>(Storage), true);
0035 ///
0036 ///  // Store and retrieve a 2 bit typed enum.
0037 ///  // Note: enum underlying type must be unsigned.
0038 ///  enum class SuitEnum : uint8_t { CLUBS, DIAMONDS, HEARTS, SPADES };
0039 ///  // Note: enum maximum value needs to be passed in as last parameter.
0040 ///  using Suit = Bitfield::Element<SuitEnum, 1, 2, SuitEnum::SPADES>;
0041 ///  Bitfield::set<Suit>(Storage, SuitEnum::HEARTS);
0042 ///  EXPECT_EQ(Storage, 0b00000101);
0043 ///  //                        ^^
0044 ///  EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::HEARTS);
0045 ///
0046 ///  // Store and retrieve a 5 bit value as unsigned.
0047 ///  using Value = Bitfield::Element<unsigned, 3, 5>;
0048 ///  Bitfield::set<Value>(Storage, 10);
0049 ///  EXPECT_EQ(Storage, 0b01010101);
0050 ///  //                   ^^^^^
0051 ///  EXPECT_EQ(Bitfield::get<Value>(Storage), 10U);
0052 ///
0053 ///  // Interpret the same 5 bit value as signed.
0054 ///  using SignedValue = Bitfield::Element<int, 3, 5>;
0055 ///  Bitfield::set<SignedValue>(Storage, -2);
0056 ///  EXPECT_EQ(Storage, 0b11110101);
0057 ///  //                   ^^^^^
0058 ///  EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -2);
0059 ///
0060 ///  // Ability to efficiently test if a field is non zero.
0061 ///  EXPECT_TRUE(Bitfield::test<Value>(Storage));
0062 ///
0063 ///  // Alter Storage changes value.
0064 ///  Storage = 0;
0065 ///  EXPECT_EQ(Bitfield::get<Bool>(Storage), false);
0066 ///  EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::CLUBS);
0067 ///  EXPECT_EQ(Bitfield::get<Value>(Storage), 0U);
0068 ///  EXPECT_EQ(Bitfield::get<SignedValue>(Storage), 0);
0069 ///
0070 ///  Storage = 255;
0071 ///  EXPECT_EQ(Bitfield::get<Bool>(Storage), true);
0072 ///  EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::SPADES);
0073 ///  EXPECT_EQ(Bitfield::get<Value>(Storage), 31U);
0074 ///  EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -1);
0075 /// \endcode
0076 ///
0077 //===----------------------------------------------------------------------===//
0078
0079 #ifndef LLVM_ADT_BITFIELDS_H
0080 #define LLVM_ADT_BITFIELDS_H
0081
0082 #include <cassert>
0083 #include <climits> // CHAR_BIT
0084 #include <cstddef> // size_t
0085 #include <cstdint> // uintXX_t
0086 #include <limits>  // numeric_limits
0087 #include <type_traits>
0088
0089 namespace llvm {
0090
0091 namespace bitfields_details {
0092
0093 /// A struct defining useful bit patterns for n-bits integer types.
0094 template <typename T, unsigned Bits> struct BitPatterns {
0095   /// Bit patterns are forged using the equivalent `Unsigned` type because of
0096   /// undefined operations over signed types (e.g. Bitwise shift operators).
0097   /// Moreover same size casting from unsigned to signed is well defined but not
0098   /// the other way around.
0099   using Unsigned = std::make_unsigned_t<T>;
0100   static_assert(sizeof(Unsigned) == sizeof(T), "Types must have same size");
0101
0102   static constexpr unsigned TypeBits = sizeof(Unsigned) * CHAR_BIT;
0103   static_assert(TypeBits >= Bits, "n-bit must fit in T");
0104
0105   /// e.g. with TypeBits == 8 and Bits == 6.
0106   static constexpr Unsigned AllZeros = Unsigned(0);                  // 00000000
0107   static constexpr Unsigned AllOnes = ~Unsigned(0);                  // 11111111
0108   static constexpr Unsigned Umin = AllZeros;                         // 00000000
0109   static constexpr Unsigned Umax = AllOnes >> (TypeBits - Bits);     // 00111111
0110   static constexpr Unsigned SignBitMask = Unsigned(1) << (Bits - 1); // 00100000
0111   static constexpr Unsigned Smax = Umax >> 1U;                       // 00011111
0112   static constexpr Unsigned Smin = ~Smax;                            // 11100000
0113   static constexpr Unsigned SignExtend = Unsigned(Smin << 1U);       // 11000000
0114 };
0115
0116 /// `Compressor` is used to manipulate the bits of a (possibly signed) integer
0117 /// type so it can be packed and unpacked into a `bits` sized integer,
0118 /// `Compressor` is specialized on signed-ness so no runtime cost is incurred.
0119 /// The `pack` method also checks that the passed in `UserValue` is valid.
0120 template <typename T, unsigned Bits, bool = std::is_unsigned<T>::value>
0121 struct Compressor {
0122   static_assert(std::is_unsigned<T>::value, "T must be unsigned");
0123   using BP = BitPatterns<T, Bits>;
0124
0125   static T pack(T UserValue, T UserMaxValue) {
0126     assert(UserValue <= UserMaxValue && "value is too big");
0127     assert(UserValue <= BP::Umax && "value is too big");
0128     return UserValue;
0129   }
0130
0131   static T unpack(T StorageValue) { return StorageValue; }
0132 };
0133
0134 template <typename T, unsigned Bits> struct Compressor<T, Bits, false> {
0135   static_assert(std::is_signed<T>::value, "T must be signed");
0136   using BP = BitPatterns<T, Bits>;
0137
0138   static T pack(T UserValue, T UserMaxValue) {
0139     assert(UserValue <= UserMaxValue && "value is too big");
0140     assert(UserValue <= T(BP::Smax) && "value is too big");
0141     assert(UserValue >= T(BP::Smin) && "value is too small");
0142     if (UserValue < 0)
0143       UserValue &= ~BP::SignExtend;
0144     return UserValue;
0145   }
0146
0147   static T unpack(T StorageValue) {
0148     if (StorageValue >= T(BP::SignBitMask))
0149       StorageValue |= BP::SignExtend;
0150     return StorageValue;
0151   }
0152 };
0153
0154 /// Impl is where Bifield description and Storage are put together to interact
0155 /// with values.
0156 template <typename Bitfield, typename StorageType> struct Impl {
0157   static_assert(std::is_unsigned<StorageType>::value,
0158                 "Storage must be unsigned");
0159   using IntegerType = typename Bitfield::IntegerType;
0160   using C = Compressor<IntegerType, Bitfield::Bits>;
0161   using BP = BitPatterns<StorageType, Bitfield::Bits>;
0162
0163   static constexpr size_t StorageBits = sizeof(StorageType) * CHAR_BIT;
0164   static_assert(Bitfield::FirstBit <= StorageBits, "Data must fit in mask");
0165   static_assert(Bitfield::LastBit <= StorageBits, "Data must fit in mask");
0166   static constexpr StorageType Mask = BP::Umax << Bitfield::Shift;
0167
0168   /// Checks `UserValue` is within bounds and packs it between `FirstBit` and
0169   /// `LastBit` of `Packed` leaving the rest unchanged.
0170   static void update(StorageType &Packed, IntegerType UserValue) {
0171     const StorageType StorageValue = C::pack(UserValue, Bitfield::UserMaxValue);
0172     Packed &= ~Mask;
0173     Packed |= StorageValue << Bitfield::Shift;
0174   }
0175
0176   /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as
0177   /// an`IntegerType`.
0178   static IntegerType extract(StorageType Packed) {
0179     const StorageType StorageValue = (Packed & Mask) >> Bitfield::Shift;
0180     return C::unpack(StorageValue);
0181   }
0182
0183   /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as
0184   /// an`IntegerType`.
0185   static StorageType test(StorageType Packed) { return Packed & Mask; }
0186 };
0187
0188 /// `Bitfield` deals with the following type:
0189 /// - unsigned enums
0190 /// - signed and unsigned integer
0191 /// - `bool`
0192 /// Internally though we only manipulate integer with well defined and
0193 /// consistent semantics, this excludes typed enums and `bool` that are replaced
0194 /// with their unsigned counterparts. The correct type is restored in the public
0195 /// API.
0196 template <typename T, bool = std::is_enum<T>::value>
0197 struct ResolveUnderlyingType {
0198   using type = std::underlying_type_t<T>;
0199 };
0200 template <typename T> struct ResolveUnderlyingType<T, false> {
0201   using type = T;
0202 };
0203 template <> struct ResolveUnderlyingType<bool, false> {
0204   /// In case sizeof(bool) != 1, replace `void` by an additionnal
0205   /// std::conditional.
0206   using type = std::conditional_t<sizeof(bool) == 1, uint8_t, void>;
0207 };
0208
0209 } // namespace bitfields_details
0210
0211 /// Holds functions to get, set or test bitfields.
0212 struct Bitfield {
0213   /// Describes an element of a Bitfield. This type is then used with the
0214   /// Bitfield static member functions.
0215   /// \tparam T         The type of the field once in unpacked form.
0216   /// \tparam Offset    The position of the first bit.
0217   /// \tparam Size      The size of the field.
0218   /// \tparam MaxValue  For enums the maximum enum allowed.
0219   template <typename T, unsigned Offset, unsigned Size,
0220             T MaxValue = std::is_enum<T>::value
0221                              ? T(0) // coupled with static_assert below
0222                              : std::numeric_limits<T>::max()>
0223   struct Element {
0224     using Type = T;
0225     using IntegerType =
0226         typename bitfields_details::ResolveUnderlyingType<T>::type;
0227     static constexpr unsigned Shift = Offset;
0228     static constexpr unsigned Bits = Size;
0229     static constexpr unsigned FirstBit = Offset;
0230     static constexpr unsigned LastBit = Shift + Bits - 1;
0231     static constexpr unsigned NextBit = Shift + Bits;
0232
0233   private:
0234     template <typename, typename> friend struct bitfields_details::Impl;
0235
0236     static_assert(Bits > 0, "Bits must be non zero");
0237     static constexpr size_t TypeBits = sizeof(IntegerType) * CHAR_BIT;
0238     static_assert(Bits <= TypeBits, "Bits may not be greater than T size");
0239     static_assert(!std::is_enum<T>::value || MaxValue != T(0),
0240                   "Enum Bitfields must provide a MaxValue");
0241     static_assert(!std::is_enum<T>::value ||
0242                       std::is_unsigned<IntegerType>::value,
0243                   "Enum must be unsigned");
0244     static_assert(std::is_integral<IntegerType>::value &&
0245                       std::numeric_limits<IntegerType>::is_integer,
0246                   "IntegerType must be an integer type");
0247
0248     static constexpr IntegerType UserMaxValue =
0249         static_cast<IntegerType>(MaxValue);
0250   };
0251
0252   /// Unpacks the field from the `Packed` value.
0253   template <typename Bitfield, typename StorageType>
0254   static typename Bitfield::Type get(StorageType Packed) {
0255     using I = bitfields_details::Impl<Bitfield, StorageType>;
0256     return static_cast<typename Bitfield::Type>(I::extract(Packed));
0257   }
0258
0259   /// Return a non-zero value if the field is non-zero.
0260   /// It is more efficient than `getField`.
0261   template <typename Bitfield, typename StorageType>
0262   static StorageType test(StorageType Packed) {
0263     using I = bitfields_details::Impl<Bitfield, StorageType>;
0264     return I::test(Packed);
0265   }
0266
0267   /// Sets the typed value in the provided `Packed` value.
0268   /// The method will asserts if the provided value is too big to fit in.
0269   template <typename Bitfield, typename StorageType>
0270   static void set(StorageType &Packed, typename Bitfield::Type Value) {
0271     using I = bitfields_details::Impl<Bitfield, StorageType>;
0272     I::update(Packed, static_cast<typename Bitfield::IntegerType>(Value));
0273   }
0274
0275   /// Returns whether the two bitfields share common bits.
0276   template <typename A, typename B> static constexpr bool isOverlapping() {
0277     return A::LastBit >= B::FirstBit && B::LastBit >= A::FirstBit;
0278   }
0279
0280   template <typename A> static constexpr bool areContiguous() { return true; }
0281   template <typename A, typename B, typename... Others>
0282   static constexpr bool areContiguous() {
0283     return A::NextBit == B::FirstBit && areContiguous<B, Others...>();
0284   }
0285 };
0286
0287 } // namespace llvm
0288
0289 #endif // LLVM_ADT_BITFIELDS_H