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