1/*!
2A 128-bit vector implementation of the "packed pair" SIMD algorithm.
3
4The "packed pair" algorithm is based on the [generic SIMD] algorithm. The main
5difference is that it (by default) uses a background distribution of byte
6frequencies 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
11use core::arch::x86_64::__m128i;
12
13use 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)]
23pub struct Finder(packedpair::Finder<__m128i>);
24
25impl 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]
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]
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]
65 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]
83 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]
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]
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]
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]
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]
161 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]
173 pub fn min_haystack_len(&self) -> usize {
174 self.0.min_haystack_len()
175 }
176}
177
178#[cfg(test)]
179mod tests {
180 use super::*;
181
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]
193 fn forward_substring() {
194 crate::tests::substring::Runner::new().fwd(find).run()
195 }
196
197 #[test]
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]
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