redst4r / fastfibonacci-rs

Fast fibonacci coding/compression of integers

FastFibonacci

Rust library implementing the FastFibonacci integer compression/decompression algorithm. Besides, the crate also supplies regular fibonacci compression/decompression.

Introduction

Fibonacci encoding is a variable-length encoding of integers, with the special property that any encoding of an interger ends in 1 (binary) and no encoding contains 11. Hence one can use 11 as a separator in a stream of Fibonacci encoded integers.

Regular Fibonacci en/decoding works decoding bit by bit, which can be quite slow. FastFibonacci encoding and decoding looks at n bits at once, decoding this chunk in a single operation which can be faster.

Performance

Regular Fibonacci encoding is up to speed with other rust implementations, e.g. fibonnaci_codec crate (which I took some code from):

• Fibonacci encoding:
  • this crate: 75ms/ 1M integers
  • fibonnaci_codec: 88ms / 1M integers

Regular fibonacci decoding (iterator based) is up to speed with the fibonnaci_codec crate. The FastFibonacci decoding functions are ~2x faster, but have some constant overhead (i.e. only pays off when decoding many integers):

• Fibonacci decoding:
  • regular decoding: 92ms/ 1M integers
  • fibonnaci_codec: 108ms / 1M integers
  • fast decoding (u8 segments): 40ms / 1M integers
  • fast decoding (u16 segments): 30ms / 1M integers
  • fast decoding (using an iterator): 54ms / 1M integers

Examples

Regular encoding and decoding:

use fastfibonacci::fibonacci::{encode, decode, FibonacciDecoder};
let encoded = encode(&vec![34, 12]) ;

// Decoding
let decoded = decode(&encoded, false); // 2nd argument: shift all values by -1 (in case we wanted to encode 0 in the fibonacci encoding)
assert_eq!(decoded, vec![34,12]);

// Alternatively, we can also create an iterator (yields one decoded int at a time)
let f = FibonacciDecoder::new(&encoded, false);
assert_eq!(f.collect::<Vec<_>>(), vec![34,12])

Fast decoding:

use fastfibonacci::fast::{fast_decode, LookupU8Vec, LookupU16Vec,get_u8_decoder };
use bitvec::prelude as bv;
let bits = bv::bits![u8, bv::Msb0; 
    1,0,1,1,0,1,0,1,
    1,0,1,0,0,1,0,1,
    0,1,1,1,0,0,1,0].to_bitvec();
// using a u8 lookup table
let table: LookupVec<u8> = LookupVec::new();
let r = fast_decode(&bits, &table);
assert_eq!(r, vec![4,7, 86]);

// using a u16 table
let table: LookupVec<u16> = LookupVec::new();
let r = fast_decode(&bits, &table);
assert_eq!(r, vec![4,7, 86]);

// using an iterator
let dec8 = get_u8_decoder(&bits, false);
assert_eq!(dec8.collect::<Vec<_>>(), vec![4,7, 86]);

fastfibonacci-rs's Issues

Implement FastFibonacci Encoding

currently only regular (bit-by-bit) encoding is available.

`fibonacci::FibonacciDecoder` consumed on iteration

Makes it impossible to get a handle on the leftover bits along the lines of

let buffer:BitVec<u8, Msb0> = BitVec::from_iter(vec![true, false, true, true, false, true, true, false, true]);
let d = FibonacciDecoder::new(buffer.as_bitslice(), false);
for decoded in d {
  println!("{}", decoded);
}

let leftover = d.get_remaining_buffer();  // THIS FAILS DO TO ONWERSHIP
let expected_leftover :BitVec<u8, Msb0> = BitVec::from_iter(vec![false, true]);
assert_eq!(leftover, expected_leftover);

probably fixed by implementing an explicit iter-struct.