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