Delta-encoding of mapping tables.

Both PC offsets and dalvik offsets are delta-encoded. Since
PC offsets are increasing, the deltas are then compressed as
unsigned LEB128. Dalvik offsets are not monotonic, so their
deltas are compressed as signed LEB128.

This reduces the size of the mapping tables by about 30%
on average, 25% from the PC offset and 5% from the dalvik
offset delta encoding.

Bug: 9437697
Change-Id: I600ab9c22dec178088d4947a811cca3bc8bd4cf4

8 files changed, 229 insertions, 62 deletions

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 @@ bool Mir2Lir::VerifyCatchEntries() {
 
 
 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 @@ void Mir2Lir::CreateMappingTables() {
   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 @@ CompiledMethod* Mir2Lir::GetCompiledMethod() {
   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 @@ class Mir2Lir : public Backend {
     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 InsertBackUnsigned(It cur, It end) {
+    for (; cur != end; ++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 InsertBack(It cur, It end) {
+  void InsertBackSigned(It cur, It end) {
     for (; cur != end; ++cur) {
-      PushBack(*cur);
+      PushBackSigned(*cur);
     }
   }
 
@@ -55,7 +76,7 @@ class UnsignedLeb128EncodingVector {
  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 @@ static DecodeUnsignedLeb128TestCase uleb128_tests[] = {
     {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, Singles) {
   }
 }
 
-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, Stream) {
   }
 }
 
+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);
diff --git a/runtime/exception_test.cc b/runtime/exception_test.cc
index e9a6e4f..8f542d8 100644
--- a/runtime/exception_test.cc
+++ b/runtime/exception_test.cc
@@ -54,17 +54,17 @@ class ExceptionTest : public CommonTest {
       fake_code_.push_back(0x70 | i);
     }
 
-    fake_mapping_data_.PushBack(4);  // first element is count
-    fake_mapping_data_.PushBack(4);  // total (non-length) elements
-    fake_mapping_data_.PushBack(2);  // count of pc to dex elements
+    fake_mapping_data_.PushBackUnsigned(4);  // first element is count
+    fake_mapping_data_.PushBackUnsigned(4);  // total (non-length) elements
+    fake_mapping_data_.PushBackUnsigned(2);  // count of pc to dex elements
                                       // ---  pc to dex table
-    fake_mapping_data_.PushBack(3);  // offset 3
-    fake_mapping_data_.PushBack(3);  // maps to dex offset 3
+    fake_mapping_data_.PushBackUnsigned(3 - 0);  // offset 3
+    fake_mapping_data_.PushBackSigned(3 - 0);    // maps to dex offset 3
                                       // ---  dex to pc table
-    fake_mapping_data_.PushBack(3);  // offset 3
-    fake_mapping_data_.PushBack(3);  // maps to dex offset 3
+    fake_mapping_data_.PushBackUnsigned(3 - 0);  // offset 3
+    fake_mapping_data_.PushBackSigned(3 - 0);    // maps to dex offset 3
 
-    fake_vmap_table_data_.PushBack(0);
+    fake_vmap_table_data_.PushBackUnsigned(0);
 
     fake_gc_map_.push_back(0);  // 0 bytes to encode references and native pc offsets.
     fake_gc_map_.push_back(0);
@@ -91,8 +91,8 @@ class ExceptionTest : public CommonTest {
   const DexFile* dex_;
 
   std::vector<uint8_t> fake_code_;
-  UnsignedLeb128EncodingVector fake_mapping_data_;
-  UnsignedLeb128EncodingVector fake_vmap_table_data_;
+  Leb128EncodingVector fake_mapping_data_;
+  Leb128EncodingVector fake_vmap_table_data_;
   std::vector<uint8_t> fake_gc_map_;
 
   mirror::ArtMethod* method_f_;
diff --git a/runtime/leb128.h b/runtime/leb128.h
index 6041f8c..7a7d38d 100644
--- a/runtime/leb128.h
+++ b/runtime/leb128.h
@@ -18,6 +18,7 @@
 #define ART_RUNTIME_LEB128_H_
 
 #include "globals.h"
+#include "utils.h"
 
 namespace art {
 
@@ -95,12 +96,20 @@ static inline int32_t DecodeSignedLeb128(const uint8_t** data) {
 
 // Returns the number of bytes needed to encode the value in unsigned LEB128.
 static inline uint32_t UnsignedLeb128Size(uint32_t data) {
-  uint32_t count = 0;
-  do {
-    data >>= 7;
-    count++;
-  } while (data != 0);
-  return count;
+  // bits_to_encode = (data != 0) ? 32 - CLZ(x) : 1  // 32 - CLZ(data | 1)
+  // bytes = ceil(bits_to_encode / 7.0);             // (6 + bits_to_encode) / 7
+  uint32_t x = 6 + 32 - CLZ(data | 1);
+  // Division by 7 is done by (x * 37) >> 8 where 37 = ceil(256 / 7).
+  // This works for 0 <= x < 256 / (7 * 37 - 256), i.e. 0 <= x <= 85.
+  return (x * 37) >> 8;
+}
+
+// Returns the number of bytes needed to encode the value in unsigned LEB128.
+static inline uint32_t SignedLeb128Size(int32_t data) {
+  // Like UnsignedLeb128Size(), but we need one bit beyond the highest bit that differs from sign.
+  data = data ^ (data >> 31);
+  uint32_t x = 1 /* we need to encode the sign bit */ + 6 + 32 - CLZ(data | 1);
+  return (x * 37) >> 8;
 }
 
 }  // namespace art
diff --git a/runtime/mapping_table.h b/runtime/mapping_table.h
index c468c1e..a82bc1c 100644
--- a/runtime/mapping_table.h
+++ b/runtime/mapping_table.h
@@ -72,7 +72,8 @@ class MappingTable {
         if (end_ > 0) {
           encoded_table_ptr_ = table_->FirstDexToPcPtr();
           native_pc_offset_ = DecodeUnsignedLeb128(&encoded_table_ptr_);
-          dex_pc_ = DecodeUnsignedLeb128(&encoded_table_ptr_);
+          // First delta is always positive.
+          dex_pc_ = static_cast<uint32_t>(DecodeSignedLeb128(&encoded_table_ptr_));
         }
       } else {  // An iterator wanted from the end.
         DCHECK_EQ(table_->DexToPcSize(), element);
@@ -87,8 +88,9 @@ class MappingTable {
     void operator++() {
       ++element_;
       if (element_ != end_) {  // Avoid reading beyond the end of the table.
-        native_pc_offset_ = DecodeUnsignedLeb128(&encoded_table_ptr_);
-        dex_pc_ = DecodeUnsignedLeb128(&encoded_table_ptr_);
+        native_pc_offset_ += DecodeUnsignedLeb128(&encoded_table_ptr_);
+        // For negative delta, unsigned overflow after static_cast does exactly what we need.
+        dex_pc_ += static_cast<uint32_t>(DecodeSignedLeb128(&encoded_table_ptr_));
       }
     }
     bool operator==(const DexToPcIterator& rhs) const {
@@ -147,7 +149,8 @@ class MappingTable {
         if (end_ > 0) {
           encoded_table_ptr_ = table_->FirstPcToDexPtr();
           native_pc_offset_ = DecodeUnsignedLeb128(&encoded_table_ptr_);
-          dex_pc_ = DecodeUnsignedLeb128(&encoded_table_ptr_);
+          // First delta is always positive.
+          dex_pc_ = static_cast<uint32_t>(DecodeSignedLeb128(&encoded_table_ptr_));
         }
       } else {  // An iterator wanted from the end.
         DCHECK_EQ(table_->PcToDexSize(), element);
@@ -162,8 +165,9 @@ class MappingTable {
     void operator++() {
       ++element_;
       if (element_ != end_) {  // Avoid reading beyond the end of the table.
-        native_pc_offset_ = DecodeUnsignedLeb128(&encoded_table_ptr_);
-        dex_pc_ = DecodeUnsignedLeb128(&encoded_table_ptr_);
+        native_pc_offset_ += DecodeUnsignedLeb128(&encoded_table_ptr_);
+        // For negative delta, unsigned overflow after static_cast does exactly what we need.
+        dex_pc_ += static_cast<uint32_t>(DecodeSignedLeb128(&encoded_table_ptr_));
       }
     }
     bool operator==(const PcToDexIterator& rhs) const {
diff --git a/runtime/oat.cc b/runtime/oat.cc
index 50069b2..52e74ab 100644
--- a/runtime/oat.cc
+++ b/runtime/oat.cc
@@ -22,7 +22,7 @@
 namespace art {
 
 const uint8_t OatHeader::kOatMagic[] = { 'o', 'a', 't', '\n' };
-const uint8_t OatHeader::kOatVersion[] = { '0', '1', '1', '\0' };
+const uint8_t OatHeader::kOatVersion[] = { '0', '1', '2', '\0' };
 
 OatHeader::OatHeader() {
   memset(this, 0, sizeof(*this));