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