Rateless invertable bloom lookup tables

This is an rust implementation of https://arxiv.org/abs/2402.02668
It aims to be efficient.

https://crates.io/crates/do-riblt The usage is explained in an example.

The entry to using this crate is the Encoder struct although you have to implement Symbol for your data first.

let set: HashSet<i32> = HashSet::from([1, 2, 3, 4]);
let encoder = Encoder::new(set.into_iter());

This implementation assumes that every T gets a unique representation in bytes. This should be logical as we need to parse them later. Note that this trait does not account for serializing and deserializing errors. You need to account for that yourself...

impl Symbol<4> for i32 {
  fn to_bytes(&self) -> [u8; 4] {
    self.to_be_bytes()
  }
  
  fn from_bytes(bytes: &[u8; 4]) -> Self {
    self.from_be_bytes(*bytes)
  }
}

Now you can create an infinite amount of symbols to send to a remote:

let symbol = encoder.next_symbol();

On the receiving side you create a decoder and feed it the symbols from the encoder:

let set = HashSet::from([1, 2, 3, 5]);
let mut decoder = Decoder::new(set.into_iter());

Feeding new symbols:

let (done, peeled) = decoder.next_symbol(symbol);

done tells if we need to peel more items by receiving more symbols. peeled is a Vec<Peeled<T>> which contains all new peeled symbols. An item will never be peeled more then once.

Here a full example implementation:

use riblt::{Decoder, Encoder, Symbol};

#[derive(Debug, Clone, Copy)]
struct SimpleData(u8, u8);

impl Symbol<2> for SimpleData {
    fn to_bytes(&self) -> [u8; 2] {
        [self.0, self.1]
    }

    fn from_bytes(bytes: &[u8; 2]) -> Self {
        Self(bytes[0], bytes[1])
    }
}

macro_rules! s {
    ($($a:expr, $b:expr),*) => {
        [$(SimpleData($a, $b)),*]
    };
}

fn main() {
    let local = s!(1, 2, 3, 4, 5, 6);
    let remote = s!(1, 2, 6, 7, 3, 4);

    //  Result should be:
    //    MissingRemote(SimpleData(5, 6))
    //    MissingLocal(SimpleData(6, 7))

    let mut remote_encoder = Encoder::new(remote.into_iter());
    let mut local_decoder = Decoder::new(local.into_iter());

    let mut peeled = Vec::new();

    let mut sent_symbols = 0u64;

    loop {
        //  This will always return Some, because the encoder is rateless (infinite)
        let symbol = remote_encoder.next().unwrap();

        //  Here we would send the symbol from remote to local
        sent_symbols += 1;

        //  Decoding the symbol, we get the new peeled values
        let (done, peeled_) = local_decoder.next_symbol(symbol);
        peeled.extend(peeled_);
        //  Check if we are done
        if done {
            break;
        }
    }

    //  Print result and number of sent symbols (aka efficiency, the lower the better)
    dbg!(peeled, sent_symbols);
}``