NativePcOffsetToReferenceMap

Rather than translate a native PC to a Dex PC and then to the reference
bitmap, just go straight from the native PC to the reference bitmap.
Encode the native PC offsets using a hash rather than linearly
searching.

Change-Id: Iee1073d93c941c0a31f639e5f23cea9e9f747bee
diff --git a/src/verifier/dex_gc_map.cc b/src/verifier/dex_gc_map.cc
new file mode 100644
index 0000000..c1c9a29
--- /dev/null
+++ b/src/verifier/dex_gc_map.cc
@@ -0,0 +1,56 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "verifier/dex_gc_map.h"
+
+#include "logging.h"
+
+namespace art {
+namespace verifier {
+
+const uint8_t* DexPcToReferenceMap::FindBitMap(uint16_t dex_pc, bool error_if_not_present) const {
+  size_t num_entries = NumEntries();
+  // Do linear or binary search?
+  static const size_t kSearchThreshold = 8;
+  if (num_entries < kSearchThreshold) {
+    for (size_t i = 0; i < num_entries; i++)  {
+      if (GetDexPc(i) == dex_pc) {
+        return GetBitMap(i);
+      }
+    }
+  } else {
+    int lo = 0;
+    int hi = num_entries -1;
+    while (hi >= lo) {
+      int mid = (hi + lo) / 2;
+      int mid_pc = GetDexPc(mid);
+      if (dex_pc > mid_pc) {
+        lo = mid + 1;
+      } else if (dex_pc < mid_pc) {
+        hi = mid - 1;
+      } else {
+        return GetBitMap(mid);
+      }
+    }
+  }
+  if (error_if_not_present) {
+    LOG(ERROR) << "Didn't find reference bit map for dex_pc " << dex_pc;
+  }
+  return NULL;
+}
+
+}  // namespace verifier
+}  // namespace art