[Support] Generalize operations on ValueT for LEB128 encoding/decoding

[nlguillemot]

Summary

Explicitly defines the non-trivial operations required to be supported
for the ValueT used in the LEB128 encoding/decoding iterators. The plan
is to use this to support using LEB128 encoding/decoding with APInt.
This patch implements the interface for integral types, and a subsequent
patch will implement the interface using APInt.

llvm/include/llvm/Support/LEB128.h

 //===- llvm/Support/LEB128.h - [SU]LEB128 utility functions -----*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file declares some utility functions for encoding SLEB128 and
 // ULEB128 values.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_LEB128_H
 #define LLVM_SUPPORT_LEB128_H
 
+#include "llvm/Support/LEB128CodecInfo.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <iterator>
 
 namespace llvm {
 
 /// Converts a value into bytes encoded in LEB128 style.
 /// Matches the interface of std input iterators.
-template <class ValueT> class LEB128InputIterator {
+template <class ValueT, class CodecInfoT = LEB128CodecInfo<ValueT>>
+class LEB128InputIterator {
   /// Denotes whether this object represents an end() iterator.
   bool IsEnd;
 
   /// The current value that the iterator is converting into LEB128.
   ValueT Value;
 
   /// Whether this iterator is outputting a signed or unsigned LEB128 data.
   bool IsSigned;
 
   /// Whether there will be more output after the previously outputted byte.
   bool More;
 
   /// The output will be sext-ed/zext-ed to this number of bytes if necessary.
   unsigned PadTo;
 
   /// The current number of outputted bytes.
   unsigned Count;
 
   /// The current LEB128 encoded byte that this iterator will return.
   uint8_t CurrByte;
 
   /// Consumes 7 bits from Value and encodes them as a LEB128 byte in CurrByte.
   void encodeNextByte() {
-    CurrByte = Value & 0x7f;
+    CurrByte = CodecInfoT::getLo7Bits(Value);
     if (IsSigned) {
-      int64_t SValue = static_cast<int64_t>(Value);
-      // NOTE: this assumes that this signed shift is an arithmetic right shift.
-      SValue >>= 7;
-      More = !((((SValue == 0) && ((CurrByte & 0x40) == 0)) ||
-                ((SValue == -1) && ((CurrByte & 0x40) != 0))));
-      Value = static_cast<ValueT>(SValue);
+      CodecInfoT::ashr7InPlace(Value);
+      More = !((!Value && ((CurrByte & 0x40) == 0)) ||
+               (CodecInfoT::isAllOnesValue(Value) && ((CurrByte & 0x40) != 0)));
     } else {
-      // Logical right shift.
-      uint64_t UValue = static_cast<uint64_t>(Value);
-      UValue >>= 7;
-      More = UValue != 0;
-      Value = static_cast<ValueT>(UValue);
+      CodecInfoT::lshr7InPlace(Value);
+      More = !!Value;
     }
     Count++;
     if (More || Count < PadTo)
       CurrByte |= 0x80; // Mark this byte to show that more bytes will follow.
   }
 
 public:
   /// Boilerplate typedefs for C++ iterators.
LEB128InputIterator &operator++() {
     // At first, keep encoding bytes from Value until there is nothing left.
     if (More) {
       encodeNextByte();
       return *this;
     }
 
     // Pad with 0s or 1s depending on whether we want to zext or sext.
     uint8_t PadValue;
-    if (IsSigned && static_cast<int64_t>(Value) < 0)
+    if (IsSigned && CodecInfoT::isAllOnesValue(Value))
       PadValue = 0x7f;
     else
       PadValue = 0x00;
 
     // Output padding as necessary.
     if (Count < PadTo) {
       CurrByte = PadValue;
       // Add a continuation bit to signal that there is more padding after this.
public:
   bool operator!=(const LEB128InputIterator &Other) const {
     return !operator==(Other);
   }
   ///@}
 };
 
 /// Decodes LEB128-encoded bytes into a value.
 /// Matches the interface of std output iterators.
-template <class ValueT> class LEB128OutputIterator {
+template <class ValueT, class CodecInfoT = LEB128CodecInfo<ValueT>>
+class LEB128OutputIterator {
   /// The value into which the decoded bytes are written.
   ValueT &Value;
 
   /// Whether this iterator is outputting a signed or unsigned value.
   bool IsSigned;
 
   /// Contains the error message of the last error. Null if there was no error.
   const char *Error;
public:
   }
 
   /// Decodes one byte from a stream of LEB128-encoded bytes, and stores the
   /// decoded bits in the Value that was used to construct the output iterator.
   LEB128OutputIterator &operator=(uint8_t Byte) {
     assert(!IsComplete && "Already saw final LEB128 byte. Can't decode more.");
     assert(!Error && "Should abandon LEB128 decoding when an error happens.");
 
-    uint64_t Slice = Byte & 0x7f;
+    uint8_t Slice = Byte & 0x7f;
     if (!IsSigned) {
       // TODO: Implement an equivalent check for signed values?
       //       (The existing code did not check this error for signed values, so
       //       this refactor is leaving it unimplemented.)
-      if (Shift >= 64 || Slice << Shift >> Shift != Slice) {
+      unsigned RequiredBits = Shift + (8 - countLeadingZeros(Slice));
+      if (Shift >= CodecInfoT::getMaxNumBits() ||
+          RequiredBits > CodecInfoT::getMaxNumBits()) {
+        // TODO: Update this error message to be more general.
         Error = "uleb128 too big for uint64";
         return *this;
       }
     }
-    Value |= Slice << Shift;
+    CodecInfoT::insertLo7InPlace(Value, Slice, Shift);
     Shift += 7;
 
     if (!(Byte & 0x80)) {
       // No continuation bit, therefore this was the final byte.
       IsComplete = true;
       // Sign extend negative numbers if needed.
-      if (IsSigned && Shift < 64 && (Byte & 0x40))
-        Value |= -1ULL << Shift;
+      if (IsSigned && Shift < CodecInfoT::getMaxNumBits() && (Byte & 0x40))
+        CodecInfoT::negSExtInPlace(Value, Shift);
     }
     return *this;
   }
 
   /// No-op. Provided to satisfy the requirements of LegacyOutputIterator.
   ///@{
   LEB128OutputIterator &operator*() { return *this; }
   LEB128OutputIterator &operator++() { return *this; }

llvm/include/llvm/Support/LEB128CodecInfo.h

+//===- llvm/Support/LEB128CodecInfo.h - Type traits for LEB128 --*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines LEB128CodecInfo traits for [SU]LEB128 encoding/decoding.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_SUPPORT_LEB128CODECINFO_H
+#define LLVM_SUPPORT_LEB128CODECINFO_H
+
+#include <cstdint>
+#include <type_traits>
+
+namespace llvm {
+
+/// The basic operations required to be supported by a type in order to be used
+/// as the source of LEB128 encoding or the destination of LEB128 decoding.
+///
+/// Note: There are also some additional requirements not mentioned here. For
+/// example, checking that the value is zero is done with operator!().
+template <class ValueT, class /* Enable */ = void> struct LEB128CodecInfo {
+  /// Get the 7 least significant bits from Value and return them as a uint8_t.
+  ///
+  /// static uint8_t getLo7Bits(const ValueT &Value);
+
+  /// Do an in-place logical right shift of 7 bits on Value.
+  ///
+  /// static void lshr7InPlace(ValueT &Value);
+
+  /// Do an in-place arithmetic right shift of 7 bits on Value.
+  ///
+  /// static void ashr7InPlace(ValueT &Value);
+
+  /// Return true if all bits in Value are 1. False otherwise.
+  /// In practice, this is used to check if we have the value of a negative
+  /// signed integer that has been arithmetically shifted to the right an
+  /// infinite number of times.
+  ///
+  /// static bool isAllOnesValue(const ValueT &Value);
+
+  /// Get the maximum number of bits possible to represent with ValueT.
+  /// May return a very large number if ValueT has no particular limit of bits.
+  ///
+  /// static unsigned getMaxNumBits();
+
+  /// Set the half-open range of bits [Shift, Shift + 7) of Value to match the
+  /// contents of Lo7. The value of Shift increases monotonically with every
+  /// call to this function. The ranges of bits of successive calls do not
+  /// overlap. You may assume that the bits in the range were previously zero.
+  /// You may assume that Lo7 always has a value that fits in 7 bits.
+  ///
+  /// static void insertLo7InPlace(ValueT &Value, uint8_t Lo7, unsigned Shift);
+
+  /// Sign extends Value, where Value is an integer that has a number
+  /// of bits corresponding to NumUnextendedBits, and where it is assumed that
+  /// Value is a negative number. In other words, sets all bits in the
+  /// representation of Value to 1 except for the number of least significant
+  /// bits stored in NumUnextendedBits.
+  ///
+  /// static void negSExtInPlace(ValueT &Value, unsigned NumUnextendedBits);
+};
+
+/// Specialization of LEB128CodecInfo for integral types.
+template <class ValueT>
+struct LEB128CodecInfo<
+    ValueT, typename std::enable_if<std::is_integral<ValueT>::value>::type> {
+  static uint8_t getLo7Bits(const ValueT &Value) { return Value & 0x7f; }
+
+  static void lshr7InPlace(ValueT &Value) {
+    uint64_t UValue = static_cast<uint64_t>(Value);
+    UValue >>= 7;
+    Value = static_cast<ValueT>(UValue);
+  }
+
+  static void ashr7InPlace(ValueT &Value) {
+    int64_t SValue = static_cast<int64_t>(Value);
+    // NOTE: this assumes that this signed shift is an arithmetic right shift.
+    SValue >>= 7;
+    Value = static_cast<ValueT>(SValue);
+  }
+
+  static bool isAllOnesValue(const ValueT &Value) {
+    return Value == ~static_cast<ValueT>(0);
+  }
+
+  static unsigned getMaxNumBits() { return sizeof(ValueT) * 8; }
+
+  static void insertLo7InPlace(ValueT &Value, uint8_t Lo7, unsigned Shift) {
+    Value |= static_cast<ValueT>(Lo7) << Shift;
+  }
+
+  static void negSExtInPlace(ValueT &Value, unsigned NumUnextendedBits) {
+    Value |= ~static_cast<ValueT>(0) << NumUnextendedBits;
+  }
+};
+
+} // namespace llvm
+
+#endif // LLVM_SUPPORT_LEB128CODECINFO_H