#
memchr/arch/x86_64/avx2/
memchr.rs

    1/*!
    2This module defines 256-bit vector implementations of `memchr` and friends.
    3
    4The main types in this module are [`One`], [`Two`] and [`Three`]. They are for
    5searching for one, two or three distinct bytes, respectively, in a haystack.
    6Each type also has corresponding double ended iterators. These searchers are
    7typically much faster than scalar routines accomplishing the same task.
    8
    9The `One` searcher also provides a [`One::count`] routine for efficiently
    10counting the number of times a single byte occurs in a haystack. This is
    11useful, for example, for counting the number of lines in a haystack. This
    12routine exists because it is usually faster, especially with a high match
    13count, then using [`One::find`] repeatedly. ([`OneIter`] specializes its
    14`Iterator::count` implementation to use this routine.)
    15
    16Only one, two and three bytes are supported because three bytes is about
    17the point where one sees diminishing returns. Beyond this point and it's
    18probably (but not necessarily) better to just use a simple `[bool; 256]` array
    19or similar. However, it depends mightily on the specific work-load and the
    20expected match frequency.
    21*/
    22
    23use core::arch::x86_64::{__m128i, __m256i};
    24
    25use crate::{arch::generic::memchr as generic, ext::Pointer, vector::Vector};
    26
    27/// Finds all occurrences of a single byte in a haystack.
    28#[derive(Clone, Copy, Debug)]
    29pub struct One {
    30    /// Used for haystacks less than 32 bytes.
    31    sse2: generic::One<__m128i>,
    32    /// Used for haystacks bigger than 32 bytes.
    33    avx2: generic::One<__m256i>,
    34}
    35
    36impl One {
    37    /// Create a new searcher that finds occurrences of the needle byte given.
    38    ///
    39    /// This particular searcher is specialized to use AVX2 vector instructions
    40    /// that typically make it quite fast. (SSE2 is used for haystacks that
    41    /// are too short to accommodate an AVX2 vector.)
    42    ///
    43    /// If either SSE2 or AVX2 is unavailable in the current environment, then
    44    /// `None` is returned.
    45    #[inline]
    46    pub fn new(needle: u8) -> Option<One> {
    47        if One::is_available() {
    48            // SAFETY: we check that sse2 and avx2 are available above.
    49            unsafe { Some(One::new_unchecked(needle)) }
    50        } else {
    51            None
    52        }
    53    }
    54
    55    /// Create a new finder specific to AVX2 vectors and routines without
    56    /// checking that either SSE2 or AVX2 is available.
    57    ///
    58    /// # Safety
    59    ///
    60    /// Callers must guarantee that it is safe to execute both `sse2` and
    61    /// `avx2` instructions in the current environment.
    62    ///
    63    /// Note that it is a common misconception that if one compiles for an
    64    /// `x86_64` target, then they therefore automatically have access to SSE2
    65    /// instructions. While this is almost always the case, it isn't true in
    66    /// 100% of cases.
    67    #[target_feature(enable = "sse2", enable = "avx2")]
    68    #[inline]
    69    pub unsafe fn new_unchecked(needle: u8) -> One {
    70        One {
    71            sse2: generic::One::new(needle),
    72            avx2: generic::One::new(needle),
    73        }
    74    }
    75
    76    /// Returns true when this implementation is available in the current
    77    /// environment.
    78    ///
    79    /// When this is true, it is guaranteed that [`One::new`] will return
    80    /// a `Some` value. Similarly, when it is false, it is guaranteed that
    81    /// `One::new` will return a `None` value.
    82    ///
    83    /// Note also that for the lifetime of a single program, if this returns
    84    /// true then it will always return true.
    85    #[inline]
    86    pub fn is_available() -> bool {
    87        #[cfg(not(target_feature = "sse2"))]
    88        {
    89            false
    90        }
    91        #[cfg(target_feature = "sse2")]
    92        {
    93            #[cfg(target_feature = "avx2")]
    94            {
    95                true
    96            }
    97            #[cfg(not(target_feature = "avx2"))]
    98            {
    99                #[cfg(feature = "std")]
    100                {
    101                    std::is_x86_feature_detected!("avx2")
    102                }
    103                #[cfg(not(feature = "std"))]
    104                {
    105                    false
    106                }
    107            }
    108        }
    109    }
    110
    111    /// Return the first occurrence of one of the needle bytes in the given
    112    /// haystack. If no such occurrence exists, then `None` is returned.
    113    ///
    114    /// The occurrence is reported as an offset into `haystack`. Its maximum
    115    /// value is `haystack.len() - 1`.
    116    #[inline]
    117    pub fn find(&self, haystack: &[u8]) -> Option<usize> {
    118        // SAFETY: `find_raw` guarantees that if a pointer is returned, it
    119        // falls within the bounds of the start and end pointers.
    120        unsafe {
    121            generic::search_slice_with_raw(haystack, |s, e| {
    122                self.find_raw(s, e)
    123            })
    124        }
    125    }
    126
    127    /// Return the last occurrence of one of the needle bytes in the given
    128    /// haystack. If no such occurrence exists, then `None` is returned.
    129    ///
    130    /// The occurrence is reported as an offset into `haystack`. Its maximum
    131    /// value is `haystack.len() - 1`.
    132    #[inline]
    133    pub fn rfind(&self, haystack: &[u8]) -> Option<usize> {
    134        // SAFETY: `find_raw` guarantees that if a pointer is returned, it
    135        // falls within the bounds of the start and end pointers.
    136        unsafe {
    137            generic::search_slice_with_raw(haystack, |s, e| {
    138                self.rfind_raw(s, e)
    139            })
    140        }
    141    }
    142
    143    /// Counts all occurrences of this byte in the given haystack.
    144    #[inline]
    145    pub fn count(&self, haystack: &[u8]) -> usize {
    146        // SAFETY: All of our pointers are derived directly from a borrowed
    147        // slice, which is guaranteed to be valid.
    148        unsafe {
    149            let start = haystack.as_ptr();
    150            let end = start.add(haystack.len());
    151            self.count_raw(start, end)
    152        }
    153    }
    154
    155    /// Like `find`, but accepts and returns raw pointers.
    156    ///
    157    /// When a match is found, the pointer returned is guaranteed to be
    158    /// `>= start` and `< end`.
    159    ///
    160    /// This routine is useful if you're already using raw pointers and would
    161    /// like to avoid converting back to a slice before executing a search.
    162    ///
    163    /// # Safety
    164    ///
    165    /// * Both `start` and `end` must be valid for reads.
    166    /// * Both `start` and `end` must point to an initialized value.
    167    /// * Both `start` and `end` must point to the same allocated object and
    168    /// must either be in bounds or at most one byte past the end of the
    169    /// allocated object.
    170    /// * Both `start` and `end` must be _derived from_ a pointer to the same
    171    /// object.
    172    /// * The distance between `start` and `end` must not overflow `isize`.
    173    /// * The distance being in bounds must not rely on "wrapping around" the
    174    /// address space.
    175    ///
    176    /// Note that callers may pass a pair of pointers such that `start >= end`.
    177    /// In that case, `None` will always be returned.
    178    #[inline]
    179    pub unsafe fn find_raw(
    180        &self,
    181        start: *const u8,
    182        end: *const u8,
    183    ) -> Option<*const u8> {
    184        if start >= end {
    185            return None;
    186        }
    187        let len = end.distance(start);
    188        if len < __m256i::BYTES {
    189            return if len < __m128i::BYTES {
    190                // SAFETY: We require the caller to pass valid start/end
    191                // pointers.
    192                generic::fwd_byte_by_byte(start, end, |b| {
    193                    b == self.sse2.needle1()
    194                })
    195            } else {
    196                // SAFETY: We require the caller to pass valid start/end
    197                // pointers.
    198                self.find_raw_sse2(start, end)
    199            };
    200        }
    201        // SAFETY: Building a `One` means it's safe to call both 'sse2' and
    202        // 'avx2' routines. Also, we've checked that our haystack is big
    203        // enough to run on the vector routine. Pointer validity is caller's
    204        // responsibility.
    205        //
    206        // Note that we could call `self.avx2.find_raw` directly here. But that
    207        // means we'd have to annotate this routine with `target_feature`.
    208        // Which is fine, because this routine is `unsafe` anyway and the
    209        // `target_feature` obligation is met by virtue of building a `One`.
    210        // The real problem is that a routine with a `target_feature`
    211        // annotation generally can't be inlined into caller code unless
    212        // the caller code has the same target feature annotations. Namely,
    213        // the common case (at time of writing) is for calling code to not
    214        // have the `avx2` target feature enabled *at compile time*. Without
    215        // `target_feature` on this routine, it can be inlined which will
    216        // handle some of the short-haystack cases above without touching the
    217        // architecture specific code.
    218        self.find_raw_avx2(start, end)
    219    }
    220
    221    /// Like `rfind`, but accepts and returns raw pointers.
    222    ///
    223    /// When a match is found, the pointer returned is guaranteed to be
    224    /// `>= start` and `< end`.
    225    ///
    226    /// This routine is useful if you're already using raw pointers and would
    227    /// like to avoid converting back to a slice before executing a search.
    228    ///
    229    /// # Safety
    230    ///
    231    /// * Both `start` and `end` must be valid for reads.
    232    /// * Both `start` and `end` must point to an initialized value.
    233    /// * Both `start` and `end` must point to the same allocated object and
    234    /// must either be in bounds or at most one byte past the end of the
    235    /// allocated object.
    236    /// * Both `start` and `end` must be _derived from_ a pointer to the same
    237    /// object.
    238    /// * The distance between `start` and `end` must not overflow `isize`.
    239    /// * The distance being in bounds must not rely on "wrapping around" the
    240    /// address space.
    241    ///
    242    /// Note that callers may pass a pair of pointers such that `start >= end`.
    243    /// In that case, `None` will always be returned.
    244    #[inline]
    245    pub unsafe fn rfind_raw(
    246        &self,
    247        start: *const u8,
    248        end: *const u8,
    249    ) -> Option<*const u8> {
    250        if start >= end {
    251            return None;
    252        }
    253        let len = end.distance(start);
    254        if len < __m256i::BYTES {
    255            return if len < __m128i::BYTES {
    256                // SAFETY: We require the caller to pass valid start/end
    257                // pointers.
    258                generic::rev_byte_by_byte(start, end, |b| {
    259                    b == self.sse2.needle1()
    260                })
    261            } else {
    262                // SAFETY: We require the caller to pass valid start/end
    263                // pointers.
    264                self.rfind_raw_sse2(start, end)
    265            };
    266        }
    267        // SAFETY: Building a `One` means it's safe to call both 'sse2' and
    268        // 'avx2' routines. Also, we've checked that our haystack is big
    269        // enough to run on the vector routine. Pointer validity is caller's
    270        // responsibility.
    271        //
    272        // See note in forward routine above for why we don't just call
    273        // `self.avx2.rfind_raw` directly here.
    274        self.rfind_raw_avx2(start, end)
    275    }
    276
    277    /// Counts all occurrences of this byte in the given haystack represented
    278    /// by raw pointers.
    279    ///
    280    /// This routine is useful if you're already using raw pointers and would
    281    /// like to avoid converting back to a slice before executing a search.
    282    ///
    283    /// # Safety
    284    ///
    285    /// * Both `start` and `end` must be valid for reads.
    286    /// * Both `start` and `end` must point to an initialized value.
    287    /// * Both `start` and `end` must point to the same allocated object and
    288    /// must either be in bounds or at most one byte past the end of the
    289    /// allocated object.
    290    /// * Both `start` and `end` must be _derived from_ a pointer to the same
    291    /// object.
    292    /// * The distance between `start` and `end` must not overflow `isize`.
    293    /// * The distance being in bounds must not rely on "wrapping around" the
    294    /// address space.
    295    ///
    296    /// Note that callers may pass a pair of pointers such that `start >= end`.
    297    /// In that case, `0` will always be returned.
    298    #[inline]
    299    pub unsafe fn count_raw(&self, start: *const u8, end: *const u8) -> usize {
    300        if start >= end {
    301            return 0;
    302        }
    303        let len = end.distance(start);
    304        if len < __m256i::BYTES {
    305            return if len < __m128i::BYTES {
    306                // SAFETY: We require the caller to pass valid start/end
    307                // pointers.
    308                generic::count_byte_by_byte(start, end, |b| {
    309                    b == self.sse2.needle1()
    310                })
    311            } else {
    312                // SAFETY: We require the caller to pass valid start/end
    313                // pointers.
    314                self.count_raw_sse2(start, end)
    315            };
    316        }
    317        // SAFETY: Building a `One` means it's safe to call both 'sse2' and
    318        // 'avx2' routines. Also, we've checked that our haystack is big
    319        // enough to run on the vector routine. Pointer validity is caller's
    320        // responsibility.
    321        self.count_raw_avx2(start, end)
    322    }
    323
    324    /// Execute a search using SSE2 vectors and routines.
    325    ///
    326    /// # Safety
    327    ///
    328    /// Same as [`One::find_raw`], except the distance between `start` and
    329    /// `end` must be at least the size of an SSE2 vector (in bytes).
    330    ///
    331    /// (The target feature safety obligation is automatically fulfilled by
    332    /// virtue of being a method on `One`, which can only be constructed
    333    /// when it is safe to call `sse2`/`avx2` routines.)
    334    #[target_feature(enable = "sse2")]
    335    #[inline]
    336    unsafe fn find_raw_sse2(
    337        &self,
    338        start: *const u8,
    339        end: *const u8,
    340    ) -> Option<*const u8> {
    341        self.sse2.find_raw(start, end)
    342    }
    343
    344    /// Execute a search using SSE2 vectors and routines.
    345    ///
    346    /// # Safety
    347    ///
    348    /// Same as [`One::rfind_raw`], except the distance between `start` and
    349    /// `end` must be at least the size of an SSE2 vector (in bytes).
    350    ///
    351    /// (The target feature safety obligation is automatically fulfilled by
    352    /// virtue of being a method on `One`, which can only be constructed
    353    /// when it is safe to call `sse2`/`avx2` routines.)
    354    #[target_feature(enable = "sse2")]
    355    #[inline]
    356    unsafe fn rfind_raw_sse2(
    357        &self,
    358        start: *const u8,
    359        end: *const u8,
    360    ) -> Option<*const u8> {
    361        self.sse2.rfind_raw(start, end)
    362    }
    363
    364    /// Execute a count using SSE2 vectors and routines.
    365    ///
    366    /// # Safety
    367    ///
    368    /// Same as [`One::count_raw`], except the distance between `start` and
    369    /// `end` must be at least the size of an SSE2 vector (in bytes).
    370    ///
    371    /// (The target feature safety obligation is automatically fulfilled by
    372    /// virtue of being a method on `One`, which can only be constructed
    373    /// when it is safe to call `sse2`/`avx2` routines.)
    374    #[target_feature(enable = "sse2")]
    375    #[inline]
    376    unsafe fn count_raw_sse2(
    377        &self,
    378        start: *const u8,
    379        end: *const u8,
    380    ) -> usize {
    381        self.sse2.count_raw(start, end)
    382    }
    383
    384    /// Execute a search using AVX2 vectors and routines.
    385    ///
    386    /// # Safety
    387    ///
    388    /// Same as [`One::find_raw`], except the distance between `start` and
    389    /// `end` must be at least the size of an AVX2 vector (in bytes).
    390    ///
    391    /// (The target feature safety obligation is automatically fulfilled by
    392    /// virtue of being a method on `One`, which can only be constructed
    393    /// when it is safe to call `sse2`/`avx2` routines.)
    394    #[target_feature(enable = "avx2")]
    395    #[inline]
    396    unsafe fn find_raw_avx2(
    397        &self,
    398        start: *const u8,
    399        end: *const u8,
    400    ) -> Option<*const u8> {
    401        self.avx2.find_raw(start, end)
    402    }
    403
    404    /// Execute a search using AVX2 vectors and routines.
    405    ///
    406    /// # Safety
    407    ///
    408    /// Same as [`One::rfind_raw`], except the distance between `start` and
    409    /// `end` must be at least the size of an AVX2 vector (in bytes).
    410    ///
    411    /// (The target feature safety obligation is automatically fulfilled by
    412    /// virtue of being a method on `One`, which can only be constructed
    413    /// when it is safe to call `sse2`/`avx2` routines.)
    414    #[target_feature(enable = "avx2")]
    415    #[inline]
    416    unsafe fn rfind_raw_avx2(
    417        &self,
    418        start: *const u8,
    419        end: *const u8,
    420    ) -> Option<*const u8> {
    421        self.avx2.rfind_raw(start, end)
    422    }
    423
    424    /// Execute a count using AVX2 vectors and routines.
    425    ///
    426    /// # Safety
    427    ///
    428    /// Same as [`One::count_raw`], except the distance between `start` and
    429    /// `end` must be at least the size of an AVX2 vector (in bytes).
    430    ///
    431    /// (The target feature safety obligation is automatically fulfilled by
    432    /// virtue of being a method on `One`, which can only be constructed
    433    /// when it is safe to call `sse2`/`avx2` routines.)
    434    #[target_feature(enable = "avx2")]
    435    #[inline]
    436    unsafe fn count_raw_avx2(
    437        &self,
    438        start: *const u8,
    439        end: *const u8,
    440    ) -> usize {
    441        self.avx2.count_raw(start, end)
    442    }
    443
    444    /// Returns an iterator over all occurrences of the needle byte in the
    445    /// given haystack.
    446    ///
    447    /// The iterator returned implements `DoubleEndedIterator`. This means it
    448    /// can also be used to find occurrences in reverse order.
    449    #[inline]
    450    pub fn iter<'a, 'h>(&'a self, haystack: &'h [u8]) -> OneIter<'a, 'h> {
    451        OneIter { searcher: self, it: generic::Iter::new(haystack) }
    452    }
    453}
    454
    455/// An iterator over all occurrences of a single byte in a haystack.
    456///
    457/// This iterator implements `DoubleEndedIterator`, which means it can also be
    458/// used to find occurrences in reverse order.
    459///
    460/// This iterator is created by the [`One::iter`] method.
    461///
    462/// The lifetime parameters are as follows:
    463///
    464/// * `'a` refers to the lifetime of the underlying [`One`] searcher.
    465/// * `'h` refers to the lifetime of the haystack being searched.
    466#[derive(Clone, Debug)]
    467pub struct OneIter<'a, 'h> {
    468    searcher: &'a One,
    469    it: generic::Iter<'h>,
    470}
    471
    472impl<'a, 'h> Iterator for OneIter<'a, 'h> {
    473    type Item = usize;
    474
    475    #[inline]
    476    fn next(&mut self) -> Option<usize> {
    477        // SAFETY: We rely on the generic iterator to provide valid start
    478        // and end pointers, but we guarantee that any pointer returned by
    479        // 'find_raw' falls within the bounds of the start and end pointer.
    480        unsafe { self.it.next(|s, e| self.searcher.find_raw(s, e)) }
    481    }
    482
    483    #[inline]
    484    fn count(self) -> usize {
    485        self.it.count(|s, e| {
    486            // SAFETY: We rely on our generic iterator to return valid start
    487            // and end pointers.
    488            unsafe { self.searcher.count_raw(s, e) }
    489        })
    490    }
    491
    492    #[inline]
    493    fn size_hint(&self) -> (usize, Option<usize>) {
    494        self.it.size_hint()
    495    }
    496}
    497
    498impl<'a, 'h> DoubleEndedIterator for OneIter<'a, 'h> {
    499    #[inline]
    500    fn next_back(&mut self) -> Option<usize> {
    501        // SAFETY: We rely on the generic iterator to provide valid start
    502        // and end pointers, but we guarantee that any pointer returned by
    503        // 'rfind_raw' falls within the bounds of the start and end pointer.
    504        unsafe { self.it.next_back(|s, e| self.searcher.rfind_raw(s, e)) }
    505    }
    506}
    507
    508impl<'a, 'h> core::iter::FusedIterator for OneIter<'a, 'h> {}
    509
    510/// Finds all occurrences of two bytes in a haystack.
    511///
    512/// That is, this reports matches of one of two possible bytes. For example,
    513/// searching for `a` or `b` in `afoobar` would report matches at offsets `0`,
    514/// `4` and `5`.
    515#[derive(Clone, Copy, Debug)]
    516pub struct Two {
    517    /// Used for haystacks less than 32 bytes.
    518    sse2: generic::Two<__m128i>,
    519    /// Used for haystacks bigger than 32 bytes.
    520    avx2: generic::Two<__m256i>,
    521}
    522
    523impl Two {
    524    /// Create a new searcher that finds occurrences of the needle bytes given.
    525    ///
    526    /// This particular searcher is specialized to use AVX2 vector instructions
    527    /// that typically make it quite fast. (SSE2 is used for haystacks that
    528    /// are too short to accommodate an AVX2 vector.)
    529    ///
    530    /// If either SSE2 or AVX2 is unavailable in the current environment, then
    531    /// `None` is returned.
    532    #[inline]
    533    pub fn new(needle1: u8, needle2: u8) -> Option<Two> {
    534        if Two::is_available() {
    535            // SAFETY: we check that sse2 and avx2 are available above.
    536            unsafe { Some(Two::new_unchecked(needle1, needle2)) }
    537        } else {
    538            None
    539        }
    540    }
    541
    542    /// Create a new finder specific to AVX2 vectors and routines without
    543    /// checking that either SSE2 or AVX2 is available.
    544    ///
    545    /// # Safety
    546    ///
    547    /// Callers must guarantee that it is safe to execute both `sse2` and
    548    /// `avx2` instructions in the current environment.
    549    ///
    550    /// Note that it is a common misconception that if one compiles for an
    551    /// `x86_64` target, then they therefore automatically have access to SSE2
    552    /// instructions. While this is almost always the case, it isn't true in
    553    /// 100% of cases.
    554    #[target_feature(enable = "sse2", enable = "avx2")]
    555    #[inline]
    556    pub unsafe fn new_unchecked(needle1: u8, needle2: u8) -> Two {
    557        Two {
    558            sse2: generic::Two::new(needle1, needle2),
    559            avx2: generic::Two::new(needle1, needle2),
    560        }
    561    }
    562
    563    /// Returns true when this implementation is available in the current
    564    /// environment.
    565    ///
    566    /// When this is true, it is guaranteed that [`Two::new`] will return
    567    /// a `Some` value. Similarly, when it is false, it is guaranteed that
    568    /// `Two::new` will return a `None` value.
    569    ///
    570    /// Note also that for the lifetime of a single program, if this returns
    571    /// true then it will always return true.
    572    #[inline]
    573    pub fn is_available() -> bool {
    574        #[cfg(not(target_feature = "sse2"))]
    575        {
    576            false
    577        }
    578        #[cfg(target_feature = "sse2")]
    579        {
    580            #[cfg(target_feature = "avx2")]
    581            {
    582                true
    583            }
    584            #[cfg(not(target_feature = "avx2"))]
    585            {
    586                #[cfg(feature = "std")]
    587                {
    588                    std::is_x86_feature_detected!("avx2")
    589                }
    590                #[cfg(not(feature = "std"))]
    591                {
    592                    false
    593                }
    594            }
    595        }
    596    }
    597
    598    /// Return the first occurrence of one of the needle bytes in the given
    599    /// haystack. If no such occurrence exists, then `None` is returned.
    600    ///
    601    /// The occurrence is reported as an offset into `haystack`. Its maximum
    602    /// value is `haystack.len() - 1`.
    603    #[inline]
    604    pub fn find(&self, haystack: &[u8]) -> Option<usize> {
    605        // SAFETY: `find_raw` guarantees that if a pointer is returned, it
    606        // falls within the bounds of the start and end pointers.
    607        unsafe {
    608            generic::search_slice_with_raw(haystack, |s, e| {
    609                self.find_raw(s, e)
    610            })
    611        }
    612    }
    613
    614    /// Return the last occurrence of one of the needle bytes in the given
    615    /// haystack. If no such occurrence exists, then `None` is returned.
    616    ///
    617    /// The occurrence is reported as an offset into `haystack`. Its maximum
    618    /// value is `haystack.len() - 1`.
    619    #[inline]
    620    pub fn rfind(&self, haystack: &[u8]) -> Option<usize> {
    621        // SAFETY: `find_raw` guarantees that if a pointer is returned, it
    622        // falls within the bounds of the start and end pointers.
    623        unsafe {
    624            generic::search_slice_with_raw(haystack, |s, e| {
    625                self.rfind_raw(s, e)
    626            })
    627        }
    628    }
    629
    630    /// Like `find`, but accepts and returns raw pointers.
    631    ///
    632    /// When a match is found, the pointer returned is guaranteed to be
    633    /// `>= start` and `< end`.
    634    ///
    635    /// This routine is useful if you're already using raw pointers and would
    636    /// like to avoid converting back to a slice before executing a search.
    637    ///
    638    /// # Safety
    639    ///
    640    /// * Both `start` and `end` must be valid for reads.
    641    /// * Both `start` and `end` must point to an initialized value.
    642    /// * Both `start` and `end` must point to the same allocated object and
    643    /// must either be in bounds or at most one byte past the end of the
    644    /// allocated object.
    645    /// * Both `start` and `end` must be _derived from_ a pointer to the same
    646    /// object.
    647    /// * The distance between `start` and `end` must not overflow `isize`.
    648    /// * The distance being in bounds must not rely on "wrapping around" the
    649    /// address space.
    650    ///
    651    /// Note that callers may pass a pair of pointers such that `start >= end`.
    652    /// In that case, `None` will always be returned.
    653    #[inline]
    654    pub unsafe fn find_raw(
    655        &self,
    656        start: *const u8,
    657        end: *const u8,
    658    ) -> Option<*const u8> {
    659        if start >= end {
    660            return None;
    661        }
    662        let len = end.distance(start);
    663        if len < __m256i::BYTES {
    664            return if len < __m128i::BYTES {
    665                // SAFETY: We require the caller to pass valid start/end
    666                // pointers.
    667                generic::fwd_byte_by_byte(start, end, |b| {
    668                    b == self.sse2.needle1() || b == self.sse2.needle2()
    669                })
    670            } else {
    671                // SAFETY: We require the caller to pass valid start/end
    672                // pointers.
    673                self.find_raw_sse2(start, end)
    674            };
    675        }
    676        // SAFETY: Building a `Two` means it's safe to call both 'sse2' and
    677        // 'avx2' routines. Also, we've checked that our haystack is big
    678        // enough to run on the vector routine. Pointer validity is caller's
    679        // responsibility.
    680        //
    681        // Note that we could call `self.avx2.find_raw` directly here. But that
    682        // means we'd have to annotate this routine with `target_feature`.
    683        // Which is fine, because this routine is `unsafe` anyway and the
    684        // `target_feature` obligation is met by virtue of building a `Two`.
    685        // The real problem is that a routine with a `target_feature`
    686        // annotation generally can't be inlined into caller code unless
    687        // the caller code has the same target feature annotations. Namely,
    688        // the common case (at time of writing) is for calling code to not
    689        // have the `avx2` target feature enabled *at compile time*. Without
    690        // `target_feature` on this routine, it can be inlined which will
    691        // handle some of the short-haystack cases above without touching the
    692        // architecture specific code.
    693        self.find_raw_avx2(start, end)
    694    }
    695
    696    /// Like `rfind`, but accepts and returns raw pointers.
    697    ///
    698    /// When a match is found, the pointer returned is guaranteed to be
    699    /// `>= start` and `< end`.
    700    ///
    701    /// This routine is useful if you're already using raw pointers and would
    702    /// like to avoid converting back to a slice before executing a search.
    703    ///
    704    /// # Safety
    705    ///
    706    /// * Both `start` and `end` must be valid for reads.
    707    /// * Both `start` and `end` must point to an initialized value.
    708    /// * Both `start` and `end` must point to the same allocated object and
    709    /// must either be in bounds or at most one byte past the end of the
    710    /// allocated object.
    711    /// * Both `start` and `end` must be _derived from_ a pointer to the same
    712    /// object.
    713    /// * The distance between `start` and `end` must not overflow `isize`.
    714    /// * The distance being in bounds must not rely on "wrapping around" the
    715    /// address space.
    716    ///
    717    /// Note that callers may pass a pair of pointers such that `start >= end`.
    718    /// In that case, `None` will always be returned.
    719    #[inline]
    720    pub unsafe fn rfind_raw(
    721        &self,
    722        start: *const u8,
    723        end: *const u8,
    724    ) -> Option<*const u8> {
    725        if start >= end {
    726            return None;
    727        }
    728        let len = end.distance(start);
    729        if len < __m256i::BYTES {
    730            return if len < __m128i::BYTES {
    731                // SAFETY: We require the caller to pass valid start/end
    732                // pointers.
    733                generic::rev_byte_by_byte(start, end, |b| {
    734                    b == self.sse2.needle1() || b == self.sse2.needle2()
    735                })
    736            } else {
    737                // SAFETY: We require the caller to pass valid start/end
    738                // pointers.
    739                self.rfind_raw_sse2(start, end)
    740            };
    741        }
    742        // SAFETY: Building a `Two` means it's safe to call both 'sse2' and
    743        // 'avx2' routines. Also, we've checked that our haystack is big
    744        // enough to run on the vector routine. Pointer validity is caller's
    745        // responsibility.
    746        //
    747        // See note in forward routine above for why we don't just call
    748        // `self.avx2.rfind_raw` directly here.
    749        self.rfind_raw_avx2(start, end)
    750    }
    751
    752    /// Execute a search using SSE2 vectors and routines.
    753    ///
    754    /// # Safety
    755    ///
    756    /// Same as [`Two::find_raw`], except the distance between `start` and
    757    /// `end` must be at least the size of an SSE2 vector (in bytes).
    758    ///
    759    /// (The target feature safety obligation is automatically fulfilled by
    760    /// virtue of being a method on `Two`, which can only be constructed
    761    /// when it is safe to call `sse2`/`avx2` routines.)
    762    #[target_feature(enable = "sse2")]
    763    #[inline]
    764    unsafe fn find_raw_sse2(
    765        &self,
    766        start: *const u8,
    767        end: *const u8,
    768    ) -> Option<*const u8> {
    769        self.sse2.find_raw(start, end)
    770    }
    771
    772    /// Execute a search using SSE2 vectors and routines.
    773    ///
    774    /// # Safety
    775    ///
    776    /// Same as [`Two::rfind_raw`], except the distance between `start` and
    777    /// `end` must be at least the size of an SSE2 vector (in bytes).
    778    ///
    779    /// (The target feature safety obligation is automatically fulfilled by
    780    /// virtue of being a method on `Two`, which can only be constructed
    781    /// when it is safe to call `sse2`/`avx2` routines.)
    782    #[target_feature(enable = "sse2")]
    783    #[inline]
    784    unsafe fn rfind_raw_sse2(
    785        &self,
    786        start: *const u8,
    787        end: *const u8,
    788    ) -> Option<*const u8> {
    789        self.sse2.rfind_raw(start, end)
    790    }
    791
    792    /// Execute a search using AVX2 vectors and routines.
    793    ///
    794    /// # Safety
    795    ///
    796    /// Same as [`Two::find_raw`], except the distance between `start` and
    797    /// `end` must be at least the size of an AVX2 vector (in bytes).
    798    ///
    799    /// (The target feature safety obligation is automatically fulfilled by
    800    /// virtue of being a method on `Two`, which can only be constructed
    801    /// when it is safe to call `sse2`/`avx2` routines.)
    802    #[target_feature(enable = "avx2")]
    803    #[inline]
    804    unsafe fn find_raw_avx2(
    805        &self,
    806        start: *const u8,
    807        end: *const u8,
    808    ) -> Option<*const u8> {
    809        self.avx2.find_raw(start, end)
    810    }
    811
    812    /// Execute a search using AVX2 vectors and routines.
    813    ///
    814    /// # Safety
    815    ///
    816    /// Same as [`Two::rfind_raw`], except the distance between `start` and
    817    /// `end` must be at least the size of an AVX2 vector (in bytes).
    818    ///
    819    /// (The target feature safety obligation is automatically fulfilled by
    820    /// virtue of being a method on `Two`, which can only be constructed
    821    /// when it is safe to call `sse2`/`avx2` routines.)
    822    #[target_feature(enable = "avx2")]
    823    #[inline]
    824    unsafe fn rfind_raw_avx2(
    825        &self,
    826        start: *const u8,
    827        end: *const u8,
    828    ) -> Option<*const u8> {
    829        self.avx2.rfind_raw(start, end)
    830    }
    831
    832    /// Returns an iterator over all occurrences of the needle bytes in the
    833    /// given haystack.
    834    ///
    835    /// The iterator returned implements `DoubleEndedIterator`. This means it
    836    /// can also be used to find occurrences in reverse order.
    837    #[inline]
    838    pub fn iter<'a, 'h>(&'a self, haystack: &'h [u8]) -> TwoIter<'a, 'h> {
    839        TwoIter { searcher: self, it: generic::Iter::new(haystack) }
    840    }
    841}
    842
    843/// An iterator over all occurrences of two possible bytes in a haystack.
    844///
    845/// This iterator implements `DoubleEndedIterator`, which means it can also be
    846/// used to find occurrences in reverse order.
    847///
    848/// This iterator is created by the [`Two::iter`] method.
    849///
    850/// The lifetime parameters are as follows:
    851///
    852/// * `'a` refers to the lifetime of the underlying [`Two`] searcher.
    853/// * `'h` refers to the lifetime of the haystack being searched.
    854#[derive(Clone, Debug)]
    855pub struct TwoIter<'a, 'h> {
    856    searcher: &'a Two,
    857    it: generic::Iter<'h>,
    858}
    859
    860impl<'a, 'h> Iterator for TwoIter<'a, 'h> {
    861    type Item = usize;
    862
    863    #[inline]
    864    fn next(&mut self) -> Option<usize> {
    865        // SAFETY: We rely on the generic iterator to provide valid start
    866        // and end pointers, but we guarantee that any pointer returned by
    867        // 'find_raw' falls within the bounds of the start and end pointer.
    868        unsafe { self.it.next(|s, e| self.searcher.find_raw(s, e)) }
    869    }
    870
    871    #[inline]
    872    fn size_hint(&self) -> (usize, Option<usize>) {
    873        self.it.size_hint()
    874    }
    875}
    876
    877impl<'a, 'h> DoubleEndedIterator for TwoIter<'a, 'h> {
    878    #[inline]
    879    fn next_back(&mut self) -> Option<usize> {
    880        // SAFETY: We rely on the generic iterator to provide valid start
    881        // and end pointers, but we guarantee that any pointer returned by
    882        // 'rfind_raw' falls within the bounds of the start and end pointer.
    883        unsafe { self.it.next_back(|s, e| self.searcher.rfind_raw(s, e)) }
    884    }
    885}
    886
    887impl<'a, 'h> core::iter::FusedIterator for TwoIter<'a, 'h> {}
    888
    889/// Finds all occurrences of three bytes in a haystack.
    890///
    891/// That is, this reports matches of one of three possible bytes. For example,
    892/// searching for `a`, `b` or `o` in `afoobar` would report matches at offsets
    893/// `0`, `2`, `3`, `4` and `5`.
    894#[derive(Clone, Copy, Debug)]
    895pub struct Three {
    896    /// Used for haystacks less than 32 bytes.
    897    sse2: generic::Three<__m128i>,
    898    /// Used for haystacks bigger than 32 bytes.
    899    avx2: generic::Three<__m256i>,
    900}
    901
    902impl Three {
    903    /// Create a new searcher that finds occurrences of the needle bytes given.
    904    ///
    905    /// This particular searcher is specialized to use AVX2 vector instructions
    906    /// that typically make it quite fast. (SSE2 is used for haystacks that
    907    /// are too short to accommodate an AVX2 vector.)
    908    ///
    909    /// If either SSE2 or AVX2 is unavailable in the current environment, then
    910    /// `None` is returned.
    911    #[inline]
    912    pub fn new(needle1: u8, needle2: u8, needle3: u8) -> Option<Three> {
    913        if Three::is_available() {
    914            // SAFETY: we check that sse2 and avx2 are available above.
    915            unsafe { Some(Three::new_unchecked(needle1, needle2, needle3)) }
    916        } else {
    917            None
    918        }
    919    }
    920
    921    /// Create a new finder specific to AVX2 vectors and routines without
    922    /// checking that either SSE2 or AVX2 is available.
    923    ///
    924    /// # Safety
    925    ///
    926    /// Callers must guarantee that it is safe to execute both `sse2` and
    927    /// `avx2` instructions in the current environment.
    928    ///
    929    /// Note that it is a common misconception that if one compiles for an
    930    /// `x86_64` target, then they therefore automatically have access to SSE2
    931    /// instructions. While this is almost always the case, it isn't true in
    932    /// 100% of cases.
    933    #[target_feature(enable = "sse2", enable = "avx2")]
    934    #[inline]
    935    pub unsafe fn new_unchecked(
    936        needle1: u8,
    937        needle2: u8,
    938        needle3: u8,
    939    ) -> Three {
    940        Three {
    941            sse2: generic::Three::new(needle1, needle2, needle3),
    942            avx2: generic::Three::new(needle1, needle2, needle3),
    943        }
    944    }
    945
    946    /// Returns true when this implementation is available in the current
    947    /// environment.
    948    ///
    949    /// When this is true, it is guaranteed that [`Three::new`] will return
    950    /// a `Some` value. Similarly, when it is false, it is guaranteed that
    951    /// `Three::new` will return a `None` value.
    952    ///
    953    /// Note also that for the lifetime of a single program, if this returns
    954    /// true then it will always return true.
    955    #[inline]
    956    pub fn is_available() -> bool {
    957        #[cfg(not(target_feature = "sse2"))]
    958        {
    959            false
    960        }
    961        #[cfg(target_feature = "sse2")]
    962        {
    963            #[cfg(target_feature = "avx2")]
    964            {
    965                true
    966            }
    967            #[cfg(not(target_feature = "avx2"))]
    968            {
    969                #[cfg(feature = "std")]
    970                {
    971                    std::is_x86_feature_detected!("avx2")
    972                }
    973                #[cfg(not(feature = "std"))]
    974                {
    975                    false
    976                }
    977            }
    978        }
    979    }
    980
    981    /// Return the first occurrence of one of the needle bytes in the given
    982    /// haystack. If no such occurrence exists, then `None` is returned.
    983    ///
    984    /// The occurrence is reported as an offset into `haystack`. Its maximum
    985    /// value is `haystack.len() - 1`.
    986    #[inline]
    987    pub fn find(&self, haystack: &[u8]) -> Option<usize> {
    988        // SAFETY: `find_raw` guarantees that if a pointer is returned, it
    989        // falls within the bounds of the start and end pointers.
    990        unsafe {
    991            generic::search_slice_with_raw(haystack, |s, e| {
    992                self.find_raw(s, e)
    993            })
    994        }
    995    }
    996
    997    /// Return the last occurrence of one of the needle bytes in the given
    998    /// haystack. If no such occurrence exists, then `None` is returned.
    999    ///
    1000    /// The occurrence is reported as an offset into `haystack`. Its maximum
    1001    /// value is `haystack.len() - 1`.
    1002    #[inline]
    1003    pub fn rfind(&self, haystack: &[u8]) -> Option<usize> {
    1004        // SAFETY: `find_raw` guarantees that if a pointer is returned, it
    1005        // falls within the bounds of the start and end pointers.
    1006        unsafe {
    1007            generic::search_slice_with_raw(haystack, |s, e| {
    1008                self.rfind_raw(s, e)
    1009            })
    1010        }
    1011    }
    1012
    1013    /// Like `find`, but accepts and returns raw pointers.
    1014    ///
    1015    /// When a match is found, the pointer returned is guaranteed to be
    1016    /// `>= start` and `< end`.
    1017    ///
    1018    /// This routine is useful if you're already using raw pointers and would
    1019    /// like to avoid converting back to a slice before executing a search.
    1020    ///
    1021    /// # Safety
    1022    ///
    1023    /// * Both `start` and `end` must be valid for reads.
    1024    /// * Both `start` and `end` must point to an initialized value.
    1025    /// * Both `start` and `end` must point to the same allocated object and
    1026    /// must either be in bounds or at most one byte past the end of the
    1027    /// allocated object.
    1028    /// * Both `start` and `end` must be _derived from_ a pointer to the same
    1029    /// object.
    1030    /// * The distance between `start` and `end` must not overflow `isize`.
    1031    /// * The distance being in bounds must not rely on "wrapping around" the
    1032    /// address space.
    1033    ///
    1034    /// Note that callers may pass a pair of pointers such that `start >= end`.
    1035    /// In that case, `None` will always be returned.
    1036    #[inline]
    1037    pub unsafe fn find_raw(
    1038        &self,
    1039        start: *const u8,
    1040        end: *const u8,
    1041    ) -> Option<*const u8> {
    1042        if start >= end {
    1043            return None;
    1044        }
    1045        let len = end.distance(start);
    1046        if len < __m256i::BYTES {
    1047            return if len < __m128i::BYTES {
    1048                // SAFETY: We require the caller to pass valid start/end
    1049                // pointers.
    1050                generic::fwd_byte_by_byte(start, end, |b| {
    1051                    b == self.sse2.needle1()
    1052                        || b == self.sse2.needle2()
    1053                        || b == self.sse2.needle3()
    1054                })
    1055            } else {
    1056                // SAFETY: We require the caller to pass valid start/end
    1057                // pointers.
    1058                self.find_raw_sse2(start, end)
    1059            };
    1060        }
    1061        // SAFETY: Building a `Three` means it's safe to call both 'sse2' and
    1062        // 'avx2' routines. Also, we've checked that our haystack is big
    1063        // enough to run on the vector routine. Pointer validity is caller's
    1064        // responsibility.
    1065        //
    1066        // Note that we could call `self.avx2.find_raw` directly here. But that
    1067        // means we'd have to annotate this routine with `target_feature`.
    1068        // Which is fine, because this routine is `unsafe` anyway and the
    1069        // `target_feature` obligation is met by virtue of building a `Three`.
    1070        // The real problem is that a routine with a `target_feature`
    1071        // annotation generally can't be inlined into caller code unless
    1072        // the caller code has the same target feature annotations. Namely,
    1073        // the common case (at time of writing) is for calling code to not
    1074        // have the `avx2` target feature enabled *at compile time*. Without
    1075        // `target_feature` on this routine, it can be inlined which will
    1076        // handle some of the short-haystack cases above without touching the
    1077        // architecture specific code.
    1078        self.find_raw_avx2(start, end)
    1079    }
    1080
    1081    /// Like `rfind`, but accepts and returns raw pointers.
    1082    ///
    1083    /// When a match is found, the pointer returned is guaranteed to be
    1084    /// `>= start` and `< end`.
    1085    ///
    1086    /// This routine is useful if you're already using raw pointers and would
    1087    /// like to avoid converting back to a slice before executing a search.
    1088    ///
    1089    /// # Safety
    1090    ///
    1091    /// * Both `start` and `end` must be valid for reads.
    1092    /// * Both `start` and `end` must point to an initialized value.
    1093    /// * Both `start` and `end` must point to the same allocated object and
    1094    /// must either be in bounds or at most one byte past the end of the
    1095    /// allocated object.
    1096    /// * Both `start` and `end` must be _derived from_ a pointer to the same
    1097    /// object.
    1098    /// * The distance between `start` and `end` must not overflow `isize`.
    1099    /// * The distance being in bounds must not rely on "wrapping around" the
    1100    /// address space.
    1101    ///
    1102    /// Note that callers may pass a pair of pointers such that `start >= end`.
    1103    /// In that case, `None` will always be returned.
    1104    #[inline]
    1105    pub unsafe fn rfind_raw(
    1106        &self,
    1107        start: *const u8,
    1108        end: *const u8,
    1109    ) -> Option<*const u8> {
    1110        if start >= end {
    1111            return None;
    1112        }
    1113        let len = end.distance(start);
    1114        if len < __m256i::BYTES {
    1115            return if len < __m128i::BYTES {
    1116                // SAFETY: We require the caller to pass valid start/end
    1117                // pointers.
    1118                generic::rev_byte_by_byte(start, end, |b| {
    1119                    b == self.sse2.needle1()
    1120                        || b == self.sse2.needle2()
    1121                        || b == self.sse2.needle3()
    1122                })
    1123            } else {
    1124                // SAFETY: We require the caller to pass valid start/end
    1125                // pointers.
    1126                self.rfind_raw_sse2(start, end)
    1127            };
    1128        }
    1129        // SAFETY: Building a `Three` means it's safe to call both 'sse2' and
    1130        // 'avx2' routines. Also, we've checked that our haystack is big
    1131        // enough to run on the vector routine. Pointer validity is caller's
    1132        // responsibility.
    1133        //
    1134        // See note in forward routine above for why we don't just call
    1135        // `self.avx2.rfind_raw` directly here.
    1136        self.rfind_raw_avx2(start, end)
    1137    }
    1138
    1139    /// Execute a search using SSE2 vectors and routines.
    1140    ///
    1141    /// # Safety
    1142    ///
    1143    /// Same as [`Three::find_raw`], except the distance between `start` and
    1144    /// `end` must be at least the size of an SSE2 vector (in bytes).
    1145    ///
    1146    /// (The target feature safety obligation is automatically fulfilled by
    1147    /// virtue of being a method on `Three`, which can only be constructed
    1148    /// when it is safe to call `sse2`/`avx2` routines.)
    1149    #[target_feature(enable = "sse2")]
    1150    #[inline]
    1151    unsafe fn find_raw_sse2(
    1152        &self,
    1153        start: *const u8,
    1154        end: *const u8,
    1155    ) -> Option<*const u8> {
    1156        self.sse2.find_raw(start, end)
    1157    }
    1158
    1159    /// Execute a search using SSE2 vectors and routines.
    1160    ///
    1161    /// # Safety
    1162    ///
    1163    /// Same as [`Three::rfind_raw`], except the distance between `start` and
    1164    /// `end` must be at least the size of an SSE2 vector (in bytes).
    1165    ///
    1166    /// (The target feature safety obligation is automatically fulfilled by
    1167    /// virtue of being a method on `Three`, which can only be constructed
    1168    /// when it is safe to call `sse2`/`avx2` routines.)
    1169    #[target_feature(enable = "sse2")]
    1170    #[inline]
    1171    unsafe fn rfind_raw_sse2(
    1172        &self,
    1173        start: *const u8,
    1174        end: *const u8,
    1175    ) -> Option<*const u8> {
    1176        self.sse2.rfind_raw(start, end)
    1177    }
    1178
    1179    /// Execute a search using AVX2 vectors and routines.
    1180    ///
    1181    /// # Safety
    1182    ///
    1183    /// Same as [`Three::find_raw`], except the distance between `start` and
    1184    /// `end` must be at least the size of an AVX2 vector (in bytes).
    1185    ///
    1186    /// (The target feature safety obligation is automatically fulfilled by
    1187    /// virtue of being a method on `Three`, which can only be constructed
    1188    /// when it is safe to call `sse2`/`avx2` routines.)
    1189    #[target_feature(enable = "avx2")]
    1190    #[inline]
    1191    unsafe fn find_raw_avx2(
    1192        &self,
    1193        start: *const u8,
    1194        end: *const u8,
    1195    ) -> Option<*const u8> {
    1196        self.avx2.find_raw(start, end)
    1197    }
    1198
    1199    /// Execute a search using AVX2 vectors and routines.
    1200    ///
    1201    /// # Safety
    1202    ///
    1203    /// Same as [`Three::rfind_raw`], except the distance between `start` and
    1204    /// `end` must be at least the size of an AVX2 vector (in bytes).
    1205    ///
    1206    /// (The target feature safety obligation is automatically fulfilled by
    1207    /// virtue of being a method on `Three`, which can only be constructed
    1208    /// when it is safe to call `sse2`/`avx2` routines.)
    1209    #[target_feature(enable = "avx2")]
    1210    #[inline]
    1211    unsafe fn rfind_raw_avx2(
    1212        &self,
    1213        start: *const u8,
    1214        end: *const u8,
    1215    ) -> Option<*const u8> {
    1216        self.avx2.rfind_raw(start, end)
    1217    }
    1218
    1219    /// Returns an iterator over all occurrences of the needle bytes in the
    1220    /// given haystack.
    1221    ///
    1222    /// The iterator returned implements `DoubleEndedIterator`. This means it
    1223    /// can also be used to find occurrences in reverse order.
    1224    #[inline]
    1225    pub fn iter<'a, 'h>(&'a self, haystack: &'h [u8]) -> ThreeIter<'a, 'h> {
    1226        ThreeIter { searcher: self, it: generic::Iter::new(haystack) }
    1227    }
    1228}
    1229
    1230/// An iterator over all occurrences of three possible bytes in a haystack.
    1231///
    1232/// This iterator implements `DoubleEndedIterator`, which means it can also be
    1233/// used to find occurrences in reverse order.
    1234///
    1235/// This iterator is created by the [`Three::iter`] method.
    1236///
    1237/// The lifetime parameters are as follows:
    1238///
    1239/// * `'a` refers to the lifetime of the underlying [`Three`] searcher.
    1240/// * `'h` refers to the lifetime of the haystack being searched.
    1241#[derive(Clone, Debug)]
    1242pub struct ThreeIter<'a, 'h> {
    1243    searcher: &'a Three,
    1244    it: generic::Iter<'h>,
    1245}
    1246
    1247impl<'a, 'h> Iterator for ThreeIter<'a, 'h> {
    1248    type Item = usize;
    1249
    1250    #[inline]
    1251    fn next(&mut self) -> Option<usize> {
    1252        // SAFETY: We rely on the generic iterator to provide valid start
    1253        // and end pointers, but we guarantee that any pointer returned by
    1254        // 'find_raw' falls within the bounds of the start and end pointer.
    1255        unsafe { self.it.next(|s, e| self.searcher.find_raw(s, e)) }
    1256    }
    1257
    1258    #[inline]
    1259    fn size_hint(&self) -> (usize, Option<usize>) {
    1260        self.it.size_hint()
    1261    }
    1262}
    1263
    1264impl<'a, 'h> DoubleEndedIterator for ThreeIter<'a, 'h> {
    1265    #[inline]
    1266    fn next_back(&mut self) -> Option<usize> {
    1267        // SAFETY: We rely on the generic iterator to provide valid start
    1268        // and end pointers, but we guarantee that any pointer returned by
    1269        // 'rfind_raw' falls within the bounds of the start and end pointer.
    1270        unsafe { self.it.next_back(|s, e| self.searcher.rfind_raw(s, e)) }
    1271    }
    1272}
    1273
    1274impl<'a, 'h> core::iter::FusedIterator for ThreeIter<'a, 'h> {}
    1275
    1276#[cfg(test)]
    1277mod tests {
    1278    use super::*;
    1279
    1280    define_memchr_quickcheck!(super);
    1281
    1282    #[test]
    1283    fn forward_one() {
    1284        crate::tests::memchr::Runner::new(1).forward_iter(
    1285            |haystack, needles| {
    1286                Some(One::new(needles[0])?.iter(haystack).collect())
    1287            },
    1288        )
    1289    }
    1290
    1291    #[test]
    1292    fn reverse_one() {
    1293        crate::tests::memchr::Runner::new(1).reverse_iter(
    1294            |haystack, needles| {
    1295                Some(One::new(needles[0])?.iter(haystack).rev().collect())
    1296            },
    1297        )
    1298    }
    1299
    1300    #[test]
    1301    fn count_one() {
    1302        crate::tests::memchr::Runner::new(1).count_iter(|haystack, needles| {
    1303            Some(One::new(needles[0])?.iter(haystack).count())
    1304        })
    1305    }
    1306
    1307    #[test]
    1308    fn forward_two() {
    1309        crate::tests::memchr::Runner::new(2).forward_iter(
    1310            |haystack, needles| {
    1311                let n1 = needles.get(0).copied()?;
    1312                let n2 = needles.get(1).copied()?;
    1313                Some(Two::new(n1, n2)?.iter(haystack).collect())
    1314            },
    1315        )
    1316    }
    1317
    1318    #[test]
    1319    fn reverse_two() {
    1320        crate::tests::memchr::Runner::new(2).reverse_iter(
    1321            |haystack, needles| {
    1322                let n1 = needles.get(0).copied()?;
    1323                let n2 = needles.get(1).copied()?;
    1324                Some(Two::new(n1, n2)?.iter(haystack).rev().collect())
    1325            },
    1326        )
    1327    }
    1328
    1329    #[test]
    1330    fn forward_three() {
    1331        crate::tests::memchr::Runner::new(3).forward_iter(
    1332            |haystack, needles| {
    1333                let n1 = needles.get(0).copied()?;
    1334                let n2 = needles.get(1).copied()?;
    1335                let n3 = needles.get(2).copied()?;
    1336                Some(Three::new(n1, n2, n3)?.iter(haystack).collect())
    1337            },
    1338        )
    1339    }
    1340
    1341    #[test]
    1342    fn reverse_three() {
    1343        crate::tests::memchr::Runner::new(3).reverse_iter(
    1344            |haystack, needles| {
    1345                let n1 = needles.get(0).copied()?;
    1346                let n2 = needles.get(1).copied()?;
    1347                let n3 = needles.get(2).copied()?;
    1348                Some(Three::new(n1, n2, n3)?.iter(haystack).rev().collect())
    1349            },
    1350        )
    1351    }
    1352}