Xorfilter 0.2.2

//! XorFilter:  const generic powered set membership approximation.
#![no_std]
#![feature(const_fn_floating_point_arithmetic)]
#![feature(generic_const_exprs)]
//#![feature(const_generics_defaults)]
use crate::num::AsPrimitive;
use core::cmp::PartialEq;
use core::hash::SipHasher;
use core::hash::{Hash, Hasher};
use core::ops::{BitXor, BitXorAssign};
pub mod num;

#[derive(Debug)]
pub struct XorFilter<const N: usize, T: Default + Copy = u8>
where
    [u8; capacity::<N>()]: Sized,
    [u8; bl::<N>() as usize]: Sized,
    T: BitXor,
    T: BitXorAssign,
    T: BitXor<Output = T>,
    T: PartialEq,
    u64: AsPrimitive<T>,
{
    pub seed: u64,
    pub blocklength: u32,
    pub fingerprints: [T; capacity::<N>()],
}

impl<const N: usize, T: Default + Copy> XorFilter<N, T>
where
    [u8; capacity::<N>()]: Sized,
    [u8; bl::<N>() as usize]: Sized,
    T: BitXor,
    T: BitXorAssign,
    T: BitXor<Output = T>,
    T: PartialEq,
    u64: AsPrimitive<T>,
{
    fn populate(&mut self, keys: &[u64; N]) {
        let mut rngcounter: u64 = 1;
        self.seed = splitmix64(rngcounter);

        let mut q0: [Keyindex; bl::<N>() as usize] =
            [Keyindex { hash: 0, index: 0 }; bl::<N>() as usize];
        let mut q1: [Keyindex; bl::<N>() as usize] =
            [Keyindex { hash: 0, index: 0 }; bl::<N>() as usize];
        let mut q2: [Keyindex; bl::<N>() as usize] =
            [Keyindex { hash: 0, index: 0 }; bl::<N>() as usize];

        let mut stack: [Keyindex; N] = [Keyindex { hash: 0, index: 0 }; N];
        let mut sets0: [Xorset; bl::<N>() as usize] = [Xorset {
            xormask: 0,
            count: 0,
        }; bl::<N>() as usize];
        let mut sets1: [Xorset; bl::<N>() as usize] = [Xorset {
            xormask: 0,
            count: 0,
        }; bl::<N>() as usize];
        let mut sets2: [Xorset; bl::<N>() as usize] = [Xorset {
            xormask: 0,
            count: 0,
        }; bl::<N>() as usize];
        while true {
            for i in 0..N {
                let key = keys[i];
                let hs = self.geth0h1h2(key);
                sets0[hs.h0 as usize].xormask ^= hs.h;
                sets0[hs.h0 as usize].count = sets0[hs.h0 as usize].count + 1;
                sets1[hs.h1 as usize].xormask ^= hs.h;
                sets1[hs.h1 as usize].count = sets1[hs.h1 as usize].count + 1;
                sets2[hs.h2 as usize].xormask ^= hs.h;
                sets2[hs.h2 as usize].count = sets2[hs.h2 as usize].count + 1;
            }

            let mut q0size = 0;
            let mut q1size = 0;
            let mut q2size = 0;

            for i in 0u32..(bl::<N>() as u32) {
                if sets0[i as usize].count == 1 {
                    q0[q0size].index = i;
                    q0[q0size].hash = sets0[i as usize].xormask;
                    q0size = q0size + 1;
                }
            }

            for i in 0u32..(bl::<N>() as u32) {
                if sets1[i as usize].count == 1 {
                    q1[q1size].index = i;
                    q1[q1size].hash = sets1[i as usize].xormask;
                    q1size = q1size + 1;
                }
            }

            for i in 0u32..(bl::<N>() as u32) {
                if sets2[i as usize].count == 1 {
                    q2[q2size].index = i;
                    q2[q2size].hash = sets2[i as usize].xormask;
                    q2size = q2size + 1;
                }
            }

            let mut stacksize = 0;

            while q0size + q1size + q2size > 0 {
                while q0size > 0 {
                    q0size = q0size - 1;
                    let mut Keyindexvar = &q0[q0size];
                    let index = Keyindexvar.index;
                    if sets0[index as usize].count == 0 {
                        continue;
                    }

                    let hash = Keyindexvar.hash;
                    let h1 = self.geth1(hash);
                    let h2 = self.geth2(hash);
                    stack[stacksize] = *Keyindexvar;
                    stacksize = stacksize + 1;
                    sets1[h1 as usize].xormask ^= hash;

                    sets1[h1 as usize].count = sets1[h1 as usize].count.wrapping_sub(1);
                    if sets1[h1 as usize].count == 1 {
                        q1[q1size].index = h1;
                        q1[q1size].hash = sets1[h1 as usize].xormask;
                        q1size = q1size + 1;
                    }

                    sets2[h2 as usize].xormask ^= hash;
                    sets2[h2 as usize].count = sets2[h2 as usize].count.wrapping_sub(1);
                    if sets2[h2 as usize].count == 1 {
                        q2[q2size].index = h2;
                        q2[q2size].hash = sets2[h2 as usize].xormask;
                        q2size = q2size + 1;
                    }
                }

                while q1size > 0 {
                    q1size = q1size - 1;
                    let mut Keyindexvar = q1[q1size].clone();
                    let index = Keyindexvar.index;

                    if sets1[index as usize].count == 0 {
                        continue;
                    }

                    let hash = Keyindexvar.hash;
                    let h0 = self.geth0(hash);
                    let h2 = self.geth2(hash);
                    Keyindexvar.index += bl::<N>() as u32;

                    stack[stacksize] = Keyindexvar.clone();
                    stacksize = stacksize + 1;
                    sets0[h0 as usize].xormask ^= hash;
                    sets0[h0 as usize].count = sets0[h0 as usize].count.wrapping_sub(1);
                    if sets0[h0 as usize].count == 1 {
                        q0[q0size].index = h0;
                        q0[q0size].hash = sets0[h0 as usize].xormask;
                        q0size = q0size + 1;
                    }

                    sets2[h2 as usize].xormask ^= hash;
                    sets2[h2 as usize].count = sets2[h2 as usize].count - 1;

                    if sets2[h2 as usize].count == 1 {
                        q2[q2size].index = h2;
                        q2[q2size].hash = sets2[h2 as usize].xormask;
                        q2size = q2size + 1;
                    }
                }

                while q2size > 0 {
                    q2size = q2size - 1;
                    let mut Keyindexvar = q2[q2size].clone();
                    let index = Keyindexvar.index;
                    if sets2[index as usize].count == 0 {
                        continue;
                    }

                    let hash = Keyindexvar.hash;
                    let h0 = self.geth0(hash);
                    let h1 = self.geth1(hash);
                    Keyindexvar.index += (2 * bl::<N>() as u32);
                    stack[stacksize] = Keyindexvar.clone();
                    stacksize = stacksize + 1;

                    sets0[h0 as usize].xormask ^= hash; // need to bring this back
                    sets0[h0 as usize].count = sets0[h0 as usize].count.wrapping_sub(1);
                    if sets0[h0 as usize].count == 1 {
                        q0[q0size].index = h0;
                        q0[q0size].hash = sets0[h0 as usize].xormask;
                        q0size = q0size + 1;
                    }
                    sets1[h1 as usize].xormask ^= hash;
                    sets1[h1 as usize].count = sets1[h1 as usize].count.wrapping_sub(1);
                    if sets1[h1 as usize].count == 1 {
                        q1[q1size].index = h1;
                        q1[q1size].hash = sets1[h1 as usize].xormask;
                        q1size = q1size + 1
                    }
                }
            }

            if stacksize == N {
                break;
            }

            for i in 0..sets0.len() {
                sets0[i as usize] = Xorset {
                    xormask: 0,
                    count: 0,
                };
            }

            for i in 0..sets1.len() {
                sets1[i as usize] = Xorset {
                    xormask: 0,
                    count: 0,
                };
            }

            for i in 0..sets2.len() {
                sets2[i as usize] = Xorset {
                    xormask: 0,
                    count: 0,
                };
            }

            self.seed = splitmix64(rngcounter);
        }

        let mut stacksize = keys.len();
        while stacksize > 0 {
            stacksize = stacksize - 1;
            let ki = &stack[stacksize];
            let mut val = fingerprint(ki.hash).as_();

            if ki.index < self.blocklength {
                let r1 = rotl64(ki.hash, 21) as u32;
                let r2 = rotl64(ki.hash, 42) as u32;
                val ^= self.fingerprints[(reduce(r1, self.blocklength) + self.blocklength) as usize]
                    ^ self.fingerprints
                        [(reduce(r2, self.blocklength) + 2 * self.blocklength) as usize]
            } else if ki.index < 2 * self.blocklength {
                let r0 = ki.hash as u32;
                let r2 = rotl64(ki.hash, 42) as u32;
                val ^= self.fingerprints[reduce(r0, self.blocklength) as usize]
                    ^ self.fingerprints
                        [(reduce(r2, self.blocklength) + 2 * self.blocklength) as usize]
            } else {
                let r0 = ki.hash as u32;
                let r1 = rotl64(ki.hash, 21) as u32;
                val ^= self.fingerprints[reduce(r0, self.blocklength) as usize]
                    ^ self.fingerprints[(reduce(r1, self.blocklength) + self.blocklength) as usize]
            }
            self.fingerprints[ki.index as usize] = val;
        }
    }

    pub fn contains(&self, mut key: u64) -> bool {
        let mut hash = mixsplit(key, self.seed);
        let f = fingerprint(hash).as_();
        let r0 = hash as u32;
        let r1 = rotl64(hash, 21) as u32;
        let r2 = rotl64(hash, 42) as u32;
        let h0 = reduce(r0, self.blocklength);
        let h1 = reduce(r1, self.blocklength) + self.blocklength;
        let h2 = reduce(r2, self.blocklength) + 2 * self.blocklength;

        f == (self.fingerprints[h0 as usize]
            ^ self.fingerprints[h1 as usize]
            ^ self.fingerprints[h2 as usize])
            .into()
    }

    fn len(&self) -> usize {
        self.fingerprints.len()
    }

    pub fn new(keys: [u64; { N }]) -> Self {
        let mut default_xor_filter = XorFilter {
            seed: 0,
            blocklength: bl::<{ N }>() as u32,
            fingerprints: [Default::default(); capacity::<{ N }>()],
        };

        default_xor_filter.populate(&keys);
        default_xor_filter
    }

    pub fn geth0h1h2(&mut self, k: u64) -> Hashes {
        let hash = mixsplit(k, self.seed);
        let r0 = hash as u32;
        let r1 = rotl64(hash, 21) as u32;
        let r2 = rotl64(hash, 42) as u32;

        let answer = Hashes {
            h: hash,
            h0: reduce(r0, self.blocklength),
            h1: reduce(r1, self.blocklength),
            h2: reduce(r2, self.blocklength),
        };

        answer
    }

    pub fn geth0(&mut self, hash: u64) -> u32 {
        let r0 = hash as u32;
        reduce(r0, self.blocklength)
    }

    pub fn geth1(&mut self, hash: u64) -> u32 {
        let r1 = rotl64(hash, 21) as u32;
        reduce(r1, self.blocklength)
    }

    pub fn geth2(&mut self, hash: u64) -> u32 {
        let r2 = rotl64(hash, 42) as u32;
        reduce(r2, self.blocklength)
    }
}

