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>
 
#ifdef __cplusplus
 
#include <limits>
#include <type_traits>
 
#include "lib/stdcompat/bit.h"
#include "pw_bytes/span.h"
#include "pw_preprocessor/compiler.h"
 
extern "C" {
#endif  // __cplusplus
 
// C++ API.
 
#define PW_VARINT_MAX_INT32_SIZE_BYTES 5
 
#define PW_VARINT_MAX_INT64_SIZE_BYTES 10
 
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;
 
#ifdef __cplusplus
}  // extern "C"
namespace pw::varint {
 
 
constexpr size_t kMaxVarint32SizeBytes = PW_VARINT_MAX_INT32_SIZE_BYTES;
 
constexpr size_t kMaxVarint64SizeBytes = PW_VARINT_MAX_INT64_SIZE_BYTES;
 
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,
};
 
constexpr uint64_t MaxValueInBytes(size_t bytes) {
  return bytes >= kMaxVarint64SizeBytes ? std::numeric_limits<uint64_t>::max()
                                        : (uint64_t(1) << (7 * bytes)) - 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 value) {
  return value == 0
             ? 1u
             : static_cast<size_t>(
                   (64 - cpp20::countl_zero(static_cast<uint64_t>(value)) + 6) /
                   7);
}
 
template <typename T>
constexpr size_t Encode(T value, ByteSpan out_encoded);
size_t Encode(uint64_t value, ByteSpan out_encoded, Format format);
 
constexpr size_t EncodeLittleEndianBase128(uint64_t value,
                                           ByteSpan out_encoded);
 
template <typename T>
constexpr std::byte EncodeOneByte(T* value);
 
template <typename T>
constexpr std::make_unsigned_t<T> ZigZagEncode(T value);
 
template <typename T>
constexpr size_t Decode(ConstByteSpan encoded, T* out_value);
size_t Decode(ConstByteSpan encoded, uint64_t* out_value, Format format);
 
template <typename T>
[[nodiscard]] constexpr bool DecodeOneByte(std::byte encoded,
                                           size_t count,
                                           T* out_value);
 
template <typename T>
constexpr std::make_signed_t<T> ZigZagDecode(T encoded);
 
}  // namespace pw::varint
extern "C" {
#endif  // __cplusplus
 
// C API.
 
size_t pw_varint_EncodedSizeBytes(uint64_t value);
 
size_t pw_varint_Encode32(uint32_t value,
                          void* out_encoded,
                          size_t out_encoded_size);
 
size_t pw_varint_Encode64(uint64_t value,
                          void* out_encoded,
                          size_t out_encoded_size);
 
size_t pw_varint_EncodeCustom(uint64_t value,
                              void* out_encoded,
                              size_t out_encoded_size,
                              pw_varint_Format format);
 
uint8_t pw_varint_EncodeOneByte32(uint32_t* value);
 
uint8_t pw_varint_EncodeOneByte64(uint64_t* value);
 
uint32_t pw_varint_ZigZagEncode32(int32_t value);
 
uint64_t pw_varint_ZigZagEncode64(int64_t value);
 
size_t pw_varint_Decode32(const void* encoded,
                          size_t encoded_size,
                          uint32_t* out_value);
 
size_t pw_varint_Decode64(const void* encoded,
                          size_t encoded_size,
                          uint64_t* out_value);
 
size_t pw_varint_DecodeCustom(const void* encoded,
                              size_t encoded_size,
                              uint64_t* out_value,
                              pw_varint_Format format);
 
bool pw_varint_DecodeOneByte32(uint8_t encoded,
                               size_t count,
                               uint32_t* out_value);
 
bool pw_varint_DecodeOneByte64(uint8_t encoded,
                               size_t count,
                               uint64_t* out_value);
 
int32_t pw_varint_ZigZagDecode32(uint32_t encoded);
 
int64_t pw_varint_ZigZagDecode64(uint64_t encoded);
 
#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)
 
#ifdef __cplusplus
}  // extern "C"
namespace pw::varint {
 
// Template function implementations.
 
namespace internal {
 
template <typename U>
constexpr size_t DecodeUnsigned(ConstByteSpan encoded,
                                U* out_uvalue,
                                size_t max_count) {
  max_count = std::min(encoded.size(), max_count);
  size_t count = 0;
  bool keep_going = true;
  while (keep_going) {
    if (count >= max_count) {
      *out_uvalue = U(0);
      return 0;
    }
    keep_going = DecodeOneByte(encoded[count], count, out_uvalue);
    ++count;
  }
  return count;
}
 
template <typename U>
constexpr size_t EncodeUnsigned(U uvalue, ByteSpan out_encoded) {
  size_t written = 0;
  do {
    if (written >= out_encoded.size()) {
      return 0u;
    }
    out_encoded[written++] = EncodeOneByte(&uvalue);
  } while (uvalue != 0u);
 
  out_encoded[written - 1] &= static_cast<std::byte>(0x7f);
  return written;
}
 
}  // namespace internal
 
template <typename T>
constexpr size_t Encode(T value, ByteSpan out_encoded) {
  using U = std::conditional_t<sizeof(T) <= sizeof(uint32_t),
                               uint_fast32_t,
                               uint_fast64_t>;
  if constexpr (std::is_signed<T>()) {
    return internal::EncodeUnsigned<U>(ZigZagEncode(value), out_encoded);
  } else {
    return internal::EncodeUnsigned<U>(value, out_encoded);
  }
}
 
template <typename T>
constexpr std::byte EncodeOneByte(T* value) {
  const auto bits = static_cast<std::byte>((*value & 0x7Fu) | 0x80u);
  *value >>= 7;
  return bits;
}
 
template <typename T>
constexpr std::make_unsigned_t<T> ZigZagEncode(T value) {
  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>(value) << 1) ^
         static_cast<U>(value >> (sizeof(T) * 8 - 1));
}
 
constexpr size_t EncodeLittleEndianBase128(uint64_t value,
                                           ByteSpan out_encoded) {
  return Encode(value, out_encoded);
}
 
template <typename T>
constexpr size_t Decode(ConstByteSpan encoded, T* out_value) {
  static_assert(sizeof(T) >= sizeof(uint32_t));
  using U = std::conditional_t<sizeof(T) == sizeof(uint32_t),
                               uint_fast32_t,
                               uint_fast64_t>;
  U uvalue = 0u;
  size_t max_count = sizeof(T) <= sizeof(uint32_t) ? kMaxVarint32SizeBytes
                                                   : kMaxVarint64SizeBytes;
  size_t count = internal::DecodeUnsigned(encoded, &uvalue, max_count);
  if constexpr (std::is_signed_v<T>) {
    *out_value = static_cast<T>(ZigZagDecode(uvalue));
  } else {
    *out_value = static_cast<T>(uvalue);
  }
  return count;
}
 
template <typename T>
[[nodiscard]] constexpr bool DecodeOneByte(std::byte encoded,
                                           size_t count,
                                           T* out_value) {
  auto u8 = static_cast<uint_fast8_t>(encoded);
  *out_value |= static_cast<T>(u8 & 0x7fu) << (count * 7);
  return (u8 & 0x80u) != 0u;
}
 
template <typename T>
constexpr std::make_signed_t<T> ZigZagDecode(T encoded)
    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>>((encoded >> 1) ^
                                            (~(encoded & 1) + 1));
}
 
}  // namespace pw::varint
#endif  // __cplusplus