Port Android relocation packer to chromium build

third_party/android_platform/bionic/tools/relocation_packer/src/delta_encoder.cc

Index: third_party/android_platform/bionic/tools/relocation_packer/src/delta_encoder.cc
diff --git a/third_party/android_platform/bionic/tools/relocation_packer/src/delta_encoder.cc b/third_party/android_platform/bionic/tools/relocation_packer/src/delta_encoder.cc
new file mode 100644
index 0000000000000000000000000000000000000000..8349d7c64e552d3ceec86e56a30439be642a19b8
--- /dev/null
+++ b/third_party/android_platform/bionic/tools/relocation_packer/src/delta_encoder.cc
@@ -0,0 +1,307 @@
+// Copyright 2014 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 "delta_encoder.h"
+
+#include <vector>
+
+#include "debug.h"
+
+static constexpr uint32_t RELOCATION_GROUPED_BY_INFO_FLAG = 1;
+static constexpr uint32_t RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG = 2;
+static constexpr uint32_t RELOCATION_GROUPED_BY_ADDEND_FLAG = 4;
+static constexpr uint32_t RELOCATION_GROUP_HAS_ADDEND_FLAG = 8;
+
+static bool is_relocation_grouped_by_info(uint64_t flags) {
+  return (flags & RELOCATION_GROUPED_BY_INFO_FLAG) != 0;
+}
+
+static bool is_relocation_grouped_by_offset_delta(uint64_t flags) {
+  return (flags & RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG) != 0;
+}
+
+static bool is_relocation_grouped_by_addend(uint64_t flags) {
+  return (flags & RELOCATION_GROUPED_BY_ADDEND_FLAG) != 0;
+}
+
+static bool is_relocation_group_has_addend(uint64_t flags) {
+  return (flags & RELOCATION_GROUP_HAS_ADDEND_FLAG) != 0;
+}
+
+namespace relocation_packer {
+
+// Encode relocations into a delta encoded (packed) representation.
+template <typename ELF>
+void RelocationDeltaCodec<ELF>::Encode(const std::vector<ElfRela>& relocations,
+                                       std::vector<ElfAddr>* packed) {
+  if (relocations.size() == 0)
+    return;
+
+  // Start with the relocation count, then append groups
+  // TODO(dimitry): we might want to move it to DT_ANDROID_RELCOUNT section
+  packed->push_back(static_cast<ElfAddr>(relocations.size()));
+
+  // lets write starting offset (offset of the first reloc - first delta)
+  ElfAddr start_offset = relocations.size() > 1 ?
+      relocations[0].r_offset - (relocations[1].r_offset - relocations[0].r_offset) :
+      relocations[0].r_offset;
+
+  packed->push_back(start_offset);
+
+  // this one is used to calculate delta
+  ElfAddr previous_addend = 0;
+  ElfAddr previous_offset = start_offset;
+
+  for (size_t group_start = 0; group_start < relocations.size(); ) {
+    ElfAddr group_flags = 0;
+    ElfAddr group_offset_delta = 0;
+    ElfAddr group_addend = 0;
+    ElfAddr group_info = 0;
+
+    ElfAddr group_size = 0;
+
+    DetectGroup(relocations, group_start, previous_offset, &group_size, &group_flags,
+        &group_offset_delta, &group_info, &group_addend);
+
+    // write the group header
+    packed->push_back(group_size);
+    packed->push_back(group_flags);
+
+    if (is_relocation_grouped_by_offset_delta(group_flags)) {
+      packed->push_back(group_offset_delta);
+    }
+
+    if (is_relocation_grouped_by_info(group_flags)) {
+      packed->push_back(group_info);
+    }
+
+    if (is_relocation_group_has_addend(group_flags) &&
+        is_relocation_grouped_by_addend(group_flags)) {
+      packed->push_back(group_addend - previous_addend);
+      previous_addend = group_addend;
+    }
+
+    for (size_t i = 0; i < static_cast<size_t>(group_size); ++i) {
+      CHECK((group_start + i) < relocations.size());
+      const ElfRela* relocation = &relocations[group_start + i];
+
+      if (!is_relocation_grouped_by_offset_delta(group_flags)) {
+        packed->push_back(relocation->r_offset - previous_offset);
+      }
+      previous_offset = relocation->r_offset;
+
+      if (!is_relocation_grouped_by_info(group_flags)) {
+        packed->push_back(relocation->r_info);
+      }
+
+      if (is_relocation_group_has_addend(group_flags) &&
+          !is_relocation_grouped_by_addend(group_flags)) {
+        packed->push_back(relocation->r_addend - previous_addend);
+        previous_addend = relocation->r_addend;
+      }
+    }
+
+    // If the relocation group does not have an addend - reset it to 0
+    // to simplify addend computation for the group following this one.
+    if (!is_relocation_group_has_addend(group_flags)) {
+      previous_addend = 0;
+    }
+
+    group_start += group_size;
+  }
+}
+
+// Decode relocations from a delta encoded (packed) representation.
+template <typename ELF>
+void RelocationDeltaCodec<ELF>::Decode(const std::vector<ElfAddr>& packed,
+                                       std::vector<ElfRela>* relocations) {
+  if (packed.size() < 5) {
+    return;
+  }
+
+  size_t ndx = 0;
+  ElfAddr current_count = 0;
+  ElfAddr total_count = packed[ndx++];
+
+  ElfAddr offset = packed[ndx++];
+  ElfAddr info = 0;
+  ElfAddr addend = 0;
+
+  while(current_count < total_count) {
+    // read group
+    ElfAddr group_size = packed[ndx++];
+    ElfAddr group_flags = packed[ndx++];
+    ElfAddr group_offset_delta = 0;
+
+    if (is_relocation_grouped_by_offset_delta(group_flags)) {
+      group_offset_delta = packed[ndx++];
+    }
+
+    if (is_relocation_grouped_by_info(group_flags)) {
+      info = packed[ndx++];
+    }
+
+    if (is_relocation_group_has_addend(group_flags) &&
+        is_relocation_grouped_by_addend(group_flags)) {
+      addend += packed[ndx++];
+    }
+
+    // now read not grouped info
+    for (ElfAddr i = 0; i<group_size; ++i) {
+      if (is_relocation_grouped_by_offset_delta(group_flags)) {
+        offset += group_offset_delta;
+      } else {
+        offset += packed[ndx++];
+      }
+
+      if (!is_relocation_grouped_by_info(group_flags)) {
+        info = packed[ndx++];
+      }
+
+      if (is_relocation_group_has_addend(group_flags) &&
+          !is_relocation_grouped_by_addend(group_flags)) {
+        addend += packed[ndx++];
+      }
+
+      ElfRela reloc;
+      reloc.r_offset = offset;
+      reloc.r_info = info;
+      reloc.r_addend = is_relocation_group_has_addend(group_flags) ? addend : 0;
+      relocations->push_back(reloc);
+    }
+
+    if (!is_relocation_group_has_addend(group_flags)) {
+      addend = 0;
+    }
+
+    current_count += group_size;
+  }
+}
+
+// This function detects a way to group reloc_one and reloc_two, sets up group_flags
+// and initializes values for corresponding group_ fields. For example if relocations
+// can be grouped by r_info the function will set group_info variable.
+template <typename ELF>
+void RelocationDeltaCodec<ELF>::DetectGroupFields(const ElfRela& reloc_one,
+                                                  const ElfRela& reloc_two,
+                                                  ElfAddr current_offset_delta,
+                                                  ElfAddr* group_flags,
+                                                  ElfAddr* group_offset_delta,
+                                                  ElfAddr* group_info,
+                                                  ElfAddr* group_addend) {
+  *group_flags = 0;
+
+  const ElfAddr offset_delta = static_cast<ElfAddr>(reloc_two.r_offset) -
+      static_cast<ElfAddr>(reloc_one.r_offset);
+
+  if (offset_delta == current_offset_delta) {
+    *group_flags |= RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG;
+    if (group_offset_delta != nullptr) {
+      *group_offset_delta = current_offset_delta;
+    }
+  }
+
+  if (reloc_one.r_info == reloc_two.r_info) {
+    *group_flags |= RELOCATION_GROUPED_BY_INFO_FLAG;
+    if (group_info != nullptr) {
+      *group_info = reloc_one.r_info;
+    }
+  }
+
+  if (reloc_one.r_addend != 0 || reloc_two.r_addend != 0) {
+    *group_flags |= RELOCATION_GROUP_HAS_ADDEND_FLAG;
+    if (reloc_one.r_addend == reloc_two.r_addend) {
+      *group_flags |= RELOCATION_GROUPED_BY_ADDEND_FLAG;
+      if (group_addend != nullptr) {
+        *group_addend = reloc_one.r_addend;
+      }
+    }
+  }
+}
+
+// This function is used to detect if there is better group available
+// during RelocationDeltaCodec<ELF>::DetectGroup processing.
+// Current implementation prefers having groups without addend (== zero addend)
+// to any other groups field with the ratio 3:1. This is because addend tends
+// to be more unevenly distributed than other fields.
+static uint32_t group_weight(uint64_t flags) {
+  uint32_t weight = 0;
+  if (!is_relocation_group_has_addend(flags)) {
+    weight += 3;
+  } else if (is_relocation_grouped_by_addend(flags)) {
+    weight += 1;
+  }
+
+  if (is_relocation_grouped_by_offset_delta(flags)) {
+    weight += 1;
+  }
+
+  if (is_relocation_grouped_by_info(flags)) {
+    weight += 1;
+  }
+
+  return weight;
+}
+
+template <typename ELF>
+void RelocationDeltaCodec<ELF>::DetectGroup(const std::vector<ElfRela>& relocations,
+                                          size_t group_starts_with, ElfAddr previous_offset,
+                                          ElfAddr* group_size, ElfAddr* group_flags,
+                                          ElfAddr* group_offset_delta, ElfAddr* group_info,
+                                          ElfAddr* group_addend) {
+  CHECK(group_starts_with < relocations.size());
+  CHECK(group_flags != nullptr);
+
+  const ElfRela& reloc_one = relocations[group_starts_with++];
+  if (group_starts_with == relocations.size()) {
+    *group_flags = reloc_one.r_addend == 0 ? 0 : RELOCATION_GROUP_HAS_ADDEND_FLAG;
+    *group_size = 1;
+    return;
+  }
+
+  const ElfAddr offset_delta = reloc_one.r_offset - previous_offset;
+
+  // detect group_flags
+  DetectGroupFields(reloc_one, relocations[group_starts_with], offset_delta, group_flags,
+      group_offset_delta, group_info, group_addend);
+
+  if (group_starts_with + 1 == relocations.size()) {
+    *group_size = 2;
+    return;
+  }
+
+  ElfAddr cnt = 1;
+  for (size_t i = group_starts_with; i < relocations.size() - 1; ++i) {
+    ElfAddr candidate_flags;
+    // check if next group (reloc_current; reloc_next) has better grouped_by flags
+    DetectGroupFields(relocations[i], relocations[i+1], offset_delta, &candidate_flags,
+        nullptr, nullptr, nullptr);
+
+    if (group_weight(*group_flags) < group_weight(candidate_flags)) {
+      break;
+    }
+    cnt++;
+
+    if (candidate_flags != *group_flags) {
+      break;
+    }
+
+    if (i + 1 == relocations.size() - 1) { // last one
+      cnt++;
+    }
+  }
+
+  // if as a result of checking candidates we ended up with cnt == 1
+  // reset flags to the default state
+  if (cnt == 1) {
+    *group_flags = reloc_one.r_addend == 0 ? 0 : RELOCATION_GROUP_HAS_ADDEND_FLAG;
+  }
+
+  *group_size = cnt;
+}
+
+template class RelocationDeltaCodec<ELF32_traits>;
+template class RelocationDeltaCodec<ELF64_traits>;
+
+}  // namespace relocation_packer