Module zerotrie::varint

Varint spec for ZeroTrie:

• Lead byte: top M (2 or 3) bits are metadata; next is varint extender; rest is value
• Trail bytes: top bit is varint extender; rest are low bits of value
• Guaranteed uniqueness of varint by adding “latent value” for each extender byte
• No maximum, but high bits will be dropped if they don’t fit in the platform’s usize

This is best shown by examples.

xxx0'1010 = 10
xxx0'1111 = 15 (largest single-byte value with M=3)
xxx1'0000 0000'0000 must be 16 (smallest two-byte value with M=3)
xxx1'0000 0000'0001 = 17
xxx1'1111 0111'1111 = 2063 (largest two-byte value with M=3)
xxx1'0000 1000'0000 0000'0000 must be 2064 (smallest three-byte value with M=3)
xxx1'0000 1000'0000 0000'0001 = 2065

The latent values by number of bytes for M=3 are:

• 1 byte: 0
• 2 bytes: 16 = 0x10 = 0b10000
• 3 bytes: 2064 = 0x810 = 0b100000010000
• 4 bytes: 264208 = 0x40810 = 0b1000000100000010000
• 5 bytes: 33818640 = 0x2040810 = 0b10000001000000100000010000
• …

For M=2, the latent values are:

• 1 byte: 0
• 2 bytes: 32 = 0x20 = 0b100000
• 3 bytes: 4128 = 0x1020 = 0b1000000100000
• 4 bytes: 524320 = 0x81020 = 0b10000001000000100000
• 5 bytes: 67637280 = 0x4081020 = 0b100000010000001000000100000
• …

Constants

• MAX_VARINT_LENGTH 🔒

Functions

• read_varint_meta2
  Reads a varint with 2 bits of metadata in the lead byte.
• read_varint_meta3
  Reads a varint with 3 bits of metadata in the lead byte.
• try_read_varint_meta3_from_tstore 🔒
  Reads and removes a varint with 3 bits of metadata from a TrieBuilderStore.
• write_varint_meta2 🔒
  Returns a new ConstArrayBuilder containing a varint with 2 bits of metadata.
• write_varint_meta3 🔒
  Returns a new ConstArrayBuilder containing a varint with 3 bits of metadata.