<title>Variable-Length Integers</title>
A variable length integer is an encoding of 64-bit unsigned integers
into between 1 and 9 bytes. The encoding has the following properties:
1. Smaller (and more common) values use fewer bytes and take up less space
than larger (and less common) values.
2. The length of any varint can be determined by looking at just the
first byte of the encoding.
3. Lexicographical and numeric ordering for varints are the same. Hence
if a group of varints are order lexicographically (that is to say, if
they are order by memcmp() with shorter varints coming first) then
those varints will also be in numeric order. This property means
that varints can be used as keys in the key/value backend storage
and the records will occur in numerical order of the keys.
The encoding is described by algorithms to decode (convert from
varint to 8-byte unsigned integer) and to encode (convert from
8-byte unsigned integer to varint). Treat each byte of the encoding
as an unsigned integer between 0 and 255. Let the bytes of the
encoding be called A0, A1, A2, ..., A8.
<h2>Decode</h2>
* If A0 is between 0 and 240 inclusive, then the result is the value of A0.
* If A0 is between 241 and 248 inclusive, then the result is
240+256*(A0-241)+A1.
* If A0 is 249 then the result is 2287+256*A1+A2.
* If A0 is 250 then the result is A1..A3 as a 3-byte big-ending integer.
* If A0 is 251 then the result is A1..A4 as a 4-byte big-ending integer.
* If A0 is 252 then the result is A1..A5 as a 5-byte big-ending integer.
* If A0 is 253 then the result is A1..A6 as a 6-byte big-ending integer.
* If A0 is 254 then the result is A1..A7 as a 7-byte big-ending integer.
* If A0 is 255 then the result is A1..A8 as a 8-byte big-ending integer.
<h2>Encode</h2>
Let the input value be V.
* If V<=240 then output a single by A0 equal to V.
* If V<=2287 then output A0 as (V-240)/256 + 241 and A1 as (V-240)%256.
* If V<=67823 then output A0 as 249, A1 as (V-2288)/256, and A2
as (V-2288)%256.
* If V<=16777215 then output A0 as 250 and A1 through A3 as a big-endian
3-byte integer.
* If V<=4294967295 then output A0 as 251 and A1..A4 as a big-ending
4-byte integer.
* If V<=1099511627775 then output A0 as 252 and A1..A5 as a big-ending
5-byte integer.
* If V<=281474976710655 then output A0 as 253 and A1..A6 as a big-ending
6-byte integer.
* If V<=72057594037927935 then output A0 as 254 and A1..A7 as a
big-ending 7-byte integer.
* Otherwise then output A0 as 255 and A1..A8 as a big-ending 8-byte integer.
<h2>Other information</h2>
<blockquote><table border=1 cellpadding=5>
<tr><th>Bytes<th>Max Value<th>Digits
<tr><td> 1 <td> 240 <td> 2.3
<tr><td> 2 <td> 2287 <td> 3.3
<tr><td> 3 <td> 67823 <td> 4.8
<tr><td> 4 <td> 2<sup>24</sup>-1 <td> 7.2
<tr><td> 5 <td> 2<sup>32</sup>-1 <td> 9.6
<tr><td> 6 <td> 2<sup>40</sup>-1 <td> 12.0
<tr><td> 7 <td> 2<sup>48</sup>-1 <td> 14.4
<tr><td> 8 <td> 2<sup>56</sup>-1 <td> 16.8
<tr><td> 9 <td> 2<sup>64</sup>-1 <td> 19.2
</table></blockquote>