1 // Copyright 2019 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_BASE_BIT_FIELD_H_ 6 #define V8_BASE_BIT_FIELD_H_ 7 8 #include <stdint.h> 9 10 #include "src/base/macros.h" 11 12 namespace v8 { 13 namespace base { 14 15 // ---------------------------------------------------------------------------- 16 // BitField is a help template for encoding and decode bitfield with 17 // unsigned content. 18 // Instantiate them via 'using', which is cheaper than deriving a new class: 19 // using MyBitField = base::BitField<MyEnum, 4, 2>; 20 // The BitField class is final to enforce this style over derivation. 21 22 template <class T, int shift, int size, class U = uint32_t> 23 class BitField final { 24 public: 25 STATIC_ASSERT(std::is_unsigned<U>::value); 26 STATIC_ASSERT(shift < 8 * sizeof(U)); // Otherwise shifts by {shift} are UB. 27 STATIC_ASSERT(size < 8 * sizeof(U)); // Otherwise shifts by {size} are UB. 28 STATIC_ASSERT(shift + size <= 8 * sizeof(U)); 29 STATIC_ASSERT(size > 0); 30 31 using FieldType = T; 32 33 // A type U mask of bit field. To use all bits of a type U of x bits 34 // in a bitfield without compiler warnings we have to compute 2^x 35 // without using a shift count of x in the computation. 36 static constexpr int kShift = shift; 37 static constexpr int kSize = size; 38 static constexpr U kMask = ((U{1} << kShift) << kSize) - (U{1} << kShift); 39 static constexpr int kLastUsedBit = kShift + kSize - 1; 40 static constexpr U kNumValues = U{1} << kSize; 41 42 // Value for the field with all bits set. 43 static constexpr T kMax = static_cast<T>(kNumValues - 1); 44 45 template <class T2, int size2> 46 using Next = BitField<T2, kShift + kSize, size2, U>; 47 48 // Tells whether the provided value fits into the bit field. is_valid(T value)49 static constexpr bool is_valid(T value) { 50 return (static_cast<U>(value) & ~static_cast<U>(kMax)) == 0; 51 } 52 53 // Returns a type U with the bit field value encoded. encode(T value)54 static constexpr U encode(T value) { 55 DCHECK(is_valid(value)); 56 return static_cast<U>(value) << kShift; 57 } 58 59 // Returns a type U with the bit field value updated. update(U previous,T value)60 static constexpr U update(U previous, T value) { 61 return (previous & ~kMask) | encode(value); 62 } 63 64 // Extracts the bit field from the value. decode(U value)65 static constexpr T decode(U value) { 66 return static_cast<T>((value & kMask) >> kShift); 67 } 68 }; 69 70 template <class T, int shift, int size> 71 using BitField8 = BitField<T, shift, size, uint8_t>; 72 73 template <class T, int shift, int size> 74 using BitField16 = BitField<T, shift, size, uint16_t>; 75 76 template <class T, int shift, int size> 77 using BitField64 = BitField<T, shift, size, uint64_t>; 78 79 // Helper macros for defining a contiguous sequence of bit fields. Example: 80 // (backslashes at the ends of respective lines of this multi-line macro 81 // definition are omitted here to please the compiler) 82 // 83 // #define MAP_BIT_FIELD1(V, _) 84 // V(IsAbcBit, bool, 1, _) 85 // V(IsBcdBit, bool, 1, _) 86 // V(CdeBits, int, 5, _) 87 // V(DefBits, MutableMode, 1, _) 88 // 89 // DEFINE_BIT_FIELDS(MAP_BIT_FIELD1) 90 // or 91 // DEFINE_BIT_FIELDS_64(MAP_BIT_FIELD1) 92 // 93 #define DEFINE_BIT_FIELD_RANGE_TYPE(Name, Type, Size, _) \ 94 k##Name##Start, k##Name##End = k##Name##Start + Size - 1, 95 96 #define DEFINE_BIT_RANGES(LIST_MACRO) \ 97 struct LIST_MACRO##_Ranges { \ 98 enum { LIST_MACRO(DEFINE_BIT_FIELD_RANGE_TYPE, _) kBitsCount }; \ 99 }; 100 101 #define DEFINE_BIT_FIELD_TYPE(Name, Type, Size, RangesName) \ 102 using Name = base::BitField<Type, RangesName::k##Name##Start, Size>; 103 104 #define DEFINE_BIT_FIELD_64_TYPE(Name, Type, Size, RangesName) \ 105 using Name = base::BitField64<Type, RangesName::k##Name##Start, Size>; 106 107 #define DEFINE_BIT_FIELDS(LIST_MACRO) \ 108 DEFINE_BIT_RANGES(LIST_MACRO) \ 109 LIST_MACRO(DEFINE_BIT_FIELD_TYPE, LIST_MACRO##_Ranges) 110 111 #define DEFINE_BIT_FIELDS_64(LIST_MACRO) \ 112 DEFINE_BIT_RANGES(LIST_MACRO) \ 113 LIST_MACRO(DEFINE_BIT_FIELD_64_TYPE, LIST_MACRO##_Ranges) 114 115 // ---------------------------------------------------------------------------- 116 // BitSetComputer is a help template for encoding and decoding information for 117 // a variable number of items in an array. 118 // 119 // To encode boolean data in a smi array you would use: 120 // using BoolComputer = BitSetComputer<bool, 1, kSmiValueSize, uint32_t>; 121 // 122 template <class T, int kBitsPerItem, int kBitsPerWord, class U> 123 class BitSetComputer { 124 public: 125 static const int kItemsPerWord = kBitsPerWord / kBitsPerItem; 126 static const int kMask = (1 << kBitsPerItem) - 1; 127 128 // The number of array elements required to embed T information for each item. word_count(int items)129 static int word_count(int items) { 130 if (items == 0) return 0; 131 return (items - 1) / kItemsPerWord + 1; 132 } 133 134 // The array index to look at for item. index(int base_index,int item)135 static int index(int base_index, int item) { 136 return base_index + item / kItemsPerWord; 137 } 138 139 // Extract T data for a given item from data. decode(U data,int item)140 static T decode(U data, int item) { 141 return static_cast<T>((data >> shift(item)) & kMask); 142 } 143 144 // Return the encoding for a store of value for item in previous. encode(U previous,int item,T value)145 static U encode(U previous, int item, T value) { 146 int shift_value = shift(item); 147 int set_bits = (static_cast<int>(value) << shift_value); 148 return (previous & ~(kMask << shift_value)) | set_bits; 149 } 150 shift(int item)151 static int shift(int item) { return (item % kItemsPerWord) * kBitsPerItem; } 152 }; 153 154 } // namespace base 155 } // namespace v8 156 157 #endif // V8_BASE_BIT_FIELD_H_ 158