1 //===-- llvm/ADT/Bitfield.h - Get and Set bits in an integer ---*- C++ -*--===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// 9 /// \file 10 /// This file implements methods to test, set and extract typed bits from packed 11 /// unsigned integers. 12 /// 13 /// Why not C++ bitfields? 14 /// ---------------------- 15 /// C++ bitfields do not offer control over the bit layout nor consistent 16 /// behavior when it comes to out of range values. 17 /// For instance, the layout is implementation defined and adjacent bits may be 18 /// packed together but are not required to. This is problematic when storage is 19 /// sparse and data must be stored in a particular integer type. 20 /// 21 /// The methods provided in this file ensure precise control over the 22 /// layout/storage as well as protection against out of range values. 23 /// 24 /// Usage example 25 /// ------------- 26 /// \code{.cpp} 27 /// uint8_t Storage = 0; 28 /// 29 /// // Store and retrieve a single bit as bool. 30 /// using Bool = Bitfield::Element<bool, 0, 1>; 31 /// Bitfield::set<Bool>(Storage, true); 32 /// EXPECT_EQ(Storage, 0b00000001); 33 /// // ^ 34 /// EXPECT_EQ(Bitfield::get<Bool>(Storage), true); 35 /// 36 /// // Store and retrieve a 2 bit typed enum. 37 /// // Note: enum underlying type must be unsigned. 38 /// enum class SuitEnum : uint8_t { CLUBS, DIAMONDS, HEARTS, SPADES }; 39 /// // Note: enum maximum value needs to be passed in as last parameter. 40 /// using Suit = Bitfield::Element<SuitEnum, 1, 2, SuitEnum::SPADES>; 41 /// Bitfield::set<Suit>(Storage, SuitEnum::HEARTS); 42 /// EXPECT_EQ(Storage, 0b00000101); 43 /// // ^^ 44 /// EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::HEARTS); 45 /// 46 /// // Store and retrieve a 5 bit value as unsigned. 47 /// using Value = Bitfield::Element<unsigned, 3, 5>; 48 /// Bitfield::set<Value>(Storage, 10); 49 /// EXPECT_EQ(Storage, 0b01010101); 50 /// // ^^^^^ 51 /// EXPECT_EQ(Bitfield::get<Value>(Storage), 10U); 52 /// 53 /// // Interpret the same 5 bit value as signed. 54 /// using SignedValue = Bitfield::Element<int, 3, 5>; 55 /// Bitfield::set<SignedValue>(Storage, -2); 56 /// EXPECT_EQ(Storage, 0b11110101); 57 /// // ^^^^^ 58 /// EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -2); 59 /// 60 /// // Ability to efficiently test if a field is non zero. 61 /// EXPECT_TRUE(Bitfield::test<Value>(Storage)); 62 /// 63 /// // Alter Storage changes value. 64 /// Storage = 0; 65 /// EXPECT_EQ(Bitfield::get<Bool>(Storage), false); 66 /// EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::CLUBS); 67 /// EXPECT_EQ(Bitfield::get<Value>(Storage), 0U); 68 /// EXPECT_EQ(Bitfield::get<SignedValue>(Storage), 0); 69 /// 70 /// Storage = 255; 71 /// EXPECT_EQ(Bitfield::get<Bool>(Storage), true); 72 /// EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::SPADES); 73 /// EXPECT_EQ(Bitfield::get<Value>(Storage), 31U); 74 /// EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -1); 75 /// \endcode 76 /// 77 //===----------------------------------------------------------------------===// 78 79 #ifndef LLVM_ADT_BITFIELDS_H 80 #define LLVM_ADT_BITFIELDS_H 81 82 #include <cassert> 83 #include <climits> // CHAR_BIT 84 #include <cstddef> // size_t 85 #include <cstdint> // uintXX_t 86 #include <limits> // numeric_limits 87 #include <type_traits> 88 89 namespace llvm { 90 91 namespace bitfields_details { 92 93 /// A struct defining useful bit patterns for n-bits integer types. 94 template <typename T, unsigned Bits> struct BitPatterns { 95 /// Bit patterns are forged using the equivalent `Unsigned` type because of 96 /// undefined operations over signed types (e.g. Bitwise shift operators). 97 /// Moreover same size casting from unsigned to signed is well defined but not 98 /// the other way around. 99 using Unsigned = typename std::make_unsigned<T>::type; 100 static_assert(sizeof(Unsigned) == sizeof(T), "Types must have same size"); 101 102 static constexpr unsigned TypeBits = sizeof(Unsigned) * CHAR_BIT; 103 static_assert(TypeBits >= Bits, "n-bit must fit in T"); 104 105 /// e.g. with TypeBits == 8 and Bits == 6. 106 static constexpr Unsigned AllZeros = Unsigned(0); // 00000000 107 static constexpr Unsigned AllOnes = ~Unsigned(0); // 11111111 108 static constexpr Unsigned Umin = AllZeros; // 00000000 109 static constexpr Unsigned Umax = AllOnes >> (TypeBits - Bits); // 00111111 110 static constexpr Unsigned SignBitMask = Unsigned(1) << (Bits - 1); // 00100000 111 static constexpr Unsigned Smax = Umax >> 1U; // 00011111 112 static constexpr Unsigned Smin = ~Smax; // 11100000 113 static constexpr Unsigned SignExtend = Unsigned(Smin << 1U); // 11000000 114 }; 115 116 /// `Compressor` is used to manipulate the bits of a (possibly signed) integer 117 /// type so it can be packed and unpacked into a `bits` sized integer, 118 /// `Compressor` is specialized on signed-ness so no runtime cost is incurred. 119 /// The `pack` method also checks that the passed in `UserValue` is valid. 120 template <typename T, unsigned Bits, bool = std::is_unsigned<T>::value> 121 struct Compressor { 122 static_assert(std::is_unsigned<T>::value, "T is unsigned"); 123 using BP = BitPatterns<T, Bits>; 124 packCompressor125 static T pack(T UserValue, T UserMaxValue) { 126 assert(UserValue <= UserMaxValue && "value is too big"); 127 assert(UserValue <= BP::Umax && "value is too big"); 128 return UserValue; 129 } 130 unpackCompressor131 static T unpack(T StorageValue) { return StorageValue; } 132 }; 133 134 template <typename T, unsigned Bits> struct Compressor<T, Bits, false> { 135 static_assert(std::is_signed<T>::value, "T is signed"); 136 using BP = BitPatterns<T, Bits>; 137 138 static T pack(T UserValue, T UserMaxValue) { 139 assert(UserValue <= UserMaxValue && "value is too big"); 140 assert(UserValue <= T(BP::Smax) && "value is too big"); 141 assert(UserValue >= T(BP::Smin) && "value is too small"); 142 if (UserValue < 0) 143 UserValue &= ~BP::SignExtend; 144 return UserValue; 145 } 146 147 static T unpack(T StorageValue) { 148 if (StorageValue >= T(BP::SignBitMask)) 149 StorageValue |= BP::SignExtend; 150 return StorageValue; 151 } 152 }; 153 154 /// Impl is where Bifield description and Storage are put together to interact 155 /// with values. 156 template <typename Bitfield, typename StorageType> struct Impl { 157 static_assert(std::is_unsigned<StorageType>::value, 158 "Storage must be unsigned"); 159 using IntegerType = typename Bitfield::IntegerType; 160 using C = Compressor<IntegerType, Bitfield::Bits>; 161 using BP = BitPatterns<StorageType, Bitfield::Bits>; 162 163 static constexpr size_t StorageBits = sizeof(StorageType) * CHAR_BIT; 164 static_assert(Bitfield::FirstBit <= StorageBits, "Data must fit in mask"); 165 static_assert(Bitfield::LastBit <= StorageBits, "Data must fit in mask"); 166 static constexpr StorageType Mask = BP::Umax << Bitfield::Shift; 167 168 /// Checks `UserValue` is within bounds and packs it between `FirstBit` and 169 /// `LastBit` of `Packed` leaving the rest unchanged. 170 static void update(StorageType &Packed, IntegerType UserValue) { 171 const StorageType StorageValue = C::pack(UserValue, Bitfield::UserMaxValue); 172 Packed &= ~Mask; 173 Packed |= StorageValue << Bitfield::Shift; 174 } 175 176 /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as 177 /// an`IntegerType`. 178 static IntegerType extract(StorageType Packed) { 179 const StorageType StorageValue = (Packed & Mask) >> Bitfield::Shift; 180 return C::unpack(StorageValue); 181 } 182 183 /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as 184 /// an`IntegerType`. 185 static StorageType test(StorageType Packed) { return Packed & Mask; } 186 }; 187 188 /// `Bitfield` deals with the following type: 189 /// - unsigned enums 190 /// - signed and unsigned integer 191 /// - `bool` 192 /// Internally though we only manipulate integer with well defined and 193 /// consistent semantics, this excludes typed enums and `bool` that are replaced 194 /// with their unsigned counterparts. The correct type is restored in the public 195 /// API. 196 template <typename T, bool = std::is_enum<T>::value> 197 struct ResolveUnderlyingType { 198 using type = typename std::underlying_type<T>::type; 199 }; 200 template <typename T> struct ResolveUnderlyingType<T, false> { 201 using type = T; 202 }; 203 template <> struct ResolveUnderlyingType<bool, false> { 204 /// In case sizeof(bool) != 1, replace `void` by an additionnal 205 /// std::conditional. 206 using type = std::conditional<sizeof(bool) == 1, uint8_t, void>::type; 207 }; 208 209 } // namespace bitfields_details 210 211 /// Holds functions to get, set or test bitfields. 212 struct Bitfield { 213 /// Describes an element of a Bitfield. This type is then used with the 214 /// Bitfield static member functions. 215 /// \tparam T The type of the field once in unpacked form. 216 /// \tparam Offset The position of the first bit. 217 /// \tparam Size The size of the field. 218 /// \tparam MaxValue For enums the maximum enum allowed. 219 template <typename T, unsigned Offset, unsigned Size, 220 T MaxValue = std::is_enum<T>::value 221 ? T(0) // coupled with static_assert below 222 : std::numeric_limits<T>::max()> 223 struct Element { 224 using Type = T; 225 using IntegerType = 226 typename bitfields_details::ResolveUnderlyingType<T>::type; 227 static constexpr unsigned Shift = Offset; 228 static constexpr unsigned Bits = Size; 229 static constexpr unsigned FirstBit = Offset; 230 static constexpr unsigned LastBit = Shift + Bits - 1; 231 static constexpr unsigned NextBit = Shift + Bits; 232 233 private: 234 template <typename, typename> friend struct bitfields_details::Impl; 235 236 static_assert(Bits > 0, "Bits must be non zero"); 237 static constexpr size_t TypeBits = sizeof(IntegerType) * CHAR_BIT; 238 static_assert(Bits <= TypeBits, "Bits may not be greater than T size"); 239 static_assert(!std::is_enum<T>::value || MaxValue != T(0), 240 "Enum Bitfields must provide a MaxValue"); 241 static_assert(!std::is_enum<T>::value || 242 std::is_unsigned<IntegerType>::value, 243 "Enum must be unsigned"); 244 static_assert(std::is_integral<IntegerType>::value && 245 std::numeric_limits<IntegerType>::is_integer, 246 "IntegerType must be an integer type"); 247 248 static constexpr IntegerType UserMaxValue = 249 static_cast<IntegerType>(MaxValue); 250 }; 251 252 /// Unpacks the field from the `Packed` value. 253 template <typename Bitfield, typename StorageType> 254 static typename Bitfield::Type get(StorageType Packed) { 255 using I = bitfields_details::Impl<Bitfield, StorageType>; 256 return static_cast<typename Bitfield::Type>(I::extract(Packed)); 257 } 258 259 /// Return a non-zero value if the field is non-zero. 260 /// It is more efficient than `getField`. 261 template <typename Bitfield, typename StorageType> 262 static StorageType test(StorageType Packed) { 263 using I = bitfields_details::Impl<Bitfield, StorageType>; 264 return I::test(Packed); 265 } 266 267 /// Sets the typed value in the provided `Packed` value. 268 /// The method will asserts if the provided value is too big to fit in. 269 template <typename Bitfield, typename StorageType> 270 static void set(StorageType &Packed, typename Bitfield::Type Value) { 271 using I = bitfields_details::Impl<Bitfield, StorageType>; 272 I::update(Packed, static_cast<typename Bitfield::IntegerType>(Value)); 273 } 274 275 /// Returns whether the two bitfields share common bits. 276 template <typename A, typename B> static constexpr bool isOverlapping() { 277 return A::LastBit >= B::FirstBit && B::LastBit >= A::FirstBit; 278 } 279 280 template <typename A> static constexpr bool areContiguous() { return true; } 281 template <typename A, typename B, typename... Others> 282 static constexpr bool areContiguous() { 283 return A::NextBit == B::FirstBit && areContiguous<B, Others...>(); 284 } 285 }; 286 287 } // namespace llvm 288 289 #endif // LLVM_ADT_BITFIELDS_H 290