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
89namespace llvm {
90
91namespace bitfields_details {
92
93/// A struct defining useful bit patterns for n-bits integer types.
94template <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 = std::make_unsigned_t<T>;
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.
120template <typename T, unsigned Bits, bool = std::is_unsigned<T>::value>
121struct Compressor {
122  static_assert(std::is_unsigned<T>::value, "T must be unsigned");
123  using BP = BitPatterns<T, Bits>;
124
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");
128    return UserValue;
129  }
130
131  static T unpack(T StorageValue) { return StorageValue; }
132};
133
134template <typename T, unsigned Bits> struct Compressor<T, Bits, false> {
135  static_assert(std::is_signed<T>::value, "T must be 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.
156template <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.
196template <typename T, bool = std::is_enum<T>::value>
197struct ResolveUnderlyingType {
198  using type = std::underlying_type_t<T>;
199};
200template <typename T> struct ResolveUnderlyingType<T, false> {
201  using type = T;
202};
203template <> struct ResolveUnderlyingType<bool, false> {
204  /// In case sizeof(bool) != 1, replace `void` by an additionnal
205  /// std::conditional.
206  using type = std::conditional_t<sizeof(bool) == 1, uint8_t, void>;
207};
208
209} // namespace bitfields_details
210
211/// Holds functions to get, set or test bitfields.
212struct 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