1 /*! 2 A 128-bit vector implementation of the "packed pair" SIMD algorithm. 3 4 The "packed pair" algorithm is based on the [generic SIMD] algorithm. The main 5 difference is that it (by default) uses a background distribution of byte 6 frequencies to heuristically select the pair of bytes to search for. 7 8 [generic SIMD]: http://0x80.pl/articles/simd-strfind.html#first-and-last 9 */ 10 11 use core::arch::x86_64::__m128i; 12 13 use crate::arch::{all::packedpair::Pair, generic::packedpair}; 14 15 /// A "packed pair" finder that uses 128-bit vector operations. 16 /// 17 /// This finder picks two bytes that it believes have high predictive power 18 /// for indicating an overall match of a needle. Depending on whether 19 /// `Finder::find` or `Finder::find_prefilter` is used, it reports offsets 20 /// where the needle matches or could match. In the prefilter case, candidates 21 /// are reported whenever the [`Pair`] of bytes given matches. 22 #[derive(Clone, Copy, Debug)] 23 pub struct Finder(packedpair::Finder<__m128i>); 24 25 impl Finder { 26 /// Create a new pair searcher. The searcher returned can either report 27 /// exact matches of `needle` or act as a prefilter and report candidate 28 /// positions of `needle`. 29 /// 30 /// If SSE2 is unavailable in the current environment or if a [`Pair`] 31 /// could not be constructed from the needle given, then `None` is 32 /// returned. 33 #[inline] new(needle: &[u8]) -> Option<Finder>34 pub fn new(needle: &[u8]) -> Option<Finder> { 35 Finder::with_pair(needle, Pair::new(needle)?) 36 } 37 38 /// Create a new "packed pair" finder using the pair of bytes given. 39 /// 40 /// This constructor permits callers to control precisely which pair of 41 /// bytes is used as a predicate. 42 /// 43 /// If SSE2 is unavailable in the current environment, then `None` is 44 /// returned. 45 #[inline] with_pair(needle: &[u8], pair: Pair) -> Option<Finder>46 pub fn with_pair(needle: &[u8], pair: Pair) -> Option<Finder> { 47 if Finder::is_available() { 48 // SAFETY: we check that sse2 is available above. We are also 49 // guaranteed to have needle.len() > 1 because we have a valid 50 // Pair. 51 unsafe { Some(Finder::with_pair_impl(needle, pair)) } 52 } else { 53 None 54 } 55 } 56 57 /// Create a new `Finder` specific to SSE2 vectors and routines. 58 /// 59 /// # Safety 60 /// 61 /// Same as the safety for `packedpair::Finder::new`, and callers must also 62 /// ensure that SSE2 is available. 63 #[target_feature(enable = "sse2")] 64 #[inline] with_pair_impl(needle: &[u8], pair: Pair) -> Finder65 unsafe fn with_pair_impl(needle: &[u8], pair: Pair) -> Finder { 66 let finder = packedpair::Finder::<__m128i>::new(needle, pair); 67 Finder(finder) 68 } 69 70 /// Returns true when this implementation is available in the current 71 /// environment. 72 /// 73 /// When this is true, it is guaranteed that [`Finder::with_pair`] will 74 /// return a `Some` value. Similarly, when it is false, it is guaranteed 75 /// that `Finder::with_pair` will return a `None` value. Notice that this 76 /// does not guarantee that [`Finder::new`] will return a `Finder`. Namely, 77 /// even when `Finder::is_available` is true, it is not guaranteed that a 78 /// valid [`Pair`] can be found from the needle given. 79 /// 80 /// Note also that for the lifetime of a single program, if this returns 81 /// true then it will always return true. 82 #[inline] is_available() -> bool83 pub fn is_available() -> bool { 84 #[cfg(not(target_feature = "sse2"))] 85 { 86 false 87 } 88 #[cfg(target_feature = "sse2")] 89 { 90 true 91 } 92 } 93 94 /// Execute a search using SSE2 vectors and routines. 95 /// 96 /// # Panics 97 /// 98 /// When `haystack.len()` is less than [`Finder::min_haystack_len`]. 99 #[inline] find(&self, haystack: &[u8], needle: &[u8]) -> Option<usize>100 pub fn find(&self, haystack: &[u8], needle: &[u8]) -> Option<usize> { 101 // SAFETY: Building a `Finder` means it's safe to call 'sse2' routines. 102 unsafe { self.find_impl(haystack, needle) } 103 } 104 105 /// Run this finder on the given haystack as a prefilter. 106 /// 107 /// If a candidate match is found, then an offset where the needle *could* 108 /// begin in the haystack is returned. 109 /// 110 /// # Panics 111 /// 112 /// When `haystack.len()` is less than [`Finder::min_haystack_len`]. 113 #[inline] find_prefilter(&self, haystack: &[u8]) -> Option<usize>114 pub fn find_prefilter(&self, haystack: &[u8]) -> Option<usize> { 115 // SAFETY: Building a `Finder` means it's safe to call 'sse2' routines. 116 unsafe { self.find_prefilter_impl(haystack) } 117 } 118 119 /// Execute a search using SSE2 vectors and routines. 120 /// 121 /// # Panics 122 /// 123 /// When `haystack.len()` is less than [`Finder::min_haystack_len`]. 124 /// 125 /// # Safety 126 /// 127 /// (The target feature safety obligation is automatically fulfilled by 128 /// virtue of being a method on `Finder`, which can only be constructed 129 /// when it is safe to call `sse2` routines.) 130 #[target_feature(enable = "sse2")] 131 #[inline] find_impl( &self, haystack: &[u8], needle: &[u8], ) -> Option<usize>132 unsafe fn find_impl( 133 &self, 134 haystack: &[u8], 135 needle: &[u8], 136 ) -> Option<usize> { 137 self.0.find(haystack, needle) 138 } 139 140 /// Execute a prefilter search using SSE2 vectors and routines. 141 /// 142 /// # Panics 143 /// 144 /// When `haystack.len()` is less than [`Finder::min_haystack_len`]. 145 /// 146 /// # Safety 147 /// 148 /// (The target feature safety obligation is automatically fulfilled by 149 /// virtue of being a method on `Finder`, which can only be constructed 150 /// when it is safe to call `sse2` routines.) 151 #[target_feature(enable = "sse2")] 152 #[inline] find_prefilter_impl(&self, haystack: &[u8]) -> Option<usize>153 unsafe fn find_prefilter_impl(&self, haystack: &[u8]) -> Option<usize> { 154 self.0.find_prefilter(haystack) 155 } 156 157 /// Returns the pair of offsets (into the needle) used to check as a 158 /// predicate before confirming whether a needle exists at a particular 159 /// position. 160 #[inline] pair(&self) -> &Pair161 pub fn pair(&self) -> &Pair { 162 self.0.pair() 163 } 164 165 /// Returns the minimum haystack length that this `Finder` can search. 166 /// 167 /// Using a haystack with length smaller than this in a search will result 168 /// in a panic. The reason for this restriction is that this finder is 169 /// meant to be a low-level component that is part of a larger substring 170 /// strategy. In that sense, it avoids trying to handle all cases and 171 /// instead only handles the cases that it can handle very well. 172 #[inline] min_haystack_len(&self) -> usize173 pub fn min_haystack_len(&self) -> usize { 174 self.0.min_haystack_len() 175 } 176 } 177 178 #[cfg(test)] 179 mod tests { 180 use super::*; 181 find(haystack: &[u8], needle: &[u8]) -> Option<Option<usize>>182 fn find(haystack: &[u8], needle: &[u8]) -> Option<Option<usize>> { 183 let f = Finder::new(needle)?; 184 if haystack.len() < f.min_haystack_len() { 185 return None; 186 } 187 Some(f.find(haystack, needle)) 188 } 189 190 define_substring_forward_quickcheck!(find); 191 192 #[test] forward_substring()193 fn forward_substring() { 194 crate::tests::substring::Runner::new().fwd(find).run() 195 } 196 197 #[test] forward_packedpair()198 fn forward_packedpair() { 199 fn find( 200 haystack: &[u8], 201 needle: &[u8], 202 index1: u8, 203 index2: u8, 204 ) -> Option<Option<usize>> { 205 let pair = Pair::with_indices(needle, index1, index2)?; 206 let f = Finder::with_pair(needle, pair)?; 207 if haystack.len() < f.min_haystack_len() { 208 return None; 209 } 210 Some(f.find(haystack, needle)) 211 } 212 crate::tests::packedpair::Runner::new().fwd(find).run() 213 } 214 215 #[test] forward_packedpair_prefilter()216 fn forward_packedpair_prefilter() { 217 fn find( 218 haystack: &[u8], 219 needle: &[u8], 220 index1: u8, 221 index2: u8, 222 ) -> Option<Option<usize>> { 223 let pair = Pair::with_indices(needle, index1, index2)?; 224 let f = Finder::with_pair(needle, pair)?; 225 if haystack.len() < f.min_haystack_len() { 226 return None; 227 } 228 Some(f.find_prefilter(haystack)) 229 } 230 crate::tests::packedpair::Runner::new().fwd(find).run() 231 } 232 } 233