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