HomePhabricator

Compact serialization for variable-length integers
4d6144f97fafUnpublished

Unpublished Commit ยท Learn More

Repository Importing: This repository is still importing.

Description

Compact serialization for variable-length integers

Variable-length integers: bytes are a MSB base-128 encoding of the number.
The high bit in each byte signifies whether another digit follows. To make
the encoding is one-to-one, one is subtracted from all but the last digit.
Thus, the byte sequence a[] with length len, where all but the last byte
has bit 128 set, encodes the number:

(a[len-1] & 0x7F) + sum(i=1..len-1, 128^i*((a[len-i-1] & 0x7F)+1))

Properties:

  • Very small (0-127: 1 byte, 128-16511: 2 bytes, 16512-2113663: 3 bytes)
  • Every integer has exactly one encoding
  • Encoding does not depend on size of original integer type

Details

Provenance
Pieter Wuille <pieter.wuille@gmail.com>Authored on Jun 15 2012, 12:19
deadalnixPushed on May 14 2017, 22:04
Parents
rABC43b7905e98d8: LevelDB glue
Branches
Unknown
Tags
Unknown

Event Timeline

Pieter Wuille <pieter.wuille@gmail.com> committed rABC4d6144f97faf: Compact serialization for variable-length integers (authored by Pieter Wuille <pieter.wuille@gmail.com>).Oct 20 2012, 21:08