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