diff --git a/compiler/dex/quick/codegen_util.cc b/compiler/dex/quick/codegen_util.cc
index 4bc0b35..92b24e1 100644
--- a/compiler/dex/quick/codegen_util.cc
+++ b/compiler/dex/quick/codegen_util.cc
@@ -556,12 +556,34 @@
 
 
 void Mir2Lir::CreateMappingTables() {
+  uint32_t pc2dex_data_size = 0u;
+  uint32_t pc2dex_entries = 0u;
+  uint32_t pc2dex_offset = 0u;
+  uint32_t pc2dex_dalvik_offset = 0u;
+  uint32_t dex2pc_data_size = 0u;
+  uint32_t dex2pc_entries = 0u;
+  uint32_t dex2pc_offset = 0u;
+  uint32_t dex2pc_dalvik_offset = 0u;
   for (LIR* tgt_lir = first_lir_insn_; tgt_lir != NULL; tgt_lir = NEXT_LIR(tgt_lir)) {
     if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoSafepointPC)) {
+      pc2dex_entries += 1;
+      DCHECK(pc2dex_offset <= tgt_lir->offset);
+      pc2dex_data_size += UnsignedLeb128Size(tgt_lir->offset - pc2dex_offset);
+      pc2dex_data_size += SignedLeb128Size(static_cast<int32_t>(tgt_lir->dalvik_offset) -
+                                           static_cast<int32_t>(pc2dex_dalvik_offset));
+      pc2dex_offset = tgt_lir->offset;
+      pc2dex_dalvik_offset = tgt_lir->dalvik_offset;
       pc2dex_mapping_table_.push_back(tgt_lir->offset);
       pc2dex_mapping_table_.push_back(tgt_lir->dalvik_offset);
     }
     if (!tgt_lir->flags.is_nop && (tgt_lir->opcode == kPseudoExportedPC)) {
+      dex2pc_entries += 1;
+      DCHECK(dex2pc_offset <= tgt_lir->offset);
+      dex2pc_data_size += UnsignedLeb128Size(tgt_lir->offset - dex2pc_offset);
+      dex2pc_data_size += SignedLeb128Size(static_cast<int32_t>(tgt_lir->dalvik_offset) -
+                                           static_cast<int32_t>(dex2pc_dalvik_offset));
+      dex2pc_offset = tgt_lir->offset;
+      dex2pc_dalvik_offset = tgt_lir->dalvik_offset;
       dex2pc_mapping_table_.push_back(tgt_lir->offset);
       dex2pc_mapping_table_.push_back(tgt_lir->dalvik_offset);
     }
@@ -569,32 +591,57 @@
   if (kIsDebugBuild) {
     CHECK(VerifyCatchEntries());
   }
