[res] Optimize idmap format for lookups

Idmap format is currently storing sorted mappings for the
overlays: be it target id -> overlay id, or target id ->
frro data, or the reverse overlay id -> target id list

All of these require binary search for finding the right entry,
and this binary search always touches just 4 bytes of the key,
skipping over all remaining bytes of value. This usually doesn't
make much of a difference for the smaller idmaps but in case of
the larger ones binary search has to load a whole bunch of
RAM into the CPU cache to then throw at least half of it away.

This CL rearranges all mappings into two separate lists: the
first one only contains the sorted keys, and the second one
stores the corresponding data in the same order. This means the
search can only touch the minimum amount of RAM and disk pages,
and then jump exactly to the value of the element it found.

We don't have any benchmarks that would _directly_ capture the
speedup here, and the Java resources_perf ones are too noisy to
make a clear call, but overall they look like some 3-5% speedup
for the overlaid lookups

Test: atest libanrdoidfw_tests idmap2_tests libandroidfw_benchmarks
Flag: EXEMPT performance optimization
Change-Id: I450797f233c9371e70738546a89feaa0e683b333

10 files changed, 234 insertions, 185 deletions

diff --git a/cmds/idmap2/include/idmap2/Idmap.h b/cmds/idmap2/include/idmap2/Idmap.h
index e86f81485a41..b0ba01957ab6 100644
--- a/cmds/idmap2/include/idmap2/Idmap.h
+++ b/cmds/idmap2/include/idmap2/Idmap.h
@@ -21,18 +21,19 @@
  * header                     := magic version target_crc overlay_crc fulfilled_policies
  *                               enforce_overlayable target_path overlay_path overlay_name
  *                               debug_info
- * data                       := data_header target_entry* target_inline_entry*
-                                 target_inline_entry_value* config* overlay_entry* string_pool
+ * data                       := data_header target_entries target_inline_entries
+                                 target_inline_entry_value* config* overlay_entries string_pool
  * data_header                := target_entry_count target_inline_entry_count
                                  target_inline_entry_value_count config_count overlay_entry_count
  *                               string_pool_index
- * target_entry               := target_id overlay_id
- * target_inline_entry        := target_id start_value_index value_count
+ * target_entries             := target_id* overlay_id*
+ * target_inline_entries      := target_id* target_inline_value_header*
+ * target_inline_value_header := start_value_index value_count
  * target_inline_entry_value  := config_index Res_value::size padding(1) Res_value::type
  *                               Res_value::value
  * config                     := target_id Res_value::size padding(1) Res_value::type
  *                               Res_value::value
- * overlay_entry              := overlay_id target_id
+ * overlay_entries            := overlay_id* target_id*
  *
  * debug_info                       := string
  * enforce_overlayable              := <uint32_t>
