1 //===-- llvm/ADT/Bitfield.h - Get and Set bits in an integer ---*- C++ -*--===//
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
7 //===----------------------------------------------------------------------===//
10 /// This file implements methods to test, set and extract typed bits from packed
11 /// unsigned integers.
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.
21 /// The methods provided in this file ensure precise control over the
22 /// layout/storage as well as protection against out of range values.
27 /// uint8_t Storage = 0;
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);
34 /// EXPECT_EQ(Bitfield::get<Bool>(Storage), true);
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);
44 /// EXPECT_EQ(Bitfield::get<Suit>(Storage), SuitEnum::HEARTS);
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);
51 /// EXPECT_EQ(Bitfield::get<Value>(Storage), 10U);
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);
58 /// EXPECT_EQ(Bitfield::get<SignedValue>(Storage), -2);
60 /// // Ability to efficiently test if a field is non zero.
61 /// EXPECT_TRUE(Bitfield::test<Value>(Storage));
63 /// // Alter Storage changes value.
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);
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);
77 //===----------------------------------------------------------------------===//
79 #ifndef LLVM_ADT_BITFIELDS_H
80 #define LLVM_ADT_BITFIELDS_H
83 #include <climits> // CHAR_BIT
84 #include <cstddef> // size_t
85 #include <cstdint> // uintXX_t
86 #include <limits> // numeric_limits
87 #include <type_traits>
91 namespace bitfields_details {
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");
102 static constexpr unsigned TypeBits = sizeof(Unsigned) * CHAR_BIT;
103 static_assert(TypeBits >= Bits, "n-bit must fit in T");
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
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>
122 static_assert(std::is_unsigned<T>::value, "T is unsigned");
123 using BP = BitPatterns<T, Bits>;
125 static T pack(T UserValue, T UserMaxValue) {
126 assert(UserValue <= UserMaxValue && "value is too big");
127 assert(UserValue <= BP::Umax && "value is too big");
131 static T unpack(T StorageValue) { return StorageValue; }
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>;
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");
143 UserValue &= ~BP::SignExtend;
147 static T unpack(T StorageValue) {
148 if (StorageValue >= T(BP::SignBitMask))
149 StorageValue |= BP::SignExtend;
154 /// Impl is where Bifield description and Storage are put together to interact
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>;
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;
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);
173 Packed |= StorageValue << Bitfield::Shift;
176 /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as
178 static IntegerType extract(StorageType Packed) {
179 const StorageType StorageValue = (Packed & Mask) >> Bitfield::Shift;
180 return C::unpack(StorageValue);
183 /// Interprets bits between `FirstBit` and `LastBit` of `Packed` as
185 static StorageType test(StorageType Packed) { return Packed & Mask; }
188 /// `Bitfield` deals with the following type:
190 /// - signed and unsigned integer
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
196 template <typename T, bool = std::is_enum<T>::value>
197 struct ResolveUnderlyingType {
198 using type = typename std::underlying_type<T>::type;
200 template <typename T> struct ResolveUnderlyingType<T, false> {
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;
209 } // namespace bitfields_details
211 /// Holds functions to get, set or test bitfields.
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()>
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;
234 template <typename, typename> friend struct bitfields_details::Impl;
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");
248 static constexpr IntegerType UserMaxValue =
249 static_cast<IntegerType>(MaxValue);
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));
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);
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));
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;
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...>();
289 #endif // LLVM_ADT_BITFIELDS_H