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 | |

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 | |

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 |