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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

#[cfg(not(feature = "std"))]
pub(crate) use self::nostd::Forward;
#[cfg(feature = "std")]
pub(crate) use self::std::Forward;

#[cfg(feature = "std")]
mod std {
    use core::arch::x86_64::{__m128i, __m256i};

    use crate::memmem::{genericsimd, NeedleInfo};

    /// An AVX accelerated vectorized substring search routine that only works
    /// on small needles.
    #[derive(Clone, Copy, Debug)]
    pub(crate) struct Forward(genericsimd::Forward);

    impl Forward {
        /// Create a new "generic simd" forward searcher. If one could not be
        /// created from the given inputs, then None is returned.
        pub(crate) fn new(
            ninfo: &NeedleInfo,
            needle: &[u8],
        ) -> Option<Forward> {
            if !cfg!(memchr_runtime_avx) || !is_x86_feature_detected!("avx2") {
                return None;
            }
            genericsimd::Forward::new(ninfo, needle).map(Forward)
        }

        /// Returns the minimum length of haystack that is needed for this
        /// searcher to work. Passing a haystack with a length smaller than
        /// this will cause `find` to panic.
        #[inline(always)]
        pub(crate) fn min_haystack_len(&self) -> usize {
            self.0.min_haystack_len::<__m128i>()
        }

        #[inline(always)]
        pub(crate) fn find(
            &self,
            haystack: &[u8],
            needle: &[u8],
        ) -> Option<usize> {
            // SAFETY: The only way a Forward value can exist is if the avx2
            // target feature is enabled. This is the only safety requirement
            // for calling the genericsimd searcher.
            unsafe { self.find_impl(haystack, needle) }
        }

        /// The implementation of find marked with the appropriate target
        /// feature.
        ///
        /// # Safety
        ///
        /// Callers must ensure that the avx2 CPU feature is enabled in the
        /// current environment.
        #[target_feature(enable = "avx2")]
        unsafe fn find_impl(
            &self,
            haystack: &[u8],
            needle: &[u8],
        ) -> Option<usize> {
            if haystack.len() < self.0.min_haystack_len::<__m256i>() {
                genericsimd::fwd_find::<__m128i>(&self.0, haystack, needle)
            } else {
                genericsimd::fwd_find::<__m256i>(&self.0, haystack, needle)
            }
        }
    }
}

// We still define the avx "forward" type on nostd to make caller code a bit
// simpler. This avoids needing a lot more conditional compilation.
#[cfg(not(feature = "std"))]
mod nostd {
    use crate::memmem::NeedleInfo;

    #[derive(Clone, Copy, Debug)]
    pub(crate) struct Forward(());

    impl Forward {
        pub(crate) fn new(
            ninfo: &NeedleInfo,
            needle: &[u8],
        ) -> Option<Forward> {
            None
        }

        pub(crate) fn min_haystack_len(&self) -> usize {
            unreachable!()
        }

        pub(crate) fn find(
            &self,
            haystack: &[u8],
            needle: &[u8],
        ) -> Option<usize> {
            unreachable!()
        }
    }
}

#[cfg(all(test, feature = "std", not(miri)))]
mod tests {
    use crate::memmem::{prefilter::PrefilterState, NeedleInfo};

    fn find(
        _: &mut PrefilterState,
        ninfo: &NeedleInfo,
        haystack: &[u8],
        needle: &[u8],
    ) -> Option<usize> {
        super::Forward::new(ninfo, needle).unwrap().find(haystack, needle)
    }

    #[test]
    fn prefilter_permutations() {
        use crate::memmem::prefilter::tests::PrefilterTest;

        if !is_x86_feature_detected!("avx2") {
            return;
        }
        // SAFETY: The safety of find only requires that the current CPU
        // support AVX2, which we checked above.
        unsafe {
            PrefilterTest::run_all_tests_filter(find, |t| {
                // This substring searcher only works on certain configs, so
                // filter our tests such that Forward::new will be guaranteed
                // to succeed. (And also remove tests with a haystack that is
                // too small.)
                let fwd = match super::Forward::new(&t.ninfo, &t.needle) {
                    None => return false,
                    Some(fwd) => fwd,
                };
                t.haystack.len() >= fwd.min_haystack_len()
            })
        }
    }
}