[Support] Add LEB128 support to BinaryStreamReader/Writer.

[lhames]

Summary

This patch adds support for ULEB128 and SLEB128 encoding and decoding to
BinaryStreamWriter and BinaryStreamReader respectively.

Support for ULEB128/SLEB128 will be used for eh-frame parsing in the JITLink
library currently under development (see https://reviews.llvm.org/D58704).

[dblaikie]

Looks reasonable to me

lib/Support/BinaryStreamReader.cpp

64–68

Wonder if it's worth rewriting decodeULEB128 as a template (so it can read from different sources without having to buffer it all into an array (& in doing that buffering, having to reimplement the 0x80 check piece))?

[lhames]

Thanks Dave!

lib/Support/BinaryStreamReader.cpp

64–68

Yep — I considered that, but it would involve teaching decodeULEB128 to deal with sources that potentially generate errors. Since ULEB128 encoding isn’t built for speed anyway (prefix-based variable length encodings are better for that) I did not think the complication was worth it.

include/llvm/Support/BinaryStreamReader.h

static_assert(std::is_enum<T>::value,
                   "Cannot call readEnum with non-enum value!");
     typename std::underlying_type<T>::type N;
     if (auto EC = readInteger(N))
       return EC;
     Dest = static_cast<T>(N);
     return Error::success();
   }
 
+  /// Read an unsigned LEB128 encoded value.
+  ///
+  /// \returns a success error code if the data was successfully read, otherwise
+  /// returns an appropriate error code.
+  Error readULEB128(uint64_t &Dest);
+
+  /// Read a signed LEB128 encoded value.
+  ///
+  /// \returns a success error code if the data was successfully read, otherwise
+  /// returns an appropriate error code.
+  Error readSLEB128(int64_t &Dest);
+
   /// Read a null terminated string from \p Dest.  Whether a copy occurs depends
   /// on the implementation of the underlying stream.  Updates the stream's
   /// offset to point after the newly read data.
   ///
   /// \returns a success error code if the data was successfully read, otherwise
   /// returns an appropriate error code.
   Error readCString(StringRef &Dest);
 

include/llvm/Support/BinaryStreamWriter.h

public:
   template <typename T> Error writeEnum(T Num) {
     static_assert(std::is_enum<T>::value,
                   "Cannot call writeEnum with non-Enum type");
 
     using U = typename std::underlying_type<T>::type;
     return writeInteger<U>(static_cast<U>(Num));
   }
 
+  /// Write the unsigned integer Value to the underlying stream using ULEB128
+  /// encoding.
+  ///
+  /// \returns a success error code if the data was successfully written,
+  /// otherwise returns an appropriate error code.
+  Error writeULEB128(uint64_t Value);
+
+  /// Write the unsigned integer Value to the underlying stream using ULEB128
+  /// encoding.
+  ///
+  /// \returns a success error code if the data was successfully written,
+  /// otherwise returns an appropriate error code.
+  Error writeSLEB128(int64_t Value);
+
   /// Write the string \p Str to the underlying stream followed by a null
   /// terminator.  On success, updates the offset so that subsequent writes
   /// occur at the next unwritten position.  \p Str need not be null terminated
   /// on input.
   ///
   /// \returns a success error code if the data was successfully written,
   /// otherwise returns an appropriate error code.
   Error writeCString(StringRef Str);

lib/Support/BinaryStreamReader.cpp

 //===- BinaryStreamReader.cpp - Reads objects from a binary stream --------===//
 //
 // 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 "llvm/Support/BinaryStreamReader.h"
 
 #include "llvm/Support/BinaryStreamError.h"
 #include "llvm/Support/BinaryStreamRef.h"
+#include "llvm/Support/LEB128.h"
 
 using namespace llvm;
 using endianness = llvm::support::endianness;
 
 BinaryStreamReader::BinaryStreamReader(BinaryStreamRef Ref) : Stream(Ref) {}
 
 BinaryStreamReader::BinaryStreamReader(BinaryStream &Stream) : Stream(Stream) {}
 

 
 Error BinaryStreamReader::readBytes(ArrayRef<uint8_t> &Buffer, uint32_t Size) {
   if (auto EC = Stream.readBytes(Offset, Size, Buffer))
     return EC;
   Offset += Size;
   return Error::success();
 }
 
