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 #include "base/bit_string.h" 18 19 #include "gtest/gtest.h" 20 #include "android-base/logging.h" 21 22 namespace art { 23 24 constexpr size_t BitString::kBitSizeAtPosition[BitString::kCapacity]; 25 constexpr size_t BitString::kCapacity; 26 27 }; // namespace art 28 29 using namespace art; // NOLINT [build/namespaces] [5] 30 31 // These helper functions are only used by the test, 32 // so they are not in the main BitString class. 33 std::string Stringify(BitString bit_string) { 34 std::stringstream ss; 35 ss << bit_string; 36 return ss.str(); 37 } 38 39 BitStringChar MakeBitStringChar(size_t idx, size_t val) { 40 return BitStringChar(val, BitString::MaybeGetBitLengthAtPosition(idx)); 41 } 42 43 BitStringChar MakeBitStringChar(size_t val) { 44 return BitStringChar(val, MinimumBitsToStore(val)); 45 } 46 47 BitString MakeBitString(std::initializer_list<size_t> values = {}) { 48 CHECK_GE(BitString::kCapacity, values.size()); 49 50 BitString bs{}; 51 52 size_t i = 0; 53 for (size_t val : values) { 54 bs.SetAt(i, MakeBitStringChar(i, val)); 55 ++i; 56 } 57 58 return bs; 59 } 60 61 template <typename T> 62 size_t AsUint(const T& value) { 63 size_t uint_value = 0; 64 memcpy(&uint_value, &value, sizeof(value)); 65 return uint_value; 66 } 67 68 // Make max bitstring, e.g. BitString[4095,15,2047] for {12,4,11} 69 template <size_t kCount = BitString::kCapacity> 70 BitString MakeBitStringMax() { 71 BitString bs{}; 72 73 for (size_t i = 0; i < kCount; ++i) { 74 bs.SetAt(i, 75 MakeBitStringChar(i, MaxInt<BitStringChar::StorageType>(BitString::kBitSizeAtPosition[i]))); 76 } 77 78 return bs; 79 } 80 81 BitString SetBitStringCharAt(BitString bit_string, size_t i, size_t val) { 82 BitString bs = bit_string; 83 bs.SetAt(i, MakeBitStringChar(i, val)); 84 return bs; 85 } 86 87 #define EXPECT_BITSTRING_STR(expected_str, actual_value) \ 88 EXPECT_STREQ((expected_str), Stringify((actual_value)).c_str()) 89 90 // TODO: Consider removing this test, it's kind of replicating the logic in GetLsbForPosition(). 91 TEST(InstanceOfBitString, GetLsbForPosition) { 92 ASSERT_LE(3u, BitString::kCapacity); 93 // Test will fail if kCapacity is not at least 3. Update it. 94 EXPECT_EQ(0u, BitString::GetLsbForPosition(0u)); 95 EXPECT_EQ(BitString::kBitSizeAtPosition[0u], BitString::GetLsbForPosition(1u)); 96 EXPECT_EQ(BitString::kBitSizeAtPosition[0u] + BitString::kBitSizeAtPosition[1u], 97 BitString::GetLsbForPosition(2u)); 98 } 99 100 TEST(InstanceOfBitString, ToString) { 101 EXPECT_BITSTRING_STR("BitString[]", MakeBitString({0})); 102 EXPECT_BITSTRING_STR("BitString[1]", MakeBitString({1})); 103 EXPECT_BITSTRING_STR("BitString[1,2,3]", MakeBitString({1, 2, 3})); 104 } 105 106 TEST(InstanceOfBitString, ReadWrite) { 107 BitString bs = MakeBitString(); 108 109 // Update tests if changing the capacity. 110 ASSERT_EQ(BitString::kCapacity, 3u); 111 112 EXPECT_BITSTRING_STR("BitString[]", bs); 113 bs = SetBitStringCharAt(bs, /*i*/0, /*val*/1u); 114 EXPECT_BITSTRING_STR("BitString[1]", bs); 115 bs = SetBitStringCharAt(bs, /*i*/1, /*val*/2u); 116 EXPECT_BITSTRING_STR("BitString[1,2]", bs); 117 bs = SetBitStringCharAt(bs, /*i*/2, /*val*/3u); 118 EXPECT_BITSTRING_STR("BitString[1,2,3]", bs); 119 120 // There should be at least "kCapacity" # of checks here, 1 for each unique position. 121 EXPECT_EQ(MakeBitStringChar(/*idx*/0, /*val*/1u), bs[0]); 122 EXPECT_EQ(MakeBitStringChar(/*idx*/1, /*val*/2u), bs[1]); 123 EXPECT_EQ(MakeBitStringChar(/*idx*/2, /*val*/3u), bs[2]); 124 125 // Each maximal value should be tested here for each position. 126 uint32_t max_bitstring_ints[] = { 127 MaxInt<uint32_t>(12), 128 MaxInt<uint32_t>(4), 129 MaxInt<uint32_t>(11), 130 }; 131 132 // Update tests if changing the tuning values above. 133 for (size_t i = 0; i < arraysize(max_bitstring_ints); ++i) { 134 ASSERT_EQ(MinimumBitsToStore(max_bitstring_ints[i]), BitString::kBitSizeAtPosition[i]) << i; 135 } 136 137 BitString bs_max = MakeBitStringMax(); 138 139 for (size_t i = 0; i < arraysize(max_bitstring_ints); ++i) { 140 ASSERT_EQ(max_bitstring_ints[i], static_cast<uint32_t>(bs_max[i])) << i; 141 } 142 143 EXPECT_EQ(MaskLeastSignificant(BitString::GetBitLengthTotalAtPosition(BitString::kCapacity)), 144 AsUint(MakeBitStringMax())); 145 } 146 147 template <size_t kPos> 148 constexpr auto MaxForPos() { 149 return MaxInt<BitString::StorageType>(BitString::kBitSizeAtPosition[kPos]); 150 } 151 152 TEST(InstanceOfBitString, MemoryRepresentation) { 153 // Verify that the lower positions are stored in less significant bits. 154 BitString bs = MakeBitString({MaxForPos<0>(), MaxForPos<1>()}); 155 BitString::StorageType as_int = static_cast<BitString::StorageType>(bs); 156 157 // Below tests assumes the capacity is at least 3. 158 ASSERT_LE(3u, BitString::kCapacity); 159 EXPECT_EQ((MaxForPos<0>() << 0) | (MaxForPos<1>() << BitString::kBitSizeAtPosition[0]), 160 as_int); 161 } 162 163 TEST(InstanceOfBitString, Truncate) { 164 EXPECT_BITSTRING_STR("BitString[]", MakeBitString({1, 2, 3}).Truncate(0)); 165 EXPECT_BITSTRING_STR("BitString[1]", MakeBitString({1, 2, 3}).Truncate(1)); 166 EXPECT_BITSTRING_STR("BitString[1,2]", MakeBitString({1, 2, 3}).Truncate(2)); 167 EXPECT_BITSTRING_STR("BitString[1,2,3]", MakeBitString({1, 2, 3}).Truncate(3)); 168 } 169
