1 use memchr::{memchr, memchr2, memchr3, memrchr, memrchr2, memrchr3};
2 mod scalar;
3 
4 #[inline]
build_table(byteset: &[u8]) -> [u8; 256]5 fn build_table(byteset: &[u8]) -> [u8; 256] {
6     let mut table = [0u8; 256];
7     for &b in byteset {
8         table[b as usize] = 1;
9     }
10     table
11 }
12 
13 #[inline]
find(haystack: &[u8], byteset: &[u8]) -> Option<usize>14 pub(crate) fn find(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
15     match byteset.len() {
16         0 => return None,
17         1 => memchr(byteset[0], haystack),
18         2 => memchr2(byteset[0], byteset[1], haystack),
19         3 => memchr3(byteset[0], byteset[1], byteset[2], haystack),
20         _ => {
21             let table = build_table(byteset);
22             scalar::forward_search_bytes(haystack, |b| table[b as usize] != 0)
23         }
24     }
25 }
26 
27 #[inline]
rfind(haystack: &[u8], byteset: &[u8]) -> Option<usize>28 pub(crate) fn rfind(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
29     match byteset.len() {
30         0 => return None,
31         1 => memrchr(byteset[0], haystack),
32         2 => memrchr2(byteset[0], byteset[1], haystack),
33         3 => memrchr3(byteset[0], byteset[1], byteset[2], haystack),
34         _ => {
35             let table = build_table(byteset);
36             scalar::reverse_search_bytes(haystack, |b| table[b as usize] != 0)
37         }
38     }
39 }
40 
41 #[inline]
find_not(haystack: &[u8], byteset: &[u8]) -> Option<usize>42 pub(crate) fn find_not(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
43     if haystack.is_empty() {
44         return None;
45     }
46     match byteset.len() {
47         0 => return Some(0),
48         1 => scalar::inv_memchr(byteset[0], haystack),
49         2 => scalar::forward_search_bytes(haystack, |b| {
50             b != byteset[0] && b != byteset[1]
51         }),
52         3 => scalar::forward_search_bytes(haystack, |b| {
53             b != byteset[0] && b != byteset[1] && b != byteset[2]
54         }),
55         _ => {
56             let table = build_table(byteset);
57             scalar::forward_search_bytes(haystack, |b| table[b as usize] == 0)
58         }
59     }
60 }
61 #[inline]
rfind_not(haystack: &[u8], byteset: &[u8]) -> Option<usize>62 pub(crate) fn rfind_not(haystack: &[u8], byteset: &[u8]) -> Option<usize> {
63     if haystack.is_empty() {
64         return None;
65     }
66     match byteset.len() {
67         0 => return Some(haystack.len() - 1),
68         1 => scalar::inv_memrchr(byteset[0], haystack),
69         2 => scalar::reverse_search_bytes(haystack, |b| {
70             b != byteset[0] && b != byteset[1]
71         }),
72         3 => scalar::reverse_search_bytes(haystack, |b| {
73             b != byteset[0] && b != byteset[1] && b != byteset[2]
74         }),
75         _ => {
76             let table = build_table(byteset);
77             scalar::reverse_search_bytes(haystack, |b| table[b as usize] == 0)
78         }
79     }
80 }
81 
82 #[cfg(test)]
83 mod tests {
84 
85     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