Compiler Explorer

Source code

#include <memory>
#include <vector>
#include <utility>
#include <limits>

# define PROTOBUF_PREDICT_TRUE(x) (__builtin_expect(false || (x), true))
# define PROTOBUF_PREDICT_FALSE(x) (__builtin_expect(false || (x), false))
# define PROTOBUF_MUSTTAIL [[clang::musttail]]

template <class T>
__attribute__((always_inline)) constexpr T RotateLeft(
    T x, int s) noexcept {
  return static_cast<T>(x << (s & (std::numeric_limits<T>::digits - 1))) |
         static_cast<T>(x >> ((-s) & (std::numeric_limits<T>::digits - 1)));
}

inline __attribute__((always_inline)) uint64_t
RotRight7AndReplaceLowByte(uint64_t res, const char& byte) {
  // TODO(b/239808098): remove the inline assembly
#if defined(__x86_64__) && defined(__GNUC__)
  // This will only use one register for `res`.
  // `byte` comes as a reference to allow the compiler to generate code like:
  //
  //   rorq    $7, %rcx
  //   movb    1(%rax), %cl
  //
  // which avoids loading the incoming bytes into a separate register first.
  asm("ror $7,%0\n\t"
      "movb %1,%b0"
      : "+r"(res)
      : "m"(byte));
#else
  res = RotateLeft(res, -7);
  res = res & ~0xFF;
  res |= 0xFF & byte;
#endif
  return res;
};

struct TcFieldData {
  constexpr TcFieldData() : data(0) {}

// Fast table entry constructor:
  constexpr TcFieldData(uint16_t coded_tag, uint8_t hasbit_idx, uint8_t aux_idx,
                        uint16_t offset)
      : data(uint64_t{offset} << 48 |      //
             uint64_t{aux_idx} << 24 |     //
             uint64_t{hasbit_idx} << 16 |  //
             uint64_t{coded_tag}) {}

// Fields used in fast table parsing:
  //
  //     Bit:
  //     +-----------+-------------------+
  //     |63    ..     32|31     ..     0|
  //     +---------------+---------------+
  //     :   .   :   .   :   . 16|=======| [16] coded_tag()
  //     :   .   :   .   : 24|===|   .   : [ 8] hasbit_idx()
  //     :   .   :   . 32|===|   :   .   : [ 8] aux_idx()
  //     :   . 48:---.---:   .   :   .   : [16] (unused)
  //     |=======|   .   :   .   :   .   : [16] offset()
  //     +-----------+-------------------+
  //     |63    ..     32|31     ..     0|
  //     +---------------+---------------+

template <typename TagType = uint16_t>
  TagType coded_tag() const {
    return static_cast<TagType>(data);
  }
  uint8_t hasbit_idx() const { return static_cast<uint8_t>(data >> 16); }
  uint8_t aux_idx() const { return static_cast<uint8_t>(data >> 24); }
  uint16_t offset() const { return static_cast<uint16_t>(data >> 48); }

// Constructor for special entries that do not represent a field.
  //  - End group: `nonfield_info` is the decoded tag.
  constexpr TcFieldData(uint16_t coded_tag, uint16_t nonfield_info)
      : data(uint64_t{nonfield_info} << 16 |  //
             uint64_t{coded_tag}) {}

// Fields used in non-field entries
  //
  //     Bit:
  //     +-----------+-------------------+
  //     |63    ..     32|31     ..     0|
  //     +---------------+---------------+
  //     :   .   :   .   :   . 16|=======| [16] coded_tag()
  //     :   .   :   . 32|=======|   .   : [16] decoded_tag()
  //     :---.---:---.---:   .   :   .   : [32] (unused)
  //     +-----------+-------------------+
  //     |63    ..     32|31     ..     0|
  //     +---------------+---------------+

uint16_t decoded_tag() const { return static_cast<uint16_t>(data >> 16); }

// Fields used in mini table parsing:
  //
  //     Bit:
  //     +-----------+-------------------+
  //     |63    ..     32|31     ..     0|
  //     +---------------+---------------+
  //     :   .   :   .   |===============| [32] tag() (decoded)
  //     |===============|   .   :   .   : [32] entry_offset()
  //     +-----------+-------------------+
  //     |63    ..     32|31     ..     0|
  //     +---------------+---------------+

uint32_t tag() const { return static_cast<uint32_t>(data); }
  uint32_t entry_offset() const { return static_cast<uint32_t>(data >> 32); }

uint64_t data;
};

