Compiler Explorer

Source code

trait HashmapCompatible {
    fn get(&self, map_unsigned: &BitvectorHashmap, map_signed: &BitvectorHashmap, extended_ascii:  &[u64; 256]) -> u64;
    fn insert_mask(&self, map_unsigned: &mut BitvectorHashmap, map_signed: &mut BitvectorHashmap, extended_ascii:  &mut [u64; 256], mask: u64);
}

macro_rules! impl_hashmap_compatible {
    ($base_type:ty $(, $t:ty)*) => {
        impl HashmapCompatible for $base_type {
            #[allow(unused_comparisons)]
            #[inline]
            fn get(&self, map_unsigned: &BitvectorHashmap, map_signed: &BitvectorHashmap, extended_ascii:  &[u64; 256]) -> u64 {
                let key = *self $(as $t)*;
                extended_ascii[key as usize]
            }

#[allow(unused_comparisons)]
            #[inline]
            fn insert_mask(&self, map_unsigned: &mut BitvectorHashmap, map_signed: &mut BitvectorHashmap, extended_ascii:  &mut [u64; 256], mask: u64)
            {
                let key = *self $(as $t)*;

let item = &mut extended_ascii[key as usize];
                *item |= mask;
            }
        }
    }
}

impl_hashmap_compatible!(char, u32);
// extend to i16 so the comparision with 255 is possible
impl_hashmap_compatible!(i8, i16);
impl_hashmap_compatible!(i16);
impl_hashmap_compatible!(i32);
impl_hashmap_compatible!(i64);
impl_hashmap_compatible!(u8);
impl_hashmap_compatible!(u16);
impl_hashmap_compatible!(u32);
impl_hashmap_compatible!(u64);

#[derive(Clone, Copy)]
struct BitvectorHashmapMapElem {
    key: u64,
    value: u64
}

impl Default for BitvectorHashmapMapElem {
    #[inline]
    fn default() -> BitvectorHashmapMapElem {
        BitvectorHashmapMapElem {
            key: 0,
            value: 0,
        }
    }
}

struct BitvectorHashmap {
    map: [BitvectorHashmapMapElem; 128],
}

impl Default for BitvectorHashmap {
    #[inline]
    fn default() -> BitvectorHashmap {
        BitvectorHashmap {
            map: [BitvectorHashmapMapElem::default(); 128],
        }
    }
}

impl BitvectorHashmap {
    fn get(&self, key: u64) -> u64 {
        // todo potentially use unsafe index for performance
        return self.map[self.lookup(key)].value;
    }

fn get_mut(&mut self, key: u64) -> &mut u64 {
        let i = self.lookup(key);
        // todo potentially use unsafe index for performance
        let elem = &mut self.map[i];
        elem.key = key;
        return &mut elem.value;
    }

fn lookup(&self, key: u64) -> usize {
        let mut i = (key % 128) as usize;

if self.map[i].value == 0 || self.map[i].key == key {
            return i;
        }

let mut perturb = key;
        loop {
            i = (i * 5 + perturb as usize + 1) % 128;

if self.map[i].value == 0 || self.map[i].key == key {
                return i;
            }

perturb >>= 5;
        }
    }
}

struct PatternMatchVector {
    map_unsigned: BitvectorHashmap,
    map_signed: BitvectorHashmap,
    extended_ascii: [u64; 256],
}

trait BitVectorInterface {
    fn get<CharT>(&self, block: usize, key: CharT) -> u64
    where
        CharT: HashmapCompatible;
}

impl Default for PatternMatchVector {
    fn default() -> PatternMatchVector
    {
        PatternMatchVector {
            map_unsigned: BitvectorHashmap::default(),
            map_signed: BitvectorHashmap::default(),
            extended_ascii: [0; 256],
        }
    }

}

impl PatternMatchVector {
    fn new<Iter1, CharT>(s1: Iter1) -> PatternMatchVector
    where
        Iter1: IntoIterator<Item = CharT>,
        Iter1::IntoIter: Clone,
        CharT: HashmapCompatible,
    {
        let mut vec = PatternMatchVector {
            map_unsigned: BitvectorHashmap::default(),
            map_signed: BitvectorHashmap::default(),
            extended_ascii: [0; 256],
        };
        vec.insert(s1);
        vec
    }

fn insert<Iter1, CharT>(&mut self, s1: Iter1)
    where
        Iter1: IntoIterator<Item = CharT>,
        Iter1::IntoIter: Clone,
        CharT: HashmapCompatible,
    {
        let mut mask: u64 = 1;
        for ch in s1.into_iter() {
            self.insert_mask(ch, mask);
            mask <<= 1;
        }
    }

fn insert_mask<CharT>(&mut self, key: CharT, mask: u64)
    where
        CharT: HashmapCompatible,
    {
        key.insert_mask(&mut self.map_unsigned, &mut self.map_signed, &mut self.extended_ascii, mask);
    }
}

impl BitVectorInterface for PatternMatchVector {
    fn get<CharT>(&self, _block: usize, key: CharT) -> u64
    where
        CharT: HashmapCompatible,
    {
        key.get(&self.map_unsigned, &self.map_signed, &self.extended_ascii)
    }
}

fn levenshtein_hyrroe2003<Iter1, Iter2, Elem1, Elem2>(
    pm: &PatternMatchVector,
    _s1: Iter1,
    len1: usize,
    s2: Iter2,
    _len2: usize,
    score_cutoff: usize,
) -> usize
where
    Iter1: IntoIterator<Item = Elem1>,
    Iter1::IntoIter: Clone,
    Iter2: IntoIterator<Item = Elem2>,
    Iter2::IntoIter: Clone,
    Elem1: PartialEq<Elem2> + HashmapCompatible,
    Elem2: PartialEq<Elem1> + HashmapCompatible,
{
    debug_assert!(len1 != 0);

/* VP is set to 1^m. Shifting by bitwidth would be undefined behavior */
    let mut vp: u64 = !(0 as u64);
    let mut vn: u64 = 0;

let mut dist = len1;
    let mask: u64 = (1 as u64) << (len1 - 1);

for ch2 in s2.into_iter() {
        let pm_j = pm.get(0, ch2);
        let x = pm_j;
        let d0 = (((x & vp) + vp) ^ vp) | x | vn;

/* Step 2: Computing HP and HN */
        let mut hp = vn | !(d0 | vp);
        let mut hn = d0 & vp;

/* Step 3: Computing the value D[m,j] */
        dist += (hp & mask != 0) as usize;
        dist -= (hn & mask != 0) as usize;

/* Step 4: Computing Vp and VN */
        hp = (hp << 1) | 1;
        hn = hn << 1;

vp = hn | !(d0 | hp);
        vn = hp & d0;
    }

if dist > score_cutoff {
        dist = score_cutoff + 1;
    }

return dist;
}

pub fn test(s1: &str, s2: &str) -> usize {
    let s1_iter = s1.bytes().into_iter();
    let s2_iter = s2.bytes().into_iter();
    let len1 = s1_iter.clone().count();
    let len2 = s2_iter.clone().count();

// this was the intial solution
    //let mut vec = PatternMatchVector {
    //    map_unsigned: BitvectorHashmap::default(),
    //    map_signed: BitvectorHashmap::default(),
    //    extended_ascii: [0; 256],
    //};
    // since then I figured out that I can return the array as well
    // as long as I insert the text into the bitvectors separately
    let mut vec = PatternMatchVector::default();
    vec.insert(s2_iter.clone());

return levenshtein_hyrroe2003(
        &vec,
        s2_iter,
        len2,
        s1_iter,
        len1,
        1000,
    );
}