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 
Ref()34 StringPool::Ref::Ref() : entry_(nullptr) {}
35 
Ref(const StringPool::Ref & rhs)36 StringPool::Ref::Ref(const StringPool::Ref& rhs) : entry_(rhs.entry_) {
37   if (entry_ != nullptr) {
38     entry_->ref_++;
39   }
40 }
41 
Ref(StringPool::Entry * entry)42 StringPool::Ref::Ref(StringPool::Entry* entry) : entry_(entry) {
43   if (entry_ != nullptr) {
44     entry_->ref_++;
45   }
46 }
47 
~Ref()48 StringPool::Ref::~Ref() {
49   if (entry_ != nullptr) {
50     entry_->ref_--;
51   }
52 }
53 
operator =(const StringPool::Ref & rhs)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 
operator ==(const Ref & rhs) const66 bool StringPool::Ref::operator==(const Ref& rhs) const {
67   return entry_->value == rhs.entry_->value;
68 }
69 
operator !=(const Ref & rhs) const70 bool StringPool::Ref::operator!=(const Ref& rhs) const {
71   return entry_->value != rhs.entry_->value;
72 }
73 
operator ->() const74 const std::string* StringPool::Ref::operator->() const {
75   return &entry_->value;
76 }
77 
operator *() const78 const std::string& StringPool::Ref::operator*() const {
79   return entry_->value;
80 }
81 
index() const82 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 
GetContext() const87 const StringPool::Context& StringPool::Ref::GetContext() const {
88   return entry_->context;
89 }
90 
StyleRef()91 StringPool::StyleRef::StyleRef() : entry_(nullptr) {}
92 
StyleRef(const StringPool::StyleRef & rhs)93 StringPool::StyleRef::StyleRef(const StringPool::StyleRef& rhs)
94     : entry_(rhs.entry_) {
95   if (entry_ != nullptr) {
96     entry_->ref_++;
97   }
98 }
99 
StyleRef(StringPool::StyleEntry * entry)100 StringPool::StyleRef::StyleRef(StringPool::StyleEntry* entry) : entry_(entry) {
101   if (entry_ != nullptr) {
102     entry_->ref_++;
103   }
104 }
105 
~StyleRef()106 StringPool::StyleRef::~StyleRef() {
107   if (entry_ != nullptr) {
108     entry_->ref_--;
109   }
110 }
111 
operator =(const StringPool::StyleRef & rhs)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 
operator ==(const StyleRef & rhs) const124 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 
operator !=(const StyleRef & rhs) const144 bool StringPool::StyleRef::operator!=(const StyleRef& rhs) const {
145   return !operator==(rhs);
146 }
147 
operator ->() const148 const StringPool::StyleEntry* StringPool::StyleRef::operator->() const {
149   return entry_;
150 }
151 
operator *() const152 const StringPool::StyleEntry& StringPool::StyleRef::operator*() const {
153   return *entry_;
154 }
155 
index() const156 size_t StringPool::StyleRef::index() const {
157   return entry_->index_;
158 }
159 
GetContext() const160 const StringPool::Context& StringPool::StyleRef::GetContext() const {
161   return entry_->context;
162 }
163 
MakeRef(const StringPiece & str)164 StringPool::Ref StringPool::MakeRef(const StringPiece& str) {
165   return MakeRefImpl(str, Context{}, true);
166 }
167 
MakeRef(const StringPiece & str,const Context & context)168 StringPool::Ref StringPool::MakeRef(const StringPiece& str, const Context& context) {
169   return MakeRefImpl(str, context, true);
170 }
171 
MakeRefImpl(const StringPiece & str,const Context & context,bool unique)172 StringPool::Ref StringPool::MakeRefImpl(const StringPiece& str, const Context& context,
173                                         bool unique) {
174   if (unique) {
175     auto range = indexed_strings_.equal_range(str);
176     for (auto iter = range.first; iter != range.second; ++iter) {
177       if (context.priority == iter->second->context.priority) {
178         return Ref(iter->second);
179       }
180     }
181   }
182 
183   std::unique_ptr<Entry> entry(new Entry());
184   entry->value = str.to_string();
185   entry->context = context;
186   entry->index_ = strings_.size();
187   entry->ref_ = 0;
188   entry->pool_ = this;
189 
190   Entry* borrow = entry.get();
191   strings_.emplace_back(std::move(entry));
192   indexed_strings_.insert(std::make_pair(StringPiece(borrow->value), borrow));
193   return Ref(borrow);
194 }
195 
MakeRef(const Ref & ref)196 StringPool::Ref StringPool::MakeRef(const Ref& ref) {
197   if (ref.entry_->pool_ == this) {
198     return ref;
199   }
200   return MakeRef(ref.entry_->value, ref.entry_->context);
201 }
202 
MakeRef(const StyleString & str)203 StringPool::StyleRef StringPool::MakeRef(const StyleString& str) {
204   return MakeRef(str, Context{});
205 }
206 
MakeRef(const StyleString & str,const Context & context)207 StringPool::StyleRef StringPool::MakeRef(const StyleString& str, const Context& context) {
208   std::unique_ptr<StyleEntry> entry(new StyleEntry());
209   entry->value = str.str;
210   entry->context = context;
211   entry->index_ = styles_.size();
212   entry->ref_ = 0;
213   for (const aapt::Span& span : str.spans) {
214     entry->spans.emplace_back(Span{MakeRef(span.name), span.first_char, span.last_char});
215   }
216 
217   StyleEntry* borrow = entry.get();
218   styles_.emplace_back(std::move(entry));
219   return StyleRef(borrow);
220 }
221 
MakeRef(const StyleRef & ref)222 StringPool::StyleRef StringPool::MakeRef(const StyleRef& ref) {
223   std::unique_ptr<StyleEntry> entry(new StyleEntry());
224   entry->value = ref.entry_->value;
225   entry->context = ref.entry_->context;
226   entry->index_ = styles_.size();
227   entry->ref_ = 0;
228   for (const Span& span : ref.entry_->spans) {
229     entry->spans.emplace_back(Span{MakeRef(*span.name), span.first_char, span.last_char});
230   }
231 
232   StyleEntry* borrow = entry.get();
233   styles_.emplace_back(std::move(entry));
234   return StyleRef(borrow);
235 }
236 
ReAssignIndices()237 void StringPool::ReAssignIndices() {
238   // Assign the style indices.
239   const size_t style_len = styles_.size();
240   for (size_t index = 0; index < style_len; index++) {
241     styles_[index]->index_ = index;
242   }
243 
244   // Assign the string indices.
245   const size_t string_len = strings_.size();
246   for (size_t index = 0; index < string_len; index++) {
247     strings_[index]->index_ = index;
248   }
249 }
250 
Merge(StringPool && pool)251 void StringPool::Merge(StringPool&& pool) {
252   // First, change the owning pool for the incoming strings.
253   for (std::unique_ptr<Entry>& entry : pool.strings_) {
254     entry->pool_ = this;
255   }
256 
257   // Now move the styles, strings, and indices over.
258   std::move(pool.styles_.begin(), pool.styles_.end(), std::back_inserter(styles_));
259   pool.styles_.clear();
260   std::move(pool.strings_.begin(), pool.strings_.end(), std::back_inserter(strings_));
261   pool.strings_.clear();
262   indexed_strings_.insert(pool.indexed_strings_.begin(), pool.indexed_strings_.end());
263   pool.indexed_strings_.clear();
264 
265   ReAssignIndices();
266 }
267 
HintWillAdd(size_t string_count,size_t style_count)268 void StringPool::HintWillAdd(size_t string_count, size_t style_count) {
269   strings_.reserve(strings_.size() + string_count);
270   styles_.reserve(styles_.size() + style_count);
271 }
272 
Prune()273 void StringPool::Prune() {
274   const auto iter_end = indexed_strings_.end();
275   auto index_iter = indexed_strings_.begin();
276   while (index_iter != iter_end) {
277     if (index_iter->second->ref_ <= 0) {
278       index_iter = indexed_strings_.erase(index_iter);
279     } else {
280       ++index_iter;
281     }
282   }
283 
284   auto end_iter2 =
285       std::remove_if(strings_.begin(), strings_.end(),
286                      [](const std::unique_ptr<Entry>& entry) -> bool { return entry->ref_ <= 0; });
287   auto end_iter3 = std::remove_if(
288       styles_.begin(), styles_.end(),
289       [](const std::unique_ptr<StyleEntry>& entry) -> bool { return entry->ref_ <= 0; });
290 
291   // Remove the entries at the end or else we'll be accessing a deleted string from the StyleEntry.
292   strings_.erase(end_iter2, strings_.end());
293   styles_.erase(end_iter3, styles_.end());
294 
295   ReAssignIndices();
296 }
297 
298 template <typename E>
SortEntries(std::vector<std::unique_ptr<E>> & entries,const std::function<int (const StringPool::Context &,const StringPool::Context &)> & cmp)299 static void SortEntries(
300     std::vector<std::unique_ptr<E>>& entries,
301     const std::function<int(const StringPool::Context&, const StringPool::Context&)>& cmp) {
302   using UEntry = std::unique_ptr<E>;
303 
304   if (cmp != nullptr) {
305     std::sort(entries.begin(), entries.end(), [&cmp](const UEntry& a, const UEntry& b) -> bool {
306       int r = cmp(a->context, b->context);
307       if (r == 0) {
308         r = a->value.compare(b->value);
309       }
310       return r < 0;
311     });
312   } else {
313     std::sort(entries.begin(), entries.end(),
314               [](const UEntry& a, const UEntry& b) -> bool { return a->value < b->value; });
315   }
316 }
317 
Sort(const std::function<int (const Context &,const Context &)> & cmp)318 void StringPool::Sort(const std::function<int(const Context&, const Context&)>& cmp) {
319   SortEntries(styles_, cmp);
320   SortEntries(strings_, cmp);
321   ReAssignIndices();
322 }
323 
324 template <typename T>
EncodeLength(T * data,size_t length)325 static T* EncodeLength(T* data, size_t length) {
326   static_assert(std::is_integral<T>::value, "wat.");
327 
328   constexpr size_t kMask = 1 << ((sizeof(T) * 8) - 1);
329   constexpr size_t kMaxSize = kMask - 1;
330   if (length > kMaxSize) {
331     *data++ = kMask | (kMaxSize & (length >> (sizeof(T) * 8)));
332   }
333   *data++ = length;
334   return data;
335 }
336 
337 /**
338  * Returns the maximum possible string length that can be successfully encoded
339  * using 2 units of the specified T.
340  *    EncodeLengthMax<char> -> maximum unit length of 0x7FFF
341  *    EncodeLengthMax<char16_t> -> maximum unit length of 0x7FFFFFFF
342  **/
343 template <typename T>
EncodeLengthMax()344 static size_t EncodeLengthMax() {
345   static_assert(std::is_integral<T>::value, "wat.");
346 
347   constexpr size_t kMask = 1 << ((sizeof(T) * 8 * 2) - 1);
348   constexpr size_t max = kMask - 1;
349   return max;
350 }
351 
352 /**
353  * Returns the number of units (1 or 2) needed to encode the string length
354  * before writing the string.
355  */
356 template <typename T>
EncodedLengthUnits(size_t length)357 static size_t EncodedLengthUnits(size_t length) {
358   static_assert(std::is_integral<T>::value, "wat.");
359 
360   constexpr size_t kMask = 1 << ((sizeof(T) * 8) - 1);
361   constexpr size_t kMaxSize = kMask - 1;
362   return length > kMaxSize ? 2 : 1;
363 }
364 
365 const std::string kStringTooLarge = "STRING_TOO_LARGE";
366 
EncodeString(const std::string & str,const bool utf8,BigBuffer * out,IDiagnostics * diag)367 static bool EncodeString(const std::string& str, const bool utf8, BigBuffer* out,
368                          IDiagnostics* diag) {
369   if (utf8) {
370     const std::string& encoded = util::Utf8ToModifiedUtf8(str);
371     const ssize_t utf16_length = utf8_to_utf16_length(
372         reinterpret_cast<const uint8_t*>(encoded.data()), encoded.size());
373     CHECK(utf16_length >= 0);
374 
375     // Make sure the lengths to be encoded do not exceed the maximum length that
376     // can be encoded using chars
377     if ((((size_t)encoded.size()) > EncodeLengthMax<char>())
378         || (((size_t)utf16_length) > EncodeLengthMax<char>())) {
379 
380       diag->Error(DiagMessage() << "string too large to encode using UTF-8 "
381           << "written instead as '" << kStringTooLarge << "'");
382 
383       EncodeString(kStringTooLarge, utf8, out, diag);
384       return false;
385     }
386 
387     const size_t total_size = EncodedLengthUnits<char>(utf16_length)
388         + EncodedLengthUnits<char>(encoded.size()) + encoded.size() + 1;
389 
390     char* data = out->NextBlock<char>(total_size);
391 
392     // First encode the UTF16 string length.
393     data = EncodeLength(data, utf16_length);
394 
395     // Now encode the size of the real UTF8 string.
396     data = EncodeLength(data, encoded.size());
397     strncpy(data, encoded.data(), encoded.size());
398 
399   } else {
400     const std::u16string encoded = util::Utf8ToUtf16(str);
401     const ssize_t utf16_length = encoded.size();
402 
403     // Make sure the length to be encoded does not exceed the maximum possible
404     // length that can be encoded
405     if (((size_t)utf16_length) > EncodeLengthMax<char16_t>()) {
406       diag->Error(DiagMessage() << "string too large to encode using UTF-16 "
407           << "written instead as '" << kStringTooLarge << "'");
408 
409       EncodeString(kStringTooLarge, utf8, out, diag);
410       return false;
411     }
412 
413     // Total number of 16-bit words to write.
414     const size_t total_size = EncodedLengthUnits<char16_t>(utf16_length)
415         + encoded.size() + 1;
416 
417     char16_t* data = out->NextBlock<char16_t>(total_size);
418 
419     // Encode the actual UTF16 string length.
420     data = EncodeLength(data, utf16_length);
421     const size_t byte_length = encoded.size() * sizeof(char16_t);
422 
423     // NOTE: For some reason, strncpy16(data, entry->value.data(),
424     // entry->value.size()) truncates the string.
425     memcpy(data, encoded.data(), byte_length);
426 
427     // The null-terminating character is already here due to the block of data
428     // being set to 0s on allocation.
429   }
430 
431   return true;
432 }
433 
Flatten(BigBuffer * out,const StringPool & pool,bool utf8,IDiagnostics * diag)434 bool StringPool::Flatten(BigBuffer* out, const StringPool& pool, bool utf8,
435                          IDiagnostics* diag) {
436   bool no_error = true;
437   const size_t start_index = out->size();
438   android::ResStringPool_header* header = out->NextBlock<android::ResStringPool_header>();
439   header->header.type = util::HostToDevice16(android::RES_STRING_POOL_TYPE);
440   header->header.headerSize = util::HostToDevice16(sizeof(*header));
441   header->stringCount = util::HostToDevice32(pool.size());
442   header->styleCount = util::HostToDevice32(pool.styles_.size());
443   if (utf8) {
444     header->flags |= android::ResStringPool_header::UTF8_FLAG;
445   }
446 
447   uint32_t* indices = pool.size() != 0 ? out->NextBlock<uint32_t>(pool.size()) : nullptr;
448   uint32_t* style_indices =
449       pool.styles_.size() != 0 ? out->NextBlock<uint32_t>(pool.styles_.size()) : nullptr;
450 
451   const size_t before_strings_index = out->size();
452   header->stringsStart = before_strings_index - start_index;
453 
454   // Styles always come first.
455   for (const std::unique_ptr<StyleEntry>& entry : pool.styles_) {
456     *indices++ = out->size() - before_strings_index;
457     no_error = EncodeString(entry->value, utf8, out, diag) && no_error;
458   }
459 
460   for (const std::unique_ptr<Entry>& entry : pool.strings_) {
461     *indices++ = out->size() - before_strings_index;
462     no_error = EncodeString(entry->value, utf8, out, diag) && no_error;
463   }
464 
465   out->Align4();
466 
467   if (style_indices != nullptr) {
468     const size_t before_styles_index = out->size();
469     header->stylesStart = util::HostToDevice32(before_styles_index - start_index);
470 
471     for (const std::unique_ptr<StyleEntry>& entry : pool.styles_) {
472       *style_indices++ = out->size() - before_styles_index;
473 
474       if (!entry->spans.empty()) {
475         android::ResStringPool_span* span =
476             out->NextBlock<android::ResStringPool_span>(entry->spans.size());
477         for (const Span& s : entry->spans) {
478           span->name.index = util::HostToDevice32(s.name.index());
479           span->firstChar = util::HostToDevice32(s.first_char);
480           span->lastChar = util::HostToDevice32(s.last_char);
481           span++;
482         }
483       }
484 
485       uint32_t* spanEnd = out->NextBlock<uint32_t>();
486       *spanEnd = android::ResStringPool_span::END;
487     }
488 
489     // The error checking code in the platform looks for an entire
490     // ResStringPool_span structure worth of 0xFFFFFFFF at the end
491     // of the style block, so fill in the remaining 2 32bit words
492     // with 0xFFFFFFFF.
493     const size_t padding_length = sizeof(android::ResStringPool_span) -
494                                   sizeof(android::ResStringPool_span::name);
495     uint8_t* padding = out->NextBlock<uint8_t>(padding_length);
496     memset(padding, 0xff, padding_length);
497     out->Align4();
498   }
499   header->header.size = util::HostToDevice32(out->size() - start_index);
500   return no_error;
501 }
502 
FlattenUtf8(BigBuffer * out,const StringPool & pool,IDiagnostics * diag)503 bool StringPool::FlattenUtf8(BigBuffer* out, const StringPool& pool, IDiagnostics* diag) {
504   return Flatten(out, pool, true, diag);
505 }
506 
FlattenUtf16(BigBuffer * out,const StringPool & pool,IDiagnostics * diag)507 bool StringPool::FlattenUtf16(BigBuffer* out, const StringPool& pool, IDiagnostics* diag) {
508   return Flatten(out, pool, false, diag);
509 }
510 
511 }  // namespace aapt
512