third_party/pigweed/repo/pw_varint/public/pw_varint/varint.h

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14 #pragma once
  15
  16 #include <stddef.h>
  17 #include <stdint.h>
  18
  19 #include "pw_preprocessor/compiler.h"
  20
  21 #ifdef __cplusplus
  22 extern "C" {
  23 #endif
  24
  25 // Expose a subset of the varint API for use in C code.
  26
  27 size_t pw_VarintEncode(uint64_t integer, void* output, size_t output_size);
  28 size_t pw_VarintZigZagEncode(int64_t integer, void* output, size_t output_size);
  29
  30 size_t pw_VarintDecode(const void* input, size_t input_size, uint64_t* output);
  31 size_t pw_VarintZigZagDecode(const void* input,
  32                              size_t input_size,
  33                              int64_t* output);
  34
  35 // Returns the size of an when encoded as a varint.
  36 size_t pw_VarintEncodedSize(uint64_t integer);
  37 size_t pw_VarintZigZagEncodedSize(int64_t integer);
  38
  39 #ifdef __cplusplus
  40
  41 }  // extern "C"
  42
  43 #include <span>
  44 #include <type_traits>
  45
  46 #include "pw_polyfill/language_feature_macros.h"
  47
  48 namespace pw {
  49 namespace varint {
  50
  51 // The maximum number of bytes occupied by an encoded varint.
  52 PW_INLINE_VARIABLE constexpr size_t kMaxVarint32SizeBytes = 5;
  53 PW_INLINE_VARIABLE constexpr size_t kMaxVarint64SizeBytes = 10;
  54
  55 // ZigZag encodes a signed integer. This maps small negative numbers to small,
  56 // unsigned positive numbers, which improves their density for LEB128 encoding.
  57 //
  58 // ZigZag encoding works by moving the sign bit from the most-significant bit to
  59 // the least-significant bit. For the signed k-bit integer n, the formula is
  60 //
  61 //   (n << 1) ^ (n >> (k - 1))
  62 //
  63 // See the following for a description of ZigZag encoding:
  64 //   https://developers.google.com/protocol-buffers/docs/encoding#types
  65 template <typename T>
  66 constexpr std::make_unsigned_t<T> ZigZagEncode(T n) {
  67   static_assert(std::is_signed<T>(), "Zig-zag encoding is for signed integers");
  68   using U = std::make_unsigned_t<T>;
  69   return (static_cast<U>(n) << 1) ^ static_cast<U>(n >> (sizeof(T) * 8 - 1));
  70 }
  71
  72 // ZigZag decodes a signed integer.
  73 // The calculation is done modulo std::numeric_limits<T>::max()+1, so the
  74 // unsigned integer overflows are intentional.
  75 template <typename T>
  76 constexpr std::make_signed_t<T> ZigZagDecode(T n)
  77     PW_NO_SANITIZE("unsigned-integer-overflow") {
  78   static_assert(std::is_unsigned<T>(),
  79                 "Zig-zag decoding is for unsigned integers");
  80   return static_cast<std::make_signed_t<T>>((n >> 1) ^ (~(n & 1) + 1));
  81 }
  82
  83 // Encodes a uint64_t with Little-Endian Base 128 (LEB128) encoding.
  84 inline size_t EncodeLittleEndianBase128(uint64_t integer,
  85                                         const std::span<std::byte>& output) {
  86   return pw_VarintEncode(integer, output.data(), output.size());
  87 }
  88
  89 // Encodes the provided integer using a variable-length encoding and returns the
  90 // number of bytes written.
  91 //
  92 // The encoding is the same as used in protocol buffers. Signed integers are
  93 // ZigZag encoded to remove leading 1s from small negative numbers, then the
  94 // resulting number is encoded as Little Endian Base 128 (LEB128). Unsigned
  95 // integers are encoded directly as LEB128.
  96 //
  97 // Returns the number of bytes written or 0 if the result didn't fit in the
  98 // encoding buffer.
  99 template <typename T>
 100 size_t Encode(T integer, const std::span<std::byte>& output) {
 101   if (std::is_signed<T>()) {
 102     return pw_VarintZigZagEncode(integer, output.data(), output.size());
 103   } else {
 104     return pw_VarintEncode(integer, output.data(), output.size());
 105   }
 106 }
 107
 108 // Decodes a varint-encoded value. If reading into a signed integer, the value
 109 // is ZigZag decoded.
 110 //
 111 // Returns the number of bytes read from the input if successful. Returns zero
 112 // if the result does not fit in a int64_t / uint64_t or if the input is
 113 // exhausted before the number terminates. Reads a maximum of 10 bytes.
 114 //
 115 // The following example decodes multiple varints from a buffer:
 116 //
 117 //   while (!data.empty()) {
 118 //     int64_t value;
 119 //     size_t bytes = Decode(data, &value);
 120 //
 121 //     if (bytes == 0u) {
 122 //       return Status::DataLoss();
 123 //     }
 124 //     results.push_back(value);
 125 //     data = data.subspan(bytes)
 126 //   }
 127 //
 128 inline size_t Decode(const std::span<const std::byte>& input, int64_t* value) {
 129   return pw_VarintZigZagDecode(input.data(), input.size(), value);
 130 }
 131
 132 inline size_t Decode(const std::span<const std::byte>& input, uint64_t* value) {
 133   return pw_VarintDecode(input.data(), input.size(), value);
 134 }
 135
 136 // Returns a size of an integer when encoded as a varint.
 137 constexpr size_t EncodedSize(uint64_t integer) {
 138   return integer == 0 ? 1 : (64 - __builtin_clzll(integer) + 6) / 7;
 139 }
 140
 141 // Returns a size of an signed integer when ZigZag encoded as a varint.
 142 constexpr size_t ZigZagEncodedSize(int64_t integer) {
 143   return EncodedSize(ZigZagEncode(integer));
 144 }
 145
 146 }  // namespace varint
 147 }  // namespace pw
 148
 149 #endif  // __cplusplus