[sanitizer] Add Leb128 encoding/decoding
Reviewed By: dvyukov, kstoimenov
Differential Revision: https://reviews.llvm.org/D114464
diff --git a/compiler-rt/lib/sanitizer_common/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/CMakeLists.txt
index 2144555..48c8010 100644
--- a/compiler-rt/lib/sanitizer_common/CMakeLists.txt
+++ b/compiler-rt/lib/sanitizer_common/CMakeLists.txt
@@ -148,6 +148,7 @@
sanitizer_interceptors_ioctl_netbsd.inc
sanitizer_interface_internal.h
sanitizer_internal_defs.h
+ sanitizer_leb128.h
sanitizer_lfstack.h
sanitizer_libc.h
sanitizer_libignore.h
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_leb128.h b/compiler-rt/lib/sanitizer_common/sanitizer_leb128.h
new file mode 100644
index 0000000..553550d
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_leb128.h
@@ -0,0 +1,87 @@
+//===-- sanitizer_leb128.h --------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SANITIZER_LEB128_H
+#define SANITIZER_LEB128_H
+
+#include "sanitizer_common.h"
+#include "sanitizer_internal_defs.h"
+
+namespace __sanitizer {
+
+template <typename T, typename It>
+It EncodeSLEB128(T value, It begin, It end) {
+ bool more;
+ do {
+ u8 byte = value & 0x7f;
+ // NOTE: this assumes that this signed shift is an arithmetic right shift.
+ value >>= 7;
+ more = !((((value == 0) && ((byte & 0x40) == 0)) ||
+ ((value == -1) && ((byte & 0x40) != 0))));
+ if (more)
+ byte |= 0x80;
+ if (UNLIKELY(begin == end))
+ break;
+ *(begin++) = byte;
+ } while (more);
+ return begin;
+}
+
+template <typename T, typename It>
+It DecodeSLEB128(It begin, It end, T* v) {
+ T value = 0;
+ unsigned shift = 0;
+ u8 byte;
+ do {
+ if (UNLIKELY(begin == end))
+ return begin;
+ byte = *(begin++);
+ T slice = byte & 0x7f;
+ value |= slice << shift;
+ shift += 7;
+ } while (byte >= 128);
+ if (shift < 64 && (byte & 0x40))
+ value |= (-1ULL) << shift;
+ *v = value;
+ return begin;
+}
+
+template <typename T, typename It>
+It EncodeULEB128(T value, It begin, It end) {
+ do {
+ u8 byte = value & 0x7f;
+ value >>= 7;
+ if (value)
+ byte |= 0x80;
+ if (UNLIKELY(begin == end))
+ break;
+ *(begin++) = byte;
+ } while (value);
+ return begin;
+}
+
+template <typename T, typename It>
+It DecodeULEB128(It begin, It end, T* v) {
+ T value = 0;
+ unsigned shift = 0;
+ u8 byte;
+ do {
+ if (UNLIKELY(begin == end))
+ return begin;
+ byte = *(begin++);
+ T slice = byte & 0x7f;
+ value += slice << shift;
+ shift += 7;
+ } while (byte >= 128);
+ *v = value;
+ return begin;
+}
+
+} // namespace __sanitizer
+
+#endif // SANITIZER_LEB128_H
diff --git a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
index 2cff2b0..0ca8f7f 100644
--- a/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
+++ b/compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt
@@ -23,6 +23,7 @@
sanitizer_format_interceptor_test.cpp
sanitizer_hash_test.cpp
sanitizer_ioctl_test.cpp
+ sanitizer_leb128_test.cpp
sanitizer_libc_test.cpp
sanitizer_linux_test.cpp
sanitizer_list_test.cpp
diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_leb128_test.cpp b/compiler-rt/lib/sanitizer_common/tests/sanitizer_leb128_test.cpp
new file mode 100644
index 0000000..c0c75c4
--- /dev/null
+++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_leb128_test.cpp
@@ -0,0 +1,83 @@
+//===-- sanitizer_leb128.cpp ------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+#include "sanitizer_common/sanitizer_leb128.h"
+
+#include <type_traits>
+
+#include "gtest/gtest.h"
+#include "sanitizer_common/sanitizer_common.h"
+#include "sanitizer_internal_defs.h"
+
+namespace __sanitizer {
+
+template <typename T>
+class Leb128Test : public ::testing::Test {};
+
+using Leb128TestTypes = ::testing::Types<u8, u16, u32, u64>;
+TYPED_TEST_SUITE(Leb128Test, Leb128TestTypes, );
+
+static uptr BitsNeeded(u64 v) {
+ if (!v)
+ return 1;
+ uptr r = 0;
+ uptr uptr_bits = 8 * sizeof(uptr);
+ while (v >> uptr_bits) {
+ r += uptr_bits;
+ v >>= uptr_bits;
+ }
+ return r + MostSignificantSetBitIndex(v) + 1;
+}
+
+TYPED_TEST(Leb128Test, SignedOverflow) {
+ using T = typename std::make_signed<TypeParam>::type;
+ u8 buffer[16] = {255};
+ T v = -128;
+ EXPECT_EQ(buffer + 1, EncodeSLEB128(v, buffer, buffer + 1));
+ EXPECT_EQ(buffer + 1, DecodeSLEB128(buffer, buffer + 1, &v));
+}
+
+TYPED_TEST(Leb128Test, Signed) {
+ using T = typename std::make_signed<TypeParam>::type;
+ T v = 0;
+ for (int i = 0; i < 100; ++i) {
+ u8 buffer[16] = {};
+ u8* p = EncodeSLEB128(v, std::begin(buffer), std::end(buffer));
+ EXPECT_EQ(int(BitsNeeded(v < 0 ? (-v - 1) : v) + 6 + 1) / 7, p - buffer)
+ << (int)v;
+ T v2;
+ u8* p2 = DecodeSLEB128(std::begin(buffer), std::end(buffer), &v2);
+ EXPECT_EQ(v, v2);
+ EXPECT_EQ(p, p2);
+ v = -TypeParam(v) * 3u + 1u;
+ }
+}
+
+TYPED_TEST(Leb128Test, UnsignedOverflow) {
+ using T = TypeParam;
+ u8 buffer[16] = {255};
+ T v = 255;
+ EXPECT_EQ(buffer + 1, EncodeULEB128(v, buffer, buffer + 1));
+ EXPECT_EQ(buffer + 1, DecodeULEB128(buffer, buffer + 1, &v));
+}
+
+TYPED_TEST(Leb128Test, Unsigned) {
+ using T = TypeParam;
+ T v = 0;
+ for (int i = 0; i < 100; ++i) {
+ u8 buffer[16] = {};
+ u8* p = EncodeULEB128(v, std::begin(buffer), std::end(buffer));
+ EXPECT_EQ(int(BitsNeeded(v) + 6) / 7, p - buffer);
+ T v2;
+ u8* p2 = DecodeULEB128(std::begin(buffer), std::end(buffer), &v2);
+ EXPECT_EQ(v, v2);
+ EXPECT_EQ(p, p2);
+ v = v * 3 + 1;
+ }
+}
+
+} // namespace __sanitizer
