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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
/*!
Generic crate-internal routines for 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 crate::{
    arch::all::{is_equal_raw, packedpair::Pair},
    ext::Pointer,
    vector::{MoveMask, Vector},
};

/// A generic architecture dependent "packed pair" finder.
///
/// 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.
///
/// This is architecture dependent because it uses specific vector operations
/// to look for occurrences of the pair of bytes.
///
/// This type is not meant to be exported and is instead meant to be used as
/// the implementation for architecture specific facades. Why? Because it's a
/// bit of a quirky API that requires `inline(always)` annotations. And pretty
/// much everything has safety obligations due (at least) to the caller needing
/// to inline calls into routines marked with
/// `#[target_feature(enable = "...")]`.
#[derive(Clone, Copy, Debug)]
pub(crate) struct Finder<V> {
    pair: Pair,
    v1: V,
    v2: V,
    min_haystack_len: usize,
}

impl<V: Vector> Finder<V> {
    /// 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`.
    ///
    /// # Safety
    ///
    /// Callers must ensure that whatever vector type this routine is called
    /// with is supported by the current environment.
    ///
    /// Callers must also ensure that `needle.len() >= 2`.
    #[inline(always)]
    pub(crate) unsafe fn new(needle: &[u8], pair: Pair) -> Finder<V> {
        let max_index = pair.index1().max(pair.index2());
        let min_haystack_len =
            core::cmp::max(needle.len(), usize::from(max_index) + V::BYTES);
        let v1 = V::splat(needle[usize::from(pair.index1())]);
        let v2 = V::splat(needle[usize::from(pair.index2())]);
        Finder { pair, v1, v2, min_haystack_len }
    }

    /// Searches the given haystack for the given needle. The needle given
    /// should be the same as the needle that this finder was initialized
    /// with.
    ///
    /// # Panics
    ///
    /// When `haystack.len()` is less than [`Finder::min_haystack_len`].
    ///
    /// # Safety
    ///
    /// Since this is meant to be used with vector functions, callers need to
    /// specialize this inside of a function with a `target_feature` attribute.
    /// Therefore, callers must ensure that whatever target feature is being
    /// used supports the vector functions that this function is specialized
    /// for. (For the specific vector functions used, see the Vector trait
    /// implementations.)
    #[inline(always)]
    pub(crate) unsafe fn find(
        &self,
        haystack: &[u8],
        needle: &[u8],
    ) -> Option<usize> {
        assert!(
            haystack.len() >= self.min_haystack_len,
            "haystack too small, should be at least {} but got {}",
            self.min_haystack_len,
            haystack.len(),
        );

        let all = V::Mask::all_zeros_except_least_significant(0);
        let start = haystack.as_ptr();
        let end = start.add(haystack.len());
        let max = end.sub(self.min_haystack_len);
        let mut cur = start;

        // N.B. I did experiment with unrolling the loop to deal with size(V)
        // bytes at a time and 2*size(V) bytes at a time. The double unroll
        // was marginally faster while the quadruple unroll was unambiguously
        // slower. In the end, I decided the complexity from unrolling wasn't
        // worth it. I used the memmem/krate/prebuilt/huge-en/ benchmarks to
        // compare.
        while cur <= max {
            if let Some(chunki) = self.find_in_chunk(needle, cur, end, all) {
                return Some(matched(start, cur, chunki));
            }
            cur = cur.add(V::BYTES);
        }
        if cur < end {
            let remaining = end.distance(cur);
            debug_assert!(
                remaining < self.min_haystack_len,
                "remaining bytes should be smaller than the minimum haystack \
                 length of {}, but there are {} bytes remaining",
                self.min_haystack_len,
                remaining,
            );
            if remaining < needle.len() {
                return None;
            }
            debug_assert!(
                max < cur,
                "after main loop, cur should have exceeded max",
            );
            let overlap = cur.distance(max);
            debug_assert!(
                overlap > 0,
                "overlap ({}) must always be non-zero",
                overlap,
            );
            debug_assert!(
                overlap < V::BYTES,
                "overlap ({}) cannot possibly be >= than a vector ({})",
                overlap,
                V::BYTES,
            );
            // The mask has all of its bits set except for the first N least
            // significant bits, where N=overlap. This way, any matches that
            // occur in find_in_chunk within the overlap are automatically
            // ignored.
            let mask = V::Mask::all_zeros_except_least_significant(overlap);
            cur = max;
            let m = self.find_in_chunk(needle, cur, end, mask);
            if let Some(chunki) = m {
                return Some(matched(start, cur, chunki));
            }
        }
        None
    }

    /// Searches the given haystack for offsets that represent candidate
    /// matches of the `needle` given to this finder's constructor. The offsets
    /// returned, if they are a match, correspond to the starting offset of
    /// `needle` in the given `haystack`.
    ///
    /// # Panics
    ///
    /// When `haystack.len()` is less than [`Finder::min_haystack_len`].
    ///
    /// # Safety
    ///
    /// Since this is meant to be used with vector functions, callers need to
    /// specialize this inside of a function with a `target_feature` attribute.
    /// Therefore, callers must ensure that whatever target feature is being
    /// used supports the vector functions that this function is specialized
    /// for. (For the specific vector functions used, see the Vector trait
    /// implementations.)
    #[inline(always)]
    pub(crate) unsafe fn find_prefilter(
        &self,
        haystack: &[u8],
    ) -> Option<usize> {
        assert!(
            haystack.len() >= self.min_haystack_len,
            "haystack too small, should be at least {} but got {}",
            self.min_haystack_len,
            haystack.len(),
        );

        let start = haystack.as_ptr();
        let end = start.add(haystack.len());
        let max = end.sub(self.min_haystack_len);
        let mut cur = start;

        // N.B. I did experiment with unrolling the loop to deal with size(V)
        // bytes at a time and 2*size(V) bytes at a time. The double unroll
        // was marginally faster while the quadruple unroll was unambiguously
        // slower. In the end, I decided the complexity from unrolling wasn't
        // worth it. I used the memmem/krate/prebuilt/huge-en/ benchmarks to
        // compare.
        while cur <= max {
            if let Some(chunki) = self.find_prefilter_in_chunk(cur) {
                return Some(matched(start, cur, chunki));
            }
            cur = cur.add(V::BYTES);
        }
        if cur < end {
            // This routine immediately quits if a candidate match is found.
            // That means that if we're here, no candidate matches have been
            // found at or before 'ptr'. Thus, we don't need to mask anything
            // out even though we might technically search part of the haystack
            // that we've already searched (because we know it can't match).
            cur = max;
            if let Some(chunki) = self.find_prefilter_in_chunk(cur) {
                return Some(matched(start, cur, chunki));
            }
        }
        None
    }

    /// Search for an occurrence of our byte pair from the needle in the chunk
    /// pointed to by cur, with the end of the haystack pointed to by end.
    /// When an occurrence is found, memcmp is run to check if a match occurs
    /// at the corresponding position.
    ///
    /// `mask` should have bits set corresponding the positions in the chunk
    /// in which matches are considered. This is only used for the last vector
    /// load where the beginning of the vector might have overlapped with the
    /// last load in the main loop. The mask lets us avoid visiting positions
    /// that have already been discarded as matches.
    ///
    /// # Safety
    ///
    /// It must be safe to do an unaligned read of size(V) bytes starting at
    /// both (cur + self.index1) and (cur + self.index2). It must also be safe
    /// to do unaligned loads on cur up to (end - needle.len()).
    #[inline(always)]
    unsafe fn find_in_chunk(
        &self,
        needle: &[u8],
        cur: *const u8,
        end: *const u8,
        mask: V::Mask,
    ) -> Option<usize> {
        let index1 = usize::from(self.pair.index1());
        let index2 = usize::from(self.pair.index2());
        let chunk1 = V::load_unaligned(cur.add(index1));
        let chunk2 = V::load_unaligned(cur.add(index2));
        let eq1 = chunk1.cmpeq(self.v1);
        let eq2 = chunk2.cmpeq(self.v2);

        let mut offsets = eq1.and(eq2).movemask().and(mask);
        while offsets.has_non_zero() {
            let offset = offsets.first_offset();
            let cur = cur.add(offset);
            if end.sub(needle.len()) < cur {
                return None;
            }
            if is_equal_raw(needle.as_ptr(), cur, needle.len()) {
                return Some(offset);
            }
            offsets = offsets.clear_least_significant_bit();
        }
        None
    }

    /// Search for an occurrence of our byte pair from the needle in the chunk
    /// pointed to by cur, with the end of the haystack pointed to by end.
    /// When an occurrence is found, memcmp is run to check if a match occurs
    /// at the corresponding position.
    ///
    /// # Safety
    ///
    /// It must be safe to do an unaligned read of size(V) bytes starting at
    /// both (cur + self.index1) and (cur + self.index2). It must also be safe
    /// to do unaligned reads on cur up to (end - needle.len()).
    #[inline(always)]
    unsafe fn find_prefilter_in_chunk(&self, cur: *const u8) -> Option<usize> {
        let index1 = usize::from(self.pair.index1());
        let index2 = usize::from(self.pair.index2());
        let chunk1 = V::load_unaligned(cur.add(index1));
        let chunk2 = V::load_unaligned(cur.add(index2));
        let eq1 = chunk1.cmpeq(self.v1);
        let eq2 = chunk2.cmpeq(self.v2);

        let offsets = eq1.and(eq2).movemask();
        if !offsets.has_non_zero() {
            return None;
        }
        Some(offsets.first_offset())
    }

    /// 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(crate) fn pair(&self) -> &Pair {
        &self.pair
    }

    /// Returns the minimum haystack length that this `Finder` can search.
    ///
    /// Providing a haystack to this `Finder` shorter than this length is
    /// guaranteed to result in a panic.
    #[inline(always)]
    pub(crate) fn min_haystack_len(&self) -> usize {
        self.min_haystack_len
    }
}

/// Accepts a chunk-relative offset and returns a haystack relative offset.
///
/// This used to be marked `#[cold]` and `#[inline(never)]`, but I couldn't
/// observe a consistent measureable difference between that and just inlining
/// it. So we go with inlining it.
///
/// # Safety
///
/// Same at `ptr::offset_from` in addition to `cur >= start`.
#[inline(always)]
unsafe fn matched(start: *const u8, cur: *const u8, chunki: usize) -> usize {
    cur.distance(start) + chunki
}

// If you're looking for tests, those are run for each instantiation of the
// above code. So for example, see arch::x86_64::sse2::packedpair.