runtime: Bitstring implementation for subtype checking (1/4).

Implement a BitString abstraction for storing nbit-sized characters in a
single machine word (uint32).

This is used to enable an O(1) subtype check in subsequent CLs.

Test: art/test.py -b -j32 --host --target
Bug: 64692057
Change-Id: I792405e0c34242cc1206cedeb18e3e6fb687d94b

3 files changed, 474 insertions, 0 deletions

diff --git a/runtime/Android.bp b/runtime/Android.bp
index cfdac1c1b3..30595335f0 100644
--- a/runtime/Android.bp
+++ b/runtime/Android.bp
@@ -534,6 +534,7 @@ art_cc_test {
         "barrier_test.cc",
         "base/arena_allocator_test.cc",
         "base/bit_field_test.cc",
+        "base/bit_string_test.cc",
         "base/bit_struct_test.cc",
         "base/bit_utils_test.cc",
         "base/bit_vector_test.cc",
diff --git a/runtime/base/bit_string.h b/runtime/base/bit_string.h
new file mode 100644
index 0000000000..d4197e363a
--- /dev/null
+++ b/runtime/base/bit_string.h
@@ -0,0 +1,303 @@
+/*
+ * 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_RUNTIME_BASE_BIT_STRING_H_
+#define ART_RUNTIME_BASE_BIT_STRING_H_
+
+#include "base/bit_struct.h"
+#include "base/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                                                      LSB
+ *  +------------+------------+------------+-----+------------+
+ *  |            |            |            |     |            |
+ *  |   Char0    |    Char1   |   Char2    | ... |   CharN    |
+ *  |            |            |            |     |            |
+ *  +------------+------------+------------+-----+------------+
+ *   <- len[0] -> <- len[1] -> <- len[2] ->  ...  <- len[N] ->
+ *
+ * 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) := MaxBitStringLen - | forall char in CharI..CharN : char == 0 AND Char(I-1) != 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, 3, 8};          // 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);
+    constexpr size_t kMaximumBitLength = GetBitLengthTotalAtPosition(kCapacity);
+    return kMaximumBitLength - GetBitLengthTotalAtPosition(position + 1u);
+  }
+
+  // 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);
+  }
+
+  // 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;
+
+    size_t bit_size = 0;
+    for (size_t idx = end; idx < kCapacity; ++idx) {
+      bit_size += kBitSizeAtPosition[idx];
+    }
+    // TODO: precompute above table.
+
+    if (bit_size > 0) {
+      StorageType data =
+          BitFieldClear(copy.storage_,
+                        GetLsbForPosition(kCapacity),
+                        bit_size);
+      copy.storage_ = data;
+    }
+
+    return copy;
+  }
+
+ private:
+  friend std::ostream& operator<<(std::ostream& os, const BitString& bit_string);
+
+  // Data is stored with the "highest" position in the least-significant-bit.
+  // As positions approach 0, the bits are stored with increasing significance.
+  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_RUNTIME_BASE_BIT_STRING_H_
diff --git a/runtime/base/bit_string_test.cc b/runtime/base/bit_string_test.cc
new file mode 100644
index 0000000000..d5610e7a73
--- /dev/null
+++ b/runtime/base/bit_string_test.cc
@@ -0,0 +1,170 @@
+/*
+ * 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.
+ */
+
+#include "base/bit_string.h"
+
+#include "gtest/gtest.h"
+#include "android-base/logging.h"
+
+namespace art {
+
+constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity];
+constexpr size_t BitString::kCapacity;
+
+};  // namespace art
+
+using namespace art;  // NOLINT [build/namespaces] [5]
+
+// These helper functions are only used by the test,
+// so they are not in the main BitString class.
+std::string Stringify(BitString bit_string) {
+  std::stringstream ss;
+  ss << bit_string;
+  return ss.str();
+}
+
+BitStringChar MakeBitStringChar(size_t idx, size_t val) {
+  return BitStringChar(val, BitString::MaybeGetBitLengthAtPosition(idx));
+}
+
+BitStringChar MakeBitStringChar(size_t val) {
+  return BitStringChar(val, MinimumBitsToStore(val));
+}
+
+BitString MakeBitString(std::initializer_list<size_t> values = {}) {
+  CHECK_GE(BitString::kCapacity, values.size());
+
+  BitString bs{};  // NOLINT
+
+  size_t i = 0;
+  for (size_t val : values) {
+    bs.SetAt(i, MakeBitStringChar(i, val));
+    ++i;
+  }
+
+  return bs;
+}
+
+template <typename T>
+size_t AsUint(const T& value) {
+  size_t uint_value = 0;
+  memcpy(&uint_value, &value, sizeof(value));
+  return uint_value;
+}
+
+// Make max bitstring, e.g. BitString[4095,7,255] for {12,3,8}
+template <size_t kCount = BitString::kCapacity>
+BitString MakeBitStringMax() {
+  BitString bs{};  // NOLINT
+
+  for (size_t i = 0; i < kCount; ++i) {
+    bs.SetAt(i,
+             MakeBitStringChar(i, MaxInt<BitStringChar::StorageType>(BitString::kBitSizeAtPosition[i])));
+  }
+
+  return bs;
+}
+
+BitString SetBitStringCharAt(BitString bit_string, size_t i, size_t val) {
+  BitString bs = bit_string;
+  bs.SetAt(i, MakeBitStringChar(i, val));
+  return bs;
+}
+
+#define EXPECT_BITSTRING_STR(expected_str, actual_value)                       \
+  EXPECT_STREQ((expected_str), Stringify((actual_value)).c_str())
+
+TEST(InstanceOfBitString, GetLsbForPosition) {
+  ASSERT_LE(3u, BitString::kCapacity);
+  // Test will fail if kCapacity is not at least 3. Update it.
+  EXPECT_EQ(0u, BitString::GetLsbForPosition(BitString::kCapacity - 1u));
+  EXPECT_EQ(BitString::kBitSizeAtPosition[BitString::kCapacity - 1u],
+            BitString::GetLsbForPosition(BitString::kCapacity - 2u));
+  EXPECT_EQ(BitString::kBitSizeAtPosition[BitString::kCapacity - 1u] +
+                BitString::kBitSizeAtPosition[BitString::kCapacity - 2u],
+            BitString::GetLsbForPosition(BitString::kCapacity - 3u));
+}
+
+TEST(InstanceOfBitString, ToString) {
+  EXPECT_BITSTRING_STR("BitString[]", MakeBitString({0}));
+  EXPECT_BITSTRING_STR("BitString[1]", MakeBitString({1}));
+  EXPECT_BITSTRING_STR("BitString[1,2,3]", MakeBitString({1, 2, 3}));
+}
+
+TEST(InstanceOfBitString, ReadWrite) {
+  BitString bs = MakeBitString();
+
+  // Update tests if changing the capacity.
+  ASSERT_EQ(BitString::kCapacity, 3u);
+
+  EXPECT_BITSTRING_STR("BitString[]", bs);
+  bs = SetBitStringCharAt(bs, /*i*/0, /*val*/1u);
+  EXPECT_BITSTRING_STR("BitString[1]", bs);
+  bs = SetBitStringCharAt(bs, /*i*/1, /*val*/2u);
+  EXPECT_BITSTRING_STR("BitString[1,2]", bs);
+  bs = SetBitStringCharAt(bs, /*i*/2, /*val*/3u);
+  EXPECT_BITSTRING_STR("BitString[1,2,3]", bs);
+
+  // There should be at least "kCapacity" # of checks here, 1 for each unique position.
+  EXPECT_EQ(MakeBitStringChar(/*idx*/0, /*val*/1u), bs[0]);
+  EXPECT_EQ(MakeBitStringChar(/*idx*/1, /*val*/2u), bs[1]);
+  EXPECT_EQ(MakeBitStringChar(/*idx*/2, /*val*/3u), bs[2]);
+
+  // Each maximal value should be tested here for each position.
+  uint32_t max_bitstring_ints[] = {
+      MaxInt<uint32_t>(12),
+      MaxInt<uint32_t>(3),
+      MaxInt<uint32_t>(8),
+  };
+
+  // Update tests if changing the tuning values above.
+  for (size_t i = 0; i < arraysize(max_bitstring_ints); ++i) {
+    ASSERT_EQ(MinimumBitsToStore(max_bitstring_ints[i]), BitString::kBitSizeAtPosition[i]) << i;
+  }
+
+  BitString bs_max = MakeBitStringMax();
+
+  for (size_t i = 0; i < arraysize(max_bitstring_ints); ++i) {
+    ASSERT_EQ(max_bitstring_ints[i], static_cast<uint32_t>(bs_max[i])) << i;
+  }
+
+  EXPECT_EQ(MaskLeastSignificant(BitString::GetBitLengthTotalAtPosition(BitString::kCapacity)),
+            AsUint(MakeBitStringMax()));
+}
+
+template <size_t kPos>
+constexpr auto MaxForPos() {
+    return MaxInt<BitString::StorageType>(BitString::kBitSizeAtPosition[kPos]);
+}
+
+TEST(InstanceOfBitString, MemoryRepresentation) {
+  // Verify that the lower positions are stored in more significant bits.
+  BitString bs = MakeBitString({MaxForPos<0>(), MaxForPos<1>()});
+  BitString::StorageType as_int = static_cast<BitString::StorageType>(bs);
+
+  // Below tests assumes the capacity is 3. Update if it this changes.
+  ASSERT_EQ(3u, BitString::kCapacity);
+  EXPECT_EQ(MaxForPos<0>()  << (BitString::kBitSizeAtPosition[2] + BitString::kBitSizeAtPosition[1]) |
+               (MaxForPos<1>() << BitString::kBitSizeAtPosition[2]),
+            as_int);
+}
+
+TEST(InstanceOfBitString, Truncate) {
+  EXPECT_BITSTRING_STR("BitString[]", MakeBitString({1, 2, 3}).Truncate(0));
+  EXPECT_BITSTRING_STR("BitString[1]", MakeBitString({1, 2, 3}).Truncate(1));
+  EXPECT_BITSTRING_STR("BitString[1,2]", MakeBitString({1, 2, 3}).Truncate(2));
+  EXPECT_BITSTRING_STR("BitString[1,2,3]", MakeBitString({1, 2, 3}).Truncate(3));
+}