diff --git a/cmds/idmap2/libidmap2/BinaryStreamVisitor.cpp b/cmds/idmap2/libidmap2/BinaryStreamVisitor.cpp
index 89769246434a..00ef0c7f8cf0 100644
--- a/cmds/idmap2/libidmap2/BinaryStreamVisitor.cpp
+++ b/cmds/idmap2/libidmap2/BinaryStreamVisitor.cpp
@@ -66,43 +66,57 @@ void BinaryStreamVisitor::visit(const IdmapHeader& header) {
 void BinaryStreamVisitor::visit(const IdmapData& data) {
   for (const auto& target_entry : data.GetTargetEntries()) {
     Write32(target_entry.target_id);
+  }
+  for (const auto& target_entry : data.GetTargetEntries()) {
     Write32(target_entry.overlay_id);
   }
 
-  static constexpr uint16_t kValueSize = 8U;
-  std::vector<std::pair<ConfigDescription, TargetValue>> target_values;
-  target_values.reserve(data.GetHeader()->GetTargetInlineEntryValueCount());
-  for (const auto& target_entry : data.GetTargetInlineEntries()) {
-    Write32(target_entry.target_id);
-    Write32(target_values.size());
-    Write32(target_entry.values.size());
-    target_values.insert(
-        target_values.end(), target_entry.values.begin(), target_entry.values.end());
+  uint32_t current_inline_entry_values_count = 0;
+  for (const auto& target_inline_entry : data.GetTargetInlineEntries()) {
+    Write32(target_inline_entry.target_id);
+  }
+  for (const auto& target_inline_entry : data.GetTargetInlineEntries()) {
+    Write32(current_inline_entry_values_count);
+    Write32(target_inline_entry.values.size());
+    current_inline_entry_values_count += target_inline_entry.values.size();
   }
 
   std::vector<ConfigDescription> configs;
   configs.reserve(data.GetHeader()->GetConfigCount());
-  for (const auto& target_entry_value : target_values) {
-    auto config_it = find(configs.begin(), configs.end(), target_entry_value.first);
-    if (config_it != configs.end()) {
-      Write32(config_it - configs.begin());
-    } else {
-      Write32(configs.size());
-      configs.push_back(target_entry_value.first);
+  for (const auto& target_entry : data.GetTargetInlineEntries()) {
+    for (const auto& target_entry_value : target_entry.values) {
+      auto config_it = std::find(configs.begin(), configs.end(), target_entry_value.first);
+      if (config_it != configs.end()) {
+        Write32(config_it - configs.begin());
+      } else {
+        Write32(configs.size());
+        configs.push_back(target_entry_value.first);
+      }
+      // We're writing a Res_value entry here, and the first 3 bytes of that are
+      // sizeof() + a padding 0 byte
+      static constexpr decltype(android::Res_value::size) kSize = sizeof(android::Res_value);
+      Write16(kSize);
+      Write8(0U);
+      Write8(target_entry_value.second.data_type);
+      Write32(target_entry_value.second.data_value);
     }
-    Write16(kValueSize);
-    Write8(0U);  // padding
-    Write8(target_entry_value.second.data_type);
-    Write32(target_entry_value.second.data_value);
   }
 
-  for( auto& cd : configs) {
-    cd.swapHtoD();
-    stream_.write(reinterpret_cast<char*>(&cd), sizeof(cd));
+  if (!configs.empty()) {
+    stream_.write(reinterpret_cast<const char*>(&configs.front()),
+                  sizeof(configs.front()) * configs.size());
+    if (configs.size() >= 100) {
+      // Let's write a message to future us so that they know when to replace the linear search
+      // in `configs` vector with something more efficient.
+      LOG(WARNING) << "Idmap got " << configs.size()
+                   << " configurations, time to fix the bruteforce search";
+    }
   }
 
   for (const auto& overlay_entry : data.GetOverlayEntries()) {
     Write32(overlay_entry.overlay_id);
+  }
+  for (const auto& overlay_entry : data.GetOverlayEntries()) {
     Write32(overlay_entry.target_id);
   }
 
diff --git a/cmds/idmap2/libidmap2/Idmap.cpp b/cmds/idmap2/libidmap2/Idmap.cpp
index 12d9dd9bd1ad..7680109f1d54 100644
--- a/cmds/idmap2/libidmap2/Idmap.cpp
+++ b/cmds/idmap2/libidmap2/Idmap.cpp
@@ -204,73 +204,91 @@ std::unique_ptr<const IdmapData> IdmapData::FromBinaryStream(std::istream& strea
   }
 
   // Read the mapping of target resource id to overlay resource value.
+  data->target_entries_.resize(data->header_->GetTargetEntryCount());
   for (size_t i = 0; i < data->header_->GetTargetEntryCount(); i++) {
-    TargetEntry target_entry{};
-    if (!Read32(stream, &target_entry.target_id) || !Read32(stream, &target_entry.overlay_id)) {
+    if (!Read32(stream, &data->target_entries_[i].target_id)) {
+      return nullptr;
+    }
+  }
+  for (size_t i = 0; i < data->header_->GetTargetEntryCount(); i++) {
+    if (!Read32(stream, &data->target_entries_[i].overlay_id)) {
       return nullptr;
     }
-    data->target_entries_.emplace_back(target_entry);
   }
 
   // Read the mapping of target resource id to inline overlay values.
-  std::vector<std::tuple<TargetInlineEntry, uint32_t, uint32_t>> target_inline_entries;
+  struct TargetInlineEntryHeader {
+    ResourceId target_id;
+    uint32_t values_offset;
+    uint32_t values_count;
+  };
+  std::vector<TargetInlineEntryHeader> target_inline_entries(
+      data->header_->GetTargetInlineEntryCount());
+  for (size_t i = 0; i < data->header_->GetTargetInlineEntryCount(); i++) {
+    if (!Read32(stream, &target_inline_entries[i].target_id)) {
+      return nullptr;
+    }
+  }
   for (size_t i = 0; i < data->header_->GetTargetInlineEntryCount(); i++) {
-    TargetInlineEntry target_entry{};
-    uint32_t entry_offset;
-    uint32_t entry_count;
-    if (!Read32(stream, &target_entry.target_id) || !Read32(stream, &entry_offset)
-        || !Read32(stream, &entry_count)) {
+    if (!Read32(stream, &target_inline_entries[i].values_offset) ||
+        !Read32(stream, &target_inline_entries[i].values_count)) {
       return nullptr;
     }
-    target_inline_entries.emplace_back(target_entry, entry_offset, entry_count);
   }
 
   // Read the inline overlay resource values
-  std::vector<std::pair<uint32_t, TargetValue>> target_values;
-  uint8_t unused1;
-  uint16_t unused2;
-  for (size_t i = 0; i < data->header_->GetTargetInlineEntryValueCount(); i++) {
+  struct TargetValueHeader {
     uint32_t config_index;
-    if (!Read32(stream, &config_index)) {
+    DataType data_type;
+    DataValue data_value;
+  };
+  std::vector<TargetValueHeader> target_values(data->header_->GetTargetInlineEntryValueCount());
+  for (size_t i = 0; i < data->header_->GetTargetInlineEntryValueCount(); i++) {
+    auto& value = target_values[i];
+    if (!Read32(stream, &value.config_index)) {
       return nullptr;
     }
-    TargetValue value;
-    if (!Read16(stream, &unused2)
-        || !Read8(stream, &unused1)
-        || !Read8(stream, &value.data_type)
-        || !Read32(stream, &value.data_value)) {
+    // skip the padding
+    stream.seekg(3, std::ios::cur);
+    if (!Read8(stream, &value.data_type) || !Read32(stream, &value.data_value)) {
       return nullptr;
     }
-    target_values.emplace_back(config_index, value);
   }
 
   // Read the configurations
-  std::vector<ConfigDescription> configurations;
-  for (size_t i = 0; i < data->header_->GetConfigCount(); i++) {
-    ConfigDescription cd;
-    if (!stream.read(reinterpret_cast<char*>(&cd), sizeof(ConfigDescription))) {
+  std::vector<ConfigDescription> configurations(data->header_->GetConfigCount());
+  if (!configurations.empty()) {
+    if (!stream.read(reinterpret_cast<char*>(&configurations.front()),
+                     sizeof(configurations.front()) * configurations.size())) {
       return nullptr;
     }
-    configurations.emplace_back(cd);
   }
 
   // Construct complete target inline entries
-  for (auto [target_entry, entry_offset, entry_count] : target_inline_entries) {
-    for(size_t i = 0; i < entry_count; i++) {
-      const auto& target_value = target_values[entry_offset + i];
-      const auto& config = configurations[target_value.first];
-      target_entry.values[config] = target_value.second;
+  data->target_inline_entries_.reserve(target_inline_entries.size());
+  for (auto&& entry_header : target_inline_entries) {
+    TargetInlineEntry& entry = data->target_inline_entries_.emplace_back();
+    entry.target_id = entry_header.target_id;
+    for (size_t i = 0; i < entry_header.values_count; i++) {
+      const auto& value_header = target_values[entry_header.values_offset + i];
+      const auto& config = configurations[value_header.config_index];
+      auto& value = entry.values[config];
+      value.data_type = value_header.data_type;
+      value.data_value = value_header.data_value;
     }
-    data->target_inline_entries_.emplace_back(target_entry);
   }
 
   // Read the mapping of overlay resource id to target resource id.
+  data->overlay_entries_.resize(data->header_->GetOverlayEntryCount());
+  for (size_t i = 0; i < data->header_->GetOverlayEntryCount(); i++) {
+    if (!Read32(stream, &data->overlay_entries_[i].overlay_id)) {
+      return nullptr;
+    }
+  }
   for (size_t i = 0; i < data->header_->GetOverlayEntryCount(); i++) {
-    OverlayEntry overlay_entry{};
-    if (!Read32(stream, &overlay_entry.overlay_id) || !Read32(stream, &overlay_entry.target_id)) {
+    if (!Read32(stream, &data->overlay_entries_[i].target_id)) {
       return nullptr;
     }
-    data->overlay_entries_.emplace_back(overlay_entry);
   }
 
   // Read raw string pool bytes.
@@ -320,7 +338,7 @@ Result<std::unique_ptr<const IdmapData>> IdmapData::FromResourceMapping(
   std::unique_ptr<IdmapData> data(new IdmapData());
   data->string_pool_data_ = std::string(resource_mapping.GetStringPoolData());
   uint32_t inline_value_count = 0;
-  std::set<std::string> config_set;
+  std::set<std::string_view> config_set;
   for (const auto& mapping : resource_mapping.GetTargetToOverlayMap()) {
     if (auto overlay_resource = std::get_if<ResourceId>(&mapping.second)) {
       data->target_entries_.push_back({mapping.first, *overlay_resource});
@@ -329,7 +347,9 @@ Result<std::unique_ptr<const IdmapData>> IdmapData::FromResourceMapping(
       for (const auto& [config, value] : std::get<ConfigMap>(mapping.second)) {
         config_set.insert(config);
         ConfigDescription cd;
-        ConfigDescription::Parse(config, &cd);
+        if (!ConfigDescription::Parse(config, &cd)) {
+          return Error("failed to parse configuration string '%s'", config.c_str());
+        }
         values[cd] = value;
         inline_value_count++;
       }
diff --git a/cmds/idmap2/tests/IdmapTests.cpp b/cmds/idmap2/tests/IdmapTests.cpp
index c85619c1e4bf..1b656e8c2088 100644
--- a/cmds/idmap2/tests/IdmapTests.cpp
+++ b/cmds/idmap2/tests/IdmapTests.cpp
@@ -68,7 +68,7 @@ TEST(IdmapTests, CreateIdmapHeaderFromBinaryStream) {
   std::unique_ptr<const IdmapHeader> header = IdmapHeader::FromBinaryStream(stream);
   ASSERT_THAT(header, NotNull());
   ASSERT_EQ(header->GetMagic(), 0x504d4449U);
-  ASSERT_EQ(header->GetVersion(), 0x09U);
+  ASSERT_EQ(header->GetVersion(), 10);
   ASSERT_EQ(header->GetTargetCrc(), 0x1234U);
   ASSERT_EQ(header->GetOverlayCrc(), 0x5678U);
   ASSERT_EQ(header->GetFulfilledPolicies(), 0x11);
@@ -143,7 +143,7 @@ TEST(IdmapTests, CreateIdmapFromBinaryStream) {
 
   ASSERT_THAT(idmap->GetHeader(), NotNull());
   ASSERT_EQ(idmap->GetHeader()->GetMagic(), 0x504d4449U);
-  ASSERT_EQ(idmap->GetHeader()->GetVersion(), 0x09U);
+  ASSERT_EQ(idmap->GetHeader()->GetVersion(), 10);
   ASSERT_EQ(idmap->GetHeader()->GetTargetCrc(), 0x1234U);
   ASSERT_EQ(idmap->GetHeader()->GetOverlayCrc(), 0x5678U);
   ASSERT_EQ(idmap->GetHeader()->GetFulfilledPolicies(), kIdmapRawDataPolicies);
@@ -204,7 +204,7 @@ TEST(IdmapTests, CreateIdmapHeaderFromApkAssets) {
 
   ASSERT_THAT(idmap->GetHeader(), NotNull());
   ASSERT_EQ(idmap->GetHeader()->GetMagic(), 0x504d4449U);
-  ASSERT_EQ(idmap->GetHeader()->GetVersion(), 0x09U);
+  ASSERT_EQ(idmap->GetHeader()->GetVersion(), 10);
   ASSERT_EQ(idmap->GetHeader()->GetTargetCrc(), android::idmap2::TestConstants::TARGET_CRC);
   ASSERT_EQ(idmap->GetHeader()->GetOverlayCrc(), android::idmap2::TestConstants::OVERLAY_CRC);
   ASSERT_EQ(idmap->GetHeader()->GetFulfilledPolicies(), PolicyFlags::PUBLIC);
diff --git a/cmds/idmap2/tests/RawPrintVisitorTests.cpp b/cmds/idmap2/tests/RawPrintVisitorTests.cpp
index 68164e26f352..7fae1c64f014 100644
--- a/cmds/idmap2/tests/RawPrintVisitorTests.cpp
+++ b/cmds/idmap2/tests/RawPrintVisitorTests.cpp
@@ -64,7 +64,7 @@ TEST(RawPrintVisitorTests, CreateRawPrintVisitor) {
   (*idmap)->accept(&visitor);
 
   ASSERT_CONTAINS_REGEX(ADDRESS "504d4449  magic\n", stream.str());
-  ASSERT_CONTAINS_REGEX(ADDRESS "00000009  version\n", stream.str());
+  ASSERT_CONTAINS_REGEX(ADDRESS "0000000a  version\n", stream.str());
   ASSERT_CONTAINS_REGEX(
       StringPrintf(ADDRESS "%s  target crc\n", android::idmap2::TestConstants::TARGET_CRC_STRING),
       stream.str());
@@ -113,7 +113,7 @@ TEST(RawPrintVisitorTests, CreateRawPrintVisitorWithoutAccessToApks) {
   (*idmap)->accept(&visitor);
 
   ASSERT_CONTAINS_REGEX(ADDRESS "504d4449  magic\n", stream.str());
-  ASSERT_CONTAINS_REGEX(ADDRESS "00000009  version\n", stream.str());
+  ASSERT_CONTAINS_REGEX(ADDRESS "0000000a  version\n", stream.str());
   ASSERT_CONTAINS_REGEX(ADDRESS "00001234  target crc\n", stream.str());
   ASSERT_CONTAINS_REGEX(ADDRESS "00005678  overlay crc\n", stream.str());
   ASSERT_CONTAINS_REGEX(ADDRESS "00000011  fulfilled policies: public|signature\n", stream.str());
diff --git a/cmds/idmap2/tests/TestHelpers.h b/cmds/idmap2/tests/TestHelpers.h
index bf01c32c4c86..2b4ebd1ae800 100644
--- a/cmds/idmap2/tests/TestHelpers.h
+++ b/cmds/idmap2/tests/TestHelpers.h
@@ -34,7 +34,7 @@ const unsigned char kIdmapRawData[] = {
     0x49, 0x44, 0x4d, 0x50,
 
     // 0x4: version
-    0x09, 0x00, 0x00, 0x00,
+    0x0a, 0x00, 0x00, 0x00,
 
     // 0x8: target crc
     0x34, 0x12, 0x00, 0x00,
@@ -95,19 +95,15 @@ const unsigned char kIdmapRawData[] = {
     // TARGET ENTRIES
     // 0x6c: target id (0x7f020000)
     0x00, 0x00, 0x02, 0x7f,
-
-    // 0x70: overlay_id (0x7f020000)
-    0x00, 0x00, 0x02, 0x7f,
-
-    // 0x74: target id (0x7f030000)
-    0x00, 0x00, 0x03, 0x7f,
-
-    // 0x78: overlay_id (0x7f030000)
+    // 0x70: target id (0x7f030000)
     0x00, 0x00, 0x03, 0x7f,
-
-    // 0x7c: target id (0x7f030002)
+    // 0x74: target id (0x7f030002)
     0x02, 0x00, 0x03, 0x7f,
 
+    // 0x78: overlay_id (0x7f020000)
+    0x00, 0x00, 0x02, 0x7f,
+    // 0x7c: overlay_id (0x7f030000)
+    0x00, 0x00, 0x03, 0x7f,
     // 0x80: overlay_id (0x7f030001)
     0x01, 0x00, 0x03, 0x7f,
 
@@ -178,16 +174,20 @@ const unsigned char kIdmapRawData[] = {
     // 0xe1: padding
     0x00, 0x00, 0x00,
 
-
     // OVERLAY ENTRIES
-    // 0xe4: 0x7f020000 -> 0x7f020000
-    0x00, 0x00, 0x02, 0x7f, 0x00, 0x00, 0x02, 0x7f,
-
-    // 0xec: 0x7f030000 -> 0x7f030000
-    0x00, 0x00, 0x03, 0x7f, 0x00, 0x00, 0x03, 0x7f,
+    // 0xe4: 0x7f020000 -> ...
+    0x00, 0x00, 0x02, 0x7f,
+    // 0xe8: 0x7f030000 -> ...
+    0x00, 0x00, 0x03, 0x7f,
+    // 0xec: 0x7f030001 -> ...
+    0x01, 0x00, 0x03, 0x7f,
 
-    // 0xf4: 0x7f030001 -> 0x7f030002
-    0x01, 0x00, 0x03, 0x7f, 0x02, 0x00, 0x03, 0x7f,
+    // 0xf0: ... -> 0x7f020000
+    0x00, 0x00, 0x02, 0x7f,
+    // 0xf4: ... -> 0x7f030000
+    0x00, 0x00, 0x03, 0x7f,
+    // 0xf8: ... -> 0x7f030002
+    0x02, 0x00, 0x03, 0x7f,
 
     // 0xfc: string pool
     // string length,
diff --git a/libs/androidfw/Idmap.cpp b/libs/androidfw/Idmap.cpp
index f066e4620675..3ecd82b074a1 100644
--- a/libs/androidfw/Idmap.cpp
+++ b/libs/androidfw/Idmap.cpp
@@ -65,13 +65,7 @@ struct Idmap_data_header {
   uint32_t string_pool_index_offset;
 };
 
-struct Idmap_target_entry {
-  uint32_t target_id;
-  uint32_t overlay_id;
-};
-
 struct Idmap_target_entry_inline {
-  uint32_t target_id;
   uint32_t start_value_index;
   uint32_t value_count;
 };
@@ -81,10 +75,9 @@ struct Idmap_target_entry_inline_value {
   Res_value value;
 };
 
-struct Idmap_overlay_entry {
-  uint32_t overlay_id;
-  uint32_t target_id;
-};
+static constexpr uint32_t convert_dev_target_id(uint32_t dev_target_id) {
+  return (0x00FFFFFFU & dtohl(dev_target_id));
+}
 
 OverlayStringPool::OverlayStringPool(const LoadedIdmap* loaded_idmap)
     : data_header_(loaded_idmap->data_header_),
@@ -117,27 +110,29 @@ size_t OverlayStringPool::size() const {
 }
 
 OverlayDynamicRefTable::OverlayDynamicRefTable(const Idmap_data_header* data_header,
-                                               const Idmap_overlay_entry* entries,
+                                               Idmap_overlay_entries entries,
                                                uint8_t target_assigned_package_id)
     : data_header_(data_header),
       entries_(entries),
-      target_assigned_package_id_(target_assigned_package_id) {}
+      target_assigned_package_id_(target_assigned_package_id) {
+}
 
 status_t OverlayDynamicRefTable::lookupResourceId(uint32_t* resId) const {
-  const Idmap_overlay_entry* first_entry = entries_;
-  const Idmap_overlay_entry* end_entry = entries_ + dtohl(data_header_->overlay_entry_count);
-  auto entry = std::lower_bound(first_entry, end_entry, *resId,
-                                [](const Idmap_overlay_entry& e1, const uint32_t overlay_id) {
-    return dtohl(e1.overlay_id) < overlay_id;
-  });
-
-  if (entry == end_entry || dtohl(entry->overlay_id) != *resId) {
+  const auto count = dtohl(data_header_->overlay_entry_count);
+  const auto overlay_it_end = entries_.overlay_id + count;
+  const auto entry_it = std::lower_bound(entries_.overlay_id, overlay_it_end, *resId,
+                                         [](uint32_t dev_overlay_id, uint32_t overlay_id) {
+                                           return dtohl(dev_overlay_id) < overlay_id;
+                                         });
+
+  if (entry_it == overlay_it_end || dtohl(*entry_it) != *resId) {
     // A mapping for the target resource id could not be found.
     return DynamicRefTable::lookupResourceId(resId);
   }
 
-  *resId = (0x00FFFFFFU & dtohl(entry->target_id))
-      | (((uint32_t) target_assigned_package_id_) << 24U);
+  const auto index = entry_it - entries_.overlay_id;
+  *resId = convert_dev_target_id(entries_.target_id[index]) |
+           (((uint32_t)target_assigned_package_id_) << 24U);
   return NO_ERROR;
 }
 
@@ -145,12 +140,10 @@ status_t OverlayDynamicRefTable::lookupResourceIdNoRewrite(uint32_t* resId) cons
   return DynamicRefTable::lookupResourceId(resId);
 }
 
-IdmapResMap::IdmapResMap(const Idmap_data_header* data_header,
-                         const Idmap_target_entry* entries,
-                         const Idmap_target_entry_inline* inline_entries,
+IdmapResMap::IdmapResMap(const Idmap_data_header* data_header, Idmap_target_entries entries,
+                         Idmap_target_inline_entries inline_entries,
                          const Idmap_target_entry_inline_value* inline_entry_values,
-                         const ConfigDescription* configs,
-                         uint8_t target_assigned_package_id,
+                         const ConfigDescription* configs, uint8_t target_assigned_package_id,
                          const OverlayDynamicRefTable* overlay_ref_table)
     : data_header_(data_header),
       entries_(entries),
@@ -158,7 +151,8 @@ IdmapResMap::IdmapResMap(const Idmap_data_header* data_header,
       inline_entry_values_(inline_entry_values),
       configurations_(configs),
       target_assigned_package_id_(target_assigned_package_id),
-      overlay_ref_table_(overlay_ref_table) { }
+      overlay_ref_table_(overlay_ref_table) {
+}
 
 IdmapResMap::Result IdmapResMap::Lookup(uint32_t target_res_id) const {
   if ((target_res_id >> 24U) != target_assigned_package_id_) {
@@ -171,15 +165,15 @@ IdmapResMap::Result IdmapResMap::Lookup(uint32_t target_res_id) const {
   target_res_id &= 0x00FFFFFFU;
 
   // Check if the target resource is mapped to an overlay resource.
-  auto first_entry = entries_;
-  auto end_entry = entries_ + dtohl(data_header_->target_entry_count);
-  auto entry = std::lower_bound(first_entry, end_entry, target_res_id,
-                                [](const Idmap_target_entry& e, const uint32_t target_id) {
-    return (0x00FFFFFFU & dtohl(e.target_id)) < target_id;
-  });
-
-  if (entry != end_entry && (0x00FFFFFFU & dtohl(entry->target_id)) == target_res_id) {
-    uint32_t overlay_resource_id = dtohl(entry->overlay_id);
+  const auto target_end = entries_.target_id + dtohl(data_header_->target_entry_count);
+  auto target_it = std::lower_bound(entries_.target_id, target_end, target_res_id,
+                                    [](uint32_t dev_target_id, uint32_t target_id) {
+                                      return convert_dev_target_id(dev_target_id) < target_id;
+                                    });
+
+  if (target_it != target_end && convert_dev_target_id(*target_it) == target_res_id) {
+    const auto index = target_it - entries_.target_id;
+    uint32_t overlay_resource_id = dtohl(entries_.overlay_id[index]);
     // Lookup the resource without rewriting the overlay resource id back to the target resource id
     // being looked up.
     overlay_ref_table_->lookupResourceIdNoRewrite(&overlay_resource_id);
@@ -187,20 +181,22 @@ IdmapResMap::Result IdmapResMap::Lookup(uint32_t target_res_id) const {
   }
 
   // Check if the target resources is mapped to an inline table entry.
-  auto first_inline_entry = inline_entries_;
-  auto end_inline_entry = inline_entries_ + dtohl(data_header_->target_inline_entry_count);
-  auto inline_entry = std::lower_bound(first_inline_entry, end_inline_entry, target_res_id,
-                                       [](const Idmap_target_entry_inline& e,
-                                          const uint32_t target_id) {
-    return (0x00FFFFFFU & dtohl(e.target_id)) < target_id;
-  });
-
-  if (inline_entry != end_inline_entry &&
-      (0x00FFFFFFU & dtohl(inline_entry->target_id)) == target_res_id) {
+  const auto inline_entry_target_end =
+      inline_entries_.target_id + dtohl(data_header_->target_inline_entry_count);
+  const auto inline_entry_target_it =
+      std::lower_bound(inline_entries_.target_id, inline_entry_target_end, target_res_id,
+                       [](uint32_t dev_target_id, uint32_t target_id) {
+                         return convert_dev_target_id(dev_target_id) < target_id;
+                       });
+
+  if (inline_entry_target_it != inline_entry_target_end &&
+      convert_dev_target_id(*inline_entry_target_it) == target_res_id) {
+    const auto index = inline_entry_target_it - inline_entries_.target_id;
     std::map<ConfigDescription, Res_value> values_map;
-    for (int i = 0; i < inline_entry->value_count; i++) {
-      const auto& value = inline_entry_values_[inline_entry->start_value_index + i];
-      const auto& config = configurations_[value.config_index];
+    const auto& inline_entry = inline_entries_.entry[index];
+    for (int i = 0; i < dtohl(inline_entry.value_count); i++) {
+      const auto& value = inline_entry_values_[dtohl(inline_entry.start_value_index) + i];
+      const auto& config = configurations_[dtohl(value.config_index)];
       values_map[config] = value.value;
     }
     return Result(std::move(values_map));
@@ -210,15 +206,15 @@ IdmapResMap::Result IdmapResMap::Lookup(uint32_t target_res_id) const {
 
 namespace {
 template <typename T>
-const T* ReadType(const uint8_t** in_out_data_ptr, size_t* in_out_size, const std::string& label,
+const T* ReadType(const uint8_t** in_out_data_ptr, size_t* in_out_size, const char* label,
                   size_t count = 1) {
   if (!util::IsFourByteAligned(*in_out_data_ptr)) {
-    LOG(ERROR) << "Idmap " << label << " is not word aligned.";
+    LOG(ERROR) << "Idmap " << label << " in " << __func__ << " is not word aligned.";
     return {};
   }
   if ((*in_out_size / sizeof(T)) < count) {
-    LOG(ERROR) << "Idmap too small for the number of " << label << " entries ("
-               << count << ").";
+    LOG(ERROR) << "Idmap too small for the number of " << label << " in " << __func__
+               << " entries (" << count << ").";
     return nullptr;
   }
   auto data_ptr = *in_out_data_ptr;
@@ -229,8 +225,8 @@ const T* ReadType(const uint8_t** in_out_data_ptr, size_t* in_out_size, const st
 }
 
 std::optional<std::string_view> ReadString(const uint8_t** in_out_data_ptr, size_t* in_out_size,
-                                           const std::string& label) {
-  const auto* len = ReadType<uint32_t>(in_out_data_ptr, in_out_size, label + " length");
+                                           const char* label) {
+  const auto* len = ReadType<uint32_t>(in_out_data_ptr, in_out_size, label);
   if (len == nullptr) {
     return {};
   }
@@ -242,7 +238,7 @@ std::optional<std::string_view> ReadString(const uint8_t** in_out_data_ptr, size
   const uint32_t padding_size = (4U - ((size_t)*in_out_data_ptr & 0x3U)) % 4U;
   for (uint32_t i = 0; i < padding_size; i++) {
     if (**in_out_data_ptr != 0) {
-      LOG(ERROR) << " Idmap padding of " << label << " is non-zero.";
+      LOG(ERROR) << " Idmap padding of " << label << " in " << __func__ << " is non-zero.";
       return {};
     }
     *in_out_data_ptr += sizeof(uint8_t);
@@ -258,12 +254,10 @@ std::optional<std::string_view> ReadString(const uint8_t** in_out_data_ptr, size
 #endif
 
 LoadedIdmap::LoadedIdmap(const std::string& idmap_path, const Idmap_header* header,
-                         const Idmap_data_header* data_header,
-                         const Idmap_target_entry* target_entries,
-                         const Idmap_target_entry_inline* target_inline_entries,
+                         const Idmap_data_header* data_header, Idmap_target_entries target_entries,
+                         Idmap_target_inline_entries target_inline_entries,
                          const Idmap_target_entry_inline_value* inline_entry_values,
-                         const ConfigDescription* configs,
-                         const Idmap_overlay_entry* overlay_entries,
+                         const ConfigDescription* configs, Idmap_overlay_entries overlay_entries,
                          std::unique_ptr<ResStringPool>&& string_pool,
                          std::string_view overlay_apk_path, std::string_view target_apk_path)
     : header_(header),
@@ -274,10 +268,12 @@ LoadedIdmap::LoadedIdmap(const std::string& idmap_path, const Idmap_header* head
       configurations_(configs),
       overlay_entries_(overlay_entries),
       string_pool_(std::move(string_pool)),
-      idmap_fd_(android::base::utf8::open(idmap_path.c_str(), O_RDONLY|O_CLOEXEC|O_BINARY|O_PATH)),
+      idmap_fd_(
+          android::base::utf8::open(idmap_path.c_str(), O_RDONLY | O_CLOEXEC | O_BINARY | O_PATH)),
       overlay_apk_path_(overlay_apk_path),
       target_apk_path_(target_apk_path),
-      idmap_last_mod_time_(getFileModDate(idmap_fd_.get())) {}
+      idmap_last_mod_time_(getFileModDate(idmap_fd_.get())) {
+}
 
 std::unique_ptr<LoadedIdmap> LoadedIdmap::Load(StringPiece idmap_path, StringPiece idmap_data) {
   ATRACE_CALL();
@@ -319,14 +315,21 @@ std::unique_ptr<LoadedIdmap> LoadedIdmap::Load(StringPiece idmap_path, StringPie
   if (data_header == nullptr) {
     return {};
   }
-  auto target_entries = ReadType<Idmap_target_entry>(&data_ptr, &data_size, "target",
-                                                     dtohl(data_header->target_entry_count));
-  if (target_entries == nullptr) {
+  Idmap_target_entries target_entries{
+      .target_id = ReadType<uint32_t>(&data_ptr, &data_size, "entries.target_id",
+                                      dtohl(data_header->target_entry_count)),
+      .overlay_id = ReadType<uint32_t>(&data_ptr, &data_size, "entries.overlay_id",
+                                       dtohl(data_header->target_entry_count)),
+  };
+  if (!target_entries.target_id || !target_entries.overlay_id) {
     return {};
   }
-  auto target_inline_entries = ReadType<Idmap_target_entry_inline>(
-      &data_ptr, &data_size, "target inline", dtohl(data_header->target_inline_entry_count));
-  if (target_inline_entries == nullptr) {
+  Idmap_target_inline_entries target_inline_entries{
+      .target_id = ReadType<uint32_t>(&data_ptr, &data_size, "target inline.target_id",
+                                      dtohl(data_header->target_inline_entry_count)),
+      .entry = ReadType<Idmap_target_entry_inline>(&data_ptr, &data_size, "target inline.entry",
+                                                   dtohl(data_header->target_inline_entry_count))};
+  if (!target_inline_entries.target_id || !target_inline_entries.entry) {
     return {};
   }
 
@@ -344,9 +347,13 @@ std::unique_ptr<LoadedIdmap> LoadedIdmap::Load(StringPiece idmap_path, StringPie
     return {};
   }
 
-  auto overlay_entries = ReadType<Idmap_overlay_entry>(&data_ptr, &data_size, "target inline",
-                                                       dtohl(data_header->overlay_entry_count));
-  if (overlay_entries == nullptr) {
+  Idmap_overlay_entries overlay_entries{
+      .overlay_id = ReadType<uint32_t>(&data_ptr, &data_size, "overlay entries.overlay_id",
+                                       dtohl(data_header->overlay_entry_count)),
+      .target_id = ReadType<uint32_t>(&data_ptr, &data_size, "overlay entries.target_id",
+                                      dtohl(data_header->overlay_entry_count)),
+  };
+  if (!overlay_entries.overlay_id || !overlay_entries.target_id) {
     return {};
   }
   std::optional<std::string_view> string_pool = ReadString(&data_ptr, &data_size, "string pool");
diff --git a/libs/androidfw/include/androidfw/Idmap.h b/libs/androidfw/include/androidfw/Idmap.h
index 64b1f0c6ed03..e213fbd22ab0 100644
--- a/libs/androidfw/include/androidfw/Idmap.h
+++ b/libs/androidfw/include/androidfw/Idmap.h
@@ -40,6 +40,19 @@ struct Idmap_target_entry_inline;
 struct Idmap_target_entry_inline_value;
 struct Idmap_overlay_entry;
 
+struct Idmap_target_entries {
+  const uint32_t* target_id = nullptr;
+  const uint32_t* overlay_id = nullptr;
+};
+struct Idmap_target_inline_entries {
+  const uint32_t* target_id = nullptr;
+  const Idmap_target_entry_inline* entry = nullptr;
+};
+struct Idmap_overlay_entries {
+  const uint32_t* overlay_id = nullptr;
+  const uint32_t* target_id = nullptr;
+};
+
 // A string pool for overlay apk assets. The string pool holds the strings of the overlay resources
 // table and additionally allows for loading strings from the idmap string pool. The idmap string
 // pool strings are offset after the end of the overlay resource table string pool entries so
@@ -67,7 +80,7 @@ class OverlayDynamicRefTable : public DynamicRefTable {
 
  private:
   explicit OverlayDynamicRefTable(const Idmap_data_header* data_header,
-                                  const Idmap_overlay_entry* entries,
+                                  Idmap_overlay_entries entries,
                                   uint8_t target_assigned_package_id);
 
   // Rewrites a compile-time overlay resource id to the runtime resource id of corresponding target
@@ -75,8 +88,8 @@ class OverlayDynamicRefTable : public DynamicRefTable {
   status_t lookupResourceIdNoRewrite(uint32_t* resId) const;
 
   const Idmap_data_header* data_header_;
-  const Idmap_overlay_entry* entries_;
-  const int8_t target_assigned_package_id_;
+  Idmap_overlay_entries entries_;
+  uint8_t target_assigned_package_id_;
 
   friend LoadedIdmap;
   friend IdmapResMap;
@@ -131,17 +144,15 @@ class IdmapResMap {
   }
 
  private:
-  explicit IdmapResMap(const Idmap_data_header* data_header,
-                       const Idmap_target_entry* entries,
-                       const Idmap_target_entry_inline* inline_entries,
+  explicit IdmapResMap(const Idmap_data_header* data_header, Idmap_target_entries entries,
+                       Idmap_target_inline_entries inline_entries,
                        const Idmap_target_entry_inline_value* inline_entry_values,
-                       const ConfigDescription* configs,
-                       uint8_t target_assigned_package_id,
+                       const ConfigDescription* configs, uint8_t target_assigned_package_id,
                        const OverlayDynamicRefTable* overlay_ref_table);
 
   const Idmap_data_header* data_header_;
-  const Idmap_target_entry* entries_;
-  const Idmap_target_entry_inline* inline_entries_;
+  Idmap_target_entries entries_;
+  Idmap_target_inline_entries inline_entries_;
   const Idmap_target_entry_inline_value* inline_entry_values_;
   const ConfigDescription* configurations_;
   const uint8_t target_assigned_package_id_;
@@ -192,11 +203,11 @@ class LoadedIdmap {
 
   const Idmap_header* header_;
   const Idmap_data_header* data_header_;
-  const Idmap_target_entry* target_entries_;
-  const Idmap_target_entry_inline* target_inline_entries_;
+  Idmap_target_entries target_entries_;
+  Idmap_target_inline_entries target_inline_entries_;
   const Idmap_target_entry_inline_value* inline_entry_values_;
   const ConfigDescription* configurations_;
-  const Idmap_overlay_entry* overlay_entries_;
+  const Idmap_overlay_entries overlay_entries_;
   const std::unique_ptr<ResStringPool> string_pool_;
 
   android::base::unique_fd idmap_fd_;
@@ -207,17 +218,13 @@ class LoadedIdmap {
  private:
   DISALLOW_COPY_AND_ASSIGN(LoadedIdmap);
 
-  explicit LoadedIdmap(const std::string& idmap_path,
-                       const Idmap_header* header,
-                       const Idmap_data_header* data_header,
-                       const Idmap_target_entry* target_entries,
-                       const Idmap_target_entry_inline* target_inline_entries,
+  explicit LoadedIdmap(const std::string& idmap_path, const Idmap_header* header,
+                       const Idmap_data_header* data_header, Idmap_target_entries target_entries,
+                       Idmap_target_inline_entries target_inline_entries,
                        const Idmap_target_entry_inline_value* inline_entry_values_,
-                       const ConfigDescription* configs,
-                       const Idmap_overlay_entry* overlay_entries,
+                       const ConfigDescription* configs, Idmap_overlay_entries overlay_entries,
                        std::unique_ptr<ResStringPool>&& string_pool,
-                       std::string_view overlay_apk_path,
-                       std::string_view target_apk_path);
+                       std::string_view overlay_apk_path, std::string_view target_apk_path);
 
   friend OverlayStringPool;
 };
diff --git a/libs/androidfw/include/androidfw/ResourceTypes.h b/libs/androidfw/include/androidfw/ResourceTypes.h
index c2648909386c..e330410ed1a0 100644
--- a/libs/androidfw/include/androidfw/ResourceTypes.h
+++ b/libs/androidfw/include/androidfw/ResourceTypes.h
@@ -48,7 +48,7 @@
 namespace android {
 
 constexpr const uint32_t kIdmapMagic = 0x504D4449u;
-constexpr const uint32_t kIdmapCurrentVersion = 0x00000009u;
+constexpr const uint32_t kIdmapCurrentVersion = 0x0000000Au;
 
 // This must never change.
 constexpr const uint32_t kFabricatedOverlayMagic = 0x4f525246; // FRRO (big endian)
diff --git a/libs/androidfw/tests/data/overlay/overlay.idmap b/libs/androidfw/tests/data/overlay/overlay.idmap
index 8e847e81aa31..7e4b261cf109 100644
--- a/libs/androidfw/tests/data/overlay/overlay.idmap
+++ b/libs/androidfw/tests/data/overlay/overlay.idmap