Always use signed leb128 encoding

 According to runs on /system/lib there using
 unsigned leb128 does not save us any additional
 space. In order to keep packing as simple as
 possible switch to using signed leb128 for
 everything.

Bug: http://b/18051137
Change-Id: I1a47cb9eb2175895b3c3f7c13b4c6b1060de86c0

11 files changed, 50 insertions, 317 deletions

diff --git a/tools/relocation_packer/Android.mk b/tools/relocation_packer/Android.mk
index eabe0da..75dba71 100644
--- a/tools/relocation_packer/Android.mk
+++ b/tools/relocation_packer/Android.mk
@@ -26,7 +26,6 @@ LOCAL_SRC_FILES := \
   src/debug.cc \
   src/delta_encoder.cc \
   src/elf_file.cc \
-  src/leb128.cc \
   src/packer.cc \
   src/sleb128.cc \
 
@@ -67,7 +66,6 @@ LOCAL_SRC_FILES := \
   src/debug_unittest.cc \
   src/delta_encoder_unittest.cc \
   src/elf_file_unittest.cc \
-  src/leb128_unittest.cc \
   src/sleb128_unittest.cc \
   src/packer_unittest.cc \
 
diff --git a/tools/relocation_packer/src/elf_file.cc b/tools/relocation_packer/src/elf_file.cc
index 6843f5b..11af9ed 100644
--- a/tools/relocation_packer/src/elf_file.cc
+++ b/tools/relocation_packer/src/elf_file.cc
@@ -190,6 +190,7 @@ bool ElfFile<ELF>::Load() {
   // these; both is unsupported.
   bool has_rel_relocations = false;
   bool has_rela_relocations = false;
+  bool has_android_relocations = false;
 
   Elf_Scn* section = NULL;
   while ((section = elf_nextscn(elf, section)) != nullptr) {
@@ -209,6 +210,11 @@ bool ElfFile<ELF>::Load() {
     if ((name == ".rel.dyn" || name == ".rela.dyn") &&
         section_header->sh_size > 0) {
       found_relocations_section = section;
+
+      // Note if relocation section is already packed
+      has_android_relocations =
+          section_header->sh_type == SHT_ANDROID_REL ||
+          section_header->sh_type == SHT_ANDROID_RELA;
     }
 
     if (section_header->sh_offset == dynamic_program_header->p_offset) {
@@ -250,6 +256,7 @@ bool ElfFile<ELF>::Load() {
   relocations_section_ = found_relocations_section;
   dynamic_section_ = found_dynamic_section;
   relocations_type_ = has_rel_relocations ? REL : RELA;
+  has_android_relocations_ = has_android_relocations;
   return true;
 }
 
@@ -610,10 +617,15 @@ template <typename ELF>
 bool ElfFile<ELF>::PackTypedRelocations(std::vector<typename ELF::Rela>* relocations) {
   typedef typename ELF::Rela Rela;
 
+  if (has_android_relocations_) {
+    LOG(ERROR) << "Relocation table is already packed";
+    return false;
+  }
+
   // If no relocations then we have nothing packable.  Perhaps
   // the shared object has already been packed?
   if (relocations->empty()) {
-    LOG(ERROR) << "No relocations found (already packed?)";
+    LOG(ERROR) << "No relocations found";
     return false;
   }
 
@@ -737,7 +749,7 @@ bool ElfFile<ELF>::UnpackRelocations() {
       packed.size() > 3 &&
       packed[0] == 'A' &&
       packed[1] == 'P' &&
-      (packed[2] == 'U' || packed[2] == 'S') &&
+      packed[2] == 'S' &&
       packed[3] == '2') {
     LOG(INFO) << "Relocations   : " << (relocations_type_ == REL ? "REL" : "RELA");
   } else {
diff --git a/tools/relocation_packer/src/elf_file.h b/tools/relocation_packer/src/elf_file.h
index a749d50..d6acc76 100644
--- a/tools/relocation_packer/src/elf_file.h
+++ b/tools/relocation_packer/src/elf_file.h
@@ -36,7 +36,7 @@ class ElfFile {
   explicit ElfFile(int fd)
       : fd_(fd), is_padding_relocations_(false), elf_(NULL),
         relocations_section_(NULL), dynamic_section_(NULL),
-        relocations_type_(NONE) {}
+        relocations_type_(NONE), has_android_relocations_(false) {}
   ~ElfFile() {}
 
   // Set padding mode.  When padding, PackRelocations() will not shrink
@@ -111,6 +111,9 @@ class ElfFile {
 
   // Relocation type found, assigned by Load().
   relocations_type_t relocations_type_;
+
+  // Elf-file has android relocations section
+  bool has_android_relocations_;
 };
 
 }  // namespace relocation_packer
diff --git a/tools/relocation_packer/src/elf_file_unittest.cc b/tools/relocation_packer/src/elf_file_unittest.cc
index 434f101..5271eef 100644
--- a/tools/relocation_packer/src/elf_file_unittest.cc
+++ b/tools/relocation_packer/src/elf_file_unittest.cc
@@ -175,13 +175,19 @@ static void RunPackRelocationsTestFor(const std::string& arch) {
 
 namespace relocation_packer {
 
-TEST(ElfFile, PackRelocations) {
+TEST(ElfFile, PackRelocationsArm32) {
   RunPackRelocationsTestFor("arm32");
+}
+
+TEST(ElfFile, PackRelocationsArm64) {
   RunPackRelocationsTestFor("arm64");
 }
 
-TEST(ElfFile, UnpackRelocations) {
+TEST(ElfFile, UnpackRelocationsArm32) {
   RunUnpackRelocationsTestFor("arm32");
+}
+
+TEST(ElfFile, UnpackRelocationsArm64) {
   RunUnpackRelocationsTestFor("arm64");
 }
 
diff --git a/tools/relocation_packer/src/leb128.cc b/tools/relocation_packer/src/leb128.cc
deleted file mode 100644
index 101c557..0000000
--- a/tools/relocation_packer/src/leb128.cc
+++ /dev/null
@@ -1,87 +0,0 @@
-// 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 "leb128.h"
-
-#include <stdint.h>
-#include <vector>
-
-#include "elf_traits.h"
-
-namespace relocation_packer {
-
-// Empty constructor and destructor to silence chromium-style.
-template <typename uint_t>
-Leb128Encoder<uint_t>::Leb128Encoder() { }
-
-template <typename uint_t>
-Leb128Encoder<uint_t>::~Leb128Encoder() { }
-
-// Add a single value to the encoding.  Values are encoded with variable
-// length.  The least significant 7 bits of each byte hold 7 bits of data,
-// and the most significant bit is set on each byte except the last.
-template <typename uint_t>
-void Leb128Encoder<uint_t>::Enqueue(uint_t value) {
-  uint_t uvalue = static_cast<uint_t>(value);
-  do {
-    const uint8_t byte = uvalue & 127;
-    uvalue >>= 7;
-    encoding_.push_back((uvalue ? 128 : 0) | byte);
-  } while (uvalue);
-}
-
-// Add a vector of values to the encoding.
-template <typename uint_t>
-void Leb128Encoder<uint_t>::EnqueueAll(const std::vector<uint_t>& values) {
-  for (size_t i = 0; i < values.size(); ++i) {
-    Enqueue(values[i]);
-  }
-}
-
-// Create a new decoder for the given encoded stream.
-template <typename uint_t>
-Leb128Decoder<uint_t>::Leb128Decoder(const std::vector<uint8_t>& encoding, size_t start_with) {
-  encoding_ = encoding;
-  cursor_ = start_with;
-}
-
-// Empty destructor to silence chromium-style.
-template <typename uint_t>
-Leb128Decoder<uint_t>::~Leb128Decoder() { }
-
-// Decode and retrieve a single value from the encoding.  Read forwards until
-// a byte without its most significant bit is found, then read the 7 bit
-// fields of the bytes spanned to re-form the value.
-template <typename uint_t>
-uint_t Leb128Decoder<uint_t>::Dequeue() {
-  uint_t value = 0;
-
-  size_t shift = 0;
-  uint8_t byte;
-
-  // Loop until we reach a byte with its high order bit clear.
-  do {
-    byte = encoding_[cursor_++];
-    value |= static_cast<uint_t>(byte & 127) << shift;
-    shift += 7;
-  } while (byte & 128);
-
-  return value;
-}
-
-// Decode and retrieve all remaining values from the encoding.
-template <typename uint_t>
-void Leb128Decoder<uint_t>::DequeueAll(std::vector<uint_t>* values) {
-  while (cursor_ < encoding_.size()) {
-    values->push_back(Dequeue());
-  }
-}
-
-template class Leb128Encoder<uint32_t>;
-template class Leb128Encoder<uint64_t>;
-
-template class Leb128Decoder<uint32_t>;
-template class Leb128Decoder<uint64_t>;
-
-}  // namespace relocation_packer
diff --git a/tools/relocation_packer/src/leb128.h b/tools/relocation_packer/src/leb128.h
deleted file mode 100644
index 67fc4b8..0000000
--- a/tools/relocation_packer/src/leb128.h
+++ /dev/null
@@ -1,75 +0,0 @@
-// 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.
-
-// LEB128 encoder and decoder for packed relative relocations.
-//
-// Packed relocations consist of a large number of relatively small
-// integer values.  Encoding these as LEB128 saves space.
-//
-// For more on LEB128 see http://en.wikipedia.org/wiki/LEB128.
-
-#ifndef TOOLS_RELOCATION_PACKER_SRC_LEB128_H_
-#define TOOLS_RELOCATION_PACKER_SRC_LEB128_H_
-
-#include <stdint.h>
-#include <vector>
-
-#include "elf_traits.h"
-
-namespace relocation_packer {
-
-// Encode packed words as a LEB128 byte stream.
-template <typename uint_t>
-class Leb128Encoder {
- public:
-  // Explicit (but empty) constructor and destructor, for chromium-style.
-  Leb128Encoder();
-  ~Leb128Encoder();
-
-  // Add a value to the encoding stream.
-  // |value| is the unsigned int to add.
-  void Enqueue(uint_t value);
-
-  // Add a vector of values to the encoding stream.
-  // |values| is the vector of unsigned ints to add.
-  void EnqueueAll(const std::vector<uint_t>& values);
-
-  // Retrieve the encoded representation of the values.
-  // |encoding| is the returned vector of encoded data.
-  void GetEncoding(std::vector<uint8_t>* encoding) { *encoding = encoding_; }
-
- private:
-  // Growable vector holding the encoded LEB128 stream.
-  std::vector<uint8_t> encoding_;
-};
-
-// Decode a LEB128 byte stream to produce packed words.
-template <typename uint_t>
-class Leb128Decoder {
- public:
-  // Create a new decoder for the given encoded stream.
-  // |encoding| is the vector of encoded data.
-  explicit Leb128Decoder(const std::vector<uint8_t>& encoding, size_t start_with);
-
-  // Explicit (but empty) destructor, for chromium-style.
-  ~Leb128Decoder();
-
-  // Retrieve the next value from the encoded stream.
-  uint_t Dequeue();
-
-  // Retrieve all remaining values from the encoded stream.
-  // |values| is the vector of decoded data.
-  void DequeueAll(std::vector<uint_t>* values);
-
- private:
-  // Encoded LEB128 stream.
-  std::vector<uint8_t> encoding_;
-
-  // Cursor indicating the current stream retrieval point.
-  size_t cursor_;
-};
-
-}  // namespace relocation_packer
-
-#endif  // TOOLS_RELOCATION_PACKER_SRC_LEB128_H_
diff --git a/tools/relocation_packer/src/leb128_unittest.cc b/tools/relocation_packer/src/leb128_unittest.cc
deleted file mode 100644
index 8a7028c..0000000
--- a/tools/relocation_packer/src/leb128_unittest.cc
+++ /dev/null
@@ -1,111 +0,0 @@
-// 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 "leb128.h"
-
-#include <vector>
-#include "gtest/gtest.h"
-
-namespace relocation_packer {
-
-TEST(Leb128, Encoder64) {
-  std::vector<uint64_t> values;
-  values.push_back(624485);
-  values.push_back(0);
-  values.push_back(1);
-  values.push_back(127);
-  values.push_back(128);
-
-  Leb128Encoder<uint64_t> encoder;
-  encoder.EnqueueAll(values);
-
-  encoder.Enqueue(4294967295);
-  encoder.Enqueue(18446744073709551615ul);
-
-  std::vector<uint8_t> encoding;
-  encoder.GetEncoding(&encoding);
-
-  EXPECT_EQ(23U, encoding.size());
-  // 624485
-  EXPECT_EQ(0xe5, encoding[0]);
-  EXPECT_EQ(0x8e, encoding[1]);
-  EXPECT_EQ(0x26, encoding[2]);
-  // 0
-  EXPECT_EQ(0x00, encoding[3]);
-  // 1
-  EXPECT_EQ(0x01, encoding[4]);
-  // 127
-  EXPECT_EQ(0x7f, encoding[5]);
-  // 128
-  EXPECT_EQ(0x80, encoding[6]);
-  EXPECT_EQ(0x01, encoding[7]);
-  // 4294967295
-  EXPECT_EQ(0xff, encoding[8]);
-  EXPECT_EQ(0xff, encoding[9]);
-  EXPECT_EQ(0xff, encoding[10]);
-  EXPECT_EQ(0xff, encoding[11]);
-  EXPECT_EQ(0x0f, encoding[12]);
-  // 18446744073709551615
-  EXPECT_EQ(0xff, encoding[13]);
-  EXPECT_EQ(0xff, encoding[14]);
-  EXPECT_EQ(0xff, encoding[15]);
-  EXPECT_EQ(0xff, encoding[16]);
-  EXPECT_EQ(0xff, encoding[17]);
-  EXPECT_EQ(0xff, encoding[18]);
-  EXPECT_EQ(0xff, encoding[19]);
-  EXPECT_EQ(0xff, encoding[20]);
-  EXPECT_EQ(0xff, encoding[21]);
-  EXPECT_EQ(0x01, encoding[22]);
-}
-
-TEST(Leb128, Decoder64) {
-  std::vector<uint8_t> encoding;
-  // 624485
-  encoding.push_back(0xe5);
-  encoding.push_back(0x8e);
-  encoding.push_back(0x26);
-  // 0
-  encoding.push_back(0x00);
-  // 1
-  encoding.push_back(0x01);
-  // 127
-  encoding.push_back(0x7f);
-  // 128
-  encoding.push_back(0x80);
-  encoding.push_back(0x01);
-  // 4294967295
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0x0f);
-  // 18446744073709551615
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0xff);
-  encoding.push_back(0x01);
-
-  Leb128Decoder<uint64_t> decoder(encoding, 0);
-
-  EXPECT_EQ(624485U, decoder.Dequeue());
-
-  std::vector<uint64_t> dequeued;
-  decoder.DequeueAll(&dequeued);
-
-  EXPECT_EQ(6U, dequeued.size());
-  EXPECT_EQ(0U, dequeued[0]);
-  EXPECT_EQ(1U, dequeued[1]);
-  EXPECT_EQ(127U, dequeued[2]);
-  EXPECT_EQ(128U, dequeued[3]);
-  EXPECT_EQ(4294967295U, dequeued[4]);
-  EXPECT_EQ(18446744073709551615UL, dequeued[5]);
-}
-
-}  // namespace relocation_packer
diff --git a/tools/relocation_packer/src/packer.cc b/tools/relocation_packer/src/packer.cc
index 8e30612..433611f 100644
--- a/tools/relocation_packer/src/packer.cc
+++ b/tools/relocation_packer/src/packer.cc
@@ -9,7 +9,6 @@
 #include "debug.h"
 #include "delta_encoder.h"
 #include "elf_traits.h"
-#include "leb128.h"
 #include "sleb128.h"
 
 namespace relocation_packer {
@@ -28,32 +27,17 @@ void RelocationPacker<ELF>::PackRelocations(const std::vector<typename ELF::Rela
     return;
 
   Sleb128Encoder<typename ELF::Addr> sleb128_encoder;
-  Leb128Encoder<typename ELF::Addr> leb128_encoder;
 
-  std::vector<uint8_t> leb128_packed;
   std::vector<uint8_t> sleb128_packed;
 
-  leb128_encoder.EnqueueAll(packed_words);
-  leb128_encoder.GetEncoding(&leb128_packed);
-
   sleb128_encoder.EnqueueAll(packed_words);
   sleb128_encoder.GetEncoding(&sleb128_packed);
 
-  // TODO (simonb): Estimate savings on current android system image and consider using
-  // one encoder for all packed relocations to reduce complexity.
-  if (leb128_packed.size() <= sleb128_packed.size()) {
-    packed->push_back('A');
-    packed->push_back('P');
-    packed->push_back('U');
-    packed->push_back('2');
-    packed->insert(packed->end(), leb128_packed.begin(), leb128_packed.end());
-  } else {
-    packed->push_back('A');
-    packed->push_back('P');
-    packed->push_back('S');
-    packed->push_back('2');
-    packed->insert(packed->end(), sleb128_packed.begin(), sleb128_packed.end());
-  }
+  packed->push_back('A');
+  packed->push_back('P');
+  packed->push_back('S');
+  packed->push_back('2');
+  packed->insert(packed->end(), sleb128_packed.begin(), sleb128_packed.end());
 }
 
 // Unpack relative relocations from a run-length encoded packed
@@ -67,16 +51,11 @@ void RelocationPacker<ELF>::UnpackRelocations(
   CHECK(packed.size() > 4 &&
         packed[0] == 'A' &&
         packed[1] == 'P' &&
-        (packed[2] == 'U' || packed[2] == 'S') &&
+        packed[2] == 'S' &&
         packed[3] == '2');
 
-  if (packed[2] == 'U') {
-    Leb128Decoder<typename ELF::Addr> decoder(packed, 4);
-    decoder.DequeueAll(&packed_words);
-  } else {
-    Sleb128Decoder<typename ELF::Addr> decoder(packed, 4);
-    decoder.DequeueAll(&packed_words);
-  }
+  Sleb128Decoder<typename ELF::Addr> decoder(packed, 4);
+  decoder.DequeueAll(&packed_words);
 
   RelocationDeltaCodec<ELF> codec;
   codec.Decode(packed_words, relocations);
diff --git a/tools/relocation_packer/src/packer_unittest.cc b/tools/relocation_packer/src/packer_unittest.cc
index 8dddd8b..424b92c 100644
--- a/tools/relocation_packer/src/packer_unittest.cc
+++ b/tools/relocation_packer/src/packer_unittest.cc
@@ -39,6 +39,7 @@ template <typename ELF>
 static void DoPackNoAddend() {
   std::vector<typename ELF::Rela> relocations;
   std::vector<uint8_t> packed;
+  bool is_32 = sizeof(typename ELF::Addr) == 4;
   // Initial relocation.
   AddRelocation<ELF>(0xd1ce0000, 0x11, 0, &relocations);
   // Two more relocations, 4 byte deltas.
@@ -59,16 +60,16 @@ static void DoPackNoAddend() {
   size_t ndx = 0;
   EXPECT_EQ('A', packed[ndx++]);
   EXPECT_EQ('P', packed[ndx++]);
-  EXPECT_EQ('U', packed[ndx++]);
+  EXPECT_EQ('S', packed[ndx++]);
   EXPECT_EQ('2', packed[ndx++]);
   // relocation count
   EXPECT_EQ(6, packed[ndx++]);
-  // base relocation = 0xd1cdfffc -> fc, ff, b7, 8e, 0d
+  // base relocation = 0xd1cdfffc -> fc, ff, b7, 8e, 7d/0d (32/64bit)
   EXPECT_EQ(0xfc, packed[ndx++]);
   EXPECT_EQ(0xff, packed[ndx++]);
   EXPECT_EQ(0xb7, packed[ndx++]);
   EXPECT_EQ(0x8e, packed[ndx++]);
-  EXPECT_EQ(0x0d, packed[ndx++]);
+  EXPECT_EQ(is_32 ? 0x7d : 0x0d, packed[ndx++]);
   // first group
   EXPECT_EQ(3, packed[ndx++]);  // size
   EXPECT_EQ(3, packed[ndx++]); // flags
@@ -83,8 +84,11 @@ static void DoPackNoAddend() {
   EXPECT_EQ(ndx, packed.size());
 }
 
-TEST(Packer, PackNoAddend) {
+TEST(Packer, PackNoAddend32) {
   DoPackNoAddend<ELF32_traits>();
+}
+
+TEST(Packer, PackNoAddend64) {
   DoPackNoAddend<ELF64_traits>();
 }
 
@@ -92,18 +96,19 @@ template <typename ELF>
 static void DoUnpackNoAddend() {
   std::vector<typename ELF::Rela> relocations;
   std::vector<uint8_t> packed;
+  bool is_32 = sizeof(typename ELF::Addr) == 4;
   packed.push_back('A');
   packed.push_back('P');
-  packed.push_back('U');
+  packed.push_back('S');
   packed.push_back('2');
   // relocation count
   packed.push_back(6);
-  // base relocation = 0xd1cdfffc -> fc, ff, b7, 8e, 0d
+  // base relocation = 0xd1cdfffc -> fc, ff, b7, 8e, 7d/0d (32/64bit)
   packed.push_back(0xfc);
   packed.push_back(0xff);
   packed.push_back(0xb7);
   packed.push_back(0x8e);
-  packed.push_back(0x0d);
+  packed.push_back(is_32 ? 0x7d : 0x0d);
   // first group
   packed.push_back(3);  // size
   packed.push_back(3); // flags
@@ -131,8 +136,11 @@ static void DoUnpackNoAddend() {
   EXPECT_EQ(ndx, relocations.size());
 }
 
-TEST(Packer, UnpackNoAddend) {
+TEST(Packer, UnpackNoAddend32) {
   DoUnpackNoAddend<ELF32_traits>();
+}
+
+TEST(Packer, UnpackNoAddend64) {
   DoUnpackNoAddend<ELF64_traits>();
 }
 
diff --git a/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm32_packed.so b/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm32_packed.so
index d97ef82..6ac2eef 100755
--- a/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm32_packed.so
+++ b/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm32_packed.so
diff --git a/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm64_packed.so b/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm64_packed.so
index e44e459..a2b0039 100755
--- a/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm64_packed.so
+++ b/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm64_packed.so