Home | History | Annotate | Download | only in optimize 
      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 
     19 #include <math.h>
     20 #include <unordered_set>
     21 
     22 #include "androidfw/StringPiece.h"
     23 
     24 #include "ResourceTable.h"
     25 #include "ValueVisitor.h"
     26 
     27 
     28 static const std::string base64_chars =
     29              "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
     30              "abcdefghijklmnopqrstuvwxyz"
     31              "0123456789-_";
     32 
     33 namespace aapt {
     34 
     35 ResourcePathShortener::ResourcePathShortener(
     36     std::map<std::string, std::string>& path_map_out)
     37     : path_map_(path_map_out) {
     38 }
     39 
     40 std::string ShortenFileName(const android::StringPiece& file_path, int output_length) {
     41   std::size_t hash_num = std::hash<android::StringPiece>{}(file_path);
     42   std::string result = "";
     43   // Convert to (modified) base64 so that it is a proper file path.
     44   for (int i = 0; i < output_length; i++) {
     45     uint8_t sextet = hash_num & 0x3f;
     46     hash_num >>= 6;
     47     result += base64_chars[sextet];
     48   }
     49   return result;
     50 }
     51 
     52 
     53 // Calculate the optimal hash length such that an average of 10% of resources
     54 // collide in their shortened path.
     55 // Reference: http://matt.might.net/articles/counting-hash-collisions/
     56 int OptimalShortenedLength(int num_resources) {
     57   int num_chars = 2;
     58   double N = 64*64; // hash space when hash is 2 chars long
     59   double max_collisions = num_resources * 0.1;
     60   while (num_resources - N + N * pow((N - 1) / N, num_resources) > max_collisions) {
     61     N *= 64;
     62     num_chars++;
     63   }
     64   return num_chars;
     65 }
     66 
     67 std::string GetShortenedPath(const android::StringPiece& shortened_filename,
     68     const android::StringPiece& extension, int collision_count) {
     69   std::string shortened_path = "res/" + shortened_filename.to_string();
     70   if (collision_count > 0) {
     71     shortened_path += std::to_string(collision_count);
     72   }
     73   shortened_path += extension;
     74   return shortened_path;
     75 }
     76 
     77 bool ResourcePathShortener::Consume(IAaptContext* context, ResourceTable* table) {
     78   // used to detect collisions
     79   std::unordered_set<std::string> shortened_paths;
     80   std::unordered_set<FileReference*> file_refs;
     81   for (auto& package : table->packages) {
     82     for (auto& type : package->types) {
     83       for (auto& entry : type->entries) {
     84         for (auto& config_value : entry->values) {
     85           FileReference* file_ref = ValueCast<FileReference>(config_value->value.get());
     86           if (file_ref) {
     87             file_refs.insert(file_ref);
     88           }
     89         }
     90       }
     91     }
     92   }
     93   int num_chars = OptimalShortenedLength(file_refs.size());
     94   for (auto& file_ref : file_refs) {
     95     android::StringPiece res_subdir, actual_filename, extension;
     96     util::ExtractResFilePathParts(*file_ref->path, &res_subdir, &actual_filename, &extension);
     97 
     98     std::string shortened_filename = ShortenFileName(*file_ref->path, num_chars);
     99     int collision_count = 0;
    100     std::string shortened_path = GetShortenedPath(shortened_filename, extension, collision_count);
    101     while (shortened_paths.find(shortened_path) != shortened_paths.end()) {
    102       collision_count++;
    103       shortened_path = GetShortenedPath(shortened_filename, extension, collision_count);
    104     }
    105     shortened_paths.insert(shortened_path);
    106     path_map_.insert({*file_ref->path, shortened_path});
    107     file_ref->path = table->string_pool.MakeRef(shortened_path, file_ref->path.GetContext());
    108   }
    109   return true;
    110 }
    111 
    112 }  // namespace aapt
    113