Number encoding

I have spent far too much time implementing and thinking about variable length quantities, the well known and much studied problem of a universal code for integers

And became deeply confused about suitable representation of such quantities in patricia trees because I lost track of the levels of encapsulation.

A patricia vertex represents a prefix with a bitcount. A patricia tree represents a prefix free index. A patricia vertex encapsulates a bitcount of the prefix, and is encapsulated by a bytecount of the vertex.

There is mud all over my web pages resulting from this confusion.

If we ever have a patricia tree of integers, variable length number encoding means that it is still just a bit string and a bit count. It will be the common bits of the variable length encoded integers of its children.

Because the variable length representation of the integers has normal byte order we don’t have to worry that some of them are different length and we don’t have worry about where the binary point is relative to start of the prefix, on which points I was endlessly confused.

1 history of mucking around.

I originally implemented variable length quantities following the standard.

And then I realized that an sql index represented as a Merkle-patricia tree inherently sorts in byte string order. Which is fine if we represent integers as fixed length integers in big endian format, but does not correctly sort variable length quantities if we follow the standard:

2 The problem to be solved

As computers and networks grow, any fixed length fields in protocols tend to become obsolete. Therefore, for future upwards compatibility, we want to have variable precision numbers.

Secondly, to represent integers within a Merkle-patricia tree representing a database index, we want all values to be left field aligned, rather than right field aligned, which requires some form of variable length encoding that preserves the order relationship between integers, so that the bytestring order is the same as the integer order.

2.1 Merkle-patricia dag

2.1.1 patricia tree

A patricia tree inherently represents a collection of prefix free bitstrings, which means the represented bitstrings must be self terminating, which for fixed length bitstrings is just reaching a certain number of bits, and for cee strings is eight zero bits, byte aligned.

But the vertices of a patricia tree represent a collection of prefixes. Each vertex represents some left aligned bits and a count of those bits. The count of the bits is extrinsic to the bits, they are inherently not self terminating, and the vertices are themselves not self terminating, they have an extrinsic byte count or bit count which is not itself part of the vertex, but part of the data structure within which the vertex is stored or represented.

We could represent the vertices by a self terminating bytestring or bitstring, but only if we wanted to put the vertices of a patricia tree inside another patricia tree. Which seems like a stupid thing to do under most circumstances. And what is being represented is itself inherently not self terminating.

The leaves of the patricia tree represent a data structure whose index is in the patricia tree, the index being a fixed length set of fields, each field itself a self terminating string of bits. Thus the leaf is not a patricia vertex, but an object of a different kind. (Unless of course the index fully represents all the information of the object)

The links inside a vertex also represent a short string of bits, the bits that the vertex pointed to, in addition to the bits that vertex point already has.

2.1.2 Merkle dag

We intend to have a vast Merkle dag, and a vast collection of immutable append only data structures. Each new block in the append only data structure is represented by a hash, whose preimage is a Merkle vertex. A path through the Merkle dag is represented by a consecutive sequence of integers, which represent not a Merkle-patricia tree, but a sequence of immutable Merkle-patricia trees that represent the mutable Merkle-patricia tree that is the current state of the blockchain.

2.2 VLQ encoding preserving lexicographic order

We want to represent integers by byte strings whose lexicographic order reflects their order as integers, which is to say, when sorted as a left aligned field, they sort like integers represented as a right aligned field. (Because a Merkle-patricia tree has a hard time with right aligned fields, and we do not want to represent integers by a fixed length field, because the fixed length will always either be too big or too small, as has given TCP no end of grief. Thirty two bit fixed length turned out to be too small.)

So, we allot half of the lexicographic space to one byte VLQ quantities.

Then half the remaining lexicographic space is split into two equal allocations of two and three byte VLQ quantities. Equal amounts of lexicographic space, but extremely unequal amounts of number space, in that the second space represents 2^8 times as many numbers.

Then half the remaining lexicographic space is split into four equal allocations of four, five, six, and seven byte VLQ quantities, equal allocations of lexicographic space to very unequal amounts of numbers.

