/vle

Simple variable-length encoder/decoder (C99)(C++03)

Primary LanguageC++zlib LicenseZlib

vle

  • VLE is a simple variable-length encoder/decoder (C99)(C++03)
  • VLE is simple. Format is 7-bit packing, MSB stream terminator.
  • VLE is streamable. Designed to encode and decode integers with low overhead.
  • VLE is embeddable. Header-only. No external deps. C and C++ APIs provided.
  • VLE is extendable. Signed/unsigned integers of any size (8/16/32/64/...) are supported.
  • VLE is zlib/libpng licensed.

Quick tutorial

  • You want to serialize an struct { uint16_t len; uint64_t buffer[6]; } to disk, network, etc...
  • You could just flush a 50-bytes stream, or you could flush a VLE stream instead.
  • This VLE stream will range from 7-bytes (best-case, 43-bytes saved) up to 63-bytes (worst-case, 13-bytes overhead).

Features

  • For any 8-bit sequence, the VLE stream will range from len up to 2*len bytes.
  • For any 16-bit sequence, the VLE stream will range from len up to 3*len bytes.
  • For any 32-bit sequence, the VLE stream will range from len up to 5*len bytes.
  • For any 64-bit sequence, the VLE stream will range from len up to 10*len bytes.
  • Magnitude of value determinates size of encoded stream. Magnitude of type does not matter.
    • All byte(0), short(0), int(0), int64(0)... serialize to a 1-byte stream.
    • All byte(127), short(127), int(127), int64(127)... serialize to a 1-byte stream.
    • All byte(128), short(128), int(128), int64(128)... serialize to a 2-bytes stream.
    • All byte(255), short(255), int(255), int64(255)... serialize to a 2-bytes stream.
    • All short(16383), int(16383), int64(16383)... serialize to a 2-bytes stream.
    • All short(16384), int(16384), int64(16384)... serialize to a 3-bytes stream.
    • And so on... (see range tables below).
  • Rule: The closer to zero integer you encode, the smaller the stream you decode.
    • Note: Negative integers are rearranged to meet this criteria (see appendix).

VLE stream format

  • All non-significative (zero) bits on the left are discarded.
  • Bytes are repacked into 7-bit components and glued together until a LSB/MSB bit is found.
  • Additionally, signed integers are pre-encoded and post-decoded to a more efficient signed number representation.

API, C

  • Basic API. Allows streaming and fine control.
  • Encoders do not append null character at end of string.
  • Decoders do not need null character at end of string.
  • All functions assume buffers are preallocated to worst-case scenarios.
  • All functions return integer of streamed bytes.
 VLE_API uint64_t vle_encode_u(  uint8_t *buffer, uint64_t value );
 VLE_API uint64_t vle_encode_i(  uint8_t *buffer,  int64_t value );
 VLE_API uint64_t vle_decode_u( uint64_t *value, const uint8_t *buffer );
 VLE_API uint64_t vle_decode_i(  int64_t *value, const uint8_t *buffer );

API, C++

vlei:: {
  string   encode( int64_t );
  int64_t  decode( string );
}
vleu:: {
  string   encode( uint64_t );
  uint64_t decode( string );
}

VLE unsigned, 64-bit ranges

 1 byte  [0..127]
 2 bytes [128..16383]
 3 bytes [16384..2097151]
 4 bytes [2097152..268435455]
 5 bytes [268435456..34359738367]
 6 bytes [34359738368..4398046511103]
 7 bytes [4398046511104..562949953421311]
 8 bytes [562949953421312..72057594037927935]
 9 bytes [72057594037927936..9223372036854775807]
10 bytes [9223372036854775808..18446744073709551615]

VLE signed, 64-bit ranges

10 bytes [-9223372036854775808..-4611686018427387905]
 9 bytes [-4611686018427387904..-36028797018963969]
 8 bytes [-36028797018963968..-281474976710657]
 7 bytes [-281474976710656..-2199023255553]
 6 bytes [-2199023255552..-17179869185]
 5 bytes [-17179869184..-134217729]
 4 bytes [-134217728..-1048577]
 3 bytes [-1048576..-8193]
 2 bytes [-8192..-65]
 1 byte  [-64..63]
 2 bytes [64..8191]
 3 bytes [8192..1048575]
 4 bytes [1048576..134217727]
 5 bytes [134217728..17179869183]
 6 bytes [17179869184..2199023255551]
 7 bytes [2199023255552..281474976710655]
 8 bytes [281474976710656..36028797018963967]
 9 bytes [36028797018963968..4611686018427387903]
10 bytes [4611686018427387904..9223372036854775807]

used in

  • collage, a diff/patch library.
  • bundle, a de/compression library.

appendix: sign theory and conversion functions

## Signed-Magnitude Complement-2 VLEi (*)
+7 0 111 0 111 111 0
+6 0 110 0 110 110 0
+5 0 101 0 101 101 0
+4 0 100 0 100 100 0
+3 0 011 0 011 011 0
+2 0 010 0 010 010 0
+1 0 001 0 001 001 0
+0 0 000 0 000 000 0
-0 1 000 ----- -----
-1 1 001 1 111 000 1
-2 1 010 1 110 001 1
-3 1 011 1 101 010 1
-4 1 100 1 100 011 1
-5 1 101 1 011 100 1
-6 1 110 1 010 101 1
-7 1 111 1 001 110 1
-8 ---- 1 000 111 1

(*): compared to C2 (default signed integer), bits are shared or inverted

c2tovlei(n) {
    return n & MSB ? ~(n<<1) : (n<<1);
}
vleitoc2(n) {
    return n & LSB ? ~(n>>1) : (n>>1);
}