1 /*
2 * Copyright (C) 2019 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 "string_builder_append.h"
18
19 #include "base/casts.h"
20 #include "base/logging.h"
21 #include "common_throws.h"
22 #include "gc/heap.h"
23 #include "mirror/string-alloc-inl.h"
24 #include "obj_ptr-inl.h"
25 #include "runtime.h"
26
27 namespace art {
28
29 class StringBuilderAppend::Builder {
30 public:
Builder(uint32_t format,const uint32_t * args,Thread * self)31 Builder(uint32_t format, const uint32_t* args, Thread* self)
32 : format_(format),
33 args_(args),
34 hs_(self) {}
35
36 int32_t CalculateLengthWithFlag() REQUIRES_SHARED(Locks::mutator_lock_);
37
38 void operator()(ObjPtr<mirror::Object> obj, size_t usable_size) const
39 REQUIRES_SHARED(Locks::mutator_lock_);
40
41 private:
42 static size_t Uint64Length(uint64_t value);
43
Int64Length(int64_t value)44 static size_t Int64Length(int64_t value) {
45 uint64_t v = static_cast<uint64_t>(value);
46 return (value >= 0) ? Uint64Length(v) : 1u + Uint64Length(-v);
47 }
48
RemainingSpace(ObjPtr<mirror::String> new_string,const uint8_t * data)49 static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint8_t* data)
50 REQUIRES_SHARED(Locks::mutator_lock_) {
51 DCHECK(new_string->IsCompressed());
52 DCHECK_GE(new_string->GetLength(), data - new_string->GetValueCompressed());
53 return new_string->GetLength() - (data - new_string->GetValueCompressed());
54 }
55
RemainingSpace(ObjPtr<mirror::String> new_string,const uint16_t * data)56 static size_t RemainingSpace(ObjPtr<mirror::String> new_string, const uint16_t* data)
57 REQUIRES_SHARED(Locks::mutator_lock_) {
58 DCHECK(!new_string->IsCompressed());
59 DCHECK_GE(new_string->GetLength(), data - new_string->GetValue());
60 return new_string->GetLength() - (data - new_string->GetValue());
61 }
62
63 template <typename CharType, size_t size>
64 static CharType* AppendLiteral(ObjPtr<mirror::String> new_string,
65 CharType* data,
66 const char (&literal)[size]) REQUIRES_SHARED(Locks::mutator_lock_);
67
68 template <typename CharType>
69 static CharType* AppendString(ObjPtr<mirror::String> new_string,
70 CharType* data,
71 ObjPtr<mirror::String> str) REQUIRES_SHARED(Locks::mutator_lock_);
72
73 template <typename CharType>
74 static CharType* AppendInt64(ObjPtr<mirror::String> new_string,
75 CharType* data,
76 int64_t value) REQUIRES_SHARED(Locks::mutator_lock_);
77
78 template <typename CharType>
79 void StoreData(ObjPtr<mirror::String> new_string, CharType* data) const
80 REQUIRES_SHARED(Locks::mutator_lock_);
81
82 static constexpr char kNull[] = "null";
83 static constexpr size_t kNullLength = sizeof(kNull) - 1u;
84 static constexpr char kTrue[] = "true";
85 static constexpr size_t kTrueLength = sizeof(kTrue) - 1u;
86 static constexpr char kFalse[] = "false";
87 static constexpr size_t kFalseLength = sizeof(kFalse) - 1u;
88
89 // The format and arguments to append.
90 const uint32_t format_;
91 const uint32_t* const args_;
92
93 // References are moved to the handle scope during CalculateLengthWithFlag().
94 StackHandleScope<kMaxArgs> hs_;
95
96 // The length and flag to store when the AppendBuilder is used as a pre-fence visitor.
97 int32_t length_with_flag_ = 0u;
98 };
99
Uint64Length(uint64_t value)100 inline size_t StringBuilderAppend::Builder::Uint64Length(uint64_t value) {
101 if (value == 0u) {
102 return 1u;
103 }
104 // Calculate floor(log2(value)).
105 size_t log2_value = BitSizeOf<uint64_t>() - 1u - CLZ(value);
106 // Calculate an estimate of floor(log10(value)).
107 // log10(2) = 0.301029996 > 0.296875 = 19/64
108 // floor(log10(v)) == floor(log2(v) * log10(2))
109 // >= floor(log2(v) * 19/64)
110 // >= floor(floor(log2(v)) * 19/64)
111 // This estimate is no more that one off from the actual value because log2(value) < 64 and thus
112 // log2(v) * log10(2) - log2(v) * 19/64 < 64*(log10(2) - 19/64)
113 // for the first approximation and
114 // log2(v) * 19/64 - floor(log2(v)) * 19/64 < 19/64
115 // for the second one. Together,
116 // 64*(log10(2) - 19/64) + 19/64 = 0.56278 < 1 .
117 size_t log10_value_estimate = log2_value * 19u / 64u;
118 static constexpr uint64_t bounds[] = {
119 UINT64_C(9),
120 UINT64_C(99),
121 UINT64_C(999),
122 UINT64_C(9999),
123 UINT64_C(99999),
124 UINT64_C(999999),
125 UINT64_C(9999999),
126 UINT64_C(99999999),
127 UINT64_C(999999999),
128 UINT64_C(9999999999),
129 UINT64_C(99999999999),
130 UINT64_C(999999999999),
131 UINT64_C(9999999999999),
132 UINT64_C(99999999999999),
133 UINT64_C(999999999999999),
134 UINT64_C(9999999999999999),
135 UINT64_C(99999999999999999),
136 UINT64_C(999999999999999999),
137 UINT64_C(9999999999999999999),
138 };
139 // Add 1 for the lowest digit, add another 1 if the estimate was too low.
140 DCHECK_LT(log10_value_estimate, std::size(bounds));
141 size_t adjustment = (value > bounds[log10_value_estimate]) ? 2u : 1u;
142 return log10_value_estimate + adjustment;
143 }
144
145 template <typename CharType, size_t size>
AppendLiteral(ObjPtr<mirror::String> new_string,CharType * data,const char (& literal)[size])146 inline CharType* StringBuilderAppend::Builder::AppendLiteral(ObjPtr<mirror::String> new_string,
147 CharType* data,
148 const char (&literal)[size]) {
149 static_assert(size >= 2, "We need something to append.");
150
151 // Literals are zero-terminated.
152 constexpr size_t length = size - 1u;
153 DCHECK_EQ(literal[length], '\0');
154
155 DCHECK_LE(length, RemainingSpace(new_string, data));
156 for (size_t i = 0; i != length; ++i) {
157 data[i] = literal[i];
158 }
159 return data + length;
160 }
161
162 template <typename CharType>
AppendString(ObjPtr<mirror::String> new_string,CharType * data,ObjPtr<mirror::String> str)163 inline CharType* StringBuilderAppend::Builder::AppendString(ObjPtr<mirror::String> new_string,
164 CharType* data,
165 ObjPtr<mirror::String> str) {
166 size_t length = dchecked_integral_cast<size_t>(str->GetLength());
167 DCHECK_LE(length, RemainingSpace(new_string, data));
168 if (sizeof(CharType) == sizeof(uint8_t) || str->IsCompressed()) {
169 DCHECK(str->IsCompressed());
170 const uint8_t* value = str->GetValueCompressed();
171 for (size_t i = 0; i != length; ++i) {
172 data[i] = value[i];
173 }
174 } else {
175 const uint16_t* value = str->GetValue();
176 for (size_t i = 0; i != length; ++i) {
177 data[i] = dchecked_integral_cast<CharType>(value[i]);
178 }
179 }
180 return data + length;
181 }
182
183 template <typename CharType>
AppendInt64(ObjPtr<mirror::String> new_string,CharType * data,int64_t value)184 inline CharType* StringBuilderAppend::Builder::AppendInt64(ObjPtr<mirror::String> new_string,
185 CharType* data,
186 int64_t value) {
187 DCHECK_GE(RemainingSpace(new_string, data), Int64Length(value));
188 uint64_t v = static_cast<uint64_t>(value);
189 if (value < 0) {
190 *data = '-';
191 ++data;
192 v = -v;
193 }
194 size_t length = Uint64Length(v);
195 // Write the digits from the end, do not write the most significant digit
196 // in the loop to avoid an unnecessary division.
197 for (size_t i = 1; i != length; ++i) {
198 uint64_t digit = v % UINT64_C(10);
199 v /= UINT64_C(10);
200 data[length - i] = '0' + static_cast<char>(digit);
201 }
202 DCHECK_LE(v, 10u);
203 *data = '0' + static_cast<char>(v);
204 return data + length;
205 }
206
CalculateLengthWithFlag()207 inline int32_t StringBuilderAppend::Builder::CalculateLengthWithFlag() {
208 static_assert(static_cast<size_t>(Argument::kEnd) == 0u, "kEnd must be 0.");
209 bool compressible = mirror::kUseStringCompression;
210 uint64_t length = 0u;
211 const uint32_t* current_arg = args_;
212 for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) {
213 DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast));
214 switch (static_cast<Argument>(f & kArgMask)) {
215 case Argument::kString: {
216 Handle<mirror::String> str =
217 hs_.NewHandle(reinterpret_cast32<mirror::String*>(*current_arg));
218 if (str != nullptr) {
219 length += str->GetLength();
220 compressible = compressible && str->IsCompressed();
221 } else {
222 length += kNullLength;
223 }
224 break;
225 }
226 case Argument::kBoolean: {
227 length += (*current_arg != 0u) ? kTrueLength : kFalseLength;
228 break;
229 }
230 case Argument::kChar: {
231 length += 1u;
232 compressible = compressible &&
233 mirror::String::IsASCII(reinterpret_cast<const uint16_t*>(current_arg)[0]);
234 break;
235 }
236 case Argument::kInt: {
237 length += Int64Length(static_cast<int32_t>(*current_arg));
238 break;
239 }
240 case Argument::kLong: {
241 current_arg = AlignUp(current_arg, sizeof(int64_t));
242 length += Int64Length(*reinterpret_cast<const int64_t*>(current_arg));
243 ++current_arg; // Skip the low word, let the common code skip the high word.
244 break;
245 }
246
247 case Argument::kStringBuilder:
248 case Argument::kCharArray:
249 case Argument::kObject:
250 case Argument::kFloat:
251 case Argument::kDouble:
252 LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex
253 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
254 UNREACHABLE();
255 default:
256 LOG(FATAL) << "Unexpected arg format: 0x" << std::hex
257 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
258 UNREACHABLE();
259 }
260 ++current_arg;
261 DCHECK_LE(hs_.NumberOfReferences(), kMaxArgs);
262 }
263
264 if (length > std::numeric_limits<int32_t>::max()) {
265 // We cannot allocate memory for the entire result.
266 hs_.Self()->ThrowNewException("Ljava/lang/OutOfMemoryError;",
267 "Out of memory for StringBuilder append.");
268 return -1;
269 }
270
271 length_with_flag_ = mirror::String::GetFlaggedCount(length, compressible);
272 return length_with_flag_;
273 }
274
275 template <typename CharType>
StoreData(ObjPtr<mirror::String> new_string,CharType * data) const276 inline void StringBuilderAppend::Builder::StoreData(ObjPtr<mirror::String> new_string,
277 CharType* data) const {
278 size_t handle_index = 0u;
279 const uint32_t* current_arg = args_;
280 for (uint32_t f = format_; f != 0u; f >>= kBitsPerArg) {
281 DCHECK_LE(f & kArgMask, static_cast<uint32_t>(Argument::kLast));
282 switch (static_cast<Argument>(f & kArgMask)) {
283 case Argument::kString: {
284 ObjPtr<mirror::String> str =
285 ObjPtr<mirror::String>::DownCast(hs_.GetReference(handle_index));
286 ++handle_index;
287 if (str != nullptr) {
288 data = AppendString(new_string, data, str);
289 } else {
290 data = AppendLiteral(new_string, data, kNull);
291 }
292 break;
293 }
294 case Argument::kBoolean: {
295 if (*current_arg != 0u) {
296 data = AppendLiteral(new_string, data, kTrue);
297 } else {
298 data = AppendLiteral(new_string, data, kFalse);
299 }
300 break;
301 }
302 case Argument::kChar: {
303 DCHECK_GE(RemainingSpace(new_string, data), 1u);
304 *data = *reinterpret_cast<const CharType*>(current_arg);
305 ++data;
306 break;
307 }
308 case Argument::kInt: {
309 data = AppendInt64(new_string, data, static_cast<int32_t>(*current_arg));
310 break;
311 }
312 case Argument::kLong: {
313 current_arg = AlignUp(current_arg, sizeof(int64_t));
314 data = AppendInt64(new_string, data, *reinterpret_cast<const int64_t*>(current_arg));
315 ++current_arg; // Skip the low word, let the common code skip the high word.
316 break;
317 }
318
319 case Argument::kStringBuilder:
320 case Argument::kCharArray:
321 case Argument::kFloat:
322 case Argument::kDouble:
323 LOG(FATAL) << "Unimplemented arg format: 0x" << std::hex
324 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
325 UNREACHABLE();
326 default:
327 LOG(FATAL) << "Unexpected arg format: 0x" << std::hex
328 << (f & kArgMask) << " full format: 0x" << std::hex << format_;
329 UNREACHABLE();
330 }
331 ++current_arg;
332 DCHECK_LE(handle_index, hs_.NumberOfReferences());
333 }
334 DCHECK_EQ(RemainingSpace(new_string, data), 0u) << std::hex << format_;
335 }
336
operator ()(ObjPtr<mirror::Object> obj,size_t usable_size ATTRIBUTE_UNUSED) const337 inline void StringBuilderAppend::Builder::operator()(ObjPtr<mirror::Object> obj,
338 size_t usable_size ATTRIBUTE_UNUSED) const {
339 ObjPtr<mirror::String> new_string = ObjPtr<mirror::String>::DownCast(obj);
340 new_string->SetCount(length_with_flag_);
341 if (mirror::String::IsCompressed(length_with_flag_)) {
342 StoreData(new_string, new_string->GetValueCompressed());
343 } else {
344 StoreData(new_string, new_string->GetValue());
345 }
346 }
347
AppendF(uint32_t format,const uint32_t * args,Thread * self)348 ObjPtr<mirror::String> StringBuilderAppend::AppendF(uint32_t format,
349 const uint32_t* args,
350 Thread* self) {
351 Builder builder(format, args, self);
352 self->AssertNoPendingException();
353 int32_t length_with_flag = builder.CalculateLengthWithFlag();
354 if (self->IsExceptionPending()) {
355 return nullptr;
356 }
357 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator();
358 ObjPtr<mirror::String> result = mirror::String::Alloc(
359 self, length_with_flag, allocator_type, builder);
360
361 return result;
362 }
363
364 } // namespace art
365