varint.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <limits>
#include <type_traits>
#include "lib/stdcompat/bit.h"
#include "pw_bytes/span.h"
#include "pw_preprocessor/compiler.h"

Go to the source code of this file.

Namespaces
namespace	pw
	The Pigweed namespace.

Macros
#define	PW_VARINT_MAX_INT32_SIZE_BYTES   5
	Maximum size of an LEB128-encoded uint32_t.
#define	PW_VARINT_MAX_INT64_SIZE_BYTES   10
	Maximum size of an LEB128-encoded uint64_t.
#define	PW_VARINT_ENCODED_SIZE_BYTES(value)

Enumerations
enum	pw_varint_Format { 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 }
	Describes a custom varint format.
enum class	pw::varint::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 }
	Describes a custom varint format.

Functions
constexpr uint64_t	pw::varint::MaxValueInBytes (size_t bytes)
	Returns the maximum (max) integer value that can be encoded as a varint into the specified number of bytes.
template<typename T , typename = std::enable_if_t<std::is_integral<T>::value || std::is_convertible<T, uint64_t>::value>>
constexpr size_t	pw::varint::EncodedSize (T value)
	Computes the size of an integer when encoded as a varint.
constexpr size_t	pw::varint::EncodeLittleEndianBase128 (uint64_t value, ByteSpan out_encoded)
template<typename T >
constexpr std::byte	pw::varint::EncodeOneByte (T *value)
template<typename T >
constexpr std::make_unsigned_t< T >	pw::varint::ZigZagEncode (T value)
template<typename T >
constexpr bool	pw::varint::DecodeOneByte (std::byte encoded, size_t count, T *out_value)
template<typename T >
constexpr std::make_signed_t< T >	pw::varint::ZigZagDecode (T encoded)
size_t	pw_varint_EncodedSizeBytes (uint64_t value)
	Computes the size of an integer when encoded as a varint.
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)
template<typename U >
constexpr size_t	pw::varint::internal::DecodeUnsigned (ConstByteSpan encoded, U *out_uvalue, size_t max_count)
template<typename U >
constexpr size_t	pw::varint::internal::EncodeUnsigned (U uvalue, ByteSpan out_encoded)
Encode
Encodes the provided integer using a variable-length encoding and returns the number of bytes written. The encoding is the same as used in protocol buffers. Signed integers are ZigZag encoded to remove leading 1s from small negative numbers, then the resulting number is encoded as Little Endian Base 128 (LEB128). Unsigned integers are encoded directly as LEB128. Returns the number of bytes written or 0 if the result didn't fit in the encoding buffer.
template<typename T >
constexpr size_t	pw::varint::Encode (T value, ByteSpan out_encoded)
size_t	pw::varint::Encode (uint64_t value, ByteSpan out_encoded, Format format)
Decode
Decodes a varint-encoded value. If reading into a signed integer, the value is ZigZag decoded. Returns the number of bytes read from the input if successful. Returns zero if the result does not fit in a int64_t/ uint64_t or if the input is exhausted before the number terminates. Reads a maximum of 10 bytes. The following example decodes multiple varints from a buffer: while (!data.empty()) { int64_t value; size_t bytes = Decode(data, &value); if (bytes == 0u) { return Status::DataLoss(); } results.push_back(value); data = data.subspan(bytes) }
template<typename T >
constexpr size_t	pw::varint::Decode (ConstByteSpan encoded, T *out_value)
size_t	pw::varint::Decode (ConstByteSpan encoded, uint64_t *out_value, Format format)

Variables
constexpr size_t	pw::varint::kMaxVarint32SizeBytes = 5
	Maximum size of a varint (LEB128) encoded uint32_t.
constexpr size_t	pw::varint::kMaxVarint64SizeBytes = 10
	Maximum size of a varint (LEB128) encoded uint64_t.

Detailed Description

The pw_varint module provides functions for encoding and decoding variable length integers or varints. For smaller values, varints require less memory than a fixed-size encoding. For example, a 32-bit (4-byte) integer requires 1–5 bytes when varint-encoded.

pw_varint supports custom variable-length encodings with different terminator bit values and positions (

embed:rst:inline :cpp:type:`pw::varint::Format` 

). The basic encoding for unsigned integers is Little Endian Base 128 (LEB128). ZigZag encoding is also supported, which maps negative integers to positive integers to improve encoding density for LEB128.

Protocol Buffers and

embed:rst:inline :ref:`HDLC <module-pw_hdlc>` 

use variable-length integer encodings for integers.

