1 /*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef ART_LIBARTBASE_BASE_BIT_STRUCT_H_
18 #define ART_LIBARTBASE_BASE_BIT_STRUCT_H_
19
20 #include <type_traits>
21
22 #include "base/casts.h"
23 #include "bit_struct_detail.h"
24 #include "bit_utils.h"
25
26 //
27 // Zero-cost, type-safe, well-defined "structs" of bit fields.
28 //
29 // ---------------------------------------------
30 // Usage example:
31 // ---------------------------------------------
32 //
33 // // Definition for type 'Example'
34 // BITSTRUCT_DEFINE_START(Example, 10)
35 // BITSTRUCT_UINT(0, 2) u2; // Every field must be a BitStruct[*] with the same StorageType,
36 // BITSTRUCT_INT(2, 7) i7; // preferably using BITSTRUCT_{FIELD,UINT,INT}
37 // BITSTRUCT_UINT(9, 1) i1; // to fill in the StorageType parameter.
38 // BITSTRUCT_DEFINE_END(Example);
39 //
40 // Would define a bit struct with this layout:
41 // <- 1 -> <-- 7 --> <- 2 ->
42 // +--------+---------------+-----+
43 // | i1 | i7 | u2 +
44 // +--------+---------------+-----+
45 // 10 9 2 0
46 //
47 // // Read-write just like regular values.
48 // Example ex;
49 // ex.u2 = 3;
50 // ex.i7 = -25;
51 // ex.i1 = true;
52 // size_t u2 = ex.u2;
53 // int i7 = ex.i7;
54 // bool i1 = ex.i1;
55 //
56 // // It's packed down to the smallest # of machine words.
57 // assert(sizeof(Example) == 2);
58 // // The exact bit pattern is well-defined by the template parameters.
59 // uint16_t cast = *reinterpret_cast<uint16_t*>(ex);
60 // assert(cast == ((3) | (0b100111 << 2) | (true << 9);
61 //
62 // ---------------------------------------------
63 // Why not just use C++ bitfields?
64 // ---------------------------------------------
65 //
66 // The layout is implementation-defined.
67 // We do not know whether the fields are packed left-to-right or
68 // right-to-left, so it makes it useless when the memory layout needs to be
69 // precisely controlled.
70 //
71 // ---------------------------------------------
72 // More info:
73 // ---------------------------------------------
74 // Currently uintmax_t is the largest supported underlying storage type,
75 // all (kBitOffset + kBitWidth) must fit into BitSizeOf<uintmax_t>();
76 //
77 // Using BitStruct[U]int will automatically select an underlying type
78 // that's the smallest to fit your (offset + bitwidth).
79 //
80 // BitStructNumber can be used to manually select an underlying type.
81 //
82 // BitStructField can be used with custom standard-layout structs,
83 // thus allowing for arbitrary nesting of bit structs.
84 //
85 namespace art {
86 // Zero-cost wrapper around a struct 'T', allowing it to be stored as a bitfield
87 // at offset 'kBitOffset' and width 'kBitWidth'.
88 // The storage is plain unsigned int, whose size is the smallest required to fit
89 // 'kBitOffset + kBitWidth'. All operations to this become BitFieldExtract/BitFieldInsert
90 // operations to the underlying uint.
91 //
92 // Field memory representation:
93 //
94 // MSB <-- width --> LSB
95 // +--------+------------+--------+
96 // | ?????? | u bitfield | ?????? +
97 // +--------+------------+--------+
98 // offset 0
99 //
100 // Reading/writing the bitfield (un)packs it into a temporary T:
101 //
102 // MSB <-- width --> LSB
103 // +-----------------+------------+
104 // | 0.............0 | T bitfield |
105 // +-----------------+------------+
106 // 0
107 //
108 // It's the responsibility of the StorageType to ensure the bit representation
109 // of T can be represented by kBitWidth.
110 template <typename T,
111 size_t kBitOffset,
112 size_t kBitWidth,
113 typename StorageType>
114 struct BitStructField {
115 static_assert(std::is_standard_layout_v<T>, "T must be standard layout");
116
TBitStructField117 operator T() const {
118 return Get();
119 }
120
121 // Exclude overload when T==StorageType.
122 template <typename _ = void,
123 typename = std::enable_if_t<std::is_same_v<T, StorageType>, _>>
StorageTypeBitStructField124 explicit operator StorageType() const {
125 return BitFieldExtract(storage_, kBitOffset, kBitWidth);
126 }
127
128 BitStructField& operator=(T value) {
129 return Assign(*this, value);
130 }
131
BitStructSizeOfBitStructField132 static constexpr size_t BitStructSizeOf() {
133 return kBitWidth;
134 }
135
136 BitStructField& operator=(const BitStructField& other) {
137 // Warning. The default operator= will overwrite the entire storage!
138 return *this = static_cast<T>(other);
139 }
140
BitStructFieldBitStructField141 BitStructField(const BitStructField& other) {
142 Assign(*this, static_cast<T>(other));
143 }
144
145 BitStructField() = default;
146 ~BitStructField() = default;
147
148 protected:
149 template <typename T2>
AssignBitStructField150 T2& Assign(T2& what, T value) {
151 // Since C++ doesn't allow the type of operator= to change out
152 // in the subclass, reimplement operator= in each subclass
153 // manually and call this helper function.
154 static_assert(std::is_base_of_v<BitStructField, T2>, "T2 must inherit BitStructField");
155 what.Set(value);
156 return what;
157 }
158
GetBitStructField159 T Get() const {
160 ExtractionType storage = static_cast<ExtractionType>(storage_);
161 ExtractionType extracted = BitFieldExtract(storage, kBitOffset, kBitWidth);
162 ConversionType to_convert = dchecked_integral_cast<ConversionType>(extracted);
163 return ValueConverter::FromUnderlyingStorage(to_convert);
164 }
165
SetBitStructField166 void Set(T value) {
167 ConversionType converted = ValueConverter::ToUnderlyingStorage(value);
168 ExtractionType extracted = dchecked_integral_cast<ExtractionType>(converted);
169 storage_ = BitFieldInsert(storage_, extracted, kBitOffset, kBitWidth);
170 }
171
172 private:
173 using ValueConverter = detail::ValueConverter<T>;
174 using ConversionType = typename ValueConverter::StorageType;
175 using ExtractionType = std::conditional_t<std::is_signed_v<ConversionType>,
176 std::make_signed_t<StorageType>,
177 StorageType>;
178
179 StorageType storage_;
180 };
181
182 // Base class for number-like BitStruct fields.
183 // T is the type to store in as a bit field.
184 // kBitOffset, kBitWidth define the position and length of the bitfield.
185 //
186 // (Common usage should be BitStructInt, BitStructUint -- this
187 // intermediate template allows a user-defined integer to be used.)
188 template <typename T, size_t kBitOffset, size_t kBitWidth, typename StorageType>
189 struct BitStructNumber : public BitStructField<T, kBitOffset, kBitWidth, StorageType> {
190 BitStructNumber& operator=(T value) {
191 return BaseType::Assign(*this, value);
192 }
193
TBitStructNumber194 /*implicit*/ operator T() const {
195 return Get();
196 }
197
198 explicit operator bool() const {
199 return static_cast<bool>(Get());
200 }
201
202 BitStructNumber& operator++() {
203 *this = Get() + 1u;
204 return *this;
205 }
206
207 StorageType operator++(int) {
208 return Get() + 1u;
209 }
210
211 BitStructNumber& operator--() {
212 *this = Get() - 1u;
213 return *this;
214 }
215
216 StorageType operator--(int) {
217 return Get() - 1u;
218 }
219
220 private:
221 using BaseType = BitStructField<T, kBitOffset, kBitWidth, StorageType>;
222 using BaseType::Get;
223 };
224
225 // Create a BitStruct field which uses the smallest underlying int storage type,
226 // in order to be large enough to fit (kBitOffset + kBitWidth).
227 //
228 // Values are sign-extended when they are read out.
229 template <size_t kBitOffset, size_t kBitWidth, typename StorageType>
230 using BitStructInt =
231 BitStructNumber<typename detail::MinimumTypeHelper<int, kBitOffset + kBitWidth>::type,
232 kBitOffset,
233 kBitWidth,
234 StorageType>;
235
236 // Create a BitStruct field which uses the smallest underlying uint storage type,
237 // in order to be large enough to fit (kBitOffset + kBitWidth).
238 //
239 // Values are zero-extended when they are read out.
240 template <size_t kBitOffset, size_t kBitWidth, typename StorageType>
241 using BitStructUint =
242 BitStructNumber<typename detail::MinimumTypeHelper<unsigned int, kBitOffset + kBitWidth>::type,
243 kBitOffset,
244 kBitWidth,
245 StorageType>;
246
247 // Start a definition for a bitstruct.
248 // A bitstruct is defined to be a union with a common initial subsequence
249 // that we call 'DefineBitStructSize<bitwidth>'.
250 //
251 // See top of file for usage example.
252 //
253 // This marker is required by the C++ standard in order to
254 // have a "common initial sequence".
255 //
256 // See C++ 9.5.1 [class.union]:
257 // If a standard-layout union contains several standard-layout structs that share a common
258 // initial sequence ... it is permitted to inspect the common initial sequence of any of
259 // standard-layout struct members.
260 #define BITSTRUCT_DEFINE_START(name, bitwidth) \
261 union name { /* NOLINT */ \
262 using StorageType = \
263 typename detail::MinimumTypeUnsignedHelper<(bitwidth)>::type; \
264 art::detail::DefineBitStructSize<(bitwidth)> _; \
265 static constexpr size_t BitStructSizeOf() { return (bitwidth); } \
266 name& operator=(const name& other) { _ = other._; return *this; } /* NOLINT */ \
267 name(const name& other) : _(other._) {} \
268 name() = default; \
269 ~name() = default;
270
271 // Define a field. See top of file for usage example.
272 #define BITSTRUCT_FIELD(type, bit_offset, bit_width) \
273 BitStructField<type, (bit_offset), (bit_width), StorageType>
274 #define BITSTRUCT_INT(bit_offset, bit_width) \
275 BitStructInt<(bit_offset), (bit_width), StorageType>
276 #define BITSTRUCT_UINT(bit_offset, bit_width) \
277 BitStructUint<(bit_offset), (bit_width), StorageType>
278
279 // End the definition of a bitstruct, and insert a check
280 // to ensure that the bitstruct did not exceed the specified size.
281 //
282 // See top of file for usage example.
283 #define BITSTRUCT_DEFINE_END(name) \
284 }; \
285 static_assert(art::detail::ValidateBitStructSize<name>(), \
286 #name "bitsize incorrect: " \
287 "did you insert extra fields that weren't BitStructX, " \
288 "and does the size match the sum of the field widths?")
289
290 // Determine the minimal bit size for a user-defined type T.
291 // Used by BitStructField to determine how small a custom type is.
292 template <typename T>
BitStructSizeOf()293 static constexpr size_t BitStructSizeOf() {
294 return T::BitStructSizeOf();
295 }
296
297 } // namespace art
298
299 #endif // ART_LIBARTBASE_BASE_BIT_STRUCT_H_
300