After step n of this process we have 2^{-n} of the original lexicographic space remaining, and have defined prefixes to identify 2^{n}-1 sizes of VLQ quantities.

To map an integer to its VLQ representation, we subtract a term for the integers that have been allocated to smaller lengths, we convert it to big endian form, truncate or sign extend to the correct total size, and fix the leading bits, which for signed integers are always leading sign bits, to give it the correct prefix.

2.2.1 representation of unsigned integers as variable length quantities

We want representation of variable length unsigned values representable as

(The current implementation stops at nine bytes: src/serialization.cpp decodes any first byte 0xE2 or greater as a nine byte unsigned value, and throws BadDataException when the value does not fit in sixty four bits.)

Thus an unsigned integer value in the range 0\le n \lt 2^7, in the range 0\le n \lt \text{0x80}, is the one byte unsigned eight bit integer n itself.

An unsigned integer in the range 2^7\le n \lt 2^{13}+2^7, an integer in the range \text{0x80}\le n \lt \text{0x2080}, has a representation that starts with the bits 0b100x xxxx. Thus an integer in this range is represented by the two byte integer n+2^{15}-2^7 the integer n+\text{0x7F80}, in big endian format, or equivalently, by the two byte big endian integer n-2^7, with its leading byte, its high order byte, ored with \text{0x80}.

We are using C++20. The C++20 standard library provides std::endian for detecting the native endianness of the execution environment and std::byteswap for efficiently reversing the byte order of integers.

An unsigned integer in the range 2^{13}+2^7\le n \lt 2^{21}+2^{13}+2^7, in the range \text{0x2080}\le n \lt \text{0x202080}, starts with the bits 101, indicating the representation needs three bytes. Thus it is represented by the three byte big endian integer n+0\text{xA00000}-\text{0x2080} in big endian format, or equivalently by the three byte big endian integer n-2^{13}-2^7, with its leading byte, its high order byte, ored with \text{0xA0}

An unsigned integer in the range 2^{21}+2^{13}+2^7\le n \lt 2^{27}+2^{21}+2^{13}+2^7, in the range \text{0x202080}\le n \lt \text{0x8202080}, starts with the bits 11000, indicating four bytes. Thus is represented by the integer itself +\text{0xC000 0000}-\text{0x202080} in big endian format, or equivalently by the four byte big endian integer n-2^{21}-2^{13}-2^7, with its leading byte, its high order byte, ored with \text{0xC0}

Similarly, values with an eight byte representation start with 0b1110000x, representing values in the range 2^{51}+2^{43}+2^{35}+2^{27}+2^{21}+2^{13}+2^7\le n \lt 2^{57}+2^{51}+2^{43}+2^{35}+2^{27}+2^{21}+2^{13}+2^7, and the representation is constructed by creating the big endian representation of n-2^{51}-2^{43}-2^{35}-2^{27}-2^{21}-2^{13}-2^7 and oring the high order byte with 0b11100000$

And so on and so forth except that for a very long time to come the deserialize implementation is going to throw an exception if it attempts to read a value larger than 2^{64}-1, because it will have nowhere to put it, and the serialize implementation is not going to have to deal with values larger than sixty four bits.

Eventually we will allow 128 bit values, requiring a nine bit header, but not for a very long time.

2.2.2 representation of signed integers as variable length quantities.

Because overflow is undefined on signed integers, we need to use bitwise boolean operations in place of additions to set the high order byte

Bitwise and, &, works for negative values, because the high order bits are always 1.

Bitwise or, |, works for positive values, because the high order bits are always 0.

For eight byte and nine byte representations, we are using the entire first byte for the header, so simply store it, rather than and it.

The table for signed integers begins and ends with etcetera, representing the fact that this system can represent unboundedly large values, but for the moment we only care about continuing it far enough to cover sixty four bit integers.

We construct the representation of a positive signed integer in much the same way as we did for unsigned integers.

