src/arch/all/packedpair/mod.rs - platform/external/rust/crates/memchr - Git at Google

 /*!
 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()
     }
 }
	/*!
	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()
	}
	}