Crate svbyte

This library provides encoding/decoding primitives for Stream VByte encoding.

Stream VByte encoding is a SIMD accelerated algorithm of varint decompression. It is used in a search and database systems as a way of efficiently store and stream large number of variable length integers from a disk or main memory.

The idea behind varint is to skip leading zero bytes of the number, so large amount of relatively small numbers can be stored eficiently. Varint encoding is frequently used with delta-encoding if numbers are stored in the ascending order. This way all the numbers are smaller by magnitude, hence better compression.

Stream VByte is a storage format and an algorithm which allows to vectorize compressing and decompressing of numbers on a modern CPUs.

Main types of this crate are DecodeCursor and EncodeCursor.

Encoding

let output = BufWriter::new(File::create("./encoded.bin")?);
let mut encoder = EncodeCursor::new(output);
encoder.encode(&[1, 2, 3, 4]);

encoder.finish()?.flush()?;

Decoding

let segments = BufReadSegments::new(BufReader::new(File::open("./encoded.bin")?));
let mut decoder = DecodeCursor::new(segments)?;

let mut buffer = [0u32; 128];
let mut sum = 0u64;
loop {
    let decoded = decoder.decode(&mut buffer)?;
    if decoded == 0 {
        break;
    }
    sum += buffer[..decoded].iter().sum::<u32>() as u64;
}

Links

• Stream VByte: Faster Byte-Oriented Integer Compression by Daniel Lemire, Nathan Kurz, and Christoph Rupp
• Stream VByte: breaking new speed records for integer compression by Daniel Lemire

Structs

• BufReadSegments
  Reads a segment from an underlying BufRead
• DecodeCursor
  Decodes integers
• EncodeCursor
  Stream VByte Encoder
• MemorySegments
  Segments implementation with all segment data in memory

Traits

• Decoder
  Represents an object that can decode a stream of data into a buffer of fixed size. A type parameter T specifies /// the type of the elements in the buffer.
• Segments
  Provides facility for reading segments