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
diff --git a/tools/aapt2/LoadedApk.cpp b/tools/aapt2/LoadedApk.cpp
index 3d7bd94..407550b 100644
--- a/tools/aapt2/LoadedApk.cpp
+++ b/tools/aapt2/LoadedApk.cpp
@@ -94,7 +94,9 @@
     // The resource table needs to be reserialized since it might have changed.
     if (path == "resources.arsc") {
       BigBuffer buffer = BigBuffer(1024);
-      TableFlattener flattener(&buffer);
+      // TODO(adamlesinski): How to determine if there were sparse entries (and if to encode
+      // with sparse entries) b/35389232.
+      TableFlattener flattener({}, &buffer);
       if (!flattener.Consume(context, table_.get())) {
         return false;
       }
diff --git a/tools/aapt2/SdkConstants.h b/tools/aapt2/SdkConstants.h
index 98ba94b..c2ee252 100644
--- a/tools/aapt2/SdkConstants.h
+++ b/tools/aapt2/SdkConstants.h
@@ -25,7 +25,7 @@
 
 namespace aapt {
 
-enum {
+enum : int {
   SDK_CUPCAKE = 3,
   SDK_DONUT = 4,
   SDK_ECLAIR = 5,
@@ -49,7 +49,7 @@
   SDK_MARSHMALLOW = 23,
   SDK_NOUGAT = 24,
   SDK_NOUGAT_MR1 = 25,
-  SDK_O = 26, // STOPSHIP Replace with real version
+  SDK_O = 26,  // STOPSHIP Replace with real version
 };
 
 size_t FindAttributeSdkLevel(const ResourceId& id);
diff --git a/tools/aapt2/flatten/TableFlattener.cpp b/tools/aapt2/flatten/TableFlattener.cpp
index 19d030e..697b07f 100644
--- a/tools/aapt2/flatten/TableFlattener.cpp
+++ b/tools/aapt2/flatten/TableFlattener.cpp
@@ -26,6 +26,7 @@
 
 #include "ResourceTable.h"
 #include "ResourceValues.h"
+#include "SdkConstants.h"
 #include "ValueVisitor.h"
 #include "flatten/ChunkWriter.h"
 #include "flatten/ResourceTypeExtensions.h"
@@ -216,8 +217,11 @@
 
 class PackageFlattener {
  public:
-  PackageFlattener(IDiagnostics* diag, ResourceTablePackage* package)
-      : diag_(diag), package_(package) {}
+  PackageFlattener(IAaptContext* context, ResourceTablePackage* package, bool use_sparse_entries)
+      : context_(context),
+        diag_(context->GetDiagnostics()),
+        package_(package),
+        use_sparse_entries_(use_sparse_entries) {}
 
   bool FlattenPackage(BigBuffer* buffer) {
     ChunkWriter pkg_writer(buffer);
@@ -298,9 +302,12 @@
     return true;
   }
 
-  bool FlattenConfig(const ResourceTableType* type,
-                     const ConfigDescription& config,
-                     std::vector<FlatEntry>* entries, BigBuffer* buffer) {
+  bool FlattenConfig(const ResourceTableType* type, const ConfigDescription& config,
+                     const size_t num_total_entries, std::vector<FlatEntry>* entries,
+                     BigBuffer* buffer) {
+    CHECK(num_total_entries != 0);
+    CHECK(num_total_entries <= std::numeric_limits<uint16_t>::max());
+
     ChunkWriter type_writer(buffer);
     ResTable_type* type_header =
         type_writer.StartChunk<ResTable_type>(RES_TABLE_TYPE_TYPE);
@@ -308,39 +315,60 @@
     type_header->config = config;
     type_header->config.swapHtoD();
 
-    auto max_accum = [](uint32_t max,
-                        const std::unique_ptr<ResourceEntry>& a) -> uint32_t {
-      return std::max(max, (uint32_t)a->id.value());
-    };
+    std::vector<uint32_t> offsets;
+    offsets.resize(num_total_entries, 0xffffffffu);
 
-    // Find the largest entry ID. That is how many entries we will have.
-    const uint32_t entry_count =
-        std::accumulate(type->entries.begin(), type->entries.end(), 0,
-                        max_accum) +
-        1;
-
-    type_header->entryCount = util::HostToDevice32(entry_count);
-    uint32_t* indices = type_writer.NextBlock<uint32_t>(entry_count);
-
-    CHECK((size_t)entry_count <= std::numeric_limits<uint16_t>::max());
-    memset(indices, 0xff, entry_count * sizeof(uint32_t));
-
-    type_header->entriesStart = util::HostToDevice32(type_writer.size());
-
-    const size_t entry_start = type_writer.buffer()->size();
+    BigBuffer values_buffer(512);
     for (FlatEntry& flat_entry : *entries) {
-      CHECK(flat_entry.entry->id.value() < entry_count);
-      indices[flat_entry.entry->id.value()] =
-          util::HostToDevice32(type_writer.buffer()->size() - entry_start);
-      if (!FlattenValue(&flat_entry, type_writer.buffer())) {
+      CHECK(static_cast<size_t>(flat_entry.entry->id.value()) < num_total_entries);
+      offsets[flat_entry.entry->id.value()] = values_buffer.size();
+      if (!FlattenValue(&flat_entry, &values_buffer)) {
         diag_->Error(DiagMessage()
                      << "failed to flatten resource '"
-                     << ResourceNameRef(package_->name, type->type,
-                                        flat_entry.entry->name)
+                     << ResourceNameRef(package_->name, type->type, flat_entry.entry->name)
                      << "' for configuration '" << config << "'");
         return false;
       }
     }
+
+    bool sparse_encode = use_sparse_entries_;
+
+    // Only sparse encode if the entries will be read on platforms O+.
+    sparse_encode =
+        sparse_encode && (context_->GetMinSdkVersion() >= SDK_O || config.sdkVersion >= SDK_O);
+
+    // Only sparse encode if the offsets are representable in 2 bytes.
+    sparse_encode =
+        sparse_encode && (values_buffer.size() / 4u) <= std::numeric_limits<uint16_t>::max();
+
+    // Only sparse encode if the ratio of populated entries to total entries is below some
+    // threshold.
+    sparse_encode =
+        sparse_encode && ((100 * entries->size()) / num_total_entries) < kSparseEncodingThreshold;
+
+    if (sparse_encode) {
+      type_header->entryCount = util::HostToDevice32(entries->size());
+      type_header->flags |= ResTable_type::FLAG_SPARSE;
+      ResTable_sparseTypeEntry* indices =
+          type_writer.NextBlock<ResTable_sparseTypeEntry>(entries->size());
+      for (size_t i = 0; i < num_total_entries; i++) {
+        if (offsets[i] != ResTable_type::NO_ENTRY) {
+          CHECK((offsets[i] & 0x03) == 0);
+          indices->idx = util::HostToDevice16(i);
+          indices->offset = util::HostToDevice16(offsets[i] / 4u);
+          indices++;
+        }
+      }
+    } else {
+      type_header->entryCount = util::HostToDevice32(num_total_entries);
+      uint32_t* indices = type_writer.NextBlock<uint32_t>(num_total_entries);
+      for (size_t i = 0; i < num_total_entries; i++) {
+        indices[i] = util::HostToDevice32(offsets[i]);
+      }
+    }
+
+    type_header->entriesStart = util::HostToDevice32(type_writer.size());
+    type_writer.buffer()->AppendBuffer(std::move(values_buffer));
     type_writer.Finish();
     return true;
   }
@@ -370,8 +398,7 @@
       CHECK(bool(entry->id)) << "entry must have an ID set";
       sorted_entries.push_back(entry.get());
     }
-    std::sort(sorted_entries.begin(), sorted_entries.end(),
-              cmp_ids<ResourceEntry>);
+    std::sort(sorted_entries.begin(), sorted_entries.end(), cmp_ids<ResourceEntry>);
     return sorted_entries;
   }
 
@@ -443,22 +470,22 @@
       type_pool_.MakeRef(ToString(type->type));
 
       std::vector<ResourceEntry*> sorted_entries = CollectAndSortEntries(type);
-
       if (!FlattenTypeSpec(type, &sorted_entries, buffer)) {
         return false;
       }
 
+      // Since the entries are sorted by ID, the last ID will be the largest.
+      const size_t num_entries = sorted_entries.back()->id.value() + 1;
+
       // The binary resource table lists resource entries for each
       // configuration.
       // We store them inverted, where a resource entry lists the values for
       // each
       // configuration available. Here we reverse this to match the binary
       // table.
-      std::map<ConfigDescription, std::vector<FlatEntry>>
-          config_to_entry_list_map;
+      std::map<ConfigDescription, std::vector<FlatEntry>> config_to_entry_list_map;
       for (ResourceEntry* entry : sorted_entries) {
-        const uint32_t key_index =
-            (uint32_t)key_pool_.MakeRef(entry->name).index();
+        const uint32_t key_index = (uint32_t)key_pool_.MakeRef(entry->name).index();
 
         // Group values by configuration.
         for (auto& config_value : entry->values) {
@@ -469,7 +496,7 @@
 
       // Flatten a configuration value.
       for (auto& entry : config_to_entry_list_map) {
-        if (!FlattenConfig(type, entry.first, &entry.second, buffer)) {
+        if (!FlattenConfig(type, entry.first, num_entries, &entry.second, buffer)) {
           return false;
         }
       }
@@ -477,8 +504,10 @@
     return true;
   }
 
+  IAaptContext* context_;
   IDiagnostics* diag_;
   ResourceTablePackage* package_;
+  bool use_sparse_entries_;
   StringPool type_pool_;
   StringPool key_pool_;
 };
@@ -513,7 +542,7 @@
 
   // Flatten each package.
   for (auto& package : table->packages) {
-    PackageFlattener flattener(context->GetDiagnostics(), package.get());
+    PackageFlattener flattener(context, package.get(), options_.use_sparse_entries);
     if (!flattener.FlattenPackage(&package_buffer)) {
       return false;
     }
diff --git a/tools/aapt2/flatten/TableFlattener.h b/tools/aapt2/flatten/TableFlattener.h
index 53f52c2..223aef8 100644
--- a/tools/aapt2/flatten/TableFlattener.h
+++ b/tools/aapt2/flatten/TableFlattener.h
@@ -25,15 +25,29 @@
 
 namespace aapt {
 
+// The percentage of used entries for a type for which using a sparse encoding is
+// preferred.
+constexpr const size_t kSparseEncodingThreshold = 60;
+
+struct TableFlattenerOptions {
+  // When true, types for configurations with a sparse set of entries are encoded
+  // as a sparse map of entry ID and offset to actual data.
+  // This is only available on platforms O+ and will only be respected when
+  // minSdk is O+.
+  bool use_sparse_entries = false;
+};
+
 class TableFlattener : public IResourceTableConsumer {
  public:
-  explicit TableFlattener(BigBuffer* buffer) : buffer_(buffer) {}
+  explicit TableFlattener(const TableFlattenerOptions& options, BigBuffer* buffer)
+      : options_(options), buffer_(buffer) {}
 
   bool Consume(IAaptContext* context, ResourceTable* table) override;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(TableFlattener);
 
+  TableFlattenerOptions options_;
   BigBuffer* buffer_;
 };
 
diff --git a/tools/aapt2/flatten/TableFlattener_test.cpp b/tools/aapt2/flatten/TableFlattener_test.cpp
index c726240..ff71742 100644
--- a/tools/aapt2/flatten/TableFlattener_test.cpp
+++ b/tools/aapt2/flatten/TableFlattener_test.cpp
@@ -16,7 +16,10 @@
 
 #include "flatten/TableFlattener.h"
 
+#include "android-base/stringprintf.h"
+
 #include "ResourceUtils.h"
+#include "SdkConstants.h"
 #include "test/Test.h"
 #include "unflatten/BinaryResourceParser.h"
 #include "util/Util.h"
@@ -34,32 +37,40 @@
                    .Build();
   }
 
-  ::testing::AssertionResult Flatten(ResourceTable* table,
-                                     ResTable* out_table) {
+  ::testing::AssertionResult Flatten(IAaptContext* context, const TableFlattenerOptions& options,
+                                     ResourceTable* table, std::string* out_content) {
     BigBuffer buffer(1024);
-    TableFlattener flattener(&buffer);
-    if (!flattener.Consume(context_.get(), table)) {
+    TableFlattener flattener(options, &buffer);
+    if (!flattener.Consume(context, table)) {
       return ::testing::AssertionFailure() << "failed to flatten ResourceTable";
     }
+    *out_content = buffer.to_string();
+    return ::testing::AssertionSuccess();
+  }
 
-    std::unique_ptr<uint8_t[]> data = util::Copy(buffer);
-    if (out_table->add(data.get(), buffer.size(), -1, true) != NO_ERROR) {
+  ::testing::AssertionResult Flatten(IAaptContext* context, const TableFlattenerOptions& options,
+                                     ResourceTable* table, ResTable* out_table) {
+    std::string content;
+    auto result = Flatten(context, options, table, &content);
+    if (!result) {
+      return result;
+    }
+
+    if (out_table->add(content.data(), content.size(), -1, true) != NO_ERROR) {
       return ::testing::AssertionFailure() << "flattened ResTable is corrupt";
     }
     return ::testing::AssertionSuccess();
   }
 
-  ::testing::AssertionResult Flatten(ResourceTable* table,
-                                     ResourceTable* out_table) {
-    BigBuffer buffer(1024);
-    TableFlattener flattener(&buffer);
-    if (!flattener.Consume(context_.get(), table)) {
-      return ::testing::AssertionFailure() << "failed to flatten ResourceTable";
+  ::testing::AssertionResult Flatten(IAaptContext* context, const TableFlattenerOptions options,
+                                     ResourceTable* table, ResourceTable* out_table) {
+    std::string content;
+    auto result = Flatten(context, options, table, &content);
+    if (!result) {
+      return result;
     }
 
-    std::unique_ptr<uint8_t[]> data = util::Copy(buffer);
-    BinaryResourceParser parser(context_.get(), out_table, {}, data.get(),
-                                buffer.size());
+    BinaryResourceParser parser(context, out_table, {}, content.data(), content.size());
     if (!parser.Parse()) {
       return ::testing::AssertionFailure() << "flattened ResTable is corrupt";
     }
@@ -127,7 +138,7 @@
     return ::testing::AssertionSuccess();
   }
 
- private:
+ protected:
   std::unique_ptr<IAaptContext> context_;
 };
 
@@ -153,7 +164,7 @@
           .Build();
 
   ResTable res_table;
-  ASSERT_TRUE(Flatten(table.get(), &res_table));
+  ASSERT_TRUE(Flatten(context_.get(), {}, table.get(), &res_table));
 
   EXPECT_TRUE(Exists(&res_table, "com.app.test:id/one", ResourceId(0x7f020000),
                      {}, Res_value::TYPE_INT_BOOLEAN, 0u, 0u));
@@ -200,7 +211,7 @@
           .Build();
 
   ResTable res_table;
-  ASSERT_TRUE(Flatten(table.get(), &res_table));
+  ASSERT_TRUE(Flatten(context_.get(), {}, table.get(), &res_table));
 
   EXPECT_TRUE(Exists(&res_table, "com.app.test:id/one", ResourceId(0x7f020001),
                      {}, Res_value::TYPE_INT_BOOLEAN, 0u, 0u));
@@ -222,7 +233,7 @@
           .Build();
 
   ResourceTable result;
-  ASSERT_TRUE(Flatten(table.get(), &result));
+  ASSERT_TRUE(Flatten(context_.get(), {}, table.get(), &result));
 
   Attribute* actualAttr =
       test::GetValue<Attribute>(&result, "android:attr/foo");
@@ -233,4 +244,119 @@
   EXPECT_EQ(attr.max_int, actualAttr->max_int);
 }
 
+static std::unique_ptr<ResourceTable> BuildTableWithSparseEntries(
+    IAaptContext* context, const ConfigDescription& sparse_config, float load) {
+  std::unique_ptr<ResourceTable> table =
+      test::ResourceTableBuilder()
+          .SetPackageId(context->GetCompilationPackage(), context->GetPackageId())
+          .Build();
+
+  // Add regular entries.
+  int stride = static_cast<int>(1.0f / load);
+  for (int i = 0; i < 100; i++) {
+    const ResourceName name = test::ParseNameOrDie(
+        base::StringPrintf("%s:string/foo_%d", context->GetCompilationPackage().data(), i));
+    const ResourceId resid(context->GetPackageId(), 0x02, static_cast<uint16_t>(i));
+    const auto value =
+        util::make_unique<BinaryPrimitive>(Res_value::TYPE_INT_DEC, static_cast<uint32_t>(i));
+    CHECK(table->AddResource(name, resid, ConfigDescription::DefaultConfig(), "",
+                             std::unique_ptr<Value>(value->Clone(nullptr)),
+                             context->GetDiagnostics()));
+
+    // Every few entries, write out a sparse_config value. This will give us the desired load.
+    if (i % stride == 0) {
+      CHECK(table->AddResource(name, resid, sparse_config, "",
+                               std::unique_ptr<Value>(value->Clone(nullptr)),
+                               context->GetDiagnostics()));
+    }
+  }
+  return table;
+}
+
+TEST_F(TableFlattenerTest, FlattenSparseEntryWithMinSdkO) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder()
+                                              .SetCompilationPackage("android")
+                                              .SetPackageId(0x01)
+                                              .SetMinSdkVersion(SDK_O)
+                                              .Build();
+
+  const ConfigDescription sparse_config = test::ParseConfigOrDie("en-rGB");
+  auto table_in = BuildTableWithSparseEntries(context.get(), sparse_config, 0.25f);
+
+  TableFlattenerOptions options;
+  options.use_sparse_entries = true;
+
+  std::string no_sparse_contents;
+  ASSERT_TRUE(Flatten(context.get(), {}, table_in.get(), &no_sparse_contents));
+
+  std::string sparse_contents;
+  ASSERT_TRUE(Flatten(context.get(), options, table_in.get(), &sparse_contents));
+
+  EXPECT_GT(no_sparse_contents.size(), sparse_contents.size());
+
+  // Attempt to parse the sparse contents.
+
+  ResourceTable sparse_table;
+  BinaryResourceParser parser(context.get(), &sparse_table, Source("test.arsc"),
+                              sparse_contents.data(), sparse_contents.size());
+  ASSERT_TRUE(parser.Parse());
+
+  auto value = test::GetValueForConfig<BinaryPrimitive>(&sparse_table, "android:string/foo_0",
+                                                        sparse_config);
+  ASSERT_NE(nullptr, value);
+  EXPECT_EQ(0u, value->value.data);
+
+  ASSERT_EQ(nullptr, test::GetValueForConfig<BinaryPrimitive>(&sparse_table, "android:string/foo_1",
+                                                              sparse_config));
+
+  value = test::GetValueForConfig<BinaryPrimitive>(&sparse_table, "android:string/foo_4",
+                                                   sparse_config);
+  ASSERT_NE(nullptr, value);
+  EXPECT_EQ(4u, value->value.data);
+}
+
+TEST_F(TableFlattenerTest, FlattenSparseEntryWithConfigSdkVersionO) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder()
+                                              .SetCompilationPackage("android")
+                                              .SetPackageId(0x01)
+                                              .SetMinSdkVersion(SDK_LOLLIPOP)
+                                              .Build();
+
+  const ConfigDescription sparse_config = test::ParseConfigOrDie("en-rGB-v26");
+  auto table_in = BuildTableWithSparseEntries(context.get(), sparse_config, 0.25f);
+
+  TableFlattenerOptions options;
+  options.use_sparse_entries = true;
+
+  std::string no_sparse_contents;
+  ASSERT_TRUE(Flatten(context.get(), {}, table_in.get(), &no_sparse_contents));
+
+  std::string sparse_contents;
+  ASSERT_TRUE(Flatten(context.get(), options, table_in.get(), &sparse_contents));
+
+  EXPECT_GT(no_sparse_contents.size(), sparse_contents.size());
+}
+
+TEST_F(TableFlattenerTest, DoNotUseSparseEntryForDenseConfig) {
+  std::unique_ptr<IAaptContext> context = test::ContextBuilder()
+                                              .SetCompilationPackage("android")
+                                              .SetPackageId(0x01)
+                                              .SetMinSdkVersion(SDK_O)
+                                              .Build();
+
+  const ConfigDescription sparse_config = test::ParseConfigOrDie("en-rGB");
+  auto table_in = BuildTableWithSparseEntries(context.get(), sparse_config, 0.80f);
+
+  TableFlattenerOptions options;
+  options.use_sparse_entries = true;
+
+  std::string no_sparse_contents;
+  ASSERT_TRUE(Flatten(context.get(), {}, table_in.get(), &no_sparse_contents));
+
+  std::string sparse_contents;
+  ASSERT_TRUE(Flatten(context.get(), options, table_in.get(), &sparse_contents));
+
+  EXPECT_EQ(no_sparse_contents.size(), sparse_contents.size());
+}
+
 }  // namespace aapt
diff --git a/tools/aapt2/link/Link.cpp b/tools/aapt2/link/Link.cpp
index 0501a3b..f07e20b 100644
--- a/tools/aapt2/link/Link.cpp
+++ b/tools/aapt2/link/Link.cpp
@@ -96,6 +96,9 @@
   // Products to use/filter on.
   std::unordered_set<std::string> products;
 
+  // Flattening options.
+  TableFlattenerOptions table_flattener_options;
+
   // Split APK options.
   TableSplitterOptions table_splitter_options;
   std::vector<SplitConstraints> split_constraints;
@@ -874,7 +877,7 @@
 
   bool FlattenTable(ResourceTable* table, IArchiveWriter* writer) {
     BigBuffer buffer(1024);
-    TableFlattener flattener(&buffer);
+    TableFlattener flattener(options_.table_flattener_options, &buffer);
     if (!flattener.Consume(context_, table)) {
       return false;
     }
@@ -1870,24 +1873,19 @@
           .RequiredFlag("-o", "Output path", &options.output_path)
           .RequiredFlag("--manifest", "Path to the Android manifest to build",
                         &options.manifest_path)
-          .OptionalFlagList("-I", "Adds an Android APK to link against",
-                            &options.include_paths)
-          .OptionalFlagList(
-              "-R",
-              "Compilation unit to link, using `overlay` semantics.\n"
-              "The last conflicting resource given takes precedence.",
-              &overlay_arg_list)
+          .OptionalFlagList("-I", "Adds an Android APK to link against", &options.include_paths)
+          .OptionalFlagList("-R",
+                            "Compilation unit to link, using `overlay` semantics.\n"
+                            "The last conflicting resource given takes precedence.",
+                            &overlay_arg_list)
           .OptionalFlag("--java", "Directory in which to generate R.java",
                         &options.generate_java_class_path)
-          .OptionalFlag("--proguard",
-                        "Output file for generated Proguard rules",
+          .OptionalFlag("--proguard", "Output file for generated Proguard rules",
                         &options.generate_proguard_rules_path)
-          .OptionalFlag(
-              "--proguard-main-dex",
-              "Output file for generated Proguard rules for the main dex",
-              &options.generate_main_dex_proguard_rules_path)
-          .OptionalSwitch("--no-auto-version",
-                          "Disables automatic style and layout SDK versioning",
+          .OptionalFlag("--proguard-main-dex",
+                        "Output file for generated Proguard rules for the main dex",
+                        &options.generate_main_dex_proguard_rules_path)
+          .OptionalSwitch("--no-auto-version", "Disables automatic style and layout SDK versioning",
                           &options.no_auto_version)
           .OptionalSwitch("--no-version-vectors",
                           "Disables automatic versioning of vector drawables. "
@@ -1903,25 +1901,22 @@
                           "Disables automatic deduping of resources with\n"
                           "identical values across compatible configurations.",
                           &options.no_resource_deduping)
-          .OptionalSwitch(
-              "-x",
-              "Legacy flag that specifies to use the package identifier 0x01",
-              &legacy_x_flag)
-          .OptionalSwitch("-z",
-                          "Require localization of strings marked 'suggested'",
+          .OptionalSwitch("--enable-sparse-encoding",
+                          "Enables encoding sparse entries using a binary search tree.\n"
+                          "This decreases APK size at the cost of resource retrieval performance.",
+                          &options.table_flattener_options.use_sparse_entries)
+          .OptionalSwitch("-x", "Legacy flag that specifies to use the package identifier 0x01",
+                          &legacy_x_flag)
+          .OptionalSwitch("-z", "Require localization of strings marked 'suggested'",
                           &require_localization)
-          .OptionalFlag(
-              "-c",
-              "Comma separated list of configurations to include. The default\n"
-              "is all configurations",
-              &configs)
-          .OptionalFlag(
-              "--preferred-density",
-              "Selects the closest matching density and strips out all others.",
-              &preferred_density)
-          .OptionalFlag("--product",
-                        "Comma separated list of product names to keep",
-                        &product_list)
+          .OptionalFlag("-c",
+                        "Comma separated list of configurations to include. The default\n"
+                        "is all configurations",
+                        &configs)
+          .OptionalFlag("--preferred-density",
+                        "Selects the closest matching density and strips out all others.",
+                        &preferred_density)
+          .OptionalFlag("--product", "Comma separated list of product names to keep", &product_list)
           .OptionalSwitch("--output-to-dir",
                           "Outputs the APK contents to a directory specified "
                           "by -o",
@@ -1935,11 +1930,10 @@
                         "Default minimum SDK version to use for "
                         "AndroidManifest.xml",
                         &options.manifest_fixer_options.min_sdk_version_default)
-          .OptionalFlag(
-              "--target-sdk-version",
-              "Default target SDK version to use for "
-              "AndroidManifest.xml",
-              &options.manifest_fixer_options.target_sdk_version_default)
+          .OptionalFlag("--target-sdk-version",
+                        "Default target SDK version to use for "
+                        "AndroidManifest.xml",
+                        &options.manifest_fixer_options.target_sdk_version_default)
           .OptionalFlag("--version-code",
                         "Version code (integer) to inject into the "
                         "AndroidManifest.xml if none is present",
@@ -1948,8 +1942,7 @@
                         "Version name to inject into the AndroidManifest.xml "
                         "if none is present",
                         &options.manifest_fixer_options.version_name_default)
-          .OptionalSwitch("--static-lib", "Generate a static Android library",
-                          &options.static_lib)
+          .OptionalSwitch("--static-lib", "Generate a static Android library", &options.static_lib)
           .OptionalSwitch("--no-static-lib-packages",
                           "Merge all library resources under the app's package",
                           &options.no_static_lib_packages)
@@ -1957,14 +1950,12 @@
                           "Generates R.java without the final modifier.\n"
                           "This is implied when --static-lib is specified.",
                           &options.generate_non_final_ids)
-          .OptionalFlag("--stable-ids",
-                        "File containing a list of name to ID mapping.",
+          .OptionalFlag("--stable-ids", "File containing a list of name to ID mapping.",
                         &stable_id_file_path)
-          .OptionalFlag(
-              "--emit-ids",
-              "Emit a file at the given path with a list of name to ID\n"
-              "mappings, suitable for use with --stable-ids.",
-              &options.resource_id_map_path)
+          .OptionalFlag("--emit-ids",
+                        "Emit a file at the given path with a list of name to ID\n"
+                        "mappings, suitable for use with --stable-ids.",
+                        &options.resource_id_map_path)
           .OptionalFlag("--private-symbols",
                         "Package name to use when generating R.java for "
                         "private symbols.\n"
@@ -1972,8 +1963,7 @@
                         "the application's "
                         "package name",
                         &options.private_symbols)
-          .OptionalFlag("--custom-package",
-                        "Custom Java package under which to generate R.java",
+          .OptionalFlag("--custom-package", "Custom Java package under which to generate R.java",
                         &options.custom_java_package)
           .OptionalFlagList("--extra-packages",
                             "Generate the same R.java but with different "
@@ -1987,23 +1977,19 @@
                           "Allows the addition of new resources in "
                           "overlays without <add-resource> tags",
                           &options.auto_add_overlay)
-          .OptionalFlag("--rename-manifest-package",
-                        "Renames the package in AndroidManifest.xml",
+          .OptionalFlag("--rename-manifest-package", "Renames the package in AndroidManifest.xml",
                         &options.manifest_fixer_options.rename_manifest_package)
-          .OptionalFlag(
-              "--rename-instrumentation-target-package",
-              "Changes the name of the target package for instrumentation. "
-              "Most useful "
-              "when used\nin conjunction with --rename-manifest-package",
-              &options.manifest_fixer_options
-                   .rename_instrumentation_target_package)
+          .OptionalFlag("--rename-instrumentation-target-package",
+                        "Changes the name of the target package for instrumentation. "
+                        "Most useful "
+                        "when used\nin conjunction with --rename-manifest-package",
+                        &options.manifest_fixer_options.rename_instrumentation_target_package)
           .OptionalFlagList("-0", "File extensions not to compress",
                             &options.extensions_to_not_compress)
-          .OptionalFlagList(
-              "--split",
-              "Split resources matching a set of configs out to a "
-              "Split APK.\nSyntax: path/to/output.apk:<config>[,<config>[...]]",
-              &split_args)
+          .OptionalFlagList("--split",
+                            "Split resources matching a set of configs out to a "
+                            "Split APK.\nSyntax: path/to/output.apk:<config>[,<config>[...]]",
+                            &split_args)
           .OptionalSwitch("-v", "Enables verbose logging", &verbose);
 
   if (!flags.Parse("aapt2 link", args, &std::cerr)) {
diff --git a/tools/aapt2/util/BigBuffer.cpp b/tools/aapt2/util/BigBuffer.cpp
index ef99dca..75fa789 100644
--- a/tools/aapt2/util/BigBuffer.cpp
+++ b/tools/aapt2/util/BigBuffer.cpp
@@ -76,4 +76,12 @@
   return blocks_.back().buffer.get();
 }
 
+std::string BigBuffer::to_string() const {
+  std::string result;
+  for (const Block& block : blocks_) {
+    result.append(block.buffer.get(), block.buffer.get() + block.size);
+  }
+  return result;
+}
+
 }  // namespace aapt
diff --git a/tools/aapt2/util/BigBuffer.h b/tools/aapt2/util/BigBuffer.h
index d23c41d..3045255 100644
--- a/tools/aapt2/util/BigBuffer.h
+++ b/tools/aapt2/util/BigBuffer.h
@@ -19,6 +19,7 @@
 
 #include <cstring>
 #include <memory>
+#include <string>
 #include <type_traits>
 #include <vector>
 
@@ -116,6 +117,8 @@
   const_iterator begin() const;
   const_iterator end() const;
 
+  std::string to_string() const;
+
  private:
   DISALLOW_COPY_AND_ASSIGN(BigBuffer);