google/protobuf/varint_shuffle.h

0001 // Protocol Buffers - Google's data interchange format
0002 // Copyright 2023 Google Inc.  All rights reserved.
0003 //
0004 // Use of this source code is governed by a BSD-style
0005 // license that can be found in the LICENSE file or at
0006 // https://developers.google.com/open-source/licenses/bsd
0007
0008 #ifndef GOOGLE_PROTOBUF_VARINT_SHUFFLE_H__
0009 #define GOOGLE_PROTOBUF_VARINT_SHUFFLE_H__
0010
0011 #include <cassert>
0012 #include <cstddef>
0013 #include <cstdint>
0014 #include <type_traits>
0015 #include <utility>
0016
0017 // Must be included last.
0018 #include "google/protobuf/port_def.inc"
0019
0020 namespace google {
0021 namespace protobuf {
0022 namespace internal {
0023
0024 // Shifts "byte" left by n * 7 bits, filling vacated bits from `ones`.
0025 template <int n>
0026 inline PROTOBUF_ALWAYS_INLINE int64_t VarintShlByte(int8_t byte, int64_t ones) {
0027   return static_cast<int64_t>((static_cast<uint64_t>(byte) << n * 7) |
0028                               (static_cast<uint64_t>(ones) >> (64 - n * 7)));
0029 }
0030
0031 // Shifts "byte" left by n * 7 bits, filling vacated bits from `ones` and
0032 // bitwise ANDs the resulting value into the input/output `res` parameter.
0033 // Returns true if the result was not negative.
0034 template <int n>
0035 inline PROTOBUF_ALWAYS_INLINE bool VarintShlAnd(int8_t byte, int64_t ones,
0036                                                 int64_t& res) {
0037   res &= VarintShlByte<n>(byte, ones);
0038   return res >= 0;
0039 }
0040
0041 // Shifts `byte` left by n * 7 bits, filling vacated bits with ones, and
0042 // puts the new value in the output only parameter `res`.
0043 // Returns true if the result was not negative.
0044 template <int n>
0045 inline PROTOBUF_ALWAYS_INLINE bool VarintShl(int8_t byte, int64_t ones,
0046                                              int64_t& res) {
0047   res = VarintShlByte<n>(byte, ones);
0048   return res >= 0;
0049 }
0050
0051 template <typename VarintType, int limit = 10>
0052 inline PROTOBUF_ALWAYS_INLINE const char* ShiftMixParseVarint(const char* p,
0053                                                               int64_t& res1) {
0054   using Signed = std::make_signed_t<VarintType>;
0055   constexpr bool kIs64BitVarint = std::is_same<Signed, int64_t>::value;
0056   constexpr bool kIs32BitVarint = std::is_same<Signed, int32_t>::value;
0057   static_assert(kIs64BitVarint || kIs32BitVarint, "");
0058
0059   // The algorithm relies on sign extension for each byte to set all high bits
0060   // when the varint continues. It also relies on asserting all of the lower
0061   // bits for each successive byte read. This allows the result to be aggregated
0062   // using a bitwise AND. For example:
0063   //
0064   //          8       1          64     57 ... 24     17  16      9  8       1
0065   // ptr[0] = 1aaa aaaa ; res1 = 1111 1111 ... 1111 1111  1111 1111  1aaa aaaa
0066   // ptr[1] = 1bbb bbbb ; res2 = 1111 1111 ... 1111 1111  11bb bbbb  b111 1111
0067   // ptr[2] = 0ccc cccc ; res3 = 0000 0000 ... 000c cccc  cc11 1111  1111 1111
0068   //                             ---------------------------------------------
0069   //        res1 & res2 & res3 = 0000 0000 ... 000c cccc  ccbb bbbb  baaa aaaa
0070   //
0071   // On x86-64, a shld from a single register filled with enough 1s in the high
0072   // bits can accomplish all this in one instruction. It so happens that res1
0073   // has 57 high bits of ones, which is enough for the largest shift done.
0074   //
0075   // Just as importantly, by keeping results in res1, res2, and res3, we take
0076   // advantage of the superscalar abilities of the CPU.
0077   const auto next = [&p] { return static_cast<const int8_t>(*p++); };
0078   const auto last = [&p] { return static_cast<const int8_t>(p[-1]); };
0079
0080   int64_t res2, res3;  // accumulated result chunks
0081   res1 = next();
0082   if (PROTOBUF_PREDICT_TRUE(res1 >= 0)) return p;
0083   if (limit <= 1) goto limit0;
0084
0085   // Densify all ops with explicit FALSE predictions from here on, except that
0086   // we predict length = 5 as a common length for fields like timestamp.
0087   if (PROTOBUF_PREDICT_FALSE(VarintShl<1>(next(), res1, res2))) goto done1;
0088   if (limit <= 2) goto limit1;
0089   if (PROTOBUF_PREDICT_FALSE(VarintShl<2>(next(), res1, res3))) goto done2;
0090   if (limit <= 3) goto limit2;
0091   if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<3>(next(), res1, res2))) goto done2;
0092   if (limit <= 4) goto limit2;
0093   if (PROTOBUF_PREDICT_TRUE(VarintShlAnd<4>(next(), res1, res3))) goto done2;
0094   if (limit <= 5) goto limit2;
0095
0096   if (kIs64BitVarint) {
0097     if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<5>(next(), res1, res2))) goto done2;
0098     if (limit <= 6) goto limit2;
0099     if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<6>(next(), res1, res3))) goto done2;
0100     if (limit <= 7) goto limit2;
0101     if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<7>(next(), res1, res2))) goto done2;
0102     if (limit <= 8) goto limit2;
0103     if (PROTOBUF_PREDICT_FALSE(VarintShlAnd<8>(next(), res1, res3))) goto done2;
0104     if (limit <= 9) goto limit2;
0105   } else {
0106     // An overlong int32 is expected to span the full 10 bytes
0107     if (PROTOBUF_PREDICT_FALSE(!(next() & 0x80))) goto done2;
0108     if (limit <= 6) goto limit2;
0109     if (PROTOBUF_PREDICT_FALSE(!(next() & 0x80))) goto done2;
0110     if (limit <= 7) goto limit2;
0111     if (PROTOBUF_PREDICT_FALSE(!(next() & 0x80))) goto done2;
0112     if (limit <= 8) goto limit2;
0113     if (PROTOBUF_PREDICT_FALSE(!(next() & 0x80))) goto done2;
0114     if (limit <= 9) goto limit2;
0115   }
0116
0117   // For valid 64bit varints, the 10th byte/ptr[9] should be exactly 1. In this
0118   // case, the continuation bit of ptr[8] already set the top bit of res3
0119   // correctly, so all we have to do is check that the expected case is true.
0120   if (PROTOBUF_PREDICT_TRUE(next() == 1)) goto done2;
0121
0122   if (PROTOBUF_PREDICT_FALSE(last() & 0x80)) {
0123     // If the continue bit is set, it is an unterminated varint.
0124     return nullptr;
0125   }
0126
0127   // A zero value of the first bit of the 10th byte represents an
0128   // over-serialized varint. This case should not happen, but if does (say, due
0129   // to a nonconforming serializer), deassert the continuation bit that came
0130   // from ptr[8].
0131   if (kIs64BitVarint && (last() & 1) == 0) {
0132     static constexpr int bits = 64 - 1;
0133 #if defined(__GCC_ASM_FLAG_OUTPUTS__) && defined(__x86_64__)
0134     // Use a small instruction since this is an uncommon code path.
0135     asm("btc %[bits], %[res3]" : [res3] "+r"(res3) : [bits] "i"(bits));
0136 #else
0137     res3 ^= int64_t{1} << bits;
0138 #endif
0139   }
0140
0141 done2:
0142   res2 &= res3;
0143 done1:
0144   res1 &= res2;
0145   PROTOBUF_ASSUME(p != nullptr);
0146   return p;
0147 limit2:
0148   res2 &= res3;
0149 limit1:
0150   res1 &= res2;
0151 limit0:
0152   PROTOBUF_ASSUME(p != nullptr);
0153   PROTOBUF_ASSUME(res1 < 0);
0154   return p;
0155 }
0156
0157 }  // namespace internal
0158 }  // namespace protobuf
0159 }  // namespace google
0160
0161 #include "google/protobuf/port_undef.inc"
0162
0163 #endif  // GOOGLE_PROTOBUF_VARINT_SHUFFLE_H__