diff options
Diffstat (limited to 'vendor/memchr/src/arch/x86_64/avx2/packedpair.rs')
| -rw-r--r-- | vendor/memchr/src/arch/x86_64/avx2/packedpair.rs | 272 |
1 files changed, 0 insertions, 272 deletions
diff --git a/vendor/memchr/src/arch/x86_64/avx2/packedpair.rs b/vendor/memchr/src/arch/x86_64/avx2/packedpair.rs deleted file mode 100644 index efae7b6..0000000 --- a/vendor/memchr/src/arch/x86_64/avx2/packedpair.rs +++ /dev/null @@ -1,272 +0,0 @@ -/*! -A 256-bit vector implementation of the "packed pair" SIMD algorithm. - -The "packed pair" algorithm is based on the [generic SIMD] algorithm. The main -difference is that it (by default) uses a background distribution of byte -frequencies to heuristically select the pair of bytes to search for. - -[generic SIMD]: http://0x80.pl/articles/simd-strfind.html#first-and-last -*/ - -use core::arch::x86_64::{__m128i, __m256i}; - -use crate::arch::{all::packedpair::Pair, generic::packedpair}; - -/// A "packed pair" finder that uses 256-bit vector operations. -/// -/// This finder picks two bytes that it believes have high predictive power -/// for indicating an overall match of a needle. Depending on whether -/// `Finder::find` or `Finder::find_prefilter` is used, it reports offsets -/// where the needle matches or could match. In the prefilter case, candidates -/// are reported whenever the [`Pair`] of bytes given matches. -#[derive(Clone, Copy, Debug)] -pub struct Finder { - sse2: packedpair::Finder<__m128i>, - avx2: packedpair::Finder<__m256i>, -} - -impl Finder { - /// Create a new pair searcher. The searcher returned can either report - /// exact matches of `needle` or act as a prefilter and report candidate - /// positions of `needle`. - /// - /// If AVX2 is unavailable in the current environment or if a [`Pair`] - /// could not be constructed from the needle given, then `None` is - /// returned. - #[inline] - pub fn new(needle: &[u8]) -> Option<Finder> { - Finder::with_pair(needle, Pair::new(needle)?) - } - - /// Create a new "packed pair" finder using the pair of bytes given. - /// - /// This constructor permits callers to control precisely which pair of - /// bytes is used as a predicate. - /// - /// If AVX2 is unavailable in the current environment, then `None` is - /// returned. - #[inline] - pub fn with_pair(needle: &[u8], pair: Pair) -> Option<Finder> { - if Finder::is_available() { - // SAFETY: we check that sse2/avx2 is available above. We are also - // guaranteed to have needle.len() > 1 because we have a valid - // Pair. - unsafe { Some(Finder::with_pair_impl(needle, pair)) } - } else { - None - } - } - - /// Create a new `Finder` specific to SSE2 vectors and routines. - /// - /// # Safety - /// - /// Same as the safety for `packedpair::Finder::new`, and callers must also - /// ensure that both SSE2 and AVX2 are available. - #[target_feature(enable = "sse2", enable = "avx2")] - #[inline] - unsafe fn with_pair_impl(needle: &[u8], pair: Pair) -> Finder { - let sse2 = packedpair::Finder::<__m128i>::new(needle, pair); - let avx2 = packedpair::Finder::<__m256i>::new(needle, pair); - Finder { sse2, avx2 } - } - - /// Returns true when this implementation is available in the current - /// environment. - /// - /// When this is true, it is guaranteed that [`Finder::with_pair`] will - /// return a `Some` value. Similarly, when it is false, it is guaranteed - /// that `Finder::with_pair` will return a `None` value. Notice that this - /// does not guarantee that [`Finder::new`] will return a `Finder`. Namely, - /// even when `Finder::is_available` is true, it is not guaranteed that a - /// valid [`Pair`] can be found from the needle given. - /// - /// Note also that for the lifetime of a single program, if this returns - /// true then it will always return true. - #[inline] - pub fn is_available() -> bool { - #[cfg(not(target_feature = "sse2"))] - { - false - } - #[cfg(target_feature = "sse2")] - { - #[cfg(target_feature = "avx2")] - { - true - } - #[cfg(not(target_feature = "avx2"))] - { - #[cfg(feature = "std")] - { - std::is_x86_feature_detected!("avx2") - } - #[cfg(not(feature = "std"))] - { - false - } - } - } - } - - /// Execute a search using AVX2 vectors and routines. - /// - /// # Panics - /// - /// When `haystack.len()` is less than [`Finder::min_haystack_len`]. - #[inline] - pub fn find(&self, haystack: &[u8], needle: &[u8]) -> Option<usize> { - // SAFETY: Building a `Finder` means it's safe to call 'sse2' routines. - unsafe { self.find_impl(haystack, needle) } - } - - /// Run this finder on the given haystack as a prefilter. - /// - /// If a candidate match is found, then an offset where the needle *could* - /// begin in the haystack is returned. - /// - /// # Panics - /// - /// When `haystack.len()` is less than [`Finder::min_haystack_len`]. - #[inline] - pub fn find_prefilter(&self, haystack: &[u8]) -> Option<usize> { - // SAFETY: Building a `Finder` means it's safe to call 'sse2' routines. - unsafe { self.find_prefilter_impl(haystack) } - } - - /// Execute a search using AVX2 vectors and routines. - /// - /// # Panics - /// - /// When `haystack.len()` is less than [`Finder::min_haystack_len`]. - /// - /// # Safety - /// - /// (The target feature safety obligation is automatically fulfilled by - /// virtue of being a method on `Finder`, which can only be constructed - /// when it is safe to call `sse2` and `avx2` routines.) - #[target_feature(enable = "sse2", enable = "avx2")] - #[inline] - unsafe fn find_impl( - &self, - haystack: &[u8], - needle: &[u8], - ) -> Option<usize> { - if haystack.len() < self.avx2.min_haystack_len() { - self.sse2.find(haystack, needle) - } else { - self.avx2.find(haystack, needle) - } - } - - /// Execute a prefilter search using AVX2 vectors and routines. - /// - /// # Panics - /// - /// When `haystack.len()` is less than [`Finder::min_haystack_len`]. - /// - /// # Safety - /// - /// (The target feature safety obligation is automatically fulfilled by - /// virtue of being a method on `Finder`, which can only be constructed - /// when it is safe to call `sse2` and `avx2` routines.) - #[target_feature(enable = "sse2", enable = "avx2")] - #[inline] - unsafe fn find_prefilter_impl(&self, haystack: &[u8]) -> Option<usize> { - if haystack.len() < self.avx2.min_haystack_len() { - self.sse2.find_prefilter(haystack) - } else { - self.avx2.find_prefilter(haystack) - } - } - - /// Returns the pair of offsets (into the needle) used to check as a - /// predicate before confirming whether a needle exists at a particular - /// position. - #[inline] - pub fn pair(&self) -> &Pair { - self.avx2.pair() - } - - /// Returns the minimum haystack length that this `Finder` can search. - /// - /// Using a haystack with length smaller than this in a search will result - /// in a panic. The reason for this restriction is that this finder is - /// meant to be a low-level component that is part of a larger substring - /// strategy. In that sense, it avoids trying to handle all cases and - /// instead only handles the cases that it can handle very well. - #[inline] - pub fn min_haystack_len(&self) -> usize { - // The caller doesn't need to care about AVX2's min_haystack_len - // since this implementation will automatically switch to the SSE2 - // implementation if the haystack is too short for AVX2. Therefore, the - // caller only needs to care about SSE2's min_haystack_len. - // - // This does assume that SSE2's min_haystack_len is less than or - // equal to AVX2's min_haystack_len. In practice, this is true and - // there is no way it could be false based on how this Finder is - // implemented. Namely, both SSE2 and AVX2 use the same `Pair`. If - // they used different pairs, then it's possible (although perhaps - // pathological) for SSE2's min_haystack_len to be bigger than AVX2's. - self.sse2.min_haystack_len() - } -} - -#[cfg(test)] -mod tests { - use super::*; - - fn find(haystack: &[u8], needle: &[u8]) -> Option<Option<usize>> { - let f = Finder::new(needle)?; - if haystack.len() < f.min_haystack_len() { - return None; - } - Some(f.find(haystack, needle)) - } - - define_substring_forward_quickcheck!(find); - - #[test] - fn forward_substring() { - crate::tests::substring::Runner::new().fwd(find).run() - } - - #[test] - fn forward_packedpair() { - fn find( - haystack: &[u8], - needle: &[u8], - index1: u8, - index2: u8, - ) -> Option<Option<usize>> { - let pair = Pair::with_indices(needle, index1, index2)?; - let f = Finder::with_pair(needle, pair)?; - if haystack.len() < f.min_haystack_len() { - return None; - } - Some(f.find(haystack, needle)) - } - crate::tests::packedpair::Runner::new().fwd(find).run() - } - - #[test] - fn forward_packedpair_prefilter() { - fn find( - haystack: &[u8], - needle: &[u8], - index1: u8, - index2: u8, - ) -> Option<Option<usize>> { - if !cfg!(target_feature = "sse2") { - return None; - } - let pair = Pair::with_indices(needle, index1, index2)?; - let f = Finder::with_pair(needle, pair)?; - if haystack.len() < f.min_haystack_len() { - return None; - } - Some(f.find_prefilter(haystack)) - } - crate::tests::packedpair::Runner::new().fwd(find).run() - } -} |