4 releases (1 stable)

1.0.0 Mar 29, 2024
0.3.0 Nov 21, 2023
0.2.0 Nov 20, 2023
0.1.0 Nov 20, 2023

#108 in Compression

Download history 4/week @ 2024-02-13 11/week @ 2024-02-20 14/week @ 2024-02-27 2/week @ 2024-03-05 8/week @ 2024-03-12 126/week @ 2024-03-26 43/week @ 2024-04-02

179 downloads per month
Used in 3 crates (2 directly)


1.5K SLoC


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


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.


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


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; 
// 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]);


~41K SLoC