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     quickcheck::quickcheck! {
85         fn qc_byteset_forward_matches_naive(
86             haystack: Vec<u8>,
87             needles: Vec<u8>
88         ) -> bool {
89             super::find(&haystack, &needles)
90                 == haystack.iter().position(|b| needles.contains(b))
91         }
92         fn qc_byteset_backwards_matches_naive(
93             haystack: Vec<u8>,
94             needles: Vec<u8>
95         ) -> bool {
96             super::rfind(&haystack, &needles)
97                 == haystack.iter().rposition(|b| needles.contains(b))
98         }
99         fn qc_byteset_forward_not_matches_naive(
100             haystack: Vec<u8>,
101             needles: Vec<u8>
102         ) -> bool {
103             super::find_not(&haystack, &needles)
104                 == haystack.iter().position(|b| !needles.contains(b))
105         }
106         fn qc_byteset_backwards_not_matches_naive(
107             haystack: Vec<u8>,
108             needles: Vec<u8>
109         ) -> bool {
110             super::rfind_not(&haystack, &needles)
111                 == haystack.iter().rposition(|b| !needles.contains(b))
112         }
113     }
114 }
115