1 /* 2 * Copyright (C) 2011 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-inl.h" 18 19 #include "arch/memcmp16.h" 20 #include "array.h" 21 #include "class-inl.h" 22 #include "gc/accounting/card_table-inl.h" 23 #include "handle_scope-inl.h" 24 #include "intern_table.h" 25 #include "object-inl.h" 26 #include "runtime.h" 27 #include "string-inl.h" 28 #include "thread.h" 29 #include "utf-inl.h" 30 31 namespace art { 32 namespace mirror { 33 34 // TODO: get global references for these 35 GcRoot<Class> String::java_lang_String_; 36 37 int32_t String::FastIndexOf(int32_t ch, int32_t start) { 38 int32_t count = GetLength(); 39 if (start < 0) { 40 start = 0; 41 } else if (start > count) { 42 start = count; 43 } 44 if (IsCompressed()) { 45 return FastIndexOf<uint8_t>(GetValueCompressed(), ch, start); 46 } else { 47 return FastIndexOf<uint16_t>(GetValue(), ch, start); 48 } 49 } 50 51 void String::SetClass(ObjPtr<Class> java_lang_String) { 52 CHECK(java_lang_String_.IsNull()); 53 CHECK(java_lang_String != nullptr); 54 CHECK(java_lang_String->IsStringClass()); 55 java_lang_String_ = GcRoot<Class>(java_lang_String); 56 } 57 58 void String::ResetClass() { 59 CHECK(!java_lang_String_.IsNull()); 60 java_lang_String_ = GcRoot<Class>(nullptr); 61 } 62 63 int String::ComputeHashCode() { 64 int32_t hash_code = 0; 65 if (IsCompressed()) { 66 hash_code = ComputeUtf16Hash(GetValueCompressed(), GetLength()); 67 } else { 68 hash_code = ComputeUtf16Hash(GetValue(), GetLength()); 69 } 70 SetHashCode(hash_code); 71 return hash_code; 72 } 73 74 int32_t String::GetUtfLength() { 75 if (IsCompressed()) { 76 return GetLength(); 77 } else { 78 return CountUtf8Bytes(GetValue(), GetLength()); 79 } 80 } 81 82 inline bool String::AllASCIIExcept(const uint16_t* chars, int32_t length, uint16_t non_ascii) { 83 DCHECK(!IsASCII(non_ascii)); 84 for (int32_t i = 0; i < length; ++i) { 85 if (!IsASCII(chars[i]) && chars[i] != non_ascii) { 86 return false; 87 } 88 } 89 return true; 90 } 91 92 ObjPtr<String> String::DoReplace(Thread* self, Handle<String> src, uint16_t old_c, uint16_t new_c) { 93 int32_t length = src->GetLength(); 94 DCHECK(src->IsCompressed() 95 ? ContainsElement(ArrayRef<uint8_t>(src->value_compressed_, length), old_c) 96 : ContainsElement(ArrayRef<uint16_t>(src->value_, length), old_c)); 97 bool compressible = 98 kUseStringCompression && 99 IsASCII(new_c) && 100 (src->IsCompressed() || (!IsASCII(old_c) && AllASCIIExcept(src->value_, length, old_c))); 101 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); 102 const int32_t length_with_flag = String::GetFlaggedCount(length, compressible); 103 SetStringCountVisitor visitor(length_with_flag); 104 ObjPtr<String> string = Alloc<true>(self, length_with_flag, allocator_type, visitor); 105 if (UNLIKELY(string == nullptr)) { 106 return nullptr; 107 } 108 if (compressible) { 109 auto replace = [old_c, new_c](uint16_t c) { 110 return dchecked_integral_cast<uint8_t>((old_c != c) ? c : new_c); 111 }; 112 uint8_t* out = string->value_compressed_; 113 if (LIKELY(src->IsCompressed())) { // LIKELY(compressible == src->IsCompressed()) 114 std::transform(src->value_compressed_, src->value_compressed_ + length, out, replace); 115 } else { 116 std::transform(src->value_, src->value_ + length, out, replace); 117 } 118 DCHECK(kUseStringCompression && AllASCII(out, length)); 119 } else { 120 auto replace = [old_c, new_c](uint16_t c) { 121 return (old_c != c) ? c : new_c; 122 }; 123 uint16_t* out = string->value_; 124 if (UNLIKELY(src->IsCompressed())) { // LIKELY(compressible == src->IsCompressed()) 125 std::transform(src->value_compressed_, src->value_compressed_ + length, out, replace); 126 } else { 127 std::transform(src->value_, src->value_ + length, out, replace); 128 } 129 DCHECK(!kUseStringCompression || !AllASCII(out, length)); 130 } 131 return string; 132 } 133 134 String* String::AllocFromStrings(Thread* self, Handle<String> string, Handle<String> string2) { 135 int32_t length = string->GetLength(); 136 int32_t length2 = string2->GetLength(); 137 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); 138 const bool compressible = kUseStringCompression && 139 (string->IsCompressed() && string2->IsCompressed()); 140 const int32_t length_with_flag = String::GetFlaggedCount(length + length2, compressible); 141 142 SetStringCountVisitor visitor(length_with_flag); 143 ObjPtr<String> new_string = Alloc<true>(self, length_with_flag, allocator_type, visitor); 144 if (UNLIKELY(new_string == nullptr)) { 145 return nullptr; 146 } 147 if (compressible) { 148 uint8_t* new_value = new_string->GetValueCompressed(); 149 memcpy(new_value, string->GetValueCompressed(), length * sizeof(uint8_t)); 150 memcpy(new_value + length, string2->GetValueCompressed(), length2 * sizeof(uint8_t)); 151 } else { 152 uint16_t* new_value = new_string->GetValue(); 153 if (string->IsCompressed()) { 154 for (int i = 0; i < length; ++i) { 155 new_value[i] = string->CharAt(i); 156 } 157 } else { 158 memcpy(new_value, string->GetValue(), length * sizeof(uint16_t)); 159 } 160 if (string2->IsCompressed()) { 161 for (int i = 0; i < length2; ++i) { 162 new_value[i+length] = string2->CharAt(i); 163 } 164 } else { 165 memcpy(new_value + length, string2->GetValue(), length2 * sizeof(uint16_t)); 166 } 167 } 168 return new_string.Ptr(); 169 } 170 171 String* String::AllocFromUtf16(Thread* self, int32_t utf16_length, const uint16_t* utf16_data_in) { 172 CHECK(utf16_data_in != nullptr || utf16_length == 0); 173 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); 174 const bool compressible = kUseStringCompression && 175 String::AllASCII<uint16_t>(utf16_data_in, utf16_length); 176 int32_t length_with_flag = String::GetFlaggedCount(utf16_length, compressible); 177 SetStringCountVisitor visitor(length_with_flag); 178 ObjPtr<String> string = Alloc<true>(self, length_with_flag, allocator_type, visitor); 179 if (UNLIKELY(string == nullptr)) { 180 return nullptr; 181 } 182 if (compressible) { 183 for (int i = 0; i < utf16_length; ++i) { 184 string->GetValueCompressed()[i] = static_cast<uint8_t>(utf16_data_in[i]); 185 } 186 } else { 187 uint16_t* array = string->GetValue(); 188 memcpy(array, utf16_data_in, utf16_length * sizeof(uint16_t)); 189 } 190 return string.Ptr(); 191 } 192 193 String* String::AllocFromModifiedUtf8(Thread* self, const char* utf) { 194 DCHECK(utf != nullptr); 195 size_t byte_count = strlen(utf); 196 size_t char_count = CountModifiedUtf8Chars(utf, byte_count); 197 return AllocFromModifiedUtf8(self, char_count, utf, byte_count); 198 } 199 200 String* String::AllocFromModifiedUtf8(Thread* self, 201 int32_t utf16_length, 202 const char* utf8_data_in) { 203 return AllocFromModifiedUtf8(self, utf16_length, utf8_data_in, strlen(utf8_data_in)); 204 } 205 206 String* String::AllocFromModifiedUtf8(Thread* self, 207 int32_t utf16_length, 208 const char* utf8_data_in, 209 int32_t utf8_length) { 210 gc::AllocatorType allocator_type = Runtime::Current()->GetHeap()->GetCurrentAllocator(); 211 const bool compressible = kUseStringCompression && (utf16_length == utf8_length); 212 const int32_t utf16_length_with_flag = String::GetFlaggedCount(utf16_length, compressible); 213 SetStringCountVisitor visitor(utf16_length_with_flag); 214 ObjPtr<String> string = Alloc<true>(self, utf16_length_with_flag, allocator_type, visitor); 215 if (UNLIKELY(string == nullptr)) { 216 return nullptr; 217 } 218 if (compressible) { 219 memcpy(string->GetValueCompressed(), utf8_data_in, utf16_length * sizeof(uint8_t)); 220 } else { 221 uint16_t* utf16_data_out = string->GetValue(); 222 ConvertModifiedUtf8ToUtf16(utf16_data_out, utf16_length, utf8_data_in, utf8_length); 223 } 224 return string.Ptr(); 225 } 226 227 bool String::Equals(ObjPtr<String> that) { 228 if (this == that) { 229 // Quick reference equality test 230 return true; 231 } else if (that == nullptr) { 232 // Null isn't an instanceof anything 233 return false; 234 } else if (this->GetLength() != that->GetLength()) { 235 // Quick length inequality test 236 return false; 237 } else { 238 // Note: don't short circuit on hash code as we're presumably here as the 239 // hash code was already equal 240 for (int32_t i = 0; i < that->GetLength(); ++i) { 241 if (this->CharAt(i) != that->CharAt(i)) { 242 return false; 243 } 244 } 245 return true; 246 } 247 } 248 249 bool String::Equals(const uint16_t* that_chars, int32_t that_offset, int32_t that_length) { 250 if (this->GetLength() != that_length) { 251 return false; 252 } else { 253 for (int32_t i = 0; i < that_length; ++i) { 254 if (this->CharAt(i) != that_chars[that_offset + i]) { 255 return false; 256 } 257 } 258 return true; 259 } 260 } 261 262 bool String::Equals(const char* modified_utf8) { 263 const int32_t length = GetLength(); 264 int32_t i = 0; 265 while (i < length) { 266 const uint32_t ch = GetUtf16FromUtf8(&modified_utf8); 267 if (ch == '\0') { 268 return false; 269 } 270 271 if (GetLeadingUtf16Char(ch) != CharAt(i++)) { 272 return false; 273 } 274 275 const uint16_t trailing = GetTrailingUtf16Char(ch); 276 if (trailing != 0) { 277 if (i == length) { 278 return false; 279 } 280 281 if (CharAt(i++) != trailing) { 282 return false; 283 } 284 } 285 } 286 return *modified_utf8 == '\0'; 287 } 288 289 bool String::Equals(const StringPiece& modified_utf8) { 290 const int32_t length = GetLength(); 291 const char* p = modified_utf8.data(); 292 for (int32_t i = 0; i < length; ++i) { 293 uint32_t ch = GetUtf16FromUtf8(&p); 294 295 if (GetLeadingUtf16Char(ch) != CharAt(i)) { 296 return false; 297 } 298 299 const uint16_t trailing = GetTrailingUtf16Char(ch); 300 if (trailing != 0) { 301 if (i == (length - 1)) { 302 return false; 303 } 304 305 if (CharAt(++i) != trailing) { 306 return false; 307 } 308 } 309 } 310 return true; 311 } 312 313 // Create a modified UTF-8 encoded std::string from a java/lang/String object. 314 std::string String::ToModifiedUtf8() { 315 size_t byte_count = GetUtfLength(); 316 std::string result(byte_count, static_cast<char>(0)); 317 if (IsCompressed()) { 318 for (size_t i = 0; i < byte_count; ++i) { 319 result[i] = static_cast<char>(CharAt(i)); 320 } 321 } else { 322 const uint16_t* chars = GetValue(); 323 ConvertUtf16ToModifiedUtf8(&result[0], byte_count, chars, GetLength()); 324 } 325 return result; 326 } 327 328 int32_t String::CompareTo(ObjPtr<String> rhs) { 329 // Quick test for comparison of a string with itself. 330 ObjPtr<String> lhs = this; 331 if (lhs == rhs) { 332 return 0; 333 } 334 int32_t lhs_count = lhs->GetLength(); 335 int32_t rhs_count = rhs->GetLength(); 336 int32_t count_diff = lhs_count - rhs_count; 337 int32_t min_count = (count_diff < 0) ? lhs_count : rhs_count; 338 if (lhs->IsCompressed() && rhs->IsCompressed()) { 339 const uint8_t* lhs_chars = lhs->GetValueCompressed(); 340 const uint8_t* rhs_chars = rhs->GetValueCompressed(); 341 for (int32_t i = 0; i < min_count; ++i) { 342 int32_t char_diff = static_cast<int32_t>(lhs_chars[i]) - static_cast<int32_t>(rhs_chars[i]); 343 if (char_diff != 0) { 344 return char_diff; 345 } 346 } 347 } else if (lhs->IsCompressed() || rhs->IsCompressed()) { 348 const uint8_t* compressed_chars = 349 lhs->IsCompressed() ? lhs->GetValueCompressed() : rhs->GetValueCompressed(); 350 const uint16_t* uncompressed_chars = lhs->IsCompressed() ? rhs->GetValue() : lhs->GetValue(); 351 for (int32_t i = 0; i < min_count; ++i) { 352 int32_t char_diff = 353 static_cast<int32_t>(compressed_chars[i]) - static_cast<int32_t>(uncompressed_chars[i]); 354 if (char_diff != 0) { 355 return lhs->IsCompressed() ? char_diff : -char_diff; 356 } 357 } 358 } else { 359 const uint16_t* lhs_chars = lhs->GetValue(); 360 const uint16_t* rhs_chars = rhs->GetValue(); 361 // FIXME: The MemCmp16() name is misleading. It returns the char difference on mismatch 362 // where memcmp() only guarantees that the returned value has the same sign. 363 int32_t char_diff = MemCmp16(lhs_chars, rhs_chars, min_count); 364 if (char_diff != 0) { 365 return char_diff; 366 } 367 } 368 return count_diff; 369 } 370 371 void String::VisitRoots(RootVisitor* visitor) { 372 java_lang_String_.VisitRootIfNonNull(visitor, RootInfo(kRootStickyClass)); 373 } 374 375 CharArray* String::ToCharArray(Thread* self) { 376 StackHandleScope<1> hs(self); 377 Handle<String> string(hs.NewHandle(this)); 378 ObjPtr<CharArray> result = CharArray::Alloc(self, GetLength()); 379 if (result != nullptr) { 380 if (string->IsCompressed()) { 381 int32_t length = string->GetLength(); 382 for (int i = 0; i < length; ++i) { 383 result->GetData()[i] = string->CharAt(i); 384 } 385 } else { 386 memcpy(result->GetData(), string->GetValue(), string->GetLength() * sizeof(uint16_t)); 387 } 388 } else { 389 self->AssertPendingOOMException(); 390 } 391 return result.Ptr(); 392 } 393 394 void String::GetChars(int32_t start, int32_t end, Handle<CharArray> array, int32_t index) { 395 uint16_t* data = array->GetData() + index; 396 if (IsCompressed()) { 397 for (int i = start; i < end; ++i) { 398 data[i-start] = CharAt(i); 399 } 400 } else { 401 uint16_t* value = GetValue() + start; 402 memcpy(data, value, (end - start) * sizeof(uint16_t)); 403 } 404 } 405 406 bool String::IsValueNull() { 407 return (IsCompressed()) ? (GetValueCompressed() == nullptr) : (GetValue() == nullptr); 408 } 409 410 std::string String::PrettyStringDescriptor(ObjPtr<mirror::String> java_descriptor) { 411 if (java_descriptor == nullptr) { 412 return "null"; 413 } 414 return java_descriptor->PrettyStringDescriptor(); 415 } 416 417 std::string String::PrettyStringDescriptor() { 418 return PrettyDescriptor(ToModifiedUtf8().c_str()); 419 } 420 421 } // namespace mirror 422 } // namespace art 423