template <int n>
inline __attribute__((always_inline)) uint64_t
shift_left_fill_with_ones(uint64_t byte, uint64_t ones) {
  return (byte << (n * 7)) | (ones >> (64 - (n * 7)));
}

// Shift "byte" left by n * 7 bits, filling vacated bits with ones, and
// put the new value in res.  Return whether the result was negative.
template <int n>
inline __attribute__((always_inline)) bool shift_left_fill_with_ones_was_negative(
    uint64_t byte, uint64_t ones, int64_t& res) {
#if defined(__GCC_ASM_FLAG_OUTPUTS__) && defined(__x86_64__)
  // For the first two rounds (ptr[1] and ptr[2]), micro benchmarks show a
  // substantial improvement from capturing the sign from the condition code
  // register on x86-64.
  bool sign_bit;
  asm("shldq %3, %2, %1"
      : "=@ccs"(sign_bit), "+r"(byte)
      : "r"(ones), "i"(n * 7));
  res = byte;
  return sign_bit;
#else
  // Generic fallback:
  res = shift_left_fill_with_ones<n>(byte, ones);
  return static_cast<int64_t>(res) < 0;
#endif
}

inline __attribute__((always_inline)) std::pair<const char*, uint64_t>
Parse64FallbackPair(const char* p, int64_t res1) {
  auto ptr = reinterpret_cast<const int8_t*>(p);

// The algorithm relies on sign extension for each byte to set all high bits
  // when the varint continues. It also relies on asserting all of the lower
  // bits for each successive byte read. This allows the result to be aggregated
  // using a bitwise AND. For example:
  //
  //          8       1          64     57 ... 24     17  16      9  8       1
  // ptr[0] = 1aaa aaaa ; res1 = 1111 1111 ... 1111 1111  1111 1111  1aaa aaaa
  // ptr[1] = 1bbb bbbb ; res2 = 1111 1111 ... 1111 1111  11bb bbbb  b111 1111
  // ptr[2] = 1ccc cccc ; res3 = 0000 0000 ... 000c cccc  cc11 1111  1111 1111
  //                             ---------------------------------------------
  //        res1 & res2 & res3 = 0000 0000 ... 000c cccc  ccbb bbbb  baaa aaaa
  //
  // On x86-64, a shld from a single register filled with enough 1s in the high
  // bits can accomplish all this in one instruction. It so happens that res1
  // has 57 high bits of ones, which is enough for the largest shift done.
  //
  // Just as importantly, by keeping results in res1, res2, and res3, we take
  // advantage of the superscalar abilities of the CPU.
  //ABSL_DCHECK_EQ(res1 >> 7, -1);
  uint64_t ones = res1;  // save the high 1 bits from res1 (input to SHLD)
  int64_t res2, res3;    // accumulated result chunks

if (!shift_left_fill_with_ones_was_negative<1>(ptr[1], ones, res2))
    goto done2;
  if (!shift_left_fill_with_ones_was_negative<2>(ptr[2], ones, res3))
    goto done3;

// For the remainder of the chunks, check the sign of the AND result.
  res1 &= shift_left_fill_with_ones<3>(ptr[3], ones);
  if (res1 >= 0) goto done4;
  res2 &= shift_left_fill_with_ones<4>(ptr[4], ones);
  if (res2 >= 0) goto done5;
  res3 &= shift_left_fill_with_ones<5>(ptr[5], ones);
  if (res3 >= 0) goto done6;
  res1 &= shift_left_fill_with_ones<6>(ptr[6], ones);
  if (res1 >= 0) goto done7;
  res2 &= shift_left_fill_with_ones<7>(ptr[7], ones);
  if (res2 >= 0) goto done8;
  res3 &= shift_left_fill_with_ones<8>(ptr[8], ones);
  if (res3 >= 0) goto done9;
  // For valid 64bit varints, the 10th byte/ptr[9] should be exactly 1. In this
  // case, the continuation bit of ptr[8] already set the top bit of res3
  // correctly, so all we have to do is check that the expected case is true.
  if (PROTOBUF_PREDICT_TRUE(ptr[9] == 1)) goto done10;

if (PROTOBUF_PREDICT_FALSE(ptr[9] & 0x80)) {
    // If the continue bit is set, it is an unterminated varint.
    return {nullptr, 0};
  }

// A zero value of the first bit of the 10th byte represents an
  // over-serialized varint. This case should not happen, but if does (say, due
  // to a nonconforming serializer), deassert the continuation bit that came
  // from ptr[8].
  if ((ptr[9] & 1) == 0) {
#if defined(__GCC_ASM_FLAG_OUTPUTS__) && defined(__x86_64__)
    // Use a small instruction since this is an uncommon code path.
    asm("btcq $63,%0" : "+r"(res3));
#else
    res3 ^= static_cast<uint64_t>(1) << 63;
#endif
  }
  goto done10;

done2:
  return {p + 2, res1 & res2};
done3:
  return {p + 3, res1 & res2 & res3};
done4:
  return {p + 4, res1 & res2 & res3};
done5:
  return {p + 5, res1 & res2 & res3};
done6:
  return {p + 6, res1 & res2 & res3};
done7:
  return {p + 7, res1 & res2 & res3};
done8:
  return {p + 8, res1 & res2 & res3};
done9:
  return {p + 9, res1 & res2 & res3};
done10:
  return {p + 10, res1 & res2 & res3};
}

