1 /* 2 * Copyright (C) 2015 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 "StringPool.h" 18 19 #include <algorithm> 20 #include <memory> 21 #include <string> 22 23 #include "android-base/logging.h" 24 #include "androidfw/ResourceTypes.h" 25 #include "androidfw/StringPiece.h" 26 27 #include "util/BigBuffer.h" 28 #include "util/Util.h" 29 30 using ::android::StringPiece; 31 32 namespace aapt { 33 34 StringPool::Ref::Ref() : entry_(nullptr) {} 35 36 StringPool::Ref::Ref(const StringPool::Ref& rhs) : entry_(rhs.entry_) { 37 if (entry_ != nullptr) { 38 entry_->ref_++; 39 } 40 } 41 42 StringPool::Ref::Ref(StringPool::Entry* entry) : entry_(entry) { 43 if (entry_ != nullptr) { 44 entry_->ref_++; 45 } 46 } 47 48 StringPool::Ref::~Ref() { 49 if (entry_ != nullptr) { 50 entry_->ref_--; 51 } 52 } 53 54 StringPool::Ref& StringPool::Ref::operator=(const StringPool::Ref& rhs) { 55 if (rhs.entry_ != nullptr) { 56 rhs.entry_->ref_++; 57 } 58 59 if (entry_ != nullptr) { 60 entry_->ref_--; 61 } 62 entry_ = rhs.entry_; 63 return *this; 64 } 65 66 bool StringPool::Ref::operator==(const Ref& rhs) const { 67 return entry_->value == rhs.entry_->value; 68 } 69 70 bool StringPool::Ref::operator!=(const Ref& rhs) const { 71 return entry_->value != rhs.entry_->value; 72 } 73 74 const std::string* StringPool::Ref::operator->() const { 75 return &entry_->value; 76 } 77 78 const std::string& StringPool::Ref::operator*() const { 79 return entry_->value; 80 } 81 82 size_t StringPool::Ref::index() const { 83 // Account for the styles, which *always* come first. 84 return entry_->pool_->styles_.size() + entry_->index_; 85 } 86 87 const StringPool::Context& StringPool::Ref::GetContext() const { 88 return entry_->context; 89 } 90 91 StringPool::StyleRef::StyleRef() : entry_(nullptr) {} 92 93 StringPool::StyleRef::StyleRef(const StringPool::StyleRef& rhs) 94 : entry_(rhs.entry_) { 95 if (entry_ != nullptr) { 96 entry_->ref_++; 97 } 98 } 99 100 StringPool::StyleRef::StyleRef(StringPool::StyleEntry* entry) : entry_(entry) { 101 if (entry_ != nullptr) { 102 entry_->ref_++; 103 } 104 } 105 106 StringPool::StyleRef::~StyleRef() { 107 if (entry_ != nullptr) { 108 entry_->ref_--; 109 } 110 } 111 112 StringPool::StyleRef& StringPool::StyleRef::operator=(const StringPool::StyleRef& rhs) { 113 if (rhs.entry_ != nullptr) { 114 rhs.entry_->ref_++; 115 } 116 117 if (entry_ != nullptr) { 118 entry_->ref_--; 119 } 120 entry_ = rhs.entry_; 121 return *this; 122 } 123 124 bool StringPool::StyleRef::operator==(const StyleRef& rhs) const { 125 if (entry_->value != rhs.entry_->value) { 126 return false; 127 } 128 129 if (entry_->spans.size() != rhs.entry_->spans.size()) { 130 return false; 131 } 132 133 auto rhs_iter = rhs.entry_->spans.begin(); 134 for (const Span& span : entry_->spans) { 135 const Span& rhs_span = *rhs_iter; 136 if (span.first_char != rhs_span.first_char || span.last_char != rhs_span.last_char || 137 span.name != rhs_span.name) { 138 return false; 139 } 140 } 141 return true; 142 } 143 144 bool StringPool::StyleRef::operator!=(const StyleRef& rhs) const { 145 return !operator==(rhs); 146 } 147 148 const StringPool::StyleEntry* StringPool::StyleRef::operator->() const { 149 return entry_; 150 } 151 152 const StringPool::StyleEntry& StringPool::StyleRef::operator*() const { 153 return *entry_; 154 } 155 156 size_t StringPool::StyleRef::index() const { 157 return entry_->index_; 158 } 159 160 const StringPool::Context& StringPool::StyleRef::GetContext() const { 161 return entry_->context; 162 } 163 164 StringPool::Ref StringPool::MakeRef(const StringPiece& str) { 165 return MakeRefImpl(str, Context{}, true); 166 } 167 168 StringPool::Ref StringPool::MakeRef(const StringPiece& str, const Context& context) { 169 return MakeRefImpl(str, context, true); 170 } 171 172 StringPool::Ref StringPool::MakeRefImpl(const StringPiece& str, const Context& context, 173 bool unique) { 174 if (unique) { 175 auto iter = indexed_strings_.find(str); 176 if (iter != std::end(indexed_strings_)) { 177 return Ref(iter->second); 178 } 179 } 180 181 std::unique_ptr<Entry> entry(new Entry()); 182 entry->value = str.to_string(); 183 entry->context = context; 184 entry->index_ = strings_.size(); 185 entry->ref_ = 0; 186 entry->pool_ = this; 187 188 Entry* borrow = entry.get(); 189 strings_.emplace_back(std::move(entry)); 190 indexed_strings_.insert(std::make_pair(StringPiece(borrow->value), borrow)); 191 return Ref(borrow); 192 } 193 194 StringPool::Ref StringPool::MakeRef(const Ref& ref) { 195 if (ref.entry_->pool_ == this) { 196 return ref; 197 } 198 return MakeRef(ref.entry_->value, ref.entry_->context); 199 } 200 201 StringPool::StyleRef StringPool::MakeRef(const StyleString& str) { 202 return MakeRef(str, Context{}); 203 } 204 205 StringPool::StyleRef StringPool::MakeRef(const StyleString& str, const Context& context) { 206 std::unique_ptr<StyleEntry> entry(new StyleEntry()); 207 entry->value = str.str; 208 entry->context = context; 209 entry->index_ = styles_.size(); 210 entry->ref_ = 0; 211 for (const aapt::Span& span : str.spans) { 212 entry->spans.emplace_back(Span{MakeRef(span.name), span.first_char, span.last_char}); 213 } 214 215 StyleEntry* borrow = entry.get(); 216 styles_.emplace_back(std::move(entry)); 217 return StyleRef(borrow); 218 } 219 220 StringPool::StyleRef StringPool::MakeRef(const StyleRef& ref) { 221 std::unique_ptr<StyleEntry> entry(new StyleEntry()); 222 entry->value = ref.entry_->value; 223 entry->context = ref.entry_->context; 224 entry->index_ = styles_.size(); 225 entry->ref_ = 0; 226 for (const Span& span : ref.entry_->spans) { 227 entry->spans.emplace_back(Span{MakeRef(*span.name), span.first_char, span.last_char}); 228 } 229 230 StyleEntry* borrow = entry.get(); 231 styles_.emplace_back(std::move(entry)); 232 return StyleRef(borrow); 233 } 234 235 void StringPool::ReAssignIndices() { 236 // Assign the style indices. 237 const size_t style_len = styles_.size(); 238 for (size_t index = 0; index < style_len; index++) { 239 styles_[index]->index_ = index; 240 } 241 242 // Assign the string indices. 243 const size_t string_len = strings_.size(); 244 for (size_t index = 0; index < string_len; index++) { 245 strings_[index]->index_ = index; 246 } 247 } 248 249 void StringPool::Merge(StringPool&& pool) { 250 // First, change the owning pool for the incoming strings. 251 for (std::unique_ptr<Entry>& entry : pool.strings_) { 252 entry->pool_ = this; 253 } 254 255 // Now move the styles, strings, and indices over. 256 std::move(pool.styles_.begin(), pool.styles_.end(), std::back_inserter(styles_)); 257 pool.styles_.clear(); 258 std::move(pool.strings_.begin(), pool.strings_.end(), std::back_inserter(strings_)); 259 pool.strings_.clear(); 260 indexed_strings_.insert(pool.indexed_strings_.begin(), pool.indexed_strings_.end()); 261 pool.indexed_strings_.clear(); 262 263 ReAssignIndices(); 264 } 265 266 void StringPool::HintWillAdd(size_t string_count, size_t style_count) { 267 strings_.reserve(strings_.size() + string_count); 268 styles_.reserve(styles_.size() + style_count); 269 } 270 271 void StringPool::Prune() { 272 const auto iter_end = indexed_strings_.end(); 273 auto index_iter = indexed_strings_.begin(); 274 while (index_iter != iter_end) { 275 if (index_iter->second->ref_ <= 0) { 276 index_iter = indexed_strings_.erase(index_iter); 277 } else { 278 ++index_iter; 279 } 280 } 281 282 auto end_iter2 = 283 std::remove_if(strings_.begin(), strings_.end(), 284 [](const std::unique_ptr<Entry>& entry) -> bool { return entry->ref_ <= 0; }); 285 auto end_iter3 = std::remove_if( 286 styles_.begin(), styles_.end(), 287 [](const std::unique_ptr<StyleEntry>& entry) -> bool { return entry->ref_ <= 0; }); 288 289 // Remove the entries at the end or else we'll be accessing a deleted string from the StyleEntry. 290 strings_.erase(end_iter2, strings_.end()); 291 styles_.erase(end_iter3, styles_.end()); 292 293 ReAssignIndices(); 294 } 295 296 template <typename E> 297 static void SortEntries( 298 std::vector<std::unique_ptr<E>>& entries, 299 const std::function<int(const StringPool::Context&, const StringPool::Context&)>& cmp) { 300 using UEntry = std::unique_ptr<E>; 301 302 if (cmp != nullptr) { 303 std::sort(entries.begin(), entries.end(), [&cmp](const UEntry& a, const UEntry& b) -> bool { 304 int r = cmp(a->context, b->context); 305 if (r == 0) { 306 r = a->value.compare(b->value); 307 } 308 return r < 0; 309 }); 310 } else { 311 std::sort(entries.begin(), entries.end(), 312 [](const UEntry& a, const UEntry& b) -> bool { return a->value < b->value; }); 313 } 314 } 315 316 void StringPool::Sort(const std::function<int(const Context&, const Context&)>& cmp) { 317 SortEntries(styles_, cmp); 318 SortEntries(strings_, cmp); 319 ReAssignIndices(); 320 } 321 322 template <typename T> 323 static T* EncodeLength(T* data, size_t length) { 324 static_assert(std::is_integral<T>::value, "wat."); 325 326 constexpr size_t kMask = 1 << ((sizeof(T) * 8) - 1); 327 constexpr size_t kMaxSize = kMask - 1; 328 if (length > kMaxSize) { 329 *data++ = kMask | (kMaxSize & (length >> (sizeof(T) * 8))); 330 } 331 *data++ = length; 332 return data; 333 } 334 335 template <typename T> 336 static size_t EncodedLengthUnits(size_t length) { 337 static_assert(std::is_integral<T>::value, "wat."); 338 339 constexpr size_t kMask = 1 << ((sizeof(T) * 8) - 1); 340 constexpr size_t kMaxSize = kMask - 1; 341 return length > kMaxSize ? 2 : 1; 342 } 343 344 static void EncodeString(const std::string& str, const bool utf8, BigBuffer* out) { 345 if (utf8) { 346 const std::string& encoded = str; 347 const ssize_t utf16_length = 348 utf8_to_utf16_length(reinterpret_cast<const uint8_t*>(str.data()), str.size()); 349 CHECK(utf16_length >= 0); 350 351 const size_t total_size = EncodedLengthUnits<char>(utf16_length) + 352 EncodedLengthUnits<char>(encoded.length()) + encoded.size() + 1; 353 354 char* data = out->NextBlock<char>(total_size); 355 356 // First encode the UTF16 string length. 357 data = EncodeLength(data, utf16_length); 358 359 // Now encode the size of the real UTF8 string. 360 data = EncodeLength(data, encoded.length()); 361 strncpy(data, encoded.data(), encoded.size()); 362 363 } else { 364 const std::u16string encoded = util::Utf8ToUtf16(str); 365 const ssize_t utf16_length = encoded.size(); 366 367 // Total number of 16-bit words to write. 368 const size_t total_size = EncodedLengthUnits<char16_t>(utf16_length) + encoded.size() + 1; 369 370 char16_t* data = out->NextBlock<char16_t>(total_size); 371 372 // Encode the actual UTF16 string length. 373 data = EncodeLength(data, utf16_length); 374 const size_t byte_length = encoded.size() * sizeof(char16_t); 375 376 // NOTE: For some reason, strncpy16(data, entry->value.data(), 377 // entry->value.size()) truncates the string. 378 memcpy(data, encoded.data(), byte_length); 379 380 // The null-terminating character is already here due to the block of data 381 // being set to 0s on allocation. 382 } 383 } 384 385 bool StringPool::Flatten(BigBuffer* out, const StringPool& pool, bool utf8) { 386 const size_t start_index = out->size(); 387 android::ResStringPool_header* header = out->NextBlock<android::ResStringPool_header>(); 388 header->header.type = util::HostToDevice16(android::RES_STRING_POOL_TYPE); 389 header->header.headerSize = util::HostToDevice16(sizeof(*header)); 390 header->stringCount = util::HostToDevice32(pool.size()); 391 header->styleCount = util::HostToDevice32(pool.styles_.size()); 392 if (utf8) { 393 header->flags |= android::ResStringPool_header::UTF8_FLAG; 394 } 395 396 uint32_t* indices = pool.size() != 0 ? out->NextBlock<uint32_t>(pool.size()) : nullptr; 397 uint32_t* style_indices = 398 pool.styles_.size() != 0 ? out->NextBlock<uint32_t>(pool.styles_.size()) : nullptr; 399 400 const size_t before_strings_index = out->size(); 401 header->stringsStart = before_strings_index - start_index; 402 403 // Styles always come first. 404 for (const std::unique_ptr<StyleEntry>& entry : pool.styles_) { 405 *indices++ = out->size() - before_strings_index; 406 EncodeString(entry->value, utf8, out); 407 } 408 409 for (const std::unique_ptr<Entry>& entry : pool.strings_) { 410 *indices++ = out->size() - before_strings_index; 411 EncodeString(entry->value, utf8, out); 412 } 413 414 out->Align4(); 415 416 if (style_indices != nullptr) { 417 const size_t before_styles_index = out->size(); 418 header->stylesStart = util::HostToDevice32(before_styles_index - start_index); 419 420 for (const std::unique_ptr<StyleEntry>& entry : pool.styles_) { 421 *style_indices++ = out->size() - before_styles_index; 422 423 if (!entry->spans.empty()) { 424 android::ResStringPool_span* span = 425 out->NextBlock<android::ResStringPool_span>(entry->spans.size()); 426 for (const Span& s : entry->spans) { 427 span->name.index = util::HostToDevice32(s.name.index()); 428 span->firstChar = util::HostToDevice32(s.first_char); 429 span->lastChar = util::HostToDevice32(s.last_char); 430 span++; 431 } 432 } 433 434 uint32_t* spanEnd = out->NextBlock<uint32_t>(); 435 *spanEnd = android::ResStringPool_span::END; 436 } 437 438 // The error checking code in the platform looks for an entire 439 // ResStringPool_span structure worth of 0xFFFFFFFF at the end 440 // of the style block, so fill in the remaining 2 32bit words 441 // with 0xFFFFFFFF. 442 const size_t padding_length = sizeof(android::ResStringPool_span) - 443 sizeof(android::ResStringPool_span::name); 444 uint8_t* padding = out->NextBlock<uint8_t>(padding_length); 445 memset(padding, 0xff, padding_length); 446 out->Align4(); 447 } 448 header->header.size = util::HostToDevice32(out->size() - start_index); 449 return true; 450 } 451 452 bool StringPool::FlattenUtf8(BigBuffer* out, const StringPool& pool) { 453 return Flatten(out, pool, true); 454 } 455 456 bool StringPool::FlattenUtf16(BigBuffer* out, const StringPool& pool) { 457 return Flatten(out, pool, false); 458 } 459 460 } // namespace aapt 461