pw_varint

Overview

Functions for encoding and decoding variable length integers.

Main docs: Home

Variable-length integer encoding and decoding library

Enumerations
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
StatusWithSize	pw::varint::Read (stream::Reader &reader, int64_t *output, size_t max_size=std::numeric_limits< size_t >::max())
	Decodes a variable-length integer (varint) from the current position of a pw::stream. Reads a maximum of 10 bytes or max_size, whichever is smaller.
StatusWithSize	pw::varint::Read (stream::Reader &reader, uint64_t *output, size_t max_size=std::numeric_limits< size_t >::max())
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)
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)

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.

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)

Function Documentation

DecodeOneByte()

template<typename T >

constexpr bool pw::varint::DecodeOneByte ( std::byte  encoded, size_t  count, T *  out_value  )

constexpr

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

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

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

constexpr size_t pw::varint::EncodeLittleEndianBase128 ( uint64_t  value, ByteSpan  out_encoded  )

constexpr

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

Returns

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

EncodeOneByte()

template<typename T >

constexpr std::byte pw::varint::EncodeOneByte ( T *  value )

constexpr

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.

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.

Read()

StatusWithSize pw::varint::Read	(	stream::Reader &	reader,
		int64_t *	output,
		size_t	max_size = std::numeric_limits< size_t >::max()
	)

Decodes a variable-length integer (varint) from the current position of a pw::stream. Reads a maximum of 10 bytes or max_size, whichever is smaller.

This method always returns the number of bytes read, even on error.

Parameters

reader	The pw::stream to read from.
output	The integer to read into. If reading into a signed integer, the value is ZigZag-decoded.
max_size	The maximum number of bytes to read. The upper limit is 10 bytes.

Returns

• OK: The decoded value is placed in output.
• OUT_OF_RANGE: No input is available, e.g. the stream is closed.
• DATA_LOSS: The decoded value is too large for output or is incomplete, e.g. the input was exhausted after a partial varint was read.

ZigZagDecode()

template<typename T >

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

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

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