varint.h File Reference

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include "pw_preprocessor/compiler.h"
#include <limits>
#include <type_traits>
#include "lib/stdcompat/bit.h"
#include "pw_span/span.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
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 uint32_t	pw_varint_ZigZagEncode32 (int32_t n)
	Zig-zag encodes an int32_t, returning it as a uint32_t.
static uint64_t	pw_varint_ZigZagEncode64 (int64_t n)
	Zig-zag encodes an int64_t, returning it as a uint64_t.
static uint8_t	pw_varint_EncodeOneByte32 (uint32_t *integer)
static uint8_t	pw_varint_EncodeOneByte64 (uint64_t *integer)
static int32_t	pw_varint_ZigZagDecode32 (uint32_t n)
	Zig-zag decodes a uint64_t, returning it as an int64_t.
static int64_t	pw_varint_ZigZagDecode64 (uint64_t n)
	Zig-zag decodes a uint64_t, returning it as an int64_t.
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 bool	pw_varint_DecodeOneByte32 (uint8_t byte, size_t count, uint32_t *value)
static bool	pw_varint_DecodeOneByte64 (uint8_t byte, size_t count, uint64_t *value)
size_t	pw_varint_EncodedSizeBytes (uint64_t integer)
	Returns the size of a uint64_t when encoded as a varint (LEB128).
size_t	pw_varint_EncodeCustom (uint64_t integer, void *output, size_t output_size, pw_varint_Format format)
	Encodes a uint64_t using a custom varint format.
size_t	pw_varint_DecodeCustom (const void *input, size_t input_size, uint64_t *output, pw_varint_Format format)
	Decodes a uint64_t using a custom varint format.
template<typename T >
constexpr std::make_unsigned_t< T >	pw::varint::ZigZagEncode (T n)
template<typename T >
constexpr std::make_signed_t< T >	pw::varint::ZigZagDecode (T n)
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 integer)
	Computes the size of an integer when encoded as a varint.
size_t	pw::varint::EncodeLittleEndianBase128 (uint64_t integer, const span< std::byte > &output)
template<typename T >
size_t	pw::varint::Encode (T integer, const span< std::byte > &output)
size_t	pw::varint::Decode (const span< const std::byte > &input, int64_t *output)
size_t	pw::varint::Decode (const span< const std::byte > &input, uint64_t *value)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.
size_t	pw::varint::Encode (uint64_t value, span< std::byte > output, Format format)
	Encodes a varint in a custom format.
size_t	pw::varint::Decode (span< const std::byte > input, uint64_t *value, Format format)
	Decodes a varint from a custom format.
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.

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 *	input,
		size_t	input_size_bytes,
		uint32_t *	output
	)

Decodes an LEB128-encoded integer to a uint32_t.

Returns

the number of bytes read; 0 if decoding failed

pw_varint_Decode64()

size_t pw_varint_Decode64	(	const void *	input,
		size_t	input_size_bytes,
		uint64_t *	output
	)

Decodes an LEB128-encoded integer to a uint64_t.

Returns

the number of bytes read; 0 if decoding failed

pw_varint_DecodeOneByte32()

static bool pw_varint_DecodeOneByte32 ( uint8_t  byte, size_t  count, uint32_t *  value  )

inlinestatic

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()

static bool pw_varint_DecodeOneByte64 ( uint8_t  byte, size_t  count, uint64_t *  value  )

inlinestatic

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

Returns

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

pw_varint_Encode32()

size_t pw_varint_Encode32	(	uint32_t	integer,
		void *	output,
		size_t	output_size_bytes
	)

Encodes a 32-bit integer as LEB128.

Returns

the number of bytes written

pw_varint_Encode64()

size_t pw_varint_Encode64	(	uint64_t	integer,
		void *	output,
		size_t	output_size_bytes
	)

Encodes a 64-bit integer as LEB128.

Returns

the number of bytes written

pw_varint_EncodeOneByte32()

static uint8_t pw_varint_EncodeOneByte32 ( uint32_t *  integer )

inlinestatic

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()

static uint8_t pw_varint_EncodeOneByte64 ( uint64_t *  integer )

inlinestatic

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.