Variable length serialisation of integers

A variable length serialisation is available for (unsigned) integers, using fewer octets for smaller numbers. This has two important benefits:

Smaller numbers tend to occur very frequently in practise, so this represents a more compact format than fixed size representations such as always using 4 octets for a uint32; and
It provides a measure of platform independence, since the serialisation is determined by the value of the integer, not the type (e.g. uint8 / uint16 / uint32 / uint64). This is handy for serialising values of platform dependent types like the size of an std::vector which has type size_t which might be 32 bit or 64 bit.

Although uncompressed integers are serialised in little endian order, the variable length serialisation is big endian (i.e. the most significant octet appears first in the sequence).

The following table shows the serialisation format for various ranges of the integer. The format is shown as a list of octets in square brackets where each octet is expressed in binary with 8 binary digits. The binary digits which are x's mark bits which come from the binary representation of the value, with the most significant bit on the left. For example in the format [110xxxxx, xxxxxxxx, xxxxxxxx] there are three octets and there are 21 x's corresponding to a 21 bit representation of the value.

Range of integer	Num serialised octets	Serialisation format
0 to 2⁷-1	1	[0xxxxxxx]
2⁷ to 2¹⁴-1	2	[10xxxxxx, xxxxxxxx]
2¹⁴ to 2²¹-1	3	[110xxxxx, xxxxxxxx, xxxxxxxx]
2²¹ to 2²⁸-1	4	[1110xxxx, xxxxxxxx, xxxxxxxx, xxxxxxxx]
2²⁸ to 2³⁵-1	5	[11110xxx, xxxxxxxx, xxxxxxxx, xxxxxxxx, xxxxxxxx]

Examples

The following table provides some examples, using hexadecimal notation

Value	Serialisation
0x00	[ 0x00 ]
0x05	[ 0x05 ]
0x7F	[ 0x7F ]
0x80	[ 0x80, 0x80 ]
0x85	[ 0x80, 0x85 ]
0x3FFF	[ 0xBF, 0xFF ]
0x4000	[ 0xC0, 0x40, 0x00 ]
0x4005	[ 0xC0, 0x40, 0x05 ]
0x1FFFFF	[ 0xDF, 0xFF, 0xFF ]
0x200000	[ 0xE0, 0x20, 0x00, 0x00 ]
0x212345	[ 0xE0, 0x21, 0x23, 0x45 ]
0xFFFFFFF	[ 0xEF, 0xFF, 0xFF, 0xFF ]
0x10000000	[ 0xF0, 0x10, 0x00, 0x00, 0x00 ]
0x12345678	[ 0xF0, 0x12, 0x34, 0x56, 0x78 ]

Serialisation and deserialisation rate

The serialisation and deserialisation rate for a uint32 was measured for values in the range from 0 to 10000000, on a laptop with an i7-4700MQ 2.4GHz processor and 16GB RAM.

A rate of 750 MByte/sec was obtained for both serialisation and deserialisation.