Mohamed Heikal | c769403 | 2018-11-07 16:49:02 -0500 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2018 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 "optimize/ResourcePathShortener.h" |
| 18 | |
Mohamed Heikal | b2bac12 | 2019-07-17 17:47:17 -0400 | [diff] [blame] | 19 | #include <set> |
Mohamed Heikal | c769403 | 2018-11-07 16:49:02 -0500 | [diff] [blame] | 20 | #include <unordered_set> |
| 21 | |
| 22 | #include "androidfw/StringPiece.h" |
| 23 | |
| 24 | #include "ResourceTable.h" |
| 25 | #include "ValueVisitor.h" |
Mohamed Heikal | 61d528f | 2019-07-08 15:06:39 -0400 | [diff] [blame] | 26 | #include "util/Util.h" |
Mohamed Heikal | c769403 | 2018-11-07 16:49:02 -0500 | [diff] [blame] | 27 | |
| 28 | |
| 29 | static const std::string base64_chars = |
| 30 | "ABCDEFGHIJKLMNOPQRSTUVWXYZ" |
| 31 | "abcdefghijklmnopqrstuvwxyz" |
| 32 | "0123456789-_"; |
| 33 | |
| 34 | namespace aapt { |
| 35 | |
| 36 | ResourcePathShortener::ResourcePathShortener( |
| 37 | std::map<std::string, std::string>& path_map_out) |
| 38 | : path_map_(path_map_out) { |
| 39 | } |
| 40 | |
| 41 | std::string ShortenFileName(const android::StringPiece& file_path, int output_length) { |
| 42 | std::size_t hash_num = std::hash<android::StringPiece>{}(file_path); |
| 43 | std::string result = ""; |
| 44 | // Convert to (modified) base64 so that it is a proper file path. |
| 45 | for (int i = 0; i < output_length; i++) { |
| 46 | uint8_t sextet = hash_num & 0x3f; |
| 47 | hash_num >>= 6; |
| 48 | result += base64_chars[sextet]; |
| 49 | } |
| 50 | return result; |
| 51 | } |
| 52 | |
| 53 | |
Mohamed Heikal | 525714a | 2019-07-18 11:14:31 -0400 | [diff] [blame] | 54 | // Return the optimal hash length such that at most 10% of resources collide in |
| 55 | // their shortened path. |
Mohamed Heikal | c769403 | 2018-11-07 16:49:02 -0500 | [diff] [blame] | 56 | // Reference: http://matt.might.net/articles/counting-hash-collisions/ |
| 57 | int OptimalShortenedLength(int num_resources) { |
Mohamed Heikal | 525714a | 2019-07-18 11:14:31 -0400 | [diff] [blame] | 58 | if (num_resources > 4000) { |
| 59 | return 3; |
| 60 | } else { |
| 61 | return 2; |
Mohamed Heikal | c769403 | 2018-11-07 16:49:02 -0500 | [diff] [blame] | 62 | } |
Mohamed Heikal | c769403 | 2018-11-07 16:49:02 -0500 | [diff] [blame] | 63 | } |
| 64 | |
| 65 | std::string GetShortenedPath(const android::StringPiece& shortened_filename, |
| 66 | const android::StringPiece& extension, int collision_count) { |
| 67 | std::string shortened_path = "res/" + shortened_filename.to_string(); |
| 68 | if (collision_count > 0) { |
| 69 | shortened_path += std::to_string(collision_count); |
| 70 | } |
| 71 | shortened_path += extension; |
| 72 | return shortened_path; |
| 73 | } |
| 74 | |
Mohamed Heikal | b2bac12 | 2019-07-17 17:47:17 -0400 | [diff] [blame] | 75 | // implement custom comparator of FileReference pointers so as to use the |
| 76 | // underlying filepath as key rather than the integer address. This is to ensure |
| 77 | // determinism of output for colliding files. |
| 78 | struct PathComparator { |
| 79 | bool operator() (const FileReference* lhs, const FileReference* rhs) const { |
| 80 | return lhs->path->compare(*rhs->path); |
| 81 | } |
| 82 | }; |
| 83 | |
Mohamed Heikal | c769403 | 2018-11-07 16:49:02 -0500 | [diff] [blame] | 84 | bool ResourcePathShortener::Consume(IAaptContext* context, ResourceTable* table) { |
| 85 | // used to detect collisions |
| 86 | std::unordered_set<std::string> shortened_paths; |
Mohamed Heikal | b2bac12 | 2019-07-17 17:47:17 -0400 | [diff] [blame] | 87 | std::set<FileReference*, PathComparator> file_refs; |
Mohamed Heikal | c769403 | 2018-11-07 16:49:02 -0500 | [diff] [blame] | 88 | for (auto& package : table->packages) { |
| 89 | for (auto& type : package->types) { |
| 90 | for (auto& entry : type->entries) { |
| 91 | for (auto& config_value : entry->values) { |
| 92 | FileReference* file_ref = ValueCast<FileReference>(config_value->value.get()); |
| 93 | if (file_ref) { |
| 94 | file_refs.insert(file_ref); |
| 95 | } |
| 96 | } |
| 97 | } |
| 98 | } |
| 99 | } |
| 100 | int num_chars = OptimalShortenedLength(file_refs.size()); |
| 101 | for (auto& file_ref : file_refs) { |
| 102 | android::StringPiece res_subdir, actual_filename, extension; |
| 103 | util::ExtractResFilePathParts(*file_ref->path, &res_subdir, &actual_filename, &extension); |
| 104 | |
Mohamed Heikal | 61d528f | 2019-07-08 15:06:39 -0400 | [diff] [blame] | 105 | // Android detects ColorStateLists via pathname, skip res/color* |
| 106 | if (util::StartsWith(res_subdir, "res/color")) |
Mohamed Heikal | 7c75730 | 2019-04-25 17:39:43 -0400 | [diff] [blame] | 107 | continue; |
| 108 | |
Mohamed Heikal | c769403 | 2018-11-07 16:49:02 -0500 | [diff] [blame] | 109 | std::string shortened_filename = ShortenFileName(*file_ref->path, num_chars); |
| 110 | int collision_count = 0; |
| 111 | std::string shortened_path = GetShortenedPath(shortened_filename, extension, collision_count); |
| 112 | while (shortened_paths.find(shortened_path) != shortened_paths.end()) { |
| 113 | collision_count++; |
| 114 | shortened_path = GetShortenedPath(shortened_filename, extension, collision_count); |
| 115 | } |
| 116 | shortened_paths.insert(shortened_path); |
| 117 | path_map_.insert({*file_ref->path, shortened_path}); |
| 118 | file_ref->path = table->string_pool.MakeRef(shortened_path, file_ref->path.GetContext()); |
| 119 | } |
| 120 | return true; |
| 121 | } |
| 122 | |
| 123 | } // namespace aapt |