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 117 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, _>> 124 explicit operator StorageType() const { 125 return BitFieldExtract(storage_, kBitOffset, kBitWidth); 126 } 127 128 BitStructField& operator=(T value) { 129 return Assign(*this, value); 130 } 131 132 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 141 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> 150 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 159 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 166 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 195 /*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 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> 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