libandroidfw: Add SparseEntry support for LoadedArsc

go/o-restable-sparse-entries

Test: make libandroidfw_tests
Change-Id: Ib1a7d1fc69008390eee53a1de04356dc50e05b45

6 files changed, 135 insertions, 67 deletions

diff --git a/libs/androidfw/LoadedArsc.cpp b/libs/androidfw/LoadedArsc.cpp
index c361ea2dbe0a..6ee5e86c55a2 100644
--- a/libs/androidfw/LoadedArsc.cpp
+++ b/libs/androidfw/LoadedArsc.cpp
@@ -18,6 +18,7 @@
 
 #include "androidfw/LoadedArsc.h"
 
+#include <algorithm>
 #include <cstddef>
 #include <limits>
 
@@ -244,31 +245,63 @@ bool LoadedPackage::FindEntry(const TypeSpecPtr& type_spec_ptr, uint16_t entry_i
 
   for (uint32_t i = 0; i < type_spec_ptr->type_count; i++) {
     const Type* type = &type_spec_ptr->types[i];
+    const ResTable_type* type_chunk = type->type;
 
     if (type->configuration.match(config) &&
         (best_config == nullptr || type->configuration.isBetterThan(*best_config, &config))) {
       // The configuration matches and is better than the previous selection.
       // Find the entry value if it exists for this configuration.
-      const size_t entry_count = dtohl(type->type->entryCount);
-      const size_t offsets_offset = dtohs(type->type->header.headerSize);
-      if (entry_idx < entry_count) {
-        // If the package hasn't been verified, do bounds checking.
-        if (!Verified) {
-          if (!VerifyResTableType(type->type)) {
-            continue;
-          }
+      const size_t entry_count = dtohl(type_chunk->entryCount);
+      const size_t offsets_offset = dtohs(type_chunk->header.headerSize);
+
+      // If the package hasn't been verified, do bounds checking.
+      if (!Verified) {
+        if (!VerifyResTableType(type_chunk)) {
+          continue;
+        }
+      }
+
+      // Check if there is the desired entry in this type.
+
+      if (type_chunk->flags & ResTable_type::FLAG_SPARSE) {
+        // This is encoded as a sparse map, so perform a binary search.
+        const ResTable_sparseTypeEntry* sparse_indices =
+            reinterpret_cast<const ResTable_sparseTypeEntry*>(
+                reinterpret_cast<const uint8_t*>(type_chunk) + offsets_offset);
+        const ResTable_sparseTypeEntry* sparse_indices_end = sparse_indices + entry_count;
+        const ResTable_sparseTypeEntry* result =
+            std::lower_bound(sparse_indices, sparse_indices_end, entry_idx,
+                             [](const ResTable_sparseTypeEntry& entry, uint16_t entry_idx) {
+                               return dtohs(entry.idx) < entry_idx;
+                             });
+
+        if (result == sparse_indices_end || dtohs(result->idx) != entry_idx) {
+          // No entry found.
+          continue;
+        }
+
+        // Extract the offset from the entry. Each offset must be a multiple of 4 so we store it as
+        // the real offset divided by 4.
+        best_offset = dtohs(result->offset) * 4u;
+      } else {
+        if (entry_idx >= entry_count) {
+          // This entry cannot be here.
+          continue;
         }
 
         const uint32_t* entry_offsets = reinterpret_cast<const uint32_t*>(
-            reinterpret_cast<const uint8_t*>(type->type) + offsets_offset);
+            reinterpret_cast<const uint8_t*>(type_chunk) + offsets_offset);
         const uint32_t offset = dtohl(entry_offsets[entry_idx]);
-        if (offset != ResTable_type::NO_ENTRY) {
-          // There is an entry for this resource, record it.
-          best_config = &type->configuration;
-          best_type = type->type;
-          best_offset = offset;
+        if (offset == ResTable_type::NO_ENTRY) {
+          continue;
         }
+
+        // There is an entry for this resource, record it.
+        best_offset = offset;
       }
+
+      best_config = &type->configuration;
+      best_type = type_chunk;
     }
   }
 
@@ -335,16 +368,29 @@ static bool VerifyType(const Chunk& chunk) {
   const size_t entry_count = dtohl(header->entryCount);
   const size_t offsets_offset = chunk.header_size();
 
-  // Check each entry offset.
-  const uint32_t* offsets =
-      reinterpret_cast<const uint32_t*>(reinterpret_cast<const uint8_t*>(header) + offsets_offset);
-  for (size_t i = 0; i < entry_count; i++) {
-    uint32_t offset = dtohl(offsets[i]);
-    if (offset != ResTable_type::NO_ENTRY) {
+  if (header->flags & ResTable_type::FLAG_SPARSE) {
+    // This is encoded as a sparse map, so perform a binary search.
+    const ResTable_sparseTypeEntry* sparse_indices =
+        reinterpret_cast<const ResTable_sparseTypeEntry*>(reinterpret_cast<const uint8_t*>(header) +
+                                                          offsets_offset);
+    for (size_t i = 0; i < entry_count; i++) {
+      const uint32_t offset = uint32_t{dtohs(sparse_indices[i].offset)} * 4u;
       if (!VerifyResTableEntry(header, offset, i)) {
         return false;
       }
     }
+  } else {
+    // Check each entry offset.
+    const uint32_t* offsets = reinterpret_cast<const uint32_t*>(
+        reinterpret_cast<const uint8_t*>(header) + offsets_offset);
+    for (size_t i = 0; i < entry_count; i++) {
+      uint32_t offset = dtohl(offsets[i]);
+      if (offset != ResTable_type::NO_ENTRY) {
+        if (!VerifyResTableEntry(header, offset, i)) {
+          return false;
+        }
+      }
+    }
   }
   return true;
 }
diff --git a/libs/androidfw/tests/AssetManager2_bench.cpp b/libs/androidfw/tests/AssetManager2_bench.cpp
index 739e733716c9..ea9d427f8f11 100644
--- a/libs/androidfw/tests/AssetManager2_bench.cpp
+++ b/libs/androidfw/tests/AssetManager2_bench.cpp
@@ -83,37 +83,6 @@ static void BM_AssetManagerLoadFrameworkAssetsOld(benchmark::State& state) {
 }
 BENCHMARK(BM_AssetManagerLoadFrameworkAssetsOld);
 
-static void GetResourceBenchmark(const std::vector<std::string>& paths,
-                                 const ResTable_config* config, uint32_t resid,
-                                 benchmark::State& state) {
-  std::vector<std::unique_ptr<const ApkAssets>> apk_assets;
-  std::vector<const ApkAssets*> apk_assets_ptrs;
-  for (const std::string& path : paths) {
-    std::unique_ptr<const ApkAssets> apk = ApkAssets::Load(path);
-    if (apk == nullptr) {
-      state.SkipWithError(base::StringPrintf("Failed to load assets %s", path.c_str()).c_str());
-      return;
-    }
-    apk_assets_ptrs.push_back(apk.get());
-    apk_assets.push_back(std::move(apk));
-  }
-
-  AssetManager2 assetmanager;
-  assetmanager.SetApkAssets(apk_assets_ptrs);
-  if (config != nullptr) {
-    assetmanager.SetConfiguration(*config);
-  }
-
-  Res_value value;
-  ResTable_config selected_config;
-  uint32_t flags;
-
-  while (state.KeepRunning()) {
-    assetmanager.GetResource(resid, false /* may_be_bag */, 0u /* density_override */, &value,
-                             &selected_config, &flags);
-  }
-}
-
 static void BM_AssetManagerGetResource(benchmark::State& state) {
   GetResourceBenchmark({GetTestDataPath() + "/basic/basic.apk"}, nullptr /*config*/,
                        basic::R::integer::number1, state);
diff --git a/libs/androidfw/tests/BenchmarkHelpers.cpp b/libs/androidfw/tests/BenchmarkHelpers.cpp
index 3619b7ee83ab..7149beef797f 100644
--- a/libs/androidfw/tests/BenchmarkHelpers.cpp
+++ b/libs/androidfw/tests/BenchmarkHelpers.cpp
@@ -18,6 +18,7 @@
 
 #include "android-base/stringprintf.h"
 #include "androidfw/AssetManager.h"
+#include "androidfw/AssetManager2.h"
 
 namespace android {
 
@@ -48,4 +49,34 @@ void GetResourceBenchmarkOld(const std::vector<std::string>& paths, const ResTab
   }
 }
 
+void GetResourceBenchmark(const std::vector<std::string>& paths, const ResTable_config* config,
+                          uint32_t resid, benchmark::State& state) {
+  std::vector<std::unique_ptr<const ApkAssets>> apk_assets;
+  std::vector<const ApkAssets*> apk_assets_ptrs;
+  for (const std::string& path : paths) {
+    std::unique_ptr<const ApkAssets> apk = ApkAssets::Load(path);
+    if (apk == nullptr) {
+      state.SkipWithError(base::StringPrintf("Failed to load assets %s", path.c_str()).c_str());
+      return;
+    }
+    apk_assets_ptrs.push_back(apk.get());
+    apk_assets.push_back(std::move(apk));
+  }
+
+  AssetManager2 assetmanager;
+  assetmanager.SetApkAssets(apk_assets_ptrs);
+  if (config != nullptr) {
+    assetmanager.SetConfiguration(*config);
+  }
+
+  Res_value value;
+  ResTable_config selected_config;
+  uint32_t flags;
+
+  while (state.KeepRunning()) {
+    assetmanager.GetResource(resid, false /* may_be_bag */, 0u /* density_override */, &value,
+                             &selected_config, &flags);
+  }
+}
+
 }  // namespace android
diff --git a/libs/androidfw/tests/BenchmarkHelpers.h b/libs/androidfw/tests/BenchmarkHelpers.h
index 0bb96b5d3471..eb0939d0e23b 100644
--- a/libs/androidfw/tests/BenchmarkHelpers.h
+++ b/libs/androidfw/tests/BenchmarkHelpers.h
@@ -30,6 +30,9 @@ namespace android {
 void GetResourceBenchmarkOld(const std::vector<std::string>& paths, const ResTable_config* config,
                              uint32_t resid, ::benchmark::State& state);
 
+void GetResourceBenchmark(const std::vector<std::string>& paths, const ResTable_config* config,
+                          uint32_t resid, benchmark::State& state);
+
 }  // namespace android
 
 #endif  // ANDROIDFW_TESTS_BENCHMARKHELPERS_H
diff --git a/libs/androidfw/tests/LoadedArsc_test.cpp b/libs/androidfw/tests/LoadedArsc_test.cpp
index 954a54d1ce62..37ddafb14fd3 100644
--- a/libs/androidfw/tests/LoadedArsc_test.cpp
+++ b/libs/androidfw/tests/LoadedArsc_test.cpp
@@ -19,11 +19,13 @@
 #include "TestHelpers.h"
 #include "data/basic/R.h"
 #include "data/libclient/R.h"
+#include "data/sparse/R.h"
 #include "data/styles/R.h"
 
 namespace app = com::android::app;
 namespace basic = com::android::basic;
 namespace libclient = com::android::libclient;
+namespace sparse = com::android::sparse;
 
 namespace android {
 
@@ -68,6 +70,23 @@ TEST(LoadedArscTest, FindDefaultEntry) {
   ASSERT_NE(nullptr, entry.entry);
 }
 
+TEST(LoadedArscTest, LoadSparseEntryApp) {
+  std::string contents;
+  ASSERT_TRUE(ReadFileFromZipToString(GetTestDataPath() + "/sparse/sparse.apk", "resources.arsc",
+                                      &contents));
+
+  std::unique_ptr<const LoadedArsc> loaded_arsc = LoadedArsc::Load(StringPiece(contents));
+  ASSERT_NE(nullptr, loaded_arsc);
+
+  ResTable_config config;
+  memset(&config, 0, sizeof(config));
+  config.sdkVersion = 26;
+
+  FindEntryResult entry;
+  ASSERT_TRUE(loaded_arsc->FindEntry(sparse::R::integer::foo_9, config, &entry));
+  ASSERT_NE(nullptr, entry.entry);
+}
+
 TEST(LoadedArscTest, LoadSharedLibrary) {
   std::string contents;
   ASSERT_TRUE(ReadFileFromZipToString(GetTestDataPath() + "/lib_one/lib_one.apk", "resources.arsc",
diff --git a/libs/androidfw/tests/SparseEntry_bench.cpp b/libs/androidfw/tests/SparseEntry_bench.cpp
index d6dc07dfb704..c9b4ad8af278 100644
--- a/libs/androidfw/tests/SparseEntry_bench.cpp
+++ b/libs/androidfw/tests/SparseEntry_bench.cpp
@@ -24,40 +24,40 @@ namespace sparse = com::android::sparse;
 
 namespace android {
 
-static void BM_SparseEntryGetResourceSparseSmall(benchmark::State& state) {
+static void BM_SparseEntryGetResourceOldSparse(benchmark::State& state, uint32_t resid) {
   ResTable_config config;
   memset(&config, 0, sizeof(config));
   config.sdkVersion = 26;
-  GetResourceBenchmarkOld({GetTestDataPath() + "/sparse/sparse.apk"}, &config,
-                          sparse::R::integer::foo_9, state);
+  GetResourceBenchmarkOld({GetTestDataPath() + "/sparse/sparse.apk"}, &config, resid, state);
 }
-BENCHMARK(BM_SparseEntryGetResourceSparseSmall);
+BENCHMARK_CAPTURE(BM_SparseEntryGetResourceOldSparse, Small, sparse::R::integer::foo_9);
+BENCHMARK_CAPTURE(BM_SparseEntryGetResourceOldSparse, Large, sparse::R::string::foo_999);
 
-static void BM_SparseEntryGetResourceNotSparseSmall(benchmark::State& state) {
+static void BM_SparseEntryGetResourceOldNotSparse(benchmark::State& state, uint32_t resid) {
   ResTable_config config;
   memset(&config, 0, sizeof(config));
   config.sdkVersion = 26;
-  GetResourceBenchmarkOld({GetTestDataPath() + "/sparse/not_sparse.apk"}, &config,
-                          sparse::R::integer::foo_9, state);
+  GetResourceBenchmarkOld({GetTestDataPath() + "/sparse/not_sparse.apk"}, &config, resid, state);
 }
-BENCHMARK(BM_SparseEntryGetResourceNotSparseSmall);
+BENCHMARK_CAPTURE(BM_SparseEntryGetResourceOldNotSparse, Small, sparse::R::integer::foo_9);
+BENCHMARK_CAPTURE(BM_SparseEntryGetResourceOldNotSparse, Large, sparse::R::string::foo_999);
 
-static void BM_SparseEntryGetResourceSparseLarge(benchmark::State& state) {
+static void BM_SparseEntryGetResourceSparse(benchmark::State& state, uint32_t resid) {
   ResTable_config config;
   memset(&config, 0, sizeof(config));
   config.sdkVersion = 26;
-  GetResourceBenchmarkOld({GetTestDataPath() + "/sparse/sparse.apk"}, &config,
-                          sparse::R::string::foo_999, state);
+  GetResourceBenchmark({GetTestDataPath() + "/sparse/sparse.apk"}, &config, resid, state);
 }
-BENCHMARK(BM_SparseEntryGetResourceSparseLarge);
+BENCHMARK_CAPTURE(BM_SparseEntryGetResourceSparse, Small, sparse::R::integer::foo_9);
+BENCHMARK_CAPTURE(BM_SparseEntryGetResourceSparse, Large, sparse::R::string::foo_999);
 
-static void BM_SparseEntryGetResourceNotSparseLarge(benchmark::State& state) {
+static void BM_SparseEntryGetResourceNotSparse(benchmark::State& state, uint32_t resid) {
   ResTable_config config;
   memset(&config, 0, sizeof(config));
   config.sdkVersion = 26;
-  GetResourceBenchmarkOld({GetTestDataPath() + "/sparse/not_sparse.apk"}, &config,
-                          sparse::R::string::foo_999, state);
+  GetResourceBenchmark({GetTestDataPath() + "/sparse/not_sparse.apk"}, &config, resid, state);
 }
-BENCHMARK(BM_SparseEntryGetResourceNotSparseLarge);
+BENCHMARK_CAPTURE(BM_SparseEntryGetResourceNotSparse, Small, sparse::R::integer::foo_9);
+BENCHMARK_CAPTURE(BM_SparseEntryGetResourceNotSparse, Large, sparse::R::string::foo_999);
 
 }  // namespace android