aboutsummaryrefslogtreecommitdiff
path: root/vendor/memchr/src/arch/all
diff options
context:
space:
mode:
authorValentin Popov <valentin@popov.link>2024-07-19 15:37:58 +0300
committerValentin Popov <valentin@popov.link>2024-07-19 15:37:58 +0300
commita990de90fe41456a23e58bd087d2f107d321f3a1 (patch)
tree15afc392522a9e85dc3332235e311b7d39352ea9 /vendor/memchr/src/arch/all
parent3d48cd3f81164bbfc1a755dc1d4a9a02f98c8ddd (diff)
downloadfparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.tar.xz
fparkan-a990de90fe41456a23e58bd087d2f107d321f3a1.zip
Deleted vendor folder
Diffstat (limited to 'vendor/memchr/src/arch/all')
-rw-r--r--vendor/memchr/src/arch/all/memchr.rs996
-rw-r--r--vendor/memchr/src/arch/all/mod.rs234
-rw-r--r--vendor/memchr/src/arch/all/packedpair/default_rank.rs258
-rw-r--r--vendor/memchr/src/arch/all/packedpair/mod.rs359
-rw-r--r--vendor/memchr/src/arch/all/rabinkarp.rs390
-rw-r--r--vendor/memchr/src/arch/all/shiftor.rs89
-rw-r--r--vendor/memchr/src/arch/all/twoway.rs877
7 files changed, 0 insertions, 3203 deletions
diff --git a/vendor/memchr/src/arch/all/memchr.rs b/vendor/memchr/src/arch/all/memchr.rs
deleted file mode 100644
index 435b1be..0000000
--- a/vendor/memchr/src/arch/all/memchr.rs
+++ /dev/null
@@ -1,996 +0,0 @@
-/*!
-Provides architecture independent implementations of `memchr` and friends.
-
-The main types in this module are [`One`], [`Two`] and [`Three`]. They are for
-searching for one, two or three distinct bytes, respectively, in a haystack.
-Each type also has corresponding double ended iterators. These searchers
-are typically slower than hand-coded vector routines accomplishing the same
-task, but are also typically faster than naive scalar code. These routines
-effectively work by treating a `usize` as a vector of 8-bit lanes, and thus
-achieves some level of data parallelism even without explicit vector support.
-
-The `One` searcher also provides a [`One::count`] routine for efficiently
-counting the number of times a single byte occurs in a haystack. This is
-useful, for example, for counting the number of lines in a haystack. This
-routine exists because it is usually faster, especially with a high match
-count, then using [`One::find`] repeatedly. ([`OneIter`] specializes its
-`Iterator::count` implementation to use this routine.)
-
-Only one, two and three bytes are supported because three bytes is about
-the point where one sees diminishing returns. Beyond this point and it's
-probably (but not necessarily) better to just use a simple `[bool; 256]` array
-or similar. However, it depends mightily on the specific work-load and the
-expected match frequency.
-*/
-
-use crate::{arch::generic::memchr as generic, ext::Pointer};
-
-/// The number of bytes in a single `usize` value.
-const USIZE_BYTES: usize = (usize::BITS / 8) as usize;
-/// The bits that must be zero for a `*const usize` to be properly aligned.
-const USIZE_ALIGN: usize = USIZE_BYTES - 1;
-
-/// Finds all occurrences of a single byte in a haystack.
-#[derive(Clone, Copy, Debug)]
-pub struct One {
- s1: u8,
- v1: usize,
-}
-
-impl One {
- /// The number of bytes we examine per each iteration of our search loop.
- const LOOP_BYTES: usize = 2 * USIZE_BYTES;
-
- /// Create a new searcher that finds occurrences of the byte given.
- #[inline]
- pub fn new(needle: u8) -> One {
- One { s1: needle, v1: splat(needle) }
- }
-
- /// A test-only routine so that we can bundle a bunch of quickcheck
- /// properties into a single macro. Basically, this provides a constructor
- /// that makes it identical to most other memchr implementations, which
- /// have fallible constructors.
- #[cfg(test)]
- pub(crate) fn try_new(needle: u8) -> Option<One> {
- Some(One::new(needle))
- }
-
- /// Return the first occurrence of the needle in the given haystack. If no
- /// such occurrence exists, then `None` is returned.
- ///
- /// The occurrence is reported as an offset into `haystack`. Its maximum
- /// value for a non-empty haystack is `haystack.len() - 1`.
- #[inline]
- pub fn find(&self, haystack: &[u8]) -> Option<usize> {
- // SAFETY: `find_raw` guarantees that if a pointer is returned, it
- // falls within the bounds of the start and end pointers.
- unsafe {
- generic::search_slice_with_raw(haystack, |s, e| {
- self.find_raw(s, e)
- })
- }
- }
-
- /// Return the last occurrence of the needle in the given haystack. If no
- /// such occurrence exists, then `None` is returned.
- ///
- /// The occurrence is reported as an offset into `haystack`. Its maximum
- /// value for a non-empty haystack is `haystack.len() - 1`.
- #[inline]
- pub fn rfind(&self, haystack: &[u8]) -> Option<usize> {
- // SAFETY: `find_raw` guarantees that if a pointer is returned, it
- // falls within the bounds of the start and end pointers.
- unsafe {
- generic::search_slice_with_raw(haystack, |s, e| {
- self.rfind_raw(s, e)
- })
- }
- }
-
- /// Counts all occurrences of this byte in the given haystack.
- #[inline]
- pub fn count(&self, haystack: &[u8]) -> usize {
- // SAFETY: All of our pointers are derived directly from a borrowed
- // slice, which is guaranteed to be valid.
- unsafe {
- let start = haystack.as_ptr();
- let end = start.add(haystack.len());
- self.count_raw(start, end)
- }
- }
-
- /// Like `find`, but accepts and returns raw pointers.
- ///
- /// When a match is found, the pointer returned is guaranteed to be
- /// `>= start` and `< end`.
- ///
- /// This routine is useful if you're already using raw pointers and would
- /// like to avoid converting back to a slice before executing a search.
- ///
- /// # Safety
- ///
- /// * Both `start` and `end` must be valid for reads.
- /// * Both `start` and `end` must point to an initialized value.
- /// * Both `start` and `end` must point to the same allocated object and
- /// must either be in bounds or at most one byte past the end of the
- /// allocated object.
- /// * Both `start` and `end` must be _derived from_ a pointer to the same
- /// object.
- /// * The distance between `start` and `end` must not overflow `isize`.
- /// * The distance being in bounds must not rely on "wrapping around" the
- /// address space.
- ///
- /// Note that callers may pass a pair of pointers such that `start >= end`.
- /// In that case, `None` will always be returned.
- #[inline]
- pub unsafe fn find_raw(
- &self,
- start: *const u8,
- end: *const u8,
- ) -> Option<*const u8> {
- if start >= end {
- return None;
- }
- let confirm = |b| self.confirm(b);
- let len = end.distance(start);
- if len < USIZE_BYTES {
- return generic::fwd_byte_by_byte(start, end, confirm);
- }
-
- // The start of the search may not be aligned to `*const usize`,
- // so we do an unaligned load here.
- let chunk = start.cast::<usize>().read_unaligned();
- if self.has_needle(chunk) {
- return generic::fwd_byte_by_byte(start, end, confirm);
- }
-
- // And now we start our search at a guaranteed aligned position.
- // The first iteration of the loop below will overlap with the the
- // unaligned chunk above in cases where the search starts at an
- // unaligned offset, but that's okay as we're only here if that
- // above didn't find a match.
- let mut cur =
- start.add(USIZE_BYTES - (start.as_usize() & USIZE_ALIGN));
- debug_assert!(cur > start);
- if len <= One::LOOP_BYTES {
- return generic::fwd_byte_by_byte(cur, end, confirm);
- }
- debug_assert!(end.sub(One::LOOP_BYTES) >= start);
- while cur <= end.sub(One::LOOP_BYTES) {
- debug_assert_eq!(0, cur.as_usize() % USIZE_BYTES);
-
- let a = cur.cast::<usize>().read();
- let b = cur.add(USIZE_BYTES).cast::<usize>().read();
- if self.has_needle(a) || self.has_needle(b) {
- break;
- }
- cur = cur.add(One::LOOP_BYTES);
- }
- generic::fwd_byte_by_byte(cur, end, confirm)
- }
-
- /// Like `rfind`, but accepts and returns raw pointers.
- ///
- /// When a match is found, the pointer returned is guaranteed to be
- /// `>= start` and `< end`.
- ///
- /// This routine is useful if you're already using raw pointers and would
- /// like to avoid converting back to a slice before executing a search.
- ///
- /// # Safety
- ///
- /// * Both `start` and `end` must be valid for reads.
- /// * Both `start` and `end` must point to an initialized value.
- /// * Both `start` and `end` must point to the same allocated object and
- /// must either be in bounds or at most one byte past the end of the
- /// allocated object.
- /// * Both `start` and `end` must be _derived from_ a pointer to the same
- /// object.
- /// * The distance between `start` and `end` must not overflow `isize`.
- /// * The distance being in bounds must not rely on "wrapping around" the
- /// address space.
- ///
- /// Note that callers may pass a pair of pointers such that `start >= end`.
- /// In that case, `None` will always be returned.
- #[inline]
- pub unsafe fn rfind_raw(
- &self,
- start: *const u8,
- end: *const u8,
- ) -> Option<*const u8> {
- if start >= end {
- return None;
- }
- let confirm = |b| self.confirm(b);
- let len = end.distance(start);
- if len < USIZE_BYTES {
- return generic::rev_byte_by_byte(start, end, confirm);
- }
-
- let chunk = end.sub(USIZE_BYTES).cast::<usize>().read_unaligned();
- if self.has_needle(chunk) {
- return generic::rev_byte_by_byte(start, end, confirm);
- }
-
- let mut cur = end.sub(end.as_usize() & USIZE_ALIGN);
- debug_assert!(start <= cur && cur <= end);
- if len <= One::LOOP_BYTES {
- return generic::rev_byte_by_byte(start, cur, confirm);
- }
- while cur >= start.add(One::LOOP_BYTES) {
- debug_assert_eq!(0, cur.as_usize() % USIZE_BYTES);
-
- let a = cur.sub(2 * USIZE_BYTES).cast::<usize>().read();
- let b = cur.sub(1 * USIZE_BYTES).cast::<usize>().read();
- if self.has_needle(a) || self.has_needle(b) {
- break;
- }
- cur = cur.sub(One::LOOP_BYTES);
- }
- generic::rev_byte_by_byte(start, cur, confirm)
- }
-
- /// Counts all occurrences of this byte in the given haystack represented
- /// by raw pointers.
- ///
- /// This routine is useful if you're already using raw pointers and would
- /// like to avoid converting back to a slice before executing a search.
- ///
- /// # Safety
- ///
- /// * Both `start` and `end` must be valid for reads.
- /// * Both `start` and `end` must point to an initialized value.
- /// * Both `start` and `end` must point to the same allocated object and
- /// must either be in bounds or at most one byte past the end of the
- /// allocated object.
- /// * Both `start` and `end` must be _derived from_ a pointer to the same
- /// object.
- /// * The distance between `start` and `end` must not overflow `isize`.
- /// * The distance being in bounds must not rely on "wrapping around" the
- /// address space.
- ///
- /// Note that callers may pass a pair of pointers such that `start >= end`.
- /// In that case, `0` will always be returned.
- #[inline]
- pub unsafe fn count_raw(&self, start: *const u8, end: *const u8) -> usize {
- if start >= end {
- return 0;
- }
- // Sadly I couldn't get the SWAR approach to work here, so we just do
- // one byte at a time for now. PRs to improve this are welcome.
- let mut ptr = start;
- let mut count = 0;
- while ptr < end {
- count += (ptr.read() == self.s1) as usize;
- ptr = ptr.offset(1);
- }
- count
- }
-
- /// Returns an iterator over all occurrences of the needle byte in the
- /// given haystack.
- ///
- /// The iterator returned implements `DoubleEndedIterator`. This means it
- /// can also be used to find occurrences in reverse order.
- pub fn iter<'a, 'h>(&'a self, haystack: &'h [u8]) -> OneIter<'a, 'h> {
- OneIter { searcher: self, it: generic::Iter::new(haystack) }
- }
-
- #[inline(always)]
- fn has_needle(&self, chunk: usize) -> bool {
- has_zero_byte(self.v1 ^ chunk)
- }
-
- #[inline(always)]
- fn confirm(&self, haystack_byte: u8) -> bool {
- self.s1 == haystack_byte
- }
-}
-
-/// An iterator over all occurrences of a single byte in a haystack.
-///
-/// This iterator implements `DoubleEndedIterator`, which means it can also be
-/// used to find occurrences in reverse order.
-///
-/// This iterator is created by the [`One::iter`] method.
-///
-/// The lifetime parameters are as follows:
-///
-/// * `'a` refers to the lifetime of the underlying [`One`] searcher.
-/// * `'h` refers to the lifetime of the haystack being searched.
-#[derive(Clone, Debug)]
-pub struct OneIter<'a, 'h> {
- /// The underlying memchr searcher.
- searcher: &'a One,
- /// Generic iterator implementation.
- it: generic::Iter<'h>,
-}
-
-impl<'a, 'h> Iterator for OneIter<'a, 'h> {
- type Item = usize;
-
- #[inline]
- fn next(&mut self) -> Option<usize> {
- // SAFETY: We rely on the generic iterator to provide valid start
- // and end pointers, but we guarantee that any pointer returned by
- // 'find_raw' falls within the bounds of the start and end pointer.
- unsafe { self.it.next(|s, e| self.searcher.find_raw(s, e)) }
- }
-
- #[inline]
- fn count(self) -> usize {
- self.it.count(|s, e| {
- // SAFETY: We rely on our generic iterator to return valid start
- // and end pointers.
- unsafe { self.searcher.count_raw(s, e) }
- })
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.it.size_hint()
- }
-}
-
-impl<'a, 'h> DoubleEndedIterator for OneIter<'a, 'h> {
- #[inline]
- fn next_back(&mut self) -> Option<usize> {
- // SAFETY: We rely on the generic iterator to provide valid start
- // and end pointers, but we guarantee that any pointer returned by
- // 'rfind_raw' falls within the bounds of the start and end pointer.
- unsafe { self.it.next_back(|s, e| self.searcher.rfind_raw(s, e)) }
- }
-}
-
-/// Finds all occurrences of two bytes in a haystack.
-///
-/// That is, this reports matches of one of two possible bytes. For example,
-/// searching for `a` or `b` in `afoobar` would report matches at offsets `0`,
-/// `4` and `5`.
-#[derive(Clone, Copy, Debug)]
-pub struct Two {
- s1: u8,
- s2: u8,
- v1: usize,
- v2: usize,
-}
-
-impl Two {
- /// Create a new searcher that finds occurrences of the two needle bytes
- /// given.
- #[inline]
- pub fn new(needle1: u8, needle2: u8) -> Two {
- Two {
- s1: needle1,
- s2: needle2,
- v1: splat(needle1),
- v2: splat(needle2),
- }
- }
-
- /// A test-only routine so that we can bundle a bunch of quickcheck
- /// properties into a single macro. Basically, this provides a constructor
- /// that makes it identical to most other memchr implementations, which
- /// have fallible constructors.
- #[cfg(test)]
- pub(crate) fn try_new(needle1: u8, needle2: u8) -> Option<Two> {
- Some(Two::new(needle1, needle2))
- }
-
- /// Return the first occurrence of one of the needle bytes in the given
- /// haystack. If no such occurrence exists, then `None` is returned.
- ///
- /// The occurrence is reported as an offset into `haystack`. Its maximum
- /// value for a non-empty haystack is `haystack.len() - 1`.
- #[inline]
- pub fn find(&self, haystack: &[u8]) -> Option<usize> {
- // SAFETY: `find_raw` guarantees that if a pointer is returned, it
- // falls within the bounds of the start and end pointers.
- unsafe {
- generic::search_slice_with_raw(haystack, |s, e| {
- self.find_raw(s, e)
- })
- }
- }
-
- /// Return the last occurrence of one of the needle bytes in the given
- /// haystack. If no such occurrence exists, then `None` is returned.
- ///
- /// The occurrence is reported as an offset into `haystack`. Its maximum
- /// value for a non-empty haystack is `haystack.len() - 1`.
- #[inline]
- pub fn rfind(&self, haystack: &[u8]) -> Option<usize> {
- // SAFETY: `find_raw` guarantees that if a pointer is returned, it
- // falls within the bounds of the start and end pointers.
- unsafe {
- generic::search_slice_with_raw(haystack, |s, e| {
- self.rfind_raw(s, e)
- })
- }
- }
-
- /// Like `find`, but accepts and returns raw pointers.
- ///
- /// When a match is found, the pointer returned is guaranteed to be
- /// `>= start` and `< end`.
- ///
- /// This routine is useful if you're already using raw pointers and would
- /// like to avoid converting back to a slice before executing a search.
- ///
- /// # Safety
- ///
- /// * Both `start` and `end` must be valid for reads.
- /// * Both `start` and `end` must point to an initialized value.
- /// * Both `start` and `end` must point to the same allocated object and
- /// must either be in bounds or at most one byte past the end of the
- /// allocated object.
- /// * Both `start` and `end` must be _derived from_ a pointer to the same
- /// object.
- /// * The distance between `start` and `end` must not overflow `isize`.
- /// * The distance being in bounds must not rely on "wrapping around" the
- /// address space.
- ///
- /// Note that callers may pass a pair of pointers such that `start >= end`.
- /// In that case, `None` will always be returned.
- #[inline]
- pub unsafe fn find_raw(
- &self,
- start: *const u8,
- end: *const u8,
- ) -> Option<*const u8> {
- if start >= end {
- return None;
- }
- let confirm = |b| self.confirm(b);
- let len = end.distance(start);
- if len < USIZE_BYTES {
- return generic::fwd_byte_by_byte(start, end, confirm);
- }
-
- // The start of the search may not be aligned to `*const usize`,
- // so we do an unaligned load here.
- let chunk = start.cast::<usize>().read_unaligned();
- if self.has_needle(chunk) {
- return generic::fwd_byte_by_byte(start, end, confirm);
- }
-
- // And now we start our search at a guaranteed aligned position.
- // The first iteration of the loop below will overlap with the the
- // unaligned chunk above in cases where the search starts at an
- // unaligned offset, but that's okay as we're only here if that
- // above didn't find a match.
- let mut cur =
- start.add(USIZE_BYTES - (start.as_usize() & USIZE_ALIGN));
- debug_assert!(cur > start);
- debug_assert!(end.sub(USIZE_BYTES) >= start);
- while cur <= end.sub(USIZE_BYTES) {
- debug_assert_eq!(0, cur.as_usize() % USIZE_BYTES);
-
- let chunk = cur.cast::<usize>().read();
- if self.has_needle(chunk) {
- break;
- }
- cur = cur.add(USIZE_BYTES);
- }
- generic::fwd_byte_by_byte(cur, end, confirm)
- }
-
- /// Like `rfind`, but accepts and returns raw pointers.
- ///
- /// When a match is found, the pointer returned is guaranteed to be
- /// `>= start` and `< end`.
- ///
- /// This routine is useful if you're already using raw pointers and would
- /// like to avoid converting back to a slice before executing a search.
- ///
- /// # Safety
- ///
- /// * Both `start` and `end` must be valid for reads.
- /// * Both `start` and `end` must point to an initialized value.
- /// * Both `start` and `end` must point to the same allocated object and
- /// must either be in bounds or at most one byte past the end of the
- /// allocated object.
- /// * Both `start` and `end` must be _derived from_ a pointer to the same
- /// object.
- /// * The distance between `start` and `end` must not overflow `isize`.
- /// * The distance being in bounds must not rely on "wrapping around" the
- /// address space.
- ///
- /// Note that callers may pass a pair of pointers such that `start >= end`.
- /// In that case, `None` will always be returned.
- #[inline]
- pub unsafe fn rfind_raw(
- &self,
- start: *const u8,
- end: *const u8,
- ) -> Option<*const u8> {
- if start >= end {
- return None;
- }
- let confirm = |b| self.confirm(b);
- let len = end.distance(start);
- if len < USIZE_BYTES {
- return generic::rev_byte_by_byte(start, end, confirm);
- }
-
- let chunk = end.sub(USIZE_BYTES).cast::<usize>().read_unaligned();
- if self.has_needle(chunk) {
- return generic::rev_byte_by_byte(start, end, confirm);
- }
-
- let mut cur = end.sub(end.as_usize() & USIZE_ALIGN);
- debug_assert!(start <= cur && cur <= end);
- while cur >= start.add(USIZE_BYTES) {
- debug_assert_eq!(0, cur.as_usize() % USIZE_BYTES);
-
- let chunk = cur.sub(USIZE_BYTES).cast::<usize>().read();
- if self.has_needle(chunk) {
- break;
- }
- cur = cur.sub(USIZE_BYTES);
- }
- generic::rev_byte_by_byte(start, cur, confirm)
- }
-
- /// Returns an iterator over all occurrences of one of the needle bytes in
- /// the given haystack.
- ///
- /// The iterator returned implements `DoubleEndedIterator`. This means it
- /// can also be used to find occurrences in reverse order.
- pub fn iter<'a, 'h>(&'a self, haystack: &'h [u8]) -> TwoIter<'a, 'h> {
- TwoIter { searcher: self, it: generic::Iter::new(haystack) }
- }
-
- #[inline(always)]
- fn has_needle(&self, chunk: usize) -> bool {
- has_zero_byte(self.v1 ^ chunk) || has_zero_byte(self.v2 ^ chunk)
- }
-
- #[inline(always)]
- fn confirm(&self, haystack_byte: u8) -> bool {
- self.s1 == haystack_byte || self.s2 == haystack_byte
- }
-}
-
-/// An iterator over all occurrences of two possible bytes in a haystack.
-///
-/// This iterator implements `DoubleEndedIterator`, which means it can also be
-/// used to find occurrences in reverse order.
-///
-/// This iterator is created by the [`Two::iter`] method.
-///
-/// The lifetime parameters are as follows:
-///
-/// * `'a` refers to the lifetime of the underlying [`Two`] searcher.
-/// * `'h` refers to the lifetime of the haystack being searched.
-#[derive(Clone, Debug)]
-pub struct TwoIter<'a, 'h> {
- /// The underlying memchr searcher.
- searcher: &'a Two,
- /// Generic iterator implementation.
- it: generic::Iter<'h>,
-}
-
-impl<'a, 'h> Iterator for TwoIter<'a, 'h> {
- type Item = usize;
-
- #[inline]
- fn next(&mut self) -> Option<usize> {
- // SAFETY: We rely on the generic iterator to provide valid start
- // and end pointers, but we guarantee that any pointer returned by
- // 'find_raw' falls within the bounds of the start and end pointer.
- unsafe { self.it.next(|s, e| self.searcher.find_raw(s, e)) }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.it.size_hint()
- }
-}
-
-impl<'a, 'h> DoubleEndedIterator for TwoIter<'a, 'h> {
- #[inline]
- fn next_back(&mut self) -> Option<usize> {
- // SAFETY: We rely on the generic iterator to provide valid start
- // and end pointers, but we guarantee that any pointer returned by
- // 'rfind_raw' falls within the bounds of the start and end pointer.
- unsafe { self.it.next_back(|s, e| self.searcher.rfind_raw(s, e)) }
- }
-}
-
-/// Finds all occurrences of three bytes in a haystack.
-///
-/// That is, this reports matches of one of three possible bytes. For example,
-/// searching for `a`, `b` or `o` in `afoobar` would report matches at offsets
-/// `0`, `2`, `3`, `4` and `5`.
-#[derive(Clone, Copy, Debug)]
-pub struct Three {
- s1: u8,
- s2: u8,
- s3: u8,
- v1: usize,
- v2: usize,
- v3: usize,
-}
-
-impl Three {
- /// Create a new searcher that finds occurrences of the three needle bytes
- /// given.
- #[inline]
- pub fn new(needle1: u8, needle2: u8, needle3: u8) -> Three {
- Three {
- s1: needle1,
- s2: needle2,
- s3: needle3,
- v1: splat(needle1),
- v2: splat(needle2),
- v3: splat(needle3),
- }
- }
-
- /// A test-only routine so that we can bundle a bunch of quickcheck
- /// properties into a single macro. Basically, this provides a constructor
- /// that makes it identical to most other memchr implementations, which
- /// have fallible constructors.
- #[cfg(test)]
- pub(crate) fn try_new(
- needle1: u8,
- needle2: u8,
- needle3: u8,
- ) -> Option<Three> {
- Some(Three::new(needle1, needle2, needle3))
- }
-
- /// Return the first occurrence of one of the needle bytes in the given
- /// haystack. If no such occurrence exists, then `None` is returned.
- ///
- /// The occurrence is reported as an offset into `haystack`. Its maximum
- /// value for a non-empty haystack is `haystack.len() - 1`.
- #[inline]
- pub fn find(&self, haystack: &[u8]) -> Option<usize> {
- // SAFETY: `find_raw` guarantees that if a pointer is returned, it
- // falls within the bounds of the start and end pointers.
- unsafe {
- generic::search_slice_with_raw(haystack, |s, e| {
- self.find_raw(s, e)
- })
- }
- }
-
- /// Return the last occurrence of one of the needle bytes in the given
- /// haystack. If no such occurrence exists, then `None` is returned.
- ///
- /// The occurrence is reported as an offset into `haystack`. Its maximum
- /// value for a non-empty haystack is `haystack.len() - 1`.
- #[inline]
- pub fn rfind(&self, haystack: &[u8]) -> Option<usize> {
- // SAFETY: `find_raw` guarantees that if a pointer is returned, it
- // falls within the bounds of the start and end pointers.
- unsafe {
- generic::search_slice_with_raw(haystack, |s, e| {
- self.rfind_raw(s, e)
- })
- }
- }
-
- /// Like `find`, but accepts and returns raw pointers.
- ///
- /// When a match is found, the pointer returned is guaranteed to be
- /// `>= start` and `< end`.
- ///
- /// This routine is useful if you're already using raw pointers and would
- /// like to avoid converting back to a slice before executing a search.
- ///
- /// # Safety
- ///
- /// * Both `start` and `end` must be valid for reads.
- /// * Both `start` and `end` must point to an initialized value.
- /// * Both `start` and `end` must point to the same allocated object and
- /// must either be in bounds or at most one byte past the end of the
- /// allocated object.
- /// * Both `start` and `end` must be _derived from_ a pointer to the same
- /// object.
- /// * The distance between `start` and `end` must not overflow `isize`.
- /// * The distance being in bounds must not rely on "wrapping around" the
- /// address space.
- ///
- /// Note that callers may pass a pair of pointers such that `start >= end`.
- /// In that case, `None` will always be returned.
- #[inline]
- pub unsafe fn find_raw(
- &self,
- start: *const u8,
- end: *const u8,
- ) -> Option<*const u8> {
- if start >= end {
- return None;
- }
- let confirm = |b| self.confirm(b);
- let len = end.distance(start);
- if len < USIZE_BYTES {
- return generic::fwd_byte_by_byte(start, end, confirm);
- }
-
- // The start of the search may not be aligned to `*const usize`,
- // so we do an unaligned load here.
- let chunk = start.cast::<usize>().read_unaligned();
- if self.has_needle(chunk) {
- return generic::fwd_byte_by_byte(start, end, confirm);
- }
-
- // And now we start our search at a guaranteed aligned position.
- // The first iteration of the loop below will overlap with the the
- // unaligned chunk above in cases where the search starts at an
- // unaligned offset, but that's okay as we're only here if that
- // above didn't find a match.
- let mut cur =
- start.add(USIZE_BYTES - (start.as_usize() & USIZE_ALIGN));
- debug_assert!(cur > start);
- debug_assert!(end.sub(USIZE_BYTES) >= start);
- while cur <= end.sub(USIZE_BYTES) {
- debug_assert_eq!(0, cur.as_usize() % USIZE_BYTES);
-
- let chunk = cur.cast::<usize>().read();
- if self.has_needle(chunk) {
- break;
- }
- cur = cur.add(USIZE_BYTES);
- }
- generic::fwd_byte_by_byte(cur, end, confirm)
- }
-
- /// Like `rfind`, but accepts and returns raw pointers.
- ///
- /// When a match is found, the pointer returned is guaranteed to be
- /// `>= start` and `< end`.
- ///
- /// This routine is useful if you're already using raw pointers and would
- /// like to avoid converting back to a slice before executing a search.
- ///
- /// # Safety
- ///
- /// * Both `start` and `end` must be valid for reads.
- /// * Both `start` and `end` must point to an initialized value.
- /// * Both `start` and `end` must point to the same allocated object and
- /// must either be in bounds or at most one byte past the end of the
- /// allocated object.
- /// * Both `start` and `end` must be _derived from_ a pointer to the same
- /// object.
- /// * The distance between `start` and `end` must not overflow `isize`.
- /// * The distance being in bounds must not rely on "wrapping around" the
- /// address space.
- ///
- /// Note that callers may pass a pair of pointers such that `start >= end`.
- /// In that case, `None` will always be returned.
- #[inline]
- pub unsafe fn rfind_raw(
- &self,
- start: *const u8,
- end: *const u8,
- ) -> Option<*const u8> {
- if start >= end {
- return None;
- }
- let confirm = |b| self.confirm(b);
- let len = end.distance(start);
- if len < USIZE_BYTES {
- return generic::rev_byte_by_byte(start, end, confirm);
- }
-
- let chunk = end.sub(USIZE_BYTES).cast::<usize>().read_unaligned();
- if self.has_needle(chunk) {
- return generic::rev_byte_by_byte(start, end, confirm);
- }
-
- let mut cur = end.sub(end.as_usize() & USIZE_ALIGN);
- debug_assert!(start <= cur && cur <= end);
- while cur >= start.add(USIZE_BYTES) {
- debug_assert_eq!(0, cur.as_usize() % USIZE_BYTES);
-
- let chunk = cur.sub(USIZE_BYTES).cast::<usize>().read();
- if self.has_needle(chunk) {
- break;
- }
- cur = cur.sub(USIZE_BYTES);
- }
- generic::rev_byte_by_byte(start, cur, confirm)
- }
-
- /// Returns an iterator over all occurrences of one of the needle bytes in
- /// the given haystack.
- ///
- /// The iterator returned implements `DoubleEndedIterator`. This means it
- /// can also be used to find occurrences in reverse order.
- pub fn iter<'a, 'h>(&'a self, haystack: &'h [u8]) -> ThreeIter<'a, 'h> {
- ThreeIter { searcher: self, it: generic::Iter::new(haystack) }
- }
-
- #[inline(always)]
- fn has_needle(&self, chunk: usize) -> bool {
- has_zero_byte(self.v1 ^ chunk)
- || has_zero_byte(self.v2 ^ chunk)
- || has_zero_byte(self.v3 ^ chunk)
- }
-
- #[inline(always)]
- fn confirm(&self, haystack_byte: u8) -> bool {
- self.s1 == haystack_byte
- || self.s2 == haystack_byte
- || self.s3 == haystack_byte
- }
-}
-
-/// An iterator over all occurrences of three possible bytes in a haystack.
-///
-/// This iterator implements `DoubleEndedIterator`, which means it can also be
-/// used to find occurrences in reverse order.
-///
-/// This iterator is created by the [`Three::iter`] method.
-///
-/// The lifetime parameters are as follows:
-///
-/// * `'a` refers to the lifetime of the underlying [`Three`] searcher.
-/// * `'h` refers to the lifetime of the haystack being searched.
-#[derive(Clone, Debug)]
-pub struct ThreeIter<'a, 'h> {
- /// The underlying memchr searcher.
- searcher: &'a Three,
- /// Generic iterator implementation.
- it: generic::Iter<'h>,
-}
-
-impl<'a, 'h> Iterator for ThreeIter<'a, 'h> {
- type Item = usize;
-
- #[inline]
- fn next(&mut self) -> Option<usize> {
- // SAFETY: We rely on the generic iterator to provide valid start
- // and end pointers, but we guarantee that any pointer returned by
- // 'find_raw' falls within the bounds of the start and end pointer.
- unsafe { self.it.next(|s, e| self.searcher.find_raw(s, e)) }
- }
-
- #[inline]
- fn size_hint(&self) -> (usize, Option<usize>) {
- self.it.size_hint()
- }
-}
-
-impl<'a, 'h> DoubleEndedIterator for ThreeIter<'a, 'h> {
- #[inline]
- fn next_back(&mut self) -> Option<usize> {
- // SAFETY: We rely on the generic iterator to provide valid start
- // and end pointers, but we guarantee that any pointer returned by
- // 'rfind_raw' falls within the bounds of the start and end pointer.
- unsafe { self.it.next_back(|s, e| self.searcher.rfind_raw(s, e)) }
- }
-}
-
-/// Return `true` if `x` contains any zero byte.
-///
-/// That is, this routine treats `x` as a register of 8-bit lanes and returns
-/// true when any of those lanes is `0`.
-///
-/// From "Matters Computational" by J. Arndt.
-#[inline(always)]
-fn has_zero_byte(x: usize) -> bool {
- // "The idea is to subtract one from each of the bytes and then look for
- // bytes where the borrow propagated all the way to the most significant
- // bit."
- const LO: usize = splat(0x01);
- const HI: usize = splat(0x80);
-
- (x.wrapping_sub(LO) & !x & HI) != 0
-}
-
-/// Repeat the given byte into a word size number. That is, every 8 bits
-/// is equivalent to the given byte. For example, if `b` is `\x4E` or
-/// `01001110` in binary, then the returned value on a 32-bit system would be:
-/// `01001110_01001110_01001110_01001110`.
-#[inline(always)]
-const fn splat(b: u8) -> usize {
- // TODO: use `usize::from` once it can be used in const context.
- (b as usize) * (usize::MAX / 255)
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- define_memchr_quickcheck!(super, try_new);
-
- #[test]
- fn forward_one() {
- crate::tests::memchr::Runner::new(1).forward_iter(
- |haystack, needles| {
- Some(One::new(needles[0]).iter(haystack).collect())
- },
- )
- }
-
- #[test]
- fn reverse_one() {
- crate::tests::memchr::Runner::new(1).reverse_iter(
- |haystack, needles| {
- Some(One::new(needles[0]).iter(haystack).rev().collect())
- },
- )
- }
-
- #[test]
- fn count_one() {
- crate::tests::memchr::Runner::new(1).count_iter(|haystack, needles| {
- Some(One::new(needles[0]).iter(haystack).count())
- })
- }
-
- #[test]
- fn forward_two() {
- crate::tests::memchr::Runner::new(2).forward_iter(
- |haystack, needles| {
- let n1 = needles.get(0).copied()?;
- let n2 = needles.get(1).copied()?;
- Some(Two::new(n1, n2).iter(haystack).collect())
- },
- )
- }
-
- #[test]
- fn reverse_two() {
- crate::tests::memchr::Runner::new(2).reverse_iter(
- |haystack, needles| {
- let n1 = needles.get(0).copied()?;
- let n2 = needles.get(1).copied()?;
- Some(Two::new(n1, n2).iter(haystack).rev().collect())
- },
- )
- }
-
- #[test]
- fn forward_three() {
- crate::tests::memchr::Runner::new(3).forward_iter(
- |haystack, needles| {
- let n1 = needles.get(0).copied()?;
- let n2 = needles.get(1).copied()?;
- let n3 = needles.get(2).copied()?;
- Some(Three::new(n1, n2, n3).iter(haystack).collect())
- },
- )
- }
-
- #[test]
- fn reverse_three() {
- crate::tests::memchr::Runner::new(3).reverse_iter(
- |haystack, needles| {
- let n1 = needles.get(0).copied()?;
- let n2 = needles.get(1).copied()?;
- let n3 = needles.get(2).copied()?;
- Some(Three::new(n1, n2, n3).iter(haystack).rev().collect())
- },
- )
- }
-
- // This was found by quickcheck in the course of refactoring this crate
- // after memchr 2.5.0.
- #[test]
- fn regression_double_ended_iterator() {
- let finder = One::new(b'a');
- let haystack = "a";
- let mut it = finder.iter(haystack.as_bytes());
- assert_eq!(Some(0), it.next());
- assert_eq!(None, it.next_back());
- }
-
- // This regression test was caught by ripgrep's test suite on i686 when
- // upgrading to memchr 2.6. Namely, something about the \x0B bytes here
- // screws with the SWAR counting approach I was using. This regression test
- // prompted me to remove the SWAR counting approach and just replace it
- // with a byte-at-a-time loop.
- #[test]
- fn regression_count_new_lines() {
- let haystack = "01234567\x0b\n\x0b\n\x0b\n\x0b\nx";
- let count = One::new(b'\n').count(haystack.as_bytes());
- assert_eq!(4, count);
- }
-}
diff --git a/vendor/memchr/src/arch/all/mod.rs b/vendor/memchr/src/arch/all/mod.rs
deleted file mode 100644
index 559cb75..0000000
--- a/vendor/memchr/src/arch/all/mod.rs
+++ /dev/null
@@ -1,234 +0,0 @@
-/*!
-Contains architecture independent routines.
-
-These routines are often used as a "fallback" implementation when the more
-specialized architecture dependent routines are unavailable.
-*/
-
-pub mod memchr;
-pub mod packedpair;
-pub mod rabinkarp;
-#[cfg(feature = "alloc")]
-pub mod shiftor;
-pub mod twoway;
-
-/// Returns true if and only if `needle` is a prefix of `haystack`.
-///
-/// This uses a latency optimized variant of `memcmp` internally which *might*
-/// make this faster for very short strings.
-///
-/// # Inlining
-///
-/// This routine is marked `inline(always)`. If you want to call this function
-/// in a way that is not always inlined, you'll need to wrap a call to it in
-/// another function that is marked as `inline(never)` or just `inline`.
-#[inline(always)]
-pub fn is_prefix(haystack: &[u8], needle: &[u8]) -> bool {
- needle.len() <= haystack.len()
- && is_equal(&haystack[..needle.len()], needle)
-}
-
-/// Returns true if and only if `needle` is a suffix of `haystack`.
-///
-/// This uses a latency optimized variant of `memcmp` internally which *might*
-/// make this faster for very short strings.
-///
-/// # Inlining
-///
-/// This routine is marked `inline(always)`. If you want to call this function
-/// in a way that is not always inlined, you'll need to wrap a call to it in
-/// another function that is marked as `inline(never)` or just `inline`.
-#[inline(always)]
-pub fn is_suffix(haystack: &[u8], needle: &[u8]) -> bool {
- needle.len() <= haystack.len()
- && is_equal(&haystack[haystack.len() - needle.len()..], needle)
-}
-
-/// Compare corresponding bytes in `x` and `y` for equality.
-///
-/// That is, this returns true if and only if `x.len() == y.len()` and
-/// `x[i] == y[i]` for all `0 <= i < x.len()`.
-///
-/// # Inlining
-///
-/// This routine is marked `inline(always)`. If you want to call this function
-/// in a way that is not always inlined, you'll need to wrap a call to it in
-/// another function that is marked as `inline(never)` or just `inline`.
-///
-/// # Motivation
-///
-/// Why not use slice equality instead? Well, slice equality usually results in
-/// a call out to the current platform's `libc` which might not be inlineable
-/// or have other overhead. This routine isn't guaranteed to be a win, but it
-/// might be in some cases.
-#[inline(always)]
-pub fn is_equal(x: &[u8], y: &[u8]) -> bool {
- if x.len() != y.len() {
- return false;
- }
- // SAFETY: Our pointers are derived directly from borrowed slices which
- // uphold all of our safety guarantees except for length. We account for
- // length with the check above.
- unsafe { is_equal_raw(x.as_ptr(), y.as_ptr(), x.len()) }
-}
-
-/// Compare `n` bytes at the given pointers for equality.
-///
-/// This returns true if and only if `*x.add(i) == *y.add(i)` for all
-/// `0 <= i < n`.
-///
-/// # Inlining
-///
-/// This routine is marked `inline(always)`. If you want to call this function
-/// in a way that is not always inlined, you'll need to wrap a call to it in
-/// another function that is marked as `inline(never)` or just `inline`.
-///
-/// # Motivation
-///
-/// Why not use slice equality instead? Well, slice equality usually results in
-/// a call out to the current platform's `libc` which might not be inlineable
-/// or have other overhead. This routine isn't guaranteed to be a win, but it
-/// might be in some cases.
-///
-/// # Safety
-///
-/// * Both `x` and `y` must be valid for reads of up to `n` bytes.
-/// * Both `x` and `y` must point to an initialized value.
-/// * Both `x` and `y` must each point to an allocated object and
-/// must either be in bounds or at most one byte past the end of the
-/// allocated object. `x` and `y` do not need to point to the same allocated
-/// object, but they may.
-/// * Both `x` and `y` must be _derived from_ a pointer to their respective
-/// allocated objects.
-/// * The distance between `x` and `x+n` must not overflow `isize`. Similarly
-/// for `y` and `y+n`.
-/// * The distance being in bounds must not rely on "wrapping around" the
-/// address space.
-#[inline(always)]
-pub unsafe fn is_equal_raw(
- mut x: *const u8,
- mut y: *const u8,
- mut n: usize,
-) -> bool {
- // When we have 4 or more bytes to compare, then proceed in chunks of 4 at
- // a time using unaligned loads.
- //
- // Also, why do 4 byte loads instead of, say, 8 byte loads? The reason is
- // that this particular version of memcmp is likely to be called with tiny
- // needles. That means that if we do 8 byte loads, then a higher proportion
- // of memcmp calls will use the slower variant above. With that said, this
- // is a hypothesis and is only loosely supported by benchmarks. There's
- // likely some improvement that could be made here. The main thing here
- // though is to optimize for latency, not throughput.
-
- // SAFETY: The caller is responsible for ensuring the pointers we get are
- // valid and readable for at least `n` bytes. We also do unaligned loads,
- // so there's no need to ensure we're aligned. (This is justified by this
- // routine being specifically for short strings.)
- while n >= 4 {
- let vx = x.cast::<u32>().read_unaligned();
- let vy = y.cast::<u32>().read_unaligned();
- if vx != vy {
- return false;
- }
- x = x.add(4);
- y = y.add(4);
- n -= 4;
- }
- // If we don't have enough bytes to do 4-byte at a time loads, then
- // do partial loads. Note that I used to have a byte-at-a-time
- // loop here and that turned out to be quite a bit slower for the
- // memmem/pathological/defeat-simple-vector-alphabet benchmark.
- if n >= 2 {
- let vx = x.cast::<u16>().read_unaligned();
- let vy = y.cast::<u16>().read_unaligned();
- if vx != vy {
- return false;
- }
- x = x.add(2);
- y = y.add(2);
- n -= 2;
- }
- if n > 0 {
- if x.read() != y.read() {
- return false;
- }
- }
- true
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- #[test]
- fn equals_different_lengths() {
- assert!(!is_equal(b"", b"a"));
- assert!(!is_equal(b"a", b""));
- assert!(!is_equal(b"ab", b"a"));
- assert!(!is_equal(b"a", b"ab"));
- }
-
- #[test]
- fn equals_mismatch() {
- let one_mismatch = [
- (&b"a"[..], &b"x"[..]),
- (&b"ab"[..], &b"ax"[..]),
- (&b"abc"[..], &b"abx"[..]),
- (&b"abcd"[..], &b"abcx"[..]),
- (&b"abcde"[..], &b"abcdx"[..]),
- (&b"abcdef"[..], &b"abcdex"[..]),
- (&b"abcdefg"[..], &b"abcdefx"[..]),
- (&b"abcdefgh"[..], &b"abcdefgx"[..]),
- (&b"abcdefghi"[..], &b"abcdefghx"[..]),
- (&b"abcdefghij"[..], &b"abcdefghix"[..]),
- (&b"abcdefghijk"[..], &b"abcdefghijx"[..]),
- (&b"abcdefghijkl"[..], &b"abcdefghijkx"[..]),
- (&b"abcdefghijklm"[..], &b"abcdefghijklx"[..]),
- (&b"abcdefghijklmn"[..], &b"abcdefghijklmx"[..]),
- ];
- for (x, y) in one_mismatch {
- assert_eq!(x.len(), y.len(), "lengths should match");
- assert!(!is_equal(x, y));
- assert!(!is_equal(y, x));
- }
- }
-
- #[test]
- fn equals_yes() {
- assert!(is_equal(b"", b""));
- assert!(is_equal(b"a", b"a"));
- assert!(is_equal(b"ab", b"ab"));
- assert!(is_equal(b"abc", b"abc"));
- assert!(is_equal(b"abcd", b"abcd"));
- assert!(is_equal(b"abcde", b"abcde"));
- assert!(is_equal(b"abcdef", b"abcdef"));
- assert!(is_equal(b"abcdefg", b"abcdefg"));
- assert!(is_equal(b"abcdefgh", b"abcdefgh"));
- assert!(is_equal(b"abcdefghi", b"abcdefghi"));
- }
-
- #[test]
- fn prefix() {
- assert!(is_prefix(b"", b""));
- assert!(is_prefix(b"a", b""));
- assert!(is_prefix(b"ab", b""));
- assert!(is_prefix(b"foo", b"foo"));
- assert!(is_prefix(b"foobar", b"foo"));
-
- assert!(!is_prefix(b"foo", b"fob"));
- assert!(!is_prefix(b"foobar", b"fob"));
- }
-
- #[test]
- fn suffix() {
- assert!(is_suffix(b"", b""));
- assert!(is_suffix(b"a", b""));
- assert!(is_suffix(b"ab", b""));
- assert!(is_suffix(b"foo", b"foo"));
- assert!(is_suffix(b"foobar", b"bar"));
-
- assert!(!is_suffix(b"foo", b"goo"));
- assert!(!is_suffix(b"foobar", b"gar"));
- }
-}
diff --git a/vendor/memchr/src/arch/all/packedpair/default_rank.rs b/vendor/memchr/src/arch/all/packedpair/default_rank.rs
deleted file mode 100644
index 6aa3895..0000000
--- a/vendor/memchr/src/arch/all/packedpair/default_rank.rs
+++ /dev/null
@@ -1,258 +0,0 @@
-pub(crate) const RANK: [u8; 256] = [
- 55, // '\x00'
- 52, // '\x01'
- 51, // '\x02'
- 50, // '\x03'
- 49, // '\x04'
- 48, // '\x05'
- 47, // '\x06'
- 46, // '\x07'
- 45, // '\x08'
- 103, // '\t'
- 242, // '\n'
- 66, // '\x0b'
- 67, // '\x0c'
- 229, // '\r'
- 44, // '\x0e'
- 43, // '\x0f'
- 42, // '\x10'
- 41, // '\x11'
- 40, // '\x12'
- 39, // '\x13'
- 38, // '\x14'
- 37, // '\x15'
- 36, // '\x16'
- 35, // '\x17'
- 34, // '\x18'
- 33, // '\x19'
- 56, // '\x1a'
- 32, // '\x1b'
- 31, // '\x1c'
- 30, // '\x1d'
- 29, // '\x1e'
- 28, // '\x1f'
- 255, // ' '
- 148, // '!'
- 164, // '"'
- 149, // '#'
- 136, // '$'
- 160, // '%'
- 155, // '&'
- 173, // "'"
- 221, // '('
- 222, // ')'
- 134, // '*'
- 122, // '+'
- 232, // ','
- 202, // '-'
- 215, // '.'
- 224, // '/'
- 208, // '0'
- 220, // '1'
- 204, // '2'
- 187, // '3'
- 183, // '4'
- 179, // '5'
- 177, // '6'
- 168, // '7'
- 178, // '8'
- 200, // '9'
- 226, // ':'
- 195, // ';'
- 154, // '<'
- 184, // '='
- 174, // '>'
- 126, // '?'
- 120, // '@'
- 191, // 'A'
- 157, // 'B'
- 194, // 'C'
- 170, // 'D'
- 189, // 'E'
- 162, // 'F'
- 161, // 'G'
- 150, // 'H'
- 193, // 'I'
- 142, // 'J'
- 137, // 'K'
- 171, // 'L'
- 176, // 'M'
- 185, // 'N'
- 167, // 'O'
- 186, // 'P'
- 112, // 'Q'
- 175, // 'R'
- 192, // 'S'
- 188, // 'T'
- 156, // 'U'
- 140, // 'V'
- 143, // 'W'
- 123, // 'X'
- 133, // 'Y'
- 128, // 'Z'
- 147, // '['
- 138, // '\\'
- 146, // ']'
- 114, // '^'
- 223, // '_'
- 151, // '`'
- 249, // 'a'
- 216, // 'b'
- 238, // 'c'
- 236, // 'd'
- 253, // 'e'
- 227, // 'f'
- 218, // 'g'
- 230, // 'h'
- 247, // 'i'
- 135, // 'j'
- 180, // 'k'
- 241, // 'l'
- 233, // 'm'
- 246, // 'n'
- 244, // 'o'
- 231, // 'p'
- 139, // 'q'
- 245, // 'r'
- 243, // 's'
- 251, // 't'
- 235, // 'u'
- 201, // 'v'
- 196, // 'w'
- 240, // 'x'
- 214, // 'y'
- 152, // 'z'
- 182, // '{'
- 205, // '|'
- 181, // '}'
- 127, // '~'
- 27, // '\x7f'
- 212, // '\x80'
- 211, // '\x81'
- 210, // '\x82'
- 213, // '\x83'
- 228, // '\x84'
- 197, // '\x85'
- 169, // '\x86'
- 159, // '\x87'
- 131, // '\x88'
- 172, // '\x89'
- 105, // '\x8a'
- 80, // '\x8b'
- 98, // '\x8c'
- 96, // '\x8d'
- 97, // '\x8e'
- 81, // '\x8f'
- 207, // '\x90'
- 145, // '\x91'
- 116, // '\x92'
- 115, // '\x93'
- 144, // '\x94'
- 130, // '\x95'
- 153, // '\x96'
- 121, // '\x97'
- 107, // '\x98'
- 132, // '\x99'
- 109, // '\x9a'
- 110, // '\x9b'
- 124, // '\x9c'
- 111, // '\x9d'
- 82, // '\x9e'
- 108, // '\x9f'
- 118, // '\xa0'
- 141, // '¡'
- 113, // '¢'
- 129, // '£'
- 119, // '¤'
- 125, // '¥'
- 165, // '¦'
- 117, // '§'
- 92, // '¨'
- 106, // '©'
- 83, // 'ª'
- 72, // '«'
- 99, // '¬'
- 93, // '\xad'
- 65, // '®'
- 79, // '¯'
- 166, // '°'
- 237, // '±'
- 163, // '²'
- 199, // '³'
- 190, // '´'
- 225, // 'µ'
- 209, // '¶'
- 203, // '·'
- 198, // '¸'
- 217, // '¹'
- 219, // 'º'
- 206, // '»'
- 234, // '¼'
- 248, // '½'
- 158, // '¾'
- 239, // '¿'
- 255, // 'À'
- 255, // 'Á'
- 255, // 'Â'
- 255, // 'Ã'
- 255, // 'Ä'
- 255, // 'Å'
- 255, // 'Æ'
- 255, // 'Ç'
- 255, // 'È'
- 255, // 'É'
- 255, // 'Ê'
- 255, // 'Ë'
- 255, // 'Ì'
- 255, // 'Í'
- 255, // 'Î'
- 255, // 'Ï'
- 255, // 'Ð'
- 255, // 'Ñ'
- 255, // 'Ò'
- 255, // 'Ó'
- 255, // 'Ô'
- 255, // 'Õ'
- 255, // 'Ö'
- 255, // '×'
- 255, // 'Ø'
- 255, // 'Ù'
- 255, // 'Ú'
- 255, // 'Û'
- 255, // 'Ü'
- 255, // 'Ý'
- 255, // 'Þ'
- 255, // 'ß'
- 255, // 'à'
- 255, // 'á'
- 255, // 'â'
- 255, // 'ã'
- 255, // 'ä'
- 255, // 'å'
- 255, // 'æ'
- 255, // 'ç'
- 255, // 'è'
- 255, // 'é'
- 255, // 'ê'
- 255, // 'ë'
- 255, // 'ì'
- 255, // 'í'
- 255, // 'î'
- 255, // 'ï'
- 255, // 'ð'
- 255, // 'ñ'
- 255, // 'ò'
- 255, // 'ó'
- 255, // 'ô'
- 255, // 'õ'
- 255, // 'ö'
- 255, // '÷'
- 255, // 'ø'
- 255, // 'ù'
- 255, // 'ú'
- 255, // 'û'
- 255, // 'ü'
- 255, // 'ý'
- 255, // 'þ'
- 255, // 'ÿ'
-];
diff --git a/vendor/memchr/src/arch/all/packedpair/mod.rs b/vendor/memchr/src/arch/all/packedpair/mod.rs
deleted file mode 100644
index 148a985..0000000
--- a/vendor/memchr/src/arch/all/packedpair/mod.rs
+++ /dev/null
@@ -1,359 +0,0 @@
-/*!
-Provides an architecture independent implementation of the "packed pair"
-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. Note that
-this module provides an architecture independent version that doesn't do as
-good of a job keeping the search for candidates inside a SIMD hot path. It
-however can be good enough in many circumstances.
-
-[generic SIMD]: http://0x80.pl/articles/simd-strfind.html#first-and-last
-*/
-
-use crate::memchr;
-
-mod default_rank;
-
-/// An architecture independent "packed pair" finder.
-///
-/// This finder picks two bytes that it believes have high predictive power for
-/// indicating an overall match of a needle. At search time, it reports offsets
-/// where the needle could match based on whether the pair of bytes it chose
-/// match.
-///
-/// This is architecture independent because it utilizes `memchr` to find the
-/// occurrence of one of the bytes in the pair, and then checks whether the
-/// second byte matches. If it does, in the case of [`Finder::find_prefilter`],
-/// the location at which the needle could match is returned.
-///
-/// It is generally preferred to use architecture specific routines for a
-/// "packed pair" prefilter, but this can be a useful fallback when the
-/// architecture independent routines are unavailable.
-#[derive(Clone, Copy, Debug)]
-pub struct Finder {
- pair: Pair,
- byte1: u8,
- byte2: u8,
-}
-
-impl Finder {
- /// Create a new prefilter that reports possible locations where the given
- /// needle matches.
- #[inline]
- pub fn new(needle: &[u8]) -> Option<Finder> {
- Finder::with_pair(needle, Pair::new(needle)?)
- }
-
- /// Create a new prefilter using the pair given.
- ///
- /// If the prefilter could not be constructed, then `None` is returned.
- ///
- /// This constructor permits callers to control precisely which pair of
- /// bytes is used as a predicate.
- #[inline]
- pub fn with_pair(needle: &[u8], pair: Pair) -> Option<Finder> {
- let byte1 = needle[usize::from(pair.index1())];
- let byte2 = needle[usize::from(pair.index2())];
- // Currently this can never fail so we could just return a Finder,
- // but it's conceivable this could change.
- Some(Finder { pair, byte1, byte2 })
- }
-
- /// 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.
- #[inline]
- pub fn find_prefilter(&self, haystack: &[u8]) -> Option<usize> {
- let mut i = 0;
- let index1 = usize::from(self.pair.index1());
- let index2 = usize::from(self.pair.index2());
- loop {
- // Use a fast vectorized implementation to skip to the next
- // occurrence of the rarest byte (heuristically chosen) in the
- // needle.
- i += memchr(self.byte1, &haystack[i..])?;
- let found = i;
- i += 1;
-
- // If we can't align our first byte match with the haystack, then a
- // match is impossible.
- let aligned1 = match found.checked_sub(index1) {
- None => continue,
- Some(aligned1) => aligned1,
- };
-
- // Now align the second byte match with the haystack. A mismatch
- // means that a match is impossible.
- let aligned2 = match aligned1.checked_add(index2) {
- None => continue,
- Some(aligned_index2) => aligned_index2,
- };
- if haystack.get(aligned2).map_or(true, |&b| b != self.byte2) {
- continue;
- }
-
- // We've done what we can. There might be a match here.
- return Some(aligned1);
- }
- }
-
- /// 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.pair
- }
-}
-
-/// A pair of byte offsets into a needle to use as a predicate.
-///
-/// This pair is used as a predicate to quickly filter out positions in a
-/// haystack in which a needle cannot match. In some cases, this pair can even
-/// be used in vector algorithms such that the vector algorithm only switches
-/// over to scalar code once this pair has been found.
-///
-/// A pair of offsets can be used in both substring search implementations and
-/// in prefilters. The former will report matches of a needle in a haystack
-/// where as the latter will only report possible matches of a needle.
-///
-/// The offsets are limited each to a maximum of 255 to keep memory usage low.
-/// Moreover, it's rarely advantageous to create a predicate using offsets
-/// greater than 255 anyway.
-///
-/// The only guarantee enforced on the pair of offsets is that they are not
-/// equivalent. It is not necessarily the case that `index1 < index2` for
-/// example. By convention, `index1` corresponds to the byte in the needle
-/// that is believed to be most the predictive. Note also that because of the
-/// requirement that the indices be both valid for the needle used to build
-/// the pair and not equal, it follows that a pair can only be constructed for
-/// needles with length at least 2.
-#[derive(Clone, Copy, Debug)]
-pub struct Pair {
- index1: u8,
- index2: u8,
-}
-
-impl Pair {
- /// Create a new pair of offsets from the given needle.
- ///
- /// If a pair could not be created (for example, if the needle is too
- /// short), then `None` is returned.
- ///
- /// This chooses the pair in the needle that is believed to be as
- /// predictive of an overall match of the needle as possible.
- #[inline]
- pub fn new(needle: &[u8]) -> Option<Pair> {
- Pair::with_ranker(needle, DefaultFrequencyRank)
- }
-
- /// Create a new pair of offsets from the given needle and ranker.
- ///
- /// This permits the caller to choose a background frequency distribution
- /// with which bytes are selected. The idea is to select a pair of bytes
- /// that is believed to strongly predict a match in the haystack. This
- /// usually means selecting bytes that occur rarely in a haystack.
- ///
- /// If a pair could not be created (for example, if the needle is too
- /// short), then `None` is returned.
- #[inline]
- pub fn with_ranker<R: HeuristicFrequencyRank>(
- needle: &[u8],
- ranker: R,
- ) -> Option<Pair> {
- if needle.len() <= 1 {
- return None;
- }
- // Find the rarest two bytes. We make them distinct indices by
- // construction. (The actual byte value may be the same in degenerate
- // cases, but that's OK.)
- let (mut rare1, mut index1) = (needle[0], 0);
- let (mut rare2, mut index2) = (needle[1], 1);
- if ranker.rank(rare2) < ranker.rank(rare1) {
- core::mem::swap(&mut rare1, &mut rare2);
- core::mem::swap(&mut index1, &mut index2);
- }
- let max = usize::from(core::u8::MAX);
- for (i, &b) in needle.iter().enumerate().take(max).skip(2) {
- if ranker.rank(b) < ranker.rank(rare1) {
- rare2 = rare1;
- index2 = index1;
- rare1 = b;
- index1 = u8::try_from(i).unwrap();
- } else if b != rare1 && ranker.rank(b) < ranker.rank(rare2) {
- rare2 = b;
- index2 = u8::try_from(i).unwrap();
- }
- }
- // While not strictly required for how a Pair is normally used, we
- // really don't want these to be equivalent. If they were, it would
- // reduce the effectiveness of candidate searching using these rare
- // bytes by increasing the rate of false positives.
- assert_ne!(index1, index2);
- Some(Pair { index1, index2 })
- }
-
- /// Create a new pair using the offsets given for the needle given.
- ///
- /// This bypasses any sort of heuristic process for choosing the offsets
- /// and permits the caller to choose the offsets themselves.
- ///
- /// Indices are limited to valid `u8` values so that a `Pair` uses less
- /// memory. It is not possible to create a `Pair` with offsets bigger than
- /// `u8::MAX`. It's likely that such a thing is not needed, but if it is,
- /// it's suggested to build your own bespoke algorithm because you're
- /// likely working on a very niche case. (File an issue if this suggestion
- /// does not make sense to you.)
- ///
- /// If a pair could not be created (for example, if the needle is too
- /// short), then `None` is returned.
- #[inline]
- pub fn with_indices(
- needle: &[u8],
- index1: u8,
- index2: u8,
- ) -> Option<Pair> {
- // While not strictly required for how a Pair is normally used, we
- // really don't want these to be equivalent. If they were, it would
- // reduce the effectiveness of candidate searching using these rare
- // bytes by increasing the rate of false positives.
- if index1 == index2 {
- return None;
- }
- // Similarly, invalid indices means the Pair is invalid too.
- if usize::from(index1) >= needle.len() {
- return None;
- }
- if usize::from(index2) >= needle.len() {
- return None;
- }
- Some(Pair { index1, index2 })
- }
-
- /// Returns the first offset of the pair.
- #[inline]
- pub fn index1(&self) -> u8 {
- self.index1
- }
-
- /// Returns the second offset of the pair.
- #[inline]
- pub fn index2(&self) -> u8 {
- self.index2
- }
-}
-
-/// This trait allows the user to customize the heuristic used to determine the
-/// relative frequency of a given byte in the dataset being searched.
-///
-/// The use of this trait can have a dramatic impact on performance depending
-/// on the type of data being searched. The details of why are explained in the
-/// docs of [`crate::memmem::Prefilter`]. To summarize, the core algorithm uses
-/// a prefilter to quickly identify candidate matches that are later verified
-/// more slowly. This prefilter is implemented in terms of trying to find
-/// `rare` bytes at specific offsets that will occur less frequently in the
-/// dataset. While the concept of a `rare` byte is similar for most datasets,
-/// there are some specific datasets (like binary executables) that have
-/// dramatically different byte distributions. For these datasets customizing
-/// the byte frequency heuristic can have a massive impact on performance, and
-/// might even need to be done at runtime.
-///
-/// The default implementation of `HeuristicFrequencyRank` reads from the
-/// static frequency table defined in `src/memmem/byte_frequencies.rs`. This
-/// is optimal for most inputs, so if you are unsure of the impact of using a
-/// custom `HeuristicFrequencyRank` you should probably just use the default.
-///
-/// # Example
-///
-/// ```
-/// use memchr::{
-/// arch::all::packedpair::HeuristicFrequencyRank,
-/// memmem::FinderBuilder,
-/// };
-///
-/// /// A byte-frequency table that is good for scanning binary executables.
-/// struct Binary;
-///
-/// impl HeuristicFrequencyRank for Binary {
-/// fn rank(&self, byte: u8) -> u8 {
-/// const TABLE: [u8; 256] = [
-/// 255, 128, 61, 43, 50, 41, 27, 28, 57, 15, 21, 13, 24, 17, 17,
-/// 89, 58, 16, 11, 7, 14, 23, 7, 6, 24, 9, 6, 5, 9, 4, 7, 16,
-/// 68, 11, 9, 6, 88, 7, 4, 4, 23, 9, 4, 8, 8, 5, 10, 4, 30, 11,
-/// 9, 24, 11, 5, 5, 5, 19, 11, 6, 17, 9, 9, 6, 8,
-/// 48, 58, 11, 14, 53, 40, 9, 9, 254, 35, 3, 6, 52, 23, 6, 6, 27,
-/// 4, 7, 11, 14, 13, 10, 11, 11, 5, 2, 10, 16, 12, 6, 19,
-/// 19, 20, 5, 14, 16, 31, 19, 7, 14, 20, 4, 4, 19, 8, 18, 20, 24,
-/// 1, 25, 19, 58, 29, 10, 5, 15, 20, 2, 2, 9, 4, 3, 5,
-/// 51, 11, 4, 53, 23, 39, 6, 4, 13, 81, 4, 186, 5, 67, 3, 2, 15,
-/// 0, 0, 1, 3, 2, 0, 0, 5, 0, 0, 0, 2, 0, 0, 0,
-/// 12, 2, 1, 1, 3, 1, 1, 1, 6, 1, 2, 1, 3, 1, 1, 2, 9, 1, 1, 0,
-/// 2, 2, 4, 4, 11, 6, 7, 3, 6, 9, 4, 5,
-/// 46, 18, 8, 18, 17, 3, 8, 20, 16, 10, 3, 7, 175, 4, 6, 7, 13,
-/// 3, 7, 3, 3, 1, 3, 3, 10, 3, 1, 5, 2, 0, 1, 2,
-/// 16, 3, 5, 1, 6, 1, 1, 2, 58, 20, 3, 14, 12, 2, 1, 3, 16, 3, 5,
-/// 8, 3, 1, 8, 6, 17, 6, 5, 3, 8, 6, 13, 175,
-/// ];
-/// TABLE[byte as usize]
-/// }
-/// }
-/// // Create a new finder with the custom heuristic.
-/// let finder = FinderBuilder::new()
-/// .build_forward_with_ranker(Binary, b"\x00\x00\xdd\xdd");
-/// // Find needle with custom heuristic.
-/// assert!(finder.find(b"\x00\x00\x00\xdd\xdd").is_some());
-/// ```
-pub trait HeuristicFrequencyRank {
- /// Return the heuristic frequency rank of the given byte. A lower rank
- /// means the byte is believed to occur less frequently in the haystack.
- ///
- /// Some uses of this heuristic may treat arbitrary absolute rank values as
- /// significant. For example, an implementation detail in this crate may
- /// determine that heuristic prefilters are inappropriate if every byte in
- /// the needle has a "high" rank.
- fn rank(&self, byte: u8) -> u8;
-}
-
-/// The default byte frequency heuristic that is good for most haystacks.
-pub(crate) struct DefaultFrequencyRank;
-
-impl HeuristicFrequencyRank for DefaultFrequencyRank {
- fn rank(&self, byte: u8) -> u8 {
- self::default_rank::RANK[usize::from(byte)]
- }
-}
-
-/// This permits passing any implementation of `HeuristicFrequencyRank` as a
-/// borrowed version of itself.
-impl<'a, R> HeuristicFrequencyRank for &'a R
-where
- R: HeuristicFrequencyRank,
-{
- fn rank(&self, byte: u8) -> u8 {
- (**self).rank(byte)
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- #[test]
- fn forward_packedpair() {
- fn find(
- haystack: &[u8],
- needle: &[u8],
- _index1: u8,
- _index2: u8,
- ) -> Option<Option<usize>> {
- // We ignore the index positions requested since it winds up making
- // this test too slow overall.
- let f = Finder::new(needle)?;
- Some(f.find_prefilter(haystack))
- }
- crate::tests::packedpair::Runner::new().fwd(find).run()
- }
-}
diff --git a/vendor/memchr/src/arch/all/rabinkarp.rs b/vendor/memchr/src/arch/all/rabinkarp.rs
deleted file mode 100644
index e0bafba..0000000
--- a/vendor/memchr/src/arch/all/rabinkarp.rs
+++ /dev/null
@@ -1,390 +0,0 @@
-/*!
-An implementation of the [Rabin-Karp substring search algorithm][rabinkarp].
-
-Rabin-Karp works by creating a hash of the needle provided and then computing
-a rolling hash for each needle sized window in the haystack. When the rolling
-hash matches the hash of the needle, a byte-wise comparison is done to check
-if a match exists. The worst case time complexity of Rabin-Karp is `O(m *
-n)` where `m ~ len(needle)` and `n ~ len(haystack)`. Its worst case space
-complexity is constant.
-
-The main utility of Rabin-Karp is that the searcher can be constructed very
-quickly with very little memory. This makes it especially useful when searching
-for small needles in small haystacks, as it might finish its search before a
-beefier algorithm (like Two-Way) even starts.
-
-[rabinkarp]: https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
-*/
-
-/*
-(This was the comment I wrote for this module originally when it was not
-exposed. The comment still looks useful, but it's a bit in the weeds, so it's
-not public itself.)
-
-This module implements the classical Rabin-Karp substring search algorithm,
-with no extra frills. While its use would seem to break our time complexity
-guarantee of O(m+n) (RK's time complexity is O(mn)), we are careful to only
-ever use RK on a constant subset of haystacks. The main point here is that
-RK has good latency properties for small needles/haystacks. It's very quick
-to compute a needle hash and zip through the haystack when compared to
-initializing Two-Way, for example. And this is especially useful for cases
-where the haystack is just too short for vector instructions to do much good.
-
-The hashing function used here is the same one recommended by ESMAJ.
-
-Another choice instead of Rabin-Karp would be Shift-Or. But its latency
-isn't quite as good since its preprocessing time is a bit more expensive
-(both in practice and in theory). However, perhaps Shift-Or has a place
-somewhere else for short patterns. I think the main problem is that it
-requires space proportional to the alphabet and the needle. If we, for
-example, supported needles up to length 16, then the total table size would be
-len(alphabet)*size_of::<u16>()==512 bytes. Which isn't exactly small, and it's
-probably bad to put that on the stack. So ideally, we'd throw it on the heap,
-but we'd really like to write as much code without using alloc/std as possible.
-But maybe it's worth the special casing. It's a TODO to benchmark.
-
-Wikipedia has a decent explanation, if a bit heavy on the theory:
-https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm
-
-But ESMAJ provides something a bit more concrete:
-http://www-igm.univ-mlv.fr/~lecroq/string/node5.html
-
-Finally, aho-corasick uses Rabin-Karp for multiple pattern match in some cases:
-https://github.com/BurntSushi/aho-corasick/blob/3852632f10587db0ff72ef29e88d58bf305a0946/src/packed/rabinkarp.rs
-*/
-
-use crate::ext::Pointer;
-
-/// A forward substring searcher using the Rabin-Karp algorithm.
-///
-/// Note that, as a lower level API, a `Finder` does not have access to the
-/// needle it was constructed with. For this reason, executing a search
-/// with a `Finder` requires passing both the needle and the haystack,
-/// where the needle is exactly equivalent to the one given to the `Finder`
-/// at construction time. This design was chosen so that callers can have
-/// more precise control over where and how many times a needle is stored.
-/// For example, in cases where Rabin-Karp is just one of several possible
-/// substring search algorithms.
-#[derive(Clone, Debug)]
-pub struct Finder {
- /// The actual hash.
- hash: Hash,
- /// The factor needed to multiply a byte by in order to subtract it from
- /// the hash. It is defined to be 2^(n-1) (using wrapping exponentiation),
- /// where n is the length of the needle. This is how we "remove" a byte
- /// from the hash once the hash window rolls past it.
- hash_2pow: u32,
-}
-
-impl Finder {
- /// Create a new Rabin-Karp forward searcher for the given `needle`.
- ///
- /// The needle may be empty. The empty needle matches at every byte offset.
- ///
- /// Note that callers must pass the same needle to all search calls using
- /// this `Finder`.
- #[inline]
- pub fn new(needle: &[u8]) -> Finder {
- let mut s = Finder { hash: Hash::new(), hash_2pow: 1 };
- let first_byte = match needle.get(0) {
- None => return s,
- Some(&first_byte) => first_byte,
- };
- s.hash.add(first_byte);
- for b in needle.iter().copied().skip(1) {
- s.hash.add(b);
- s.hash_2pow = s.hash_2pow.wrapping_shl(1);
- }
- s
- }
-
- /// Return the first occurrence of the `needle` in the `haystack`
- /// given. If no such occurrence exists, then `None` is returned.
- ///
- /// The `needle` provided must match the needle given to this finder at
- /// construction time.
- ///
- /// The maximum value this can return is `haystack.len()`, which can only
- /// occur when the needle and haystack both have length zero. Otherwise,
- /// for non-empty haystacks, the maximum value is `haystack.len() - 1`.
- #[inline]
- pub fn find(&self, haystack: &[u8], needle: &[u8]) -> Option<usize> {
- unsafe {
- let hstart = haystack.as_ptr();
- let hend = hstart.add(haystack.len());
- let nstart = needle.as_ptr();
- let nend = nstart.add(needle.len());
- let found = self.find_raw(hstart, hend, nstart, nend)?;
- Some(found.distance(hstart))
- }
- }
-
- /// Like `find`, but accepts and returns raw pointers.
- ///
- /// When a match is found, the pointer returned is guaranteed to be
- /// `>= start` and `<= end`. The pointer returned is only ever equivalent
- /// to `end` when both the needle and haystack are empty. (That is, the
- /// empty string matches the empty string.)
- ///
- /// This routine is useful if you're already using raw pointers and would
- /// like to avoid converting back to a slice before executing a search.
- ///
- /// # Safety
- ///
- /// Note that `start` and `end` below refer to both pairs of pointers given
- /// to this routine. That is, the conditions apply to both `hstart`/`hend`
- /// and `nstart`/`nend`.
- ///
- /// * Both `start` and `end` must be valid for reads.
- /// * Both `start` and `end` must point to an initialized value.
- /// * Both `start` and `end` must point to the same allocated object and
- /// must either be in bounds or at most one byte past the end of the
- /// allocated object.
- /// * Both `start` and `end` must be _derived from_ a pointer to the same
- /// object.
- /// * The distance between `start` and `end` must not overflow `isize`.
- /// * The distance being in bounds must not rely on "wrapping around" the
- /// address space.
- /// * It must be the case that `start <= end`.
- #[inline]
- pub unsafe fn find_raw(
- &self,
- hstart: *const u8,
- hend: *const u8,
- nstart: *const u8,
- nend: *const u8,
- ) -> Option<*const u8> {
- let hlen = hend.distance(hstart);
- let nlen = nend.distance(nstart);
- if nlen > hlen {
- return None;
- }
- let mut cur = hstart;
- let end = hend.sub(nlen);
- let mut hash = Hash::forward(cur, cur.add(nlen));
- loop {
- if self.hash == hash && is_equal_raw(cur, nstart, nlen) {
- return Some(cur);
- }
- if cur >= end {
- return None;
- }
- hash.roll(self, cur.read(), cur.add(nlen).read());
- cur = cur.add(1);
- }
- }
-}
-
-/// A reverse substring searcher using the Rabin-Karp algorithm.
-#[derive(Clone, Debug)]
-pub struct FinderRev(Finder);
-
-impl FinderRev {
- /// Create a new Rabin-Karp reverse searcher for the given `needle`.
- #[inline]
- pub fn new(needle: &[u8]) -> FinderRev {
- let mut s = FinderRev(Finder { hash: Hash::new(), hash_2pow: 1 });
- let last_byte = match needle.last() {
- None => return s,
- Some(&last_byte) => last_byte,
- };
- s.0.hash.add(last_byte);
- for b in needle.iter().rev().copied().skip(1) {
- s.0.hash.add(b);
- s.0.hash_2pow = s.0.hash_2pow.wrapping_shl(1);
- }
- s
- }
-
- /// Return the last occurrence of the `needle` in the `haystack`
- /// given. If no such occurrence exists, then `None` is returned.
- ///
- /// The `needle` provided must match the needle given to this finder at
- /// construction time.
- ///
- /// The maximum value this can return is `haystack.len()`, which can only
- /// occur when the needle and haystack both have length zero. Otherwise,
- /// for non-empty haystacks, the maximum value is `haystack.len() - 1`.
- #[inline]
- pub fn rfind(&self, haystack: &[u8], needle: &[u8]) -> Option<usize> {
- unsafe {
- let hstart = haystack.as_ptr();
- let hend = hstart.add(haystack.len());
- let nstart = needle.as_ptr();
- let nend = nstart.add(needle.len());
- let found = self.rfind_raw(hstart, hend, nstart, nend)?;
- Some(found.distance(hstart))
- }
- }
-
- /// Like `rfind`, but accepts and returns raw pointers.
- ///
- /// When a match is found, the pointer returned is guaranteed to be
- /// `>= start` and `<= end`. The pointer returned is only ever equivalent
- /// to `end` when both the needle and haystack are empty. (That is, the
- /// empty string matches the empty string.)
- ///
- /// This routine is useful if you're already using raw pointers and would
- /// like to avoid converting back to a slice before executing a search.
- ///
- /// # Safety
- ///
- /// Note that `start` and `end` below refer to both pairs of pointers given
- /// to this routine. That is, the conditions apply to both `hstart`/`hend`
- /// and `nstart`/`nend`.
- ///
- /// * Both `start` and `end` must be valid for reads.
- /// * Both `start` and `end` must point to an initialized value.
- /// * Both `start` and `end` must point to the same allocated object and
- /// must either be in bounds or at most one byte past the end of the
- /// allocated object.
- /// * Both `start` and `end` must be _derived from_ a pointer to the same
- /// object.
- /// * The distance between `start` and `end` must not overflow `isize`.
- /// * The distance being in bounds must not rely on "wrapping around" the
- /// address space.
- /// * It must be the case that `start <= end`.
- #[inline]
- pub unsafe fn rfind_raw(
- &self,
- hstart: *const u8,
- hend: *const u8,
- nstart: *const u8,
- nend: *const u8,
- ) -> Option<*const u8> {
- let hlen = hend.distance(hstart);
- let nlen = nend.distance(nstart);
- if nlen > hlen {
- return None;
- }
- let mut cur = hend.sub(nlen);
- let start = hstart;
- let mut hash = Hash::reverse(cur, cur.add(nlen));
- loop {
- if self.0.hash == hash && is_equal_raw(cur, nstart, nlen) {
- return Some(cur);
- }
- if cur <= start {
- return None;
- }
- cur = cur.sub(1);
- hash.roll(&self.0, cur.add(nlen).read(), cur.read());
- }
- }
-}
-
-/// Whether RK is believed to be very fast for the given needle/haystack.
-#[inline]
-pub(crate) fn is_fast(haystack: &[u8], _needle: &[u8]) -> bool {
- haystack.len() < 16
-}
-
-/// A Rabin-Karp hash. This might represent the hash of a needle, or the hash
-/// of a rolling window in the haystack.
-#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
-struct Hash(u32);
-
-impl Hash {
- /// Create a new hash that represents the empty string.
- #[inline(always)]
- fn new() -> Hash {
- Hash(0)
- }
-
- /// Create a new hash from the bytes given for use in forward searches.
- ///
- /// # Safety
- ///
- /// The given pointers must be valid to read from within their range.
- #[inline(always)]
- unsafe fn forward(mut start: *const u8, end: *const u8) -> Hash {
- let mut hash = Hash::new();
- while start < end {
- hash.add(start.read());
- start = start.add(1);
- }
- hash
- }
-
- /// Create a new hash from the bytes given for use in reverse searches.
- ///
- /// # Safety
- ///
- /// The given pointers must be valid to read from within their range.
- #[inline(always)]
- unsafe fn reverse(start: *const u8, mut end: *const u8) -> Hash {
- let mut hash = Hash::new();
- while start < end {
- end = end.sub(1);
- hash.add(end.read());
- }
- hash
- }
-
- /// Add 'new' and remove 'old' from this hash. The given needle hash should
- /// correspond to the hash computed for the needle being searched for.
- ///
- /// This is meant to be used when the rolling window of the haystack is
- /// advanced.
- #[inline(always)]
- fn roll(&mut self, finder: &Finder, old: u8, new: u8) {
- self.del(finder, old);
- self.add(new);
- }
-
- /// Add a byte to this hash.
- #[inline(always)]
- fn add(&mut self, byte: u8) {
- self.0 = self.0.wrapping_shl(1).wrapping_add(u32::from(byte));
- }
-
- /// Remove a byte from this hash. The given needle hash should correspond
- /// to the hash computed for the needle being searched for.
- #[inline(always)]
- fn del(&mut self, finder: &Finder, byte: u8) {
- let factor = finder.hash_2pow;
- self.0 = self.0.wrapping_sub(u32::from(byte).wrapping_mul(factor));
- }
-}
-
-/// Returns true when `x[i] == y[i]` for all `0 <= i < n`.
-///
-/// We forcefully don't inline this to hint at the compiler that it is unlikely
-/// to be called. This causes the inner rabinkarp loop above to be a bit
-/// tighter and leads to some performance improvement. See the
-/// memmem/krate/prebuilt/sliceslice-words/words benchmark.
-///
-/// # Safety
-///
-/// Same as `crate::arch::all::is_equal_raw`.
-#[cold]
-#[inline(never)]
-unsafe fn is_equal_raw(x: *const u8, y: *const u8, n: usize) -> bool {
- crate::arch::all::is_equal_raw(x, y, n)
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- define_substring_forward_quickcheck!(|h, n| Some(
- Finder::new(n).find(h, n)
- ));
- define_substring_reverse_quickcheck!(|h, n| Some(
- FinderRev::new(n).rfind(h, n)
- ));
-
- #[test]
- fn forward() {
- crate::tests::substring::Runner::new()
- .fwd(|h, n| Some(Finder::new(n).find(h, n)))
- .run();
- }
-
- #[test]
- fn reverse() {
- crate::tests::substring::Runner::new()
- .rev(|h, n| Some(FinderRev::new(n).rfind(h, n)))
- .run();
- }
-}
diff --git a/vendor/memchr/src/arch/all/shiftor.rs b/vendor/memchr/src/arch/all/shiftor.rs
deleted file mode 100644
index b690564..0000000
--- a/vendor/memchr/src/arch/all/shiftor.rs
+++ /dev/null
@@ -1,89 +0,0 @@
-/*!
-An implementation of the [Shift-Or substring search algorithm][shiftor].
-
-[shiftor]: https://en.wikipedia.org/wiki/Bitap_algorithm
-*/
-
-use alloc::boxed::Box;
-
-/// The type of our mask.
-///
-/// While we don't expose anyway to configure this in the public API, if one
-/// really needs less memory usage or support for longer needles, then it is
-/// suggested to copy the code from this module and modify it to fit your
-/// needs. The code below is written to be correct regardless of whether Mask
-/// is a u8, u16, u32, u64 or u128.
-type Mask = u16;
-
-/// A forward substring searcher using the Shift-Or algorithm.
-#[derive(Debug)]
-pub struct Finder {
- masks: Box<[Mask; 256]>,
- needle_len: usize,
-}
-
-impl Finder {
- const MAX_NEEDLE_LEN: usize = (Mask::BITS - 1) as usize;
-
- /// Create a new Shift-Or forward searcher for the given `needle`.
- ///
- /// The needle may be empty. The empty needle matches at every byte offset.
- #[inline]
- pub fn new(needle: &[u8]) -> Option<Finder> {
- let needle_len = needle.len();
- if needle_len > Finder::MAX_NEEDLE_LEN {
- // A match is found when bit 7 is set in 'result' in the search
- // routine below. So our needle can't be bigger than 7. We could
- // permit bigger needles by using u16, u32 or u64 for our mask
- // entries. But this is all we need for this example.
- return None;
- }
- let mut searcher = Finder { masks: Box::from([!0; 256]), needle_len };
- for (i, &byte) in needle.iter().enumerate() {
- searcher.masks[usize::from(byte)] &= !(1 << i);
- }
- Some(searcher)
- }
-
- /// Return the first occurrence of the needle given to `Finder::new` in
- /// the `haystack` given. If no such occurrence exists, then `None` is
- /// returned.
- ///
- /// Unlike most other substring search implementations in this crate, this
- /// finder does not require passing the needle at search time. A match can
- /// be determined without the needle at all since the required information
- /// is already encoded into this finder at construction time.
- ///
- /// The maximum value this can return is `haystack.len()`, which can only
- /// occur when the needle and haystack both have length zero. Otherwise,
- /// for non-empty haystacks, the maximum value is `haystack.len() - 1`.
- #[inline]
- pub fn find(&self, haystack: &[u8]) -> Option<usize> {
- if self.needle_len == 0 {
- return Some(0);
- }
- let mut result = !1;
- for (i, &byte) in haystack.iter().enumerate() {
- result |= self.masks[usize::from(byte)];
- result <<= 1;
- if result & (1 << self.needle_len) == 0 {
- return Some(i + 1 - self.needle_len);
- }
- }
- None
- }
-}
-
-#[cfg(test)]
-mod tests {
- use super::*;
-
- define_substring_forward_quickcheck!(|h, n| Some(Finder::new(n)?.find(h)));
-
- #[test]
- fn forward() {
- crate::tests::substring::Runner::new()
- .fwd(|h, n| Some(Finder::new(n)?.find(h)))
- .run();
- }
-}
diff --git a/vendor/memchr/src/arch/all/twoway.rs b/vendor/memchr/src/arch/all/twoway.rs
deleted file mode 100644
index 0df3b4a..0000000
--- a/vendor/memchr/src/arch/all/twoway.rs
+++ /dev/null
@@ -1,877 +0,0 @@
-/*!
-An implementation of the [Two-Way substring search algorithm][two-way].
-
-[`Finder`] can be built for forward searches, while [`FinderRev`] can be built
-for reverse searches.
-
-Two-Way makes for a nice general purpose substring search algorithm because of
-its time and space complexity properties. It also performs well in practice.
-Namely, with `m = len(needle)` and `n = len(haystack)`, Two-Way takes `O(m)`
-time to create a finder, `O(1)` space and `O(n)` search time. In other words,
-the preprocessing step is quick, doesn't require any heap memory and the worst
-case search time is guaranteed to be linear in the haystack regardless of the
-size of the needle.
-
-While vector algorithms will usually beat Two-Way handedly, vector algorithms
-also usually have pathological or edge cases that are better handled by Two-Way.
-Moreover, not all targets support vector algorithms or implementations for them
-simply may not exist yet.
-
-Two-Way can be found in the `memmem` implementations in at least [GNU libc] and
-[musl].
-
-[two-way]: https://en.wikipedia.org/wiki/Two-way_string-matching_algorithm
-[GNU libc]: https://www.gnu.org/software/libc/
-[musl]: https://www.musl-libc.org/
-*/
-
-use core::cmp;
-
-use crate::{
- arch::all::{is_prefix, is_suffix},
- memmem::Pre,
-};
-
-/// A forward substring searcher that uses the Two-Way algorithm.
-#[derive(Clone, Copy, Debug)]
-pub struct Finder(TwoWay);
-
-/// A reverse substring searcher that uses the Two-Way algorithm.
-#[derive(Clone, Copy, Debug)]
-pub struct FinderRev(TwoWay);
-
-/// An implementation of the TwoWay substring search algorithm.
-///
-/// This searcher supports forward and reverse search, although not
-/// simultaneously. It runs in `O(n + m)` time and `O(1)` space, where
-/// `n ~ len(needle)` and `m ~ len(haystack)`.
-///
-/// The implementation here roughly matches that which was developed by
-/// Crochemore and Perrin in their 1991 paper "Two-way string-matching." The
-/// changes in this implementation are 1) the use of zero-based indices, 2) a
-/// heuristic skip table based on the last byte (borrowed from Rust's standard
-/// library) and 3) the addition of heuristics for a fast skip loop. For (3),
-/// callers can pass any kind of prefilter they want, but usually it's one
-/// based on a heuristic that uses an approximate background frequency of bytes
-/// to choose rare bytes to quickly look for candidate match positions. Note
-/// though that currently, this prefilter functionality is not exposed directly
-/// in the public API. (File an issue if you want it and provide a use case
-/// please.)
-///
-/// The heuristic for fast skipping is automatically shut off if it's
-/// detected to be ineffective at search time. Generally, this only occurs in
-/// pathological cases. But this is generally necessary in order to preserve
-/// a `O(n + m)` time bound.
-///
-/// The code below is fairly complex and not obviously correct at all. It's
-/// likely necessary to read the Two-Way paper cited above in order to fully
-/// grok this code. The essence of it is:
-///
-/// 1. Do something to detect a "critical" position in the needle.
-/// 2. For the current position in the haystack, look if `needle[critical..]`
-/// matches at that position.
-/// 3. If so, look if `needle[..critical]` matches.
-/// 4. If a mismatch occurs, shift the search by some amount based on the
-/// critical position and a pre-computed shift.
-///
-/// This type is wrapped in the forward and reverse finders that expose
-/// consistent forward or reverse APIs.
-#[derive(Clone, Copy, Debug)]
-struct TwoWay {
- /// A small bitset used as a quick prefilter (in addition to any prefilter
- /// given by the caller). Namely, a bit `i` is set if and only if `b%64==i`
- /// for any `b == needle[i]`.
- ///
- /// When used as a prefilter, if the last byte at the current candidate
- /// position is NOT in this set, then we can skip that entire candidate
- /// position (the length of the needle). This is essentially the shift
- /// trick found in Boyer-Moore, but only applied to bytes that don't appear
- /// in the needle.
- ///
- /// N.B. This trick was inspired by something similar in std's
- /// implementation of Two-Way.
- byteset: ApproximateByteSet,
- /// A critical position in needle. Specifically, this position corresponds
- /// to beginning of either the minimal or maximal suffix in needle. (N.B.
- /// See SuffixType below for why "minimal" isn't quite the correct word
- /// here.)
- ///
- /// This is the position at which every search begins. Namely, search
- /// starts by scanning text to the right of this position, and only if
- /// there's a match does the text to the left of this position get scanned.
- critical_pos: usize,
- /// The amount we shift by in the Two-Way search algorithm. This
- /// corresponds to the "small period" and "large period" cases.
- shift: Shift,
-}
-
-impl Finder {
- /// Create a searcher that finds occurrences of the given `needle`.
- ///
- /// An empty `needle` results in a match at every position in a haystack,
- /// including at `haystack.len()`.
- #[inline]
- pub fn new(needle: &[u8]) -> Finder {
- let byteset = ApproximateByteSet::new(needle);
- let min_suffix = Suffix::forward(needle, SuffixKind::Minimal);
- let max_suffix = Suffix::forward(needle, SuffixKind::Maximal);
- let (period_lower_bound, critical_pos) =
- if min_suffix.pos > max_suffix.pos {
- (min_suffix.period, min_suffix.pos)
- } else {
- (max_suffix.period, max_suffix.pos)
- };
- let shift = Shift::forward(needle, period_lower_bound, critical_pos);
- Finder(TwoWay { byteset, critical_pos, shift })
- }
-
- /// Returns the first occurrence of `needle` in the given `haystack`, or
- /// `None` if no such occurrence could be found.
- ///
- /// The `needle` given must be the same as the `needle` provided to
- /// [`Finder::new`].
- ///
- /// An empty `needle` results in a match at every position in a haystack,
- /// including at `haystack.len()`.
- #[inline]
- pub fn find(&self, haystack: &[u8], needle: &[u8]) -> Option<usize> {
- self.find_with_prefilter(None, haystack, needle)
- }
-
- /// This is like [`Finder::find`], but it accepts a prefilter for
- /// accelerating searches.
- ///
- /// Currently this is not exposed in the public API because, at the time
- /// of writing, I didn't want to spend time thinking about how to expose
- /// the prefilter infrastructure (if at all). If you have a compelling use
- /// case for exposing this routine, please create an issue. Do *not* open
- /// a PR that just exposes `Pre` and friends. Exporting this routine will
- /// require API design.
- #[inline(always)]
- pub(crate) fn find_with_prefilter(
- &self,
- pre: Option<Pre<'_>>,
- haystack: &[u8],
- needle: &[u8],
- ) -> Option<usize> {
- match self.0.shift {
- Shift::Small { period } => {
- self.find_small_imp(pre, haystack, needle, period)
- }
- Shift::Large { shift } => {
- self.find_large_imp(pre, haystack, needle, shift)
- }
- }
- }
-
- // Each of the two search implementations below can be accelerated by a
- // prefilter, but it is not always enabled. To avoid its overhead when
- // its disabled, we explicitly inline each search implementation based on
- // whether a prefilter will be used or not. The decision on which to use
- // is made in the parent meta searcher.
-
- #[inline(always)]
- fn find_small_imp(
- &self,
- mut pre: Option<Pre<'_>>,
- haystack: &[u8],
- needle: &[u8],
- period: usize,
- ) -> Option<usize> {
- let mut pos = 0;
- let mut shift = 0;
- let last_byte_pos = match needle.len().checked_sub(1) {
- None => return Some(pos),
- Some(last_byte) => last_byte,
- };
- while pos + needle.len() <= haystack.len() {
- let mut i = cmp::max(self.0.critical_pos, shift);
- if let Some(pre) = pre.as_mut() {
- if pre.is_effective() {
- pos += pre.find(&haystack[pos..])?;
- shift = 0;
- i = self.0.critical_pos;
- if pos + needle.len() > haystack.len() {
- return None;
- }
- }
- }
- if !self.0.byteset.contains(haystack[pos + last_byte_pos]) {
- pos += needle.len();
- shift = 0;
- continue;
- }
- while i < needle.len() && needle[i] == haystack[pos + i] {
- i += 1;
- }
- if i < needle.len() {
- pos += i - self.0.critical_pos + 1;
- shift = 0;
- } else {
- let mut j = self.0.critical_pos;
- while j > shift && needle[j] == haystack[pos + j] {
- j -= 1;
- }
- if j <= shift && needle[shift] == haystack[pos + shift] {
- return Some(pos);
- }
- pos += period;
- shift = needle.len() - period;
- }
- }
- None
- }
-
- #[inline(always)]
- fn find_large_imp(
- &self,
- mut pre: Option<Pre<'_>>,
- haystack: &[u8],
- needle: &[u8],
- shift: usize,
- ) -> Option<usize> {
- let mut pos = 0;
- let last_byte_pos = match needle.len().checked_sub(1) {
- None => return Some(pos),
- Some(last_byte) => last_byte,
- };
- 'outer: while pos + needle.len() <= haystack.len() {
- if let Some(pre) = pre.as_mut() {
- if pre.is_effective() {
- pos += pre.find(&haystack[pos..])?;
- if pos + needle.len() > haystack.len() {
- return None;
- }
- }
- }
-
- if !self.0.byteset.contains(haystack[pos + last_byte_pos]) {
- pos += needle.len();
- continue;
- }
- let mut i = self.0.critical_pos;
- while i < needle.len() && needle[i] == haystack[pos + i] {
- i += 1;
- }
- if i < needle.len() {
- pos += i - self.0.critical_pos + 1;
- } else {
- for j in (0..self.0.critical_pos).rev() {
- if needle[j] != haystack[pos + j] {
- pos += shift;
- continue 'outer;
- }
- }
- return Some(pos);
- }
- }
- None
- }
-}
-
-impl FinderRev {
- /// Create a searcher that finds occurrences of the given `needle`.
- ///
- /// An empty `needle` results in a match at every position in a haystack,
- /// including at `haystack.len()`.
- #[inline]
- pub fn new(needle: &[u8]) -> FinderRev {
- let byteset = ApproximateByteSet::new(needle);
- let min_suffix = Suffix::reverse(needle, SuffixKind::Minimal);
- let max_suffix = Suffix::reverse(needle, SuffixKind::Maximal);
- let (period_lower_bound, critical_pos) =
- if min_suffix.pos < max_suffix.pos {
- (min_suffix.period, min_suffix.pos)
- } else {
- (max_suffix.period, max_suffix.pos)
- };
- let shift = Shift::reverse(needle, period_lower_bound, critical_pos);
- FinderRev(TwoWay { byteset, critical_pos, shift })
- }
-
- /// Returns the last occurrence of `needle` in the given `haystack`, or
- /// `None` if no such occurrence could be found.
- ///
- /// The `needle` given must be the same as the `needle` provided to
- /// [`FinderRev::new`].
- ///
- /// An empty `needle` results in a match at every position in a haystack,
- /// including at `haystack.len()`.
- #[inline]
- pub fn rfind(&self, haystack: &[u8], needle: &[u8]) -> Option<usize> {
- // For the reverse case, we don't use a prefilter. It's plausible that
- // perhaps we should, but it's a lot of additional code to do it, and
- // it's not clear that it's actually worth it. If you have a really
- // compelling use case for this, please file an issue.
- match self.0.shift {
- Shift::Small { period } => {
- self.rfind_small_imp(haystack, needle, period)
- }
- Shift::Large { shift } => {
- self.rfind_large_imp(haystack, needle, shift)
- }
- }
- }
-
- #[inline(always)]
- fn rfind_small_imp(
- &self,
- haystack: &[u8],
- needle: &[u8],
- period: usize,
- ) -> Option<usize> {
- let nlen = needle.len();
- let mut pos = haystack.len();
- let mut shift = nlen;
- let first_byte = match needle.get(0) {
- None => return Some(pos),
- Some(&first_byte) => first_byte,
- };
- while pos >= nlen {
- if !self.0.byteset.contains(haystack[pos - nlen]) {
- pos -= nlen;
- shift = nlen;
- continue;
- }
- let mut i = cmp::min(self.0.critical_pos, shift);
- while i > 0 && needle[i - 1] == haystack[pos - nlen + i - 1] {
- i -= 1;
- }
- if i > 0 || first_byte != haystack[pos - nlen] {
- pos -= self.0.critical_pos - i + 1;
- shift = nlen;
- } else {
- let mut j = self.0.critical_pos;
- while j < shift && needle[j] == haystack[pos - nlen + j] {
- j += 1;
- }
- if j >= shift {
- return Some(pos - nlen);
- }
- pos -= period;
- shift = period;
- }
- }
- None
- }
-
- #[inline(always)]
- fn rfind_large_imp(
- &self,
- haystack: &[u8],
- needle: &[u8],
- shift: usize,
- ) -> Option<usize> {
- let nlen = needle.len();
- let mut pos = haystack.len();
- let first_byte = match needle.get(0) {
- None => return Some(pos),
- Some(&first_byte) => first_byte,
- };
- while pos >= nlen {
- if !self.0.byteset.contains(haystack[pos - nlen]) {
- pos -= nlen;
- continue;
- }
- let mut i = self.0.critical_pos;
- while i > 0 && needle[i - 1] == haystack[pos - nlen + i - 1] {
- i -= 1;
- }
- if i > 0 || first_byte != haystack[pos - nlen] {
- pos -= self.0.critical_pos - i + 1;
- } else {
- let mut j = self.0.critical_pos;
- while j < nlen && needle[j] == haystack[pos - nlen + j] {
- j += 1;
- }
- if j == nlen {
- return Some(pos - nlen);
- }
- pos -= shift;
- }
- }
- None
- }
-}
-
-/// A representation of the amount we're allowed to shift by during Two-Way
-/// search.
-///
-/// When computing a critical factorization of the needle, we find the position
-/// of the critical factorization by finding the needle's maximal (or minimal)
-/// suffix, along with the period of that suffix. It turns out that the period
-/// of that suffix is a lower bound on the period of the needle itself.
-///
-/// This lower bound is equivalent to the actual period of the needle in
-/// some cases. To describe that case, we denote the needle as `x` where
-/// `x = uv` and `v` is the lexicographic maximal suffix of `v`. The lower
-/// bound given here is always the period of `v`, which is `<= period(x)`. The
-/// case where `period(v) == period(x)` occurs when `len(u) < (len(x) / 2)` and
-/// where `u` is a suffix of `v[0..period(v)]`.
-///
-/// This case is important because the search algorithm for when the
-/// periods are equivalent is slightly different than the search algorithm
-/// for when the periods are not equivalent. In particular, when they aren't
-/// equivalent, we know that the period of the needle is no less than half its
-/// length. In this case, we shift by an amount less than or equal to the
-/// period of the needle (determined by the maximum length of the components
-/// of the critical factorization of `x`, i.e., `max(len(u), len(v))`)..
-///
-/// The above two cases are represented by the variants below. Each entails
-/// a different instantiation of the Two-Way search algorithm.
-///
-/// N.B. If we could find a way to compute the exact period in all cases,
-/// then we could collapse this case analysis and simplify the algorithm. The
-/// Two-Way paper suggests this is possible, but more reading is required to
-/// grok why the authors didn't pursue that path.
-#[derive(Clone, Copy, Debug)]
-enum Shift {
- Small { period: usize },
- Large { shift: usize },
-}
-
-impl Shift {
- /// Compute the shift for a given needle in the forward direction.
- ///
- /// This requires a lower bound on the period and a critical position.
- /// These can be computed by extracting both the minimal and maximal
- /// lexicographic suffixes, and choosing the right-most starting position.
- /// The lower bound on the period is then the period of the chosen suffix.
- fn forward(
- needle: &[u8],
- period_lower_bound: usize,
- critical_pos: usize,
- ) -> Shift {
- let large = cmp::max(critical_pos, needle.len() - critical_pos);
- if critical_pos * 2 >= needle.len() {
- return Shift::Large { shift: large };
- }
-
- let (u, v) = needle.split_at(critical_pos);
- if !is_suffix(&v[..period_lower_bound], u) {
- return Shift::Large { shift: large };
- }
- Shift::Small { period: period_lower_bound }
- }
-
- /// Compute the shift for a given needle in the reverse direction.
- ///
- /// This requires a lower bound on the period and a critical position.
- /// These can be computed by extracting both the minimal and maximal
- /// lexicographic suffixes, and choosing the left-most starting position.
- /// The lower bound on the period is then the period of the chosen suffix.
- fn reverse(
- needle: &[u8],
- period_lower_bound: usize,
- critical_pos: usize,
- ) -> Shift {
- let large = cmp::max(critical_pos, needle.len() - critical_pos);
- if (needle.len() - critical_pos) * 2 >= needle.len() {
- return Shift::Large { shift: large };
- }
-
- let (v, u) = needle.split_at(critical_pos);
- if !is_prefix(&v[v.len() - period_lower_bound..], u) {
- return Shift::Large { shift: large };
- }
- Shift::Small { period: period_lower_bound }
- }
-}
-
-/// A suffix extracted from a needle along with its period.
-#[derive(Debug)]
-struct Suffix {
- /// The starting position of this suffix.
- ///
- /// If this is a forward suffix, then `&bytes[pos..]` can be used. If this
- /// is a reverse suffix, then `&bytes[..pos]` can be used. That is, for
- /// forward suffixes, this is an inclusive starting position, where as for
- /// reverse suffixes, this is an exclusive ending position.
- pos: usize,
- /// The period of this suffix.
- ///
- /// Note that this is NOT necessarily the period of the string from which
- /// this suffix comes from. (It is always less than or equal to the period
- /// of the original string.)
- period: usize,
-}
-
-impl Suffix {
- fn forward(needle: &[u8], kind: SuffixKind) -> Suffix {
- // suffix represents our maximal (or minimal) suffix, along with
- // its period.
- let mut suffix = Suffix { pos: 0, period: 1 };
- // The start of a suffix in `needle` that we are considering as a
- // more maximal (or minimal) suffix than what's in `suffix`.
- let mut candidate_start = 1;
- // The current offset of our suffixes that we're comparing.
- //
- // When the characters at this offset are the same, then we mush on
- // to the next position since no decision is possible. When the
- // candidate's character is greater (or lesser) than the corresponding
- // character than our current maximal (or minimal) suffix, then the
- // current suffix is changed over to the candidate and we restart our
- // search. Otherwise, the candidate suffix is no good and we restart
- // our search on the next candidate.
- //
- // The three cases above correspond to the three cases in the loop
- // below.
- let mut offset = 0;
-
- while candidate_start + offset < needle.len() {
- let current = needle[suffix.pos + offset];
- let candidate = needle[candidate_start + offset];
- match kind.cmp(current, candidate) {
- SuffixOrdering::Accept => {
- suffix = Suffix { pos: candidate_start, period: 1 };
- candidate_start += 1;
- offset = 0;
- }
- SuffixOrdering::Skip => {
- candidate_start += offset + 1;
- offset = 0;
- suffix.period = candidate_start - suffix.pos;
- }
- SuffixOrdering::Push => {
- if offset + 1 == suffix.period {
- candidate_start += suffix.period;
- offset = 0;
- } else {
- offset += 1;
- }
- }
- }
- }
- suffix
- }
-
- fn reverse(needle: &[u8], kind: SuffixKind) -> Suffix {
- // See the comments in `forward` for how this works.
- let mut suffix = Suffix { pos: needle.len(), period: 1 };
- if needle.len() == 1 {
- return suffix;
- }
- let mut candidate_start = match needle.len().checked_sub(1) {
- None => return suffix,
- Some(candidate_start) => candidate_start,
- };
- let mut offset = 0;
-
- while offset < candidate_start {
- let current = needle[suffix.pos - offset - 1];
- let candidate = needle[candidate_start - offset - 1];
- match kind.cmp(current, candidate) {
- SuffixOrdering::Accept => {
- suffix = Suffix { pos: candidate_start, period: 1 };
- candidate_start -= 1;
- offset = 0;
- }
- SuffixOrdering::Skip => {
- candidate_start -= offset + 1;
- offset = 0;
- suffix.period = suffix.pos - candidate_start;
- }
- SuffixOrdering::Push => {
- if offset + 1 == suffix.period {
- candidate_start -= suffix.period;
- offset = 0;
- } else {
- offset += 1;
- }
- }
- }
- }
- suffix
- }
-}
-
-/// The kind of suffix to extract.
-#[derive(Clone, Copy, Debug)]
-enum SuffixKind {
- /// Extract the smallest lexicographic suffix from a string.
- ///
- /// Technically, this doesn't actually pick the smallest lexicographic
- /// suffix. e.g., Given the choice between `a` and `aa`, this will choose
- /// the latter over the former, even though `a < aa`. The reasoning for
- /// this isn't clear from the paper, but it still smells like a minimal
- /// suffix.
- Minimal,
- /// Extract the largest lexicographic suffix from a string.
- ///
- /// Unlike `Minimal`, this really does pick the maximum suffix. e.g., Given
- /// the choice between `z` and `zz`, this will choose the latter over the
- /// former.
- Maximal,
-}
-
-/// The result of comparing corresponding bytes between two suffixes.
-#[derive(Clone, Copy, Debug)]
-enum SuffixOrdering {
- /// This occurs when the given candidate byte indicates that the candidate
- /// suffix is better than the current maximal (or minimal) suffix. That is,
- /// the current candidate suffix should supplant the current maximal (or
- /// minimal) suffix.
- Accept,
- /// This occurs when the given candidate byte excludes the candidate suffix
- /// from being better than the current maximal (or minimal) suffix. That
- /// is, the current candidate suffix should be dropped and the next one
- /// should be considered.
- Skip,
- /// This occurs when no decision to accept or skip the candidate suffix
- /// can be made, e.g., when corresponding bytes are equivalent. In this
- /// case, the next corresponding bytes should be compared.
- Push,
-}
-
-impl SuffixKind {
- /// Returns true if and only if the given candidate byte indicates that
- /// it should replace the current suffix as the maximal (or minimal)
- /// suffix.
- fn cmp(self, current: u8, candidate: u8) -> SuffixOrdering {
- use self::SuffixOrdering::*;
-
- match self {
- SuffixKind::Minimal if candidate < current => Accept,
- SuffixKind::Minimal if candidate > current => Skip,
- SuffixKind::Minimal => Push,
- SuffixKind::Maximal if candidate > current => Accept,
- SuffixKind::Maximal if candidate < current => Skip,
- SuffixKind::Maximal => Push,
- }
- }
-}
-
-/// A bitset used to track whether a particular byte exists in a needle or not.
-///
-/// Namely, bit 'i' is set if and only if byte%64==i for any byte in the
-/// needle. If a particular byte in the haystack is NOT in this set, then one
-/// can conclude that it is also not in the needle, and thus, one can advance
-/// in the haystack by needle.len() bytes.
-#[derive(Clone, Copy, Debug)]
-struct ApproximateByteSet(u64);
-
-impl ApproximateByteSet {
- /// Create a new set from the given needle.
- fn new(needle: &[u8]) -> ApproximateByteSet {
- let mut bits = 0;
- for &b in needle {
- bits |= 1 << (b % 64);
- }
- ApproximateByteSet(bits)
- }
-
- /// Return true if and only if the given byte might be in this set. This
- /// may return a false positive, but will never return a false negative.
- #[inline(always)]
- fn contains(&self, byte: u8) -> bool {
- self.0 & (1 << (byte % 64)) != 0
- }
-}
-
-#[cfg(test)]
-mod tests {
- use alloc::vec::Vec;
-
- use super::*;
-
- /// Convenience wrapper for computing the suffix as a byte string.
- fn get_suffix_forward(needle: &[u8], kind: SuffixKind) -> (&[u8], usize) {
- let s = Suffix::forward(needle, kind);
- (&needle[s.pos..], s.period)
- }
-
- /// Convenience wrapper for computing the reverse suffix as a byte string.
- fn get_suffix_reverse(needle: &[u8], kind: SuffixKind) -> (&[u8], usize) {
- let s = Suffix::reverse(needle, kind);
- (&needle[..s.pos], s.period)
- }
-
- /// Return all of the non-empty suffixes in the given byte string.
- fn suffixes(bytes: &[u8]) -> Vec<&[u8]> {
- (0..bytes.len()).map(|i| &bytes[i..]).collect()
- }
-
- /// Return the lexicographically maximal suffix of the given byte string.
- fn naive_maximal_suffix_forward(needle: &[u8]) -> &[u8] {
- let mut sufs = suffixes(needle);
- sufs.sort();
- sufs.pop().unwrap()
- }
-
- /// Return the lexicographically maximal suffix of the reverse of the given
- /// byte string.
- fn naive_maximal_suffix_reverse(needle: &[u8]) -> Vec<u8> {
- let mut reversed = needle.to_vec();
- reversed.reverse();
- let mut got = naive_maximal_suffix_forward(&reversed).to_vec();
- got.reverse();
- got
- }
-
- define_substring_forward_quickcheck!(|h, n| Some(
- Finder::new(n).find(h, n)
- ));
- define_substring_reverse_quickcheck!(|h, n| Some(
- FinderRev::new(n).rfind(h, n)
- ));
-
- #[test]
- fn forward() {
- crate::tests::substring::Runner::new()
- .fwd(|h, n| Some(Finder::new(n).find(h, n)))
- .run();
- }
-
- #[test]
- fn reverse() {
- crate::tests::substring::Runner::new()
- .rev(|h, n| Some(FinderRev::new(n).rfind(h, n)))
- .run();
- }
-
- #[test]
- fn suffix_forward() {
- macro_rules! assert_suffix_min {
- ($given:expr, $expected:expr, $period:expr) => {
- let (got_suffix, got_period) =
- get_suffix_forward($given.as_bytes(), SuffixKind::Minimal);
- let got_suffix = core::str::from_utf8(got_suffix).unwrap();
- assert_eq!(($expected, $period), (got_suffix, got_period));
- };
- }
-
- macro_rules! assert_suffix_max {
- ($given:expr, $expected:expr, $period:expr) => {
- let (got_suffix, got_period) =
- get_suffix_forward($given.as_bytes(), SuffixKind::Maximal);
- let got_suffix = core::str::from_utf8(got_suffix).unwrap();
- assert_eq!(($expected, $period), (got_suffix, got_period));
- };
- }
-
- assert_suffix_min!("a", "a", 1);
- assert_suffix_max!("a", "a", 1);
-
- assert_suffix_min!("ab", "ab", 2);
- assert_suffix_max!("ab", "b", 1);
-
- assert_suffix_min!("ba", "a", 1);
- assert_suffix_max!("ba", "ba", 2);
-
- assert_suffix_min!("abc", "abc", 3);
- assert_suffix_max!("abc", "c", 1);
-
- assert_suffix_min!("acb", "acb", 3);
- assert_suffix_max!("acb", "cb", 2);
-
- assert_suffix_min!("cba", "a", 1);
- assert_suffix_max!("cba", "cba", 3);
-
- assert_suffix_min!("abcabc", "abcabc", 3);
- assert_suffix_max!("abcabc", "cabc", 3);
-
- assert_suffix_min!("abcabcabc", "abcabcabc", 3);
- assert_suffix_max!("abcabcabc", "cabcabc", 3);
-
- assert_suffix_min!("abczz", "abczz", 5);
- assert_suffix_max!("abczz", "zz", 1);
-
- assert_suffix_min!("zzabc", "abc", 3);
- assert_suffix_max!("zzabc", "zzabc", 5);
-
- assert_suffix_min!("aaa", "aaa", 1);
- assert_suffix_max!("aaa", "aaa", 1);
-
- assert_suffix_min!("foobar", "ar", 2);
- assert_suffix_max!("foobar", "r", 1);
- }
-
- #[test]
- fn suffix_reverse() {
- macro_rules! assert_suffix_min {
- ($given:expr, $expected:expr, $period:expr) => {
- let (got_suffix, got_period) =
- get_suffix_reverse($given.as_bytes(), SuffixKind::Minimal);
- let got_suffix = core::str::from_utf8(got_suffix).unwrap();
- assert_eq!(($expected, $period), (got_suffix, got_period));
- };
- }
-
- macro_rules! assert_suffix_max {
- ($given:expr, $expected:expr, $period:expr) => {
- let (got_suffix, got_period) =
- get_suffix_reverse($given.as_bytes(), SuffixKind::Maximal);
- let got_suffix = core::str::from_utf8(got_suffix).unwrap();
- assert_eq!(($expected, $period), (got_suffix, got_period));
- };
- }
-
- assert_suffix_min!("a", "a", 1);
- assert_suffix_max!("a", "a", 1);
-
- assert_suffix_min!("ab", "a", 1);
- assert_suffix_max!("ab", "ab", 2);
-
- assert_suffix_min!("ba", "ba", 2);
- assert_suffix_max!("ba", "b", 1);
-
- assert_suffix_min!("abc", "a", 1);
- assert_suffix_max!("abc", "abc", 3);
-
- assert_suffix_min!("acb", "a", 1);
- assert_suffix_max!("acb", "ac", 2);
-
- assert_suffix_min!("cba", "cba", 3);
- assert_suffix_max!("cba", "c", 1);
-
- assert_suffix_min!("abcabc", "abca", 3);
- assert_suffix_max!("abcabc", "abcabc", 3);
-
- assert_suffix_min!("abcabcabc", "abcabca", 3);
- assert_suffix_max!("abcabcabc", "abcabcabc", 3);
-
- assert_suffix_min!("abczz", "a", 1);
- assert_suffix_max!("abczz", "abczz", 5);
-
- assert_suffix_min!("zzabc", "zza", 3);
- assert_suffix_max!("zzabc", "zz", 1);
-
- assert_suffix_min!("aaa", "aaa", 1);
- assert_suffix_max!("aaa", "aaa", 1);
- }
-
- #[cfg(not(miri))]
- quickcheck::quickcheck! {
- fn qc_suffix_forward_maximal(bytes: Vec<u8>) -> bool {
- if bytes.is_empty() {
- return true;
- }
-
- let (got, _) = get_suffix_forward(&bytes, SuffixKind::Maximal);
- let expected = naive_maximal_suffix_forward(&bytes);
- got == expected
- }
-
- fn qc_suffix_reverse_maximal(bytes: Vec<u8>) -> bool {
- if bytes.is_empty() {
- return true;
- }
-
- let (got, _) = get_suffix_reverse(&bytes, SuffixKind::Maximal);
- let expected = naive_maximal_suffix_reverse(&bytes);
- expected == got
- }
- }
-
- // This is a regression test caught by quickcheck that exercised a bug in
- // the reverse small period handling. The bug was that we were using 'if j
- // == shift' to determine if a match occurred, but the correct guard is 'if
- // j >= shift', which matches the corresponding guard in the forward impl.
- #[test]
- fn regression_rev_small_period() {
- let rfind = |h, n| FinderRev::new(n).rfind(h, n);
- let haystack = "ababaz";
- let needle = "abab";
- assert_eq!(Some(0), rfind(haystack.as_bytes(), needle.as_bytes()));
- }
-}
Copyright © 2024 Valentin A. Popov. All Rights Reverse Engineered.