1 use memchr::{memchr, memchr2, memchr3, memrchr, memrchr2, memrchr3};
2 
3 mod scalar;
4 
5 #[inline]
build_table(byteset: &[u8]) -> [u8; 256]6 fn build_table(byteset: &[u8]) -> [u8; 256] {
7     let mut table = [0u8; 256];
8     for &b in byteset {
9         table[b as usize] = 1;
10     }
11     table
12 }
13 
14 #[inline]
find(haystack: &[u8], byteset: &[u8]) -> Option<usize>15 pub(crate) fn find(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
16     match byteset.len() {
17         0 => return None,
18         1 => memchr(byteset[0], haystack),
19         2 => memchr2(byteset[0], byteset[1], haystack),
20         3 => memchr3(byteset[0], byteset[1], byteset[2], haystack),
21         _ => {
22             let table = build_table(byteset);
23             scalar::forward_search_bytes(haystack, |b| table[b as usize] != 0)
24         }
25     }
26 }
27 
28 #[inline]
rfind(haystack: &[u8], byteset: &[u8]) -> Option<usize>29 pub(crate) fn rfind(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
30     match byteset.len() {
31         0 => return None,
32         1 => memrchr(byteset[0], haystack),
33         2 => memrchr2(byteset[0], byteset[1], haystack),
34         3 => memrchr3(byteset[0], byteset[1], byteset[2], haystack),
35         _ => {
36             let table = build_table(byteset);
37             scalar::reverse_search_bytes(haystack, |b| table[b as usize] != 0)
38         }
39     }
40 }
41 
42 #[inline]
find_not(haystack: &[u8], byteset: &[u8]) -> Option<usize>43 pub(crate) fn find_not(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
44     if haystack.is_empty() {
45         return None;
46     }
47     match byteset.len() {
48         0 => return Some(0),
49         1 => scalar::inv_memchr(byteset[0], haystack),
50         2 => scalar::forward_search_bytes(haystack, |b| {
51             b != byteset[0] && b != byteset[1]
52         }),
53         3 => scalar::forward_search_bytes(haystack, |b| {
54             b != byteset[0] && b != byteset[1] && b != byteset[2]
55         }),
56         _ => {
57             let table = build_table(byteset);
58             scalar::forward_search_bytes(haystack, |b| table[b as usize] == 0)
59         }
60     }
61 }
62 #[inline]
rfind_not(haystack: &[u8], byteset: &[u8]) -> Option<usize>63 pub(crate) fn rfind_not(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
64     if haystack.is_empty() {
65         return None;
66     }
67     match byteset.len() {
68         0 => return Some(haystack.len() - 1),
69         1 => scalar::inv_memrchr(byteset[0], haystack),
70         2 => scalar::reverse_search_bytes(haystack, |b| {
71             b != byteset[0] && b != byteset[1]
72         }),
73         3 => scalar::reverse_search_bytes(haystack, |b| {
74             b != byteset[0] && b != byteset[1] && b != byteset[2]
75         }),
76         _ => {
77             let table = build_table(byteset);
78             scalar::reverse_search_bytes(haystack, |b| table[b as usize] == 0)
79         }
80     }
81 }
82 
83 #[cfg(all(test, feature = "std", not(miri)))]
84 mod tests {
85     quickcheck::quickcheck! {
86         fn qc_byteset_forward_matches_naive(
87             haystack: Vec<u8>,
88             needles: Vec<u8>
89         ) -> bool {
90             super::find(&haystack, &needles)
91                 == haystack.iter().position(|b| needles.contains(b))
92         }
93         fn qc_byteset_backwards_matches_naive(
94             haystack: Vec<u8>,
95             needles: Vec<u8>
96         ) -> bool {
97             super::rfind(&haystack, &needles)
98                 == haystack.iter().rposition(|b| needles.contains(b))
99         }
100         fn qc_byteset_forward_not_matches_naive(
101             haystack: Vec<u8>,
102             needles: Vec<u8>
103         ) -> bool {
104             super::find_not(&haystack, &needles)
105                 == haystack.iter().position(|b| !needles.contains(b))
106         }
107         fn qc_byteset_backwards_not_matches_naive(
108             haystack: Vec<u8>,
109             needles: Vec<u8>
110         ) -> bool {
111             super::rfind_not(&haystack, &needles)
112                 == haystack.iter().rposition(|b| !needles.contains(b))
113         }
114     }
115 }
116