[sanitizer] Add Leb128 encoding/decoding

[kstoimenov]

compiler-rt/lib/sanitizer_common/sanitizer_leb128.h

19

Why not making this iterator? I think it will make the code more readable. Plus it will still work with the regular pointers.

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_leb128.h

19

Pointers will not be enough here, but iterators probably require more boilerplate on caller side. Not sure.

[dvyukov]

compiler-rt/lib/sanitizer_common/sanitizer_leb128.h

35

templates don't need inline to avoid multiple definitions

[kstoimenov]

compiler-rt/lib/sanitizer_common/sanitizer_leb128.h

19

What I am proposing is this:
template <typename T, typename It> inline void EncodeSLEB128(T v, It it) {
......
*(it++) = byte; // instead of fn(byte) on line 29

This will work both with regular pointers and STL integrators depending on the instantiation of the template. For example if you are using a container you can pass a back_insert_iterator.

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_leb128.h

19

Problem is we don't have STL in compiler-rt, so for anything but pointer you to define one, which is a class with at least deference and increment operators vs just a lambda.

[vitalybuka]

remove inline

[vitalybuka]

compiler-rt/lib/sanitizer_common/sanitizer_leb128.h

19

I don't have strong preference about Iterator vs lambda. Both will work.
I need some way to chain coders, in later patches (they are not yet uploaded), something stream like, but it's even more noise without stream lib like in llvm or STL. So I reconsider that later.

[morehouse]

I understand the ULEB128 for compression. What will we need SLEB128 for?

[vitalybuka]

rebase

[vitalybuka]

iterators

[kstoimenov]

compiler-rt/lib/sanitizer_common/sanitizer_leb128.h

37

Nit: output value should be at the end of the list and a pointer according to g3 styleguide. Up to you.

[fmayer]

compiler-rt/lib/sanitizer_common/sanitizer_leb128.h

37

The bit about pointers is no longer true: … while non-optional output and input/output parameters should usually be references (which cannot be null). See https://google.github.io/styleguide/cppguide.html#Inputs_and_Outputs.

compiler-rt/lib/sanitizer_common/CMakeLists.txt

set(SANITIZER_IMPL_HEADERS
   sanitizer_flat_map.h
   sanitizer_freebsd.h
   sanitizer_fuchsia.h
   sanitizer_getauxval.h
   sanitizer_hash.h
   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
   sanitizer_linux.h
   sanitizer_list.h
   sanitizer_local_address_space_view.h
   sanitizer_mac.h
   sanitizer_malloc_mac.inc

compiler-rt/lib/sanitizer_common/sanitizer_leb128.h

+//===-- 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

compiler-rt/lib/sanitizer_common/tests/CMakeLists.txt

set(SANITIZER_UNITTESTS
   sanitizer_common_test.cpp
   sanitizer_deadlock_detector_test.cpp
   sanitizer_dense_map_test.cpp
   sanitizer_flags_test.cpp
   sanitizer_flat_map_test.cpp
   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
   sanitizer_mac_test.cpp
   sanitizer_mutex_test.cpp
   sanitizer_nolibc_test.cpp
   sanitizer_posix_test.cpp
   sanitizer_printf_test.cpp

compiler-rt/lib/sanitizer_common/tests/sanitizer_leb128_test.cpp

+//===-- 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