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 // 82 namespace 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. 107 template <typename T, 108 size_t kBitOffset, 109 size_t kBitWidth = BitStructSizeOf<T>(), 110 typename StorageType = typename detail::MinimumTypeUnsignedHelper<kBitOffset + kBitWidth>::type> 111 struct 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.) 205 template <typename T, size_t kBitOffset, size_t kBitWidth> 206 struct 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. 248 template <size_t kBitOffset, size_t kBitWidth> 249 using 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. 258 template <size_t kBitOffset, size_t kBitWidth> 259 using 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. 299 template <typename T> 300 static constexpr size_t BitStructSizeOf() { 301 return T::BitStructSizeOf(); 302 } 303 304 } // namespace art 305 306 #endif // ART_LIBARTBASE_BASE_BIT_STRUCT_H_ 307