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 #ifndef ART_LIBARTBASE_BASE_BIT_STRING_H_
18 #define ART_LIBARTBASE_BASE_BIT_STRING_H_
19 
20 #include "base/bit_struct.h"
21 #include "base/bit_utils.h"
22 
23 #include <ostream>
24 
25 namespace art {
26 
27 struct BitStringChar;
28 inline std::ostream& operator<<(std::ostream& os, const BitStringChar& bc);
29 
30 /**
31  * A BitStringChar is a light-weight wrapper to read/write a single character
32  * into a BitString, while restricting the bitlength.
33  *
34  * This is only intended for reading/writing into temporaries, as the representation is
35  * inefficient for memory (it uses a word for the character and another word for the bitlength).
36  *
37  * See also BitString below.
38  */
39 struct BitStringChar {
40   using StorageType = uint32_t;
41   static_assert(std::is_unsigned<StorageType>::value, "BitStringChar::StorageType must be unsigned");
42 
43   // BitStringChars are always zero-initialized by default. Equivalent to BitStringChar(0,0).
BitStringCharBitStringChar44   BitStringChar() : data_(0u), bitlength_(0u) { }
45 
46   // Create a new BitStringChar whose data bits can be at most bitlength.
BitStringCharBitStringChar47   BitStringChar(StorageType data, size_t bitlength)
48       : data_(data), bitlength_(bitlength) {
49     // All bits higher than bitlength must be set to 0.
50     DCHECK_EQ(0u, data & ~MaskLeastSignificant(bitlength_))
51         << "BitStringChar data out of range, data: " << data << ", bitlength: " << bitlength;
52   }
53 
54   // What is the bitlength constraint for this character?
55   // (Data could use less bits, but this is the maximum bit capacity at that BitString position).
GetBitLengthBitStringChar56   size_t GetBitLength() const {
57     return bitlength_;
58   }
59 
60   // Is there any capacity in this BitStringChar to store any data?
IsEmptyBitStringChar61   bool IsEmpty() const {
62     return bitlength_ == 0;
63   }
64 
StorageTypeBitStringChar65   explicit operator StorageType() const {
66     return data_;
67   }
68 
69   bool operator==(StorageType storage) const {
70     return data_ == storage;
71   }
72 
73   bool operator!=(StorageType storage) const {
74     return !(*this == storage);
75   }
76 
77   // Compare equality against another BitStringChar. Note: bitlength is ignored.
78   bool operator==(const BitStringChar& other) const {
79     return data_ == other.data_;
80   }
81 
82   // Compare non-equality against another BitStringChar. Note: bitlength is ignored.
83   bool operator!=(const BitStringChar& other) const {
84     return !(*this == other);
85   }
86 
87   // Add a BitStringChar with an integer. The resulting BitStringChar's data must still fit within
88   // this BitStringChar's bit length.
89   BitStringChar operator+(StorageType storage) const {
90     DCHECK_LE(storage, MaximumValue().data_ - data_) << "Addition would overflow " << *this;
91     return BitStringChar(data_ + storage, bitlength_);
92   }
93 
94   // Get the maximum representible value with the same bitlength.
95   // (Useful to figure out the maximum value for this BitString position.)
MaximumValueBitStringChar96   BitStringChar MaximumValue() const {
97     StorageType maximimum_data = MaxInt<StorageType>(bitlength_);
98     return BitStringChar(maximimum_data, bitlength_);
99   }
100 
101  private:
102   StorageType data_;  // Unused bits (outside of bitlength) are 0.
103   size_t bitlength_;
104   // Logically const. Physically non-const so operator= still works.
105 };
106 
107 // Print e.g. "BitStringChar<10>(123)" where 10=bitlength, 123=data.
108 inline std::ostream& operator<<(std::ostream& os, const BitStringChar& bc) {
109   os << "BitStringChar<" << bc.GetBitLength() << ">("
110      << static_cast<BitStringChar::StorageType>(bc) << ")";
111   return os;
112 }
113 
114 /**
115  *                           BitString
116  *
117  * MSB (most significant bit)                                LSB
118  *  +------------+-----+------------+------------+------------+
119  *  |            |     |            |            |            |
120  *  |   CharN    | ... |    Char2   |   Char1    |   Char0    |
121  *  |            |     |            |            |            |
122  *  +------------+-----+------------+------------+------------+
123  *   <- len[N] ->  ...  <- len[2] -> <- len[1] -> <- len[0] ->
124  *
125  * Stores up to "N+1" characters in a subset of a machine word. Each character has a different
126  * bitlength, as defined by len[pos]. This BitString can be nested inside of a BitStruct
127  * (see e.g. SubtypeCheckBitsAndStatus).
128  *
129  * Definitions:
130  *
131  *  "ABCDE...K"       := [A,B,C,D,E, ... K] + [0]*(N-idx(K)) s.t. N >= K.
132  *                    // Padded with trailing 0s to fit (N+1) bitstring chars.
133  *  MaxBitstringLen   := N+1
134  *  StrLen(Bitstring) := I s.t. (I == 0 OR Char(I-1) != 0)
135  *                              AND forall char in CharI..CharN : char == 0
136  *                    // = Maximum length - the # of consecutive trailing zeroes.
137  *  Bitstring[N]      := CharN
138  *  Bitstring[I..N)   := [CharI, CharI+1, ... CharN-1]
139  *
140  * (These are used by the SubtypeCheckInfo definitions and invariants, see subtype_check_info.h)
141  */
142 struct BitString {
143   using StorageType = BitStringChar::StorageType;
144 
145   // As this is meant to be used only with "SubtypeCheckInfo",
146   // the bitlengths and the maximum string length is tuned by maximizing the coverage of "Assigned"
147   // bitstrings for instance-of and check-cast targets during Optimizing compilation.
148   static constexpr size_t kBitSizeAtPosition[] = {12, 4, 11};         // len[] from header docs.
149   static constexpr size_t kCapacity = arraysize(kBitSizeAtPosition);  // MaxBitstringLen above.
150 
151   // How many bits are needed to represent BitString[0..position)?
GetBitLengthTotalAtPositionBitString152   static constexpr size_t GetBitLengthTotalAtPosition(size_t position) {
153     size_t idx = 0;
154     size_t sum = 0;
155     while (idx < position && idx < kCapacity) {
156       sum += kBitSizeAtPosition[idx];
157       ++idx;
158     }
159     // TODO: precompute with CreateArray helper.
160 
161     return sum;
162   }
163 
164   // What is the least-significant-bit for a position?
165   // (e.g. to use with BitField{Insert,Extract,Clear}.)
GetLsbForPositionBitString166   static constexpr size_t GetLsbForPosition(size_t position) {
167     DCHECK_GE(kCapacity, position);
168     return GetBitLengthTotalAtPosition(position);
169   }
170 
171   // How many bits are needed for a BitStringChar at the position?
172   // Returns 0 if the position is out of range.
MaybeGetBitLengthAtPositionBitString173   static constexpr size_t MaybeGetBitLengthAtPosition(size_t position) {
174     if (position >= kCapacity) {
175       return 0;
176     }
177     return kBitSizeAtPosition[position];
178   }
179 
180   // Read a bitchar at some index within the capacity.
181   // See also "BitString[N]" in the doc header.
182   BitStringChar operator[](size_t idx) const {
183     DCHECK_LT(idx, kCapacity);
184 
185     StorageType data = BitFieldExtract(storage_, GetLsbForPosition(idx), kBitSizeAtPosition[idx]);
186 
187     return BitStringChar(data, kBitSizeAtPosition[idx]);
188   }
189 
190   // Overwrite a bitchar at a position with a new one.
191   //
192   // The `bitchar` bitlength must be no more than the maximum bitlength for that position.
SetAtBitString193   void SetAt(size_t idx, BitStringChar bitchar) {
194     DCHECK_LT(idx, kCapacity);
195     DCHECK_LE(bitchar.GetBitLength(), kBitSizeAtPosition[idx]);
196 
197     // Read the bitchar: Bits > bitlength in bitchar are defined to be 0.
198     storage_ = BitFieldInsert(storage_,
199                               static_cast<StorageType>(bitchar),
200                               GetLsbForPosition(idx),
201                               kBitSizeAtPosition[idx]);
202   }
203 
204   // How many characters are there in this bitstring?
205   // Trailing 0s are ignored, but 0s in-between are counted.
206   // See also "StrLen(BitString)" in the doc header.
LengthBitString207   size_t Length() const {
208     size_t num_trailing_zeros = 0;
209     size_t i;
210     for (i = kCapacity - 1u; ; --i) {
211       BitStringChar bc = (*this)[i];
212       if (bc != 0u) {
213         break;  // Found first trailing non-zero.
214       }
215 
216       ++num_trailing_zeros;
217       if (i == 0u) {
218         break;  // No more bitchars remaining: don't underflow.
219       }
220     }
221 
222     return kCapacity - num_trailing_zeros;
223   }
224 
225   // Cast to the underlying integral storage type.
StorageTypeBitString226   explicit operator StorageType() const {
227     return storage_;
228   }
229 
230   // Get the # of bits this would use if it was nested inside of a BitStruct.
BitStructSizeOfBitString231   static constexpr size_t BitStructSizeOf() {
232     return GetBitLengthTotalAtPosition(kCapacity);
233   }
234 
235   BitString() = default;
236 
237   // Efficient O(1) comparison: Equal if both bitstring words are the same.
238   bool operator==(const BitString& other) const {
239     return storage_ == other.storage_;
240   }
241 
242   // Efficient O(1) negative comparison: Not-equal if both bitstring words are different.
243   bool operator!=(const BitString& other) const {
244     return !(*this == other);
245   }
246 
247   // Does this bitstring contain exactly 0 characters?
IsEmptyBitString248   bool IsEmpty() const {
249     return (*this) == BitString{};
250   }
251 
252   // Remove all BitStringChars starting at end.
253   // Returns the BitString[0..end) substring as a copy.
254   // See also "BitString[I..N)" in the doc header.
TruncateBitString255   BitString Truncate(size_t end) {
256     DCHECK_GE(kCapacity, end);
257     BitString copy = *this;
258 
259     if (end < kCapacity) {
260       size_t lsb = GetLsbForPosition(end);
261       size_t bit_size = GetLsbForPosition(kCapacity) - lsb;
262       StorageType data = BitFieldClear(copy.storage_, lsb, bit_size);
263       copy.storage_ = data;
264     }
265 
266     return copy;
267   }
268 
269  private:
270   friend std::ostream& operator<<(std::ostream& os, const BitString& bit_string);
271 
272   // Data is stored with the first character in the least-significant-bit.
273   // Unused bits are zero.
274   StorageType storage_;
275 };
276 
277 static_assert(BitSizeOf<BitString::StorageType>() >=
278                   BitString::GetBitLengthTotalAtPosition(BitString::kCapacity),
279               "Storage type is too small for the # of bits requested");
280 
281 // Print e.g. "BitString[1,0,3]". Trailing 0s are dropped.
282 inline std::ostream& operator<<(std::ostream& os, const BitString& bit_string) {
283   const size_t length = bit_string.Length();
284 
285   os << "BitString[";
286   for (size_t i = 0; i < length; ++i) {
287     BitStringChar bc = bit_string[i];
288     if (i != 0) {
289       os << ",";
290     }
291     os << static_cast<BitString::StorageType>(bc);
292   }
293   os << "]";
294   return os;
295 }
296 
297 }  // namespace art
298 
299 #endif  // ART_LIBARTBASE_BASE_BIT_STRING_H_
300