impl<const N: usize> From<[u64; N]> for XorFilter<N>
where
    [(); capacity::<N>()]: Sized,
    [(); bl::<N>() as usize]: Sized,
{
    fn from(keys: [u64; N]) -> XorFilter<N> {
        let mut default_xor_filter = XorFilter {
            seed: 0,
            blocklength: bl::<{ N }>() as u32,
            fingerprints: [Default::default(); capacity::<{ N }>()],
        };

        default_xor_filter.populate(&keys);
        default_xor_filter
    }
}

#[derive(Debug)]
pub struct H012 {
    pub h0: u32,
    pub h1: u32,
    pub h2: u32,
}

#[derive(Copy, Clone, Debug)]
pub struct Xorset {
    pub xormask: u64,
    pub count: u32,
}

#[derive(Debug)]
pub struct Hashes {
    pub h: u64,
    pub h0: u32,
    pub h1: u32,
    pub h2: u32,
}

#[derive(Copy, Clone, Debug)]
pub struct Keyindex {
    pub hash: u64,
    pub index: u32,
}

pub fn murmur64(mut h: u64) -> u64 {
    h ^= h >> 33;
    h = h.wrapping_mul(0xff51afd7ed558ccd);
    h ^= h >> 33;
    h = h.wrapping_mul(0xc4ceb9fe1a85ec53);
    h ^= h >> 33;
    h
}

