frizbee 0.10.0

Fast typo-resistant fuzzy matching via SIMD smith waterman, similar algorithm to FZF/FZY
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

use crate::prefilter::backend::{Backend, BitMaskOps};

#[inline(always)]
pub(crate) unsafe fn load_window<B: Backend>(
    haystack: &[u8],
    start: usize,
    len: usize,
) -> (B::Chunk, B::Mask) {
    unsafe {
        debug_assert!(B::LANES <= 64);
        let remaining = len - start;
        if remaining >= B::LANES {
            return (B::load(haystack.as_ptr().add(start)), B::Mask::all());
        }

        let mask = B::Mask::first_n(remaining);
        let ptr = haystack.as_ptr().add(start);
        // if the read wouldn't pass a page boundary, we can read past the end
        // of the haystack and mask out the invalid bytes
        if can_overread(ptr, B::LANES) {
            (B::load(ptr), mask)
        } else {
            (B::load_partial(ptr, remaining, mask), mask)
        }
    }
}

#[inline(always)]
pub(super) unsafe fn load_window_maskless<B: Backend>(
    haystack: &[u8],
    start: usize,
    len: usize,
) -> B::Chunk {
    unsafe {
        debug_assert!(B::LANES <= 64);
        let remaining = len - start;
        if remaining >= B::LANES {
            return B::load(haystack.as_ptr().add(start));
        }

        let ptr = haystack.as_ptr().add(start);
        if can_overread(ptr, B::LANES) {
            B::load(ptr)
        } else {
            let mask = B::Mask::first_n(remaining);
            B::load_partial(ptr, remaining, mask)
        }
    }
}

#[inline(always)]
pub(crate) fn can_overread(ptr: *const u8, bytes: usize) -> bool {
    if cfg!(feature = "safe_read") || cfg!(miri) {
        return false;
    }
    (ptr as usize & 0xFFF) <= (4096 - bytes)
}