class ParseContext;

template <typename T>
  static inline T& RefAt(void* x, size_t offset) {
    T* target = reinterpret_cast<T*>(static_cast<char*>(x) + offset);
    return *target;
  }

template <typename T>
  static inline const T& RefAt(const void* x, size_t offset) {
    const T* target =
        reinterpret_cast<const T*>(static_cast<const char*>(x) + offset);
    return *target;
  }

class MessageLite;

#define PROTOBUF_TC_PARAM_DECL                 \
      MessageLite *msg, const char *ptr, \
      ParseContext *ctx,   \
      TcFieldData data,    \
      const void *table, uint64_t hasbits
// PROTOBUF_TC_PARAM_PASS passes values to match PROTOBUF_TC_PARAM_DECL.
#define PROTOBUF_TC_PARAM_PASS msg, ptr, ctx, data, table, hasbits

static const char* ToTagDispatch(PROTOBUF_TC_PARAM_DECL);
static const char* MiniParse(PROTOBUF_TC_PARAM_DECL);
static const char* Error(PROTOBUF_TC_PARAM_DECL);

template <class VarintType>
inline __attribute__((always_inline))  std::pair<const char*, VarintType>
ParseFallbackPair(const char* p, int64_t res1) {
  constexpr bool kIs64BitVarint = std::is_same<VarintType, uint64_t>::value ||
                                  std::is_same<VarintType, int64_t>::value;
  constexpr bool kIs32BitVarint = std::is_same<VarintType, uint32_t>::value ||
                                  std::is_same<VarintType, int32_t>::value;
  static_assert(kIs64BitVarint || kIs32BitVarint,
                "Only 32 or 64 bit varints are supported");
  auto ptr = reinterpret_cast<const int8_t*>(p);

if (!shift_left_fill_with_ones_was_negative<1>(ptr[1], ones, res2))
    goto done2;
  if (!shift_left_fill_with_ones_was_negative<2>(ptr[2], ones, res3))
    goto done3;

// For the remainder of the chunks, check the sign of the AND result.
  res2 &= shift_left_fill_with_ones<3>(ptr[3], ones);
  if (res2 >= 0) goto done4;
  res1 &= shift_left_fill_with_ones<4>(ptr[4], ones);
  if (res1 >= 0) goto done5;
  if (kIs64BitVarint) {
    res2 &= shift_left_fill_with_ones<5>(ptr[5], ones);
    if (res2 >= 0) goto done6;
    res3 &= shift_left_fill_with_ones<6>(ptr[6], ones);
    if (res3 >= 0) goto done7;
    res1 &= shift_left_fill_with_ones<7>(ptr[7], ones);
    if (res1 >= 0) goto done8;
    res3 &= shift_left_fill_with_ones<8>(ptr[8], ones);
    if (res3 >= 0) goto done9;
  } else if (kIs32BitVarint) {
    if (PROTOBUF_PREDICT_TRUE(!(ptr[5] & 0x80))) goto done6;
    if (PROTOBUF_PREDICT_TRUE(!(ptr[6] & 0x80))) goto done7;
    if (PROTOBUF_PREDICT_TRUE(!(ptr[7] & 0x80))) goto done8;
    if (PROTOBUF_PREDICT_TRUE(!(ptr[8] & 0x80))) goto done9;
  }

// For valid 64bit varints, the 10th byte/ptr[9] should be exactly 1. In this
  // case, the continuation bit of ptr[8] already set the top bit of res3
  // correctly, so all we have to do is check that the expected case is true.
  if (PROTOBUF_PREDICT_TRUE(kIs64BitVarint && ptr[9] == 1)) goto done10;

if (PROTOBUF_PREDICT_FALSE(ptr[9] & 0x80)) {
    // If the continue bit is set, it is an unterminated varint.
    return {nullptr, 0};
  }

// A zero value of the first bit of the 10th byte represents an
  // over-serialized varint. This case should not happen, but if does (say, due
  // to a nonconforming serializer), deassert the continuation bit that came
  // from ptr[8].
  if (kIs64BitVarint && ((ptr[9] & 1) == 0)) {
#if defined(__GCC_ASM_FLAG_OUTPUTS__) && defined(__x86_64__)
    // Use a small instruction since this is an uncommon code path.
    asm("btcq $63,%0" : "+r"(res3));
#else
    res3 ^= static_cast<uint64_t>(1) << 63;
#endif
  }
  goto done10;

const char* FastTV64S1(PROTOBUF_TC_PARAM_DECL) {
    constexpr int hasbit_idx = 0;
    constexpr int data_offset = 24;
    using FieldType = unsigned long;
  using TagType = uint8_t;
  // super-early success test...
  if (PROTOBUF_PREDICT_TRUE(((data.data) & 0x80FF) == 0)) {
    ptr += sizeof(TagType);  // Consume tag
    if (hasbit_idx < 32) {
      hasbits |= (uint64_t{1} << hasbit_idx);
    }
    uint8_t value = data.data >> 8;
    RefAt<FieldType>(msg, data_offset) = value;
    ptr += 1;
    [[clang::musttail]] return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
  }
  if (PROTOBUF_PREDICT_FALSE(data.coded_tag<TagType>() != 0)) {
    [[clang::musttail]] return MiniParse(PROTOBUF_TC_PARAM_PASS);
  }
  ptr += sizeof(TagType);  // Consume tag
  if (hasbit_idx < 32) {
    hasbits |= (uint64_t{1} << hasbit_idx);
  }
#ifdef OLD
  auto tmp = Parse64FallbackPair(ptr, static_cast<int8_t>(data.data >> 8));
#else
  auto tmp = ParseFallbackPair<uint64_t>(ptr, static_cast<int8_t>(data.data >> 8));
#endif
  data.data = 0;  // Indicate to the compiler that we don't need this anymore.
  ptr = tmp.first;
  if (PROTOBUF_PREDICT_FALSE(ptr == nullptr)) {
    return Error(PROTOBUF_TC_PARAM_PASS);
  }

RefAt<FieldType>(msg, data_offset) = static_cast<FieldType>(tmp.second);
  [[clang::musttail]] return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
}

const char* FastTV32S1(PROTOBUF_TC_PARAM_DECL) {
  using TagType = uint8_t;
  constexpr int hasbit_idx = 0;
    constexpr int data_offset = 24;
    using FieldType = unsigned long;
  // super-early success test...
  if (PROTOBUF_PREDICT_TRUE(((data.data) & 0x80FF) == 0)) {
    ptr += sizeof(TagType);  // Consume tag
    if (hasbit_idx < 32) {
      hasbits |= (uint64_t{1} << hasbit_idx);
    }
    uint8_t value = data.data >> 8;
    RefAt<FieldType>(msg, data_offset) = value;
    ptr += 1;
    [[clang::musttail]] return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
  }
  if (PROTOBUF_PREDICT_FALSE(data.coded_tag<TagType>() != 0)) {
    [[clang::musttail]] return MiniParse(PROTOBUF_TC_PARAM_PASS);
  }
  ptr += sizeof(TagType);  // Consume tag
  if (hasbit_idx < 32) {
    hasbits |= (uint64_t{1} << hasbit_idx);
  }

#ifndef OLD
  auto tmp = ParseFallbackPair<uint32_t>(ptr, static_cast<int8_t>(data.data >> 8));
  data.data = 0;  // Indicate to the compiler that we don't need this anymore.
  ptr = tmp.first;
  if (PROTOBUF_PREDICT_FALSE(ptr == nullptr)) {
    return Error(PROTOBUF_TC_PARAM_PASS);
  }

RefAt<FieldType>(msg, data_offset) = static_cast<FieldType>(tmp.second);
  [[clang::musttail]] return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
#else
   // Few registers
  auto* out = &RefAt<FieldType>(msg, data_offset);
  uint64_t res = 0xFF & (data.data >> 8);
  /* if (PROTOBUF_PREDICT_FALSE(res & 0x80)) */ {
    res = RotRight7AndReplaceLowByte(res, ptr[1]);
    if (PROTOBUF_PREDICT_FALSE(res & 0x80)) {
      res = RotRight7AndReplaceLowByte(res, ptr[2]);
      if (PROTOBUF_PREDICT_FALSE(res & 0x80)) {
        res = RotRight7AndReplaceLowByte(res, ptr[3]);
        if (PROTOBUF_PREDICT_FALSE(res & 0x80)) {
          res = RotRight7AndReplaceLowByte(res, ptr[4]);
          if (PROTOBUF_PREDICT_FALSE(res & 0x80)) {
            if (PROTOBUF_PREDICT_FALSE(ptr[5] & 0x80)) {
              if (PROTOBUF_PREDICT_FALSE(ptr[6] & 0x80)) {
                if (PROTOBUF_PREDICT_FALSE(ptr[7] & 0x80)) {
                  if (PROTOBUF_PREDICT_FALSE(ptr[8] & 0x80)) {
                    if (ptr[9] & 0x80) return Error(PROTOBUF_TC_PARAM_PASS);
                    *out = RotateLeft(res, 28);
                    ptr += 10;
                    PROTOBUF_MUSTTAIL return ToTagDispatch(
                        PROTOBUF_TC_PARAM_PASS);
                  }
                  *out = RotateLeft(res, 28);
                  ptr += 9;
                  PROTOBUF_MUSTTAIL return ToTagDispatch(
                      PROTOBUF_TC_PARAM_PASS);
                }
                *out = RotateLeft(res, 28);
                ptr += 8;
                PROTOBUF_MUSTTAIL return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
              }
              *out = RotateLeft(res, 28);
              ptr += 7;
              PROTOBUF_MUSTTAIL return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
            }
            *out = RotateLeft(res, 28);
            ptr += 6;
            PROTOBUF_MUSTTAIL return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
          }
          *out = RotateLeft(res, 28);
          ptr += 5;
          PROTOBUF_MUSTTAIL return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
        }
        *out = RotateLeft(res, 21);
        ptr += 4;
        PROTOBUF_MUSTTAIL return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
      }
      *out = RotateLeft(res, 14);
      ptr += 3;
      PROTOBUF_MUSTTAIL return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
    }
    *out = RotateLeft(res, 7);
    ptr += 2;
    PROTOBUF_MUSTTAIL return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
  }
  *out = res;
  ptr += 1;
  PROTOBUF_MUSTTAIL return ToTagDispatch(PROTOBUF_TC_PARAM_PASS);
#endif
}

uint64_t handPDEP_7F7F7F7F7F7F7F7F(uint64_t value) {
  // 1. Reshape value into two halves, each of which have 28 bits
#if defined(__aarch64__)
  uint64_t top28 = value & 0x00FFFFFFF0000000;
  uint64_t bot28 = value & 0x000000000FFFFFFF;
  value = (top28 << 4) + bot28;
#else
  value <<= 4;
  asm("" : "+r"(value));  // Improve clang
  value = (value & 0x0FFFFFFF00000000) | (static_cast<uint32_t>(value) >> 4);
#endif
  // 2. Reshape value into four quarters, each of which have 14 bits
  uint64_t top14s = value & 0xFFFFC000'0FFFC000;
  uint64_t bot14s = value - top14s;
  value = bot14s + (top14s << 2);
  // 3. Reshape value into eight bytes, each of which have 7 bits
  uint64_t top7s = value & 0x3F80'3F80'3F80'3F80;
  value += top7s;
  return value;
}