// Copyright 2019 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_BASE_BIT_FIELD_H_
#define V8_BASE_BIT_FIELD_H_
#include <stdint.h>
#include <algorithm>
#include <type_traits>
#include <utility>
#include "src/base/macros.h"
#include "src/base/strong-alias.h"
namespace v8::base {
namespace bitfield_detail {
template <typename T>
static constexpr auto to_value(T value) {
if constexpr (is_strong_alias_v<T>) {
return value.value();
} else {
return value;
}
}
} // namespace bitfield_detail
// ----------------------------------------------------------------------------
// BitField is a help template for encoding and decode bitfield with
// unsigned content.
// Instantiate them via 'using', which is cheaper than deriving a new class:
// using MyBitField = base::BitField<MyEnum, 4, 2>;
// The BitField class is final to enforce this style over derivation.
template <class T, int shift, int size, class U = uint32_t>
class BitField final {
public:
static constexpr auto to_value(T value) {
return bitfield_detail::to_value(value);
}
using TValue = decltype(to_value(std::declval<T>()));
static_assert(std::is_unsigned_v<U>);
static_assert(shift < 8 * sizeof(U)); // Otherwise shifts by {shift} are UB.
static_assert(size < 8 * sizeof(U)); // Otherwise shifts by {size} are UB.
static_assert(shift + size <= 8 * sizeof(U));
static_assert(size > 0);
static_assert(sizeof(TValue) == sizeof(T));
// Make sure we don't create bitfields that are too large for their value.
// Carve out an exception for 32-bit size_t, for uniformity between 32-bit
// and 64-bit code.
static_assert(size <= 8 * sizeof(T) ||
(std::is_same_v<T, size_t> && sizeof(size_t) == 4),
"Bitfield is unnecessarily big!");
static_assert(!std::is_same_v<TValue, bool> || size == 1,
"Bitfield is unnecessarily big!");
using FieldType = T;
using BaseType = U;
// A type U mask of bit field. To use all bits of a type U of x bits
// in a bitfield without compiler warnings we have to compute 2^x
// without using a shift count of x in the computation.
static constexpr int kShift = shift;
static constexpr int kSize = size;
static constexpr U kMask = ((U{1} << kShift) << kSize) - (U{1} << kShift);
static constexpr int kLastUsedBit = kShift + kSize - 1;
static constexpr U kNumValues = U{1} << kSize;
static constexpr U kMax = kNumValues - 1;
template <class T2, int size2>
using Next = BitField<T2, kShift + kSize, size2, U>;
// Tells whether the provided value fits into the bit field.
static constexpr bool is_valid(T value) {
return (static_cast<U>(to_value(value)) & ~kMax) == 0;
}
// Returns a type U with the bit field value encoded.
static constexpr U encode(T value) {
if constexpr (std::is_enum_v<TValue> || sizeof(TValue) * 8 <= kSize ||
std::is_same_v<TValue, bool>) {
// For enums, we trust that they are within the valid range, since they
// are typed and we assume that the enum itself has a valid value. DCHECK
// just in case (e.g. in case valid enum values are outside the bitfield
// size).
//
// Similarly, if T fits exactly in the bitfield (either in bytes, or
// because bools can be stored as 1 bit), we trust that they are valid.
DCHECK(is_valid(value));
} else {
// For non-enums (in practice, integers), we don't trust that they are
// valid, since we pass them around without static value interval
// information.
CHECK(is_valid(value));
}
return static_cast<U>(to_value(value)) << kShift;
}
// Returns a type U with the bit field value updated.
V8_NODISCARD static constexpr U update(U previous, T value) {
return (previous & ~kMask) | encode(value);
}
// Extracts the bit field from the value.
static constexpr T decode(U value) {
return static_cast<T>((value & kMask) >> kShift);
}
};
// ----------------------------------------------------------------------------
// BitFieldUnion can be used to combine two linear BitFields.
// So far only the static mask is computed. Encoding and decoding tbd.
// Can be used for example as a quick combined check:
// `if (BitFieldUnion<BFA, BFB>::kMask & bitfield) ...`
template <typename A, typename B>
class BitFieldUnion final {
public:
static_assert(std::is_same_v<typename A::BaseType, typename B::BaseType>);
static_assert((A::kMask & B::kMask) == 0);
static constexpr int kShift = std::min(A::kShift, B::kShift);
static constexpr int kMask = A::kMask | B::kMask;
static constexpr int kSize =
A::kSize + B::kSize + (std::max(A::kShift, B::kShift) - kShift);
};
template <class T, int shift, int size>
using BitField8 = BitField<T, shift, size, uint8_t>;
template <class T, int shift, int size>
using BitField16 = BitField<T, shift, size, uint16_t>;
template <class T, int shift, int size>
using BitField64 = BitField<T, shift, size, uint64_t>;
// Helper macros for defining a contiguous sequence of bit fields. Example:
// (backslashes at the ends of respective lines of this multi-line macro
// definition are omitted here to please the compiler)
//
// #define MAP_BIT_FIELD1(V, _)
// V(IsAbcBit, bool, 1, _)
// V(IsBcdBit, bool, 1, _)
// V(CdeBits, int, 5, _)
// V(DefBits, MutableMode, 1, _)
//
// DEFINE_BIT_FIELDS(MAP_BIT_FIELD1)
// or
// DEFINE_BIT_FIELDS_64(MAP_BIT_FIELD1)
//
#define DEFINE_BIT_FIELD_RANGE_TYPE(Name, Type, Size, _) \
k##Name##Start, k##Name##End = k##Name##Start + Size - 1,
#define DEFINE_BIT_RANGES(LIST_MACRO) \
struct LIST_MACRO##_Ranges { \
enum { LIST_MACRO(DEFINE_BIT_FIELD_RANGE_TYPE, _) kBitsCount }; \
};
#define DEFINE_BIT_FIELD_TYPE(Name, Type, Size, RangesName) \
using Name = base::BitField<Type, RangesName::k##Name##Start, Size>;
#define DEFINE_BIT_FIELD_64_TYPE(Name, Type, Size, RangesName) \
using Name = base::BitField64<Type, RangesName::k##Name##Start, Size>;
#define DEFINE_BIT_FIELDS(LIST_MACRO) \
DEFINE_BIT_RANGES(LIST_MACRO) \
LIST_MACRO(DEFINE_BIT_FIELD_TYPE, LIST_MACRO##_Ranges)
#define DEFINE_BIT_FIELDS_64(LIST_MACRO) \
DEFINE_BIT_RANGES(LIST_MACRO) \
LIST_MACRO(DEFINE_BIT_FIELD_64_TYPE, LIST_MACRO##_Ranges)
// ----------------------------------------------------------------------------
// BitSetComputer is a help template for encoding and decoding information for
// a variable number of items in an array.
//
// To encode boolean data in a smi array you would use:
// using BoolComputer = BitSetComputer<bool, 1, kSmiValueSize, uint32_t>;
//
template <class T, int kBitsPerItem, int kBitsPerWord, class U>
class BitSetComputer {
public:
static constexpr auto to_value(T value) {
return bitfield_detail::to_value(value);
}
using TValue = decltype(to_value(std::declval<T>()));
static const int kItemsPerWord = kBitsPerWord / kBitsPerItem;
static const int kMask = (1 << kBitsPerItem) - 1;
static_assert(sizeof(TValue) == sizeof(T));
// The number of array elements required to embed T information for each item.
static int word_count(int items) {
if (items == 0) return 0;
return (items - 1) / kItemsPerWord + 1;
}
// The array index to look at for item.
static int index(int base_index, int item) {
return base_index + item / kItemsPerWord;
}
// Extract T data for a given item from data.
static T decode(U data, int item) {
return static_cast<T>((data >> shift(item)) & kMask);
}
// Return the encoding for a store of value for item in previous.
static U encode(U previous, int item, T value) {
int shift_value = shift(item);
TValue value_val = to_value(value);
int set_bits = (static_cast<int>(value_val) << shift_value);
return (previous & ~(kMask << shift_value)) | set_bits;
}
static int shift(int item) { return (item % kItemsPerWord) * kBitsPerItem; }
};
} // namespace v8::base
#endif // V8_BASE_BIT_FIELD_H_