-  CHECK_EQ(pc2dex_mapping_table_.size() & 1, 0U);
-  CHECK_EQ(dex2pc_mapping_table_.size() & 1, 0U);
-  uint32_t total_entries = (pc2dex_mapping_table_.size() + dex2pc_mapping_table_.size()) / 2;
-  uint32_t pc2dex_entries = pc2dex_mapping_table_.size() / 2;
-  encoded_mapping_table_.PushBack(total_entries);
-  encoded_mapping_table_.PushBack(pc2dex_entries);
-  encoded_mapping_table_.InsertBack(pc2dex_mapping_table_.begin(), pc2dex_mapping_table_.end());
-  encoded_mapping_table_.InsertBack(dex2pc_mapping_table_.begin(), dex2pc_mapping_table_.end());
+  DCHECK_EQ(pc2dex_mapping_table_.size(), 2u * pc2dex_entries);
+  DCHECK_EQ(dex2pc_mapping_table_.size(), 2u * dex2pc_entries);
+
+  uint32_t total_entries = pc2dex_entries + dex2pc_entries;
+  uint32_t hdr_data_size = UnsignedLeb128Size(total_entries) + UnsignedLeb128Size(pc2dex_entries);
+  uint32_t data_size = hdr_data_size + pc2dex_data_size + dex2pc_data_size;
+  encoded_mapping_table_.Reserve(data_size);
+  encoded_mapping_table_.PushBackUnsigned(total_entries);
+  encoded_mapping_table_.PushBackUnsigned(pc2dex_entries);
+
+  dex2pc_offset = 0u;
+  dex2pc_dalvik_offset = 0u;
+  pc2dex_offset = 0u;
+  pc2dex_dalvik_offset = 0u;
+  for (uint32_t i = 0; i != pc2dex_entries; ++i) {
+    encoded_mapping_table_.PushBackUnsigned(pc2dex_mapping_table_[2 * i] - pc2dex_offset);
+    encoded_mapping_table_.PushBackSigned(static_cast<int32_t>(pc2dex_mapping_table_[2 * i + 1]) -
+                                          static_cast<int32_t>(pc2dex_dalvik_offset));
+    pc2dex_offset = pc2dex_mapping_table_[2 * i];
+    pc2dex_dalvik_offset = pc2dex_mapping_table_[2 * i + 1];
+  }
+  DCHECK(encoded_mapping_table_.GetData().size() == hdr_data_size + pc2dex_data_size);
+  for (uint32_t i = 0; i != dex2pc_entries; ++i) {
+    encoded_mapping_table_.PushBackUnsigned(dex2pc_mapping_table_[2 * i] - dex2pc_offset);
+    encoded_mapping_table_.PushBackSigned(static_cast<int32_t>(dex2pc_mapping_table_[2 * i + 1]) -
+                                          static_cast<int32_t>(dex2pc_dalvik_offset));
+    dex2pc_offset = dex2pc_mapping_table_[2 * i];
+    dex2pc_dalvik_offset = dex2pc_mapping_table_[2 * i + 1];
+  }
+  DCHECK(encoded_mapping_table_.GetData().size() == data_size);
+
   if (kIsDebugBuild) {
     // Verify the encoded table holds the expected data.
     MappingTable table(&encoded_mapping_table_.GetData()[0]);
     CHECK_EQ(table.TotalSize(), total_entries);
     CHECK_EQ(table.PcToDexSize(), pc2dex_entries);
     CHECK_EQ(table.DexToPcSize(), dex2pc_mapping_table_.size() / 2);
-    MappingTable::PcToDexIterator it = table.PcToDexBegin();
+    auto it = table.PcToDexBegin();
     for (uint32_t i = 0; i < pc2dex_mapping_table_.size(); ++i, ++it) {
       CHECK_EQ(pc2dex_mapping_table_.at(i), it.NativePcOffset());
       ++i;
       CHECK_EQ(pc2dex_mapping_table_.at(i), it.DexPc());
     }
-    MappingTable::DexToPcIterator it2 = table.DexToPcBegin();
+    CHECK(it == table.PcToDexEnd());
+    auto it2 = table.DexToPcBegin();
     for (uint32_t i = 0; i < dex2pc_mapping_table_.size(); ++i, ++it2) {
       CHECK_EQ(dex2pc_mapping_table_.at(i), it2.NativePcOffset());
       ++i;
       CHECK_EQ(dex2pc_mapping_table_.at(i), it2.DexPc());
     }
+    CHECK(it2 == table.DexToPcEnd());
   }
 }
 
@@ -986,11 +1033,11 @@
   for (uint32_t i = 0; i < fp_vmap_table_.size(); i++) {
     raw_vmap_table.push_back(fp_vmap_table_[i]);
   }
-  UnsignedLeb128EncodingVector vmap_encoder;
+  Leb128EncodingVector vmap_encoder;
   // Prefix the encoded data with its size.
