varint.h

Go to the documentation of this file.

// Copyright 2023 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#pragma once
 
 
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
 
#include "pw_preprocessor/compiler.h"
 
#ifdef __cplusplus
extern "C" {
#endif
 
#define PW_VARINT_MAX_INT32_SIZE_BYTES 5
 
#define PW_VARINT_MAX_INT64_SIZE_BYTES 10
 
size_t pw_varint_Encode32(uint32_t integer,
                          void* output,
                          size_t output_size_bytes);
 
size_t pw_varint_Encode64(uint64_t integer,
                          void* output,
                          size_t output_size_bytes);
 
static inline uint32_t pw_varint_ZigZagEncode32(int32_t n) {
  return (uint32_t)((uint32_t)n << 1) ^ (uint32_t)(n >> (sizeof(n) * 8 - 1));
}
 
static inline uint64_t pw_varint_ZigZagEncode64(int64_t n) {
  return (uint64_t)((uint64_t)n << 1) ^ (uint64_t)(n >> (sizeof(n) * 8 - 1));
}
 
static inline uint8_t pw_varint_EncodeOneByte32(uint32_t* integer) {
  const uint8_t bits = (uint8_t)((*integer & 0x7Fu) | 0x80u);
  *integer >>= 7;
  return bits;
}
 
static inline uint8_t pw_varint_EncodeOneByte64(uint64_t* integer) {
  const uint8_t bits = (uint8_t)((*integer & 0x7Fu) | 0x80u);
  *integer >>= 7;
  return bits;
}
 
static inline int32_t pw_varint_ZigZagDecode32(uint32_t n)
    PW_NO_SANITIZE("unsigned-integer-overflow") {
  return (int32_t)((n >> 1) ^ (~(n & 1) + 1));
}
 
static inline int64_t pw_varint_ZigZagDecode64(uint64_t n)
    PW_NO_SANITIZE("unsigned-integer-overflow") {
  return (int64_t)((n >> 1) ^ (~(n & 1) + 1));
}
 
size_t pw_varint_Decode32(const void* input,
                          size_t input_size_bytes,
                          uint32_t* output);
 
size_t pw_varint_Decode64(const void* input,
                          size_t input_size_bytes,
                          uint64_t* output);
 
static inline bool pw_varint_DecodeOneByte32(uint8_t byte,
                                             size_t count,
                                             uint32_t* value) {
  *value |= (uint32_t)(byte & 0x7fu) << (count * 7);
  return (byte & 0x80u) != 0u;
}
 
static inline bool pw_varint_DecodeOneByte64(uint8_t byte,
                                             size_t count,
                                             uint64_t* value) {
  *value |= (uint64_t)(byte & 0x7fu) << (count * 7);
  return (byte & 0x80u) != 0u;
}
 
#define PW_VARINT_ENCODED_SIZE_BYTES(value)        \
  ((unsigned long long)value < (1u << 7)      ? 1u \
   : (unsigned long long)value < (1u << 14)   ? 2u \
   : (unsigned long long)value < (1u << 21)   ? 3u \
   : (unsigned long long)value < (1u << 28)   ? 4u \
   : (unsigned long long)value < (1llu << 35) ? 5u \
   : (unsigned long long)value < (1llu << 42) ? 6u \
   : (unsigned long long)value < (1llu << 49) ? 7u \
   : (unsigned long long)value < (1llu << 56) ? 8u \
   : (unsigned long long)value < (1llu << 63) ? 9u \
                                              : 10u)
 
size_t pw_varint_EncodedSizeBytes(uint64_t integer);
 
typedef enum {
  PW_VARINT_ZERO_TERMINATED_LEAST_SIGNIFICANT = 0,
  PW_VARINT_ZERO_TERMINATED_MOST_SIGNIFICANT = 1,
  PW_VARINT_ONE_TERMINATED_LEAST_SIGNIFICANT = 2,
  PW_VARINT_ONE_TERMINATED_MOST_SIGNIFICANT = 3,
} pw_varint_Format;
 
size_t pw_varint_EncodeCustom(uint64_t integer,
                              void* output,
                              size_t output_size,
                              pw_varint_Format format);
 
size_t pw_varint_DecodeCustom(const void* input,
                              size_t input_size,
                              uint64_t* output,
                              pw_varint_Format format);
 
#ifdef __cplusplus
 
}  // extern "C"
 
