protozero  1.7.0
Minimalistic protocol buffer decoder and encoder in C++.
varint.hpp
Go to the documentation of this file.
1 #ifndef PROTOZERO_VARINT_HPP
2 #define PROTOZERO_VARINT_HPP
3 
4 /*****************************************************************************
5 
6 protozero - Minimalistic protocol buffer decoder and encoder in C++.
7 
8 This file is from https://github.com/mapbox/protozero where you can find more
9 documentation.
10 
11 *****************************************************************************/
12 
19 #include "buffer_tmpl.hpp"
20 #include "exception.hpp"
21 
22 #include <cstdint>
23 
24 namespace protozero {
25 
29 constexpr const int8_t max_varint_length = sizeof(uint64_t) * 8 / 7 + 1;
30 
31 namespace detail {
32 
33  // from https://github.com/facebook/folly/blob/master/folly/Varint.h
34  inline uint64_t decode_varint_impl(const char** data, const char* end) {
35  const auto* begin = reinterpret_cast<const int8_t*>(*data);
36  const auto* iend = reinterpret_cast<const int8_t*>(end);
37  const int8_t* p = begin;
38  uint64_t val = 0;
39 
40  if (iend - begin >= max_varint_length) { // fast path
41  do {
42  int64_t b = *p++;
43  val = ((uint64_t(b) & 0x7fU) ); if (b >= 0) { break; }
44  b = *p++; val |= ((uint64_t(b) & 0x7fU) << 7U); if (b >= 0) { break; }
45  b = *p++; val |= ((uint64_t(b) & 0x7fU) << 14U); if (b >= 0) { break; }
46  b = *p++; val |= ((uint64_t(b) & 0x7fU) << 21U); if (b >= 0) { break; }
47  b = *p++; val |= ((uint64_t(b) & 0x7fU) << 28U); if (b >= 0) { break; }
48  b = *p++; val |= ((uint64_t(b) & 0x7fU) << 35U); if (b >= 0) { break; }
49  b = *p++; val |= ((uint64_t(b) & 0x7fU) << 42U); if (b >= 0) { break; }
50  b = *p++; val |= ((uint64_t(b) & 0x7fU) << 49U); if (b >= 0) { break; }
51  b = *p++; val |= ((uint64_t(b) & 0x7fU) << 56U); if (b >= 0) { break; }
52  b = *p++; val |= ((uint64_t(b) & 0x01U) << 63U); if (b >= 0) { break; }
54  } while (false);
55  } else {
56  unsigned int shift = 0;
57  while (p != iend && *p < 0) {
58  val |= (uint64_t(*p++) & 0x7fU) << shift;
59  shift += 7;
60  }
61  if (p == iend) {
63  }
64  val |= uint64_t(*p++) << shift;
65  }
66 
67  *data = reinterpret_cast<const char*>(p);
68  return val;
69  }
70 
71 } // end namespace detail
72 
90 inline uint64_t decode_varint(const char** data, const char* end) {
91  // If this is a one-byte varint, decode it here.
92  if (end != *data && ((static_cast<uint64_t>(**data) & 0x80U) == 0)) {
93  const auto val = static_cast<uint64_t>(**data);
94  ++(*data);
95  return val;
96  }
97  // If this varint is more than one byte, defer to complete implementation.
98  return detail::decode_varint_impl(data, end);
99 }
100 
113 inline void skip_varint(const char** data, const char* end) {
114  const auto* begin = reinterpret_cast<const int8_t*>(*data);
115  const auto* iend = reinterpret_cast<const int8_t*>(end);
116  const int8_t* p = begin;
117 
118  while (p != iend && *p < 0) {
119  ++p;
120  }
121 
122  if (p - begin >= max_varint_length) {
124  }
125 
126  if (p == iend) {
127  throw end_of_buffer_exception{};
128  }
129 
130  ++p;
131 
132  *data = reinterpret_cast<const char*>(p);
133 }
134 
146 template <typename T>
147 inline int write_varint(T data, uint64_t value) {
148  int n = 1;
149 
150  while (value >= 0x80U) {
151  *data++ = char((value & 0x7fU) | 0x80U);
152  value >>= 7U;
153  ++n;
154  }
155  *data = char(value);
156 
157  return n;
158 }
159 
169 template <typename TBuffer>
170 inline void add_varint_to_buffer(TBuffer* buffer, uint64_t value) {
171  while (value >= 0x80U) {
172  buffer_customization<TBuffer>::push_back(buffer, char((value & 0x7fU) | 0x80U));
173  value >>= 7U;
174  }
175  buffer_customization<TBuffer>::push_back(buffer, char(value));
176 }
177 
185 inline int add_varint_to_buffer(char* data, uint64_t value) noexcept {
186  int n = 1;
187 
188  while (value >= 0x80U) {
189  *data++ = char((value & 0x7fU) | 0x80U);
190  value >>= 7U;
191  ++n;
192  }
193  *data = char(value);
194 
195  return n;
196 }
197 
204 inline int length_of_varint(uint64_t value) noexcept {
205  int n = 1;
206 
207  while (value >= 0x80U) {
208  value >>= 7U;
209  ++n;
210  }
211 
212  return n;
213 }
214 
218 inline constexpr uint32_t encode_zigzag32(int32_t value) noexcept {
219  return (static_cast<uint32_t>(value) << 1U) ^ static_cast<uint32_t>(-static_cast<int32_t>(static_cast<uint32_t>(value) >> 31U));
220 }
221 
225 inline constexpr uint64_t encode_zigzag64(int64_t value) noexcept {
226  return (static_cast<uint64_t>(value) << 1U) ^ static_cast<uint64_t>(-static_cast<int64_t>(static_cast<uint64_t>(value) >> 63U));
227 }
228 
232 inline constexpr int32_t decode_zigzag32(uint32_t value) noexcept {
233  return static_cast<int32_t>((value >> 1U) ^ static_cast<uint32_t>(-static_cast<int32_t>(value & 1U)));
234 }
235 
239 inline constexpr int64_t decode_zigzag64(uint64_t value) noexcept {
240  return static_cast<int64_t>((value >> 1U) ^ static_cast<uint64_t>(-static_cast<int64_t>(value & 1U)));
241 }
242 
243 } // end namespace protozero
244 
245 #endif // PROTOZERO_VARINT_HPP
protozero::varint_too_long_exception
Definition: exception.hpp:41
protozero
All parts of the protozero header-only library are in this namespace.
Definition: basic_pbf_builder.hpp:24
protozero::length_of_varint
int length_of_varint(uint64_t value) noexcept
Definition: varint.hpp:204
protozero::max_varint_length
constexpr const int8_t max_varint_length
Definition: varint.hpp:29
protozero::encode_zigzag64
constexpr uint64_t encode_zigzag64(int64_t value) noexcept
Definition: varint.hpp:225
protozero::decode_zigzag64
constexpr int64_t decode_zigzag64(uint64_t value) noexcept
Definition: varint.hpp:239
protozero::write_varint
int write_varint(T data, uint64_t value)
Definition: varint.hpp:147
protozero::add_varint_to_buffer
void add_varint_to_buffer(TBuffer *buffer, uint64_t value)
Definition: varint.hpp:170
protozero::encode_zigzag32
constexpr uint32_t encode_zigzag32(int32_t value) noexcept
Definition: varint.hpp:218
protozero::decode_zigzag32
constexpr int32_t decode_zigzag32(uint32_t value) noexcept
Definition: varint.hpp:232
exception.hpp
Contains the exceptions used in the protozero library.
protozero::decode_varint
uint64_t decode_varint(const char **data, const char *end)
Definition: varint.hpp:90
protozero::end_of_buffer_exception
Definition: exception.hpp:67
protozero::skip_varint
void skip_varint(const char **data, const char *end)
Definition: varint.hpp:113
buffer_tmpl.hpp
Contains the customization points for buffer implementations.