Idmap format changes for bidirectional lookup
This change modifies the idmap file format to allow for target resources
to map to arbitrary type/value combinations and to allow overlay
resources to be mapped back to target resource ids so references to
overlay resources can appear as references to target resources at
runtime.
The mappings of target resources to overlay resources and vice-versa are
both encoded as sparse arrays. Instead of looking up a resource by
indexing into an array that maps to the overlay resource id, the runtime
will binary search over the sparse array to find the type and value that
overlays the target resource.
Bug: 135943783
Test: idmap2_tests
Change-Id: I5d5344cdb7fe35f4f2e8d6781016299dea5d1e20
diff --git a/cmds/idmap2/libidmap2/Idmap.cpp b/cmds/idmap2/libidmap2/Idmap.cpp
index 389ade5..5cb91d7 100644
--- a/cmds/idmap2/libidmap2/Idmap.cpp
+++ b/cmds/idmap2/libidmap2/Idmap.cpp
@@ -42,30 +42,10 @@
namespace {
-class MatchingResources {
- public:
- void Add(ResourceId target_resid, ResourceId overlay_resid) {
- TypeId target_typeid = EXTRACT_TYPE(target_resid);
- if (map_.find(target_typeid) == map_.end()) {
- map_.emplace(target_typeid, std::set<std::pair<ResourceId, ResourceId>>());
- }
- map_[target_typeid].insert(std::make_pair(target_resid, overlay_resid));
- }
-
- inline const std::map<TypeId, std::set<std::pair<ResourceId, ResourceId>>>& WARN_UNUSED
- Map() const {
- return map_;
- }
-
- private:
- // target type id -> set { pair { overlay entry id, overlay entry id } }
- std::map<TypeId, std::set<std::pair<ResourceId, ResourceId>>> map_;
-};
-
-bool WARN_UNUSED Read16(std::istream& stream, uint16_t* out) {
- uint16_t value;
- if (stream.read(reinterpret_cast<char*>(&value), sizeof(uint16_t))) {
- *out = dtohl(value);
+bool WARN_UNUSED Read8(std::istream& stream, uint8_t* out) {
+ uint8_t value;
+ if (stream.read(reinterpret_cast<char*>(&value), sizeof(uint8_t))) {
+ *out = value;
return true;
}
return false;
@@ -80,6 +60,15 @@
return false;
}
+bool WARN_UNUSED ReadBuffer(std::istream& stream, std::unique_ptr<uint8_t[]>* out, size_t length) {
+ auto buffer = std::unique_ptr<uint8_t[]>(new uint8_t[length]);
+ if (stream.read(reinterpret_cast<char*>(buffer.get()), length)) {
+ *out = std::move(buffer);
+ return true;
+ }
+ return false;
+}
+
// a string is encoded as a kIdmapStringLength char array; the array is always null-terminated
bool WARN_UNUSED ReadString(std::istream& stream, char out[kIdmapStringLength]) {
char buf[kIdmapStringLength];
@@ -162,51 +151,48 @@
std::unique_ptr<const IdmapData::Header> IdmapData::Header::FromBinaryStream(std::istream& stream) {
std::unique_ptr<IdmapData::Header> idmap_data_header(new IdmapData::Header());
- uint16_t target_package_id16;
- if (!Read16(stream, &target_package_id16) || !Read16(stream, &idmap_data_header->type_count_)) {
+ if (!Read8(stream, &idmap_data_header->target_package_id_) ||
+ !Read8(stream, &idmap_data_header->overlay_package_id_) ||
+ !Read32(stream, &idmap_data_header->target_entry_count) ||
+ !Read32(stream, &idmap_data_header->overlay_entry_count) ||
+ !Read32(stream, &idmap_data_header->string_pool_index_offset) ||
+ !Read32(stream, &idmap_data_header->string_pool_len)) {
return nullptr;
}
- idmap_data_header->target_package_id_ = target_package_id16;
return std::move(idmap_data_header);
}
-std::unique_ptr<const IdmapData::TypeEntry> IdmapData::TypeEntry::FromBinaryStream(
- std::istream& stream) {
- std::unique_ptr<IdmapData::TypeEntry> data(new IdmapData::TypeEntry());
- uint16_t target_type16;
- uint16_t overlay_type16;
- uint16_t entry_count;
- if (!Read16(stream, &target_type16) || !Read16(stream, &overlay_type16) ||
- !Read16(stream, &entry_count) || !Read16(stream, &data->entry_offset_)) {
- return nullptr;
- }
- data->target_type_id_ = target_type16;
- data->overlay_type_id_ = overlay_type16;
- for (uint16_t i = 0; i < entry_count; i++) {
- ResourceId resid;
- if (!Read32(stream, &resid)) {
- return nullptr;
- }
- data->entries_.push_back(resid);
- }
-
- return std::move(data);
-}
-
std::unique_ptr<const IdmapData> IdmapData::FromBinaryStream(std::istream& stream) {
std::unique_ptr<IdmapData> data(new IdmapData());
data->header_ = IdmapData::Header::FromBinaryStream(stream);
if (!data->header_) {
return nullptr;
}
- for (size_t type_count = 0; type_count < data->header_->GetTypeCount(); type_count++) {
- std::unique_ptr<const TypeEntry> type = IdmapData::TypeEntry::FromBinaryStream(stream);
- if (!type) {
+ // Read the mapping of target resource id to overlay resource value.
+ for (size_t i = 0; i < data->header_->GetTargetEntryCount(); i++) {
+ TargetEntry target_entry{};
+ if (!Read32(stream, &target_entry.target_id) || !Read8(stream, &target_entry.data_type) ||
+ !Read32(stream, &target_entry.data_value)) {
return nullptr;
}
- data->type_entries_.push_back(std::move(type));
+ data->target_entries_.emplace_back(target_entry);
}
+
+ // Read the mapping of overlay resource id to target resource id.
+ 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)) {
+ return nullptr;
+ }
+ data->overlay_entries_.emplace_back(overlay_entry);
+ }
+
+ // Read raw string pool bytes.
+ if (!ReadBuffer(stream, &data->string_pool_, data->header_->string_pool_len)) {
+ return nullptr;
+ }
+
return std::move(data);
}
@@ -247,40 +233,28 @@
return Error("no resources were overlaid");
}
- MatchingResources matching_resources;
- for (const auto mapping : resource_mapping.GetTargetToOverlayMap()) {
- if (mapping.second.data_type != Res_value::TYPE_REFERENCE) {
- // The idmap format must change to support non-references.
- continue;
- }
-
- matching_resources.Add(mapping.first, mapping.second.data_value);
+ std::unique_ptr<IdmapData> data(new IdmapData());
+ for (const auto& mappings : resource_mapping.GetTargetToOverlayMap()) {
+ data->target_entries_.emplace_back(IdmapData::TargetEntry{
+ mappings.first, mappings.second.data_type, mappings.second.data_value});
}
- // encode idmap data
- std::unique_ptr<IdmapData> data(new IdmapData());
- const auto types_end = matching_resources.Map().cend();
- for (auto ti = matching_resources.Map().cbegin(); ti != types_end; ++ti) {
- auto ei = ti->second.cbegin();
- std::unique_ptr<IdmapData::TypeEntry> type(new IdmapData::TypeEntry());
- type->target_type_id_ = EXTRACT_TYPE(ei->first);
- type->overlay_type_id_ = EXTRACT_TYPE(ei->second);
- type->entry_offset_ = EXTRACT_ENTRY(ei->first);
- EntryId last_target_entry = kNoEntry;
- for (; ei != ti->second.cend(); ++ei) {
- if (last_target_entry != kNoEntry) {
- int count = EXTRACT_ENTRY(ei->first) - last_target_entry - 1;
- type->entries_.insert(type->entries_.end(), count, kNoEntry);
- }
- type->entries_.push_back(EXTRACT_ENTRY(ei->second));
- last_target_entry = EXTRACT_ENTRY(ei->first);
- }
- data->type_entries_.push_back(std::move(type));
+ for (const auto& mappings : resource_mapping.GetOverlayToTargetMap()) {
+ data->overlay_entries_.emplace_back(IdmapData::OverlayEntry{mappings.first, mappings.second});
}
std::unique_ptr<IdmapData::Header> data_header(new IdmapData::Header());
data_header->target_package_id_ = resource_mapping.GetTargetPackageId();
- data_header->type_count_ = data->type_entries_.size();
+ data_header->overlay_package_id_ = resource_mapping.GetOverlayPackageId();
+ data_header->target_entry_count = static_cast<uint32_t>(data->target_entries_.size());
+ data_header->overlay_entry_count = static_cast<uint32_t>(data->overlay_entries_.size());
+ data_header->string_pool_index_offset = resource_mapping.GetStringPoolOffset();
+
+ const auto string_pool_data = resource_mapping.GetStringPoolData();
+ data_header->string_pool_len = string_pool_data.second;
+ data->string_pool_ = std::unique_ptr<uint8_t[]>(new uint8_t[data_header->string_pool_len]);
+ memcpy(data->string_pool_.get(), string_pool_data.first, data_header->string_pool_len);
+
data->header_ = std::move(data_header);
return {std::move(data)};
}
@@ -367,25 +341,16 @@
v->visit(*this);
}
-void IdmapData::TypeEntry::accept(Visitor* v) const {
- assert(v != nullptr);
- v->visit(*this);
-}
-
void IdmapData::accept(Visitor* v) const {
assert(v != nullptr);
- v->visit(*this);
header_->accept(v);
- auto end = type_entries_.cend();
- for (auto iter = type_entries_.cbegin(); iter != end; ++iter) {
- (*iter)->accept(v);
- }
+ v->visit(*this);
}
void Idmap::accept(Visitor* v) const {
assert(v != nullptr);
- v->visit(*this);
header_->accept(v);
+ v->visit(*this);
auto end = data_.cend();
for (auto iter = data_.cbegin(); iter != end; ++iter) {
(*iter)->accept(v);