[Zucchini] Create dex disassembler.

Creates Disassembler that recognises and parses DEX format. For now, it doesn't
extract any type reference, so it is equivalent to DisassemblerNoOp. Extraction
of various types of reference will be added in a follow-up CL.
BufferView::covers_array() and unittests were also added.

Change-Id: I08756244e9af899cf0f40dabd2b0059e1749328e
Reviewed-on: https://chromium-review.googlesource.com/967603
Reviewed-by: Samuel Huang <huangs@chromium.org>
Commit-Queue: Etienne Pierre-Doray <etiennep@chromium.org>
Cr-Commit-Position: refs/heads/master@{#546807}
NOKEYCHECK=True
GitOrigin-RevId: d214e2cf9e23bf055f0e0655e9564761d50206ad

8 files changed, 703 insertions, 1 deletions

diff --git a/BUILD.gn b/BUILD.gn
index e8eee3a..37a548d 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -24,6 +24,8 @@ static_library("zucchini_lib") {
     "crc32.h",
     "disassembler.cc",
     "disassembler.h",
+    "disassembler_dex.cc",
+    "disassembler_dex.h",
     "disassembler_no_op.cc",
     "disassembler_no_op.h",
     "disassembler_win32.cc",
@@ -61,6 +63,7 @@ static_library("zucchini_lib") {
     "target_pool.h",
     "targets_affinity.cc",
     "targets_affinity.h",
+    "type_dex.h",
     "type_win_pe.h",
     "typed_value.h",
     "zucchini.h",
diff --git a/buffer_view.h b/buffer_view.h
index a7dfd17..8dbe817 100644
--- a/buffer_view.h
+++ b/buffer_view.h
@@ -105,6 +105,14 @@ class BufferViewBase {
     return region.FitsIn(size());
   }
 
+  // Returns whether the buffer is large enough to cover an array starting at
+  // |offset| with |num| elements, each taking |elt_size| bytes.
+  bool covers_array(size_t offset, size_t num, size_t elt_size) {
+    DCHECK_GT(elt_size, 0U);
+    // Use subtraction and division to avoid overflow.
+    return offset < size() && (size() - offset) / elt_size >= num;
+  }
+
   // Element access
 
   // Returns the raw value at specified location |pos|.
diff --git a/buffer_view_unittest.cc b/buffer_view_unittest.cc
index cfb3d9b..1d3ccb8 100644
--- a/buffer_view_unittest.cc
+++ b/buffer_view_unittest.cc
@@ -176,6 +176,40 @@ TEST_F(BufferViewTest, Covers) {
   EXPECT_FALSE(view.covers({size_t(-1), size_t(-1)}));
 }
 
+TEST_F(BufferViewTest, CoversArray) {
+  ConstBufferView view(bytes_.data(), bytes_.size());
+
+  for (uint32_t i = 1; i <= bytes_.size(); ++i) {
+    EXPECT_TRUE(view.covers_array(0, 1, i));
+    EXPECT_TRUE(view.covers_array(0, i, 1));
+    EXPECT_TRUE(view.covers_array(0, i, bytes_.size() / i));
+    EXPECT_TRUE(view.covers_array(0, bytes_.size() / i, i));
+    if (i < bytes_.size()) {
+      EXPECT_TRUE(view.covers_array(i, 1, bytes_.size() - i));
+      EXPECT_TRUE(view.covers_array(i, bytes_.size() - i, 1));
+    }
+    EXPECT_TRUE(view.covers_array(bytes_.size() - (bytes_.size() / i) * i, 1,
+                                  bytes_.size() / i));
+  }
+
+  EXPECT_TRUE(view.covers_array(0, 0, bytes_.size()));
+  EXPECT_TRUE(view.covers_array(bytes_.size() - 1, 0, bytes_.size()));
+  EXPECT_FALSE(view.covers_array(bytes_.size(), 0, bytes_.size()));
+  EXPECT_TRUE(view.covers_array(0, 0, 0x10000));
+  EXPECT_TRUE(view.covers_array(bytes_.size() - 1, 0, 0x10000));
+  EXPECT_FALSE(view.covers_array(bytes_.size(), 0, 0x10000));
+
+  EXPECT_FALSE(view.covers_array(0, 1, bytes_.size() + 1));
+  EXPECT_FALSE(view.covers_array(0, 2, bytes_.size()));
+  EXPECT_FALSE(view.covers_array(0, bytes_.size() + 11, 1));
+  EXPECT_FALSE(view.covers_array(0, bytes_.size(), 2));
+  EXPECT_FALSE(view.covers_array(1, bytes_.size(), 1));
+
+  EXPECT_FALSE(view.covers_array(bytes_.size(), 1, 1));
+  EXPECT_FALSE(view.covers_array(bytes_.size(), 0, 1));
+  EXPECT_FALSE(view.covers_array(0, 0x10000, 0x10000));
+}
+
 TEST_F(BufferViewTest, Equals) {
   // Almost identical to |bytes_|, except at 2 places:         v  v
   std::vector<uint8_t> bytes2 = ParseHexString("10 32 54 76 98 AB CD FE 10 00");
diff --git a/disassembler_dex.cc b/disassembler_dex.cc
new file mode 100644
index 0000000..23198cc
--- /dev/null
+++ b/disassembler_dex.cc
@@ -0,0 +1,307 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "components/zucchini/disassembler_dex.h"
+
+#include <cmath>
+#include <set>
+#include <utility>
+
+#include "base/logging.h"
+#include "base/numerics/safe_conversions.h"
+#include "base/strings/stringprintf.h"
+#include "components/zucchini/buffer_source.h"
+#include "components/zucchini/buffer_view.h"
+
+namespace zucchini {
+
+namespace {
+
+// Size of a Dalvik instruction unit. Need to cast to signed int because
+// sizeof() gives size_t, which dominates when operated on ptrdiff_t, then
+// wrecks havoc for base::checked_cast<int16_t>().
+constexpr int kInstrUnitSize = static_cast<int>(sizeof(uint16_t));
+
+// Buffer for ReadDexHeader() to optionally return results.
+struct ReadDexHeaderResults {
+  BufferSource source;
+  const dex::HeaderItem* header;
+  int dex_version;
+};
+
+// Returns whether |image| points to a DEX file. If this is a possibility and
+// |opt_results| is not null, then uses it to pass extracted data to enable
+// further parsing.
+bool ReadDexHeader(ConstBufferView image, ReadDexHeaderResults* opt_results) {
+  // This part needs to be fairly efficient since it may be called many times.
+  BufferSource source(image);
+  const dex::HeaderItem* header = source.GetPointer<dex::HeaderItem>();
+  if (!header)
+    return false;
+  if (header->magic[0] != 'd' || header->magic[1] != 'e' ||
+      header->magic[2] != 'x' || header->magic[3] != '\n' ||
+      header->magic[7] != '\0') {
+    return false;
+  }
+
+  // Magic matches: More detailed tests can be conducted.
+  int dex_version = 0;
+  for (int i = 4; i < 7; ++i) {
+    if (!isdigit(header->magic[i]))
+      return false;
+    dex_version = dex_version * 10 + (header->magic[i] - '0');
+  }
+  if (dex_version != 35 && dex_version != 37)
+    return false;
+
+  if (header->file_size > image.size() ||
+      header->file_size < sizeof(dex::HeaderItem) ||
+      header->map_off < sizeof(dex::HeaderItem)) {
+    return false;
+  }
+
+  if (opt_results)
+    *opt_results = {source, header, dex_version};
+  return true;
+}
+
+}  // namespace
+
+/******** CodeItemParser ********/
+
+// A parser to extract successive code items from a DEX image whose header has
+// been parsed.
+class CodeItemParser {
+ public:
+  using size_type = BufferSource::size_type;
+
+  explicit CodeItemParser(ConstBufferView image) : image_(image) {}
+
+  // Initializes the parser, returns true on success and false on error.
+  bool Init(const dex::MapItem& code_map_item) {
+    // Sanity check to quickly fail if |code_map_item.offset| or
+    // |code_map_item.size| is too large. This is a heuristic because code item
+    // sizes need to be parsed (sizeof(dex::CodeItem) is a lower bound).
+    if (!image_.covers_array(code_map_item.offset, code_map_item.size,
+                             sizeof(dex::CodeItem))) {
+      return false;
+    }
+    source_ = std::move(BufferSource(image_).Skip(code_map_item.offset));
+    return true;
+  }
+
+  // Extracts the header of the next code item, and skips the variable-length
+  // data. Returns the offset of the code item if successful. Otherwise returns
+  // kInvalidOffset, and thereafter the parser becomes valid. For reference,
+  // here's a pseudo-struct of a complete code item:
+  //
+  // struct code_item {
+  //   // 4-byte aligned here.
+  //   // 16-byte header defined (dex::CodeItem).
+  //   uint16_t registers_size;
+  //   uint16_t ins_size;
+  //   uint16_t outs_size;
+  //   uint16_t tries_size;
+  //   uint32_t debug_info_off;
+  //   uint32_t insns_size;
+  //
+  //   // Variable-length data follow.
+  //   uint16_t insns[insns_size];  // Instruction bytes.
+  //   uint16_t padding[(tries_size > 0 && insns_size % 2 == 1) ? 1 : 0];
+  //
+  //   if (tries_size > 0) {
+  //     // 4-byte aligned here.
+  //     struct try_item {  // dex::TryItem.
+  //       uint32_t start_addr;
+  //       uint16_t insn_count;
+  //       uint16_t handler_off;
+  //     } tries[tries_size];
+  //
+  //     struct encoded_catch_handler_list {
+  //       uleb128 handlers_size;
+  //       struct encoded_catch_handler {
+  //         sleb128 encoded_catch_handler_size;
+  //         struct encoded_type_addr_pair {
+  //           uleb128 type_idx;
+  //           uleb128 addr;
+  //         } handlers[abs(encoded_catch_handler_size)];
+  //         if (encoded_catch_handler_size <= 0) {
+  //           uleb128 catch_all_addr;
+  //         }
+  //       } handlers_list[handlers_size];
+  //     } handlers_group;  // Confusingly called "handlers" in DEX doc.
+  //   }
+  //
+  //   // Padding to 4-bytes align next code_item *only if more exist*.
+  // }
+  offset_t GetNext() {
+    // Read header CodeItem.
+    if (!source_.AlignOn(image_, 4U))
+      return kInvalidOffset;
+    const offset_t code_item_offset =
+        base::checked_cast<offset_t>(source_.begin() - image_.begin());
+    const auto* code_item = source_.GetPointer<const dex::CodeItem>();
+    if (!code_item)
+      return kInvalidOffset;
+    DCHECK_EQ(0U, code_item_offset % 4U);
+
+    // Skip instruction bytes.
+    if (!source_.GetArray<uint16_t>(code_item->insns_size))
+      return kInvalidOffset;
+    // Skip padding if present.
+    if (code_item->tries_size > 0 && !source_.AlignOn(image_, 4U))
+      return kInvalidOffset;
+
+    // Skip tries[] and handlers_group to arrive at the next code item. Parsing
+    // is nontrivial due to use of uleb128 / sleb128.
+    if (code_item->tries_size > 0) {
+      // Skip (try_item) tries[].
+      if (!source_.GetArray<dex::TryItem>(code_item->tries_size))
+        return kInvalidOffset;
+
+      // Skip handlers_group.
+      uint32_t handlers_size = 0;
+      if (!source_.GetUleb128(&handlers_size))
+        return kInvalidOffset;
+      // Sanity check to quickly reject excessively large |handlers_size|.
+      if (source_.Remaining() < static_cast<size_type>(handlers_size))
+        return kInvalidOffset;
+
+      // Skip (encoded_catch_handler) handlers_list[].
+      for (uint32_t k = 0; k < handlers_size; ++k) {
+        int32_t encoded_catch_handler_size = 0;
+        if (!source_.GetSleb128(&encoded_catch_handler_size))
+          return kInvalidOffset;
+        const size_type abs_size = std::abs(encoded_catch_handler_size);
+        if (source_.Remaining() < abs_size)  // Sanity check.
+          return kInvalidOffset;
+        // Skip (encoded_type_addr_pair) handlers[].
+        for (size_type j = 0; j < abs_size; ++j) {
+          if (!source_.SkipLeb128() || !source_.SkipLeb128())
+            return kInvalidOffset;
+        }
+        // Skip catch_all_addr.
+        if (encoded_catch_handler_size <= 0) {
+          if (!source_.SkipLeb128())
+            return kInvalidOffset;
+        }
+      }
+    }
+    // Success! |code_item->insns_size| is validated, but its content is still
+    // considered unsafe and requires validation.
+    return code_item_offset;
+  }
+
+  // Given |code_item_offset| that points to the start of a valid code item in
+  // |image|, returns |insns| bytes as ConstBufferView.
+  static ConstBufferView GetCodeItemInsns(ConstBufferView image,
+                                          offset_t code_item_offset) {
+    BufferSource source(BufferSource(image).Skip(code_item_offset));
+    const auto* code_item = source.GetPointer<const dex::CodeItem>();
+    DCHECK(code_item);
+    BufferRegion insns{0, code_item->insns_size * kInstrUnitSize};
+    DCHECK(source.covers(insns));
+    return source[insns];
+  }
+
+ private:
+  ConstBufferView image_;
+  BufferSource source_;
+};
+
+/******** DisassemblerDex ********/
+
+DisassemblerDex::DisassemblerDex() : Disassembler(4) {}
+
+DisassemblerDex::~DisassemblerDex() = default;
+
+// static.
+bool DisassemblerDex::QuickDetect(ConstBufferView image) {
+  return ReadDexHeader(image, nullptr);
+}
+
+ExecutableType DisassemblerDex::GetExeType() const {
+  return kExeTypeDex;
+}
+
+std::string DisassemblerDex::GetExeTypeString() const {
+  return base::StringPrintf("DEX (version %d)", dex_version_);
+}
+
+std::vector<ReferenceGroup> DisassemblerDex::MakeReferenceGroups() const {
+  return {};
+}
+
+bool DisassemblerDex::Parse(ConstBufferView image) {
+  image_ = image;
+  return ParseHeader();
+}
+
+bool DisassemblerDex::ParseHeader() {
+  ReadDexHeaderResults results;
+  if (!ReadDexHeader(image_, &results))
+    return false;
+
+  header_ = results.header;
+  dex_version_ = results.dex_version;
+  BufferSource source = results.source;
+
+  // DEX header contains file size, so use it to resize |image_| right away.
+  image_.shrink(header_->file_size);
+
+  // Read map list. This is not a fixed-size array, so instead of reading
+  // MapList directly, read |MapList::size| first, then visit elements in
+  // |MapList::list|.
+  static_assert(
+      offsetof(dex::MapList, list) == sizeof(decltype(dex::MapList::size)),
+      "MapList size error.");
+  source = std::move(BufferSource(image_).Skip(header_->map_off));
+  decltype(dex::MapList::size) list_size = 0;
+  if (!source.GetValue(&list_size) || list_size > dex::kMaxItemListSize)
+    return false;
+  const auto* item_list = source.GetArray<const dex::MapItem>(list_size);
+  if (!item_list)
+    return false;
+
+  // Read and validate map list, ensuring that required item types are present.
+  std::set<uint16_t> required_item_types = {
+      dex::kTypeStringIdItem, dex::kTypeTypeIdItem, dex::kTypeFieldIdItem,
+      dex::kTypeMethodIdItem, dex::kTypeCodeItem};
+  for (offset_t i = 0; i < list_size; ++i) {
+    const dex::MapItem* item = &item_list[i];
+    // Sanity check to reject unreasonably large |item->size|.
+    // TODO(huangs): Implement a more stringent check.
+    if (!image_.covers({item->offset, item->size}))
+      return false;
+    if (!map_item_map_.insert(std::make_pair(item->type, item)).second)
+      return false;  // A given type must appear at most once.
+    required_item_types.erase(item->type);
+  }
+  if (!required_item_types.empty())
+    return false;
+
+  // Make local copies of main map items.
+  string_map_item_ = *map_item_map_[dex::kTypeStringIdItem];
+  type_map_item_ = *map_item_map_[dex::kTypeTypeIdItem];
+  field_map_item_ = *map_item_map_[dex::kTypeFieldIdItem];
+  method_map_item_ = *map_item_map_[dex::kTypeMethodIdItem];
+  code_map_item_ = *map_item_map_[dex::kTypeCodeItem];
+
+  // Iteratively extract variable-length code items blocks. Any failure would
+  // indicate invalid DEX. Success indicates that no structural problem is
+  // found. However, contained instructions still need validation on use.
+  CodeItemParser code_item_parser(image_);
+  if (!code_item_parser.Init(code_map_item_))
+    return false;
+  code_item_offsets_.resize(code_map_item_.size);
+  for (size_t i = 0; i < code_map_item_.size; ++i) {
+    const offset_t code_item_offset = code_item_parser.GetNext();
+    if (code_item_offset == kInvalidOffset)
+      return false;
+    code_item_offsets_[i] = code_item_offset;
+  }
+  return true;
+}
+
+}  // namespace zucchini
diff --git a/disassembler_dex.h b/disassembler_dex.h
new file mode 100644
index 0000000..7bbe5d1
--- /dev/null
+++ b/disassembler_dex.h
@@ -0,0 +1,65 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COMPONENTS_ZUCCHINI_DISASSEMBLER_DEX_H_
+#define COMPONENTS_ZUCCHINI_DISASSEMBLER_DEX_H_
+
+#include <stdint.h>
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/macros.h"
+#include "components/zucchini/disassembler.h"
+#include "components/zucchini/image_utils.h"
+#include "components/zucchini/type_dex.h"
+
+namespace zucchini {
+
+// For consistency, let "canonical order" of DEX data types be the order defined
+// in https://source.android.com/devices/tech/dalvik/dex-format "Type Codes"
+// section.
+
+class DisassemblerDex : public Disassembler {
+ public:
+  DisassemblerDex();
+  ~DisassemblerDex() override;
+
+  // Applies quick checks to determine if |image| *may* point to the start of an
+  // executable. Returns true on success.
+  static bool QuickDetect(ConstBufferView image);
+
+  // Disassembler:
+  ExecutableType GetExeType() const override;
+  std::string GetExeTypeString() const override;
+  std::vector<ReferenceGroup> MakeReferenceGroups() const override;
+
+ private:
+  friend Disassembler;
+  using MapItemMap = std::map<uint16_t, const dex::MapItem*>;
+
+  // Disassembler:
+  bool Parse(ConstBufferView image) override;
+
+  bool ParseHeader();
+
+  const dex::HeaderItem* header_ = nullptr;
+  int dex_version_ = 0;
+  MapItemMap map_item_map_ = {};
+  dex::MapItem string_map_item_ = {};
+  dex::MapItem type_map_item_ = {};
+  dex::MapItem field_map_item_ = {};
+  dex::MapItem method_map_item_ = {};
+  dex::MapItem code_map_item_ = {};
+
+  // Sorted list of offsets of code items in |image_|.
+  std::vector<offset_t> code_item_offsets_;
+
+  DISALLOW_COPY_AND_ASSIGN(DisassemblerDex);
+};
+
+}  // namespace zucchini
+
+#endif  // COMPONENTS_ZUCCHINI_DISASSEMBLER_DEX_H_
diff --git a/element_detection.cc b/element_detection.cc
index d6bba5f..2fa3604 100644
--- a/element_detection.cc
+++ b/element_detection.cc
@@ -8,6 +8,7 @@
 
 #include "base/logging.h"
 #include "components/zucchini/disassembler.h"
+#include "components/zucchini/disassembler_dex.h"
 #include "components/zucchini/disassembler_no_op.h"
 #include "components/zucchini/disassembler_win32.h"
 
@@ -36,6 +37,12 @@ std::unique_ptr<Disassembler> MakeDisassemblerWithoutFallback(
       return disasm;
   }
 
+  if (DisassemblerDex::QuickDetect(image)) {
+    auto disasm = Disassembler::Make<DisassemblerDex>(image);
+    if (disasm && disasm->size() >= kMinProgramSize)
+      return disasm;
+  }
+
   return nullptr;
 }
 
@@ -46,6 +53,8 @@ std::unique_ptr<Disassembler> MakeDisassemblerOfType(ConstBufferView image,
       return Disassembler::Make<DisassemblerWin32X86>(image);
     case kExeTypeWin32X64:
       return Disassembler::Make<DisassemblerWin32X64>(image);
+    case kExeTypeDex:
+      return Disassembler::Make<DisassemblerDex>(image);
     case kExeTypeNoOp:
       return Disassembler::Make<DisassemblerNoOp>(image);
     default:
diff --git a/ensemble_matcher.cc b/ensemble_matcher.cc
index eebbae9..37a7af9 100644
--- a/ensemble_matcher.cc
+++ b/ensemble_matcher.cc
@@ -4,6 +4,7 @@
 
 #include "components/zucchini/ensemble_matcher.h"
 
+#include <algorithm>
 #include <limits>
 
 #include "base/logging.h"
@@ -18,7 +19,21 @@ EnsembleMatcher::EnsembleMatcher() = default;
 EnsembleMatcher::~EnsembleMatcher() = default;
 
 void EnsembleMatcher::Trim() {
-  // TODO(huangs): Add MultiDex handling logic when we add DEX support.
+  // Trim rule: If > 1 DEX files are found then ignore all DEX. This is done
+  // because we do not yet support MultiDex, under which contents can move
+  // across file boundary between "old" and "new" archives. When this occurs,
+  // forcing matches of DEX files and patching them separately can result in
+  // larger patches than naive patching.
+  auto is_match_dex = [](const ElementMatch& match) {
+    return match.exe_type() == kExeTypeDex;
+  };
+  auto num_dex = std::count_if(matches_.begin(), matches_.end(), is_match_dex);
+  if (num_dex > 1) {
+    LOG(WARNING) << "Found " << num_dex << " DEX: Ignoring all.";
+    matches_.erase(
+        std::remove_if(matches_.begin(), matches_.end(), is_match_dex),
+        matches_.end());
+  }
 }
 
 }  // namespace zucchini
diff --git a/type_dex.h b/type_dex.h
new file mode 100644
index 0000000..508d331
--- /dev/null
+++ b/type_dex.h
@@ -0,0 +1,261 @@
+// Copyright 2018 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef COMPONENTS_ZUCCHINI_TYPE_DEX_H_
+#define COMPONENTS_ZUCCHINI_TYPE_DEX_H_
+
+#include <stdint.h>
+
+namespace zucchini {
+namespace dex {
+// Contains types that models DEX executable format data structures.
+// See https://source.android.com/devices/tech/dalvik/dex-format
+
+// The supported versions are 035 and 037.
+
+enum class FormatId : uint8_t {
+  b,  // 22b.
+  c,  // 21c, 22c, 31c, 35c, 3rc.
+  h,  // 21h.
+  i,  // 31i.
+  l,  // 51l.
+  n,  // 11n.
+  s,  // 21s, 22s.
+  t,  // 10t, 20t, 21t, 22t, 30t, 31t.
+  x,  // 10x, 11x, 12x, 22x, 23x, 32x.
+};
+
+struct Instruction {
+  Instruction() = default;
+  constexpr Instruction(uint8_t opcode_in,
+                        uint8_t layout_in,
+                        FormatId format_in,
+                        uint8_t variant_in = 1)
+      : opcode(opcode_in),
+        layout(layout_in),
+        format(format_in),
+        variant(variant_in) {}
+
+  // The opcode that identifies the instruction.
+  uint8_t opcode;
+  // Number of uint16_t units for the instruction.
+  uint8_t layout;
+  // Identifier that groups similar instructions, as quick filter.
+  FormatId format;
+  // Number of successive opcodes that have the same format.
+  uint8_t variant = 1;
+};
+
+constexpr Instruction kByteCode[] = {
+    {0x00, 1, FormatId::x},
+    {0x01, 1, FormatId::x},
+    {0x02, 2, FormatId::x},
+    {0x03, 3, FormatId::x},
+    {0x04, 1, FormatId::x},
+    {0x05, 2, FormatId::x},
+    {0x06, 3, FormatId::x},
+    {0x07, 1, FormatId::x},
+    {0x08, 2, FormatId::x},
+    {0x09, 3, FormatId::x},
+    {0x0A, 1, FormatId::x},
+    {0x0B, 1, FormatId::x},
+    {0x0C, 1, FormatId::x},
+    {0x0D, 1, FormatId::x},
+    {0x0E, 1, FormatId::x},
+    {0x0F, 1, FormatId::x},
+    {0x10, 1, FormatId::x},
+    {0x11, 1, FormatId::x},
+    {0x12, 1, FormatId::n},
+    {0x13, 2, FormatId::s},
+    {0x14, 3, FormatId::i},
+    {0x15, 2, FormatId::h},
+    {0x16, 2, FormatId::s},
+    {0x17, 3, FormatId::i},
+    {0x18, 5, FormatId::l},
+    {0x19, 2, FormatId::h},
+    {0x1A, 2, FormatId::c},
+    {0x1B, 3, FormatId::c},
+    {0x1C, 2, FormatId::c},
+    {0x1D, 1, FormatId::x},
+    {0x1E, 1, FormatId::x},
+    {0x1F, 2, FormatId::c},
+    {0x20, 2, FormatId::c},
+    {0x21, 1, FormatId::x},
+    {0x22, 2, FormatId::c},
+    {0x23, 2, FormatId::c},
+    {0x24, 3, FormatId::c},
+    {0x25, 3, FormatId::c},
+    {0x26, 3, FormatId::t},
+    {0x27, 1, FormatId::x},
+    {0x28, 1, FormatId::t},
+    {0x29, 2, FormatId::t},
+    {0x2A, 3, FormatId::t},
+    {0x2B, 3, FormatId::t},
+    {0x2C, 3, FormatId::t},
+    {0x2D, 2, FormatId::x, 5},
+    {0x32, 2, FormatId::t, 6},
+    {0x38, 2, FormatId::t, 6},
+    // {0x3E, 1, FormatId::x, 6}, unused
+    {0x44, 2, FormatId::x, 14},
+    {0x52, 2, FormatId::c, 14},
+    {0x60, 2, FormatId::c, 14},
+    {0x6E, 3, FormatId::c, 5},
+    // {0x73, 1, FormatId::x}, unused
+    {0x74, 3, FormatId::c, 5},
+    // {0x79, 1, FormatId::x, 2}, unused
+    {0x7B, 1, FormatId::x, 21},
+    {0x90, 2, FormatId::x, 32},
+    {0xB0, 1, FormatId::x, 32},
+    {0xD0, 2, FormatId::s, 8},
+    {0xD8, 2, FormatId::b, 11},
+    // {0xE3, 1, FormatId::x, 29}, unused
+};
+
+// Supported by MSVC, g++, and clang++. Ensures no gaps in packing.
+#pragma pack(push, 1)
+
+// header_item: Appears in the header section.
+struct HeaderItem {
+  uint8_t magic[8];
+  uint32_t checksum;
+  uint8_t signature[20];
+  uint32_t file_size;
+  uint32_t header_size;
+  uint32_t endian_tag;
+  uint32_t link_size;
+  uint32_t link_off;
+  uint32_t map_off;
+  uint32_t string_ids_size;
+  uint32_t string_ids_off;
+  uint32_t type_ids_size;
+  uint32_t type_ids_off;
+  uint32_t proto_ids_size;
+  uint32_t proto_ids_off;
+  uint32_t field_ids_size;
+  uint32_t field_ids_off;
+  uint32_t method_ids_size;
+  uint32_t method_ids_off;
+  uint32_t class_defs_size;
+  uint32_t class_defs_off;
+  uint32_t data_size;
+  uint32_t data_off;
+};
+
+// string_id_item: String identifiers list.
+struct StringIdItem {
+  uint32_t string_data_off;
+};
+
+// type_id_item: Type identifiers list.
+struct TypeIdItem {
+  uint32_t descriptor_idx;
+};
+
+// proto_id_item: Method prototype identifiers list.
+struct ProtoIdItem {
+  uint32_t shorty_idx;
+  uint32_t return_type_idx;
+  uint32_t parameters_off;
+};
+
+// field_id_item: Field identifiers list.
+struct FieldIdItem {
+  uint16_t class_idx;
+  uint16_t type_idx;
+  uint32_t name_idx;
+};
+
+// method_id_item: Method identifiers list.
+struct MethodIdItem {
+  uint16_t class_idx;
+  uint16_t proto_idx;
+  uint32_t name_idx;
+};
+
+// class_def_item: Class definitions list.
+struct ClassDefItem {
+  uint32_t class_idx;
+  uint32_t access_flags;
+  uint32_t superclass_idx;
+  uint32_t interfaces_off;
+  uint32_t source_file_idx;
+  uint32_t annotations_off;
+  uint32_t class_data_off;
+  uint32_t static_values_off;
+};
+
+// code_item: Header of a code item.
+struct CodeItem {
+  uint16_t registers_size;
+  uint16_t ins_size;
+  uint16_t outs_size;
+  uint16_t tries_size;
+  uint32_t debug_info_off;
+  uint32_t insns_size;
+  // Variable length data follow for complete code item.
+};
+
+constexpr uint32_t kMaxItemListSize = 18;
+
+// map_item
+struct MapItem {
+  uint16_t type;
+  uint16_t unused;
+  uint32_t size;
+  uint32_t offset;
+};
+
+// map_list
+struct MapList {
+  uint32_t size;
+  MapItem list[kMaxItemListSize];
+};
+
+// type_item
+struct TypeItem {
+  uint16_t type_idx;
+};
+
+// annotation_set_ref_item
+struct AnnotationSetRefItem {
+  uint32_t annotations_off;
+};
+
+// annotation_off_item
+struct AnnotationOffItem {
+  uint32_t annotation_off;
+};
+
+// try_item
+struct TryItem {
+  uint32_t start_addr;
+  uint16_t insn_count;
+  uint16_t handler_off;
+};
+
+constexpr uint16_t kTypeHeaderItem = 0x0000;
+constexpr uint16_t kTypeStringIdItem = 0x0001;
+constexpr uint16_t kTypeTypeIdItem = 0x0002;
+constexpr uint16_t kTypeProtoIdItem = 0x0003;
+constexpr uint16_t kTypeFieldIdItem = 0x0004;
+constexpr uint16_t kTypeMethodIdItem = 0x0005;
+constexpr uint16_t kTypeClassDefItem = 0x0006;
+constexpr uint16_t kTypeMapList = 0x1000;
+constexpr uint16_t kTypeTypeList = 0x1001;
+constexpr uint16_t kTypeAnnotationSetRefList = 0x1002;
+constexpr uint16_t kTypeAnnotationSetItem = 0x1003;
+constexpr uint16_t kTypeClassDataItem = 0x2000;
+constexpr uint16_t kTypeCodeItem = 0x2001;
+constexpr uint16_t kTypeStringDataItem = 0x2002;
+constexpr uint16_t kTypeDebugInfoItem = 0x2003;
+constexpr uint16_t kTypeAnnotationItem = 0x2004;
+constexpr uint16_t kTypeEncodedArrayItem = 0x2005;
+constexpr uint16_t kTypeAnnotationsDirectoryItem = 0x2006;
+
+#pragma pack(pop)
+
+}  // namespace dex
+}  // namespace zucchini
+
+#endif  // COMPONENTS_ZUCCHINI_TYPE_DEX_H_