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 "base/bit_utils.h"
21#include "bit_struct_detail.h"
22
23//
24// Zero-cost, type-safe, well-defined "structs" of bit fields.
25//
26// ---------------------------------------------
27// Usage example:
28// ---------------------------------------------
29//
30//   // Definition for type 'Example'
31//   BITSTRUCT_DEFINE_START(Example, 10)
32//     BitStructUint<0, 2> u2;     // Every field must be a BitStruct[*].
33//     BitStructInt<2, 7>  i7;
34//     BitStructUint<9, 1> i1;
35//   BITSTRUCT_DEFINE_END(Example);
36//
37//  Would define a bit struct with this layout:
38//   <- 1 ->    <--  7  -->  <- 2 ->
39//  +--------+---------------+-----+
40//  |   i1   |       i7      | u2  +
41//  +--------+---------------+-----+
42//  10       9               2     0
43//
44//   // Read-write just like regular values.
45//   Example ex;
46//   ex.u2 = 3;
47//   ex.i7 = -25;
48//   ex.i1 = true;
49//   size_t u2 = ex.u2;
50//   int i7 = ex.i7;
51//   bool i1 = ex.i1;
52//
53//   // It's packed down to the smallest # of machine words.
54//   assert(sizeof(Example) == 2);
55//   // The exact bit pattern is well-defined by the template parameters.
56//   uint16_t cast = *reinterpret_cast<uint16_t*>(ex);
57//   assert(cast == ((3) | (0b100111 << 2) | (true << 9);
58//
59// ---------------------------------------------
60// Why not just use C++ bitfields?
61// ---------------------------------------------
62//
63// The layout is implementation-defined.
64// We do not know whether the fields are packed left-to-right or
65// right-to-left, so it makes it useless when the memory layout needs to be
66// precisely controlled.
67//
68// ---------------------------------------------
69// More info:
70// ---------------------------------------------
71// Currently uintmax_t is the largest supported underlying storage type,
72// all (kBitOffset + kBitWidth) must fit into BitSizeOf<uintmax_t>();
73//
74// Using BitStruct[U]int will automatically select an underlying type
75// that's the smallest to fit your (offset + bitwidth).
76//
77// BitStructNumber can be used to manually select an underlying type.
78//
79// BitStructField can be used with custom standard-layout structs,
80// thus allowing for arbitrary nesting of bit structs.
81//
82namespace art {
83// Zero-cost wrapper around a struct 'T', allowing it to be stored as a bitfield
84// at offset 'kBitOffset' and width 'kBitWidth'.
85// The storage is plain unsigned int, whose size is the smallest required  to fit
86// 'kBitOffset + kBitWidth'. All operations to this become BitFieldExtract/BitFieldInsert
87// operations to the underlying uint.
88//
89// Field memory representation:
90//
91// MSB      <-- width  -->      LSB
92// +--------+------------+--------+
93// | ?????? | u bitfield | ?????? +
94// +--------+------------+--------+
95//                       offset   0
96//
97// Reading/writing the bitfield (un)packs it into a temporary T:
98//
99// MSB               <-- width  --> LSB
100// +-----------------+------------+
101// | 0.............0 | T bitfield |
102// +-----------------+------------+
103//                                0
104//
105// It's the responsibility of the StorageType to ensure the bit representation
106// of T can be represented by kBitWidth.
107template <typename T,
108          size_t kBitOffset,
109          size_t kBitWidth = BitStructSizeOf<T>(),
110          typename StorageType = typename detail::MinimumTypeUnsignedHelper<kBitOffset + kBitWidth>::type>
111struct BitStructField {
112  static_assert(std::is_standard_layout<T>::value, "T must be standard layout");
113
114  operator T() const {
115    return Get();
116  }
117
118  // Exclude overload when T==StorageType.
119  template <typename _ = void,
120            typename = std::enable_if_t<std::is_same<T, StorageType>::value, _>>
121  explicit operator StorageType() const {
122    return GetStorage();
123  }
124
125  BitStructField& operator=(T value) {
126    return Assign(*this, value);
127  }
128
129  static constexpr size_t BitStructSizeOf() {
130    return kBitWidth;
131  }
132
133  BitStructField& operator=(const BitStructField& other) {
134    // Warning. The default operator= will overwrite the entire storage!
135    return *this = static_cast<T>(other);
136  }
137
138  BitStructField(const BitStructField& other) {
139    Assign(*this, static_cast<T>(other));
140  }
141
142  BitStructField() = default;
143  ~BitStructField() = default;
144
145 protected:
146  template <typename T2>
147  T2& Assign(T2& what, T value) {
148    // Since C++ doesn't allow the type of operator= to change out
149    // in the subclass, reimplement operator= in each subclass
150    // manually and call this helper function.
151    static_assert(std::is_base_of<BitStructField, T2>::value, "T2 must inherit BitStructField");
152    what.Set(value);
153    return what;
154  }
155
156  T Get() const {
157    ValueStorage vs;
158    vs.pod_.val_ = GetStorage();
159    return vs.value_;
160  }
161
162  void Set(T value) {
163    ValueStorage value_as_storage;
164    value_as_storage.value_ = value;
165
166    storage_.pod_.val_ = BitFieldInsert(storage_.pod_.val_,
167                                        value_as_storage.pod_.val_,
168                                        kBitOffset,
169                                        kBitWidth);
170  }
171
172 private:
173  StorageType GetStorage() const {
174    return BitFieldExtract(storage_.pod_.val_, kBitOffset, kBitWidth);
175  }
176
177  // Underlying value must be wrapped in a separate standard-layout struct.
178  // See below for more details.
179  struct PodWrapper {
180    StorageType val_;
181  };
182
183  union ValueStorage {
184    // Safely alias pod_ and value_ together.
185    //
186    // See C++ 9.5.1 [class.union]:
187    // If a standard-layout union contains several standard-layout structs that share a common
188    // initial sequence ... it is permitted to inspect the common initial sequence of any of
189    // standard-layout struct members.
190    PodWrapper pod_;
191    T value_;
192  } storage_;
193
194  // Future work: In theory almost non-standard layout can be supported here,
195  // assuming they don't rely on the address of (this).
196  // We just have to use memcpy since the union-aliasing would not work.
197};
198
199// Base class for number-like BitStruct fields.
200// T is the type to store in as a bit field.
201// kBitOffset, kBitWidth define the position and length of the bitfield.
202//
203// (Common usage should be BitStructInt, BitStructUint -- this
204// intermediate template allows a user-defined integer to be used.)
205template <typename T, size_t kBitOffset, size_t kBitWidth>
206struct BitStructNumber : public BitStructField<T, kBitOffset, kBitWidth, /*StorageType*/T> {
207  using StorageType = T;
208
209  BitStructNumber& operator=(T value) {
210    return BaseType::Assign(*this, value);
211  }
212
213  /*implicit*/ operator T() const {
214    return Get();
215  }
216
217  explicit operator bool() const {
218    return static_cast<bool>(Get());
219  }
220
221  BitStructNumber& operator++() {
222    *this = Get() + 1u;
223    return *this;
224  }
225
226  StorageType operator++(int) {
227    return Get() + 1u;
228  }
229
230  BitStructNumber& operator--() {
231    *this = Get() - 1u;
232    return *this;
233  }
234
235  StorageType operator--(int) {
236    return Get() - 1u;
237  }
238
239 private:
240  using BaseType = BitStructField<T, kBitOffset, kBitWidth, /*StorageType*/T>;
241  using BaseType::Get;
242};
243
244// Create a BitStruct field which uses the smallest underlying int storage type,
245// in order to be large enough to fit (kBitOffset + kBitWidth).
246//
247// Values are sign-extended when they are read out.
248template <size_t kBitOffset, size_t kBitWidth>
249using BitStructInt =
250    BitStructNumber<typename detail::MinimumTypeHelper<int, kBitOffset + kBitWidth>::type,
251                    kBitOffset,
252                    kBitWidth>;
253
254// Create a BitStruct field which uses the smallest underlying uint storage type,
255// in order to be large enough to fit (kBitOffset + kBitWidth).
256//
257// Values are zero-extended when they are read out.
258template <size_t kBitOffset, size_t kBitWidth>
259using BitStructUint =
260    BitStructNumber<typename detail::MinimumTypeHelper<unsigned int, kBitOffset + kBitWidth>::type,
261                    kBitOffset,
262                    kBitWidth>;
263
264// Start a definition for a bitstruct.
265// A bitstruct is defined to be a union with a common initial subsequence
266// that we call 'DefineBitStructSize<bitwidth>'.
267//
268// See top of file for usage example.
269//
270// This marker is required by the C++ standard in order to
271// have a "common initial sequence".
272//
273// See C++ 9.5.1 [class.union]:
274// If a standard-layout union contains several standard-layout structs that share a common
275// initial sequence ... it is permitted to inspect the common initial sequence of any of
276// standard-layout struct members.
277#define BITSTRUCT_DEFINE_START(name, bitwidth)                                 \
278    union name {                                                               \
279      art::detail::DefineBitStructSize<(bitwidth)> _;                          \
280      static constexpr size_t BitStructSizeOf() { return (bitwidth); }         \
281      name& operator=(const name& other) { _ = other._; return *this; }        \
282      name(const name& other) : _(other._) {}                                  \
283      name() = default;                                                        \
284      ~name() = default;
285
286// End the definition of a bitstruct, and insert a sanity check
287// to ensure that the bitstruct did not exceed the specified size.
288//
289// See top of file for usage example.
290#define BITSTRUCT_DEFINE_END(name)                                             \
291    };                                                                         \
292    static_assert(art::detail::ValidateBitStructSize<name>(),                  \
293                  #name "bitsize incorrect: "                                  \
294                  "did you insert extra fields that weren't BitStructX, "      \
295                  "and does the size match the sum of the field widths?")
296
297// Determine the minimal bit size for a user-defined type T.
298// Used by BitStructField to determine how small a custom type is.
299template <typename T>
300static constexpr size_t BitStructSizeOf() {
301  return T::BitStructSizeOf();
302}
303
304}  // namespace art
305
306#endif  // ART_LIBARTBASE_BASE_BIT_STRUCT_H_
307