pub fn splitmix64(mut seed: u64) -> u64 {
    let mut z = seed.wrapping_add(0x9e3779b97f4a7c15);
    z = (z ^ (z >> 30)).wrapping_mul(0xbf58476d1ce4e5b9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94d049bb133111eb);
    z ^ (z >> 31)
}

pub fn mixsplit(key: u64, seed: u64) -> u64 {
    murmur64(key.wrapping_add(seed))
}

pub fn rotl64(n: u64, c: i64) -> u64 {
    (n << (c & 63)) | (n >> ((-c) & 63))
}

// http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
pub fn reduce(hash: u32, n: u32) -> u32 {
    ((hash as u64).wrapping_mul(n as u64) >> 32) as u32
}

pub fn fingerprint(hash: u64) -> u64 {
    hash ^ (hash >> 32)
}

// attribution: https://crates.io/crates/micromath
pub fn floor(x: f64) -> f64 {
    let mut x_trunc = (x as i32) as f64;

    if x < x_trunc {
        x_trunc -= 1.0;
    }

    x_trunc
}

pub fn ceil(x: f64) -> f64 {
    -floor(-x)
}

pub const fn capacity<const N: usize>() -> usize {
    ((32_u32 + ceil32(1.23 * (N as f32)) as u32) / 3 * 3) as usize
}

pub const fn bl<const N: usize>() -> usize {
    capacity::<N>() / 3
}

pub const fn floor32(x: f32) -> f32 {
    let mut x_trunc = (x as i32) as f32;

    if x < x_trunc {
        x_trunc -= 1.0;
    }

    x_trunc
}

pub const fn ceil32(x: f32) -> f32 {
    -floor32(-x)
}

fn hash<T: Hash, H: Hasher + Default>(key: &T) -> u64 {
    let mut hasher = H::default();
    key.hash(&mut hasher);
    hasher.finish()
}