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<T>::value, "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<T, StorageType>::value, _>>
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<BitStructField, T2>::value, "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 =
176       typename std::conditional<std::is_signed_v<ConversionType>,
177                                 std::make_signed_t<StorageType>,
178                                 StorageType>::type;
179 
180   StorageType storage_;
181 };
182 
183 // Base class for number-like BitStruct fields.
184 // T is the type to store in as a bit field.
185 // kBitOffset, kBitWidth define the position and length of the bitfield.
186 //
187 // (Common usage should be BitStructInt, BitStructUint -- this
188 // intermediate template allows a user-defined integer to be used.)
189 template <typename T, size_t kBitOffset, size_t kBitWidth, typename StorageType>
190 struct BitStructNumber : public BitStructField<T, kBitOffset, kBitWidth, StorageType> {
191   BitStructNumber& operator=(T value) {
192     return BaseType::Assign(*this, value);
193   }
194 
TBitStructNumber195   /*implicit*/ operator T() const {
196     return Get();
197   }
198 
199   explicit operator bool() const {
200     return static_cast<bool>(Get());
201   }
202 
203   BitStructNumber& operator++() {
204     *this = Get() + 1u;
205     return *this;
206   }
207 
208   StorageType operator++(int) {
209     return Get() + 1u;
210   }
211 
212   BitStructNumber& operator--() {
213     *this = Get() - 1u;
214     return *this;
215   }
216 
217   StorageType operator--(int) {
218     return Get() - 1u;
219   }
220 
221  private:
222   using BaseType = BitStructField<T, kBitOffset, kBitWidth, StorageType>;
223   using BaseType::Get;
224 };
225 
226 // Create a BitStruct field which uses the smallest underlying int storage type,
227 // in order to be large enough to fit (kBitOffset + kBitWidth).
228 //
229 // Values are sign-extended when they are read out.
230 template <size_t kBitOffset, size_t kBitWidth, typename StorageType>
231 using BitStructInt =
232     BitStructNumber<typename detail::MinimumTypeHelper<int, kBitOffset + kBitWidth>::type,
233                     kBitOffset,
234                     kBitWidth,
235                     StorageType>;
236 
237 // Create a BitStruct field which uses the smallest underlying uint storage type,
238 // in order to be large enough to fit (kBitOffset + kBitWidth).
239 //
240 // Values are zero-extended when they are read out.
241 template <size_t kBitOffset, size_t kBitWidth, typename StorageType>
242 using BitStructUint =
243     BitStructNumber<typename detail::MinimumTypeHelper<unsigned int, kBitOffset + kBitWidth>::type,
244                     kBitOffset,
245                     kBitWidth,
246                     StorageType>;
247 
248 // Start a definition for a bitstruct.
249 // A bitstruct is defined to be a union with a common initial subsequence
250 // that we call 'DefineBitStructSize<bitwidth>'.
251 //
252 // See top of file for usage example.
253 //
254 // This marker is required by the C++ standard in order to
255 // have a "common initial sequence".
256 //
257 // See C++ 9.5.1 [class.union]:
258 // If a standard-layout union contains several standard-layout structs that share a common
259 // initial sequence ... it is permitted to inspect the common initial sequence of any of
260 // standard-layout struct members.
261 #define BITSTRUCT_DEFINE_START(name, bitwidth)                                        \
262     union name {                                                         /* NOLINT */ \
263       using StorageType =                                                             \
264           typename detail::MinimumTypeUnsignedHelper<(bitwidth)>::type;               \
265       art::detail::DefineBitStructSize<(bitwidth)> _;                                 \
266       static constexpr size_t BitStructSizeOf() { return (bitwidth); }                \
267       name& operator=(const name& other) { _ = other._; return *this; }  /* NOLINT */ \
268       name(const name& other) : _(other._) {}                                         \
269       name() = default;                                                               \
270       ~name() = default;
271 
272 // Define a field. See top of file for usage example.
273 #define BITSTRUCT_FIELD(type, bit_offset, bit_width)                           \
274     BitStructField<type, (bit_offset), (bit_width), StorageType>
275 #define BITSTRUCT_INT(bit_offset, bit_width)                                   \
276     BitStructInt<(bit_offset), (bit_width), StorageType>
277 #define BITSTRUCT_UINT(bit_offset, bit_width)                                  \
278     BitStructUint<(bit_offset), (bit_width), StorageType>
279 
280 // End the definition of a bitstruct, and insert a sanity check
281 // to ensure that the bitstruct did not exceed the specified size.
282 //
283 // See top of file for usage example.
284 #define BITSTRUCT_DEFINE_END(name)                                             \
285     };                                                                         \
286     static_assert(art::detail::ValidateBitStructSize<name>(),                  \
287                   #name "bitsize incorrect: "                                  \
288                   "did you insert extra fields that weren't BitStructX, "      \
289                   "and does the size match the sum of the field widths?")
290 
291 // Determine the minimal bit size for a user-defined type T.
292 // Used by BitStructField to determine how small a custom type is.
293 template <typename T>
BitStructSizeOf()294 static constexpr size_t BitStructSizeOf() {
295   return T::BitStructSizeOf();
296 }
297 
298 }  // namespace art
299 
300 #endif  // ART_LIBARTBASE_BASE_BIT_STRUCT_H_
301