/*
* Copyright (C) 2017 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#ifndef ART_LIBARTBASE_BASE_BIT_STRING_H_
#define ART_LIBARTBASE_BASE_BIT_STRING_H_
#include "bit_struct.h"
#include "bit_utils.h"
#include <ostream>
namespace art {
struct BitStringChar;
inline std::ostream& operator<<(std::ostream& os, const BitStringChar& bc);
/**
* A BitStringChar is a light-weight wrapper to read/write a single character
* into a BitString, while restricting the bitlength.
*
* This is only intended for reading/writing into temporaries, as the representation is
* inefficient for memory (it uses a word for the character and another word for the bitlength).
*
* See also BitString below.
*/
struct BitStringChar {
using StorageType = uint32_t;
static_assert(std::is_unsigned<StorageType>::value, "BitStringChar::StorageType must be unsigned");
// BitStringChars are always zero-initialized by default. Equivalent to BitStringChar(0,0).
BitStringChar() : data_(0u), bitlength_(0u) { }
// Create a new BitStringChar whose data bits can be at most bitlength.
BitStringChar(StorageType data, size_t bitlength)
: data_(data), bitlength_(bitlength) {
// All bits higher than bitlength must be set to 0.
DCHECK_EQ(0u, data & ~MaskLeastSignificant(bitlength_))
<< "BitStringChar data out of range, data: " << data << ", bitlength: " << bitlength;
}
// What is the bitlength constraint for this character?
// (Data could use less bits, but this is the maximum bit capacity at that BitString position).
size_t GetBitLength() const {
return bitlength_;
}
// Is there any capacity in this BitStringChar to store any data?
bool IsEmpty() const {
return bitlength_ == 0;
}
explicit operator StorageType() const {
return data_;
}
bool operator==(StorageType storage) const {
return data_ == storage;
}
bool operator!=(StorageType storage) const {
return !(*this == storage);
}
// Compare equality against another BitStringChar. Note: bitlength is ignored.
bool operator==(const BitStringChar& other) const {
return data_ == other.data_;
}
// Compare non-equality against another BitStringChar. Note: bitlength is ignored.
bool operator!=(const BitStringChar& other) const {
return !(*this == other);
}
// Add a BitStringChar with an integer. The resulting BitStringChar's data must still fit within
// this BitStringChar's bit length.
BitStringChar operator+(StorageType storage) const {
DCHECK_LE(storage, MaximumValue().data_ - data_) << "Addition would overflow " << *this;
return BitStringChar(data_ + storage, bitlength_);
}
// Get the maximum representible value with the same bitlength.
// (Useful to figure out the maximum value for this BitString position.)
BitStringChar MaximumValue() const {
StorageType maximimum_data = MaxInt<StorageType>(bitlength_);
return BitStringChar(maximimum_data, bitlength_);
}
private:
StorageType data_; // Unused bits (outside of bitlength) are 0.
size_t bitlength_;
// Logically const. Physically non-const so operator= still works.
};
// Print e.g. "BitStringChar<10>(123)" where 10=bitlength, 123=data.
inline std::ostream& operator<<(std::ostream& os, const BitStringChar& bc) {
os << "BitStringChar<" << bc.GetBitLength() << ">("
<< static_cast<BitStringChar::StorageType>(bc) << ")";
return os;
}
/**
* BitString
*
* MSB (most significant bit) LSB
* +------------+-----+------------+------------+------------+
* | | | | | |
* | CharN | ... | Char2 | Char1 | Char0 |
* | | | | | |
* +------------+-----+------------+------------+------------+
* <- len[N] -> ... <- len[2] -> <- len[1] -> <- len[0] ->
*
* Stores up to "N+1" characters in a subset of a machine word. Each character has a different
* bitlength, as defined by len[pos]. This BitString can be nested inside of a BitStruct
* (see e.g. SubtypeCheckBitsAndStatus).
*
* Definitions:
*
* "ABCDE...K" := [A,B,C,D,E, ... K] + [0]*(N-idx(K)) s.t. N >= K.
* // Padded with trailing 0s to fit (N+1) bitstring chars.
* MaxBitstringLen := N+1
* StrLen(Bitstring) := I s.t. (I == 0 OR Char(I-1) != 0)
* AND forall char in CharI..CharN : char == 0
* // = Maximum length - the # of consecutive trailing zeroes.
* Bitstring[N] := CharN
* Bitstring[I..N) := [CharI, CharI+1, ... CharN-1]
*
* (These are used by the SubtypeCheckInfo definitions and invariants, see subtype_check_info.h)
*/
struct BitString {
using StorageType = BitStringChar::StorageType;
// As this is meant to be used only with "SubtypeCheckInfo",
// the bitlengths and the maximum string length is tuned by maximizing the coverage of "Assigned"
// bitstrings for instance-of and check-cast targets during Optimizing compilation.
static constexpr size_t kBitSizeAtPosition[] = {12, 4, 11}; // len[] from header docs.
static constexpr size_t kCapacity = arraysize(kBitSizeAtPosition); // MaxBitstringLen above.
// How many bits are needed to represent BitString[0..position)?
static constexpr size_t GetBitLengthTotalAtPosition(size_t position) {
size_t idx = 0;
size_t sum = 0;
while (idx < position && idx < kCapacity) {
sum += kBitSizeAtPosition[idx];
++idx;
}
// TODO: precompute with CreateArray helper.
return sum;
}
// What is the least-significant-bit for a position?
// (e.g. to use with BitField{Insert,Extract,Clear}.)
static constexpr size_t GetLsbForPosition(size_t position) {
DCHECK_GE(kCapacity, position);
return GetBitLengthTotalAtPosition(position);
}
// How many bits are needed for a BitStringChar at the position?
// Returns 0 if the position is out of range.
static constexpr size_t MaybeGetBitLengthAtPosition(size_t position) {
if (position >= kCapacity) {
return 0;
}
return kBitSizeAtPosition[position];
}
// Read a bitchar at some index within the capacity.
// See also "BitString[N]" in the doc header.
BitStringChar operator[](size_t idx) const {
DCHECK_LT(idx, kCapacity);
StorageType data = BitFieldExtract(storage_, GetLsbForPosition(idx), kBitSizeAtPosition[idx]);
return BitStringChar(data, kBitSizeAtPosition[idx]);
}
// Overwrite a bitchar at a position with a new one.
//
// The `bitchar` bitlength must be no more than the maximum bitlength for that position.
void SetAt(size_t idx, BitStringChar bitchar) {
DCHECK_LT(idx, kCapacity);
DCHECK_LE(bitchar.GetBitLength(), kBitSizeAtPosition[idx]);
// Read the bitchar: Bits > bitlength in bitchar are defined to be 0.
storage_ = BitFieldInsert(storage_,
static_cast<StorageType>(bitchar),
GetLsbForPosition(idx),
kBitSizeAtPosition[idx]);
}
// How many characters are there in this bitstring?
// Trailing 0s are ignored, but 0s in-between are counted.
// See also "StrLen(BitString)" in the doc header.
size_t Length() const {
size_t num_trailing_zeros = 0;
size_t i;
for (i = kCapacity - 1u; ; --i) {
BitStringChar bc = (*this)[i];
if (bc != 0u) {
break; // Found first trailing non-zero.
}
++num_trailing_zeros;
if (i == 0u) {
break; // No more bitchars remaining: don't underflow.
}
}
return kCapacity - num_trailing_zeros;
}
// Cast to the underlying integral storage type.
explicit operator StorageType() const {
return storage_;
}
// Get the # of bits this would use if it was nested inside of a BitStruct.
static constexpr size_t BitStructSizeOf() {
return GetBitLengthTotalAtPosition(kCapacity);
}
BitString() = default;
// Efficient O(1) comparison: Equal if both bitstring words are the same.
bool operator==(const BitString& other) const {
return storage_ == other.storage_;
}
// Efficient O(1) negative comparison: Not-equal if both bitstring words are different.
bool operator!=(const BitString& other) const {
return !(*this == other);
}
// Does this bitstring contain exactly 0 characters?
bool IsEmpty() const {
return (*this) == BitString{};
}
// Remove all BitStringChars starting at end.
// Returns the BitString[0..end) substring as a copy.
// See also "BitString[I..N)" in the doc header.
BitString Truncate(size_t end) {
DCHECK_GE(kCapacity, end);
BitString copy = *this;
if (end < kCapacity) {
size_t lsb = GetLsbForPosition(end);
size_t bit_size = GetLsbForPosition(kCapacity) - lsb;
StorageType data = BitFieldClear(copy.storage_, lsb, bit_size);
copy.storage_ = data;
}
return copy;
}
private:
friend std::ostream& operator<<(std::ostream& os, const BitString& bit_string);
// Data is stored with the first character in the least-significant-bit.
// Unused bits are zero.
StorageType storage_;
};
static_assert(BitSizeOf<BitString::StorageType>() >=
BitString::GetBitLengthTotalAtPosition(BitString::kCapacity),
"Storage type is too small for the # of bits requested");
// Print e.g. "BitString[1,0,3]". Trailing 0s are dropped.
inline std::ostream& operator<<(std::ostream& os, const BitString& bit_string) {
const size_t length = bit_string.Length();
os << "BitString[";
for (size_t i = 0; i < length; ++i) {
BitStringChar bc = bit_string[i];
if (i != 0) {
os << ",";
}
os << static_cast<BitString::StorageType>(bc);
}
os << "]";
return os;
}
} // namespace art
#endif // ART_LIBARTBASE_BASE_BIT_STRING_H_