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 "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.
Stringify(BitString bit_string)33 std::string Stringify(BitString bit_string) {
34 std::stringstream ss;
35 ss << bit_string;
36 return ss.str();
37 }
38
MakeBitStringChar(size_t idx,size_t val)39 BitStringChar MakeBitStringChar(size_t idx, size_t val) {
40 return BitStringChar(val, BitString::MaybeGetBitLengthAtPosition(idx));
41 }
42
MakeBitStringChar(size_t val)43 BitStringChar MakeBitStringChar(size_t val) {
44 return BitStringChar(val, MinimumBitsToStore(val));
45 }
46
MakeBitString(std::initializer_list<size_t> values={})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>
AsUint(const T & value)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>
MakeBitStringMax()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
SetBitStringCharAt(BitString bit_string,size_t i,size_t val)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().
TEST(InstanceOfBitString,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
TEST(InstanceOfBitString,ToString)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
TEST(InstanceOfBitString,ReadWrite)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>
MaxForPos()148 constexpr auto MaxForPos() {
149 return MaxInt<BitString::StorageType>(BitString::kBitSizeAtPosition[kPos]);
150 }
151
TEST(InstanceOfBitString,MemoryRepresentation)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
TEST(InstanceOfBitString,Truncate)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