#include <limits>
#include <type_traits>
 
#include "lib/stdcompat/bit.h"
#include "pw_span/span.h"
 
namespace pw {
namespace varint {
 
inline constexpr size_t kMaxVarint32SizeBytes = PW_VARINT_MAX_INT32_SIZE_BYTES;
 
inline constexpr size_t kMaxVarint64SizeBytes = PW_VARINT_MAX_INT64_SIZE_BYTES;
 
template <typename T>
constexpr std::make_unsigned_t<T> ZigZagEncode(T n) {
  static_assert(std::is_signed<T>(), "Zig-zag encoding is for signed integers");
  using U = std::make_unsigned_t<T>;
  return static_cast<U>(static_cast<U>(n) << 1) ^
         static_cast<U>(n >> (sizeof(T) * 8 - 1));
}
 
template <typename T>
constexpr std::make_signed_t<T> ZigZagDecode(T n)
    PW_NO_SANITIZE("unsigned-integer-overflow") {
  static_assert(std::is_unsigned<T>(),
                "Zig-zag decoding is for unsigned integers");
  return static_cast<std::make_signed_t<T>>((n >> 1) ^ (~(n & 1) + 1));
}
 
template <typename T,
          typename = std::enable_if_t<std::is_integral<T>::value ||
                                      std::is_convertible<T, uint64_t>::value>>
constexpr size_t EncodedSize(T integer) {
  if (integer == 0) {
    return 1;
  }
  return static_cast<size_t>(
      (64 - cpp20::countl_zero(static_cast<uint64_t>(integer)) + 6) / 7);
}
 
inline size_t EncodeLittleEndianBase128(uint64_t integer,
                                        const span<std::byte>& output) {
  return pw_varint_Encode64(integer, output.data(), output.size());
}
 
template <typename T>
size_t Encode(T integer, const span<std::byte>& output) {
  if (std::is_signed<T>()) {
    using Signed =
        std::conditional_t<std::is_signed<T>::value, T, std::make_signed_t<T>>;
    return EncodeLittleEndianBase128(ZigZagEncode(static_cast<Signed>(integer)),
                                     output);
  } else {
    using Unsigned = std::
        conditional_t<std::is_signed<T>::value, std::make_unsigned_t<T>, T>;
    return EncodeLittleEndianBase128(static_cast<Unsigned>(integer), output);
  }
}
 
inline size_t Decode(const span<const std::byte>& input, int64_t* output) {
  uint64_t value = 0;
  size_t bytes_read = pw_varint_Decode64(input.data(), input.size(), &value);
  *output = pw_varint_ZigZagDecode64(value);
  return bytes_read;
}
 
inline size_t Decode(const span<const std::byte>& input, uint64_t* value) {
  return pw_varint_Decode64(input.data(), input.size(), value);
}
 
enum class Format {
  kZeroTerminatedLeastSignificant = PW_VARINT_ZERO_TERMINATED_LEAST_SIGNIFICANT,
  kZeroTerminatedMostSignificant = PW_VARINT_ZERO_TERMINATED_MOST_SIGNIFICANT,
  kOneTerminatedLeastSignificant = PW_VARINT_ONE_TERMINATED_LEAST_SIGNIFICANT,
  kOneTerminatedMostSignificant = PW_VARINT_ONE_TERMINATED_MOST_SIGNIFICANT,
};
 
inline size_t Encode(uint64_t value, span<std::byte> output, Format format) {
  return pw_varint_EncodeCustom(value,
                                output.data(),
                                output.size(),
                                static_cast<pw_varint_Format>(format));
}
 
inline size_t Decode(span<const std::byte> input,
                     uint64_t* value,
                     Format format) {
  return pw_varint_DecodeCustom(
      input.data(), input.size(), value, static_cast<pw_varint_Format>(format));
}
 
constexpr uint64_t MaxValueInBytes(size_t bytes) {
  return bytes >= kMaxVarint64SizeBytes ? std::numeric_limits<uint64_t>::max()
                                        : (uint64_t(1) << (7 * bytes)) - 1;
}
 
}  // namespace varint
}  // namespace pw
 
#endif  // __cplusplus