Macro Definition Documentation

PW_VARINT_ENCODED_SIZE_BYTES

#define PW_VARINT_ENCODED_SIZE_BYTES

(

value

)

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)

Macro that returns the encoded size of up to a 64-bit integer. This is inefficient, but is a constant expression if the input is a constant. Use pw_varint_EncodedSizeBytes for runtime encoded size calculation.

Function Documentation

pw_varint_Decode32()

size_t pw_varint_Decode32	(	const void *	encoded,
		size_t	encoded_size,
		uint32_t *	out_value
	)

pw_varint_Decode64()

size_t pw_varint_Decode64	(	const void *	encoded,
		size_t	encoded_size,
		uint64_t *	out_value
	)

pw_varint_DecodeCustom()

size_t pw_varint_DecodeCustom	(	const void *	encoded,
		size_t	encoded_size,
		uint64_t *	out_value,
		pw_varint_Format	format
	)

pw_varint_DecodeOneByte32()

bool pw_varint_DecodeOneByte32	(	uint8_t	encoded,
		size_t	count,
		uint32_t *	out_value
	)

Decodes one byte of an LEB128-encoded integer to a uint32_t.

Returns

true if there is more data to decode (top bit is set).

pw_varint_DecodeOneByte64()

bool pw_varint_DecodeOneByte64	(	uint8_t	encoded,
		size_t	count,
		uint64_t *	out_value
	)

Decodes one byte of an LEB128-encoded integer to a uint32_t.

Returns

true if there is more data to decode (top bit is set).

pw_varint_Encode32()

size_t pw_varint_Encode32	(	uint32_t	value,
		void *	out_encoded,
		size_t	out_encoded_size
	)

pw_varint_Encode64()

size_t pw_varint_Encode64	(	uint64_t	value,
		void *	out_encoded,
		size_t	out_encoded_size
	)

pw_varint_EncodeCustom()

size_t pw_varint_EncodeCustom	(	uint64_t	value,
		void *	out_encoded,
		size_t	out_encoded_size,
		pw_varint_Format	format
	)

pw_varint_EncodedSizeBytes()

size_t pw_varint_EncodedSizeBytes

(

uint64_t

value

)

Computes the size of an integer when encoded as a varint.

Parameters

integer

The integer whose encoded size is to be computed. integer can be signed or unsigned.

Returns

The size of integer when encoded as a varint.

pw_varint_EncodeOneByte32()

uint8_t pw_varint_EncodeOneByte32

(

uint32_t *

value

)

Extracts and encodes 7 bits from the integer. Sets the top bit to indicate more data is coming, which must be cleared if this was the last byte.

pw_varint_EncodeOneByte64()

uint8_t pw_varint_EncodeOneByte64

(

uint64_t *

value

)

Extracts and encodes 7 bits from the integer. Sets the top bit to indicate more data is coming, which must be cleared if this was the last byte.

pw_varint_ZigZagDecode32()

int32_t pw_varint_ZigZagDecode32

(

uint32_t

encoded

)

ZigZag decodes a signed integer.

The calculation is done modulo std::numeric_limits<T>::max()+1, so the unsigned integer overflows are intentional.

pw_varint_ZigZagDecode64()

int64_t pw_varint_ZigZagDecode64

(

uint64_t

encoded

)

ZigZag decodes a signed integer.

The calculation is done modulo std::numeric_limits<T>::max()+1, so the unsigned integer overflows are intentional.

pw_varint_ZigZagEncode32()

uint32_t pw_varint_ZigZagEncode32

(

int32_t

value

)

ZigZag encodes a signed integer. This maps small negative numbers to small, unsigned positive numbers, which improves their density for LEB128 encoding.

ZigZag encoding works by moving the sign bit from the most-significant bit to the least-significant bit. For the signed k-bit integer n, the formula is:

(n << 1) ^ (n >> (k - 1))

See the following for a description of ZigZag encoding: https://protobuf.dev/programming-guides/encoding/#signed-ints

pw_varint_ZigZagEncode64()

uint64_t pw_varint_ZigZagEncode64

(

int64_t

value

)

ZigZag encodes a signed integer. This maps small negative numbers to small, unsigned positive numbers, which improves their density for LEB128 encoding.

ZigZag encoding works by moving the sign bit from the most-significant bit to the least-significant bit. For the signed k-bit integer n, the formula is:

(n << 1) ^ (n >> (k - 1))

See the following for a description of ZigZag encoding: https://protobuf.dev/programming-guides/encoding/#signed-ints