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
	Provides basic helpers for reading and writing UTF-8 encoded strings.

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

Decode()

size_t pw::varint::Decode ( const span< const std::byte > &  input, int64_t *  output  )

inline

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

Encode()

template<typename T >

size_t pw::varint::Encode	(	T	integer,
		const span< std::byte > &	output
	)

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.

EncodedSize()

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 )

constexpr

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.

EncodeLittleEndianBase128()

size_t pw::varint::EncodeLittleEndianBase128 ( uint64_t  integer, const span< std::byte > &  output  )

inline

Encodes a uint64_t with Little-Endian Base 128 (LEB128) encoding.

Returns

the number of bytes written; 0 if the buffer is too small

MaxValueInBytes()

constexpr uint64_t pw::varint::MaxValueInBytes ( size_t  bytes )

constexpr

Returns the maximum (max) integer value that can be encoded as a varint into the specified number of bytes.

The following table lists the max value for each byte size:

Bytes	Max value
1	127
2	16,383
3	2,097,151
4	268,435,455
5	34,359,738,367
6	4,398,046,511,103
7	562,949,953,421,311
8	72,057,594,037,927,935
9	9,223,372,036,854,775,807
10	(uint64 max value)

Parameters

bytes

The size of the varint, in bytes. 5 bytes are needed for the max uint32 value. 10 bytes are needed for the max uint64 value.

Returns

The max integer value for a varint of size bytes.

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.

ZigZagDecode()

template<typename T >

constexpr std::make_signed_t< T > pw::varint::ZigZagDecode ( T  n )

constexpr

ZigZag decodes a signed integer.

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

ZigZagEncode()

template<typename T >

constexpr std::make_unsigned_t< T > pw::varint::ZigZagEncode ( T  n )

constexpr

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