// Protocol Buffers - Google's data interchange format
// Copyright 2023 Google Inc.  All rights reserved.
//
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file or at
// https://developers.google.com/open-source/licenses/bsd

#ifndef GOOGLE_PROTOBUF_VARINT_SHUFFLE_H__
#define GOOGLE_PROTOBUF_VARINT_SHUFFLE_H__

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <utility>

// Must be included last.
#include "google/protobuf/port_def.inc"

namespace google {
namespace protobuf {
namespace internal {

// Shifts "byte" left by n * 7 bits, filling vacated bits from `ones`.
template <int n>
inline PROTOBUF_ALWAYS_INLINE int64_t VarintShlByte(int8_t byte, int64_t ones) {
  return static_cast<int64_t>((static_cast<uint64_t>(byte) << n * 7) |
                              (static_cast<uint64_t>(ones) >> (64 - n * 7)));
}

// Shifts "byte" left by n * 7 bits, filling vacated bits from `ones` and
// bitwise ANDs the resulting value into the input/output `res` parameter.
// Returns true if the result was not negative.
template <int n>
inline PROTOBUF_ALWAYS_INLINE bool VarintShlAnd(int8_t byte, int64_t ones,
                                                int64_t& res) {
  res &= VarintShlByte<n>(byte, ones);
  return res >= 0;
}

// Shifts `byte` left by n * 7 bits, filling vacated bits with ones, and
// puts the new value in the output only parameter `res`.
// Returns true if the result was not negative.
template <int n>
inline PROTOBUF_ALWAYS_INLINE bool VarintShl(int8_t byte, int64_t ones,
                                             int64_t& res) {
  res = VarintShlByte<n>(byte, ones);
  return res >= 0;
}

template <typename VarintType, int limit = 10>
inline PROTOBUF_ALWAYS_INLINE const char* ShiftMixParseVarint(const char* p,
                                                              int64_t& res1) {
  using Signed = std::make_signed_t<VarintType>;
  constexpr bool kIs64BitVarint = std::is_same<Signed, int64_t>::value;
  constexpr bool kIs32BitVarint = std::is_same<Signed, int32_t>::value;
  static_assert(kIs64BitVarint || kIs32BitVarint, "");

  // 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] = 0ccc 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.
  const auto next = [&p] { return static_cast<const int8_t>(*p++); };
  const auto last = [&p] { return static_cast<const int8_t>(p[-1]); };

  int64_t res2, res3;  // accumulated result chunks
  res1 = next();
  if (PROTOBUF_PREDICT_TRUE(res1 >= 0)) return p;
  if (limit <= 1) goto limit0;

  // Densify all ops with explicit FALSE predictions from here on, except that
  // we predict length = 5 as a common length for fields like timestamp.
  if (PROTOBUF_PREDICT_FALSE(VarintShl<1>(next(), res1, res2))) goto done1;
  if (limit <= 2) goto limit1;
  if (PROTOBUF_PREDICT_FALSE(VarintShl<2>(next(), res1, res3))) goto done2;
  if (limit <= 3) goto limit2;
  if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<3>(next(), res1, res2))) goto done2;
  if (limit <= 4) goto limit2;
  if (PROTOBUF_PREDICT_TRUE(VarintShlAnd<4>(next(), res1, res3))) goto done2;
  if (limit <= 5) goto limit2;

  if (kIs64BitVarint) {
    if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<5>(next(), res1, res2))) goto done2;
    if (limit <= 6) goto limit2;
    if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<6>(next(), res1, res3))) goto done2;
    if (limit <= 7) goto limit2;
    if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<7>(next(), res1, res2))) goto done2;
    if (limit <= 8) goto limit2;
    if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<8>(next(), res1, res3))) goto done2;
    if (limit <= 9) goto limit2;
  } else {
    // An overlong int32 is expected to span the full 10 bytes
    if (PROTOBUF_PREDICT_FALSE(!(next() & 0x80))) goto done2;
    if (limit <= 6) goto limit2;
    if (PROTOBUF_PREDICT_FALSE(!(next() & 0x80))) goto done2;
    if (limit <= 7) goto limit2;
    if (PROTOBUF_PREDICT_FALSE(!(next() & 0x80))) goto done2;
    if (limit <= 8) goto limit2;
    if (PROTOBUF_PREDICT_FALSE(!(next() & 0x80))) goto done2;
    if (limit <= 9) goto limit2;
  }

  // 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(next() == 1)) goto done2;

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

  // 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 && (last() & 1) == 0) {
    static constexpr int bits = 64 - 1;
#if defined(__GCC_ASM_FLAG_OUTPUTS__) && defined(__x86_64__)
    // Use a small instruction since this is an uncommon code path.
    asm("btc %[bits], %[res3]" : [res3] "+r"(res3) : [bits] "i"(bits));
#else
    res3 ^= int64_t{1} << bits;
#endif
  }

done2:
  res2 &= res3;
done1:
  res1 &= res2;
  PROTOBUF_ASSUME(p != nullptr);
  return p;
limit2:
  res2 &= res3;
limit1:
  res1 &= res2;
limit0:
  PROTOBUF_ASSUME(p != nullptr);
  PROTOBUF_ASSUME(res1 < 0);
  return p;
}

}  // namespace internal
}  // namespace protobuf
}  // namespace google

#include "google/protobuf/port_undef.inc"

#endif  // GOOGLE_PROTOBUF_VARINT_SHUFFLE_H__