+Error BinaryStreamReader::readULEB128(uint64_t &Dest) {
+  SmallVector<uint8_t, 10> EncodedBytes;
+  ArrayRef<uint8_t> NextByte;
+
+  // Copy the encoded ULEB into the buffer.
+  do {
+    if (auto Err = readBytes(NextByte, 1))
+      return Err;
+    EncodedBytes.push_back(NextByte[0]);
+  } while (NextByte[0] & 0x80);
+
+  Dest = decodeULEB128(EncodedBytes.begin(), nullptr, EncodedBytes.end());
+  return Error::success();
+}
+
+Error BinaryStreamReader::readSLEB128(int64_t &Dest) {
+  SmallVector<uint8_t, 10> EncodedBytes;
+  ArrayRef<uint8_t> NextByte;
+
+  // Copy the encoded ULEB into the buffer.
+  do {
+    if (auto Err = readBytes(NextByte, 1))
+      return Err;
+    EncodedBytes.push_back(NextByte[0]);
+  } while (NextByte[0] & 0x80);
+
+  Dest = decodeSLEB128(EncodedBytes.begin(), nullptr, EncodedBytes.end());
+  return Error::success();
+}
+
 Error BinaryStreamReader::readCString(StringRef &Dest) {
   uint32_t OriginalOffset = getOffset();
   uint32_t FoundOffset = 0;
   while (true) {
     uint32_t ThisOffset = getOffset();
     ArrayRef<uint8_t> Buffer;
     if (auto EC = readLongestContiguousChunk(Buffer))
       return EC;
BinaryStreamReader::split(uint32_t Off) const {
 
   BinaryStreamRef First = Stream.drop_front(Offset);
 
   BinaryStreamRef Second = First.drop_front(Off);
   First = First.keep_front(Off);
   BinaryStreamReader W1{First};
   BinaryStreamReader W2{Second};
   return std::make_pair(W1, W2);
-}
+}
 

lib/Support/BinaryStreamWriter.cpp

 //===- BinaryStreamWriter.cpp - Writes objects to a BinaryStream ----------===//
 //
 // 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 "llvm/Support/BinaryStreamWriter.h"
 
 #include "llvm/Support/BinaryStreamError.h"
 #include "llvm/Support/BinaryStreamReader.h"
 #include "llvm/Support/BinaryStreamRef.h"
+#include "llvm/Support/LEB128.h"
 
 using namespace llvm;
 
 BinaryStreamWriter::BinaryStreamWriter(WritableBinaryStreamRef Ref)
     : Stream(Ref) {}
 
 BinaryStreamWriter::BinaryStreamWriter(WritableBinaryStream &Stream)
     : Stream(Stream) {}
 
 BinaryStreamWriter::BinaryStreamWriter(MutableArrayRef<uint8_t> Data,
                                        llvm::support::endianness Endian)
     : Stream(Data, Endian) {}
 
 Error BinaryStreamWriter::writeBytes(ArrayRef<uint8_t> Buffer) {
   if (auto EC = Stream.writeBytes(Offset, Buffer))
     return EC;
   Offset += Buffer.size();
   return Error::success();
 }
 
+Error BinaryStreamWriter::writeULEB128(uint64_t Value) {
+  uint8_t EncodedBytes[10] = {0};
+  unsigned Size = encodeULEB128(Value, &EncodedBytes[0]);
+  return writeBytes({EncodedBytes, Size});
+}
+
+Error BinaryStreamWriter::writeSLEB128(int64_t Value) {
+  uint8_t EncodedBytes[10] = {0};
+  unsigned Size = encodeSLEB128(Value, &EncodedBytes[0]);
+  return writeBytes({EncodedBytes, Size});
+}
+
 Error BinaryStreamWriter::writeCString(StringRef Str) {
   if (auto EC = writeFixedString(Str))
     return EC;
   if (auto EC = writeObject('\0'))
     return EC;
 
   return Error::success();
 }

unittests/Support/BinaryStreamTest.cpp

for (size_t I = 0; I < Enums.size(); ++I) {
       MyEnum Value;
       ASSERT_THAT_ERROR(Reader.readEnum(Value), Succeeded());
       EXPECT_EQ(Enums[I], Value);
     }
     ASSERT_EQ(0U, Reader.bytesRemaining());
   }
 }
 
