diff options
Diffstat (limited to 'vendor/memchr/src/arch/all/packedpair/mod.rs')
| -rw-r--r-- | vendor/memchr/src/arch/all/packedpair/mod.rs | 359 |
1 files changed, 0 insertions, 359 deletions
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() - } -} |