From c8f71aa67ea599cb80205496cb67e9e7a121299c Mon Sep 17 00:00:00 2001
From: Adam Lesinski <adamlesinski@google.com>
Date: Wed, 8 Feb 2017 07:03:50 -0800
Subject: Add ResTable_sparseTypeEntry support

Benchmarks on bullhead-userdebug show that there is a negligent
performance impact when using sparse entries on a 30% loaded
sparse type of 1000 resources.

Benchmark                                             Time           CPU Iterations
-----------------------------------------------------------------------------------
BM_SparseEntryGetResourceSparseLarge                255 ns        254 ns    2751408
BM_SparseEntryGetResourceNotSparseLarge             254 ns        254 ns    2756534

Bug: 27381711
Test: make libandroidfw_tests aapt2_tests
Change-Id: I051ea22f2f6b2bc3696e446adc9e2a34be18009f
---
 libs/androidfw/include/androidfw/ResourceTypes.h | 42 +++++++++++++++++++++---
 libs/androidfw/include/androidfw/TypeWrappers.h  |  8 +++--
 2 files changed, 43 insertions(+), 7 deletions(-)

(limited to 'libs/androidfw/include')

diff --git a/libs/androidfw/include/androidfw/ResourceTypes.h b/libs/androidfw/include/androidfw/ResourceTypes.h
index 04a5d958c614..5c5c9e6b4f55 100644
--- a/libs/androidfw/include/androidfw/ResourceTypes.h
+++ b/libs/androidfw/include/androidfw/ResourceTypes.h
@@ -1339,12 +1339,21 @@ struct ResTable_typeSpec
 
 /**
  * A collection of resource entries for a particular resource data
- * type. Followed by an array of uint32_t defining the resource
+ * type.
+ *
+ * If the flag FLAG_SPARSE is not set in `flags`, then this struct is
+ * followed by an array of uint32_t defining the resource
  * values, corresponding to the array of type strings in the
  * ResTable_package::typeStrings string block. Each of these hold an
  * index from entriesStart; a value of NO_ENTRY means that entry is
  * not defined.
  *
+ * If the flag FLAG_SPARSE is set in `flags`, then this struct is followed
+ * by an array of ResTable_sparseTypeEntry defining only the entries that
+ * have values for this type. Each entry is sorted by their entry ID such
+ * that a binary search can be performed over the entries. The ID and offset
+ * are encoded in a uint32_t. See ResTabe_sparseTypeEntry.
+ *
  * There may be multiple of these chunks for a particular resource type,
  * supply different configuration variations for the resource values of
  * that type.
@@ -1365,10 +1374,17 @@ struct ResTable_type
     // resource identifier).  0 is invalid.
     uint8_t id;
     
+    enum {
+        // If set, the entry is sparse, and encodes both the entry ID and offset into each entry,
+        // and a binary search is used to find the key. Only available on platforms >= O.
+        // Mark any types that use this with a v26 qualifier to prevent runtime issues on older
+        // platforms.
+        FLAG_SPARSE = 0x01,
+    };
+    uint8_t flags;
+
     // Must be 0.
-    uint8_t res0;
-    // Must be 0.
-    uint16_t res1;
+    uint16_t reserved;
     
     // Number of uint32_t entry indices that follow.
     uint32_t entryCount;
@@ -1380,6 +1396,24 @@ struct ResTable_type
     ResTable_config config;
 };
 
+/**
+ * An entry in a ResTable_type with the flag `FLAG_SPARSE` set.
+ */
+union ResTable_sparseTypeEntry {
+    // Holds the raw uint32_t encoded value. Do not read this.
+    uint32_t entry;
+    struct {
+        // The index of the entry.
+        uint16_t idx;
+
+        // The offset from ResTable_type::entriesStart, divided by 4.
+        uint16_t offset;
+    };
+};
+
+static_assert(sizeof(ResTable_sparseTypeEntry) == sizeof(uint32_t),
+        "ResTable_sparseTypeEntry must be 4 bytes in size");
+
 /**
  * This is the beginning of information about an entry in the resource
  * table.  It holds the reference to the name of this entry, and is
diff --git a/libs/androidfw/include/androidfw/TypeWrappers.h b/libs/androidfw/include/androidfw/TypeWrappers.h
index f1daf3365c28..5cfe54e5759d 100644
--- a/libs/androidfw/include/androidfw/TypeWrappers.h
+++ b/libs/androidfw/include/androidfw/TypeWrappers.h
@@ -23,8 +23,7 @@
 namespace android {
 
 struct TypeVariant {
-    TypeVariant(const ResTable_type* data)
-        : data(data) {}
+    TypeVariant(const ResTable_type* data);
 
     class iterator {
     public:
@@ -72,10 +71,13 @@ struct TypeVariant {
     }
 
     iterator endEntries() const {
-        return iterator(this, dtohl(data->entryCount));
+        return iterator(this, mLength);
     }
 
     const ResTable_type* data;
+
+private:
+    size_t mLength;
 };
 
 } // namespace android
-- 
cgit v1.2.3-59-g8ed1b