+TEST_F(BinaryStreamTest, StreamReaderULEB128) {
+  std::vector<uint64_t> TestValues = {
+      0,                  // Zero
+      0x7F,               // One byte
+      0xFF,               // One byte, all-ones
+      0xAAAA,             // Two bytes
+      0xAAAAAAAA,         // Four bytes
+      0xAAAAAAAAAAAAAAAA, // Eight bytes
+      0xffffffffffffffff  // Eight bytess, all-ones
+  };
+
+  // Conservatively assume a 10-byte encoding for each of our LEB128s, with no
+  // alignment requirement.
+  initializeOutput(10 * TestValues.size(), 1);
+  initializeInputFromOutput(1);
+
+  for (auto &Stream : Streams) {
+    // Write fields.
+    BinaryStreamWriter Writer(*Stream.Output);
+    for (const auto &Value : TestValues)
+      ASSERT_THAT_ERROR(Writer.writeULEB128(Value), Succeeded());
+
+    // Read fields.
+    BinaryStreamReader Reader(*Stream.Input);
+    std::vector<uint64_t> Results;
+    Results.resize(TestValues.size());
+    for (unsigned I = 0; I != TestValues.size(); ++I)
+      ASSERT_THAT_ERROR(Reader.readULEB128(Results[I]), Succeeded());
+
+    for (unsigned I = 0; I != TestValues.size(); ++I)
+      EXPECT_EQ(TestValues[I], Results[I]);
+  }
+}
+
+TEST_F(BinaryStreamTest, StreamReaderSLEB128) {
+  std::vector<int64_t> TestValues = {
+      0,                  // Zero
+      0x7F,               // One byte
+      -0x7F,              // One byte, negative
+      0xFF,               // One byte, all-ones
+      0xAAAA,             // Two bytes
+      -0xAAAA,            // Two bytes, negative
+      0xAAAAAAAA,         // Four bytes
+      -0xAAAAAAAA,        // Four bytes, negative
+      0x2AAAAAAAAAAAAAAA, // Eight bytes
+      -0x7ffffffffffffff  // Eight bytess, negative
+  };
+
+  // Conservatively assume a 10-byte encoding for each of our LEB128s, with no
+  // alignment requirement.
+  initializeOutput(10 * TestValues.size(), 1);
+  initializeInputFromOutput(1);
+
+  for (auto &Stream : Streams) {
+    // Write fields.
+    BinaryStreamWriter Writer(*Stream.Output);
+    for (const auto &Value : TestValues)
+      ASSERT_THAT_ERROR(Writer.writeSLEB128(Value), Succeeded());
+
+    // Read fields.
+    BinaryStreamReader Reader(*Stream.Input);
+    std::vector<int64_t> Results;
+    Results.resize(TestValues.size());
+    for (unsigned I = 0; I != TestValues.size(); ++I)
+      ASSERT_THAT_ERROR(Reader.readSLEB128(Results[I]), Succeeded());
+
+    for (unsigned I = 0; I != TestValues.size(); ++I)
+      EXPECT_EQ(TestValues[I], Results[I]);
+  }
+}
+
 TEST_F(BinaryStreamTest, StreamReaderObject) {
   struct Foo {
     int X;
     double Y;
     char Z;
 
     bool operator==(const Foo &Other) const {
       return X == Other.X && Y == Other.Y && Z == Other.Z;