Thus, for example, if 2^{20}+2^{12}+2^6 \le n \lt 2^{26}+2^{20}+2^{12}+2^6, its four byte representation is constructed by creating the big endian representation of n-2^{20}-2^{12}-2^6 and oring 0b1110 0000 into the high order byte.

But we construct the representation of a negative signed integer by anding, rather than oring.

Let us take as an example, n=-2^{34}-2^{26}-2^{20}-2^{12}-2^6

This fits, just barely in the five byte range, so we want the five byte big endian representation of
n+2^{26}+2^{20}+2^{12}+2^6
=-2^{34}
= 0b11111100 00000000 00000000 00000000 00000000

We then evaluate

0b11111100 & 0b00011011

To obtain the lead byte: 0b00011000

So our five byte representation of this value is
0b00011000 00000000 00000000 00000000 00000000
= 0x1800000000

3 bitstrings

It might be convenient to represent the data as a pile of edges, rather than a pile of vertices, thus solving the problem that the tree must always start with an edge, not a vertex. This duplicates the start position of every edge, but this duplication does not matter because the patricia representation of an index, and the standard and usual database representation of an index, compresses out the leading duplication.

So we are representing an sql index by a table whose primary key is the bitstring of the start position, and whose values are the start position and the end position. The patricia edges of this table live in the same table, just their values are distinguished from actual leaf values.

Variable length bitstrings are represented as variable length bytestrings by appending a one bit followed by zero to seven zero bits.

In the table we may compress the end values by discarding all leading bytes except the overlap byte.

Thus the actual table, containing only the leaf values, is a virtual table based on a select statement that excludes the internal edges of the patricia tree from the table of all edges, and concatenates the compressed value with the index to form the absolute value.

It is very common for the end value to be very short. We could optimize for that, but this would be premature optimization.

4 Dewey decimal sequences.

The only operation we ever want to do with Dewey decimal sequences is <=>, and they are always positive numbers less than 10^{34}, so we represent them as a sequence of variable length positive numbers terminated by a byte that corresponds to the header of an impermissibly large number, and compare them as bytestrings.

Albeit we could add, subtract, multiply, and divide Dewey decimal sequences as polynomials, which would require signed integer sequences, but I cannot see any use case for this, while unsigned integer sequences have the advantage that the ones used to sort and identify things are always positive in practice, and one may consider a utf string to be a very long Dewey decimal sequence.

4.1 Use case

QR codes and prefix free number encoding are useful in cases where we want data to be self describing – this bunch of bits is to be interpreted in a certain way, used in a certain action, means one thing, and not another thing. At present there is no standard for self description. QR codes are given meanings by the application, and could carry completely arbitrary data whose meaning and purpose comes from outside, from the context.

Ideally, it should make a connection, and that connection should then launch an interactive environment – the url case, where the url downloads a javascript app to address a particular database entry on a particular host.

A fixed length field is always in danger of running out, so one needs a committee to allocate numbers. With an arbitrary length field there is always plenty of headroom, we can just let people use what numbers seem good to them, and if there is a collision, well, one or both of the colliders can move to another number.

For example, the hash of a public key structure has to contain an algorithm identifier as to the hashing algorithm, to accommodate the possibility that in future the existing algorithm becomes too weak, and we must introduce new algorithms while retaining compatibility with the old. But there could potentially be quite a lot of algorithms, though in practice initially there will only be one, and it will be a long time before there are two.

When I say “arbitrarily large” I do not mean arbitrarily large, since this creates the possibility that someone could break something by sending a number bigger than the software can handle. There needs to be an absolute limit, such as sixty four bits, on representable numbers. But the limit should be larger than is ever likely to have a legitimate use.

5 Other Solutions

5.1 Zero byte encoding

Cap’n Proto zero compresses out zero bytes, and uses an encoding such that uninformative and predictable fields are zero.

5.2 62 bit compressed numbers

QUIC variable length integers are one, two, four, or eight bytes long, carrying six, fourteen, thirty, or sixty two bits of value.