-  vmap_encoder.PushBack(raw_vmap_table.size());
+  vmap_encoder.PushBackUnsigned(raw_vmap_table.size());
   for (uint16_t cur : raw_vmap_table) {
-    vmap_encoder.PushBack(cur);
+    vmap_encoder.PushBackUnsigned(cur);
   }
   CompiledMethod* result =
       new CompiledMethod(*cu_->compiler_driver, cu_->instruction_set, code_buffer_, frame_size_,
diff --git a/compiler/dex/quick/mir_to_lir.h b/compiler/dex/quick/mir_to_lir.h
index f8a2d03..92e21ff 100644
--- a/compiler/dex/quick/mir_to_lir.h
+++ b/compiler/dex/quick/mir_to_lir.h
@@ -828,7 +828,7 @@
     int live_sreg_;
     CodeBuffer code_buffer_;
     // The encoding mapping table data (dex -> pc offset and pc offset -> dex) with a size prefix.
-    UnsignedLeb128EncodingVector encoded_mapping_table_;
+    Leb128EncodingVector encoded_mapping_table_;
     std::vector<uint32_t> core_vmap_table_;
     std::vector<uint32_t> fp_vmap_table_;
     std::vector<uint8_t> native_gc_map_;
diff --git a/compiler/leb128_encoder.h b/compiler/leb128_encoder.h
index e9a1c32..fe38c2f 100644
--- a/compiler/leb128_encoder.h
+++ b/compiler/leb128_encoder.h
@@ -18,33 +18,54 @@
 #define ART_COMPILER_LEB128_ENCODER_H_
 
 #include "base/macros.h"
+#include "leb128.h"
 
 namespace art {
 
 // An encoder with an API similar to vector<uint32_t> where the data is captured in ULEB128 format.
-class UnsignedLeb128EncodingVector {
+class Leb128EncodingVector {
  public:
-  UnsignedLeb128EncodingVector() {
+  Leb128EncodingVector() {
   }
 
-  void PushBack(uint32_t value) {
-    bool done = false;
-    do {
-      uint8_t out = value & 0x7f;
-      if (out != value) {
-        data_.push_back(out | 0x80);
-        value >>= 7;
-      } else {
-        data_.push_back(out);
-        done = true;
-      }
-    } while (!done);
+  void Reserve(uint32_t size) {
+    data_.reserve(size);
+  }
+
+  void PushBackUnsigned(uint32_t value) {
+    uint8_t out = value & 0x7f;
+    value >>= 7;
+    while (value != 0) {
+      data_.push_back(out | 0x80);
+      out = value & 0x7f;
+      value >>= 7;
+    }
+    data_.push_back(out);
   }
 
   template<typename It>
-  void InsertBack(It cur, It end) {
+  void InsertBackUnsigned(It cur, It end) {
     for (; cur != end; ++cur) {
-      PushBack(*cur);
+      PushBackUnsigned(*cur);
+    }
+  }
+
+  void PushBackSigned(int32_t value) {
+    uint32_t extra_bits = static_cast<uint32_t>(value ^ (value >> 31)) >> 6;
+    uint8_t out = value & 0x7f;
+    while (extra_bits != 0u) {
+      data_.push_back(out | 0x80);
+      value >>= 7;
+      out = value & 0x7f;
+      extra_bits >>= 7;
+    }
+    data_.push_back(out);
+  }
+
+  template<typename It>
+  void InsertBackSigned(It cur, It end) {
+    for (; cur != end; ++cur) {
+      PushBackSigned(*cur);
     }
   }
 
@@ -55,7 +76,7 @@
  private:
   std::vector<uint8_t> data_;
 
-  DISALLOW_COPY_AND_ASSIGN(UnsignedLeb128EncodingVector);
+  DISALLOW_COPY_AND_ASSIGN(Leb128EncodingVector);
 };
 
 }  // namespace art
diff --git a/compiler/leb128_encoder_test.cc b/compiler/leb128_encoder_test.cc
index 4fa8075..3162ca5 100644
--- a/compiler/leb128_encoder_test.cc
+++ b/compiler/leb128_encoder_test.cc
@@ -42,11 +42,61 @@
     {0xFFFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0xF}},
 };
 
-TEST_F(Leb128Test, Singles) {
+struct DecodeSignedLeb128TestCase {
+  int32_t decoded;
+  uint8_t leb128_data[5];
+};
+
+static DecodeSignedLeb128TestCase sleb128_tests[] = {
+    {0,          {0, 0, 0, 0, 0}},
+    {1,          {1, 0, 0, 0, 0}},
+    {0x3F,       {0x3F, 0, 0, 0, 0}},
+    {0x40,       {0xC0, 0 /* sign bit */, 0, 0, 0}},
+    {0x41,       {0xC1, 0 /* sign bit */, 0, 0, 0}},
+    {0x80,       {0x80, 1, 0, 0, 0}},
+    {0xFF,       {0xFF, 1, 0, 0, 0}},
+    {0x1FFF,     {0xFF, 0x3F, 0, 0, 0}},
+    {0x2000,     {0x80, 0xC0, 0 /* sign bit */, 0, 0}},
+    {0x2001,     {0x81, 0xC0, 0 /* sign bit */, 0, 0}},
+    {0x2081,     {0x81, 0xC1, 0 /* sign bit */, 0, 0}},
+    {0x4000,     {0x80, 0x80, 1, 0, 0}},
+    {0x0FFFFF,   {0xFF, 0xFF, 0x3F, 0, 0}},
+    {0x100000,   {0x80, 0x80, 0xC0, 0 /* sign bit */, 0}},
+    {0x100001,   {0x81, 0x80, 0xC0, 0 /* sign bit */, 0}},
+    {0x100081,   {0x81, 0x81, 0xC0, 0 /* sign bit */, 0}},
+    {0x104081,   {0x81, 0x81, 0xC1, 0 /* sign bit */, 0}},
+    {0x200000,   {0x80, 0x80, 0x80, 1, 0}},
+    {0x7FFFFFF,  {0xFF, 0xFF, 0xFF, 0x3F, 0}},
+    {0x8000000,  {0x80, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
+    {0x8000001,  {0x81, 0x80, 0x80, 0xC0, 0 /* sign bit */}},
+    {0x8000081,  {0x81, 0x81, 0x80, 0xC0, 0 /* sign bit */}},
+    {0x8004081,  {0x81, 0x81, 0x81, 0xC0, 0 /* sign bit */}},
+    {0x8204081,  {0x81, 0x81, 0x81, 0xC1, 0 /* sign bit */}},
+    {0x0FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0 /* sign bit */}},
+    {0x10000000, {0x80, 0x80, 0x80, 0x80, 1}},
+    {0x7FFFFFFF, {0xFF, 0xFF, 0xFF, 0xFF, 0x7}},
+    {-1,         {0x7F, 0, 0, 0, 0}},
+    {-2,         {0x7E, 0, 0, 0, 0}},
+    {-0x3F,      {0x41, 0, 0, 0, 0}},
+    {-0x40,      {0x40, 0, 0, 0, 0}},
+    {-0x41,      {0xBF, 0x7F, 0, 0, 0}},
+    {-0x80,      {0x80, 0x7F, 0, 0, 0}},
+    {-0x81,      {0xFF, 0x7E, 0, 0, 0}},
+    {-0x00002000, {0x80, 0x40, 0, 0, 0}},
+    {-0x00002001, {0xFF, 0xBF, 0x7F, 0, 0}},
+    {-0x00100000, {0x80, 0x80, 0x40, 0, 0}},
+    {-0x00100001, {0xFF, 0xFF, 0xBF, 0x7F, 0}},
+    {-0x08000000, {0x80, 0x80, 0x80, 0x40, 0}},
+    {-0x08000001, {0xFF, 0xFF, 0xFF, 0xBF, 0x7F}},
+    {-0x20000000, {0x80, 0x80, 0x80, 0x80, 0x7E}},
+    {(-1) << 31, {0x80, 0x80, 0x80, 0x80, 0x78}},
+};
+
+TEST_F(Leb128Test, UnsignedSingles) {
   // Test individual encodings.
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
-    UnsignedLeb128EncodingVector builder;
-    builder.PushBack(uleb128_tests[i].decoded);
+    Leb128EncodingVector builder;
+    builder.PushBackUnsigned(uleb128_tests[i].decoded);
     const uint8_t* data_ptr = &uleb128_tests[i].leb128_data[0];
     const uint8_t* encoded_data_ptr = &builder.GetData()[0];
     for (size_t j = 0; j < 5; ++j) {
@@ -60,11 +110,11 @@
   }
 }
 
-TEST_F(Leb128Test, Stream) {
+TEST_F(Leb128Test, UnsignedStream) {
   // Encode a number of entries.
-  UnsignedLeb128EncodingVector builder;
+  Leb128EncodingVector builder;
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
-    builder.PushBack(uleb128_tests[i].decoded);
+    builder.PushBackUnsigned(uleb128_tests[i].decoded);
   }
   const uint8_t* encoded_data_ptr = &builder.GetData()[0];
   for (size_t i = 0; i < arraysize(uleb128_tests); ++i) {
@@ -78,15 +128,51 @@
   }
 }
 
+TEST_F(Leb128Test, SignedSingles) {
+  // Test individual encodings.
+  for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
+    Leb128EncodingVector builder;
+    builder.PushBackSigned(sleb128_tests[i].decoded);
+    const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
+    const uint8_t* encoded_data_ptr = &builder.GetData()[0];
+    for (size_t j = 0; j < 5; ++j) {
+      if (j < builder.GetData().size()) {
+        EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
+      } else {
+        EXPECT_EQ(data_ptr[j], 0U) << " i = " << i << " j = " << j;
+      }
+    }
+    EXPECT_EQ(DecodeSignedLeb128(&data_ptr), sleb128_tests[i].decoded) << " i = " << i;
+  }
+}
+
+TEST_F(Leb128Test, SignedStream) {
+  // Encode a number of entries.
+  Leb128EncodingVector builder;
+  for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
+    builder.PushBackSigned(sleb128_tests[i].decoded);
+  }
+  const uint8_t* encoded_data_ptr = &builder.GetData()[0];
+  for (size_t i = 0; i < arraysize(sleb128_tests); ++i) {
+    const uint8_t* data_ptr = &sleb128_tests[i].leb128_data[0];
+    for (size_t j = 0; j < 5; ++j) {
+      if (data_ptr[j] != 0) {
+        EXPECT_EQ(data_ptr[j], encoded_data_ptr[j]) << " i = " << i << " j = " << j;
+      }
+    }
+    EXPECT_EQ(DecodeSignedLeb128(&encoded_data_ptr), sleb128_tests[i].decoded) << " i = " << i;
+  }
+}
+
 TEST_F(Leb128Test, Speed) {
   UniquePtr<Histogram<uint64_t> > enc_hist(new Histogram<uint64_t>("Leb128EncodeSpeedTest", 5));
   UniquePtr<Histogram<uint64_t> > dec_hist(new Histogram<uint64_t>("Leb128DecodeSpeedTest", 5));
-  UnsignedLeb128EncodingVector builder;
+  Leb128EncodingVector builder;
   // Push back 1024 chunks of 1024 values measuring encoding speed.
   uint64_t last_time = NanoTime();
   for (size_t i = 0; i < 1024; i++) {
     for (size_t j = 0; j < 1024; j++) {
-      builder.PushBack((i * 1024) + j);
+      builder.PushBackUnsigned((i * 1024) + j);
     }
     uint64_t cur_time = NanoTime();
     enc_hist->AddValue(cur_time - last_time);